• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.
list_new_internal(list_free_cb callback,const allocator_t * zeroed_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 
list_new(list_free_cb callback)34 list_t *list_new(list_free_cb callback) {
35   return list_new_internal(callback, &allocator_calloc);
36 }
37 
list_free(list_t * list)38 void list_free(list_t *list) {
39   if (!list)
40     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   assert(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   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 
list_length(const list_t * list)63 size_t list_length(const list_t *list) {
64   assert(list != NULL);
65   return list->length;
66 }
67 
list_front(const list_t * list)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 
list_back(const list_t * list)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 
list_insert_after(list_t * list,list_node_t * prev_node,void * data)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 
list_prepend(list_t * list,void * data)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 
list_append(list_t * list,void * data)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 
list_remove(list_t * list,void * data)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 
list_clear(list_t * list)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 
list_foreach(const list_t * list,list_iter_cb callback)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 
list_begin(const list_t * list)182 list_node_t *list_begin(const list_t *list) {
183   assert(list != NULL);
184   return list->head;
185 }
186 
list_end(UNUSED_ATTR const list_t * list)187 list_node_t *list_end(UNUSED_ATTR const list_t *list) {
188   assert(list != NULL);
189   return NULL;
190 }
191 
list_next(const list_node_t * node)192 list_node_t *list_next(const list_node_t *node) {
193   assert(node != NULL);
194   return node->next;
195 }
196 
list_node(const list_node_t * node)197 void *list_node(const list_node_t *node) {
198   assert(node != NULL);
199   return node->data;
200 }
201 
list_free_node_(list_t * list,list_node_t * node)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