1 #include <base/logging.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 23 // tracker. 24 // Behaves the same as |list_new|, except you get to specify the allocator. 25 list_t* list_new_internal(list_free_cb callback, 26 const allocator_t* zeroed_allocator) { 27 list_t* list = (list_t*)zeroed_allocator->alloc(sizeof(list_t)); 28 if (!list) return NULL; 29 30 list->free_cb = callback; 31 list->allocator = zeroed_allocator; 32 return list; 33 } 34 35 list_t* list_new(list_free_cb callback) { 36 return list_new_internal(callback, &allocator_calloc); 37 } 38 39 void list_free(list_t* list) { 40 if (!list) return; 41 42 list_clear(list); 43 list->allocator->free(list); 44 } 45 46 bool list_is_empty(const list_t* list) { 47 CHECK(list != NULL); 48 return (list->length == 0); 49 } 50 51 bool list_contains(const list_t* list, const void* data) { 52 CHECK(list != NULL); 53 CHECK(data != NULL); 54 55 for (const list_node_t* node = list_begin(list); node != list_end(list); 56 node = list_next(node)) { 57 if (list_node(node) == data) return true; 58 } 59 60 return false; 61 } 62 63 size_t list_length(const list_t* list) { 64 CHECK(list != NULL); 65 return list->length; 66 } 67 68 void* list_front(const list_t* list) { 69 CHECK(list != NULL); 70 CHECK(!list_is_empty(list)); 71 72 return list->head->data; 73 } 74 75 void* list_back(const list_t* list) { 76 CHECK(list != NULL); 77 CHECK(!list_is_empty(list)); 78 79 return list->tail->data; 80 } 81 82 list_node_t* list_back_node(const list_t* list) { 83 CHECK(list != NULL); 84 CHECK(!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 CHECK(list != NULL); 91 CHECK(prev_node != NULL); 92 CHECK(data != NULL); 93 94 list_node_t* node = (list_node_t*)list->allocator->alloc(sizeof(list_node_t)); 95 if (!node) return false; 96 97 node->next = prev_node->next; 98 node->data = data; 99 prev_node->next = node; 100 if (list->tail == prev_node) list->tail = node; 101 ++list->length; 102 return true; 103 } 104 105 bool list_prepend(list_t* list, void* data) { 106 CHECK(list != NULL); 107 CHECK(data != NULL); 108 109 list_node_t* node = (list_node_t*)list->allocator->alloc(sizeof(list_node_t)); 110 if (!node) return false; 111 node->next = list->head; 112 node->data = data; 113 list->head = node; 114 if (list->tail == NULL) list->tail = list->head; 115 ++list->length; 116 return true; 117 } 118 119 bool list_append(list_t* list, void* data) { 120 CHECK(list != NULL); 121 CHECK(data != NULL); 122 123 list_node_t* node = (list_node_t*)list->allocator->alloc(sizeof(list_node_t)); 124 if (!node) return false; 125 node->next = NULL; 126 node->data = data; 127 if (list->tail == NULL) { 128 list->head = node; 129 list->tail = node; 130 } else { 131 list->tail->next = node; 132 list->tail = node; 133 } 134 ++list->length; 135 return true; 136 } 137 138 bool list_remove(list_t* list, void* data) { 139 CHECK(list != NULL); 140 CHECK(data != NULL); 141 142 if (list_is_empty(list)) return false; 143 144 if (list->head->data == data) { 145 list_node_t* next = list_free_node_(list, list->head); 146 if (list->tail == list->head) 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; 152 prev = node, node = node->next) 153 if (node->data == data) { 154 prev->next = list_free_node_(list, node); 155 if (list->tail == node) list->tail = prev; 156 return true; 157 } 158 159 return false; 160 } 161 162 void list_clear(list_t* list) { 163 CHECK(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 list_node_t* list_foreach(const list_t* list, list_iter_cb callback, 172 void* context) { 173 CHECK(list != NULL); 174 CHECK(callback != NULL); 175 176 for (list_node_t* node = list->head; node;) { 177 list_node_t* next = node->next; 178 if (!callback(node->data, context)) return node; 179 node = next; 180 } 181 return NULL; 182 } 183 184 list_node_t* list_begin(const list_t* list) { 185 CHECK(list != NULL); 186 return list->head; 187 } 188 189 list_node_t* list_end(UNUSED_ATTR const list_t* list) { 190 CHECK(list != NULL); 191 return NULL; 192 } 193 194 list_node_t* list_next(const list_node_t* node) { 195 CHECK(node != NULL); 196 return node->next; 197 } 198 199 void* list_node(const list_node_t* node) { 200 CHECK(node != NULL); 201 return node->data; 202 } 203 204 static list_node_t* list_free_node_(list_t* list, list_node_t* node) { 205 CHECK(list != NULL); 206 CHECK(node != NULL); 207 208 list_node_t* next = node->next; 209 210 if (list->free_cb) list->free_cb(node->data); 211 list->allocator->free(node); 212 --list->length; 213 214 return next; 215 } 216
