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
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
23// tracker.
24// Behaves the same as |list_new|, except you get to specify the allocator.
25list_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
35list_t* list_new(list_free_cb callback) {
36  return list_new_internal(callback, &allocator_calloc);
37}
38
39void list_free(list_t* list) {
40  if (!list) return;
41
42  list_clear(list);
43  list->allocator->free(list);
44}
45
46bool list_is_empty(const list_t* list) {
47  CHECK(list != NULL);
48  return (list->length == 0);
49}
50
51bool 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
63size_t list_length(const list_t* list) {
64  CHECK(list != NULL);
65  return list->length;
66}
67
68void* list_front(const list_t* list) {
69  CHECK(list != NULL);
70  CHECK(!list_is_empty(list));
71
72  return list->head->data;
73}
74
75void* list_back(const list_t* list) {
76  CHECK(list != NULL);
77  CHECK(!list_is_empty(list));
78
79  return list->tail->data;
80}
81
82list_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
89bool 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
105bool 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
119bool 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
138bool 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
162void 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
171list_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
184list_node_t* list_begin(const list_t* list) {
185  CHECK(list != NULL);
186  return list->head;
187}
188
189list_node_t* list_end(UNUSED_ATTR const list_t* list) {
190  CHECK(list != NULL);
191  return NULL;
192}
193
194list_node_t* list_next(const list_node_t* node) {
195  CHECK(node != NULL);
196  return node->next;
197}
198
199void* list_node(const list_node_t* node) {
200  CHECK(node != NULL);
201  return node->data;
202}
203
204static 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