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