reactos/ntoskrnl/rtl/list.c

   1 /*
   2  * COPYRIGHT:           See COPYING in the top level directory
   3  * PROJECT:             ReactOS kernel
   4  * FILE:                ntoskrnl/rtl/list.c
   5  * PURPOSE:             Manages linked lists
   6  * PROGRAMMER:          David Welch (welch@mcmail.com)
   7  */
   8
   9 /* INCLUDES *****************************************************************/
  10
  11 #include <ddk/ntddk.h>
  12
  13 #define NDEBUG
  14 #include <internal/debug.h>
  15
  16 /* FUNCTIONS *************************************************************/
  17
  18 static BOOLEAN CheckEntry(PLIST_ENTRY ListEntry)
  19 {
  20    assert(ListEntry!=NULL);
  21    assert(ListEntry->Blink!=NULL);
  22    assert(ListEntry->Blink->Flink!=NULL);
  23    assert(ListEntry->Flink!=NULL);
  24    assert(ListEntry->Flink->Blink!=NULL);
  25    return(TRUE);
  26 }
  27
  28 BOOLEAN IsListEmpty(PLIST_ENTRY ListHead)
  29 /*
  30  * FUNCTION: Determines if a list is empty
  31  * ARGUMENTS:
  32  *        ListHead = Head of the list
  33  * RETURNS: True if there are no entries in the list
  34  */
  35 {
  36    return(ListHead->Flink==ListHead);
  37 }
  38
  39 VOID RemoveEntryList(PLIST_ENTRY ListEntry)
  40 {
  41    PLIST_ENTRY OldFlink;
  42    PLIST_ENTRY OldBlink;
  43
  44    DPRINT("RemoveEntryList(ListEntry %x)\n", ListEntry);
  45
  46    assert(CheckEntry(ListEntry));
  47
  48    OldFlink=ListEntry->Flink;
  49    OldBlink=ListEntry->Blink;
  50
  51    OldFlink->Blink=OldBlink;
  52    OldBlink->Flink=OldFlink;
  53
  54    assert(CheckEntry(ListEntry));
  55
  56    DPRINT("RemoveEntryList()\n");
  57 }
  58
  59 PLIST_ENTRY RemoveTailList(PLIST_ENTRY ListHead)
  60 /*
  61  * FUNCTION: Remove the tail entry from a double linked list
  62  * ARGUMENTS:
  63  *         ListHead = Head of the list to remove from
  64  * RETURNS: The removed entry
  65  */
  66 {
  67    PLIST_ENTRY Old = ListHead->Blink;
  68    RemoveEntryList(ListHead->Blink);
  69    return(Old);
  70 }
  71
  72 PLIST_ENTRY RemoveHeadList(PLIST_ENTRY ListHead)
  73 {
  74    PLIST_ENTRY Old;
  75
  76    DPRINT("RemoveHeadList(ListHead %x)\n",ListHead);
  77
  78    assert(CheckEntry(ListHead));
  79
  80    Old = ListHead->Flink;
  81    RemoveEntryList(ListHead->Flink);
  82
  83    assert(CheckEntry(ListHead));
  84
  85    DPRINT("RemoveHeadList()\n");
  86
  87    return(Old);
  88 }
  89
  90 VOID InitializeListHead(PLIST_ENTRY ListHead)
  91 /*
  92  * FUNCTION: Initializes a double linked list
  93  * ARGUMENTS:
  94  *         ListHead = Caller supplied storage for the head of the list
  95  */
  96 {
  97    ListHead->Flink = ListHead->Blink = ListHead;
  98 }
  99
 100 VOID InsertTailList(PLIST_ENTRY ListHead, PLIST_ENTRY ListEntry)
 101 /*
 102  * FUNCTION: Inserts an entry in a double linked list
 103  * ARGUMENTS:
 104  *        ListHead = Head of the list
 105  *        Entry = Entry to insert
 106  */
 107 {
 108    PLIST_ENTRY Blink;
 109
 110    Blink = ListHead->Blink;
 111    ListEntry->Flink=ListHead;
 112    ListEntry->Blink=Blink;
 113    Blink->Flink=ListEntry;
 114    ListHead->Blink=ListEntry;
 115 }
 116
 117 VOID InsertHeadList(PLIST_ENTRY ListHead, PLIST_ENTRY ListEntry)
 118 {
 119    PLIST_ENTRY OldFlink;
 120
 121    OldFlink = ListHead->Flink;
 122    ListEntry->Flink = OldFlink;
 123    ListEntry->Blink = ListHead;
 124    OldFlink->Blink = ListEntry;
 125    ListHead->Flink = ListEntry;
 126 }
 127
 128 PLIST_ENTRY ExInterlockedInsertTailList(PLIST_ENTRY ListHead,
 129                                         PLIST_ENTRY ListEntry,
 130                                         PKSPIN_LOCK Lock)
 131 {
 132    PLIST_ENTRY Old;
 133    KIRQL oldlvl;
 134
 135    KeAcquireSpinLock(Lock,&oldlvl);
 136    if (IsListEmpty(ListHead))
 137      {
 138         Old = NULL;
 139      }
 140    else
 141      {
 142         Old = ListHead->Blink;
 143      }
 144    InsertTailList(ListHead,ListEntry);
 145    KeReleaseSpinLock(Lock,oldlvl);
 146
 147    return(Old);
 148 }
 149
 150 PLIST_ENTRY ExInterlockedInsertHeadList(PLIST_ENTRY ListHead,
 151                                         PLIST_ENTRY ListEntry,
 152                                         PKSPIN_LOCK Lock)
 153 /*
 154  * FUNCTION: Inserts an entry at the head of a doubly linked list
 155  * ARGUMENTS:
 156  *          ListHead = Points to the head of the list
 157  *          ListEntry = Points to the entry to be inserted
 158  *          Lock = Caller supplied spinlock used to synchronise access
 159  * RETURNS: The previous head of the list
 160  */
 161 {
 162    PLIST_ENTRY Old;
 163    KIRQL oldlvl;
 164
 165    KeAcquireSpinLock(Lock,&oldlvl);
 166    if (IsListEmpty(ListHead))
 167      {
 168         Old = NULL;
 169      }
 170    else
 171      {
 172         Old = ListHead->Flink;
 173      }
 174    InsertHeadList(ListHead,ListEntry);
 175    KeReleaseSpinLock(Lock,oldlvl);
 176
 177    return(Old);
 178 }
 179
 180
 181 PLIST_ENTRY ExInterlockedRemoveHeadList(PLIST_ENTRY Head,
 182                                         PKSPIN_LOCK Lock)
 183 /*
 184  * FUNCTION: Removes the head of a double linked list
 185  * ARGUMENTS:
 186  *          Head = List head
 187  *          Lock = Lock for synchronizing access to the list
 188  * RETURNS: The removed entry
 189  */
 190 {
 191    PLIST_ENTRY ret;
 192    KIRQL oldlvl;
 193
 194    KeAcquireSpinLock(Lock,&oldlvl);
 195    if (IsListEmpty(Head))
 196      {
 197         ret = NULL;
 198      }
 199    else
 200      {
 201         ret = RemoveHeadList(Head);
 202      }
 203    KeReleaseSpinLock(Lock,oldlvl);
 204    return(ret);
 205 }
 206
 207 PLIST_ENTRY ExInterlockedRemoveTailList(PLIST_ENTRY Head,
 208                                         PKSPIN_LOCK Lock)
 209 /*
 210  * FUNCTION: Removes the tail of a double linked list
 211  * ARGUMENTS:
 212  *          Head = List head
 213  *          Lock = Lock for synchronizing access to the list
 214  * RETURNS: The removed entry
 215  */
 216 {
 217    PLIST_ENTRY ret;
 218    KIRQL oldlvl;
 219
 220    KeAcquireSpinLock(Lock,&oldlvl);
 221    if (IsListEmpty(Head))
 222      {
 223         ret = NULL;
 224      }
 225    else
 226      {
 227         ret = RemoveTailList(Head);
 228      }
 229    KeReleaseSpinLock(Lock,oldlvl);
 230    return(ret);
 231 }