6 typedef struct list_node_t {
7 struct list_node_t *next;
11 typedef struct list_t {
18 static list_node_t *list_free_node_(list_t *list, list_node_t *node);
20 // Returns a new, empty list. Returns NULL if not enough memory could be allocated
21 // for the list structure. The returned list must be freed with |list_free|. The
22 // |callback| specifies a function to be called whenever a list element is removed
23 // from the list. It can be used to release resources held by the list element, e.g.
24 // memory or file descriptor. |callback| may be NULL if no cleanup is necessary on
26 list_t *list_new(list_free_cb callback) {
27 list_t *list = (list_t *)calloc(sizeof(list_t), 1);
29 list->free_cb = callback;
33 // Frees the list. This function accepts NULL as an argument, in which case it
34 // behaves like a no-op.
35 void list_free(list_t *list) {
42 // Returns true if the list is empty (has no elements), false otherwise.
43 // Note that a NULL list is not the same as an empty list. This function
44 // does not accept a NULL list.
45 bool list_is_empty(const list_t *list) {
47 return (list->length == 0);
50 bool list_contains(const list_t *list, const void *data) {
54 for (const list_node_t *node = list_begin(list); node != list_end(list); node = list_next(node)) {
55 if (list_node(node) == data)
62 // Returns the length of the list. This function does not accept a NULL list.
63 size_t list_length(const list_t *list) {
68 // Returns the first element in the list without removing it. |list| may not
70 void *list_front(const list_t *list) {
72 assert(!list_is_empty(list));
74 return list->head->data;
77 // Returns the last element in the list without removing it. |list| may not
79 void *list_back(const list_t *list) {
81 assert(!list_is_empty(list));
83 return list->tail->data;
86 bool list_insert_after(list_t *list, list_node_t *prev_node, void *data) {
91 list_node_t *node = (list_node_t *)malloc(sizeof(list_node_t));
95 node->next = prev_node->next;
97 prev_node->next = node;
98 if (list->tail == prev_node)
104 // Inserts |data| at the beginning of |list|. Neither |data| nor |list| may be NULL.
105 // This function does not make a copy of |data| so the pointer must remain valid
106 // at least until the element is removed from the list or the list is freed.
107 // Returns true if |data| could be inserted, false otherwise (e.g. out of memory).
108 bool list_prepend(list_t *list, void *data) {
109 assert(list != NULL);
110 assert(data != NULL);
112 list_node_t *node = (list_node_t *)malloc(sizeof(list_node_t));
115 node->next = list->head;
118 if (list->tail == NULL)
119 list->tail = list->head;
124 // Inserts |data| at the end of |list|. Neither |data| nor |list| may be NULL.
125 // This function does not make a copy of |data| so the pointer must remain valid
126 // at least until the element is removed from the list or the list is freed.
127 // Returns true if |data| could be inserted, false otherwise (e.g. out of memory).
128 bool list_append(list_t *list, void *data) {
129 assert(list != NULL);
130 assert(data != NULL);
132 list_node_t *node = (list_node_t *)malloc(sizeof(list_node_t));
137 if (list->tail == NULL) {
141 list->tail->next = node;
148 // Removes |data| from the list. Neither |list| nor |data| may be NULL. If |data|
149 // is inserted multiple times in the list, this function will only remove the first
150 // instance. If a free function was specified in |list_new|, it will be called back
151 // with |data|. This function returns true if |data| was found in the list and removed,
153 bool list_remove(list_t *list, void *data) {
154 assert(list != NULL);
155 assert(data != NULL);
157 if (list_is_empty(list))
160 if (list->head->data == data) {
161 list_node_t *next = list_free_node_(list, list->head);
162 if (list->tail == list->head)
168 for (list_node_t *prev = list->head, *node = list->head->next; node; prev = node, node = node->next)
169 if (node->data == data) {
170 prev->next = list_free_node_(list, node);
171 if (list->tail == node)
179 // Removes all elements in the list. Calling this function will return the list to the
180 // same state it was in after |list_new|. |list| may not be NULL.
181 void list_clear(list_t *list) {
182 assert(list != NULL);
183 for (list_node_t *node = list->head; node; )
184 node = list_free_node_(list, node);
190 // Iterates through the entire |list| and calls |callback| for each data element.
191 // If the list is empty, |callback| will never be called. It is safe to mutate the
192 // list inside the callback. If an element is added before the node being visited,
193 // there will be no callback for the newly-inserted node. Neither |list| nor
194 // |callback| may be NULL.
195 void list_foreach(const list_t *list, list_iter_cb callback) {
196 assert(list != NULL);
197 assert(callback != NULL);
199 for (list_node_t *node = list->head; node; ) {
200 list_node_t *next = node->next;
201 callback(node->data);
206 // Returns an iterator to the first element in |list|. |list| may not be NULL.
207 // The returned iterator is valid as long as it does not equal the value returned
209 list_node_t *list_begin(const list_t *list) {
210 assert(list != NULL);
214 // Returns an iterator that points past the end of the list. In other words,
215 // this function returns the value of an invalid iterator for the given list.
216 // When an iterator has the same value as what's returned by this function, you
217 // may no longer call |list_next| with the iterator. |list| may not be NULL.
218 list_node_t *list_end(UNUSED_ATTR const list_t *list) {
219 assert(list != NULL);
223 // Given a valid iterator |node|, this function returns the next value for the
224 // iterator. If the returned value equals the value returned by |list_end|, the
225 // iterator has reached the end of the list and may no longer be used for any
227 list_node_t *list_next(const list_node_t *node) {
228 assert(node != NULL);
232 // Returns the value stored at the location pointed to by the iterator |node|.
233 // |node| must not equal the value returned by |list_end|.
234 void *list_node(const list_node_t *node) {
235 assert(node != NULL);
239 static list_node_t *list_free_node_(list_t *list, list_node_t *node) {
240 assert(list != NULL);
241 assert(node != NULL);
243 list_node_t *next = node->next;
246 list->free_cb(node->data);