a6e9822412bc7d9f9aa751d15033e57015bc1045
[cgds.git] / src / List.h
1 /**
2 * @file List.h
3 */
4
5 #ifndef CGDS_LIST_H
6 #define CGDS_LIST_H
7
8 #include <stdlib.h>
9 #include <string.h>
10 #include "cgds/safe_alloc.h"
11 #include "cgds/types.h"
12
13 ////////////////
14 // List logic //
15 ////////////////
16
17 /**
18 * @brief Cell of a double-linked list.
19 */
20 typedef struct ListCell {
21 void* data; ///< Generic data contained in this cell.
22 struct ListCell* prev; ///< Pointer to previous cell in the list.
23 struct ListCell* next; ///< Pointer to next cell in the list.
24 } ListCell;
25
26 /**
27 * @brief Double-linked list data structure.
28 */
29 typedef struct List {
30 UInt size; ///< Count elements in the list.
31 size_t dataSize; ///< Size of a list cell element in bytes.
32 ListCell* head; ///< Pointer to the first cell in the list.
33 ListCell* tail; ///< Pointer to the last cell in the list.
34 } List;
35
36 /**
37 * @brief Initialize an empty list.
38 */
39 void _list_init(
40 List* list, ///< "this" pointer.
41 size_t dataSize ///< Size of a list cell elements in bytes.
42 );
43
44 /**
45 * @brief Return an allocated and initialized list.
46 * @param dataSize Size in bytes of a list element.
47 */
48 List* _list_new(
49 size_t dataSize ///< Size of a list cell elements in bytes.
50 );
51
52 /**
53 * @brief Return an allocated and initialized list.
54 * @param type Type of a list element (int, char*, ...).
55 *
56 * Usage: List* list_new(<Type> type)
57 */
58 #define list_new(type) \
59 _list_new(sizeof(type))
60
61 /**
62 * @brief Copy constructor (shallow copy, ok for basic types).
63 */
64 List* list_copy(
65 List* list ///< "this" pointer.
66 );
67
68 /**
69 * @brief Check if the list is empty.
70 */
71 bool list_empty(
72 List* list ///< "this" pointer.
73 );
74
75 /**
76 * @brief return the size of current list.
77 */
78 UInt list_size(
79 List* list ///< "this" pointer.
80 );
81
82 /**
83 * @brief Get data at the given list cell argument.
84 */
85 void* _list_get(
86 ListCell* listCell ///< Pointer to a cell inside "this" list.
87 );
88
89 /**
90 * @brief Get data at the given list cell argument.
91 * @param listCell Pointer to a cell inside "this" list.
92 * @param data Data to be assigned.
93 *
94 * Usage: void list_get(ListCell* listCell, void data)
95 */
96 #define list_get(listCell, data) \
97 { \
98 void* pData = _list_get(listCell); \
99 data = *((typeof(&data))pData); \
100 }
101
102 /**
103 * @brief Set data at the given list cell argument.
104 */
105 void _list_set(
106 List* list, ///< "this" pointer.
107 ListCell* listCell, ///< Pointer to a cell inside "this" list.
108 void* data ///< Pointer to data to be set.
109 );
110
111 /**
112 * @brief Set data at the given list cell argument.
113 * @param list "this" pointer.
114 * @param listCell Pointer to a cell inside "this" list.
115 * @param data Data to be set.
116 *
117 * Usage: void list_set(List* list, ListCell* listCell, void data);
118 */
119 #define list_set(list, listCell, data) \
120 { \
121 typeof(data) tmp = data; \
122 _list_set(list, listCell, &tmp); \
123 }
124
125 /**
126 * @brief Add data to the list when list is empty.
127 */
128 void _list_insert_first_element(
129 List* list, ///< "this" pointer.
130 void* data ///< Pointer to data to be added
131 );
132
133 /**
134 * @brief Add data before list cell argument.
135 */
136 void _list_insert_before(
137 List* list, ///< "this" pointer.
138 ListCell* listCell, ///< Pointer to a cell inside "this" list.
139 void* data ///< Pointer to data to be added.
140 );
141
142 /**
143 * @brief Add data before list cell argument.
144 * @param list "this" pointer.
145 * @param listCell Pointer to a cell inside "this" list.
146 * @param data Data to be inserted.
147 *
148 * Usage: void list_insert_before(List* list, ListCell* listCell, void data)
149 */
150 #define list_insert_before(list, listCell, data) \
151 { \
152 typeof(data) tmp = data; \
153 _list_insert_before(list, listCell, &tmp); \
154 }
155
156 /**
157 * @brief Add data after list cell argument.
158 */
159 void _list_insert_after(
160 List* list, ///< "this" pointer.
161 ListCell* listCell, ///< Pointer to a cell inside "this" list.
162 void* data ///< Pointer to data to be inserted.
163 );
164
165 /**
166 * @brief Add data after list cell argument.
167 * @param list "this" pointer.
168 * @param listCell Pointer to a cell inside "this" list.
169 * @param data Data to be inserted.
170 *
171 * Usage: void list_insert_after(List* list, ListCell* listCell, void data)
172 */
173 #define list_insert_after(list, listCell, data) \
174 { \
175 typeof(data) tmp = data; \
176 _list_insert_after(list, listCell, &tmp); \
177 }
178
179 /**
180 * @brief Add data at the beginning of the list.
181 */
182 void _list_insert_front(
183 List* list, ///< "this" pointer.
184 void* data ///< Pointer to data to be inserted.
185 );
186
187 /**
188 * @brief Add data at the beginning of the list.
189 * @param list "this" pointer.
190 * @param data Data to be inserted.
191 *
192 * Usage: void list_insert_front(List* list, void data)
193 */
194 #define list_insert_front(list, data) \
195 { \
196 typeof(data) tmp = data; \
197 _list_insert_front(list, &tmp); \
198 }
199
200 /**
201 * @brief Add data at the end of the list.
202 */
203 void _list_insert_back(
204 List* list, ///< "this" pointer.
205 void* data ///< Pointer to data to be inserted.
206 );
207
208 /**
209 * @brief Add data at the end of the list.
210 * @param list "this" pointer.
211 * @param data Data to be inserted.
212 *
213 * Usage: void list_insert_back(List* list, void data)
214 */
215 #define list_insert_back(list, data) \
216 { \
217 typeof(data) tmp = data; \
218 _list_insert_back(list, &tmp); \
219 }
220
221 /**
222 * @brief Remove data at position given by 'listCell'.
223 */
224 void list_remove(
225 List* list, ///< "this" pointer.
226 ListCell* listCell ///< Pointer to a cell inside "this" list.
227 );
228
229 /**
230 * @brief Remove data at the beginning of the list.
231 */
232 void list_remove_front(
233 List* list ///< "this" pointer.
234 );
235
236 /**
237 * @brief Remove data at the end of the list.
238 */
239 void list_remove_back(
240 List* list ///< "this" pointer.
241 );
242
243 /**
244 * @brief Clear the entire list.
245 */
246 void list_clear(
247 List* list ///< "this" pointer.
248 );
249
250 /**
251 * @brief Destroy the list: clear it, and free 'list' pointer.
252 */
253 void list_destroy(
254 List* list ///< "this" pointer.
255 );
256
257 ////////////////////
258 // Iterator logic //
259 ////////////////////
260
261 /**
262 * @brief Iterator on a double-linked list.
263 */
264 typedef struct ListIterator {
265 List* list; ///< The list to be iterate.
266 ListCell* current; ///< The current iterated list cell.
267 } ListIterator;
268
269 /**
270 * @brief Obtain an iterator object, starting at list beginning.
271 */
272 ListIterator* list_get_iterator(
273 List* list ///< Pointer to the list to be iterated over.
274 );
275
276 /**
277 * @brief (Re)set current position inside list to head.
278 */
279 void listI_reset_head(
280 ListIterator* listI ///< "this" pointer.
281 );
282
283 /**
284 * @brief (Re)set current position inside list to tail.
285 */
286 void listI_reset_tail(
287 ListIterator* listI ///< "this" pointer.
288 );
289
290 /**
291 * @brief Tell if there is some data at the current index.
292 */
293 bool listI_has_data(
294 ListIterator* listI ///< "this" pointer.
295 );
296
297 /**
298 * @brief Return data contained in the current list cell.
299 * @param listI "this" pointer.
300 * @param data Data to be assigned.
301 *
302 * Usage: void listI_get(ListIterator* listI, void data)
303 */
304 #define listI_get(listI, data) \
305 list_get(listI->current, data)
306
307 /**
308 * @brief Set data at the current iterator position.
309 * @param listI "this" pointer
310 * @param data Data to assign.
311 *
312 * Usage: void listI_set(ListIterator* listI, void data);
313 */
314 #define listI_set(listI, data) \
315 list_set(listI->list, listI->current, data)
316
317 /**
318 * @brief Add data before current list cell.
319 * @param listI "this" pointer
320 * @param data Data to be inserted.
321 *
322 * Usage: void listI_insert_before(ListIteratorI* listI, void data)
323 */
324 #define listI_insert_before(listI, data) \
325 list_insert_before(listI->list, listI->current, data)
326
327 /**
328 * @brief Add data after current list cell.
329 * @param listI "this" pointer
330 * @param data Data to be inserted.
331 *
332 * Usage: void listI_insert_after(ListIteratorI* listI, void data)
333 */
334 #define listI_insert_after(listI, data) \
335 list_insert_after(listI->list, listI->current, data)
336
337 /**
338 * @brief Type to encode a direction (forward / backward).
339 */
340 typedef enum {
341 BACKWARD = -1, ///< Move toward head.
342 FORWARD = 1 ///< Move toward tail.
343 } Direction;
344
345 /**
346 * @brief Remove data at the current iterator position.
347 */
348 void listI_remove(
349 ListIterator* listI, ///< "this" pointer.
350 Direction direction ///< Indicate the position of iterator after removal.
351 );
352
353 /**
354 * @brief Move current iterator position forward (toward tail).
355 */
356 void listI_move_next(
357 ListIterator* listI ///< "this" pointer.
358 );
359
360 /**
361 * @brief Move current iterator position backward (toward head).
362 */
363 void listI_move_prev(
364 ListIterator* listI ///< "this" pointer.
365 );
366
367 /**
368 * @brief Free memory allocated for the iterator.
369 */
370 void listI_destroy(
371 ListIterator* listI ///< "this" pointer.
372 );
373
374 #endif