src/backend/lib/dllist.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * dllist.c
   4  *        this is a simple doubly linked list implementation
   5  *        the elements of the lists are void*
   6  *
   7  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  *
  11  * IDENTIFICATION
  12  *        $PostgreSQL$
  13  *
  14  *-------------------------------------------------------------------------
  15  */
  16 #include "postgres.h"
  17
  18 #include "lib/dllist.h"
  19
  20
  21 Dllist *
  22 DLNewList(void)
  23 {
  24         Dllist     *l;
  25
  26         l = (Dllist *) palloc(sizeof(Dllist));
  27
  28         l->dll_head = NULL;
  29         l->dll_tail = NULL;
  30
  31         return l;
  32 }
  33
  34 void
  35 DLInitList(Dllist *list)
  36 {
  37         list->dll_head = NULL;
  38         list->dll_tail = NULL;
  39 }
  40
  41 /*
  42  * free up a list and all the nodes in it --- but *not* whatever the nodes
  43  * might point to!
  44  */
  45 void
  46 DLFreeList(Dllist *list)
  47 {
  48         Dlelem     *curr;
  49
  50         while ((curr = DLRemHead(list)) != NULL)
  51                 pfree(curr);
  52
  53         pfree(list);
  54 }
  55
  56 Dlelem *
  57 DLNewElem(void *val)
  58 {
  59         Dlelem     *e;
  60
  61         e = (Dlelem *) palloc(sizeof(Dlelem));
  62
  63         e->dle_next = NULL;
  64         e->dle_prev = NULL;
  65         e->dle_val = val;
  66         e->dle_list = NULL;
  67         return e;
  68 }
  69
  70 void
  71 DLInitElem(Dlelem *e, void *val)
  72 {
  73         e->dle_next = NULL;
  74         e->dle_prev = NULL;
  75         e->dle_val = val;
  76         e->dle_list = NULL;
  77 }
  78
  79 void
  80 DLFreeElem(Dlelem *e)
  81 {
  82         pfree(e);
  83 }
  84
  85 void
  86 DLRemove(Dlelem *e)
  87 {
  88         Dllist     *l = e->dle_list;
  89
  90         if (e->dle_prev)
  91                 e->dle_prev->dle_next = e->dle_next;
  92         else
  93         {
  94                 /* must be the head element */
  95                 Assert(e == l->dll_head);
  96                 l->dll_head = e->dle_next;
  97         }
  98         if (e->dle_next)
  99                 e->dle_next->dle_prev = e->dle_prev;
 100         else
 101         {
 102                 /* must be the tail element */
 103                 Assert(e == l->dll_tail);
 104                 l->dll_tail = e->dle_prev;
 105         }
 106
 107         e->dle_next = NULL;
 108         e->dle_prev = NULL;
 109         e->dle_list = NULL;
 110 }
 111
 112 void
 113 DLAddHead(Dllist *l, Dlelem *e)
 114 {
 115         e->dle_list = l;
 116
 117         if (l->dll_head)
 118                 l->dll_head->dle_prev = e;
 119         e->dle_next = l->dll_head;
 120         e->dle_prev = NULL;
 121         l->dll_head = e;
 122
 123         if (l->dll_tail == NULL)        /* if this is first element added */
 124                 l->dll_tail = e;
 125 }
 126
 127 void
 128 DLAddTail(Dllist *l, Dlelem *e)
 129 {
 130         e->dle_list = l;
 131
 132         if (l->dll_tail)
 133                 l->dll_tail->dle_next = e;
 134         e->dle_prev = l->dll_tail;
 135         e->dle_next = NULL;
 136         l->dll_tail = e;
 137
 138         if (l->dll_head == NULL)        /* if this is first element added */
 139                 l->dll_head = e;
 140 }
 141
 142 Dlelem *
 143 DLRemHead(Dllist *l)
 144 {
 145         /* remove and return the head */
 146         Dlelem     *result = l->dll_head;
 147
 148         if (result == NULL)
 149                 return result;
 150
 151         if (result->dle_next)
 152                 result->dle_next->dle_prev = NULL;
 153
 154         l->dll_head = result->dle_next;
 155
 156         if (result == l->dll_tail)      /* if the head is also the tail */
 157                 l->dll_tail = NULL;
 158
 159         result->dle_next = NULL;
 160         result->dle_list = NULL;
 161
 162         return result;
 163 }
 164
 165 Dlelem *
 166 DLRemTail(Dllist *l)
 167 {
 168         /* remove and return the tail */
 169         Dlelem     *result = l->dll_tail;
 170
 171         if (result == NULL)
 172                 return result;
 173
 174         if (result->dle_prev)
 175                 result->dle_prev->dle_next = NULL;
 176
 177         l->dll_tail = result->dle_prev;
 178
 179         if (result == l->dll_head)      /* if the tail is also the head */
 180                 l->dll_head = NULL;
 181
 182         result->dle_prev = NULL;
 183         result->dle_list = NULL;
 184
 185         return result;
 186 }
 187
 188 /* Same as DLRemove followed by DLAddHead, but faster */
 189 void
 190 DLMoveToFront(Dlelem *e)
 191 {
 192         Dllist     *l = e->dle_list;
 193
 194         if (l->dll_head == e)
 195                 return;                                 /* Fast path if already at front */
 196
 197         Assert(e->dle_prev != NULL);    /* since it's not the head */
 198         e->dle_prev->dle_next = e->dle_next;
 199
 200         if (e->dle_next)
 201                 e->dle_next->dle_prev = e->dle_prev;
 202         else
 203         {
 204                 /* must be the tail element */
 205                 Assert(e == l->dll_tail);
 206                 l->dll_tail = e->dle_prev;
 207         }
 208
 209         l->dll_head->dle_prev = e;
 210         e->dle_next = l->dll_head;
 211         e->dle_prev = NULL;
 212         l->dll_head = e;
 213         /* We need not check dll_tail, since there must have been > 1 entry */
 214 }