1 #include "bt_common.h"
2 #include "osi/allocator.h"
3 #include "osi/list.h"
4 #include "osi/osi.h"
5
6 struct list_node_t {
7 struct list_node_t *next;
8 void *data;
9 };
10
11 typedef struct list_t {
12 list_node_t *head;
13 list_node_t *tail;
14 size_t length;
15 list_free_cb free_cb;
16 } list_t;
17
18 //static list_node_t *list_free_node_(list_t *list, list_node_t *node);
19
20 // Hidden constructor, only to be used by the hash map for the allocation tracker.
21 // Behaves the same as |list_new|, except you get to specify the allocator.
list_new_internal(list_free_cb callback)22 list_t *list_new_internal(list_free_cb callback)
23 {
24 list_t *list = (list_t *) osi_calloc(sizeof(list_t));
25 if (!list) {
26 return NULL;
27 }
28
29 list->head = list->tail = NULL;
30 list->length = 0;
31 list->free_cb = callback;
32 return list;
33 }
34
list_new(list_free_cb callback)35 list_t *list_new(list_free_cb callback)
36 {
37 return list_new_internal(callback);
38 }
39
list_free(list_t * list)40 void list_free(list_t *list)
41 {
42 if (!list) {
43 return;
44 }
45
46 list_clear(list);
47 osi_free(list);
48 }
49
list_is_empty(const list_t * list)50 bool list_is_empty(const list_t *list)
51 {
52 assert(list != NULL);
53 return (list->length == 0);
54 }
55
list_contains(const list_t * list,const void * data)56 bool list_contains(const list_t *list, const void *data)
57 {
58 assert(list != NULL);
59 assert(data != NULL);
60
61 for (const list_node_t *node = list_begin(list); node != list_end(list); node = list_next(node)) {
62 if (list_node(node) == data) {
63 return true;
64 }
65 }
66
67 return false;
68 }
69
list_get_node(const list_t * list,const void * data)70 list_node_t *list_get_node(const list_t *list, const void *data)
71 {
72 assert(list != NULL);
73 assert(data != NULL);
74 list_node_t *p_node_ret = NULL;
75 for (list_node_t *node = list_begin(list); node != list_end(list); node = list_next(node)) {
76 if (list_node(node) == data) {
77 p_node_ret = node;
78 break;
79 }
80 }
81
82 return p_node_ret;
83 }
84
list_length(const list_t * list)85 size_t list_length(const list_t *list)
86 {
87 assert(list != NULL);
88 return list->length;
89 }
90
list_front(const list_t * list)91 void *list_front(const list_t *list)
92 {
93 assert(list != NULL);
94 assert(!list_is_empty(list));
95
96 return list->head->data;
97 }
98
list_back(const list_t * list)99 void *list_back(const list_t *list) {
100 assert(list != NULL);
101 assert(!list_is_empty(list));
102
103 return list->tail->data;
104 }
105
list_back_node(const list_t * list)106 list_node_t *list_back_node(const list_t *list) {
107 assert(list != NULL);
108 assert(!list_is_empty(list));
109
110 return list->tail;
111 }
112
list_insert_after(list_t * list,list_node_t * prev_node,void * data)113 bool list_insert_after(list_t *list, list_node_t *prev_node, void *data) {
114 assert(list != NULL);
115 assert(prev_node != NULL);
116 assert(data != NULL);
117 list_node_t *node = (list_node_t *)osi_calloc(sizeof(list_node_t));
118 if (!node) {
119 OSI_TRACE_ERROR("%s osi_calloc failed.\n", __FUNCTION__ );
120 return false;
121 }
122 node->next = prev_node->next;
123 node->data = data;
124 prev_node->next = node;
125 if (list->tail == prev_node) {
126 list->tail = node;
127 }
128 ++list->length;
129 return true;
130 }
131
list_prepend(list_t * list,void * data)132 bool list_prepend(list_t *list, void *data)
133 {
134 assert(list != NULL);
135 assert(data != NULL);
136 list_node_t *node = (list_node_t *)osi_calloc(sizeof(list_node_t));
137 if (!node) {
138 OSI_TRACE_ERROR("%s osi_calloc failed.\n", __FUNCTION__ );
139 return false;
140 }
141 node->next = list->head;
142 node->data = data;
143 list->head = node;
144 if (list->tail == NULL) {
145 list->tail = list->head;
146 }
147 ++list->length;
148 return true;
149 }
150
list_append(list_t * list,void * data)151 bool list_append(list_t *list, void *data)
152 {
153 assert(list != NULL);
154 assert(data != NULL);
155 list_node_t *node = (list_node_t *)osi_calloc(sizeof(list_node_t));
156 if (!node) {
157 OSI_TRACE_ERROR("%s osi_calloc failed.\n", __FUNCTION__ );
158 return false;
159 }
160 node->next = NULL;
161 node->data = data;
162 if (list->tail == NULL) {
163 list->head = node;
164 list->tail = node;
165 } else {
166 list->tail->next = node;
167 list->tail = node;
168 }
169 ++list->length;
170 return true;
171 }
172
list_remove(list_t * list,void * data)173 bool list_remove(list_t *list, void *data)
174 {
175 assert(list != NULL);
176 assert(data != NULL);
177
178 if (list_is_empty(list)) {
179 return false;
180 }
181
182 if (list->head->data == data) {
183 list_node_t *next = list_free_node(list, list->head);
184 if (list->tail == list->head) {
185 list->tail = next;
186 }
187 list->head = next;
188 return true;
189 }
190
191 for (list_node_t *prev = list->head, *node = list->head->next; node; prev = node, node = node->next)
192 if (node->data == data) {
193 prev->next = list_free_node(list, node);
194 if (list->tail == node) {
195 list->tail = prev;
196 }
197 return true;
198 }
199
200 return false;
201 }
202
list_delete(list_t * list,void * data)203 bool list_delete(list_t *list, void *data)
204 {
205 assert(list != NULL);
206 assert(data != NULL);
207
208 if (list_is_empty(list)) {
209 return false;
210 }
211
212 if (list->head->data == data) {
213 list_node_t *next = list_delete_node(list, list->head);
214 if (list->tail == list->head) {
215 list->tail = next;
216 }
217 list->head = next;
218 return true;
219 }
220
221 for (list_node_t *prev = list->head, *node = list->head->next; node; prev = node, node = node->next)
222 if (node->data == data) {
223 prev->next = list_delete_node(list, node);
224 if (list->tail == node) {
225 list->tail = prev;
226 }
227 return true;
228 }
229
230 return false;
231 }
232
list_clear(list_t * list)233 void list_clear(list_t *list)
234 {
235 assert(list != NULL);
236 for (list_node_t *node = list->head; node; ) {
237 node = list_free_node(list, node);
238 }
239 list->head = NULL;
240 list->tail = NULL;
241 list->length = 0;
242 }
243
list_foreach(const list_t * list,list_iter_cb callback,void * context)244 list_node_t *list_foreach(const list_t *list, list_iter_cb callback, void *context)
245 {
246 assert(list != NULL);
247 assert(callback != NULL);
248
249 for (list_node_t *node = list->head; node; ) {
250 list_node_t *next = node->next;
251 if (!callback(node->data, context)) {
252 return node;
253 }
254 node = next;
255 }
256 return NULL;
257 }
258
list_begin(const list_t * list)259 list_node_t *list_begin(const list_t *list)
260 {
261 assert(list != NULL);
262 return list->head;
263 }
264
list_end(UNUSED_ATTR const list_t * list)265 list_node_t *list_end(UNUSED_ATTR const list_t *list)
266 {
267 assert(list != NULL);
268 return NULL;
269 }
270
list_next(const list_node_t * node)271 list_node_t *list_next(const list_node_t *node)
272 {
273 assert(node != NULL);
274 return node->next;
275 }
276
list_node(const list_node_t * node)277 void *list_node(const list_node_t *node)
278 {
279 assert(node != NULL);
280 return node->data;
281 }
282
list_free_node(list_t * list,list_node_t * node)283 list_node_t *list_free_node(list_t *list, list_node_t *node)
284 {
285 assert(list != NULL);
286 assert(node != NULL);
287
288 list_node_t *next = node->next;
289
290 if (list->free_cb) {
291 list->free_cb(node->data);
292 }
293 osi_free(node);
294 --list->length;
295
296 return next;
297 }
298
299 // remove the element from list but do not free the node data
list_delete_node(list_t * list,list_node_t * node)300 list_node_t *list_delete_node(list_t *list, list_node_t *node)
301 {
302 assert(list != NULL);
303 assert(node != NULL);
304
305 list_node_t *next = node->next;
306
307 osi_free(node);
308 --list->length;
309
310 return next;
311 }
312