reactos/ntoskrnl/ex/list.c

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