5 list_init (struct list *list)
7 list->head.prev = NULL;
8 list->head.next = &list->tail;
9 list->tail.prev = &list->head;
10 list->tail.next = NULL;
14 list_begin (struct list *list)
16 return list->head.next;
20 list_end (struct list *list)
26 is_head (list_elem *elem)
28 return elem != NULL && elem->prev == NULL && elem->next != NULL;
32 is_real (list_elem *elem)
34 return elem != NULL && elem->prev != NULL && elem->next != NULL;
38 is_tail (list_elem *elem)
40 return elem != NULL && elem->prev != NULL && elem->next == NULL;
44 list_next (list_elem *elem)
46 ASSERT (is_real (elem));
51 list_prev (list_elem *elem)
53 ASSERT (is_real (elem) || is_tail (elem));
58 list_insert (list_elem *before, list_elem *elem)
60 ASSERT (is_real (before) || is_tail (before));
61 ASSERT (elem != NULL);
63 elem->prev = before->prev;
65 before->prev->next = elem;
70 list_splice (list_elem *target,
71 list_elem *first, list_elem *last)
73 ASSERT (is_real (target) || is_tail (target));
76 last = list_prev (last);
78 ASSERT (is_real (first));
79 ASSERT (is_real (last));
81 /* Cleanly remove FIRST...LAST from its current list. */
82 first->prev->next = last->next;
83 last->next->prev = first->prev;
85 /* Splice FIRST...LAST into new list. */
86 first->prev = target->prev;
88 target->prev->next = first;
93 list_push_front (struct list *list, list_elem *elem)
95 list_insert (list_begin (list), elem);
99 list_push_back (struct list *list, list_elem *elem)
101 list_insert (list_end (list), elem);
105 remove_item (list_elem *elem)
107 ASSERT (is_real (elem));
108 elem->prev->next = elem->next;
109 elem->next->prev = elem->prev;
114 list_remove (list_elem *elem)
120 list_pop_front (struct list *list)
122 return remove_item (list_front (list));
126 list_pop_back (struct list *list)
128 return remove_item (list_back (list));
132 list_front (struct list *list)
134 return list_begin (list);
138 list_back (struct list *list)
140 return list_prev (list_end (list));
144 list_size (struct list *list)
149 for (elem = list_begin (list); elem != list_end (list); elem = elem->next)
155 list_empty (struct list *list)
157 return list_begin (list) == list_end (list);
161 list_reverse (struct list *list)
165 for (e = &list->head; e != NULL; e = e->prev)
167 list_elem *tep = e->prev;
173 list->head = list->tail;
178 list_merge (struct list *al, struct list *bl,
179 list_less_func *less, void *aux)
185 ASSERT (less != NULL);
188 while (a != list_end (al))
190 list_elem *b = list_begin (bl);
191 if (less (b, a, aux))
193 list_splice (a, b, list_next (b));
200 list_splice (list_end (al), list_begin (bl), list_end (bl));
204 list_sort (struct list *list,
205 list_less_func *less, void *aux)
208 list_elem *middle, *last;
210 ASSERT (list != NULL);
211 ASSERT (less != NULL);
213 /* Empty and 1-element lists are already sorted. */
214 if (list_empty (list) || list_next (list_begin (list)) == list_end (list))
217 /* Find middle of LIST. (We're not interested in the end of
218 the list but it's incidentally needed.) */
219 middle = list_begin (list);
220 last = list_next (middle);
221 while (last != list_end (list) && list_next (last) != list_end (list))
223 middle = list_next (middle);
224 last = list_next (list_next (last));
227 /* Extract first half of LIST into a temporary list. */
229 list_splice (list_begin (&tmp), list_begin (list), middle);
231 /* Sort each half-list and merge the result. */
232 list_sort (&tmp, less, aux);
233 list_sort (list, less, aux);
234 list_merge (list, &tmp, less, aux);
238 list_insert_ordered (struct list *list, list_elem *elem,
239 list_less_func *less, void *aux)
243 ASSERT (list != NULL);
244 ASSERT (elem != NULL);
245 ASSERT (less != NULL);
247 for (e = list_begin (list); e != list_end (list); e = list_next (e))
248 if (less (elem, e, aux))
250 return list_insert (e, elem);
254 list_unique (struct list *list,
255 list_less_func *less, void *aux)
257 list_elem *elem, *next;
259 ASSERT (list != NULL);
260 ASSERT (less != NULL);
261 if (list_empty (list))
264 elem = list_begin (list);
265 while ((next = list_next (elem)) != list_end (list))
266 if (!less (elem, next, aux) && !less (next, elem, aux))