💾 Archived View for gmi.noulin.net › gitRepositories › staticList › file › staticList.h.gmi captured on 2023-01-29 at 11:37:07. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
staticList.h (13028B)
1
2 /**
3 * \file
4 *
5 * Static double linked list
6 *
7 * NOTE: The macros in this file are for creating list functions wrapping the macros.
8 * The parameters to these macros should be variables to avoid wrong computation
9 * and infinite loops.
10 * Example:
11 * staticListDelNode(list, list.head) fails because list.head changes value during the
12 * macro execution.
13 *
14 * The number of nodes is defined at list declaration, all the nodes are preallocated.
15 * The heap is not used, there is no malloc, realloc or free.
16 *
17 * The status of the macros is saved (list).res and is set to true when the operation is success and
18 * false when the operation is failure.
19 *
20 * The element type handled by the list is defined with staticListT
21 *
22 * Example:
23 *
24 * define list:
25 * staticListT(slt, u32, 3);
26 *
27 * declare list:
28 * slt sl;
29 *
30 * initialize:
31 * staticListInit(sl);
32 *
33 * push element:
34 * staticListPush(sl);
35 * staticListLast(sl) = 1;
36 *
37 * Pop/dellast element:
38 * staticListPop(sl);
39 */
40
41 #include "libsheepyObject.h"
42
43 /**
44 * list and node definition
45 *
46 * MAXCOUNT is the list capacity
47 */
48 #define staticListT(typeName, elementType, MAXCOUNT)\
49 typ struct UNIQVAR(nodet) UNIQVAR(nodet);\
50 struct UNIQVAR(nodet) {\
51 elementType elem;\
52 UNIQVAR(nodet) *prev;\
53 UNIQVAR(nodet) *next;\
54 };\
55 staticArrayT(UNIQVAR(aNodet), UNIQVAR(nodet), MAXCOUNT);\
56 staticArrayT(UNIQVAR(freeaNodet), UNIQVAR(nodet)*, MAXCOUNT);\
57 typ struct {\
58 UNIQVAR(nodet) *head;\
59 UNIQVAR(nodet) *last;\
60 UNIQVAR(aNodet) list;\
61 UNIQVAR(freeaNodet) freeList;\
62 bool res;\
63 } typeName
64
65 /**
66 * initialize list
67 *
68 * \return
69 * (name).res true success, false failed
70 */
71 #define staticListInit(name) do{\
72 (name).head = (name).last = NULL;\
73 staticArrayInit((name).list)\
74 staticArrayInit((name).freeList);\
75 (name).res = true;\
76 } while(0)
77
78 /**
79 * node type for declaring pointers to nodes
80 *
81 * Example:
82 * staticListNodeType(name) node;
83 * staticListUnlink(name, node);
84 * */
85 #define staticListNodeType(name) typeof((name).head)
86
87 /**
88 * is list empty
89 */
90 #define staticListIsEmpty(name) (staticArrayIsEmpty((name).list) || staticArrayIsFull((name).freeList))
91
92 /**
93 * is list full
94 */
95 #define staticListIsFull(name) (staticArrayIsFull((name).list) && staticArrayIsEmpty((name).freeList))
96
97 /**
98 * push element to list (only allocates node)
99 * use staticListLast to access the element
100 *
101 * \return
102 * (name).res true success, false failed
103 */
104 #define staticListPush(name) do{\
105 if (staticArrayIsEmpty((name).freeList)) {\
106 if (staticArrayIsFull((name).list)) {\
107 /* the list is full */\
108 (name).res = false;\
109 break;\
110 }\
111 staticArrayPush((name).list);\
112 if (!(name).last) {\
113 /* first node */\
114 staticArrayLast((name).list).prev = NULL;\
115 staticArrayLast((name).list).next = NULL;\
116 (name).head = &staticArrayLast((name).list);\
117 (name).last = &staticArrayLast((name).list);\
118 }\
119 else {\
120 /* link to previous node */\
121 staticArrayLast((name).list).prev = (name).last;\
122 (name).last->next = &staticArrayLast((name).list);\
123 staticArrayLast((name).list).next = NULL;\
124 (name).last = &staticArrayLast((name).list);\
125 }\
126 }\
127 else {\
128 /* reuse a free node */\
129 if (!(name).last) {\
130 staticArrayLast((name).freeList)->prev = NULL;\
131 staticArrayLast((name).freeList)->next = NULL;\
132 (name).head = staticArrayLast((name).freeList);\
133 (name).last = staticArrayLast((name).freeList);\
134 }\
135 else {\
136 staticArrayLast((name).freeList)->prev = (name).last;\
137 (name).last->next = staticArrayLast((name).freeList);\
138 staticArrayLast((name).freeList)->next = NULL;\
139 (name).last = staticArrayLast((name).freeList);\
140 }\
141 staticArrayPop((name).freeList);\
142 }\
143 (name).res = true;\
144 } while(0)
145
146 /**
147 * pop element from list (only free node)
148 *
149 * \return
150 * (name).res true success, false failed: the list is empty
151 */
152 #define staticListPop(name) do{\
153 if (!(name).last) {\
154 /* the list is empty */\
155 (name).res = false;\
156 break;\
157 }\
158 staticArrayPush((name).freeList);\
159 staticArrayLast((name).freeList) = (name).last;\
160 (name).last = (name).last->prev;\
161 if ((name).last) (name).last->next = NULL;\
162 if (!(name).last) /* the list is empty */ (name).head = NULL;\
163 (name).res = true;\
164 } while(0)
165
166 #define staticListDelLast staticListPop
167
168 /**
169 * unlink node
170 *
171 * node must be of type staticListNodeType(name)
172 *
173 * the node can be freed with staticListFreeUnlinked or
174 * inserted in the list with staticListInsertAfter or staticListInsertBefore
175 */
176 #define staticListUnlink(name, node) do{\
177 if (!(node)->prev) {\
178 /* node is head */\
179 (name).head = (node)->next;\
180 }\
181 else {\
182 (node)->prev->next = (node)->next;\
183 }\
184 if (!(node)->next) {\
185 /* node is last */\
186 (name).last = (node)->prev;\
187 }\
188 else {\
189 (node)->next->prev = (node)->prev;\
190 }\
191 } while(0)
192
193 /**
194 * free unlinked node
195 *
196 * node must be of type staticListNodeType(name)
197 */
198 #define staticListFreeUnlinked(name, node) do{\
199 staticArrayPush((name).freeList);\
200 staticArrayLast((name).freeList) = node;\
201 } while(0)
202
203 /**
204 * delete node
205 *
206 * node must be of type staticListNodeType(name)
207 *
208 * unlink and free node
209 */
210 #define staticListDelNode(name, node) do{\
211 staticListUnlink(name, node);\
212 staticListFreeUnlinked(name, node);\
213 (name).res = true;\
214 } while(0)
215
216 /** first element */
217 #define staticListFirst(name) (name).head->elem
218
219 /** first node pointer */
220 #define staticListFirstNode(name) (name).head
221 #define staticListHeadNode staticListFirstNode
222
223 /** last element */
224 #define staticListLast(name) (name).last->elem
225
226 /** last node pointer */
227 #define staticListLasttNode(name) (name).last
228
229 /** previous node */
230 #define staticListPrev(node) (node)->prev
231
232 /** next node */
233 #define staticListNext(node) (node)->next
234
235 /** node element (or use node->elem) */
236 #define staticListGetElem(node) (node)->elem
237
238 /**
239 * swap node1 with node2
240 *
241 * \return
242 * (name).res true success, false failed
243 */
244 #define staticListSwap(name, node1, node2) do{\
245 /* disable sanity checks to keep it simple - if (!node1 or !node2) {*/\
246 /* (name).res = false;*/\
247 /* break;*/\
248 /*}*/\
249 (name).res = true;\
250 if (node1 == node2) /* node1 and node2 are the same node, nothing to do */ break;\
251 var UNIQVAR(tmp) = (node1)->next;\
252 (node1)->next = (node2)->next;\
253 (node2)->next = UNIQVAR(tmp);\
254 if (!(node1)->next) (name).last = node1;\
255 else (node1)->next->prev = node1;\
256 if (!(node2)->next) (name).last = node2;\
257 else (node2)->next->prev = node2;\
258 UNIQVAR(tmp) = (node1)->prev;\
259 (node1)->prev = (node2)->prev;\
260 (node2)->prev = UNIQVAR(tmp);\
261 if (!(node1)->prev) (name).head = node1;\
262 else (node1)->prev->next = node1;\
263 if (!(node2)->prev) (name).head = node2;\
264 else (node2)->prev->next = node2;\
265 } while(0)
266
267 /** loop from head to last */
268 #define staticListForEach(name, node)\
269 for(var node = (name).head; node ; node = staticListNext(node))
270
271 /** loop from last to head */
272 #define staticListForEachDown(name, node)\
273 for(var node = (name).last; node ; node = staticListPrev(node))
274
275 /** loop from startNode to last */
276 #define staticListForEachFrom(node, startNode)\
277 for(var node = startNode; node ; node = (node)->next)
278
279 /** loop from startNode to head */
280 #define staticListForEachFromDown(node, startNode)\
281 for(var node = startNode; node ; node = (node)->prev)
282
283 /**
284 * insert nodeToInsert after referenceNode
285 *
286 * nodeToInsert and referenceNode must be of type staticListNodeType(name)
287 */
288 #define staticListInsertAfter(name, referenceNode, nodeToInsert) do{\
289 (nodeToInsert)->next = referenceNode->next;\
290 referenceNode->next = nodeToInsert;\
291 (nodeToInsert)->prev = referenceNode;\
292 if ((nodeToInsert)->next) {\
293 (nodeToInsert)->next->prev = nodeToInsert;\
294 }\
295 else {\
296 /* referenceNode was last node */\
297 (name).last = nodeToInsert;\
298 }\
299 } while(0)
300
301 /**
302 * insert nodeToInsert before referenceNode
303 *
304 * nodeToInsert and referenceNode must be of type staticListNodeType(name)
305 */
306 #define staticListInsertBefore(name, referenceNode, nodeToInsert) do{\
307 (nodeToInsert)->prev = referenceNode->prev;\
308 referenceNode->prev = nodeToInsert;\
309 (nodeToInsert)->next = referenceNode;\
310 if ((nodeToInsert)->prev) {\
311 (nodeToInsert)->prev->next = nodeToInsert;\
312 }\
313 else {\
314 /* referenceNode was head node */\
315 (name).head = nodeToInsert;\
316 }\
317 } while(0)
318
319
320 // Internal
321 // allocate a node
322 // true success, false failed: list is full
323 #define staticListAddNode(name, resultNode) do{\
324 if (staticArrayIsEmpty((name).freeList)) {\
325 if (staticArrayIsFull((name).list)) {\
326 /* the list is full */\
327 (name).res = false;\
328 break;\
329 }\
330 staticArrayPush((name).list);\
331 resultNode = &staticArrayLast((name).list);\
332 }\
333 else {\
334 /* reuse a free node */\
335 resultNode = staticArrayLast((name).freeList);\
336 staticArrayPop((name).freeList);\
337 }\
338 (name).res = true;\
339 } while(0)
340
341 /**
342 * add new node after referenceNode
343 *
344 * resultNode and referenceNode must be of type staticListNodeType(name)
345 *
346 * \return
347 * resultNode access element in node with resultNode->elem or staticListGetElem(resultNode)
348 */
349 #define staticListAddAfter(name, referenceNode, resultNode) do{\
350 staticListAddNode(name, resultNode);\
351 if (!(name).res) /* list is full, return false */ break;\
352 (resultNode)->next = referenceNode->next;\
353 referenceNode->next = resultNode;\
354 (resultNode)->prev = referenceNode;\
355 if ((resultNode)->next) {\
356 (resultNode)->next->prev = resultNode;\
357 }\
358 else {\
359 /* referenceNode was last node */\
360 (name).last = resultNode;\
361 }\
362 } while(0)
363
364 /**
365 * add new node before referenceNode
366 *
367 * resultNode and referenceNode must be of type staticListNodeType(name)
368 *
369 * \return
370 * resultNode access element in node with resultNode->elem or staticListGetElem(resultNode)
371 */
372 #define staticListAddBefore(name, referenceNode, resultNode) do{\
373 staticListAddNode(name, resultNode);\
374 if (!(name).res) /* list is full, return false */ break;\
375 (resultNode)->prev = referenceNode->prev;\
376 referenceNode->prev = resultNode;\
377 (resultNode)->next = referenceNode;\
378 if ((resultNode)->prev) {\
379 (resultNode)->prev->next = resultNode;\
380 }\
381 else {\
382 /* referenceNode was head node */\
383 (name).head = resultNode;\
384 }\
385 } while(0)
386
387 /**
388 * write the staticList content to filename file
389 * No NULL checks are done on the parameters
390 *
391 * \param
392 * filename file name string
393 */
394 #define staticListWriteFilename(name, filename) do {\
395 FILE *UNIQVAR(f) = fopen(filename, "w");\
396 if (UNIQVAR(f)) {\
397 staticListForEach(name, UNIQVAR(node)) {\
398 fwrite(&UNIQVAR(node)->elem, 1, sizeof(UNIQVAR(node)->elem), UNIQVAR(f));\
399 }\
400 fclose(UNIQVAR(f));\
401 }\
402 } while(0)
403
404 /**
405 * write the staticList content to disk
406 * No NULL checks are done on the parameters
407 *
408 * \param
409 * file already opened file
410 */
411 #define staticListWrite(name, file) do {\
412 staticListForEach(name, UNIQVAR(node)) {\
413 fwrite(&UNIQVAR(node)->elem, 1, sizeof(UNIQVAR(node)->elem), file);\
414 }\
415 } while(0)
416
417 /**
418 * read a staticList from filename file
419 * No NULL checks are done on the parameters
420 *
421 * \param
422 * filename file name string
423 */
424 #define staticListReadFilename(name, filename) do {\
425 if (fileExists(filename)) {\
426 size_t UNIQVAR(sz) = fileSize(filename);\
427 const size_t UNIQVAR(elemSz) = sizeof(staticArrayLast((name).list).elem);\
428 if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\
429 UNIQVAR(sz) /= UNIQVAR(elemSz);\
430 if (UNIQVAR(sz) > (size_t)(name).list.maxCount) /* file size exceeds capacity */ break;\
431 FILE *UNIQVAR(f) = fopen(filename, "r");\
432 if (UNIQVAR(f)) {\
433 range(UNIQVAR(i), UNIQVAR(sz)) {\
434 staticListPush(name);\
435 fread(&staticListLast(name), 1, UNIQVAR(elemSz), UNIQVAR(f));\
436 }\
437 fclose(UNIQVAR(f));\
438 }\
439 }\
440 } while(0)
441
442 /**
443 * read a staticList from disk
444 * No NULL checks are done on the parameters
445 *
446 * \param
447 * file already opened file
448 */
449 #define staticListRead(name, file) do {\
450 fseek(file, 0 , SEEK_END);\
451 size_t UNIQVAR(sz) = ftell(file);\
452 fseek(file, 0 , SEEK_SET);\
453 const size_t UNIQVAR(elemSz) = sizeof(staticArrayLast((name).list).elem);\
454 if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\
455 UNIQVAR(sz) /= UNIQVAR(elemSz);\
456 if (UNIQVAR(sz) > (size_t)(name).list.maxCount) /* file size exceeds capacity */ break;\
457 range(UNIQVAR(i), UNIQVAR(sz)) {\
458 staticListPush(name);\
459 fread(&staticListLast(name), 1, UNIQVAR(elemSz), file);\
460 }\
461 } while(0)