linkedListe.h (13788B)
1 2 /** 3 * \file 4 * 5 * double linked list with external dArray: lliste 6 * 7 * the nodes in lliste are linked with pointers and dynamically allocated in segments in a shared dArray, 8 * so multiple lists can be stored in single dArray making free node reuse more efficient 9 * 10 * the element type handled by the list is defined with llisteT 11 * 12 * the external node and free node storage must be allocated after declaring the first list and before running llisteStoreIinit 13 * 14 * Example: 15 * 16 * // define list: 17 * llisteT(llt, u32); 18 * 19 * // declare list: 20 * llt ll; 21 * 22 * // initialize: 23 * llisteInit(&ll); 24 * 25 * // push element: 26 * llistePush(&ll); 27 * llisteLast(&ll) = 1; 28 * 29 * // Pop/dellast element: 30 * llistePop(&ll); 31 * 32 * // Free 33 * llisteFree(&ll); 34 * 35 * // define list: 36 * llisteT(llet, u32); 37 * 38 * // declare list: 39 * llet lle; 40 * 41 * // initialize node storage 42 * // local 43 * llisteNodesT(&lle) nodeStore; 44 * llisteFreeNodesT(&lle) freeNodeStore; 45 * llisteStoreInit(&nodeStore, &freeNodeStore); 46 * 47 * // or on heap 48 * llisteNodesPtrT(&lle) nodeStore; 49 * llisteFreeNodesPtrT(&lle) freeNodeStore; 50 * nodeStore = malloc(sizeof(llisteNodesT(&lle))); 51 * freeNodeStore = malloc(sizeof(llisteFreeNodesT(&lle))); 52 * 53 * // initialize: 54 * llisteInit(&lle, &nodeStore, &freeNodeStore); 55 * 56 * // push element: 57 * llistePush(&lle); 58 * llisteLast(&lle) = 1; 59 * 60 * // Pop/delleast element: 61 * llistePop(&lle); 62 * 63 * // Free 64 * llisteFree(&lle); 65 * 66 * // free node storage, after this all lists using this storage are invalid 67 * llisteStoreFree(&nodeStore, &freeNodeStore); 68 * 69 * 70 * TODO add node count like singlelist 71 * TODO create linkedList without head and last 72 * TODO create a free macro that takes a free function in parameter 73 */ 74 75 #include "libsheepyObject.h" 76 77 /** 78 * list and node definition 79 */ 80 #define llisteT(typeName, elementType)\ 81 typ struct UNIQVAR(nodet) UNIQVAR(nodet);\ 82 struct UNIQVAR(nodet) {\ 83 elementType elem;\ 84 UNIQVAR(nodet) *prev;\ 85 UNIQVAR(nodet) *next;\ 86 };\ 87 dArrayT(UNIQVAR(aNodet), UNIQVAR(nodet));\ 88 dArrayT(UNIQVAR(freeaNodet), UNIQVAR(nodet)*);\ 89 typ struct {\ 90 UNIQVAR(nodet) *head;\ 91 UNIQVAR(nodet) *last;\ 92 UNIQVAR(aNodet) *list;\ 93 UNIQVAR(freeaNodet) *freeList;\ 94 } typeName 95 96 /** dArray type for storing the nodes */ 97 #define llisteNodesT(name) typeof(*(name)->list) 98 99 /** pointer type to dArray storing the nodes */ 100 #define llisteNodesPtrT(name) typeof((name)->list) 101 102 /** dArray type for storing the free nodes */ 103 #define llisteFreeNodesT(name) typeof(*(name)->freeList) 104 105 /** pointer type to dArray storing the free nodes */ 106 #define llisteFreeNodesPtrT(name) typeof((name)->freeList) 107 108 /** 109 * initialize the dArrays storing the nodes for all the lists 110 */ 111 #define llisteStoreInit(nodes, freeNodes) do{\ 112 dArrayInit(nodes);\ 113 dArrayInit(freeNodes);\ 114 } while(0) 115 116 /** 117 * free node store for all lists 118 * after this, all the nodes in lists are freed 119 */ 120 #define llisteStoreFree(nodes, freeNodes) do{\ 121 dArrayFree(nodes);\ 122 dArrayFree(freeNodes);\ 123 } while(0) 124 125 /** 126 * initialize list 127 * 128 * nodes and freeNodes must be initialized once before calling llisteInit 129 * 130 */ 131 #define llisteInit(name, nodes, freeNodes) do{\ 132 (name)->head = (name)->last = NULL;\ 133 (name)->list = nodes;\ 134 (name)->freeList = freeNodes;\ 135 } while(0) 136 137 /** 138 * free list nodes 139 * free and reset internal structures 140 * 141 * the dArrays storing the nodes are kept, use llisteStoreFree to free them 142 */ 143 #define llisteFree(name) do{\ 144 llisteForEachDown(name, UNIQVAR(node)) {\ 145 dArrayAppend((name)->freeList, UNIQVAR(node));\ 146 }\ 147 (name)->head = NULL;\ 148 (name)->last = NULL;\ 149 } while(0) 150 151 /** 152 * node type for declaring pointers to nodes 153 * 154 * Example: 155 * llisteNodeType(name) node; 156 * llisteUnlink(name, node); 157 * */ 158 #define llisteNodeType(name) typeof((name)->head) 159 160 // /** TODO 161 // * element count in list 162 // */ 163 // #define llisteCount(name) (name)->count 164 165 166 /** 167 * is list empty 168 */ 169 #define llisteIsEmpty(name) ((name)->head == NULL) 170 171 /** 172 * push element to list (only allocates node) 173 * use llisteLast to access the element 174 */ 175 #define llistePush(name) do{\ 176 if (dArrayIsEmpty((name)->freeList)) {\ 177 dArrayPush((name)->list);\ 178 if (!(name)->last) {\ 179 /* first node */\ 180 dArrayLast((name)->list).prev = NULL;\ 181 dArrayLast((name)->list).next = NULL;\ 182 (name)->head = &dArrayLast((name)->list);\ 183 (name)->last = &dArrayLast((name)->list);\ 184 }\ 185 else {\ 186 /* link to previous node */\ 187 dArrayLast((name)->list).prev = (name)->last;\ 188 (name)->last->next = &dArrayLast((name)->list);\ 189 dArrayLast((name)->list).next = NULL;\ 190 (name)->last = &dArrayLast((name)->list);\ 191 }\ 192 }\ 193 else {\ 194 /* reuse a free node */\ 195 if (!(name)->last) {\ 196 dArrayLast((name)->freeList)->prev = NULL;\ 197 dArrayLast((name)->freeList)->next = NULL;\ 198 (name)->head = dArrayLast((name)->freeList);\ 199 (name)->last = dArrayLast((name)->freeList);\ 200 }\ 201 else {\ 202 dArrayLast((name)->freeList)->prev = (name)->last;\ 203 (name)->last->next = dArrayLast((name)->freeList);\ 204 dArrayLast((name)->freeList)->next = NULL;\ 205 (name)->last = dArrayLast((name)->freeList);\ 206 }\ 207 dArrayDelLast((name)->freeList);\ 208 }\ 209 } while(0) 210 211 /** 212 * pop element from list (only free node) 213 * 214 * \return 215 * true success, false failed: the list is empty 216 */ 217 #define llistePop(name) ({\ 218 bool UNIQVAR(r) = true;\ 219 if (!(name)->last) {\ 220 /* the list is empty */\ 221 UNIQVAR(r) = false;\ 222 goto UNIQVAR(end);\ 223 }\ 224 dArrayPush((name)->freeList);\ 225 dArrayLast((name)->freeList) = (name)->last;\ 226 (name)->last = (name)->last->prev;\ 227 if ((name)->last) (name)->last->next = NULL;\ 228 if (!(name)->last) /* the list is empty */ (name)->head = NULL;\ 229 UNIQVAR(end):\ 230 UNIQVAR(r);\ 231 }) 232 233 #define llisteDelLast llistePop 234 235 /** 236 * unlink node 237 * 238 * node must be of type llisteNodeType(name) 239 * 240 * the node can be freed with llisteFreeUnlinked or 241 * inserted in the list with llisteInsertAfter or llisteInsertBefore 242 */ 243 #define llisteUnlink(name, node) do{\ 244 if (!(node)->prev) {\ 245 /* node is head */\ 246 (name)->head = (node)->next;\ 247 }\ 248 else {\ 249 (node)->prev->next = (node)->next;\ 250 }\ 251 if (!(node)->next) {\ 252 /* node is last */\ 253 (name)->last = (node)->prev;\ 254 }\ 255 else {\ 256 (node)->next->prev = (node)->prev;\ 257 }\ 258 } while(0) 259 260 /** 261 * free unlinked node 262 * 263 * node must be of type llisteNodeType(name) 264 */ 265 #define llisteFreeUnlinked(name, node) do{\ 266 dArrayPush((name)->freeList);\ 267 dArrayLast((name)->freeList) = node;\ 268 } while(0) 269 270 /** 271 * delete node 272 * 273 * node must be of type llisteNodeType(name) 274 * 275 * unlink and free node 276 */ 277 #define llisteDelNode(name, node) do{\ 278 llisteUnlink(name, node);\ 279 llisteFreeUnlinked(name, node);\ 280 } while(0) 281 282 /** first element */ 283 #define llisteFirst(name) (name)->head->elem 284 285 /** first node pointer */ 286 #define llisteFirstNode(name) (name)->head 287 #define llisteHeadNode llisteFirstNode 288 289 /** last element */ 290 #define llisteLast(name) (name)->last->elem 291 292 /** last node pointer */ 293 #define llisteLastNode(name) (name)->last 294 295 /** previous node */ 296 #define llistePrev(node) (node)->prev 297 298 /** next node */ 299 #define llisteNext(node) (node)->next 300 301 /** node element (or use node->elem) */ 302 #define llisteGetElem(node) (node)->elem 303 304 /** 305 * swap node1 with node2 306 */ 307 #define llisteSwap(name, node1, node2) do{\ 308 /* disable sanity checks to keep it simple - if (!node1 or !node2) {*/\ 309 /* return value instead --- (name)->res = false;*/\ 310 /* break;*/\ 311 /*}*/\ 312 if (node1 == node2) /* node1 and node2 are the same node, nothing to do */ break;\ 313 var UNIQVAR(tmp) = (node1)->next;\ 314 (node1)->next = (node2)->next;\ 315 (node2)->next = UNIQVAR(tmp);\ 316 if (!(node1)->next) (name)->last = node1;\ 317 else (node1)->next->prev = node1;\ 318 if (!(node2)->next) (name)->last = node2;\ 319 else (node2)->next->prev = node2;\ 320 UNIQVAR(tmp) = (node1)->prev;\ 321 (node1)->prev = (node2)->prev;\ 322 (node2)->prev = UNIQVAR(tmp);\ 323 if (!(node1)->prev) (name)->head = node1;\ 324 else (node1)->prev->next = node1;\ 325 if (!(node2)->prev) (name)->head = node2;\ 326 else (node2)->prev->next = node2;\ 327 } while(0) 328 329 /** loop from head to last */ 330 #define llisteForEach(name, node)\ 331 for(var node = (name)->head; node ; node = llisteNext(node)) 332 333 /** loop from last to head */ 334 #define llisteForEachDown(name, node)\ 335 for(var node = (name)->last; node ; node = llistePrev(node)) 336 337 /** loop from startNode to last */ 338 #define llisteForEachFrom(node, startNode)\ 339 for(var node = startNode; node ; node = (node)->next) 340 341 /** loop from startNode to head */ 342 #define llisteForEachFromDown(node, startNode)\ 343 for(var node = startNode; node ; node = (node)->prev) 344 345 /** 346 * insert nodeToInsert after referenceNode 347 * 348 * nodeToInsert and referenceNode must be of type llisteNodeType(name) 349 */ 350 #define llisteInsertAfter(name, referenceNode, nodeToInsert) do{\ 351 (nodeToInsert)->next = referenceNode->next;\ 352 referenceNode->next = nodeToInsert;\ 353 (nodeToInsert)->prev = referenceNode;\ 354 if ((nodeToInsert)->next) {\ 355 (nodeToInsert)->next->prev = nodeToInsert;\ 356 }\ 357 else {\ 358 /* referenceNode was last node */\ 359 (name)->last = nodeToInsert;\ 360 }\ 361 } while(0) 362 363 /** 364 * insert nodeToInsert before referenceNode 365 * 366 * nodeToInsert and referenceNode must be of type llisteNodeType(name) 367 */ 368 #define llisteInsertBefore(name, referenceNode, nodeToInsert) do{\ 369 (nodeToInsert)->prev = referenceNode->prev;\ 370 referenceNode->prev = nodeToInsert;\ 371 (nodeToInsert)->next = referenceNode;\ 372 if ((nodeToInsert)->prev) {\ 373 (nodeToInsert)->prev->next = nodeToInsert;\ 374 }\ 375 else {\ 376 /* referenceNode was head node */\ 377 (name)->head = nodeToInsert;\ 378 }\ 379 } while(0) 380 381 382 // Internal 383 // allocate a node 384 #define llisteAddNode(name, resultNode) do{\ 385 if (dArrayIsEmpty((name)->freeList)) {\ 386 dArrayPush((name)->list);\ 387 resultNode = &dArrayLast((name)->list);\ 388 }\ 389 else {\ 390 /* reuse a free node */\ 391 resultNode = dArrayLast((name)->freeList);\ 392 dArrayPop((name)->freeList);\ 393 }\ 394 } while(0) 395 396 /** 397 * add new node after referenceNode 398 * 399 * resultNode and referenceNode must be of type llisteNodeType(name) 400 * 401 * \return 402 * resultNode access element in node with resultNode->elem or llisteGetElem(resultNode) 403 */ 404 #define llisteAddAfter(name, referenceNode, resultNode) do{\ 405 llisteAddNode(name, resultNode);\ 406 (resultNode)->next = referenceNode->next;\ 407 referenceNode->next = resultNode;\ 408 (resultNode)->prev = referenceNode;\ 409 if ((resultNode)->next) {\ 410 (resultNode)->next->prev = resultNode;\ 411 }\ 412 else {\ 413 /* referenceNode was last node */\ 414 (name)->last = resultNode;\ 415 }\ 416 } while(0) 417 418 /** 419 * add new node before referenceNode 420 * 421 * resultNode and referenceNode must be of type llisteNodeType(name) 422 * 423 * \return 424 * resultNode access element in node with resultNode->elem or llisteGetElem(resultNode) 425 */ 426 #define llisteAddBefore(name, referenceNode, resultNode) do{\ 427 llisteAddNode(name, resultNode);\ 428 (resultNode)->prev = referenceNode->prev;\ 429 referenceNode->prev = resultNode;\ 430 (resultNode)->next = referenceNode;\ 431 if ((resultNode)->prev) {\ 432 (resultNode)->prev->next = resultNode;\ 433 }\ 434 else {\ 435 /* referenceNode was head node */\ 436 (name)->head = resultNode;\ 437 }\ 438 } while(0) 439 440 /** 441 * write the lliste content to filename file 442 * No NULL checks are done on the parameters 443 * 444 * \param 445 * filename file name string 446 */ 447 #define llisteWriteFilename(name, filename) do {\ 448 FILE *UNIQVAR(f) = fopen(filename, "w");\ 449 if (UNIQVAR(f)) {\ 450 llisteForEach(name, UNIQVAR(node)) {\ 451 fwrite(&UNIQVAR(node)->elem, 1, sizeof(UNIQVAR(node)->elem), UNIQVAR(f));\ 452 }\ 453 fclose(UNIQVAR(f));\ 454 }\ 455 } while(0) 456 457 /** 458 * write the lliste content to disk 459 * No NULL checks are done on the parameters 460 * 461 * \param 462 * file already opened file 463 */ 464 #define llisteWrite(name, file) do {\ 465 llisteForEach(name, UNIQVAR(node)) {\ 466 fwrite(&UNIQVAR(node)->elem, 1, sizeof(UNIQVAR(node)->elem), file);\ 467 }\ 468 } while(0) 469 470 /** 471 * read a lliste from filename file 472 * No NULL checks are done on the parameters 473 * 474 * \param 475 * filename file name string 476 */ 477 #define llisteReadFilename(name, filename) do {\ 478 if (fileExists(filename)) {\ 479 size_t UNIQVAR(sz) = fileSize(filename);\ 480 const size_t UNIQVAR(elemSz) = sizeof(dArrayLast((name)->list).elem);\ 481 if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\ 482 UNIQVAR(sz) /= UNIQVAR(elemSz);\ 483 if (UNIQVAR(sz) > (size_t)(name)->list.maxCount) /* file size exceeds capacity */ break;\ 484 FILE *UNIQVAR(f) = fopen(filename, "r");\ 485 if (UNIQVAR(f)) {\ 486 range(UNIQVAR(i), UNIQVAR(sz)) {\ 487 llistePush(name);\ 488 fread(&llisteLast(name), 1, UNIQVAR(elemSz), UNIQVAR(f));\ 489 }\ 490 fclose(UNIQVAR(f));\ 491 }\ 492 }\ 493 } while(0) 494 495 /** 496 * read a lliste from disk 497 * No NULL checks are done on the parameters 498 * 499 * \param 500 * file already opened file 501 */ 502 #define llisteRead(name, file) do {\ 503 fseek(file, 0 , SEEK_END);\ 504 size_t UNIQVAR(sz) = ftell(file);\ 505 fseek(file, 0 , SEEK_SET);\ 506 const size_t UNIQVAR(elemSz) = sizeof(dArrayLast((name)->list).elem);\ 507 if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\ 508 UNIQVAR(sz) /= UNIQVAR(elemSz);\ 509 if (UNIQVAR(sz) > (size_t)(name)->list.maxCount) /* file size exceeds capacity */ break;\ 510 range(UNIQVAR(i), UNIQVAR(sz)) {\ 511 llistePush(name);\ 512 fread(&llisteLast(name), 1, UNIQVAR(elemSz), file);\ 513 }\ 514 } while(0) 515