reactos/ntoskrnl/ex/list.c

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