granicus.if.org Git - postgresql/blob - 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-2004, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  *
  11  * IDENTIFICATION
  12  *        $PostgreSQL: pgsql/src/backend/lib/dllist.c,v 1.29 2004/08/29 04:12:32 momjian Exp $
  13  *
  14  *-------------------------------------------------------------------------
  15  */
  16
  17 /* can be used in frontend or backend */
  18 #ifdef FRONTEND
  19 #include "postgres_fe.h"
  20 /* No assert checks in frontend ... */
  21 #define Assert(condition)
  22 #else
  23 #include "postgres.h"
  24 #endif
  25
  26 #include "lib/dllist.h"
  27
  28
  29 Dllist *
  30 DLNewList(void)
  31 {
  32         Dllist     *l;
  33
  34         l = (Dllist *) malloc(sizeof(Dllist));
  35         if (l == NULL)
  36         {
  37 #ifdef FRONTEND
  38                 fprintf(stderr, "memory exhausted in DLNewList\n");
  39                 exit(1);
  40 #else
  41                 ereport(ERROR,
  42                                 (errcode(ERRCODE_OUT_OF_MEMORY),
  43                                  errmsg("out of memory")));
  44 #endif
  45         }
  46         l->dll_head = 0;
  47         l->dll_tail = 0;
  48
  49         return l;
  50 }
  51
  52 void
  53 DLInitList(Dllist *list)
  54 {
  55         list->dll_head = 0;
  56         list->dll_tail = 0;
  57 }
  58
  59 /*
  60  * free up a list and all the nodes in it --- but *not* whatever the nodes
  61  * might point to!
  62  */
  63 void
  64 DLFreeList(Dllist *list)
  65 {
  66         Dlelem     *curr;
  67
  68         while ((curr = DLRemHead(list)) != 0)
  69                 free(curr);
  70
  71         free(list);
  72 }
  73
  74 Dlelem *
  75 DLNewElem(void *val)
  76 {
  77         Dlelem     *e;
  78
  79         e = (Dlelem *) malloc(sizeof(Dlelem));
  80         if (e == NULL)
  81         {
  82 #ifdef FRONTEND
  83                 fprintf(stderr, "memory exhausted in DLNewElem\n");
  84                 exit(1);
  85 #else
  86                 ereport(ERROR,
  87                                 (errcode(ERRCODE_OUT_OF_MEMORY),
  88                                  errmsg("out of memory")));
  89 #endif
  90         }
  91         e->dle_next = 0;
  92         e->dle_prev = 0;
  93         e->dle_val = val;
  94         e->dle_list = 0;
  95         return e;
  96 }
  97
  98 void
  99 DLInitElem(Dlelem *e, void *val)
 100 {
 101         e->dle_next = 0;
 102         e->dle_prev = 0;
 103         e->dle_val = val;
 104         e->dle_list = 0;
 105 }
 106
 107 void
 108 DLFreeElem(Dlelem *e)
 109 {
 110         free(e);
 111 }
 112
 113 void
 114 DLRemove(Dlelem *e)
 115 {
 116         Dllist     *l = e->dle_list;
 117
 118         if (e->dle_prev)
 119                 e->dle_prev->dle_next = e->dle_next;
 120         else
 121         {
 122                 /* must be the head element */
 123                 Assert(e == l->dll_head);
 124                 l->dll_head = e->dle_next;
 125         }
 126         if (e->dle_next)
 127                 e->dle_next->dle_prev = e->dle_prev;
 128         else
 129         {
 130                 /* must be the tail element */
 131                 Assert(e == l->dll_tail);
 132                 l->dll_tail = e->dle_prev;
 133         }
 134
 135         e->dle_next = 0;
 136         e->dle_prev = 0;
 137         e->dle_list = 0;
 138 }
 139
 140 void
 141 DLAddHead(Dllist *l, Dlelem *e)
 142 {
 143         e->dle_list = l;
 144
 145         if (l->dll_head)
 146                 l->dll_head->dle_prev = e;
 147         e->dle_next = l->dll_head;
 148         e->dle_prev = 0;
 149         l->dll_head = e;
 150
 151         if (l->dll_tail == 0)           /* if this is first element added */
 152                 l->dll_tail = e;
 153 }
 154
 155 void
 156 DLAddTail(Dllist *l, Dlelem *e)
 157 {
 158         e->dle_list = l;
 159
 160         if (l->dll_tail)
 161                 l->dll_tail->dle_next = e;
 162         e->dle_prev = l->dll_tail;
 163         e->dle_next = 0;
 164         l->dll_tail = e;
 165
 166         if (l->dll_head == 0)           /* if this is first element added */
 167                 l->dll_head = e;
 168 }
 169
 170 Dlelem *
 171 DLRemHead(Dllist *l)
 172 {
 173         /* remove and return the head */
 174         Dlelem     *result = l->dll_head;
 175
 176         if (result == 0)
 177                 return result;
 178
 179         if (result->dle_next)
 180                 result->dle_next->dle_prev = 0;
 181
 182         l->dll_head = result->dle_next;
 183
 184         if (result == l->dll_tail)      /* if the head is also the tail */
 185                 l->dll_tail = 0;
 186
 187         result->dle_next = 0;
 188         result->dle_list = 0;
 189
 190         return result;
 191 }
 192
 193 Dlelem *
 194 DLRemTail(Dllist *l)
 195 {
 196         /* remove and return the tail */
 197         Dlelem     *result = l->dll_tail;
 198
 199         if (result == 0)
 200                 return result;
 201
 202         if (result->dle_prev)
 203                 result->dle_prev->dle_next = 0;
 204
 205         l->dll_tail = result->dle_prev;
 206
 207         if (result == l->dll_head)      /* if the tail is also the head */
 208                 l->dll_head = 0;
 209
 210         result->dle_prev = 0;
 211         result->dle_list = 0;
 212
 213         return result;
 214 }
 215
 216 /* Same as DLRemove followed by DLAddHead, but faster */
 217 void
 218 DLMoveToFront(Dlelem *e)
 219 {
 220         Dllist     *l = e->dle_list;
 221
 222         if (l->dll_head == e)
 223                 return;                                 /* Fast path if already at front */
 224
 225         Assert(e->dle_prev != 0);       /* since it's not the head */
 226         e->dle_prev->dle_next = e->dle_next;
 227
 228         if (e->dle_next)
 229                 e->dle_next->dle_prev = e->dle_prev;
 230         else
 231         {
 232                 /* must be the tail element */
 233                 Assert(e == l->dll_tail);
 234                 l->dll_tail = e->dle_prev;
 235         }
 236
 237         l->dll_head->dle_prev = e;
 238         e->dle_next = l->dll_head;
 239         e->dle_prev = 0;
 240         l->dll_head = e;
 241         /* We need not check dll_tail, since there must have been > 1 entry */
 242 }