Interlocked Singly Linked Lists
An interlocked singly linked list (SList) eases the task of insertion and deletion from a linked list. SLists are implemented using a nonblocking algorithm to provide atomic synchronization, increase system performance, and avoid problems such as priority inversion and lock convoys.
SLists are straightforward to implement and use in 32-bit code. However, it is challenging to implement them in 64-bit code because the amount of data exchangeable by the native interlocked exchange primitives is not double the address size, as it is in 32-bit code. Therefore, SLists enable porting high-end scalable algorithms to Windows.
Applications can use SLists by calling the InitializeSListHead function to initialize the head of the list. To insert items into the list, use the InterlockedPushEntrySList function. To delete items from the list, use the InterlockedPopEntrySList function.
All list items must be aligned on a MEMORY_ALLOCATION_ALIGNMENT boundary. Unaligned items can cause unpredictable results. See _aligned_malloc.
For an example, see Using Singly Linked Lists.
The following table lists the SList functions.
| Function | Description |
|---|---|
| InitializeSListHead | Initializes the head of a singly linked list. |
| InterlockedFlushSList | Flushes the entire list of items in a singly linked list. |
| InterlockedPopEntrySList | Removes an item from the front of a singly linked list. |
| InterlockedPushEntrySList | Inserts an item at the front of a singly linked list. |
| QueryDepthSList | Retrieves the number of entries in the specified singly linked list. |
Send comments about this topic to Microsoft
Build date: 3/7/2012
