Edit

Interlocked Singly Linked Lists

  • Article

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.

Windows 8: Starting in Windows 8 the appropriate native interlocked exchange primitives are available for 64-bit code, for example InterlockedCompare64Exchange128.

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.
InterlockedPushListSList Inserts a singly-linked list at the front of another singly linked list.
InterlockedPushListSListEx Inserts a singly-linked list at the front of another singly linked list. This version of the method does not use the __fastcall calling convention.
RtlFirstEntrySList Retrieves the first entry in a singly linked list.
QueryDepthSList Retrieves the number of entries in the specified singly linked list.