reactos/ntoskrnl/ex/list.c

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