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 static bool is_sorted (struct list_elem *a, struct list_elem *b,
35 list_less_func *less, void *aux) UNUSED;
37 /* Returns true if ELEM is a head, false otherwise. */
39 is_head (struct list_elem *elem)
41 return elem != NULL && elem->prev == NULL && elem->next != NULL;
44 /* Returns true if ELEM is an interior element,
47 is_interior (struct list_elem *elem)
49 return elem != NULL && elem->prev != NULL && elem->next != NULL;
52 /* Returns true if ELEM is a tail, false otherwise. */
54 is_tail (struct list_elem *elem)
56 return elem != NULL && elem->prev != NULL && elem->next == NULL;
59 /* Initializes LIST as an empty list. */
61 list_init (struct list *list)
63 ASSERT (list != NULL);
64 list->head.prev = NULL;
65 list->head.next = &list->tail;
66 list->tail.prev = &list->head;
67 list->tail.next = NULL;
70 /* Returns the beginning of LIST. */
72 list_begin (struct list *list)
74 ASSERT (list != NULL);
75 return list->head.next;
78 /* Returns the element after ELEM in its list. If ELEM is the
79 last element in its list, returns the list tail. Results are
80 undefined if ELEM is itself a list tail. */
82 list_next (struct list_elem *elem)
84 ASSERT (is_head (elem) || is_interior (elem));
88 /* Returns LIST's tail.
90 list_end() is often used in iterating through a list from
91 front to back. See the big comment at the top of list.h for
94 list_end (struct list *list)
96 ASSERT (list != NULL);
100 /* Returns the LIST's reverse beginning, for iterating through
101 LIST in reverse order, from back to front. */
103 list_rbegin (struct list *list)
105 ASSERT (list != NULL);
106 return list->tail.prev;
109 /* Returns the element before ELEM in its list. If ELEM is the
110 first element in its list, returns the list head. Results are
111 undefined if ELEM is itself a list head. */
113 list_prev (struct list_elem *elem)
115 ASSERT (is_interior (elem) || is_tail (elem));
119 /* Returns LIST's head.
121 list_rend() is often used in iterating through a list in
122 reverse order, from back to front. Here's typical usage,
123 following the example from the top of list.h:
125 for (e = list_rbegin (&foo_list); e != list_rend (&foo_list);
128 struct foo *f = list_entry (e, struct foo, elem);
129 ...do something with f...
133 list_rend (struct list *list)
135 ASSERT (list != NULL);
139 /* Return's LIST's head.
141 list_head() can be used for an alternate style of iterating
142 through a list, e.g.:
144 e = list_head (&list);
145 while ((e = list_next (e)) != list_end (&list))
151 list_head (struct list *list)
153 ASSERT (list != NULL);
157 /* Return's LIST's tail. */
159 list_tail (struct list *list)
161 ASSERT (list != NULL);
165 /* Inserts ELEM just before BEFORE, which may be either an
166 interior element or a tail. The latter case is equivalent to
169 list_insert (struct list_elem *before, struct list_elem *elem)
171 ASSERT (is_interior (before) || is_tail (before));
172 ASSERT (elem != NULL);
174 elem->prev = before->prev;
176 before->prev->next = elem;
180 /* Removes elements FIRST though LAST (exclusive) from their
181 current list, then inserts them just before BEFORE, which may
182 be either an interior element or a tail. */
184 list_splice (struct list_elem *before,
185 struct list_elem *first, struct list_elem *last)
187 ASSERT (is_interior (before) || is_tail (before));
190 last = list_prev (last);
192 ASSERT (is_interior (first));
193 ASSERT (is_interior (last));
195 /* Cleanly remove FIRST...LAST from its current list. */
196 first->prev->next = last->next;
197 last->next->prev = first->prev;
199 /* Splice FIRST...LAST into new list. */
200 first->prev = before->prev;
202 before->prev->next = first;
206 /* Inserts ELEM at the beginning of LIST, so that it becomes the
209 list_push_front (struct list *list, struct list_elem *elem)
211 list_insert (list_begin (list), elem);
214 /* Inserts ELEM at the end of LIST, so that it becomes the
217 list_push_back (struct list *list, struct list_elem *elem)
219 list_insert (list_end (list), elem);
222 /* Removes ELEM from its list and returns the element that
223 followed it. Undefined behavior if ELEM is not in a list.
225 It's not safe to treat ELEM as an element in a list after
226 removing it. In particular, using list_next() or list_prev()
227 on ELEM after removal yields undefined behavior. This means
228 that a naive loop to remove the elements in a list will fail:
231 for (e = list_begin (&list); e != list_end (&list); e = list_next (e))
233 ...do something with e...
238 Here is one correct way to iterate and remove elements from a
241 for (e = list_begin (&list); e != list_end (&list); e = list_remove (e))
243 ...do something with e...
246 If you need to free() elements of the list then you need to be
247 more conservative. Here's an alternate strategy that works
250 while (!list_empty (&list))
252 struct list_elem *e = list_pop_front (&list);
253 ...do something with e...
257 list_remove (struct list_elem *elem)
259 ASSERT (is_interior (elem));
260 elem->prev->next = elem->next;
261 elem->next->prev = elem->prev;
265 /* Removes the front element from LIST and returns it.
266 Undefined behavior if LIST is empty before removal. */
268 list_pop_front (struct list *list)
270 struct list_elem *front = list_front (list);
275 /* Removes the back element from LIST and returns it.
276 Undefined behavior if LIST is empty before removal. */
278 list_pop_back (struct list *list)
280 struct list_elem *back = list_back (list);
285 /* Returns the front element in LIST.
286 Undefined behavior if LIST is empty. */
288 list_front (struct list *list)
290 ASSERT (!list_empty (list));
291 return list->head.next;
294 /* Returns the back element in LIST.
295 Undefined behavior if LIST is empty. */
297 list_back (struct list *list)
299 ASSERT (!list_empty (list));
300 return list->tail.prev;
303 /* Returns the number of elements in LIST.
304 Runs in O(n) in the number of elements. */
306 list_size (struct list *list)
311 for (e = list_begin (list); e != list_end (list); e = list_next (e))
316 /* Returns true if LIST is empty, false otherwise. */
318 list_empty (struct list *list)
320 return list_begin (list) == list_end (list);
323 /* Swaps the `struct list_elem *'s that A and B point to. */
325 swap (struct list_elem **a, struct list_elem **b)
327 struct list_elem *t = *a;
332 /* Reverses the order of LIST. */
334 list_reverse (struct list *list)
336 if (!list_empty (list))
340 for (e = list_begin (list); e != list_end (list); e = e->prev)
341 swap (&e->prev, &e->next);
342 swap (&list->head.next, &list->tail.prev);
343 swap (&list->head.next->prev, &list->tail.prev->next);
347 /* Returns true only if the list elements A through B (exclusive)
348 are in order according to LESS given auxiliary data AUX. */
350 is_sorted (struct list_elem *a, struct list_elem *b,
351 list_less_func *less, void *aux)
354 while ((a = list_next (a)) != b)
355 if (less (a, list_prev (a), aux))
360 /* Finds a run, starting at A and ending not after B, of list
361 elements that are in nondecreasing order according to LESS
362 given auxiliary data AUX. Returns the (exclusive) end of the
364 A through B (exclusive) must form a non-empty range. */
365 static struct list_elem *
366 find_end_of_run (struct list_elem *a, struct list_elem *b,
367 list_less_func *less, void *aux)
371 ASSERT (less != NULL);
378 while (a != b && !less (a, list_prev (a), aux));
382 /* Merges A0 through A1B0 (exclusive) with A1B0 through B1
383 (exclusive) to form a combined range also ending at B1
384 (exclusive). Both input ranges must be nonempty and sorted in
385 nondecreasing order according to LESS given auxiliary data
386 AUX. The output range will be sorted the same way. */
388 inplace_merge (struct list_elem *a0, struct list_elem *a1b0,
389 struct list_elem *b1,
390 list_less_func *less, void *aux)
393 ASSERT (a1b0 != NULL);
395 ASSERT (less != NULL);
396 ASSERT (is_sorted (a0, a1b0, less, aux));
397 ASSERT (is_sorted (a1b0, b1, less, aux));
399 while (a0 != a1b0 && a1b0 != b1)
400 if (!less (a1b0, a0, aux))
404 a1b0 = list_next (a1b0);
405 list_splice (a0, list_prev (a1b0), a1b0);
409 /* Sorts LIST according to LESS given auxiliary data AUX, using a
410 natural iterative merge sort that runs in O(n lg n) time and
411 O(1) space in the number of elements in LIST. */
413 list_sort (struct list *list, list_less_func *less, void *aux)
415 size_t output_run_cnt; /* Number of runs output in current pass. */
417 ASSERT (list != NULL);
418 ASSERT (less != NULL);
420 /* Pass over the list repeatedly, merging adjacent runs of
421 nondecreasing elements, until only one run is left. */
424 struct list_elem *a0; /* Start of first run. */
425 struct list_elem *a1b0; /* End of first run, start of second. */
426 struct list_elem *b1; /* End of second run. */
429 for (a0 = list_begin (list); a0 != list_end (list); a0 = b1)
431 /* Each iteration produces one output run. */
434 /* Locate two adjacent runs of nondecreasing elements
435 A0...A1B0 and A1B0...B1. */
436 a1b0 = find_end_of_run (a0, list_end (list), less, aux);
437 if (a1b0 == list_end (list))
439 b1 = find_end_of_run (a1b0, list_end (list), less, aux);
441 /* Merge the runs. */
442 inplace_merge (a0, a1b0, b1, less, aux);
445 while (output_run_cnt > 1);
447 ASSERT (is_sorted (list_begin (list), list_end (list), less, aux));
450 /* Inserts ELEM in the proper position in LIST, which must be
451 sorted according to LESS given auxiliary data AUX.
452 Runs in O(n) average case in the number of elements in LIST. */
454 list_insert_ordered (struct list *list, struct list_elem *elem,
455 list_less_func *less, void *aux)
459 ASSERT (list != NULL);
460 ASSERT (elem != NULL);
461 ASSERT (less != NULL);
463 for (e = list_begin (list); e != list_end (list); e = list_next (e))
464 if (less (elem, e, aux))
466 return list_insert (e, elem);
469 /* Iterates through LIST and removes all but the first in each
470 set of adjacent elements that are equal according to LESS
471 given auxiliary data AUX. If DUPLICATES is non-null, then the
472 elements from LIST are appended to DUPLICATES. */
474 list_unique (struct list *list, struct list *duplicates,
475 list_less_func *less, void *aux)
477 struct list_elem *elem, *next;
479 ASSERT (list != NULL);
480 ASSERT (less != NULL);
481 if (list_empty (list))
484 elem = list_begin (list);
485 while ((next = list_next (elem)) != list_end (list))
486 if (!less (elem, next, aux) && !less (next, elem, aux))
489 if (duplicates != NULL)
490 list_push_back (duplicates, next);
496 /* Returns the element in LIST with the largest value according
497 to LESS given auxiliary data AUX. If there is more than one
498 maximum, returns the one that appears earlier in the list. If
499 the list is empty, returns its tail. */
501 list_max (struct list *list, list_less_func *less, void *aux)
503 struct list_elem *max = list_begin (list);
504 if (max != list_end (list))
508 for (e = list_next (max); e != list_end (list); e = list_next (e))
509 if (less (max, e, aux))
515 /* Returns the element in LIST with the smallest value according
516 to LESS given auxiliary data AUX. If there is more than one
517 minimum, returns the one that appears earlier in the list. If
518 the list is empty, returns its tail. */
520 list_min (struct list *list, list_less_func *less, void *aux)
522 struct list_elem *min = list_begin (list);
523 if (min != list_end (list))
527 for (e = list_next (min); e != list_end (list); e = list_next (e))
528 if (less (e, min, aux))