1 #include <assert.h> 2 3 #include "osi/include/allocator.h" 4 #include "osi/include/list.h" 5 #include "osi/include/osi.h" 6 7 struct list_node_t { 8 struct list_node_t *next; 9 void *data; 10 }; 11 12 typedef struct list_t { 13 list_node_t *head; 14 list_node_t *tail; 15 size_t length; 16 list_free_cb free_cb; 17 const allocator_t *allocator; 18 } list_t; 19 20 static list_node_t *list_free_node_(list_t *list, list_node_t *node); 21 22 // Hidden constructor, only to be used by the hash map for the allocation tracker. 23 // Behaves the same as |list_new|, except you get to specify the allocator. 24 list_t *list_new_internal(list_free_cb callback, const allocator_t *zeroed_allocator) { 25 list_t *list = (list_t *)zeroed_allocator->alloc(sizeof(list_t)); 26 if (!list) 27 return NULL; 28 29 list->free_cb = callback; 30 list->allocator = zeroed_allocator; 31 return list; 32 } 33 34 list_t *list_new(list_free_cb callback) { 35 return list_new_internal(callback, &allocator_calloc); 36 } 37 38 void list_free(list_t *list) { 39 if (!list) 40 return; 41 42 list_clear(list); 43 list->allocator->free(list); 44 } 45 46 bool list_is_empty(const list_t *list) { 47 assert(list != NULL); 48 return (list->length == 0); 49 } 50 51 bool list_contains(const list_t *list, const void *data) { 52 assert(list != NULL); 53 assert(data != NULL); 54 55 for (const list_node_t *node = list_begin(list); node != list_end(list); node = list_next(node)) { 56 if (list_node(node) == data) 57 return true; 58 } 59 60 return false; 61 } 62 63 size_t list_length(const list_t *list) { 64 assert(list != NULL); 65 return list->length; 66 } 67 68 void *list_front(const list_t *list) { 69 assert(list != NULL); 70 assert(!list_is_empty(list)); 71 72 return list->head->data; 73 } 74 75 void *list_back(const list_t *list) { 76 assert(list != NULL); 77 assert(!list_is_empty(list)); 78 79 return list->tail->data; 80 } 81 82 list_node_t *list_back_node(const list_t *list) { 83 assert(list != NULL); 84 assert(!list_is_empty(list)); 85 86 return list->tail; 87 } 88 89 bool list_insert_after(list_t *list, list_node_t *prev_node, void *data) { 90 assert(list != NULL); 91 assert(prev_node != NULL); 92 assert(data != NULL); 93 94 list_node_t *node = (list_node_t *)list->allocator->alloc(sizeof(list_node_t)); 95 if (!node) 96 return false; 97 98 node->next = prev_node->next; 99 node->data = data; 100 prev_node->next = node; 101 if (list->tail == prev_node) 102 list->tail = node; 103 ++list->length; 104 return true; 105 } 106 107 bool list_prepend(list_t *list, void *data) { 108 assert(list != NULL); 109 assert(data != NULL); 110 111 list_node_t *node = (list_node_t *)list->allocator->alloc(sizeof(list_node_t)); 112 if (!node) 113 return false; 114 node->next = list->head; 115 node->data = data; 116 list->head = node; 117 if (list->tail == NULL) 118 list->tail = list->head; 119 ++list->length; 120 return true; 121 } 122 123 bool list_append(list_t *list, void *data) { 124 assert(list != NULL); 125 assert(data != NULL); 126 127 list_node_t *node = (list_node_t *)list->allocator->alloc(sizeof(list_node_t)); 128 if (!node) 129 return false; 130 node->next = NULL; 131 node->data = data; 132 if (list->tail == NULL) { 133 list->head = node; 134 list->tail = node; 135 } else { 136 list->tail->next = node; 137 list->tail = node; 138 } 139 ++list->length; 140 return true; 141 } 142 143 bool list_remove(list_t *list, void *data) { 144 assert(list != NULL); 145 assert(data != NULL); 146 147 if (list_is_empty(list)) 148 return false; 149 150 if (list->head->data == data) { 151 list_node_t *next = list_free_node_(list, list->head); 152 if (list->tail == list->head) 153 list->tail = next; 154 list->head = next; 155 return true; 156 } 157 158 for (list_node_t *prev = list->head, *node = list->head->next; node; prev = node, node = node->next) 159 if (node->data == data) { 160 prev->next = list_free_node_(list, node); 161 if (list->tail == node) 162 list->tail = prev; 163 return true; 164 } 165 166 return false; 167 } 168 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 list_node_t *list_foreach(const list_t *list, list_iter_cb callback, void *context) { 179 assert(list != NULL); 180 assert(callback != NULL); 181 182 for (list_node_t *node = list->head; node; ) { 183 list_node_t *next = node->next; 184 if (!callback(node->data, context)) 185 return node; 186 node = next; 187 } 188 return NULL; 189 } 190 191 list_node_t *list_begin(const list_t *list) { 192 assert(list != NULL); 193 return list->head; 194 } 195 196 list_node_t *list_end(UNUSED_ATTR const list_t *list) { 197 assert(list != NULL); 198 return NULL; 199 } 200 201 list_node_t *list_next(const list_node_t *node) { 202 assert(node != NULL); 203 return node->next; 204 } 205 206 void *list_node(const list_node_t *node) { 207 assert(node != NULL); 208 return node->data; 209 } 210 211 static list_node_t *list_free_node_(list_t *list, list_node_t *node) { 212 assert(list != NULL); 213 assert(node != NULL); 214 215 list_node_t *next = node->next; 216 217 if (list->free_cb) 218 list->free_cb(node->data); 219 list->allocator->free(node); 220 --list->length; 221 222 return next; 223 } 224
