reactos/ntoskrnl/ex/list.c

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