ThreadSafePriorityQueue
Engine/source/platform/threads/threadSafePriorityQueue.h
Fast, lock-free priority queue implementation for concurrent access.
Classes:
A queue node.
Protected Types
NodePtr
Public Friends
struct
Public Functions
Construct an empty queue.
bool
isEmpty()
Return true if the queue does not currently contain an item.
Protected Functions
Detailed Description
Fast, lock-free priority queue implementation for concurrent access.
Equal priorities are allowed and are placed before existing items of identical priority in the queue.
Based on (but with significant deviations from) "Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems" by Hakan Sundell and Philippas Tsigas. Parts of the skiplist code is based on work by William Pugh.
Parameters:
| T | The item value type. Must have a default constructor. |
| K | The priority key type. Must be comparable, have a default constructor, and be a valid template parameter to TypeTraits. |
| SORT_MIN_TO_MAX | If true, the queue sorts from minimum to maximum priority or the reverse if false. |
| MAX_LEVEL | The number of levels a node can have at most. |
| PROBABILISTIC_BIAS | The probabilistic level distribution factor for the skiplist. Multiplied by 100 and turned into int to conform to restrictions on non-type template parameters. |
Public Types
@141
Enumerator
- MAX_LEVEL_CONST = MAX_LEVEL
typedef K KeyType
typedef T ValueType
Protected Types
typedef ThreadSafeRef< Node > NodePtr
Public Friends
Protected Attributes
NodePtr mHead
Artificial head node.
NodePtr mTail
Artificial tail node.
Public Functions
ThreadSafePriorityQueue()
Construct an empty queue.
Internally, this creates a head node with maximal priority and a tail node with minimal priority, both at maximum level.
insert(KeyType priority, const T & value)
Insert the given value into the queue at the place determined by the given priority.
isEmpty()
Return true if the queue does not currently contain an item.
takeNext(T & outValue, KeyType upToPriority)
Take the item with the highest priority from the queue.
Parameters:
| outValue | Reference to where the resulting value should be stored. |
| upToPriority | Priority limit (inclusive) up to which items are taken from the queue. |
true if there was a matching item in the queue.
Protected Functions
helpDelete()
insert(KeyType priority, const T & value, NodePtr & outResult)
readNext(NodePtr & refPrev, NodePtr & refNext, U32 level)
Update the given references to the next non-deleted node at the given level.
refPrev will be updated to reference the immediate predecessor of the next node returned. Note that this can be a node in deleted state.
Parameters:
| refPrev | Reference to a node of which the successor node should be returned. Updated to immediate predecessor of refNext on return. |
| refNext | Reference to update to refer to next non-deleted node on the given level. |
| level | Skiplist level to operate on. |
scan(NodePtr & refPrev, NodePtr & refNext, U32 level, KeyType priority)
Scan for the position at which to insert a node of the given priority.
Upon return, the position between refPrev and refNext is the one to insert at.
Parameters:
| refPrev | position at which to start scanning; updated to match insert position. |
| refNext |
scanFromHead(NodePtr & refPrev, NodePtr & refNext, U32 level, KeyType priority)