4 /* Initializes 'list' as an empty list. */
6 list_init(struct list *list)
8 list->next = list->prev = list;
11 /* Inserts 'elem' just before 'before'. */
13 list_insert(struct list *before, struct list *elem)
15 elem->prev = before->prev;
17 before->prev->next = elem;
21 /* Removes elements 'first' though 'last' (exclusive) from their current list,
22 then inserts them just before 'before'. */
24 list_splice(struct list *before, struct list *first, struct list *last)
30 /* Cleanly remove 'first'...'last' from its current list. */
31 first->prev->next = last->next;
32 last->next->prev = first->prev;
34 /* Splice 'first'...'last' into new list. */
35 first->prev = before->prev;
37 before->prev->next = first;
41 /* Inserts 'elem' at the beginning of 'list', so that it becomes the front in
44 list_push_front(struct list *list, struct list *elem)
46 list_insert(list->next, elem);
49 /* Inserts 'elem' at the end of 'list', so that it becomes the back in
52 list_push_back(struct list *list, struct list *elem)
54 list_insert(list, elem);
57 /* Puts 'elem' in the position currently occupied by 'position'.
58 * Afterward, 'position' is not part of a list. */
60 list_replace(struct list *element, const struct list *position)
62 element->next = position->next;
63 element->next->prev = element;
64 element->prev = position->prev;
65 element->prev->next = element;
68 /* Removes 'elem' from its list and returns the element that followed it.
69 Undefined behavior if 'elem' is not in a list. */
71 list_remove(struct list *elem)
73 elem->prev->next = elem->next;
74 elem->next->prev = elem->prev;
78 /* Removes the front element from 'list' and returns it. Undefined behavior if
79 'list' is empty before removal. */
81 list_pop_front(struct list *list)
83 struct list *front = list->next;
88 /* Removes the back element from 'list' and returns it.
89 Undefined behavior if 'list' is empty before removal. */
91 list_pop_back(struct list *list)
93 struct list *back = list->prev;
98 /* Returns the front element in 'list'.
99 Undefined behavior if 'list' is empty. */
101 list_front(struct list *list)
103 assert(!list_is_empty(list));
107 /* Returns the back element in 'list'.
108 Undefined behavior if 'list' is empty. */
110 list_back(struct list *list)
112 assert(!list_is_empty(list));
116 /* Returns the number of elements in 'list'.
117 Runs in O(n) in the number of elements. */
119 list_size(const struct list *list)
121 const struct list *e;
124 for (e = list->next; e != list; e = e->next)
129 /* Returns true if 'list' is empty, false otherwise. */
131 list_is_empty(const struct list *list)
133 return list->next == list;