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 (struct 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 (struct 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 (struct 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 (struct 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 (struct 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 (struct list_elem *before, struct 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 (struct list_elem *before,
182 struct list_elem *first, struct 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, struct 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, struct 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 (struct 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 struct list_elem *front = list_front (list);
240 /* Removes the back element from LIST and returns it.
241 Undefined behavior if LIST is empty before removal. */
243 list_pop_back (struct list *list)
245 struct list_elem *back = list_back (list);
250 /* Returns the front element in LIST.
251 Undefined behavior if LIST is empty. */
253 list_front (struct list *list)
255 ASSERT (!list_empty (list));
256 return list->head.next;
259 /* Returns the back element in LIST.
260 Undefined behavior if LIST is empty. */
262 list_back (struct list *list)
264 ASSERT (!list_empty (list));
265 return list->tail.prev;
268 /* Returns the number of elements in LIST.
269 Runs in O(n) in the number of elements. */
271 list_size (struct list *list)
276 for (e = list_begin (list); e != list_end (list); e = list_next (e))
281 /* Returns true if LIST is empty, false otherwise. */
283 list_empty (struct list *list)
285 return list_begin (list) == list_end (list);
288 /* Swaps the `struct list_elem *'s that A and B point to. */
290 swap (struct list_elem **a, struct list_elem **b)
292 struct list_elem *t = *a;
297 /* Reverses the order of LIST. */
299 list_reverse (struct list *list)
301 if (!list_empty (list))
305 for (e = list_begin (list); e != list_end (list); e = e->prev)
306 swap (&e->prev, &e->next);
307 swap (&list->head.next, &list->tail.prev);
308 swap (&list->head.next->prev, &list->tail.prev->next);
312 /* Returns true only if the list elements A through B (exclusive)
313 are in order according to LESS given auxiliary data AUX. */
315 is_sorted (struct list_elem *a, struct list_elem *b,
316 list_less_func *less, void *aux)
319 while ((a = list_next (a)) != b)
320 if (less (a, list_prev (a), aux))
325 /* Finds a run, starting at A and ending not after B, of list
326 elements that are in nondecreasing order according to LESS
327 given auxiliary data AUX. Returns the (exclusive) end of the
329 A through B (exclusive) must form a non-empty range. */
330 static struct list_elem *
331 find_end_of_run (struct list_elem *a, struct list_elem *b,
332 list_less_func *less, void *aux)
336 ASSERT (less != NULL);
343 while (a != b && !less (a, list_prev (a), aux));
347 /* Merges A0 through A1B0 (exclusive) with A1B0 through B1
348 (exclusive) to form a combined range also ending at B1
349 (exclusive). Both input ranges must be nonempty and sorted in
350 nondecreasing order according to LESS given auxiliary data
351 AUX. The output range will be sorted the same way. */
353 inplace_merge (struct list_elem *a0, struct list_elem *a1b0,
354 struct list_elem *b1,
355 list_less_func *less, void *aux)
358 ASSERT (a1b0 != NULL);
360 ASSERT (less != NULL);
361 ASSERT (is_sorted (a0, a1b0, less, aux));
362 ASSERT (is_sorted (a1b0, b1, less, aux));
364 while (a0 != a1b0 && a1b0 != b1)
365 if (!less (a1b0, a0, aux))
369 a1b0 = list_next (a1b0);
370 list_splice (a0, list_prev (a1b0), a1b0);
374 /* Sorts LIST according to LESS given auxiliary data AUX, using a
375 natural iterative merge sort that runs in O(n lg n) time and
376 O(1) space in the number of elements in LIST. */
378 list_sort (struct list *list, list_less_func *less, void *aux)
380 size_t output_run_cnt; /* Number of runs output in current pass. */
382 ASSERT (list != NULL);
383 ASSERT (less != NULL);
385 /* Pass over the list repeatedly, merging adjacent runs of
386 nondecreasing elements, until only one run is left. */
389 struct list_elem *a0; /* Start of first run. */
390 struct list_elem *a1b0; /* End of first run, start of second. */
391 struct list_elem *b1; /* End of second run. */
394 for (a0 = list_begin (list); a0 != list_end (list); a0 = b1)
396 /* Each iteration produces one output run. */
399 /* Locate two adjacent runs of nondecreasing elements
400 A0...A1B0 and A1B0...B1. */
401 a1b0 = find_end_of_run (a0, list_end (list), less, aux);
402 if (a1b0 == list_end (list))
404 b1 = find_end_of_run (a1b0, list_end (list), less, aux);
406 /* Merge the runs. */
407 inplace_merge (a0, a1b0, b1, less, aux);
410 while (output_run_cnt > 1);
412 ASSERT (is_sorted (list_begin (list), list_end (list), less, aux));
415 /* Inserts ELEM in the proper position in LIST, which must be
416 sorted according to LESS given auxiliary data AUX.
417 Runs in O(n) average case in the number of elements in LIST. */
419 list_insert_ordered (struct list *list, struct list_elem *elem,
420 list_less_func *less, void *aux)
424 ASSERT (list != NULL);
425 ASSERT (elem != NULL);
426 ASSERT (less != NULL);
428 for (e = list_begin (list); e != list_end (list); e = list_next (e))
429 if (less (elem, e, aux))
431 return list_insert (e, elem);
434 /* Iterates through LIST and removes all but the first in each
435 set of adjacent elements that are equal according to LESS
436 given auxiliary data AUX. If DUPLICATES is non-null, then the
437 elements from LIST are appended to DUPLICATES. */
439 list_unique (struct list *list, struct list *duplicates,
440 list_less_func *less, void *aux)
442 struct list_elem *elem, *next;
444 ASSERT (list != NULL);
445 ASSERT (less != NULL);
446 if (list_empty (list))
449 elem = list_begin (list);
450 while ((next = list_next (elem)) != list_end (list))
451 if (!less (elem, next, aux) && !less (next, elem, aux))
454 if (duplicates != NULL)
455 list_push_back (duplicates, next);
461 /* Returns the element in LIST with the largest value according
462 to LESS given auxiliary data AUX. If there is more than one
463 maximum, returns the one that appears earlier in the list. If
464 the list is empty, returns its tail. */
466 list_max (struct list *list, list_less_func *less, void *aux)
468 struct list_elem *max = list_begin (list);
469 if (max != list_end (list))
473 for (e = list_next (max); e != list_end (list); e = list_next (e))
474 if (less (max, e, aux))
480 /* Returns the element in LIST with the smallest value according
481 to LESS given auxiliary data AUX. If there is more than one
482 minimum, returns the one that appears earlier in the list. If
483 the list is empty, returns its tail. */
485 list_min (struct list *list, list_less_func *less, void *aux)
487 struct list_elem *min = list_begin (list);
488 if (min != list_end (list))
492 for (e = list_next (min); e != list_end (list); e = list_next (e))
493 if (less (e, min, aux))