1 #include <assert.h> 2 3 #include "list.h" 4 #include "osi.h" 5 6 typedef struct list_node_t { 7 struct list_node_t *next; 8 void *data; 9 } list_node_t; 10 11 typedef struct list_t { 12 list_node_t *head; 13 list_node_t *tail; 14 size_t length; 15 list_free_cb free_cb; 16 } list_t; 17 18 static list_node_t *list_free_node_(list_t *list, list_node_t *node); 19 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 25 // element removal. 26 list_t *list_new(list_free_cb callback) { 27 list_t *list = (list_t *)calloc(sizeof(list_t), 1); 28 if (list) 29 list->free_cb = callback; 30 return list; 31 } 32 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) { 36 if (list != NULL) 37 list_clear(list); 38 39 free(list); 40 } 41 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) { 46 assert(list != NULL); 47 return (list->length == 0); 48 } 49 50 // Returns the length of the list. This function does not accept a NULL list. 51 size_t list_length(const list_t *list) { 52 assert(list != NULL); 53 return list->length; 54 } 55 56 // Returns the first element in the list without removing it. |list| may not 57 // be NULL or empty. 58 void *list_front(const list_t *list) { 59 assert(list != NULL); 60 assert(!list_is_empty(list)); 61 62 return list->head->data; 63 } 64 65 // Returns the last element in the list without removing it. |list| may not 66 // be NULL or empty. 67 void *list_back(const list_t *list) { 68 assert(list != NULL); 69 assert(!list_is_empty(list)); 70 71 return list->tail->data; 72 } 73 74 bool list_insert_after(list_t *list, list_node_t *prev_node, void *data) { 75 assert(list != NULL); 76 assert(node != NULL); 77 assert(data != NULL); 78 79 list_node_t *node = (list_node_t *)malloc(sizeof(list_node_t)); 80 if (!node) 81 return false; 82 83 node->next = prev_node->next; 84 node->data = data; 85 prev_node->next = node; 86 if (list->tail == prev_node) 87 list->tail = node; 88 ++list->length; 89 return true; 90 } 91 92 // Inserts |data| at the beginning of |list|. Neither |data| nor |list| may be NULL. 93 // This function does not make a copy of |data| so the pointer must remain valid 94 // at least until the element is removed from the list or the list is freed. 95 // Returns true if |data| could be inserted, false otherwise (e.g. out of memory). 96 bool list_prepend(list_t *list, void *data) { 97 assert(list != NULL); 98 assert(data != NULL); 99 100 list_node_t *node = (list_node_t *)malloc(sizeof(list_node_t)); 101 if (!node) 102 return false; 103 node->next = list->head; 104 node->data = data; 105 list->head = node; 106 if (list->tail == NULL) 107 list->tail = list->head; 108 ++list->length; 109 return true; 110 } 111 112 // Inserts |data| at the end of |list|. Neither |data| nor |list| may be NULL. 113 // This function does not make a copy of |data| so the pointer must remain valid 114 // at least until the element is removed from the list or the list is freed. 115 // Returns true if |data| could be inserted, false otherwise (e.g. out of memory). 116 bool list_append(list_t *list, void *data) { 117 assert(list != NULL); 118 assert(data != NULL); 119 120 list_node_t *node = (list_node_t *)malloc(sizeof(list_node_t)); 121 if (!node) 122 return false; 123 node->next = NULL; 124 node->data = data; 125 if (list->tail == NULL) { 126 list->head = node; 127 list->tail = node; 128 } else { 129 list->tail->next = node; 130 list->tail = node; 131 } 132 ++list->length; 133 return true; 134 } 135 136 // Removes |data| from the list. Neither |list| nor |data| may be NULL. If |data| 137 // is inserted multiple times in the list, this function will only remove the first 138 // instance. If a free function was specified in |list_new|, it will be called back 139 // with |data|. This function returns true if |data| was found in the list and removed, 140 // false otherwise. 141 bool list_remove(list_t *list, void *data) { 142 assert(list != NULL); 143 assert(data != NULL); 144 145 if (list_is_empty(list)) 146 return false; 147 148 if (list->head->data == data) { 149 list_node_t *next = list_free_node_(list, list->head); 150 if (list->tail == list->head) 151 list->tail = next; 152 list->head = next; 153 return true; 154 } 155 156 for (list_node_t *prev = list->head, *node = list->head->next; node; prev = node, node = node->next) 157 if (node->data == data) { 158 prev->next = list_free_node_(list, node); 159 if (list->tail == node) 160 list->tail = prev; 161 return true; 162 } 163 164 return false; 165 } 166 167 // Removes all elements in the list. Calling this function will return the list to the 168 // same state it was in after |list_new|. |list| may not be NULL. 169 void list_clear(list_t *list) { 170 assert(list != NULL); 171 for (list_node_t *node = list->head; node; ) 172 node = list_free_node_(list, node); 173 list->head = NULL; 174 list->tail = NULL; 175 list->length = 0; 176 } 177 178 // Iterates through the entire |list| and calls |callback| for each data element. 179 // If the list is empty, |callback| will never be called. It is safe to mutate the 180 // list inside the callback. If an element is added before the node being visited, 181 // there will be no callback for the newly-inserted node. Neither |list| nor 182 // |callback| may be NULL. 183 void list_foreach(const list_t *list, list_iter_cb callback) { 184 assert(list != NULL); 185 assert(callback != NULL); 186 187 for (list_node_t *node = list->head; node; ) { 188 list_node_t *next = node->next; 189 callback(node->data); 190 node = next; 191 } 192 } 193 194 // Returns an iterator to the first element in |list|. |list| may not be NULL. 195 // The returned iterator is valid as long as it does not equal the value returned 196 // by |list_end|. 197 list_node_t *list_begin(const list_t *list) { 198 assert(list != NULL); 199 return list->head; 200 } 201 202 // Returns an iterator that points past the end of the list. In other words, 203 // this function returns the value of an invalid iterator for the given list. 204 // When an iterator has the same value as what's returned by this function, you 205 // may no longer call |list_next| with the iterator. |list| may not be NULL. 206 list_node_t *list_end(UNUSED_ATTR const list_t *list) { 207 assert(list != NULL); 208 return NULL; 209 } 210 211 // Given a valid iterator |node|, this function returns the next value for the 212 // iterator. If the returned value equals the value returned by |list_end|, the 213 // iterator has reached the end of the list and may no longer be used for any 214 // purpose. 215 list_node_t *list_next(const list_node_t *node) { 216 assert(node != NULL); 217 return node->next; 218 } 219 220 // Returns the value stored at the location pointed to by the iterator |node|. 221 // |node| must not equal the value returned by |list_end|. 222 void *list_node(const list_node_t *node) { 223 assert(node != NULL); 224 return node->data; 225 } 226 227 static list_node_t *list_free_node_(list_t *list, list_node_t *node) { 228 assert(list != NULL); 229 assert(node != NULL); 230 231 list_node_t *next = node->next; 232 233 if (list->free_cb) 234 list->free_cb(node->data); 235 free(node); 236 --list->length; 237 238 return next; 239 } 240
