singleList.h (15838B)
1
2
3 /**
4 * \file
5 *
6 * Single linked list: singleList
7 *
8 * head 1 <- 2 <- 3 last
9 *
10 * The single linked list can be used as a stack and is not efficient when used as a queue.
11 *
12 * The nodes in singleList are linked with pointers and dynamically allocated in segments
13 *
14 * NOTE: The macros in this file are for creating list functions wrapping the macros.
15 *
16 * The element type handled by the list is defined with singleListT
17 *
18 * The nodes have 2 members: .elem and .prev, .elem is the element data and .prev is the index of the previous node
19 *
20 * use push and pop to stack nodes
21 *
22 * The forEach macros loop on nodes or elements from last node to head node
23 *
24 * use unlinkPrev or unlinkBefore and unlinkLast to unlink nodes anywhere in the list
25 *
26 * use insertBefore, addBefore to insert anywhere in the list, before head and push, insertLast, addLast to insert after last
27 *
28 * use freeUnlinked to free unlinked nodes
29 *
30 * use singleListDelPrev or singleListDelBefore, singleListDelLast or singleListPop to delete nodes anywhere in the list
31 *
32 * To create a list in reverse order, add the first node with push and then add the nodes with addBefore head
33 *
34 * Example:
35 *
36 * // define list:
37 * singleListT(slt, u32);
38 *
39 * // declare list:
40 * slt sl;
41 *
42 * // initialize:
43 * singleListInit(&sl);
44 *
45 * // push element:
46 * singleListPush(&sl);
47 * singleListLast(&sl) = 1;
48 * sl.last->elem = 1;
49 *
50 * singleListPush(&sl);
51 * singleListLast(&sl) = 2;
52 *
53 * // head element
54 * singleListHead(&sl) = 0;
55 * sl.head->elem = 0;
56 *
57 * // previous node for last node
58 * var prev = sl.last->prev;
59 * prev->elem = 4;
60 *
61 * // pointer to node
62 * singleListNodeType(&sl) pointer = singleListHeadNode(&sl);
63 *
64 * // Pop/delLast element:
65 * singleListPop(&sl);
66 *
67 * // free list
68 * singleListFree(&sl);
69 */
70
71 #include "libsheepyObject.h"
72
73 /**
74 * list and node definition
75 */
76 #define singleListT(typeName, elementType)\
77 /* node type */\
78 typ struct UNIQVAR(nodet) UNIQVAR(nodet);\
79 struct UNIQVAR(nodet) {\
80 elementType elem;\
81 UNIQVAR(nodet) *prev;\
82 };\
83 /* dArray storing the nodes */\
84 dArrayT(UNIQVAR(aNodet), UNIQVAR(nodet));\
85 /* free node list */\
86 dArrayT(UNIQVAR(freeaNodet), UNIQVAR(nodet)*);\
87 typ struct {\
88 UNIQVAR(nodet) *head; /* first node */\
89 UNIQVAR(nodet) *last; /* last node */\
90 UNIQVAR(aNodet) list; /* node dArray */\
91 UNIQVAR(freeaNodet) freeList; /* free node dArray */\
92 size_t count; /* node count */\
93 } typeName
94
95 /**
96 * initialize list
97 *
98 * \return
99 * true success, false failed
100 */
101 #define singleListInit(name) ({\
102 (name)->head = NULL;\
103 (name)->last = NULL;\
104 dArrayInit(&(name)->list);\
105 dArrayInit(&(name)->freeList);\
106 (name)->count = 0;\
107 true;\
108 })
109
110 /**
111 * free list
112 * free and reset internal structures
113 */
114 #define singleListFree(name) do{\
115 dArrayFree(&(name)->list);\
116 dArrayFree(&(name)->freeList);\
117 (name)->head = NULL;\
118 (name)->last = NULL;\
119 (name)->count = 0;\
120 } while(0)
121
122 /**
123 * node type for declaring pointers to nodes
124 * */
125 #define singleListNodeType(name) typeof((name)->head)
126
127 /**
128 * is list empty
129 */
130 #define singleListIsEmpty(name) (!(name)->count)
131
132 /**
133 * element count in list
134 */
135 #define singleListCount(name) (name)->count
136
137 /**
138 * push element to list (only allocates node)
139 * use singleListLast to access the element
140 *
141 * \return
142 * true success, false failed
143 */
144 #define singleListPush(name) ({\
145 /* steps:
146 * check if free node is empty
147 * free list is empty, add a new node
148 * create first node
149 * or link to previous node
150 * reuse a free node
151 * create first node
152 * or link to previous node
153 */\
154 if (dArrayIsEmpty(&(name)->freeList)) {\
155 /* free list is empty, add a new node */\
156 dArrayPush(&(name)->list);\
157 if (singleListIsEmpty(name)) {\
158 /* first node */\
159 dArrayLast(&(name)->list).prev = NULL;\
160 (name)->head = (name)->last = dArrayLastPtr(&(name)->list);\
161 }\
162 else {\
163 /* link to previous node */\
164 dArrayLast(&(name)->list).prev = (name)->last;\
165 (name)->last = dArrayLastPtr(&(name)->list);\
166 }\
167 }\
168 else {\
169 /* reuse a free node */\
170 if (singleListIsEmpty(name)) {\
171 /* first node */\
172 dArrayLast(&(name)->freeList)->prev = NULL;\
173 (name)->head = (name)->last = dArrayLast(&(name)->freeList);\
174 }\
175 else {\
176 /* link to previous node */\
177 dArrayLast(&(name)->freeList)->prev = (name)->last;\
178 (name)->last = dArrayLast(&(name)->freeList);\
179 }\
180 dArrayDelLast(&(name)->freeList);\
181 }\
182 (name)->count++;\
183 true;\
184 })
185
186 /**
187 * pop element from list (only free node)
188 *
189 * \return
190 * true success, false failed: the list is empty
191 */
192 #define singleListPop(name) ({\
193 bool UNIQVAR(res) = true;\
194 if (singleListIsEmpty(name)) {\
195 /* the list is empty */\
196 UNIQVAR(res) = false;\
197 goto UNIQVAR(ret);\
198 }\
199 /* free last node */\
200 dArrayAppend(&(name)->freeList, (name)->last);\
201 /* previous node becomes last node */\
202 (name)->last = (name)->last->prev;\
203 if ((name)->count == 1) /* the list is empty, head is gone */ (name)->head = NULL;\
204 (name)->count--;\
205 UNIQVAR(ret):\
206 UNIQVAR(res);\
207 })
208
209 #define singleListDelLast singleListPop
210
211 /**
212 * unlink previous node (use pop or unlinkLast to unlink the last node)
213 *
214 * node must be of type singleListNodeType(name)
215 *
216 * the node can be freed with singleListFreeUnlinked or
217 * inserted in the list with singleListInsertBefore or singleListInsertLast
218 *
219 * \return
220 * unlinked node index
221 * null index when the list is empty or when node is head
222 */
223 #define singleListUnlinkPrev(name, node) ({\
224 singleListNodeType(name) UNIQVAR(nde) = node;\
225 singleListNodeType(name) UNIQVAR(res) = NULL;\
226 if (singleListIsEmpty(name)) /* list is empty*/ goto UNIQVAR(ret);\
227 if (UNIQVAR(nde) == (name)->head) {\
228 /* node is head, there is no previous node */\
229 goto UNIQVAR(ret);\
230 }\
231 /* the unlinked node is prev */\
232 UNIQVAR(res) = UNIQVAR(nde)->prev;\
233 if (UNIQVAR(res) == (name)->head) {\
234 /* prev node is head, so node is now head and update head */\
235 (name)->head = UNIQVAR(nde);\
236 UNIQVAR(nde)->prev = NULL;\
237 }\
238 else {\
239 /* link previous previous node to node */\
240 UNIQVAR(nde)->prev = UNIQVAR(res)->prev;\
241 }\
242 (name)->count--;\
243 UNIQVAR(ret):\
244 UNIQVAR(res);\
245 })
246
247 #define singleListUnlinkBefore singleListUnlinkPrev
248
249 /**
250 * unlink last node
251 *
252 * the node can be freed with singleListFreeUnlinked or
253 * inserted in the list with singleListInsertBefore or singleListInsertLast
254 *
255 * \return
256 * unlinked node
257 * null index when the list is empty
258 */
259 #define singleListUnlinkLast(name) ({\
260 var UNIQVAR(res) = NULL;\
261 if (singleListIsEmpty(name)) /* list is empty*/ goto UNIQVAR(ret);\
262 /* last is unlinked */\
263 UNIQVAR(res) = (name)->last;\
264 /* previous node is now last */\
265 (name)->last = (name)->last->prev;\
266 (name)->count--;\
267 /* if the list is empty set head to null */\
268 if (singleListIsEmpty(name)) (name)->head = NULL;\
269 UNIQVAR(ret):\
270 UNIQVAR(res);\
271 })
272
273 /**
274 * free unlinked node
275 *
276 * node must be of type singleListNodeType(name)
277 */
278 #define singleListFreeUnlinked(name, node) dArrayAppend(&(name)->freeList, node)
279
280 /**
281 * delete node
282 *
283 * node must be of type singleListNodeType(name)
284 *
285 * unlink and free node
286 */
287 #define singleListDelPrev(name, node) ({\
288 var UNIQVAR(prev) = singleListUnlinkPrev(name, node);\
289 singleListFreeUnlinked(name, UNIQVAR(prev));\
290 true;\
291 })
292
293 #define singleListDelBefore singleListDelPrev
294
295
296
297
298
299 /** first element */
300 #define singleListFirst(name) (name)->head->elem
301 #define singleListHead singleListFirst
302
303 /** first previous node index (always null) */
304 #define singleListFirstPrevIdx(name) (name)->head->prev
305 #define singleListHeadPrev singleListFirstPrev
306
307 /** first node */
308 #define singleListFirstNode(name) (name)->head
309 #define singleListHeadNode singleListFirstNode
310
311 /** last element */
312 #define singleListLast(name) (name)->last->elem
313
314 /** last previous node index */
315 #define singleListLastPrev(name) (name)->last->prev
316
317 /** last node */
318 #define singleListLastNode(name) (name)->last
319
320 /** node element (or use node->elem) */
321 #define singleListElem(node) (node)->elem
322
323 /** previous index in node */
324 #define singleListPrev(node) (node)->prev
325
326
327
328
329
330
331
332
333 /** loop node pointers from last to head, to access the elment use singleListNodePtrElem(node) or (node)->elem */
334 #define singleListForEachDown(name, node) lForEachDown(node, (name)->last)
335
336 /** loop element from last to head (the element data is copied) */
337 #define singleListForEachElemDown(name, element)\
338 var UNIQVAR(node) = (name)->last;\
339 for(var element = singleListLast(name); UNIQVAR(node) ; UNIQVAR(node) = UNIQVAR(node)->prev, element = UNIQVAR(node) ? UNIQVAR(node)->elem : element)
340
341 /** loop element pointers from last to head, use *elemPtr to access the element data */
342 #define singleListForEachElemPDown(name, elemPtr)\
343 var UNIQVAR(node) = (name)->last;\
344 for(var elemPtr = &singleListLast(name); UNIQVAR(node) ; UNIQVAR(node) = UNIQVAR(node)->prev, elemPtr = UNIQVAR(node) ? &UNIQVAR(node)->elem : elemPtr)
345
346 /** loop node pointers from startNode to head, to access the elment use singleListNodePtrElem(node) or (node)->elem */
347 #define singleListForEachNodeFromDown(name, node, startNode) lForEachDown(node, startNode)
348
349 /** loop element from startNode to head (the element data is copied) */
350 #define singleListForEachElemFromDown(name, element, startNode)\
351 var UNIQVAR(node) = startNode;\
352 for(var element = singleListLast(name); UNIQVAR(node) ; UNIQVAR(node) = UNIQVAR(node)->prev, element = UNIQVAR(node) ? UNIQVAR(node)->elem : element)
353
354 /** loop element pointers from startNode to head, use *elemPtr to access the element data */
355 #define singleListForEachElemPFromDown(name, elemPtr, startNode)\
356 var UNIQVAR(node) = startNode;\
357 for(var elemPtr = &singleListLast(name); UNIQVAR(node) ; UNIQVAR(node) = UNIQVAR(node)->prev, elemPtr = UNIQVAR(node) ? &UNIQVAR(node)->elem : elemPtr)
358
359
360
361
362
363
364 /**
365 * insert nodeToInsert before referenceNode
366 */
367 #define singleListInsertBefore(name, referenceNode, nodeToInsert) do{\
368 singleListNodeType(name) UNIQVAR(refNode) = referenceNode;\
369 singleListNodeType(name) UNIQVAR(nodeToInsert) = nodeToInsert;\
370 /* save previous node index */\
371 /* connect rest of the list to nodeToInsert */\
372 UNIQVAR(nodeToInsert)->prev = UNIQVAR(refNode)->prev;\
373 /* previous node in now nodeToInsert */\
374 UNIQVAR(refNode)->prev = UNIQVAR(nodeToInsert);\
375 if (!UNIQVAR(nodeToInsert)->prev) /* referenceNode was head node */ (name)->head = UNIQVAR(nodeToInsert);\
376 (name)->count++;\
377 } while(0)
378
379 #define singleListInsertPrev singleListInsertBefore
380
381 /**
382 * insert nodeToInsert last
383 */
384 #define singleListInsertLast(name, nodeToInsert) do{\
385 singleListNodeType(name) UNIQVAR(nodeToInsert) = nodeToInsert;\
386 if (singleListIsEmpty(name)) {\
387 /* list is empty, previous node is null and set both head and last */\
388 UNIQVAR(nodeToInsert)->prev = NULL;\
389 (name)->head = (name)->last = UNIQVAR(nodeToInsert);\
390 }\
391 else {\
392 /* last node is previous node for nodeToInsert */\
393 UNIQVAR(nodeToInsert)->prev = (name)->last;\
394 /* now last is nodeToInsert */\
395 (name)->last = UNIQVAR(nodeToInsert);\
396 }\
397 (name)->count++;\
398 } while(0)
399
400 // // NO - cant insert before and after last
401 // #define singleListInsert(name, referenceNodeIndex, nodeToInsertIndex) do{\
402 // typeof((name)->null) UNIQVAR(refNodeIdx) = referenceNodeIndex;\
403 // if (UNIQVAR(refNodeIdx) != (name)->last) singleListInsertBefore(name, UNIQVAR(refNodeIdx), nodeToInsertIndex);\
404 // else singleListInsertLast(name, nodeToInsertIndex);\
405 // } while(0)
406
407
408 // Internal
409 // allocate a node
410 #define singleListAddNode(name) ({\
411 singleListNodeType(name) UNIQVAR(res) = NULL;\
412 if (dArrayIsEmpty(&(name)->freeList)) {\
413 /* create new node */\
414 dArrayPush(&(name)->list);\
415 UNIQVAR(res) = dArrayLastPtr(&(name)->list);\
416 }\
417 else {\
418 /* reuse a free node */\
419 UNIQVAR(res) = dArrayLast(&(name)->freeList);\
420 dArrayDelLast(&(name)->freeList);\
421 }\
422 UNIQVAR(res);\
423 })
424
425 /**
426 * add new node before referenceNode
427 *
428 * \return
429 * resultNode new node inserted before referenceNode
430 */
431 #define singleListAddBefore(name, referenceNode) ({\
432 var UNIQVAR(res) = singleListAddNode(name);\
433 singleListInsertBefore(name, referenceNode, UNIQVAR(res));\
434 UNIQVAR(res);\
435 })
436
437 #define singleListAddPrev singleListAddBefore
438
439 /** add new node after last
440 *
441 * \return
442 * resultNode new node after last (new last node)
443 */
444 #define singleListAddLast(name) ({\
445 var UNIQVAR(res) = singleListAddNode(name);\
446 singleListInsertLast(name, UNIQVAR(res));\
447 UNIQVAR(res);\
448 })
449
450 // // NO - cant insert before and after last
451 // #define singleListAdd(name, referenceNodeIndex) ({\
452 // typeof((name)->null) UNIQVAR(res) = singleListAddNode(name);\
453 // singleListInsert(name, referenceNodeIndex, UNIQVAR(res));\
454 // UNIQVAR(res);\
455 // })
456
457
458
459
460
461 /**
462 * write the singleList content to filename file
463 * No NULL checks are done on the parameters
464 *
465 * \param
466 * filename file name string
467 */
468 #define singleListWriteFilename(name, filename) do {\
469 FILE *UNIQVAR(f) = fopen(filename, "w");\
470 if (UNIQVAR(f)) {\
471 singleListForEachDown(name, UNIQVAR(node)) {\
472 fwrite(&singleListElem(UNIQVAR(node)), 1, sizeof(singleListElem((name)->head)), UNIQVAR(f));\
473 }\
474 fclose(UNIQVAR(f));\
475 }\
476 } while(0)
477
478 /**
479 * write the singleList content to disk
480 * No NULL checks are done on the parameters
481 *
482 * \param
483 * file already opened file
484 */
485 #define singleListWrite(name, file) do {\
486 singleListForEachDown(name, UNIQVAR(node)) {\
487 fwrite(&singleListElem(UNIQVAR(node)), 1, sizeof(singleListElem((name)->head)), file);\
488 }\
489 } while(0)
490
491 /**
492 * read a singleList from filename file
493 * No NULL checks are done on the parameters
494 *
495 * \param
496 * filename file name string
497 */
498 #define singleListReadFilename(name, filename) do {\
499 if (fileExists(filename)) {\
500 size_t UNIQVAR(sz) = fileSize(filename);\
501 const size_t UNIQVAR(elemSz) = sizeof(singleListElem((name)->head));\
502 if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\
503 UNIQVAR(sz) /= UNIQVAR(elemSz);\
504 if (!UNIQVAR(sz)) /* there is no element to load*/ break;\
505 FILE *UNIQVAR(f) = fopen(filename, "r");\
506 if (UNIQVAR(f)) {\
507 singleListPush(name);\
508 fread(&singleListLast(name), 1, UNIQVAR(elemSz), UNIQVAR(f));\
509 var UNIQVAR(insertBefore) = (name)->last;\
510 range(UNIQVAR(i), UNIQVAR(sz)-1) {\
511 UNIQVAR(insertBefore) = singleListAddBefore(name, UNIQVAR(insertBefore));\
512 fread(&singleListElem(UNIQVAR(insertBefore)), 1, UNIQVAR(elemSz), UNIQVAR(f));\
513 }\
514 fclose(UNIQVAR(f));\
515 }\
516 }\
517 } while(0)
518
519 /**
520 * read a singleList from disk
521 * No NULL checks are done on the parameters
522 *
523 * \param
524 * file already opened file
525 */
526 #define singleListRead(name, file) do {\
527 fseek(file, 0 , SEEK_END);\
528 size_t UNIQVAR(sz) = ftell(file);\
529 fseek(file, 0 , SEEK_SET);\
530 const size_t UNIQVAR(elemSz) = sizeof(singleListElem((name)->head));\
531 if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\
532 UNIQVAR(sz) /= UNIQVAR(elemSz);\
533 if (!UNIQVAR(sz)) /* there is no element to load*/ break;\
534 singleListPush(name);\
535 fread(&singleListLast(name), 1, UNIQVAR(elemSz), file);\
536 var UNIQVAR(insertBefore) = (name)->last;\
537 range(UNIQVAR(i), UNIQVAR(sz)-1) {\
538 UNIQVAR(insertBefore) = singleListAddBefore(name, UNIQVAR(insertBefore));\
539 fread(&singleListElem(UNIQVAR(insertBefore)), 1, UNIQVAR(elemSz), file);\
540 }\
541 } while(0)
542
543 // vim: set expandtab ts=2 sw=2: