1 /*-------------------------------------------------------------------------
4 * this is a simple doubly linked list implementation
5 * the elements of the lists are void*
7 * Portions Copyright (c) 1996-2010, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
12 * src/backend/lib/dllist.c
14 *-------------------------------------------------------------------------
18 #include "lib/dllist.h"
26 l = (Dllist *) palloc(sizeof(Dllist));
35 DLInitList(Dllist *list)
37 list->dll_head = NULL;
38 list->dll_tail = NULL;
42 * free up a list and all the nodes in it --- but *not* whatever the nodes
46 DLFreeList(Dllist *list)
50 while ((curr = DLRemHead(list)) != NULL)
61 e = (Dlelem *) palloc(sizeof(Dlelem));
71 DLInitElem(Dlelem *e, void *val)
88 Dllist *l = e->dle_list;
91 e->dle_prev->dle_next = e->dle_next;
94 /* must be the head element */
95 Assert(e == l->dll_head);
96 l->dll_head = e->dle_next;
99 e->dle_next->dle_prev = e->dle_prev;
102 /* must be the tail element */
103 Assert(e == l->dll_tail);
104 l->dll_tail = e->dle_prev;
113 DLAddHead(Dllist *l, Dlelem *e)
118 l->dll_head->dle_prev = e;
119 e->dle_next = l->dll_head;
123 if (l->dll_tail == NULL) /* if this is first element added */
128 DLAddTail(Dllist *l, Dlelem *e)
133 l->dll_tail->dle_next = e;
134 e->dle_prev = l->dll_tail;
138 if (l->dll_head == NULL) /* if this is first element added */
145 /* remove and return the head */
146 Dlelem *result = l->dll_head;
151 if (result->dle_next)
152 result->dle_next->dle_prev = NULL;
154 l->dll_head = result->dle_next;
156 if (result == l->dll_tail) /* if the head is also the tail */
159 result->dle_next = NULL;
160 result->dle_list = NULL;
168 /* remove and return the tail */
169 Dlelem *result = l->dll_tail;
174 if (result->dle_prev)
175 result->dle_prev->dle_next = NULL;
177 l->dll_tail = result->dle_prev;
179 if (result == l->dll_head) /* if the tail is also the head */
182 result->dle_prev = NULL;
183 result->dle_list = NULL;
188 /* Same as DLRemove followed by DLAddHead, but faster */
190 DLMoveToFront(Dlelem *e)
192 Dllist *l = e->dle_list;
194 if (l->dll_head == e)
195 return; /* Fast path if already at front */
197 Assert(e->dle_prev != NULL); /* since it's not the head */
198 e->dle_prev->dle_next = e->dle_next;
201 e->dle_next->dle_prev = e->dle_prev;
204 /* must be the tail element */
205 Assert(e == l->dll_tail);
206 l->dll_tail = e->dle_prev;
209 l->dll_head->dle_prev = e;
210 e->dle_next = l->dll_head;
213 /* We need not check dll_tail, since there must have been > 1 entry */