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