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 bool list_insert_after(list_t *list, list_node_t *prev_node, void *data) { 83 assert(list != NULL); 84 assert(prev_node != NULL); 85 assert(data != NULL); 86 87 list_node_t *node = (list_node_t *)list->allocator->alloc(sizeof(list_node_t)); 88 if (!node) 89 return false; 90 91 node->next = prev_node->next; 92 node->data = data; 93 prev_node->next = node; 94 if (list->tail == prev_node) 95 list->tail = node; 96 ++list->length; 97 return true; 98 } 99 100 bool list_prepend(list_t *list, void *data) { 101 assert(list != NULL); 102 assert(data != NULL); 103 104 list_node_t *node = (list_node_t *)list->allocator->alloc(sizeof(list_node_t)); 105 if (!node) 106 return false; 107 node->next = list->head; 108 node->data = data; 109 list->head = node; 110 if (list->tail == NULL) 111 list->tail = list->head; 112 ++list->length; 113 return true; 114 } 115 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 *)list->allocator->alloc(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 bool list_remove(list_t *list, void *data) { 137 assert(list != NULL); 138 assert(data != NULL); 139 140 if (list_is_empty(list)) 141 return false; 142 143 if (list->head->data == data) { 144 list_node_t *next = list_free_node_(list, list->head); 145 if (list->tail == list->head) 146 list->tail = next; 147 list->head = next; 148 return true; 149 } 150 151 for (list_node_t *prev = list->head, *node = list->head->next; node; prev = node, node = node->next) 152 if (node->data == data) { 153 prev->next = list_free_node_(list, node); 154 if (list->tail == node) 155 list->tail = prev; 156 return true; 157 } 158 159 return false; 160 } 161 162 void list_clear(list_t *list) { 163 assert(list != NULL); 164 for (list_node_t *node = list->head; node; ) 165 node = list_free_node_(list, node); 166 list->head = NULL; 167 list->tail = NULL; 168 list->length = 0; 169 } 170 171 void list_foreach(const list_t *list, list_iter_cb callback) { 172 assert(list != NULL); 173 assert(callback != NULL); 174 175 for (list_node_t *node = list->head; node; ) { 176 list_node_t *next = node->next; 177 callback(node->data); 178 node = next; 179 } 180 } 181 182 list_node_t *list_begin(const list_t *list) { 183 assert(list != NULL); 184 return list->head; 185 } 186 187 list_node_t *list_end(UNUSED_ATTR const list_t *list) { 188 assert(list != NULL); 189 return NULL; 190 } 191 192 list_node_t *list_next(const list_node_t *node) { 193 assert(node != NULL); 194 return node->next; 195 } 196 197 void *list_node(const list_node_t *node) { 198 assert(node != NULL); 199 return node->data; 200 } 201 202 static list_node_t *list_free_node_(list_t *list, list_node_t *node) { 203 assert(list != NULL); 204 assert(node != NULL); 205 206 list_node_t *next = node->next; 207 208 if (list->free_cb) 209 list->free_cb(node->data); 210 list->allocator->free(node); 211 --list->length; 212 213 return next; 214 } 215
