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)