3 * COPYRIGHT: See COPYING in the top level directory
4 * PROJECT: ReactOS kernel
5 * FILE: ntoskrnl/ex/list.c
6 * PURPOSE: Manages double linked lists, single linked lists and
9 * PROGRAMMERS: David Welch (welch@mcmail.com)
10 * Casper S. Hornstrup (chorns@users.sourceforge.net)
13 /* INCLUDES *****************************************************************/
17 #include <internal/debug.h>
19 /* FUNCTIONS *************************************************************/
26 ExInterlockedFlushSList (
27 IN PSLIST_HEADER ListHead
32 Old
= &ListHead
->Next
;
33 ListHead
->Next
.Next
= 0;
43 ExInterlockedInsertHeadList(PLIST_ENTRY ListHead
,
44 PLIST_ENTRY ListEntry
,
47 * FUNCTION: Inserts an entry at the head of a doubly linked list
49 * ListHead = Points to the head of the list
50 * ListEntry = Points to the entry to be inserted
51 * Lock = Caller supplied spinlock used to synchronize access
52 * RETURNS: The previous head of the list
58 KeAcquireSpinLock(Lock
,&oldlvl
);
59 if (IsListEmpty(ListHead
))
65 Old
= ListHead
->Flink
;
67 InsertHeadList(ListHead
,ListEntry
);
68 KeReleaseSpinLock(Lock
,oldlvl
);
79 ExInterlockedInsertTailList(PLIST_ENTRY ListHead
,
80 PLIST_ENTRY ListEntry
,
83 * FUNCTION: Inserts an entry at the tail of a doubly linked list
85 * ListHead = Points to the head of the list
86 * ListEntry = Points to the entry to be inserted
87 * Lock = Caller supplied spinlock used to synchronize access
88 * RETURNS: The previous head of the list
94 KeAcquireSpinLock(Lock
,&oldlvl
);
95 if (IsListEmpty(ListHead
))
101 Old
= ListHead
->Blink
;
103 InsertTailList(ListHead
,ListEntry
);
104 KeReleaseSpinLock(Lock
,oldlvl
);
115 ExInterlockedRemoveHeadList(PLIST_ENTRY Head
,
118 * FUNCTION: Removes the head of a double linked list
120 * Head = Points to the head of the list
121 * Lock = Lock for synchronizing access to the list
122 * RETURNS: The removed entry
128 KeAcquireSpinLock(Lock
,&oldlvl
);
129 if (IsListEmpty(Head
))
135 ret
= RemoveHeadList(Head
);
137 KeReleaseSpinLock(Lock
,oldlvl
);
144 ExInterlockedRemoveTailList(PLIST_ENTRY Head
,
147 * FUNCTION: Removes the tail of a double linked list
149 * Head = Points to the head of the list
150 * Lock = Lock for synchronizing access to the list
151 * RETURNS: The removed entry
157 KeAcquireSpinLock(Lock
,&oldlvl
);
158 if (IsListEmpty(Head
))
164 ret
= RemoveTailList(Head
);
166 KeReleaseSpinLock(Lock
,oldlvl
);
171 #undef ExInterlockedPopEntrySList
178 ExInterlockedPopEntrySList(IN PSLIST_HEADER ListHead
,
181 * FUNCTION: Removes (pops) an entry from a sequenced list
183 * ListHead = Points to the head of the list
184 * Lock = Lock for synchronizing access to the list
185 * RETURNS: The removed entry
188 PSINGLE_LIST_ENTRY ret
;
191 KeAcquireSpinLock(Lock
,&oldlvl
);
192 ret
= PopEntryList(&ListHead
->Next
);
196 ListHead
->Sequence
++;
198 KeReleaseSpinLock(Lock
,oldlvl
);
203 #undef ExInterlockedPushEntrySList
210 ExInterlockedPushEntrySList(IN PSLIST_HEADER ListHead
,
211 IN PSINGLE_LIST_ENTRY ListEntry
,
214 * FUNCTION: Inserts (pushes) an entry into a sequenced list
216 * ListHead = Points to the head of the list
217 * ListEntry = Points to the entry to be inserted
218 * Lock = Caller supplied spinlock used to synchronize access
219 * RETURNS: The previous head of the list
223 PSINGLE_LIST_ENTRY ret
;
225 KeAcquireSpinLock(Lock
,&oldlvl
);
226 ret
=ListHead
->Next
.Next
;
227 PushEntryList(&ListHead
->Next
,ListEntry
);
229 ListHead
->Sequence
++;
230 KeReleaseSpinLock(Lock
,oldlvl
);
240 ExInterlockedPopEntryList(IN PSINGLE_LIST_ENTRY ListHead
,
243 * FUNCTION: Removes (pops) an entry from a singly list
245 * ListHead = Points to the head of the list
246 * Lock = Lock for synchronizing access to the list
247 * RETURNS: The removed entry
250 PSINGLE_LIST_ENTRY ret
;
253 KeAcquireSpinLock(Lock
,&oldlvl
);
254 ret
= PopEntryList(ListHead
);
255 KeReleaseSpinLock(Lock
,oldlvl
);
265 ExInterlockedPushEntryList(IN PSINGLE_LIST_ENTRY ListHead
,
266 IN PSINGLE_LIST_ENTRY ListEntry
,
269 * FUNCTION: Inserts (pushes) an entry into a singly linked list
271 * ListHead = Points to the head of the list
272 * ListEntry = Points to the entry to be inserted
273 * Lock = Caller supplied spinlock used to synchronize access
274 * RETURNS: The previous head of the list
278 PSINGLE_LIST_ENTRY ret
;
280 KeAcquireSpinLock(Lock
,&oldlvl
);
282 PushEntryList(ListHead
,ListEntry
);
283 KeReleaseSpinLock(Lock
,oldlvl
);
292 ExfInterlockedInsertHeadList(IN PLIST_ENTRY ListHead
,
293 IN PLIST_ENTRY ListEntry
,
296 * FUNCTION: Inserts an entry at the head of a doubly linked list
298 * ListHead = Points to the head of the list
299 * ListEntry = Points to the entry to be inserted
300 * Lock = Caller supplied spinlock used to synchronize access
301 * RETURNS: The previous head of the list
307 KeAcquireSpinLock(Lock
,&oldlvl
);
308 if (IsListEmpty(ListHead
))
314 Old
= ListHead
->Flink
;
316 InsertHeadList(ListHead
,ListEntry
);
317 KeReleaseSpinLock(Lock
,oldlvl
);
327 ExfInterlockedInsertTailList(IN PLIST_ENTRY ListHead
,
328 IN PLIST_ENTRY ListEntry
,
331 * FUNCTION: Inserts an entry at the tail of a doubly linked list
333 * ListHead = Points to the head of the list
334 * ListEntry = Points to the entry to be inserted
335 * Lock = Caller supplied spinlock used to synchronize access
336 * RETURNS: The previous head of the list
342 KeAcquireSpinLock(Lock
,&oldlvl
);
343 if (IsListEmpty(ListHead
))
349 Old
= ListHead
->Blink
;
351 InsertTailList(ListHead
,ListEntry
);
352 KeReleaseSpinLock(Lock
,oldlvl
);
361 PSINGLE_LIST_ENTRY FASTCALL
362 ExfInterlockedPopEntryList(IN PSINGLE_LIST_ENTRY ListHead
,
365 * FUNCTION: Removes (pops) an entry from a singly list
367 * ListHead = Points to the head of the list
368 * Lock = Lock for synchronizing access to the list
369 * RETURNS: The removed entry
372 PSINGLE_LIST_ENTRY ret
;
375 KeAcquireSpinLock(Lock
,&oldlvl
);
376 ret
= PopEntryList(ListHead
);
377 KeReleaseSpinLock(Lock
,oldlvl
);
385 PSINGLE_LIST_ENTRY FASTCALL
386 ExfInterlockedPushEntryList(IN PSINGLE_LIST_ENTRY ListHead
,
387 IN PSINGLE_LIST_ENTRY ListEntry
,
390 * FUNCTION: Inserts (pushes) an entry into a singly linked list
392 * ListHead = Points to the head of the list
393 * ListEntry = Points to the entry to be inserted
394 * Lock = Caller supplied spinlock used to synchronize access
395 * RETURNS: The previous head of the list
399 PSINGLE_LIST_ENTRY ret
;
401 KeAcquireSpinLock(Lock
,&oldlvl
);
403 PushEntryList(ListHead
,ListEntry
);
404 KeReleaseSpinLock(Lock
,oldlvl
);
413 ExfInterlockedRemoveHeadList(IN PLIST_ENTRY Head
,
416 * FUNCTION: Removes the head of a double linked list
418 * Head = Points to the head of the list
419 * Lock = Lock for synchronizing access to the list
420 * RETURNS: The removed entry
426 KeAcquireSpinLock(Lock
,&oldlvl
);
427 if (IsListEmpty(Head
))
433 ret
= RemoveHeadList(Head
);
435 KeReleaseSpinLock(Lock
,oldlvl
);
445 InterlockedPopEntrySList(IN PSLIST_HEADER ListHead
)
447 SLIST_HEADER newslh
, oldslh
;
452 oldslh
= *(volatile SLIST_HEADER
*)ListHead
;
453 le
= oldslh
.Next
.Next
;
459 newslh
.Sequence
= oldslh
.Sequence
+ 1;
460 newslh
.Depth
= oldslh
.Depth
- 1;
461 newslh
.Next
.Next
= MmSafeReadPtr(&le
->Next
);
462 } while(ExfInterlockedCompareExchange64(&ListHead
->Alignment
,
464 &oldslh
.Alignment
) != oldslh
.Alignment
);
475 InterlockedPushEntrySList(IN PSLIST_HEADER ListHead
,
476 IN PSLIST_ENTRY ListEntry
)
478 SLIST_HEADER newslh
, oldslh
;
480 newslh
.Next
.Next
= ListEntry
;
484 oldslh
= *(volatile SLIST_HEADER
*)ListHead
;
485 newslh
.Depth
= oldslh
.Depth
+ 1;
486 newslh
.Sequence
= oldslh
.Sequence
+ 1;
487 ListEntry
->Next
= oldslh
.Next
.Next
;
488 } while(ExfInterlockedCompareExchange64(&ListHead
->Alignment
,
490 &oldslh
.Alignment
) != oldslh
.Alignment
);
492 return oldslh
.Next
.Next
;