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
8 * PROGRAMMERS: David Welch (welch@mcmail.com)
9 * Casper S. Hornstrup (chorns@users.sourceforge.net)
11 * 02-07-2001 CSH Implemented sequenced lists
14 /* INCLUDES *****************************************************************/
18 #include <internal/debug.h>
20 static KSPIN_LOCK ExpGlobalListLock
= { 0, };
22 /* FUNCTIONS *************************************************************/
29 ExInterlockedFlushSList (
30 IN PSLIST_HEADER ListHead
35 Old
= &ListHead
->Next
;
36 ListHead
->Next
.Next
= 0;
46 ExInterlockedInsertHeadList(PLIST_ENTRY ListHead
,
47 PLIST_ENTRY ListEntry
,
50 * FUNCTION: Inserts an entry at the head of a doubly linked list
52 * ListHead = Points to the head of the list
53 * ListEntry = Points to the entry to be inserted
54 * Lock = Caller supplied spinlock used to synchronize access
55 * RETURNS: The previous head of the list
61 KeAcquireSpinLock(Lock
,&oldlvl
);
62 if (IsListEmpty(ListHead
))
68 Old
= ListHead
->Flink
;
70 InsertHeadList(ListHead
,ListEntry
);
71 KeReleaseSpinLock(Lock
,oldlvl
);
82 ExInterlockedInsertTailList(PLIST_ENTRY ListHead
,
83 PLIST_ENTRY ListEntry
,
86 * FUNCTION: Inserts an entry at the tail of a doubly linked list
88 * ListHead = Points to the head of the list
89 * ListEntry = Points to the entry to be inserted
90 * Lock = Caller supplied spinlock used to synchronize access
91 * RETURNS: The previous head of the list
97 KeAcquireSpinLock(Lock
,&oldlvl
);
98 if (IsListEmpty(ListHead
))
104 Old
= ListHead
->Blink
;
106 InsertTailList(ListHead
,ListEntry
);
107 KeReleaseSpinLock(Lock
,oldlvl
);
118 ExInterlockedRemoveHeadList(PLIST_ENTRY Head
,
121 * FUNCTION: Removes the head of a double linked list
123 * Head = Points to the head of the list
124 * Lock = Lock for synchronizing access to the list
125 * RETURNS: The removed entry
131 KeAcquireSpinLock(Lock
,&oldlvl
);
132 if (IsListEmpty(Head
))
138 ret
= RemoveHeadList(Head
);
140 KeReleaseSpinLock(Lock
,oldlvl
);
147 ExInterlockedRemoveTailList(PLIST_ENTRY Head
,
150 * FUNCTION: Removes the tail of a double linked list
152 * Head = Points to the head of the list
153 * Lock = Lock for synchronizing access to the list
154 * RETURNS: The removed entry
160 KeAcquireSpinLock(Lock
,&oldlvl
);
161 if (IsListEmpty(Head
))
167 ret
= RemoveTailList(Head
);
169 KeReleaseSpinLock(Lock
,oldlvl
);
174 #undef ExInterlockedPopEntrySList
181 ExInterlockedPopEntrySList(IN PSLIST_HEADER ListHead
,
184 * FUNCTION: Removes (pops) an entry from a sequenced list
186 * ListHead = Points to the head of the list
187 * Lock = Lock for synchronizing access to the list
188 * RETURNS: The removed entry
191 PSINGLE_LIST_ENTRY ret
;
194 KeAcquireSpinLock(Lock
,&oldlvl
);
195 ret
= PopEntryList(&ListHead
->Next
);
199 ListHead
->Sequence
++;
201 KeReleaseSpinLock(Lock
,oldlvl
);
206 #undef ExInterlockedPushEntrySList
213 ExInterlockedPushEntrySList(IN PSLIST_HEADER ListHead
,
214 IN PSINGLE_LIST_ENTRY ListEntry
,
217 * FUNCTION: Inserts (pushes) an entry into a sequenced list
219 * ListHead = Points to the head of the list
220 * ListEntry = Points to the entry to be inserted
221 * Lock = Caller supplied spinlock used to synchronize access
222 * RETURNS: The previous head of the list
226 PSINGLE_LIST_ENTRY ret
;
228 KeAcquireSpinLock(Lock
,&oldlvl
);
229 ret
=ListHead
->Next
.Next
;
230 PushEntryList(&ListHead
->Next
,ListEntry
);
232 ListHead
->Sequence
++;
233 KeReleaseSpinLock(Lock
,oldlvl
);
243 ExInterlockedPopEntryList(IN PSINGLE_LIST_ENTRY ListHead
,
246 * FUNCTION: Removes (pops) an entry from a singly list
248 * ListHead = Points to the head of the list
249 * Lock = Lock for synchronizing access to the list
250 * RETURNS: The removed entry
253 PSINGLE_LIST_ENTRY ret
;
256 KeAcquireSpinLock(Lock
,&oldlvl
);
257 ret
= PopEntryList(ListHead
);
258 KeReleaseSpinLock(Lock
,oldlvl
);
268 ExInterlockedPushEntryList(IN PSINGLE_LIST_ENTRY ListHead
,
269 IN PSINGLE_LIST_ENTRY ListEntry
,
272 * FUNCTION: Inserts (pushes) an entry into a singly linked list
274 * ListHead = Points to the head of the list
275 * ListEntry = Points to the entry to be inserted
276 * Lock = Caller supplied spinlock used to synchronize access
277 * RETURNS: The previous head of the list
281 PSINGLE_LIST_ENTRY ret
;
283 KeAcquireSpinLock(Lock
,&oldlvl
);
285 PushEntryList(ListHead
,ListEntry
);
286 KeReleaseSpinLock(Lock
,oldlvl
);
295 ExfInterlockedInsertHeadList(IN PLIST_ENTRY ListHead
,
296 IN PLIST_ENTRY ListEntry
,
299 * FUNCTION: Inserts an entry at the head of a doubly linked list
301 * ListHead = Points to the head of the list
302 * ListEntry = Points to the entry to be inserted
303 * Lock = Caller supplied spinlock used to synchronize access
304 * RETURNS: The previous head of the list
310 KeAcquireSpinLock(Lock
,&oldlvl
);
311 if (IsListEmpty(ListHead
))
317 Old
= ListHead
->Flink
;
319 InsertHeadList(ListHead
,ListEntry
);
320 KeReleaseSpinLock(Lock
,oldlvl
);
330 ExfInterlockedInsertTailList(IN PLIST_ENTRY ListHead
,
331 IN PLIST_ENTRY ListEntry
,
334 * FUNCTION: Inserts an entry at the tail of a doubly linked list
336 * ListHead = Points to the head of the list
337 * ListEntry = Points to the entry to be inserted
338 * Lock = Caller supplied spinlock used to synchronize access
339 * RETURNS: The previous head of the list
345 KeAcquireSpinLock(Lock
,&oldlvl
);
346 if (IsListEmpty(ListHead
))
352 Old
= ListHead
->Blink
;
354 InsertTailList(ListHead
,ListEntry
);
355 KeReleaseSpinLock(Lock
,oldlvl
);
364 PSINGLE_LIST_ENTRY FASTCALL
365 ExfInterlockedPopEntryList(IN PSINGLE_LIST_ENTRY ListHead
,
368 * FUNCTION: Removes (pops) an entry from a singly list
370 * ListHead = Points to the head of the list
371 * Lock = Lock for synchronizing access to the list
372 * RETURNS: The removed entry
375 PSINGLE_LIST_ENTRY ret
;
378 KeAcquireSpinLock(Lock
,&oldlvl
);
379 ret
= PopEntryList(ListHead
);
380 KeReleaseSpinLock(Lock
,oldlvl
);
388 PSINGLE_LIST_ENTRY FASTCALL
389 ExfInterlockedPushEntryList(IN PSINGLE_LIST_ENTRY ListHead
,
390 IN PSINGLE_LIST_ENTRY ListEntry
,
393 * FUNCTION: Inserts (pushes) an entry into a singly linked list
395 * ListHead = Points to the head of the list
396 * ListEntry = Points to the entry to be inserted
397 * Lock = Caller supplied spinlock used to synchronize access
398 * RETURNS: The previous head of the list
402 PSINGLE_LIST_ENTRY ret
;
404 KeAcquireSpinLock(Lock
,&oldlvl
);
406 PushEntryList(ListHead
,ListEntry
);
407 KeReleaseSpinLock(Lock
,oldlvl
);
416 ExfInterlockedRemoveHeadList(IN PLIST_ENTRY Head
,
419 * FUNCTION: Removes the head of a double linked list
421 * Head = Points to the head of the list
422 * Lock = Lock for synchronizing access to the list
423 * RETURNS: The removed entry
429 KeAcquireSpinLock(Lock
,&oldlvl
);
430 if (IsListEmpty(Head
))
436 ret
= RemoveHeadList(Head
);
438 KeReleaseSpinLock(Lock
,oldlvl
);
448 InterlockedPopEntrySList(IN PSLIST_HEADER ListHead
)
450 return (PSLIST_ENTRY
) ExInterlockedPopEntrySList(ListHead
,
460 InterlockedPushEntrySList(IN PSLIST_HEADER ListHead
,
461 IN PSLIST_ENTRY ListEntry
)
463 return (PSLIST_ENTRY
) ExInterlockedPushEntrySList(ListHead
,