linkedList.h (11521B)
1
2 /**
3 * \file
4 *
5 * double linked list: llist
6 *
7 * The nodes in llist are linked with pointers and dynamically allocated in segments
8 *
9 * The element type handled by the list is defined with llistT
10 *
11 *
12 * Example:
13 *
14 * // define list:
15 * llistT(llt, u32);
16 *
17 * // declare list:
18 * llt ll;
19 *
20 * // initialize:
21 * llistInit(&ll);
22 *
23 * // push element:
24 * llistPush(&ll);
25 * llistLast(&ll) = 1;
26 *
27 * // Pop/dellast element:
28 * llistPop(&ll);
29 *
30 * // Free
31 * llistFree(&ll);
32 *
33 * TODO create linkedList without head and last
34 */
35
36 #include "libsheepyObject.h"
37
38 /**
39 * list and node definition
40 */
41 #define llistT(typeName, elementType)\
42 typ struct UNIQVAR(nodet) UNIQVAR(nodet);\
43 struct UNIQVAR(nodet) {\
44 elementType elem;\
45 UNIQVAR(nodet) *prev;\
46 UNIQVAR(nodet) *next;\
47 };\
48 dArrayT(UNIQVAR(aNodet), UNIQVAR(nodet));\
49 dArrayT(UNIQVAR(freeaNodet), UNIQVAR(nodet)*);\
50 typ struct {\
51 UNIQVAR(nodet) *head;\
52 UNIQVAR(nodet) *last;\
53 UNIQVAR(aNodet) list;\
54 UNIQVAR(freeaNodet) freeList;\
55 } typeName
56
57 /**
58 * initialize list
59 */
60 #define llistInit(name) do{\
61 (name)->head = (name)->last = NULL;\
62 dArrayInit(&(name)->list);\
63 dArrayInit(&(name)->freeList);\
64 } while(0)
65
66 /**
67 * free list
68 */
69 #define llistFree(name) do{\
70 dArrayFree(&(name)->list);\
71 dArrayFree(&(name)->freeList);\
72 (name)->head = (name)->last = NULL;\
73 } while(0)
74
75 /**
76 * node type for declaring pointers to nodes
77 *
78 * Example:
79 * llistNodeType(name) node;
80 * llistUnlink(name, node);
81 * */
82 #define llistNodeType(name) typeof((name)->head)
83
84 /**
85 * element count in list
86 */
87 #define llistCount(name) (dArrayCount(&(name)->list) - dArrayCount(&(name)->freeList))
88
89
90 /**
91 * is list empty
92 */
93 #define llistIsEmpty(name) ((name)->head == NULL)
94
95 /**
96 * push element to list (only allocates node)
97 * use llistLast to access the element
98 */
99 #define llistPush(name) do{\
100 if (dArrayIsEmpty(&(name)->freeList)) {\
101 dArrayPush(&(name)->list);\
102 if (!(name)->last) {\
103 /* first node */\
104 dArrayLast(&(name)->list).prev = NULL;\
105 dArrayLast(&(name)->list).next = NULL;\
106 (name)->head = &dArrayLast(&(name)->list);\
107 (name)->last = &dArrayLast(&(name)->list);\
108 }\
109 else {\
110 /* link to previous node */\
111 dArrayLast(&(name)->list).prev = (name)->last;\
112 (name)->last->next = &dArrayLast(&(name)->list);\
113 dArrayLast(&(name)->list).next = NULL;\
114 (name)->last = &dArrayLast(&(name)->list);\
115 }\
116 }\
117 else {\
118 /* reuse a free node */\
119 if (!(name)->last) {\
120 dArrayLast(&(name)->freeList)->prev = NULL;\
121 dArrayLast(&(name)->freeList)->next = NULL;\
122 (name)->head = dArrayLast(&(name)->freeList);\
123 (name)->last = dArrayLast(&(name)->freeList);\
124 }\
125 else {\
126 dArrayLast(&(name)->freeList)->prev = (name)->last;\
127 (name)->last->next = dArrayLast(&(name)->freeList);\
128 dArrayLast(&(name)->freeList)->next = NULL;\
129 (name)->last = dArrayLast(&(name)->freeList);\
130 }\
131 dArrayDelLast(&(name)->freeList);\
132 }\
133 } while(0)
134
135 /**
136 * pop element from list (only free node)
137 *
138 * \return
139 * true success, false failed: the list is empty
140 */
141 #define llistPop(name) ({\
142 bool UNIQVAR(r) = true;\
143 if (!(name)->last) {\
144 /* the list is empty */\
145 UNIQVAR(r) = false;\
146 goto UNIQVAR(end);\
147 }\
148 dArrayPush(&(name)->freeList);\
149 dArrayLast(&(name)->freeList) = (name)->last;\
150 (name)->last = (name)->last->prev;\
151 if ((name)->last) (name)->last->next = NULL;\
152 if (!(name)->last) /* the list is empty */ (name)->head = NULL;\
153 UNIQVAR(end):\
154 UNIQVAR(r);\
155 })
156
157 #define llistDelLast llistPop
158
159 /**
160 * unlink node
161 *
162 * node must be of type llistNodeType(name)
163 *
164 * the node can be freed with llistFreeUnlinked or
165 * inserted in the list with llistInsertAfter or llistInsertBefore
166 */
167 #define llistUnlink(name, node) do{\
168 if (!(node)->prev) {\
169 /* node is head */\
170 (name)->head = (node)->next;\
171 }\
172 else {\
173 (node)->prev->next = (node)->next;\
174 }\
175 if (!(node)->next) {\
176 /* node is last */\
177 (name)->last = (node)->prev;\
178 }\
179 else {\
180 (node)->next->prev = (node)->prev;\
181 }\
182 } while(0)
183
184 /**
185 * free unlinked node
186 *
187 * node must be of type llistNodeType(name)
188 */
189 #define llistFreeUnlinked(name, node) do{\
190 dArrayPush(&(name)->freeList);\
191 dArrayLast(&(name)->freeList) = node;\
192 } while(0)
193
194 /**
195 * delete node
196 *
197 * node must be of type llistNodeType(name)
198 *
199 * unlink and free node
200 */
201 #define llistDelNode(name, node) do{\
202 llistUnlink(name, node);\
203 llistFreeUnlinked(name, node);\
204 } while(0)
205
206 /** first element */
207 #define llistFirst(name) (name)->head->elem
208
209 /** first node pointer */
210 #define llistFirstNode(name) (name)->head
211 #define llistHeadNode llistFirstNode
212
213 /** last element */
214 #define llistLast(name) (name)->last->elem
215
216 /** last node pointer */
217 #define llistLastNode(name) (name)->last
218
219 /** previous node */
220 #define llistPrev(node) (node)->prev
221
222 /** next node */
223 #define llistNext(node) (node)->next
224
225 /** node element (or use node->elem) */
226 #define llistGetElem(node) (node)->elem
227
228 /**
229 * swap node1 with node2
230 */
231 #define llistSwap(name, node1, node2) do{\
232 /* disable sanity checks to keep it simple - if (!node1 or !node2) {*/\
233 /* return value instead --- (name)->res = false;*/\
234 /* break;*/\
235 /*}*/\
236 if (node1 == node2) /* node1 and node2 are the same node, nothing to do */ break;\
237 var UNIQVAR(tmp) = (node1)->next;\
238 (node1)->next = (node2)->next;\
239 (node2)->next = UNIQVAR(tmp);\
240 if (!(node1)->next) (name)->last = node1;\
241 else (node1)->next->prev = node1;\
242 if (!(node2)->next) (name)->last = node2;\
243 else (node2)->next->prev = node2;\
244 UNIQVAR(tmp) = (node1)->prev;\
245 (node1)->prev = (node2)->prev;\
246 (node2)->prev = UNIQVAR(tmp);\
247 if (!(node1)->prev) (name)->head = node1;\
248 else (node1)->prev->next = node1;\
249 if (!(node2)->prev) (name)->head = node2;\
250 else (node2)->prev->next = node2;\
251 } while(0)
252
253 /** loop from head to last */
254 #define llistForEach(name, node)\
255 for(var node = (name)->head; node ; node = llistNext(node))
256
257 /** loop from last to head */
258 #define llistForEachDown(name, node)\
259 for(var node = (name)->last; node ; node = llistPrev(node))
260
261 /** loop from startNode to last */
262 #define llistForEachFrom(node, startNode)\
263 for(var node = startNode; node ; node = (node)->next)
264
265 /** loop from startNode to head */
266 #define llistForEachFromDown(node, startNode)\
267 for(var node = startNode; node ; node = (node)->prev)
268
269 /**
270 * insert nodeToInsert after referenceNode
271 *
272 * nodeToInsert and referenceNode must be of type llistNodeType(name)
273 */
274 #define llistInsertAfter(name, referenceNode, nodeToInsert) do{\
275 (nodeToInsert)->next = referenceNode->next;\
276 referenceNode->next = nodeToInsert;\
277 (nodeToInsert)->prev = referenceNode;\
278 if ((nodeToInsert)->next) {\
279 (nodeToInsert)->next->prev = nodeToInsert;\
280 }\
281 else {\
282 /* referenceNode was last node */\
283 (name)->last = nodeToInsert;\
284 }\
285 } while(0)
286
287 /**
288 * insert nodeToInsert before referenceNode
289 *
290 * nodeToInsert and referenceNode must be of type llistNodeType(name)
291 */
292 #define llistInsertBefore(name, referenceNode, nodeToInsert) do{\
293 (nodeToInsert)->prev = referenceNode->prev;\
294 referenceNode->prev = nodeToInsert;\
295 (nodeToInsert)->next = referenceNode;\
296 if ((nodeToInsert)->prev) {\
297 (nodeToInsert)->prev->next = nodeToInsert;\
298 }\
299 else {\
300 /* referenceNode was head node */\
301 (name)->head = nodeToInsert;\
302 }\
303 } while(0)
304
305
306 // Internal
307 // allocate a node
308 #define llistAddNode(name, resultNode) do{\
309 if (dArrayIsEmpty(&(name)->freeList)) {\
310 dArrayPush(&(name)->list);\
311 resultNode = &dArrayLast(&(name)->list);\
312 }\
313 else {\
314 /* reuse a free node */\
315 resultNode = dArrayLast(&(name)->freeList);\
316 dArrayPop(&(name)->freeList);\
317 }\
318 } while(0)
319
320 /**
321 * add new node after referenceNode
322 *
323 * resultNode and referenceNode must be of type llistNodeType(name)
324 *
325 * \return
326 * resultNode access element in node with resultNode->elem or llistGetElem(resultNode)
327 */
328 #define llistAddAfter(name, referenceNode, resultNode) do{\
329 llistAddNode(name, resultNode);\
330 (resultNode)->next = referenceNode->next;\
331 referenceNode->next = resultNode;\
332 (resultNode)->prev = referenceNode;\
333 if ((resultNode)->next) {\
334 (resultNode)->next->prev = resultNode;\
335 }\
336 else {\
337 /* referenceNode was last node */\
338 (name)->last = resultNode;\
339 }\
340 } while(0)
341
342 /**
343 * add new node before referenceNode
344 *
345 * resultNode and referenceNode must be of type llistNodeType(name)
346 *
347 * \return
348 * resultNode access element in node with resultNode->elem or llistGetElem(resultNode)
349 */
350 #define llistAddBefore(name, referenceNode, resultNode) do{\
351 llistAddNode(name, resultNode);\
352 (resultNode)->prev = referenceNode->prev;\
353 referenceNode->prev = resultNode;\
354 (resultNode)->next = referenceNode;\
355 if ((resultNode)->prev) {\
356 (resultNode)->prev->next = resultNode;\
357 }\
358 else {\
359 /* referenceNode was head node */\
360 (name)->head = resultNode;\
361 }\
362 } while(0)
363
364 /**
365 * write the llist content to filename file
366 * No NULL checks are done on the parameters
367 *
368 * \param
369 * filename file name string
370 */
371 #define llistWriteFilename(name, filename) do {\
372 FILE *UNIQVAR(f) = fopen(filename, "w");\
373 if (UNIQVAR(f)) {\
374 llistForEach(name, UNIQVAR(node)) {\
375 fwrite(&UNIQVAR(node)->elem, 1, sizeof(UNIQVAR(node)->elem), UNIQVAR(f));\
376 }\
377 fclose(UNIQVAR(f));\
378 }\
379 } while(0)
380
381 /**
382 * write the llist content to disk
383 * No NULL checks are done on the parameters
384 *
385 * \param
386 * file already opened file
387 */
388 #define llistWrite(name, file) do {\
389 llistForEach(name, UNIQVAR(node)) {\
390 fwrite(&UNIQVAR(node)->elem, 1, sizeof(UNIQVAR(node)->elem), file);\
391 }\
392 } while(0)
393
394 /**
395 * read a llist from filename file
396 * No NULL checks are done on the parameters
397 *
398 * \param
399 * filename file name string
400 */
401 #define llistReadFilename(name, filename) do {\
402 if (fileExists(filename)) {\
403 size_t UNIQVAR(sz) = fileSize(filename);\
404 const size_t UNIQVAR(elemSz) = sizeof(dArrayLast(&(name)->list).elem);\
405 if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\
406 UNIQVAR(sz) /= UNIQVAR(elemSz);\
407 if (UNIQVAR(sz) > (size_t)(name)->list.maxCount) /* file size exceeds capacity */ break;\
408 FILE *UNIQVAR(f) = fopen(filename, "r");\
409 if (UNIQVAR(f)) {\
410 range(UNIQVAR(i), UNIQVAR(sz)) {\
411 llistPush(name);\
412 fread(&llistLast(name), 1, UNIQVAR(elemSz), UNIQVAR(f));\
413 }\
414 fclose(UNIQVAR(f));\
415 }\
416 }\
417 } while(0)
418
419 /**
420 * read a llist from disk
421 * No NULL checks are done on the parameters
422 *
423 * \param
424 * file already opened file
425 */
426 #define llistRead(name, file) do {\
427 fseek(file, 0 , SEEK_END);\
428 size_t UNIQVAR(sz) = ftell(file);\
429 fseek(file, 0 , SEEK_SET);\
430 const size_t UNIQVAR(elemSz) = sizeof(dArrayLast(&(name)->list).elem);\
431 if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\
432 UNIQVAR(sz) /= UNIQVAR(elemSz);\
433 if (UNIQVAR(sz) > (size_t)(name)->list.maxCount) /* file size exceeds capacity */ break;\
434 range(UNIQVAR(i), UNIQVAR(sz)) {\
435 llistPush(name);\
436 fread(&llistLast(name), 1, UNIQVAR(elemSz), file);\
437 }\
438 } while(0)
439