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