reactos/ntoskrnl/ex/list.c

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