Singly Linked Lists

The system provides built-in support for singly linked lists using SINGLE_LIST_ENTRY structures. Each SINGLE_LIST_ENTRY structure contains a single Next member.

The system uses the SINGLE_LIST_ENTRY structure in two different roles:

• A SINGLE_LIST_ENTRY can represent the head of the list. In this case, the Next pointer points to the first entry of the list.
• A SINGLE_LIST_ENTRY can represent an entry in the list. In this case, the Next pointer points to the next entry of the list, or NULL if this entry is the last in the list.

The routines that manipulate a singly linked list take a pointer to a SINGLE_LIST_ENTRY that represents the list head. They update the Next pointer so that it points to the first entry of the list after the operation.

Suppose that the ListHead variable is a pointer to the SINGLE_LIST_ENTRY structure that represents the list head. A driver manipulates ListHead as follows:

• To initialize the list as empty, set ListHead->Next to be NULL.
• To add a new entry to the list, allocate a SINGLE_LIST_ENTRY to represent the new entry, and then call PushEntryList to add the entry to beginning of the list.
• Pop the first entry off the list by using PopEntryList.

A SINGLE_LIST_ENTRY, by itself, only has a Next member. To store your own data in the lists, embed the SINGLE_LIST_ENTRY as a member of the structure that describes the list entry, as follows.

typedef struct {
  // driver-defined members
  .
  .
  .
  SINGLE_LIST_ENTRY SingleListEntry;
  
  // other driver-defined members
  .
  .
  .
} XXX_ENTRY;

To add a new entry to the list, allocate an XXX_ENTRY structure, and then pass a pointer to the SingleListEntry member to PushEntryList. To convert a pointer to the SINGLE_LIST_ENTRY back to an XXX_ENTRY, use CONTAINING_RECORD. Here is an example of routines that insert and remove driver-defined entries from a singly linked list.

typedef struct {
  PVOID DriverData1;
  SINGLE_LIST_ENTRY SingleListEntry;
  ULONG DriverData2;
} XXX_ENTRY, *PXXX_ENTRY;

void
PushXxxEntry(PSINGLE_LIST_ENTRY ListHead, PXXX_ENTRY Entry)
{
    PushEntryList(ListHead, &(Entry->SingleListEntry));
}

PXXX_ENTRY
PopXxxEntry(PSINGLE_LIST_ENTRY ListHead)
{
    PSINGLE_LIST_ENTRY SingleListEntry;
    SingleListEntry = PopEntryList(ListHead);
    return CONTAINING_RECORD(SingleListEntry, XXX_ENTRY, SingleListEntry);
}

The system also provides atomic versions of the list operations, ExInterlockedPopEntryList and ExInterlockedPushEntryList. Each takes an additional spin lock parameter. The routine acquires the spin lock before it updates the list, and then the routine releases the spin lock after the operation is completed. Each operation on the list must use the same spin lock to ensure that each such operation on the list is synchronized with every other operation. You must use the spin lock only with the ExInterlockedXxxList routines. Do not use the spin lock for any other purpose. Drivers can use the same lock for multiple lists, but this behavior increases lock contention so drivers should avoid it.

Do not mix calls to the atomic and non-atomic versions of the list operations on the same list. If the atomic and non-atomic versions are run simultaneously on the same list, the data structure might become corrupted and the computer might stop responding or bug check (that is, crash). (You cannot acquire the spin lock while calling the non-atomic routine as an alternative to mixing calls to atomic and non-atomic versions of list operations. Using the spin lock in this fashion is not supported and might still cause list corruption.)

The system also provides an alternative implementation of atomic singly linked lists that is more efficient. For more information, see Sequenced Singly Linked Lists.

Doubly Linked Lists

The system provides built-in support for doubly linked lists using LIST_ENTRY structures. Each LIST_ENTRY structure contains an Flink and Blink member.

The system uses the LIST_ENTRY structure in two different roles:

• A LIST_ENTRY can represent the head of the list. In this case, the Flink pointer points to the first entry of the list and the Blink member points to the last entry of the list. If the list is empty, then Flink and Blink of the list head point to the list head itself.
• A LIST_ENTRY can represent an entry in the list. In this case, the Flink pointer points to the next entry of the list, and the Blink pointer points to the previous entry of the list. (If the entry is the last one in the list, then Flink points to the list head. Likewise if the entry is the first one in the list then Blink points to the list head.)

(While these rules may seem surprising at first glance, they allow the list insert and removal operations to implemented with no conditional code branches.)

The routines that manipulate a doubly linked list take a pointer to a LIST_ENTRY that represents the list head. They update the Flink and Blink pointers so that they point to the first and last entry of the list after the operation.

