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: