ThreadSafePriorityQueue::Node
Engine/source/platform/threads/threadSafePriorityQueue.h
A queue node.
Classes:
Public Types
Parent
Private Attributes
Private Static Attributes
FreeList
smFreeLists [MAX_LEVEL]
Public Functions
~Node()
bool
Return true if the node is marked to be deleted.
operator delete(void * ptr)
Reclaim a node.
void *
operator new(size_t size, S32 level)
Allocate a new node.
bool
Attempt to mark the node for deletion.
Public Static Functions
Choose a random level.
Detailed Description
A queue node.
Nodes are reference-counted to coordinate memory management between the different threads. Reclamation happens on the thread that releases the last reference.
Reference-counting and deletion requests are kept separate. A given node is marked for deletion and will then have its references progressively disappear and eventually be reclaimed once the reference count drops to zero.
Note that 'Next' references are released by the destructor which is only called when the reference count to the node itself drops to zero. This is to avoid threads getting trapped in a node with no link out.
Public Types
typedef ThreadSafeRefCount< Node > Parent
Private Attributes
U32 mLevel
Level count and deletion bit (highest).
Node * mNext [1]
Variable-sized array of next pointers.
KeyType mPriority
Priority key.
ValueType mValue
Private Static Attributes
FreeList smFreeLists [MAX_LEVEL]
Public Functions
Node(KeyType priority, const ValueType & value)
~Node()
clearValue()
getLevel()
Return the skip list level the node is at.
getNext(U32 level)
Return the successor node at the given level.
Parameters:
| level | The level of the desired successor node; must be within the node's level bounds. |
getPriority()
getValue()
isMarkedForDeletion()
Return true if the node is marked to be deleted.
operator delete(void * ptr)
Reclaim a node.
Parameters:
| node | The node to reclaim. Must refer to a Node instance. |
operator new(size_t size, S32 level)
Allocate a new node.
The node comes with a reference count of one and its level already set.
Parameters:
| level | The level to allocate the node at. If this is -1, a random level is chosen. |
a new node.
tryMarkForDeletion()
Attempt to mark the node for deletion.
If the mark bit has not yet been set and setting it on the current thread succeeds, returns true.
true, if the marking succeeded.
Public Static Functions
randomLevel()
Choose a random level.
The chosen level depends on the given PROBABILISTIC_BIAS and MAX_LEVEL, but is not affected by the actual number of nodes in a queue.