singleListe.h (17925B)
1 2 3 /** 4 * \file 5 * 6 * Single linked list with external dArray: singleListe 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 singleListe are linked with pointers and dynamically allocated in segments and an extrernal dArray 13 * so multiple lists can be stored in single dArray making free node reuse more efficient. 14 * 15 * NOTE: The macros in this file are for creating list functions wrapping the macros. 16 * 17 * The element type handled by the list is defined with singleListeT 18 * 19 * The external node and free node storage must be allocated after declaring the first list and before running singleListeStoreIinit 20 * 21 * The nodes have 2 members: .elem and .prev, .elem is the element data and .prev is the index of the previous node 22 * 23 * use push and pop to stack nodes 24 * 25 * The forEach macros loop on nodes or elements from last node to head node 26 * 27 * use unlinkPrev or unlinkBefore and unlinkLast to unlink nodes anywhere in the list 28 * 29 * use insertBefore, addBefore to insert anywhere in the list, before head and push, insertLast, addLast to insert after last 30 * 31 * use freeUnlinked to free unlinked nodes 32 * 33 * use singleListeDelPrev or singleListeDelBefore, singleListeDelLast or singleListePop to delete nodes anywhere in the list 34 * 35 * To create a list in reverse order, add the first node with push and then add the nodes with addBefore head 36 * 37 * Example: 38 * 39 * // define list: 40 * singleListeT(slt, u32); 41 * 42 * // declare list: 43 * slt sl; 44 * 45 * // initialize node storage 46 * // local 47 * singleListeNodesT(&sl) nodeStore; 48 * singleListeFreeNodesT(&sl) freeNodeStore; 49 * singleListeStoreInit(&nodeStore, &freeNodeStore); 50 * 51 * // or on heap 52 * singleListeNodesPtrT(&sl) nodeStore; 53 * singleListeFreeNodesPtrT(&sl) freeNodeStore; 54 * nodeStore = malloc(sizeof(singleListeNodesT(&sl))); 55 * freeNodeStore = malloc(sizeof(singleListeFreeNodesT(&sl))); 56 * 57 * // initialize: 58 * singleListeInit(&sl, &nodeStore, &freeNodeStore); 59 * 60 * // or on heap 61 * singleListeInit(&sl, nodeStore, freeNodeStore); 62 * 63 * // push element: 64 * singleListePush(&sl); 65 * singleListeLast(&sl) = 1; 66 * sl.last->elem = 1; 67 * 68 * singleListePush(&sl); 69 * singleListeLast(&sl) = 2; 70 * 71 * // head element 72 * singleListeHead(&sl) = 0; 73 * sl.head->elem = 0; 74 * 75 * // previous node for last node 76 * var prev = sl.last->prev; 77 * prev->elem = 4; 78 * 79 * // pointer to node 80 * singleListeNodeType(&sl) pointer = singleListeHeadNode(&sl); 81 * 82 * // Pop/delLast element: 83 * singleListePop(&sl); 84 * 85 * // free list 86 * singleListeFree(&sl); 87 * 88 * // free node storage, after this all lists using this storage are invalid 89 * singleListeStoreFree(&nodeStore, &freeNodeStore); 90 */ 91 92 #include "libsheepyObject.h" 93 94 /** 95 * list and node definition 96 */ 97 #define singleListeT(typeName, elementType)\ 98 /* node type */\ 99 typ struct UNIQVAR(nodet) UNIQVAR(nodet);\ 100 struct UNIQVAR(nodet) {\ 101 elementType elem;\ 102 UNIQVAR(nodet) *prev;\ 103 };\ 104 /* dArray storing the nodes */\ 105 dArrayT(UNIQVAR(aNodet), UNIQVAR(nodet));\ 106 /* free node list */\ 107 dArrayT(UNIQVAR(freeaNodet), UNIQVAR(nodet)*);\ 108 typ struct {\ 109 UNIQVAR(nodet) *head; /* first node */\ 110 UNIQVAR(nodet) *last; /* last node */\ 111 UNIQVAR(aNodet) *list; /* node dArray */\ 112 UNIQVAR(freeaNodet) *freeList; /* free node dArray */\ 113 size_t count; /* node count */\ 114 } typeName 115 116 /** dArray type for storing the nodes */ 117 #define singleListeNodesT(name) typeof(*(name)->list) 118 119 /** pointer type to dArray storing the nodes */ 120 #define singleListeNodesPtrT(name) typeof((name)->list) 121 122 /** dArray type for storing the free nodes */ 123 #define singleListeFreeNodesT(name) typeof(*(name)->freeList) 124 125 /** pointer type to dArray storing the free nodes */ 126 #define singleListeFreeNodesPtrT(name) typeof((name)->freeList) 127 128 /** 129 * initialize the dArrays storing the nodes for all the lists 130 */ 131 #define singleListeStoreInit(nodes, freeNodes) do{\ 132 dArrayInit(nodes);\ 133 dArrayInit(freeNodes);\ 134 } while(0) 135 136 /** 137 * free node store for all lists 138 * after this, all the nodes in lists are freed 139 */ 140 #define singleListeStoreFree(nodes, freeNodes) do{\ 141 dArrayFree(nodes);\ 142 dArrayFree(freeNodes);\ 143 } while(0) 144 145 /** 146 * initialize list 147 * 148 * nodes and freeNodes must be initialized once before calling singleListeInit 149 * 150 * \return 151 * true success, false failed 152 */ 153 #define singleListeInit(name, nodes, freeNodes) ({\ 154 (name)->head = NULL;\ 155 (name)->last = NULL;\ 156 (name)->list = nodes;\ 157 (name)->freeList = freeNodes;\ 158 (name)->count = 0;\ 159 true;\ 160 }) 161 162 /** 163 * free list nodes 164 * free and reset internal structures 165 * 166 * the dArrays storing the nodes are kept, use singleListeStoreFree to free them 167 */ 168 #define singleListeFree(name) do{\ 169 singleListeForEachDown(name, UNIQVAR(node)) {\ 170 dArrayAppend((name)->freeList, UNIQVAR(node));\ 171 }\ 172 (name)->head = NULL;\ 173 (name)->last = NULL;\ 174 (name)->count = 0;\ 175 } while(0) 176 177 /** 178 * node type for declaring pointers to nodes 179 * */ 180 #define singleListeNodeType(name) typeof((name)->head) 181 182 /** 183 * is list empty 184 */ 185 #define singleListeIsEmpty(name) (!(name)->count) 186 187 /** 188 * element count in list 189 */ 190 #define singleListeCount(name) (name)->count 191 192 /** 193 * push element to list (only allocates node) 194 * use singleListeLast to access the element 195 * 196 * \return 197 * true success, false failed 198 */ 199 #define singleListePush(name) ({\ 200 /* steps: 201 * check if free node is empty 202 * free list is empty, add a new node 203 * create first node 204 * or link to previous node 205 * reuse a free node 206 * create first node 207 * or link to previous node 208 */\ 209 if (dArrayIsEmpty((name)->freeList)) {\ 210 /* free list is empty, add a new node */\ 211 dArrayPush((name)->list);\ 212 if (singleListeIsEmpty(name)) {\ 213 /* first node */\ 214 dArrayLast((name)->list).prev = NULL;\ 215 (name)->head = (name)->last = dArrayLastPtr((name)->list);\ 216 }\ 217 else {\ 218 /* link to previous node */\ 219 dArrayLast((name)->list).prev = (name)->last;\ 220 (name)->last = dArrayLastPtr((name)->list);\ 221 }\ 222 }\ 223 else {\ 224 /* reuse a free node */\ 225 if (singleListeIsEmpty(name)) {\ 226 /* first node */\ 227 dArrayLast((name)->freeList)->prev = NULL;\ 228 (name)->head = (name)->last = dArrayLast((name)->freeList);\ 229 }\ 230 else {\ 231 /* link to previous node */\ 232 dArrayLast((name)->freeList)->prev = (name)->last;\ 233 (name)->last = dArrayLast((name)->freeList);\ 234 }\ 235 dArrayDelLast((name)->freeList);\ 236 }\ 237 (name)->count++;\ 238 true;\ 239 }) 240 241 /** 242 * pop element from list (only free node) 243 * 244 * \return 245 * true success, false failed: the list is empty 246 */ 247 #define singleListePop(name) ({\ 248 bool UNIQVAR(res) = true;\ 249 if (singleListeIsEmpty(name)) {\ 250 /* the list is empty */\ 251 UNIQVAR(res) = false;\ 252 goto UNIQVAR(ret);\ 253 }\ 254 /* free last node */\ 255 dArrayAppend((name)->freeList, (name)->last);\ 256 /* previous node becomes last node */\ 257 (name)->last = (name)->last->prev;\ 258 if ((name)->count == 1) /* the list is empty, head is gone */ (name)->head = NULL;\ 259 (name)->count--;\ 260 UNIQVAR(ret):\ 261 UNIQVAR(res);\ 262 }) 263 264 #define singleListeDelLast singleListePop 265 266 /** 267 * unlink previous node (use pop or unlinkLast to unlink the last node) 268 * 269 * node must be of type singleListeNodeType(name) 270 * 271 * the node can be freed with singleListeFreeUnlinked or 272 * inserted in the list with singleListeInsertBefore or singleListeInsertLast 273 * 274 * \return 275 * unlinked node index 276 * null index when the list is empty or when node is head 277 */ 278 #define singleListeUnlinkPrev(name, node) ({\ 279 singleListeNodeType(name) UNIQVAR(nde) = node;\ 280 singleListeNodeType(name) UNIQVAR(res) = NULL;\ 281 if (singleListeIsEmpty(name)) /* list is empty*/ goto UNIQVAR(ret);\ 282 if (UNIQVAR(nde) == (name)->head) {\ 283 /* node is head, there is no previous node */\ 284 goto UNIQVAR(ret);\ 285 }\ 286 /* the unlinked node is prev */\ 287 UNIQVAR(res) = UNIQVAR(nde)->prev;\ 288 if (UNIQVAR(res) == (name)->head) {\ 289 /* prev node is head, so node is now head and update head */\ 290 (name)->head = UNIQVAR(nde);\ 291 UNIQVAR(nde)->prev = NULL;\ 292 }\ 293 else {\ 294 /* link previous previous node to node */\ 295 UNIQVAR(nde)->prev = UNIQVAR(res)->prev;\ 296 }\ 297 (name)->count--;\ 298 UNIQVAR(ret):\ 299 UNIQVAR(res);\ 300 }) 301 302 #define singleListeUnlinkBefore singleListeUnlinkPrev 303 304 /** 305 * unlink last node 306 * 307 * the node can be freed with singleListeFreeUnlinked or 308 * inserted in the list with singleListeInsertBefore or singleListeInsertLast 309 * 310 * \return 311 * unlinked node 312 * null index when the list is empty 313 */ 314 #define singleListeUnlinkLast(name) ({\ 315 var UNIQVAR(res) = NULL;\ 316 if (singleListeIsEmpty(name)) /* list is empty*/ goto UNIQVAR(ret);\ 317 /* last is unlinked */\ 318 UNIQVAR(res) = (name)->last;\ 319 /* previous node is now last */\ 320 (name)->last = (name)->last->prev;\ 321 (name)->count--;\ 322 /* if the list is empty set head to null */\ 323 if (singleListeIsEmpty(name)) (name)->head = NULL;\ 324 UNIQVAR(ret):\ 325 UNIQVAR(res);\ 326 }) 327 328 /** 329 * free unlinked node 330 * 331 * node must be of type singleListeNodeType(name) 332 */ 333 #define singleListeFreeUnlinked(name, node) dArrayAppend((name)->freeList, node) 334 335 /** 336 * delete node 337 * 338 * node must be of type singleListeNodeType(name) 339 * 340 * unlink and free node 341 */ 342 #define singleListeDelPrev(name, node) ({\ 343 var UNIQVAR(prev) = singleListeUnlinkPrev(name, node);\ 344 singleListeFreeUnlinked(name, UNIQVAR(prev));\ 345 true;\ 346 }) 347 348 #define singleListeDelBefore singleListeDelPrev 349 350 351 352 353 354 /** first element */ 355 #define singleListeFirst(name) (name)->head->elem 356 #define singleListeHead singleListeFirst 357 358 /** first previous node index (always null) */ 359 #define singleListeFirstPrevIdx(name) (name)->head->prev 360 #define singleListeHeadPrev singleListeFirstPrev 361 362 /** first node */ 363 #define singleListeFirstNode(name) (name)->head 364 #define singleListeHeadNode singleListeFirstNode 365 366 /** last element */ 367 #define singleListeLast(name) (name)->last->elem 368 369 /** last previous node index */ 370 #define singleListeLastPrev(name) (name)->last->prev 371 372 /** last node */ 373 #define singleListeLastNode(name) (name)->last 374 375 /** node element (or use node->elem) */ 376 #define singleListeElem(node) (node)->elem 377 378 /** previous index in node */ 379 #define singleListePrev(node) (node)->prev 380 381 382 383 384 385 386 387 388 /** loop node pointers from last to head, to access the elment use singleListeNodePtrElem(node) or (node)->elem */ 389 #define singleListeForEachDown(name, node) lForEachDown(node, (name)->last) 390 391 /** loop element from last to head (the element data is copied) */ 392 #define singleListeForEachElemDown(name, element)\ 393 var UNIQVAR(node) = (name)->last;\ 394 for(var element = singleListeLast(name); UNIQVAR(node) ; UNIQVAR(node) = UNIQVAR(node)->prev, element = UNIQVAR(node) ? UNIQVAR(node)->elem : element) 395 396 /** loop element pointers from last to head, use *elemPtr to access the element data */ 397 #define singleListeForEachElemPDown(name, elemPtr)\ 398 var UNIQVAR(node) = (name)->last;\ 399 for(var elemPtr = &singleListeLast(name); UNIQVAR(node) ; UNIQVAR(node) = UNIQVAR(node)->prev, elemPtr = UNIQVAR(node) ? &UNIQVAR(node)->elem : elemPtr) 400 401 /** loop node pointers from startNode to head, to access the elment use singleListeNodePtrElem(node) or (node)->elem */ 402 #define singleListeForEachNodeFromDown(name, node, startNode) lForEachDown(node, startNode) 403 404 /** loop element from startNode to head (the element data is copied) */ 405 #define singleListeForEachElemFromDown(name, element, startNode)\ 406 var UNIQVAR(node) = startNode;\ 407 for(var element = singleListeLast(name); UNIQVAR(node) ; UNIQVAR(node) = UNIQVAR(node)->prev, element = UNIQVAR(node) ? UNIQVAR(node)->elem : element) 408 409 /** loop element pointers from startNode to head, use *elemPtr to access the element data */ 410 #define singleListeForEachElemPFromDown(name, elemPtr, startNode)\ 411 var UNIQVAR(node) = startNode;\ 412 for(var elemPtr = &singleListeLast(name); UNIQVAR(node) ; UNIQVAR(node) = UNIQVAR(node)->prev, elemPtr = UNIQVAR(node) ? &UNIQVAR(node)->elem : elemPtr) 413 414 415 416 417 418 419 /** 420 * insert nodeToInsert before referenceNode 421 */ 422 #define singleListeInsertBefore(name, referenceNode, nodeToInsert) do{\ 423 singleListeNodeType(name) UNIQVAR(refNode) = referenceNode;\ 424 singleListeNodeType(name) UNIQVAR(nodeToInsert) = nodeToInsert;\ 425 /* save previous node index */\ 426 /* connect rest of the list to nodeToInsert */\ 427 UNIQVAR(nodeToInsert)->prev = UNIQVAR(refNode)->prev;\ 428 /* previous node in now nodeToInsert */\ 429 UNIQVAR(refNode)->prev = UNIQVAR(nodeToInsert);\ 430 if (!UNIQVAR(nodeToInsert)->prev) /* referenceNode was head node */ (name)->head = UNIQVAR(nodeToInsert);\ 431 (name)->count++;\ 432 } while(0) 433 434 #define singleListeInsertPrev singleListeInsertBefore 435 436 /** 437 * insert nodeToInsert last 438 */ 439 #define singleListeInsertLast(name, nodeToInsert) do{\ 440 singleListeNodeType(name) UNIQVAR(nodeToInsert) = nodeToInsert;\ 441 if (singleListeIsEmpty(name)) {\ 442 /* list is empty, previous node is null and set both head and last */\ 443 UNIQVAR(nodeToInsert)->prev = NULL;\ 444 (name)->head = (name)->last = UNIQVAR(nodeToInsert);\ 445 }\ 446 else {\ 447 /* last node is previous node for nodeToInsert */\ 448 UNIQVAR(nodeToInsert)->prev = (name)->last;\ 449 /* now last is nodeToInsert */\ 450 (name)->last = UNIQVAR(nodeToInsert);\ 451 }\ 452 (name)->count++;\ 453 } while(0) 454 455 // // NO - cant insert before and after last 456 // #define singleListeInsert(name, referenceNodeIndex, nodeToInsertIndex) do{\ 457 // typeof((name)->null) UNIQVAR(refNodeIdx) = referenceNodeIndex;\ 458 // if (UNIQVAR(refNodeIdx) != (name)->last) singleListeInsertBefore(name, UNIQVAR(refNodeIdx), nodeToInsertIndex);\ 459 // else singleListeInsertLast(name, nodeToInsertIndex);\ 460 // } while(0) 461 462 463 // Internal 464 // allocate a node 465 #define singleListeAddNode(name) ({\ 466 singleListeNodeType(name) UNIQVAR(res) = NULL;\ 467 if (dArrayIsEmpty((name)->freeList)) {\ 468 /* create new node */\ 469 dArrayPush((name)->list);\ 470 UNIQVAR(res) = dArrayLastPtr((name)->list);\ 471 }\ 472 else {\ 473 /* reuse a free node */\ 474 UNIQVAR(res) = dArrayLast((name)->freeList);\ 475 dArrayDelLast((name)->freeList);\ 476 }\ 477 UNIQVAR(res);\ 478 }) 479 480 /** 481 * add new node before referenceNode 482 * 483 * \return 484 * resultNode new node inserted before referenceNode 485 */ 486 #define singleListeAddBefore(name, referenceNode) ({\ 487 var UNIQVAR(res) = singleListeAddNode(name);\ 488 singleListeInsertBefore(name, referenceNode, UNIQVAR(res));\ 489 UNIQVAR(res);\ 490 }) 491 492 #define singleListeAddPrev singleListeAddBefore 493 494 /** add new node after last 495 * 496 * \return 497 * resultNode new node after last (new last node) 498 */ 499 #define singleListeAddLast(name) ({\ 500 var UNIQVAR(res) = singleListeAddNode(name);\ 501 singleListeInsertLast(name, UNIQVAR(res));\ 502 UNIQVAR(res);\ 503 }) 504 505 // // NO - cant insert before and after last 506 // #define singleListeAdd(name, referenceNodeIndex) ({\ 507 // typeof((name)->null) UNIQVAR(res) = singleListeAddNode(name);\ 508 // singleListeInsert(name, referenceNodeIndex, UNIQVAR(res));\ 509 // UNIQVAR(res);\ 510 // }) 511 512 513 514 515 516 /** 517 * write the singleListe content to filename file 518 * No NULL checks are done on the parameters 519 * 520 * \param 521 * filename file name string 522 */ 523 #define singleListeWriteFilename(name, filename) do {\ 524 FILE *UNIQVAR(f) = fopen(filename, "w");\ 525 if (UNIQVAR(f)) {\ 526 singleListeForEachDown(name, UNIQVAR(node)) {\ 527 fwrite(&singleListeElem(UNIQVAR(node)), 1, sizeof(singleListeElem((name)->head)), UNIQVAR(f));\ 528 }\ 529 fclose(UNIQVAR(f));\ 530 }\ 531 } while(0) 532 533 /** 534 * write the singleListe content to disk 535 * No NULL checks are done on the parameters 536 * 537 * \param 538 * file already opened file 539 */ 540 #define singleListeWrite(name, file) do {\ 541 singleListeForEachDown(name, UNIQVAR(node)) {\ 542 fwrite(&singleListeElem(UNIQVAR(node)), 1, sizeof(singleListeElem((name)->head)), file);\ 543 }\ 544 } while(0) 545 546 /** 547 * read a singleListe from filename file 548 * No NULL checks are done on the parameters 549 * 550 * \param 551 * filename file name string 552 */ 553 #define singleListeReadFilename(name, filename) do {\ 554 if (fileExists(filename)) {\ 555 size_t UNIQVAR(sz) = fileSize(filename);\ 556 const size_t UNIQVAR(elemSz) = sizeof(singleListeElem((name)->head));\ 557 if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\ 558 UNIQVAR(sz) /= UNIQVAR(elemSz);\ 559 if (!UNIQVAR(sz)) /* there is no element to load*/ break;\ 560 FILE *UNIQVAR(f) = fopen(filename, "r");\ 561 if (UNIQVAR(f)) {\ 562 singleListePush(name);\ 563 fread(&singleListeLast(name), 1, UNIQVAR(elemSz), UNIQVAR(f));\ 564 var UNIQVAR(insertBefore) = (name)->last;\ 565 range(UNIQVAR(i), UNIQVAR(sz)-1) {\ 566 UNIQVAR(insertBefore) = singleListeAddBefore(name, UNIQVAR(insertBefore));\ 567 fread(&singleListeElem(UNIQVAR(insertBefore)), 1, UNIQVAR(elemSz), UNIQVAR(f));\ 568 }\ 569 fclose(UNIQVAR(f));\ 570 }\ 571 }\ 572 } while(0) 573 574 /** 575 * read a singleListe from disk 576 * No NULL checks are done on the parameters 577 * 578 * \param 579 * file already opened file 580 */ 581 #define singleListeRead(name, file) do {\ 582 fseek(file, 0 , SEEK_END);\ 583 size_t UNIQVAR(sz) = ftell(file);\ 584 fseek(file, 0 , SEEK_SET);\ 585 const size_t UNIQVAR(elemSz) = sizeof(singleListeElem((name)->head));\ 586 if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\ 587 UNIQVAR(sz) /= UNIQVAR(elemSz);\ 588 if (!UNIQVAR(sz)) /* there is no element to load*/ break;\ 589 singleListePush(name);\ 590 fread(&singleListeLast(name), 1, UNIQVAR(elemSz), file);\ 591 var UNIQVAR(insertBefore) = (name)->last;\ 592 range(UNIQVAR(i), UNIQVAR(sz)-1) {\ 593 UNIQVAR(insertBefore) = singleListeAddBefore(name, UNIQVAR(insertBefore));\ 594 fread(&singleListeElem(UNIQVAR(insertBefore)), 1, UNIQVAR(elemSz), file);\ 595 }\ 596 } while(0) 597 598 // vim: set expandtab ts=2 sw=2: