reactos/ntoskrnl/ex/list.c

   1 /* $Id$
   2  *
   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
   7  *                  sequenced lists
   8  * PROGRAMMERS:     David Welch (welch@mcmail.com)
   9  *                  Casper S. Hornstrup (chorns@users.sourceforge.net)
  10  * UPDATE HISTORY:
  11  *   02-07-2001 CSH Implemented sequenced lists
  12  */
  13
  14 /* INCLUDES *****************************************************************/
  15
  16 #include <ntoskrnl.h>
  17 #define NDEBUG
  18 #include <internal/debug.h>
  19
  20 static KSPIN_LOCK ExpGlobalListLock = { 0, };
  21
  22 /* FUNCTIONS *************************************************************/
  23
  24 /*
  25  * @implemented
  26  */
  27 PSLIST_ENTRY
  28 FASTCALL
  29 ExInterlockedFlushSList (
  30     IN PSLIST_HEADER ListHead
  31     )
  32 {
  33     PSLIST_ENTRY Old;
  34
  35     Old = &ListHead->Next;
  36     ListHead->Next.Next = 0;
  37
  38     return Old;
  39 }
  40
  41 /*
  42  * @implemented
  43  */
  44 PLIST_ENTRY
  45 STDCALL
  46 ExInterlockedInsertHeadList(PLIST_ENTRY ListHead,
  47                             PLIST_ENTRY ListEntry,
  48                             PKSPIN_LOCK Lock)
  49 /*
  50  * FUNCTION: Inserts an entry at the head of a doubly linked list
  51  * ARGUMENTS:
  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
  56  */
  57 {
  58   PLIST_ENTRY Old;
  59   KIRQL oldlvl;
  60
  61   KeAcquireSpinLock(Lock,&oldlvl);
  62   if (IsListEmpty(ListHead))
  63     {
  64       Old = NULL;
  65     }
  66   else
  67     {
  68       Old = ListHead->Flink;
  69     }
  70   InsertHeadList(ListHead,ListEntry);
  71   KeReleaseSpinLock(Lock,oldlvl);
  72
  73   return(Old);
  74 }
  75
  76
  77 /*
  78  * @implemented
  79  */
  80 PLIST_ENTRY
  81 STDCALL
  82 ExInterlockedInsertTailList(PLIST_ENTRY ListHead,
  83                             PLIST_ENTRY ListEntry,
  84                             PKSPIN_LOCK Lock)
  85 /*
  86  * FUNCTION: Inserts an entry at the tail of a doubly linked list
  87  * ARGUMENTS:
  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
  92  */
  93 {
  94   PLIST_ENTRY Old;
  95   KIRQL oldlvl;
  96
  97   KeAcquireSpinLock(Lock,&oldlvl);
  98   if (IsListEmpty(ListHead))
  99     {
 100       Old = NULL;
 101     }
 102   else
 103     {
 104       Old = ListHead->Blink;
 105     }
 106   InsertTailList(ListHead,ListEntry);
 107   KeReleaseSpinLock(Lock,oldlvl);
 108
 109   return(Old);
 110 }
 111
 112
 113 /*
 114  * @implemented
 115  */
 116 PLIST_ENTRY
 117 STDCALL
 118 ExInterlockedRemoveHeadList(PLIST_ENTRY Head,
 119                             PKSPIN_LOCK Lock)
 120 /*
 121  * FUNCTION: Removes the head of a double linked list
 122  * ARGUMENTS:
 123  *          Head = Points to the head of the list
 124  *          Lock = Lock for synchronizing access to the list
 125  * RETURNS: The removed entry
 126  */
 127 {
 128   PLIST_ENTRY ret;
 129   KIRQL oldlvl;
 130
 131   KeAcquireSpinLock(Lock,&oldlvl);
 132   if (IsListEmpty(Head))
 133     {
 134       ret = NULL;
 135     }
 136   else
 137     {
 138       ret = RemoveHeadList(Head);
 139     }
 140   KeReleaseSpinLock(Lock,oldlvl);
 141   return(ret);
 142 }
 143
 144
 145 PLIST_ENTRY
 146 STDCALL
 147 ExInterlockedRemoveTailList(PLIST_ENTRY Head,
 148                             PKSPIN_LOCK Lock)
 149 /*
 150  * FUNCTION: Removes the tail of a double linked list
 151  * ARGUMENTS:
 152  *          Head = Points to the head of the list
 153  *          Lock = Lock for synchronizing access to the list
 154  * RETURNS: The removed entry
 155  */
 156 {
 157   PLIST_ENTRY ret;
 158   KIRQL oldlvl;
 159
 160   KeAcquireSpinLock(Lock,&oldlvl);
 161   if (IsListEmpty(Head))
 162     {
 163       ret = NULL;
 164     }
 165   else
 166     {
 167       ret = RemoveTailList(Head);
 168     }
 169   KeReleaseSpinLock(Lock,oldlvl);
 170   return(ret);
 171 }
 172
 173
 174 #undef ExInterlockedPopEntrySList
 175
 176 /*
 177  * @implemented
 178  */
 179 PSINGLE_LIST_ENTRY
 180 FASTCALL
 181 ExInterlockedPopEntrySList(IN PSLIST_HEADER ListHead,
 182                            IN PKSPIN_LOCK Lock)
 183 /*
 184  * FUNCTION: Removes (pops) an entry from a sequenced list
 185  * ARGUMENTS:
 186  *          ListHead = Points to the head of the list
 187  *          Lock     = Lock for synchronizing access to the list
 188  * RETURNS: The removed entry
 189  */
 190 {
 191   PSINGLE_LIST_ENTRY ret;
 192   KIRQL oldlvl;
 193
 194   KeAcquireSpinLock(Lock,&oldlvl);
 195   ret = PopEntryList(&ListHead->Next);
 196   if (ret)
 197     {
 198       ListHead->Depth--;
 199       ListHead->Sequence++;
 200     }
 201   KeReleaseSpinLock(Lock,oldlvl);
 202   return(ret);
 203 }
 204
 205
 206 #undef ExInterlockedPushEntrySList
 207
 208 /*
 209  * @implemented
 210  */
 211 PSINGLE_LIST_ENTRY
 212 FASTCALL
 213 ExInterlockedPushEntrySList(IN PSLIST_HEADER ListHead,
 214                             IN PSINGLE_LIST_ENTRY ListEntry,
 215                             IN PKSPIN_LOCK Lock)
 216 /*
 217  * FUNCTION: Inserts (pushes) an entry into a sequenced list
 218  * ARGUMENTS:
 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
 223  */
 224 {
 225   KIRQL oldlvl;
 226   PSINGLE_LIST_ENTRY ret;
 227
 228   KeAcquireSpinLock(Lock,&oldlvl);
 229   ret=ListHead->Next.Next;
 230   PushEntryList(&ListHead->Next,ListEntry);
 231   ListHead->Depth++;
 232   ListHead->Sequence++;
 233   KeReleaseSpinLock(Lock,oldlvl);
 234   return(ret);
 235 }
 236
 237
 238 /*
 239  * @implemented
 240  */
 241 PSINGLE_LIST_ENTRY
 242 STDCALL
 243 ExInterlockedPopEntryList(IN PSINGLE_LIST_ENTRY ListHead,
 244                           IN PKSPIN_LOCK Lock)
 245 /*
 246  * FUNCTION: Removes (pops) an entry from a singly list
 247  * ARGUMENTS:
 248  *          ListHead = Points to the head of the list
 249  *          Lock     = Lock for synchronizing access to the list
 250  * RETURNS: The removed entry
 251  */
 252 {
 253   PSINGLE_LIST_ENTRY ret;
 254   KIRQL oldlvl;
 255
 256   KeAcquireSpinLock(Lock,&oldlvl);
 257   ret = PopEntryList(ListHead);
 258   KeReleaseSpinLock(Lock,oldlvl);
 259   return(ret);
 260 }
 261
 262
 263 /*
 264  * @implemented
 265  */
 266 PSINGLE_LIST_ENTRY
 267 STDCALL
 268 ExInterlockedPushEntryList(IN PSINGLE_LIST_ENTRY ListHead,
 269                            IN PSINGLE_LIST_ENTRY ListEntry,
 270                            IN PKSPIN_LOCK Lock)
 271 /*
 272  * FUNCTION: Inserts (pushes) an entry into a singly linked list
 273  * ARGUMENTS:
 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
 278  */
 279 {
 280   KIRQL oldlvl;
 281   PSINGLE_LIST_ENTRY ret;
 282
 283   KeAcquireSpinLock(Lock,&oldlvl);
 284   ret=ListHead->Next;
 285   PushEntryList(ListHead,ListEntry);
 286   KeReleaseSpinLock(Lock,oldlvl);
 287   return(ret);
 288 }
 289
 290
 291 /*
 292  * @implemented
 293  */
 294 PLIST_ENTRY FASTCALL
 295 ExfInterlockedInsertHeadList(IN PLIST_ENTRY ListHead,
 296                              IN PLIST_ENTRY ListEntry,
 297                              IN PKSPIN_LOCK Lock)
 298 /*
 299  * FUNCTION: Inserts an entry at the head of a doubly linked list
 300  * ARGUMENTS:
 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
 305  */
 306 {
 307   PLIST_ENTRY Old;
 308   KIRQL oldlvl;
 309
 310   KeAcquireSpinLock(Lock,&oldlvl);
 311   if (IsListEmpty(ListHead))
 312     {
 313       Old = NULL;
 314     }
 315   else
 316     {
 317       Old = ListHead->Flink;
 318      }
 319   InsertHeadList(ListHead,ListEntry);
 320   KeReleaseSpinLock(Lock,oldlvl);
 321
 322   return(Old);
 323 }
 324
 325
 326 /*
 327  * @implemented
 328  */
 329 PLIST_ENTRY FASTCALL
 330 ExfInterlockedInsertTailList(IN PLIST_ENTRY ListHead,
 331                              IN PLIST_ENTRY ListEntry,
 332                              IN PKSPIN_LOCK Lock)
 333 /*
 334  * FUNCTION: Inserts an entry at the tail of a doubly linked list
 335  * ARGUMENTS:
 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
 340  */
 341 {
 342   PLIST_ENTRY Old;
 343   KIRQL oldlvl;
 344
 345   KeAcquireSpinLock(Lock,&oldlvl);
 346   if (IsListEmpty(ListHead))
 347     {
 348       Old = NULL;
 349     }
 350   else
 351     {
 352       Old = ListHead->Blink;
 353     }
 354   InsertTailList(ListHead,ListEntry);
 355   KeReleaseSpinLock(Lock,oldlvl);
 356
 357   return(Old);
 358 }
 359
 360
 361 /*
 362  * @implemented
 363  */
 364 PSINGLE_LIST_ENTRY FASTCALL
 365 ExfInterlockedPopEntryList(IN PSINGLE_LIST_ENTRY ListHead,
 366                            IN PKSPIN_LOCK Lock)
 367 /*
 368  * FUNCTION: Removes (pops) an entry from a singly list
 369  * ARGUMENTS:
 370  *          ListHead = Points to the head of the list
 371  *          Lock     = Lock for synchronizing access to the list
 372  * RETURNS: The removed entry
 373  */
 374 {
 375   PSINGLE_LIST_ENTRY ret;
 376   KIRQL oldlvl;
 377
 378   KeAcquireSpinLock(Lock,&oldlvl);
 379   ret = PopEntryList(ListHead);
 380   KeReleaseSpinLock(Lock,oldlvl);
 381   return(ret);
 382 }
 383
 384
 385 /*
 386  * @implemented
 387  */
 388 PSINGLE_LIST_ENTRY FASTCALL
 389 ExfInterlockedPushEntryList(IN PSINGLE_LIST_ENTRY ListHead,
 390                             IN PSINGLE_LIST_ENTRY ListEntry,
 391                             IN PKSPIN_LOCK Lock)
 392 /*
 393  * FUNCTION: Inserts (pushes) an entry into a singly linked list
 394  * ARGUMENTS:
 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
 399  */
 400 {
 401   KIRQL oldlvl;
 402   PSINGLE_LIST_ENTRY ret;
 403
 404   KeAcquireSpinLock(Lock,&oldlvl);
 405   ret=ListHead->Next;
 406   PushEntryList(ListHead,ListEntry);
 407   KeReleaseSpinLock(Lock,oldlvl);
 408   return(ret);
 409 }
 410
 411
 412 /*
 413  * @implemented
 414  */
 415 PLIST_ENTRY FASTCALL
 416 ExfInterlockedRemoveHeadList(IN PLIST_ENTRY Head,
 417                              IN PKSPIN_LOCK Lock)
 418 /*
 419  * FUNCTION: Removes the head of a double linked list
 420  * ARGUMENTS:
 421  *          Head = Points to the head of the list
 422  *          Lock = Lock for synchronizing access to the list
 423  * RETURNS: The removed entry
 424  */
 425 {
 426   PLIST_ENTRY ret;
 427   KIRQL oldlvl;
 428
 429   KeAcquireSpinLock(Lock,&oldlvl);
 430   if (IsListEmpty(Head))
 431     {
 432       ret = NULL;
 433     }
 434   else
 435     {
 436       ret = RemoveHeadList(Head);
 437     }
 438   KeReleaseSpinLock(Lock,oldlvl);
 439   return(ret);
 440 }
 441
 442
 443 /*
 444  * @implemented
 445  */
 446 PSLIST_ENTRY
 447 FASTCALL
 448 InterlockedPopEntrySList(IN PSLIST_HEADER ListHead)
 449 {
 450   return (PSLIST_ENTRY) ExInterlockedPopEntrySList(ListHead,
 451     &ExpGlobalListLock);
 452 }
 453
 454
 455 /*
 456  * @implemented
 457  */
 458 PSLIST_ENTRY
 459 FASTCALL
 460 InterlockedPushEntrySList(IN PSLIST_HEADER ListHead,
 461   IN PSLIST_ENTRY ListEntry)
 462 {
 463   return (PSLIST_ENTRY) ExInterlockedPushEntrySList(ListHead,
 464     ListEntry,
 465     &ExpGlobalListLock);
 466 }
 467
 468 /* EOF */