initial commit
[cgds.git] / src / List.h
CommitLineData
a7868768
BA
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 */
20typedef 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 */
29typedef struct List {
30 UInt size; ///< Count elements in the list.
31 size_t dataSize; ///< Size of a list cell elements 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 */
39void _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 */
48List* _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 (works well if items do not have allocated sub-pointers).
63 */
64List* list_copy(
65 List* list ///< "this" pointer.
66);
67
68/**
69 * @brief Check if the list is empty.
70 */
71Bool list_empty(
72 List* list ///< "this" pointer.
73);
74
75/**
76 * @brief return the size of current list.
77 */
78UInt list_size(
79 List* list ///< "this" pointer.
80);
81
82/**
83 * @brief Get data at the given list cell argument.
84 */
85void* _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 */
105void _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 */
128void _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 */
136void _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 */
159void _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 */
182void _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 */
203void _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 */
224void 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 */
232void list_remove_front(
233 List* list ///< "this" pointer.
234);
235
236/**
237 * @brief Remove data at the end of the list.
238 */
239void list_remove_back(
240 List* list ///< "this" pointer.
241);
242
243/**
244 * @brief Clear the entire list.
245 */
246void list_clear(
247 List* list ///< "this" pointer.
248);
249
250/**
251 * @brief Destroy the list: clear it, and free 'list' pointer.
252 */
253void 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 */
264typedef 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 */
272ListIterator* 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 */
279void listI_reset_head(
280 ListIterator* listI ///< "this" pointer.
281);
282
283/**
284 * @brief (Re)set current position inside list to tail.
285 */
286void listI_reset_tail(
287 ListIterator* listI ///< "this" pointer.
288);
289
290/**
291 * @brief Tell if there is some data at the current index.
292 */
293Bool 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 */
340typedef 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 */
348void 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 */
356void listI_move_next(
357 ListIterator* listI ///< "this" pointer.
358);
359
360/**
361 * @brief Move current iterator position backward (toward head).
362 */
363void listI_move_prev(
364 ListIterator* listI ///< "this" pointer.
365);
366
367/**
368 * @brief Free memory allocated for the iterator.
369 */
370void listI_destroy(
371 ListIterator* listI ///< "this" pointer.
372);
373
374#endif