Suppose that the ListHead variable is a pointer to the LIST_ENTRY structure that represents the list head. A driver manipulates ListHead as follows:

• To initialize the list as empty, use InitializeListHead, which initializes ListHead->Flink and ListHead->Blink to point to ListHead.
• To add a new entry to the head of the list, allocate a LIST_ENTRY to represent the new entry, and then call InsertHeadList to insert the entry at the beginning of the list.
• To add a new entry to the tail of the list, allocate a LIST_ENTRY to represent the new entry, and then call InsertTailList to insert the entry at the end of the list.
• To remove the first entry from the list, use RemoveHeadList. This returns a pointer to the removed entry from the list, or ListHead if the list is empty.
• To remove the last entry from the list, use RemoveTailList. This returns a pointer to the removed entry from the list, or ListHead if the list is empty.
• To remove a specified entry from the list, use RemoveEntryList.
• To check to see if the list is empty, use IsListEmpty.

A LIST_ENTRY, by itself, only has Blink and Flink members. To store your own data in the lists, embed the LIST_ENTRY as a member of the structure that describes the list entry, as follows.

typedef struct {
  // driver-defined members
  .
  .
  .
  LIST_ENTRY ListEntry;
  
  // other driver-defined members.
  .
  .
  .
} XXX_ENTRY;

To add a new entry to a list, allocate an XXX_ENTRY structure, and then pass a pointer to the ListEntry member to InsertHeadList or InsertTailList. To convert a pointer to a LIST_ENTRY back to an XXX_ENTRY, use CONTAINING_RECORD. For an example of this technique, using singly linked lists, see Singly Linked Lists above.

The system also provides atomic versions of the list operations, ExInterlockedInsertHeadList, ExInterlockedInsertTailList, and ExInterlockedRemoveHeadList. (Note that there is no atomic version of RemoveTailList or RemoveList.) Each routine takes an additional spin lock parameter. The routine acquires the spin lock before updating the list and then releases the spin lock once the operation is completed. Each operation on the list must use the same spin lock to ensure that each such operation on the list is synchronized with every other. You must use the spin lock only with the ExInterlockedXxxList routines. Do not use the spin lock for any other purpose. Drivers can use the same lock for multiple lists, but this behavior increases lock contention so drivers should avoid it.

Do not mix calls to the atomic and non-atomic versions of the list operations on the same list. If the atomic and non-atomic versions are run simultaneously on the same list, the data structure might become corrupt and the computer might stop responding or bug check (that is, crash). (You cannot work acquire the spin lock while calling the non-atomic routine to avoid mixing calls to atomic and non-atomic versions of the list operations. Using the spin lock in this fashion is not supported and might still cause list corruption.)

Sequenced Singly Linked Lists

A sequenced singly linked list is an implementation of singly linked lists that supports atomic operations. It is more efficient for atomic operations than the implementation of singly linked lists described in Singly Linked Lists.

An SLIST_HEADER structure is used to describe the head of a sequence singly linked list, while SLIST_ENTRY is used to describe an entry in the list.

A driver manipulates the list as follows:

• To initialize an SLIST_HEADER structure, use ExInitializeSListHead.
• To add a new entry to the list, allocate a SLIST_ENTRY to represent the new entry, and then call ExInterlockedPushEntrySList to add the entry to the beginning of the list.
• Pop the first entry off the list by using ExInterlockedPopEntrySList.
• To clear the list completely, useExInterlockedFlushSList.
• To determine the number of entries in the list, use ExQueryDepthSList.

A SLIST_ENTRY, by itself, only has a Next member. To store your own data in the lists, embed the SLIST_ENTRY as a member of the structure that describes the list entry. as follows.

typedef struct {
  // driver-defined members
  .
  .
  .
  SLIST_ENTRY SListEntry;
  // other driver-defined members
  .
  .
  .

} XXX_ENTRY;

To add a new entry to the list, allocate an XXX_ENTRY structure, and then pass a pointer to the SListEntry member to ExInterlockedPushEntrySList. To convert a pointer to the SLIST_ENTRY back to an XXX_ENTRY, use CONTAINING_RECORD. For an example of this technique, using non-sequenced singly linked lists, use Singly Linked Lists.

Warning  For 64-bit Microsoft Windows operating systems, SLIST_ENTRY structures must be 16-byte aligned.

Windows XP and later versions of Windows provide optimized versions of the sequenced singly linked list functions that are not available in Windows 2000. If your driver uses these functions and also must run with Windows 2000, the driver must define the _WIN2K_COMPAT_SLIST_USAGE flag, as follows:

#define _WIN2K_COMPAT_SLIST_USAGE

For x86-based processors, this flag causes the compiler to use versions of the sequenced singly linked list functions that are compatible with Windows 2000.