Linked Lists

< BACK  NEXT >

[oR]

Drivers sometimes need to maintain linked list data structures. This section describes the support available for managing singly and doubly linked lists.

Singly Linked Lists

To use singly linked lists, begin by declaring a list head of type SINGLE_ LIST_ENTRY. This simplistic structure is also the data type of the linked pointer itself. Indeed, the SINGLE_LIST_ENTRY structure has but one offset: Next. The list head must be manually initialized, as demonstrated in the following code fragment.

 typedef struct _DEVICE_EXTENSION {      :      SINGLE_LIST_ENTRY listHead;   // Declare head ptr } DEVICE_EXTENSION, *PDEVICE_EXTENSION;      : pDevExt->listHead.Next = NULL;   // init the list 

To add or remove entries from the front of the list, call PushEntryList and PopEntryList. Depending on how the list is used, the actual entries can be in either page or nonpaged memory. Remember that the use of these functions may require synchronization.

The Windows 2000 kernel also provides convenient support for singly linked lists guarded by an Executive spin lock. This kind of protection is important when sharing a linked list among driver routines running at or below DISPATCH_LEVEL IRQL. To use one of these lists, set up the list head in the usual way, and then initialize an Executive spin lock that guards the list.

 typedef struct _DEVICE_EXTENSION {      :      SINGLE_LIST_ENTRY listHead;  // head pointer      KSPIN_LOCK listLock;   // declare list lock } DEVICE_EXTENSION, *PDEVICE_EXTENSION;      : KeInitializeSpinLock(&pDevExt->listLock); pDevExt->listHead.Next = NULL; 

Once the list head and spin lock are declared and initialized, the functions ExInterlockedPushEntryList and ExInterlockedPopEntryList provide convenient, protected access to the list. Code must be running at or below DISPATCH_LEVEL IRQL to use either function. The list entries themselves must reside in nonpaged memory, since the system will be linking and unlinking them from DISPATCH_LEVEL IRQL.

Doubly Linked Lists

To use doubly linked lists, declare a list head of type LIST_ENTRY. This is also the data type of the linked pointer itself. The LIST_ENTRY structure declares two offsets, Flink and Blink, for the forward and back pointers. The list head is initialized with a helper routine, InitializeListHead, as demonstrated in the following code fragment.

 typedef struct _DEVICE_EXTENSION {      : LIST_ENTRY listHead;   // head pointer } DEVICE_EXTENSION, *PDEVICE_EXTENSION;      : InitializeListHead( &pDevExt->listHead ); 

To add entries to the list, call InsertHeadList or InsertTailList, and to pull entries out, call RemoveHeadList or RemoveTailList. To determine if the list is empty, use IsListEmpty. Again, the entries can be paged or nonpaged, but these functions do not perform synchronization.

The Windows 2000 kernel also supports interlocked doubly linked lists. To use these, set up the list head in the usual way, and then initialize an Executive spin lock that guards the list.

 typedef struct _DEVICE_EXTENSION {      : LIST_ENTRY listHead;   // head pointer KSPIN_LOCK listLock;   // the list's lock } DEVICE_EXTENSION, *PDEVICE_EXTENSION;      : KeInitializeSpinLock( &pDevExt->listLock ); InitializeListHead( &pDevExt->listHead ); 

The spin lock is passed in calls to ExInterlockedInsertTailList, ExInterlockedInsertHeadList, and ExInterlockedRemoveHeadList. To make these calls, code must be running at or below DISPATCH_LEVEL IRQL. Entries for doubly linked interlock lists have to live in nonpaged memory.

Removing Blocks from a List

When a block is pulled from a list, the pop function returns a pointer to the LIST_ENTRY or SINGLE_LIST_ENTRY structure. Since these structures are merely a part of a bigger structure, a pointer to the containing structure must be obtained. One simple technique would be to ensure that the LIST_ENTRY structure is the first offset of the containing structure. Then, a pointer to the LIST_ENTRY structure is also a pointer to the containing structure. Otherwise, clever use of the offsetof operator is required to dig out a pointer to the containing structure. Fortunately, Windows 2000 provides a macro, CONTAINING_RECORD, to make the process easier. The macro arguments are listed in Table 5.5

Table 5.5. CONTAINING_RECORD Macro Arguments

CONTAINING_RECORD Macro
Parameter	Description
Address	Address returned by list "removal" function
Type	Data type of the "containing structure"
Field	Field within "containing structure" where Address argument points
Return value	Pointer to "containing structure"

The following code fragment demonstrates the use of the CONTAINING_RECORD macro.

 typedef struct _MYBLOCK {      ULONG ulSomeThingAtTopOfBlock;      :      LIST_ENTRY listEntry;      : } MYBLOCK, *PMYBLOCK;      : PMYBLOCK pMyBlock; PLIST_ENTRY pEntry;      : pEntry = RemoveHeadList( &pDevExt->listHead ); pMyBlock = CONTAINING_RECORD( pEntry, MYBLOCK, listEntry); 

Notice that, for whatever reason, the LIST_ENTRY field could not be the first offset within the MYBLOCK structure. Therefore, the address returned by RemoveHeadList needed to be converted into a pointer of the containing structure.

< BACK  NEXT >