ntoskrnl/ex/list.c

   1 /* $Id$
   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 #ifdef LIBCAPTIVE
 299   if (!ListHead->Flink && !ListHead->Blink)
 300     InitializeListHead(ListHead);
 301 #endif /* LIBCAPTIVE */
 302   InsertTailList(ListHead,ListEntry);
 303   KeReleaseSpinLock(Lock,oldlvl);
 304
 305   return(Old);
 306 }
 307
 308
 309 PSINGLE_LIST_ENTRY FASTCALL
 310 ExfInterlockedPopEntryList(IN PSINGLE_LIST_ENTRY ListHead,
 311                            IN PKSPIN_LOCK Lock)
 312 /*
 313  * FUNCTION: Removes (pops) an entry from a singly list
 314  * ARGUMENTS:
 315  *          ListHead = Points to the head of the list
 316  *          Lock     = Lock for synchronizing access to the list
 317  * RETURNS: The removed entry
 318  */
 319 {
 320   PSINGLE_LIST_ENTRY ret;
 321   KIRQL oldlvl;
 322
 323   KeAcquireSpinLock(Lock,&oldlvl);
 324   ret = PopEntryList(ListHead);
 325   KeReleaseSpinLock(Lock,oldlvl);
 326   return(ret);
 327 }
 328
 329
 330 PSINGLE_LIST_ENTRY FASTCALL
 331 ExfInterlockedPushEntryList(IN PSINGLE_LIST_ENTRY ListHead,
 332                             IN PSINGLE_LIST_ENTRY ListEntry,
 333                             IN PKSPIN_LOCK Lock)
 334 /*
 335  * FUNCTION: Inserts (pushes) an entry into a singly linked list
 336  * ARGUMENTS:
 337  *          ListHead  = Points to the head of the list
 338  *          ListEntry = Points to the entry to be inserted
 339  *          Lock      = Caller supplied spinlock used to synchronize access
 340  * RETURNS: The previous head of the list
 341  */
 342 {
 343   KIRQL oldlvl;
 344   PSINGLE_LIST_ENTRY ret;
 345
 346   KeAcquireSpinLock(Lock,&oldlvl);
 347   ret=ListHead->Next;
 348   PushEntryList(ListHead,ListEntry);
 349   KeReleaseSpinLock(Lock,oldlvl);
 350   return(ret);
 351 }
 352
 353
 354 PLIST_ENTRY FASTCALL
 355 ExfInterlockedRemoveHeadList(IN PLIST_ENTRY Head,
 356                              IN PKSPIN_LOCK Lock)
 357 /*
 358  * FUNCTION: Removes the head of a double linked list
 359  * ARGUMENTS:
 360  *          Head = Points to the head of the list
 361  *          Lock = Lock for synchronizing access to the list
 362  * RETURNS: The removed entry
 363  */
 364 {
 365   PLIST_ENTRY ret;
 366   KIRQL oldlvl;
 367
 368   KeAcquireSpinLock(Lock,&oldlvl);
 369   if (IsListEmpty(Head))
 370     {
 371       ret = NULL;
 372     }
 373   else
 374     {
 375       ret = RemoveHeadList(Head);
 376     }
 377   KeReleaseSpinLock(Lock,oldlvl);
 378   return(ret);
 379 }
 380
 381 /* EOF */