reactos/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  *
   9  * PROGRAMMERS:     David Welch (welch@mcmail.com)
  10  *                  Casper S. Hornstrup (chorns@users.sourceforge.net)
  11  */
  12
  13 /* INCLUDES *****************************************************************/
  14
  15 #include <ntoskrnl.h>
  16 #define NDEBUG
  17 #include <internal/debug.h>
  18
  19 /* FUNCTIONS *************************************************************/
  20
  21 /*
  22  * @implemented
  23  */
  24 PSLIST_ENTRY
  25 FASTCALL
  26 ExInterlockedFlushSList (
  27     IN PSLIST_HEADER ListHead
  28     )
  29 {
  30     PSLIST_ENTRY Old;
  31
  32     Old = &ListHead->Next;
  33     ListHead->Next.Next = 0;
  34
  35     return Old;
  36 }
  37
  38 /*
  39  * @implemented
  40  */
  41 PLIST_ENTRY
  42 STDCALL
  43 ExInterlockedInsertHeadList(PLIST_ENTRY ListHead,
  44                             PLIST_ENTRY ListEntry,
  45                             PKSPIN_LOCK Lock)
  46 /*
  47  * FUNCTION: Inserts an entry at the head of a doubly linked list
  48  * ARGUMENTS:
  49  *          ListHead  = Points to the head of the list
  50  *          ListEntry = Points to the entry to be inserted
  51  *          Lock      = Caller supplied spinlock used to synchronize access
  52  * RETURNS: The previous head of the list
  53  */
  54 {
  55   PLIST_ENTRY Old;
  56   KIRQL oldlvl;
  57
  58   KeAcquireSpinLock(Lock,&oldlvl);
  59   if (IsListEmpty(ListHead))
  60     {
  61       Old = NULL;
  62     }
  63   else
  64     {
  65       Old = ListHead->Flink;
  66     }
  67   InsertHeadList(ListHead,ListEntry);
  68   KeReleaseSpinLock(Lock,oldlvl);
  69
  70   return(Old);
  71 }
  72
  73
  74 /*
  75  * @implemented
  76  */
  77 PLIST_ENTRY
  78 STDCALL
  79 ExInterlockedInsertTailList(PLIST_ENTRY ListHead,
  80                             PLIST_ENTRY ListEntry,
  81                             PKSPIN_LOCK Lock)
  82 /*
  83  * FUNCTION: Inserts an entry at the tail of a doubly linked list
  84  * ARGUMENTS:
  85  *          ListHead  = Points to the head of the list
  86  *          ListEntry = Points to the entry to be inserted
  87  *          Lock      = Caller supplied spinlock used to synchronize access
  88  * RETURNS: The previous head of the list
  89  */
  90 {
  91   PLIST_ENTRY Old;
  92   KIRQL oldlvl;
  93
  94   KeAcquireSpinLock(Lock,&oldlvl);
  95   if (IsListEmpty(ListHead))
  96     {
  97       Old = NULL;
  98     }
  99   else
 100     {
 101       Old = ListHead->Blink;
 102     }
 103   InsertTailList(ListHead,ListEntry);
 104   KeReleaseSpinLock(Lock,oldlvl);
 105
 106   return(Old);
 107 }
 108
 109
 110 /*
 111  * @implemented
 112  */
 113 PLIST_ENTRY
 114 STDCALL
 115 ExInterlockedRemoveHeadList(PLIST_ENTRY Head,
 116                             PKSPIN_LOCK Lock)
 117 /*
 118  * FUNCTION: Removes the head of a double linked list
 119  * ARGUMENTS:
 120  *          Head = Points to the head of the list
 121  *          Lock = Lock for synchronizing access to the list
 122  * RETURNS: The removed entry
 123  */
 124 {
 125   PLIST_ENTRY ret;
 126   KIRQL oldlvl;
 127
 128   KeAcquireSpinLock(Lock,&oldlvl);
 129   if (IsListEmpty(Head))
 130     {
 131       ret = NULL;
 132     }
 133   else
 134     {
 135       ret = RemoveHeadList(Head);
 136     }
 137   KeReleaseSpinLock(Lock,oldlvl);
 138   return(ret);
 139 }
 140
 141
 142 PLIST_ENTRY
 143 STDCALL
 144 ExInterlockedRemoveTailList(PLIST_ENTRY Head,
 145                             PKSPIN_LOCK Lock)
 146 /*
 147  * FUNCTION: Removes the tail of a double linked list
 148  * ARGUMENTS:
 149  *          Head = Points to the head of the list
 150  *          Lock = Lock for synchronizing access to the list
 151  * RETURNS: The removed entry
 152  */
 153 {
 154   PLIST_ENTRY ret;
 155   KIRQL oldlvl;
 156
 157   KeAcquireSpinLock(Lock,&oldlvl);
 158   if (IsListEmpty(Head))
 159     {
 160       ret = NULL;
 161     }
 162   else
 163     {
 164       ret = RemoveTailList(Head);
 165     }
 166   KeReleaseSpinLock(Lock,oldlvl);
 167   return(ret);
 168 }
 169
 170
 171 #undef ExInterlockedPopEntrySList
 172
 173 /*
 174  * @implemented
 175  */
 176 PSINGLE_LIST_ENTRY
 177 FASTCALL
 178 ExInterlockedPopEntrySList(IN PSLIST_HEADER ListHead,
 179                            IN PKSPIN_LOCK Lock)
 180 /*
 181  * FUNCTION: Removes (pops) an entry from a sequenced list
 182  * ARGUMENTS:
 183  *          ListHead = Points to the head of the list
 184  *          Lock     = Lock for synchronizing access to the list
 185  * RETURNS: The removed entry
 186  */
 187 {
 188   PSINGLE_LIST_ENTRY ret;
 189   KIRQL oldlvl;
 190
 191   KeAcquireSpinLock(Lock,&oldlvl);
 192   ret = PopEntryList(&ListHead->Next);
 193   if (ret)
 194     {
 195       ListHead->Depth--;
 196       ListHead->Sequence++;
 197     }
 198   KeReleaseSpinLock(Lock,oldlvl);
 199   return(ret);
 200 }
 201
 202
 203 #undef ExInterlockedPushEntrySList
 204
 205 /*
 206  * @implemented
 207  */
 208 PSINGLE_LIST_ENTRY
 209 FASTCALL
 210 ExInterlockedPushEntrySList(IN PSLIST_HEADER ListHead,
 211                             IN PSINGLE_LIST_ENTRY ListEntry,
 212                             IN PKSPIN_LOCK Lock)
 213 /*
 214  * FUNCTION: Inserts (pushes) an entry into a sequenced list
 215  * ARGUMENTS:
 216  *          ListHead  = Points to the head of the list
 217  *          ListEntry = Points to the entry to be inserted
 218  *          Lock      = Caller supplied spinlock used to synchronize access
 219  * RETURNS: The previous head of the list
 220  */
 221 {
 222   KIRQL oldlvl;
 223   PSINGLE_LIST_ENTRY ret;
 224
 225   KeAcquireSpinLock(Lock,&oldlvl);
 226   ret=ListHead->Next.Next;
 227   PushEntryList(&ListHead->Next,ListEntry);
 228   ListHead->Depth++;
 229   ListHead->Sequence++;
 230   KeReleaseSpinLock(Lock,oldlvl);
 231   return(ret);
 232 }
 233
 234
 235 /*
 236  * @implemented
 237  */
 238 PSINGLE_LIST_ENTRY
 239 STDCALL
 240 ExInterlockedPopEntryList(IN PSINGLE_LIST_ENTRY ListHead,
 241                           IN PKSPIN_LOCK Lock)
 242 /*
 243  * FUNCTION: Removes (pops) an entry from a singly list
 244  * ARGUMENTS:
 245  *          ListHead = Points to the head of the list
 246  *          Lock     = Lock for synchronizing access to the list
 247  * RETURNS: The removed entry
 248  */
 249 {
 250   PSINGLE_LIST_ENTRY ret;
 251   KIRQL oldlvl;
 252
 253   KeAcquireSpinLock(Lock,&oldlvl);
 254   ret = PopEntryList(ListHead);
 255   KeReleaseSpinLock(Lock,oldlvl);
 256   return(ret);
 257 }
 258
 259
 260 /*
 261  * @implemented
 262  */
 263 PSINGLE_LIST_ENTRY
 264 STDCALL
 265 ExInterlockedPushEntryList(IN PSINGLE_LIST_ENTRY ListHead,
 266                            IN PSINGLE_LIST_ENTRY ListEntry,
 267                            IN PKSPIN_LOCK Lock)
 268 /*
 269  * FUNCTION: Inserts (pushes) an entry into a singly linked list
 270  * ARGUMENTS:
 271  *          ListHead  = Points to the head of the list
 272  *          ListEntry = Points to the entry to be inserted
 273  *          Lock      = Caller supplied spinlock used to synchronize access
 274  * RETURNS: The previous head of the list
 275  */
 276 {
 277   KIRQL oldlvl;
 278   PSINGLE_LIST_ENTRY ret;
 279
 280   KeAcquireSpinLock(Lock,&oldlvl);
 281   ret=ListHead->Next;
 282   PushEntryList(ListHead,ListEntry);
 283   KeReleaseSpinLock(Lock,oldlvl);
 284   return(ret);
 285 }
 286
 287
 288 /*
 289  * @implemented
 290  */
 291 PLIST_ENTRY FASTCALL
 292 ExfInterlockedInsertHeadList(IN PLIST_ENTRY ListHead,
 293                              IN PLIST_ENTRY ListEntry,
 294                              IN PKSPIN_LOCK Lock)
 295 /*
 296  * FUNCTION: Inserts an entry at the head of a doubly linked list
 297  * ARGUMENTS:
 298  *          ListHead  = Points to the head of the list
 299  *          ListEntry = Points to the entry to be inserted
 300  *          Lock      = Caller supplied spinlock used to synchronize access
 301  * RETURNS: The previous head of the list
 302  */
 303 {
 304   PLIST_ENTRY Old;
 305   KIRQL oldlvl;
 306
 307   KeAcquireSpinLock(Lock,&oldlvl);
 308   if (IsListEmpty(ListHead))
 309     {
 310       Old = NULL;
 311     }
 312   else
 313     {
 314       Old = ListHead->Flink;
 315      }
 316   InsertHeadList(ListHead,ListEntry);
 317   KeReleaseSpinLock(Lock,oldlvl);
 318
 319   return(Old);
 320 }
 321
 322
 323 /*
 324  * @implemented
 325  */
 326 PLIST_ENTRY FASTCALL
 327 ExfInterlockedInsertTailList(IN PLIST_ENTRY ListHead,
 328                              IN PLIST_ENTRY ListEntry,
 329                              IN PKSPIN_LOCK Lock)
 330 /*
 331  * FUNCTION: Inserts an entry at the tail of a doubly 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   PLIST_ENTRY Old;
 340   KIRQL oldlvl;
 341
 342   KeAcquireSpinLock(Lock,&oldlvl);
 343   if (IsListEmpty(ListHead))
 344     {
 345       Old = NULL;
 346     }
 347   else
 348     {
 349       Old = ListHead->Blink;
 350     }
 351   InsertTailList(ListHead,ListEntry);
 352   KeReleaseSpinLock(Lock,oldlvl);
 353
 354   return(Old);
 355 }
 356
 357
 358 /*
 359  * @implemented
 360  */
 361 PSINGLE_LIST_ENTRY FASTCALL
 362 ExfInterlockedPopEntryList(IN PSINGLE_LIST_ENTRY ListHead,
 363                            IN PKSPIN_LOCK Lock)
 364 /*
 365  * FUNCTION: Removes (pops) an entry from a singly list
 366  * ARGUMENTS:
 367  *          ListHead = Points to the head of the list
 368  *          Lock     = Lock for synchronizing access to the list
 369  * RETURNS: The removed entry
 370  */
 371 {
 372   PSINGLE_LIST_ENTRY ret;
 373   KIRQL oldlvl;
 374
 375   KeAcquireSpinLock(Lock,&oldlvl);
 376   ret = PopEntryList(ListHead);
 377   KeReleaseSpinLock(Lock,oldlvl);
 378   return(ret);
 379 }
 380
 381
 382 /*
 383  * @implemented
 384  */
 385 PSINGLE_LIST_ENTRY FASTCALL
 386 ExfInterlockedPushEntryList(IN PSINGLE_LIST_ENTRY ListHead,
 387                             IN PSINGLE_LIST_ENTRY ListEntry,
 388                             IN PKSPIN_LOCK Lock)
 389 /*
 390  * FUNCTION: Inserts (pushes) an entry into a singly linked list
 391  * ARGUMENTS:
 392  *          ListHead  = Points to the head of the list
 393  *          ListEntry = Points to the entry to be inserted
 394  *          Lock      = Caller supplied spinlock used to synchronize access
 395  * RETURNS: The previous head of the list
 396  */
 397 {
 398   KIRQL oldlvl;
 399   PSINGLE_LIST_ENTRY ret;
 400
 401   KeAcquireSpinLock(Lock,&oldlvl);
 402   ret=ListHead->Next;
 403   PushEntryList(ListHead,ListEntry);
 404   KeReleaseSpinLock(Lock,oldlvl);
 405   return(ret);
 406 }
 407
 408
 409 /*
 410  * @implemented
 411  */
 412 PLIST_ENTRY FASTCALL
 413 ExfInterlockedRemoveHeadList(IN PLIST_ENTRY Head,
 414                              IN PKSPIN_LOCK Lock)
 415 /*
 416  * FUNCTION: Removes the head of a double linked list
 417  * ARGUMENTS:
 418  *          Head = Points to the head of the list
 419  *          Lock = Lock for synchronizing access to the list
 420  * RETURNS: The removed entry
 421  */
 422 {
 423   PLIST_ENTRY ret;
 424   KIRQL oldlvl;
 425
 426   KeAcquireSpinLock(Lock,&oldlvl);
 427   if (IsListEmpty(Head))
 428     {
 429       ret = NULL;
 430     }
 431   else
 432     {
 433       ret = RemoveHeadList(Head);
 434     }
 435   KeReleaseSpinLock(Lock,oldlvl);
 436   return(ret);
 437 }
 438
 439
 440 /*
 441  * @implemented
 442  */
 443 PSLIST_ENTRY
 444 FASTCALL
 445 InterlockedPopEntrySList(IN PSLIST_HEADER ListHead)
 446 {
 447   SLIST_HEADER newslh, oldslh;
 448   PSLIST_ENTRY le;
 449
 450   do
 451   {
 452     oldslh = *(volatile SLIST_HEADER *)ListHead;
 453     le = oldslh.Next.Next;
 454     if(le == NULL)
 455     {
 456       /* nothing to do */
 457       return NULL;
 458     }
 459     newslh.Sequence = oldslh.Sequence + 1;
 460     newslh.Depth = oldslh.Depth - 1;
 461     newslh.Next.Next = MmSafeReadPtr(&le->Next);
 462   } while(ExfInterlockedCompareExchange64((PLONGLONG)&ListHead->Alignment,
 463                                           (PLONGLONG)&newslh.Alignment,
 464                                           (PLONGLONG)&oldslh.Alignment) != (LONGLONG)oldslh.Alignment);
 465
 466   return le;
 467 }
 468
 469
 470 /*
 471  * @implemented
 472  */
 473 PSLIST_ENTRY
 474 FASTCALL
 475 InterlockedPushEntrySList(IN PSLIST_HEADER ListHead,
 476                           IN PSLIST_ENTRY ListEntry)
 477 {
 478   SLIST_HEADER newslh, oldslh;
 479
 480   newslh.Next.Next = ListEntry;
 481
 482   do
 483   {
 484     oldslh = *(volatile SLIST_HEADER *)ListHead;
 485     newslh.Depth = oldslh.Depth + 1;
 486     newslh.Sequence = oldslh.Sequence + 1;
 487     ListEntry->Next = oldslh.Next.Next;
 488   } while(ExfInterlockedCompareExchange64((PLONGLONG)&ListHead->Alignment,
 489                                           (PLONGLONG)&newslh.Alignment,
 490                                           (PLONGLONG)&oldslh.Alignment) != (LONGLONG)oldslh.Alignment);
 491
 492   return oldslh.Next.Next;
 493 }
 494
 495 /* EOF */