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