4 /* Our doubly linked lists have two header elements: the "head"
5 just before the first element and the "tail" just after the
6 last element. The `prev' link of the front header is null, as
7 is the `next' link of the back header. Their other two links
8 point toward each other via the interior elements of the list.
10 An empty list looks like this:
13 <---| head |<--->| tail |--->
16 A list with two elements in it looks like this:
18 +------+ +-------+ +-------+ +------+
19 <---| head |<--->| 1 |<--->| 2 |<--->| tail |<--->
20 +------+ +-------+ +-------+ +------+
22 The symmetry of this arrangement eliminates lots of special
23 cases in list processing. For example, take a look at
24 list_remove(): it takes only two pointer assignments and no
25 conditionals. That's a lot simpler than the code would be
26 without header elements.
28 (Because only one of the pointers in each header element is used,
29 we could in fact combine them into a single header element
30 without sacrificing this simplicity. But using two separate
31 elements allows us to do a little bit of checking on some
32 operations, which can be valuable.) */
34 /* Returns true if ELEM is a head, false otherwise. */
36 is_head (list_elem *elem)
38 return elem != NULL && elem->prev == NULL && elem->next != NULL;
41 /* Returns true if ELEM is an interior element,
44 is_interior (list_elem *elem)
46 return elem != NULL && elem->prev != NULL && elem->next != NULL;
49 /* Returns true if ELEM is a tail, false otherwise. */
51 is_tail (list_elem *elem)
53 return elem != NULL && elem->prev != NULL && elem->next == NULL;
56 /* Initializes LIST as an empty list. */
58 list_init (struct list *list)
60 ASSERT (list != NULL);
61 list->head.prev = NULL;
62 list->head.next = &list->tail;
63 list->tail.prev = &list->head;
64 list->tail.next = NULL;
67 /* Returns the beginning of LIST. */
69 list_begin (struct list *list)
71 ASSERT (list != NULL);
72 return list->head.next;
75 /* Returns the element after ELEM in its list. If ELEM is the
76 last element in its list, returns the list tail. Results are
77 undefined if ELEM is itself a list tail. */
79 list_next (list_elem *elem)
81 ASSERT (is_head (elem) || is_interior (elem));
85 /* Returns LIST's tail.
87 list_end() is often used in iterating through a list from
88 front to back. See the big comment at the top of list.h for
91 list_end (struct list *list)
93 ASSERT (list != NULL);
97 /* Returns the LIST's reverse beginning, for iterating through
98 LIST in reverse order, from back to front. */
100 list_rbegin (struct list *list)
102 ASSERT (list != NULL);
103 return list->tail.prev;
106 /* Returns the element before ELEM in its list. If ELEM is the
107 first element in its list, returns the list head. Results are
108 undefined if ELEM is itself a list head. */
110 list_prev (list_elem *elem)
112 ASSERT (is_interior (elem) || is_tail (elem));
116 /* Returns LIST's head.
118 list_rend() is often used in iterating through a list in
119 reverse order, from back to front. Here's typical usage,
120 following the example from the top of list.h:
122 for (e = list_rbegin (&foo_list); e != list_rend (&foo_list);
125 struct foo *f = list_entry (e, struct foo, elem);
126 ...do something with f...
130 list_rend (struct list *list)
132 ASSERT (list != NULL);
136 /* Return's LIST's head.
138 list_head() can be used for an alternate style of iterating
139 through a list, e.g.:
141 e = list_head (&list);
142 while ((e = list_next (e)) != list_end (&list))
148 list_head (struct list *list)
150 ASSERT (list != NULL);
154 /* Return's LIST's tail. */
156 list_tail (struct list *list)
158 ASSERT (list != NULL);
162 /* Inserts ELEM just before BEFORE, which may be either an
163 interior element or a tail. The latter case is equivalent to
166 list_insert (list_elem *before, list_elem *elem)
168 ASSERT (is_interior (before) || is_tail (before));
169 ASSERT (elem != NULL);
171 elem->prev = before->prev;
173 before->prev->next = elem;
177 /* Removes elements FIRST though LAST (exclusive) from their
178 current list, then inserts them just before BEFORE, which may
179 be either an interior element or a tail. */
181 list_splice (list_elem *before,
182 list_elem *first, list_elem *last)
184 ASSERT (is_interior (before) || is_tail (before));
187 last = list_prev (last);
189 ASSERT (is_interior (first));
190 ASSERT (is_interior (last));
192 /* Cleanly remove FIRST...LAST from its current list. */
193 first->prev->next = last->next;
194 last->next->prev = first->prev;
196 /* Splice FIRST...LAST into new list. */
197 first->prev = before->prev;
199 before->prev->next = first;
203 /* Inserts ELEM at the beginning of LIST, so that it becomes the
206 list_push_front (struct list *list, list_elem *elem)
208 list_insert (list_begin (list), elem);
211 /* Inserts ELEM at the end of LIST, so that it becomes the
214 list_push_back (struct list *list, list_elem *elem)
216 list_insert (list_end (list), elem);
219 /* Removes ELEM from its list and returns the element that
220 followed it. Undefined behavior if ELEM is not in a list. */
222 list_remove (list_elem *elem)
224 ASSERT (is_interior (elem));
225 elem->prev->next = elem->next;
226 elem->next->prev = elem->prev;
230 /* Removes the front element from LIST and returns it.
231 Undefined behavior if LIST is empty before removal. */
233 list_pop_front (struct list *list)
235 ASSERT (list != NULL);
236 return list_remove (list_front (list));
239 /* Removes the back element from LIST and returns it.
240 Undefined behavior if LIST is empty before removal. */
242 list_pop_back (struct list *list)
244 ASSERT (list != NULL);
245 return list_remove (list_back (list));
248 /* Returns the front element in LIST.
249 Undefined behavior if LIST is empty. */
251 list_front (struct list *list)
253 ASSERT (!list_empty (list));
254 return list->head.next;
257 /* Returns the back element in LIST.
258 Undefined behavior if LIST is empty. */
260 list_back (struct list *list)
262 ASSERT (!list_empty (list));
263 return list->tail.prev;
266 /* Returns the number of elements in LIST.
267 Runs in O(n) in the number of elements. */
269 list_size (struct list *list)
274 for (e = list_begin (list); e != list_end (list); e = list_next (e))
279 /* Returns true if LIST is empty, false otherwise. */
281 list_empty (struct list *list)
283 return list_begin (list) == list_end (list);
286 /* Swaps the `list_elem *'s that A and B point to. */
288 swap (list_elem **a, list_elem **b)
295 /* Reverses the order of LIST. */
297 list_reverse (struct list *list)
299 if (!list_empty (list))
303 for (e = list_begin (list); e != list_end (list); e = e->prev)
304 swap (&e->prev, &e->next);
305 swap (&list->head.next, &list->tail.prev);
306 swap (&list->head.next->prev, &list->tail.prev->next);
310 /* Merges lists AL and BL, which must each be sorted according to
311 LESS given auxiliary data AUX, by inserting each element of BL
312 at the proper place in AL to preserve the ordering.
313 Runs in O(n) in the combined length of AL and BL. */
315 list_merge (struct list *al, struct list *bl,
316 list_less_func *less, void *aux)
322 ASSERT (less != NULL);
325 while (a != list_end (al))
327 list_elem *b = list_begin (bl);
328 if (less (b, a, aux))
330 list_splice (a, b, list_next (b));
337 list_splice (list_end (al), list_begin (bl), list_end (bl));
340 /* Sorts LIST according to LESS given auxiliary data AUX.
341 Runs in O(n lg n) in the number of elements in LIST. */
343 list_sort (struct list *list,
344 list_less_func *less, void *aux)
347 list_elem *middle, *last;
349 ASSERT (list != NULL);
350 ASSERT (less != NULL);
352 /* Empty and 1-element lists are already sorted. */
353 if (list_empty (list) || list_next (list_begin (list)) == list_end (list))
356 /* Find middle of LIST. (We're not interested in the end of
357 the list but it's incidentally needed.) */
358 middle = last = list_begin (list);
359 while (last != list_end (list) && list_next (last) != list_end (list))
361 middle = list_next (middle);
362 last = list_next (list_next (last));
365 /* Extract first half of LIST into a temporary list. */
367 list_splice (list_begin (&tmp), list_begin (list), middle);
369 /* Sort each half-list and merge the result. */
370 list_sort (&tmp, less, aux);
371 list_sort (list, less, aux);
372 list_merge (list, &tmp, less, aux);
375 /* Inserts ELEM in the proper position in LIST, which must be
376 sorted according to LESS given auxiliary data AUX.
377 Runs in O(n) average case in the number of elements in LIST. */
379 list_insert_ordered (struct list *list, list_elem *elem,
380 list_less_func *less, void *aux)
384 ASSERT (list != NULL);
385 ASSERT (elem != NULL);
386 ASSERT (less != NULL);
388 for (e = list_begin (list); e != list_end (list); e = list_next (e))
389 if (less (elem, e, aux))
391 return list_insert (e, elem);
394 /* Iterates through LIST and removes all but the first in each
395 set of adjacent elements that are equal according to LESS
396 given auxiliary data AUX. If DUPLICATES is non-null, then the
397 elements from LIST are appended to DUPLICATES. */
399 list_unique (struct list *list, struct list *duplicates,
400 list_less_func *less, void *aux)
402 list_elem *elem, *next;
404 ASSERT (list != NULL);
405 ASSERT (less != NULL);
406 if (list_empty (list))
409 elem = list_begin (list);
410 while ((next = list_next (elem)) != list_end (list))
411 if (!less (elem, next, aux) && !less (next, elem, aux))
414 if (duplicates != NULL)
415 list_push_back (duplicates, next);