1 #include "osi/include/list.h"
2
3 #include <bluetooth/log.h>
4
5 #include "osi/include/allocator.h"
6
7 using namespace bluetooth;
8
9 struct list_node_t {
10 struct list_node_t* next;
11 void* data;
12 };
13
14 typedef struct list_t {
15 list_node_t* head;
16 list_node_t* tail;
17 size_t length;
18 list_free_cb free_cb;
19 const allocator_t* allocator;
20 } list_t;
21
22 static list_node_t* list_free_node_(list_t* list, list_node_t* node);
23
24 // Hidden constructor, only to be used by the hash map for the allocation
25 // tracker.
26 // 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)27 list_t* list_new_internal(list_free_cb callback,
28 const allocator_t* zeroed_allocator) {
29 list_t* list = (list_t*)zeroed_allocator->alloc(sizeof(list_t));
30 if (!list) return NULL;
31
32 list->free_cb = callback;
33 list->allocator = zeroed_allocator;
34 return list;
35 }
36
list_new(list_free_cb callback)37 list_t* list_new(list_free_cb callback) {
38 return list_new_internal(callback, &allocator_calloc);
39 }
40
list_free(list_t * list)41 void list_free(list_t* list) {
42 if (!list) return;
43
44 list_clear(list);
45 list->allocator->free(list);
46 }
47
list_is_empty(const list_t * list)48 bool list_is_empty(const list_t* list) {
49 log::assert_that(list != NULL, "assert failed: list != NULL");
50 return (list->length == 0);
51 }
52
list_contains(const list_t * list,const void * data)53 bool list_contains(const list_t* list, const void* data) {
54 log::assert_that(list != NULL, "assert failed: list != NULL");
55 log::assert_that(data != NULL, "assert failed: data != NULL");
56
57 for (const list_node_t* node = list_begin(list); node != list_end(list);
58 node = list_next(node)) {
59 if (list_node(node) == data) return true;
60 }
61
62 return false;
63 }
64
list_length(const list_t * list)65 size_t list_length(const list_t* list) {
66 log::assert_that(list != NULL, "assert failed: list != NULL");
67 return list->length;
68 }
69
list_front(const list_t * list)70 void* list_front(const list_t* list) {
71 log::assert_that(list != NULL, "assert failed: list != NULL");
72 log::assert_that(!list_is_empty(list), "assert failed: !list_is_empty(list)");
73
74 return list->head->data;
75 }
76
list_back(const list_t * list)77 void* list_back(const list_t* list) {
78 log::assert_that(list != NULL, "assert failed: list != NULL");
79 log::assert_that(!list_is_empty(list), "assert failed: !list_is_empty(list)");
80
81 return list->tail->data;
82 }
83
list_back_node(const list_t * list)84 list_node_t* list_back_node(const list_t* list) {
85 log::assert_that(list != NULL, "assert failed: list != NULL");
86 log::assert_that(!list_is_empty(list), "assert failed: !list_is_empty(list)");
87
88 return list->tail;
89 }
90
list_insert_after(list_t * list,list_node_t * prev_node,void * data)91 bool list_insert_after(list_t* list, list_node_t* prev_node, void* data) {
92 log::assert_that(list != NULL, "assert failed: list != NULL");
93 log::assert_that(prev_node != NULL, "assert failed: prev_node != NULL");
94 log::assert_that(data != NULL, "assert failed: data != NULL");
95
96 list_node_t* node = (list_node_t*)list->allocator->alloc(sizeof(list_node_t));
97 if (!node) return false;
98
99 node->next = prev_node->next;
100 node->data = data;
101 prev_node->next = node;
102 if (list->tail == prev_node) list->tail = node;
103 ++list->length;
104 return true;
105 }
106
list_prepend(list_t * list,void * data)107 bool list_prepend(list_t* list, void* data) {
108 log::assert_that(list != NULL, "assert failed: list != NULL");
109 log::assert_that(data != NULL, "assert failed: data != NULL");
110
111 list_node_t* node = (list_node_t*)list->allocator->alloc(sizeof(list_node_t));
112 if (!node) return false;
113 node->next = list->head;
114 node->data = data;
115 list->head = node;
116 if (list->tail == NULL) list->tail = list->head;
117 ++list->length;
118 return true;
119 }
120
list_append(list_t * list,void * data)121 bool list_append(list_t* list, void* data) {
122 log::assert_that(list != NULL, "assert failed: list != NULL");
123 log::assert_that(data != NULL, "assert failed: data != NULL");
124
125 list_node_t* node = (list_node_t*)list->allocator->alloc(sizeof(list_node_t));
126 if (!node) return false;
127 node->next = NULL;
128 node->data = data;
129 if (list->tail == NULL) {
130 list->head = node;
131 list->tail = node;
132 } else {
133 list->tail->next = node;
134 list->tail = node;
135 }
136 ++list->length;
137 return true;
138 }
139
list_remove(list_t * list,void * data)140 bool list_remove(list_t* list, void* data) {
141 log::assert_that(list != NULL, "assert failed: list != NULL");
142 log::assert_that(data != NULL, "assert failed: data != NULL");
143
144 if (list_is_empty(list)) return false;
145
146 if (list->head->data == data) {
147 list_node_t* next = list_free_node_(list, list->head);
148 if (list->tail == list->head) list->tail = next;
149 list->head = next;
150 return true;
151 }
152
153 for (list_node_t *prev = list->head, *node = list->head->next; node;
154 prev = node, node = node->next)
155 if (node->data == data) {
156 prev->next = list_free_node_(list, node);
157 if (list->tail == node) list->tail = prev;
158 return true;
159 }
160
161 return false;
162 }
163
list_clear(list_t * list)164 void list_clear(list_t* list) {
165 log::assert_that(list != NULL, "assert failed: list != NULL");
166 for (list_node_t* node = list->head; node;)
167 node = list_free_node_(list, node);
168 list->head = NULL;
169 list->tail = NULL;
170 list->length = 0;
171 }
172
list_foreach(const list_t * list,list_iter_cb callback,void * context)173 list_node_t* list_foreach(const list_t* list, list_iter_cb callback,
174 void* context) {
175 log::assert_that(list != NULL, "assert failed: list != NULL");
176 log::assert_that(callback != NULL, "assert failed: callback != NULL");
177
178 for (list_node_t* node = list->head; node;) {
179 list_node_t* next = node->next;
180 if (!callback(node->data, context)) return node;
181 node = next;
182 }
183 return NULL;
184 }
185
list_begin(const list_t * list)186 list_node_t* list_begin(const list_t* list) {
187 log::assert_that(list != NULL, "assert failed: list != NULL");
188 return list->head;
189 }
190
list_end(const list_t * list)191 list_node_t* list_end(const list_t* list) {
192 log::assert_that(list != NULL, "assert failed: list != NULL");
193 return NULL;
194 }
195
list_next(const list_node_t * node)196 list_node_t* list_next(const list_node_t* node) {
197 log::assert_that(node != NULL, "assert failed: node != NULL");
198 return node->next;
199 }
200
list_node(const list_node_t * node)201 void* list_node(const list_node_t* node) {
202 log::assert_that(node != NULL, "assert failed: node != NULL");
203 return node->data;
204 }
205
list_free_node_(list_t * list,list_node_t * node)206 static list_node_t* list_free_node_(list_t* list, list_node_t* node) {
207 log::assert_that(list != NULL, "assert failed: list != NULL");
208 log::assert_that(node != NULL, "assert failed: node != NULL");
209
210 list_node_t* next = node->next;
211
212 if (list->free_cb) list->free_cb(node->data);
213 list->allocator->free(node);
214 --list->length;
215
216 return next;
217 }
218