reactos/ntoskrnl/ex/list.c

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