reactos/ntoskrnl/ex/list.c

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