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.
list_new_internal(list_free_cb callback,const allocator_t * zeroed_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 
list_new(list_free_cb callback)35 list_t* list_new(list_free_cb callback) {
36   return list_new_internal(callback, &allocator_calloc);
37 }
38 
list_free(list_t * list)39 void list_free(list_t* list) {
40   if (!list) return;
41 
42   list_clear(list);
43   list->allocator->free(list);
44 }
45 
list_is_empty(const list_t * list)46 bool list_is_empty(const list_t* list) {
47   CHECK(list != NULL);
48   return (list->length == 0);
49 }
50 
list_contains(const list_t * list,const void * data)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 
list_length(const list_t * list)63 size_t list_length(const list_t* list) {
64   CHECK(list != NULL);
65   return list->length;
66 }
67 
list_front(const list_t * list)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 
list_back(const list_t * list)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 
list_back_node(const list_t * list)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 
list_insert_after(list_t * list,list_node_t * prev_node,void * data)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 
list_prepend(list_t * list,void * data)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 
list_append(list_t * list,void * data)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 
list_remove(list_t * list,void * data)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 
list_clear(list_t * list)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 
list_foreach(const list_t * list,list_iter_cb callback,void * context)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 
list_begin(const list_t * list)184 list_node_t* list_begin(const list_t* list) {
185   CHECK(list != NULL);
186   return list->head;
187 }
188 
list_end(UNUSED_ATTR const list_t * list)189 list_node_t* list_end(UNUSED_ATTR const list_t* list) {
190   CHECK(list != NULL);
191   return NULL;
192 }
193 
list_next(const list_node_t * node)194 list_node_t* list_next(const list_node_t* node) {
195   CHECK(node != NULL);
196   return node->next;
197 }
198 
list_node(const list_node_t * node)199 void* list_node(const list_node_t* node) {
200   CHECK(node != NULL);
201   return node->data;
202 }
203 
list_free_node_(list_t * list,list_node_t * node)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