linkedList.h (11521B)
1 2 /** 3 * \file 4 * 5 * double linked list: llist 6 * 7 * The nodes in llist are linked with pointers and dynamically allocated in segments 8 * 9 * The element type handled by the list is defined with llistT 10 * 11 * 12 * Example: 13 * 14 * // define list: 15 * llistT(llt, u32); 16 * 17 * // declare list: 18 * llt ll; 19 * 20 * // initialize: 21 * llistInit(&ll); 22 * 23 * // push element: 24 * llistPush(&ll); 25 * llistLast(&ll) = 1; 26 * 27 * // Pop/dellast element: 28 * llistPop(&ll); 29 * 30 * // Free 31 * llistFree(&ll); 32 * 33 * TODO create linkedList without head and last 34 */ 35 36 #include "libsheepyObject.h" 37 38 /** 39 * list and node definition 40 */ 41 #define llistT(typeName, elementType)\ 42 typ struct UNIQVAR(nodet) UNIQVAR(nodet);\ 43 struct UNIQVAR(nodet) {\ 44 elementType elem;\ 45 UNIQVAR(nodet) *prev;\ 46 UNIQVAR(nodet) *next;\ 47 };\ 48 dArrayT(UNIQVAR(aNodet), UNIQVAR(nodet));\ 49 dArrayT(UNIQVAR(freeaNodet), UNIQVAR(nodet)*);\ 50 typ struct {\ 51 UNIQVAR(nodet) *head;\ 52 UNIQVAR(nodet) *last;\ 53 UNIQVAR(aNodet) list;\ 54 UNIQVAR(freeaNodet) freeList;\ 55 } typeName 56 57 /** 58 * initialize list 59 */ 60 #define llistInit(name) do{\ 61 (name)->head = (name)->last = NULL;\ 62 dArrayInit(&(name)->list);\ 63 dArrayInit(&(name)->freeList);\ 64 } while(0) 65 66 /** 67 * free list 68 */ 69 #define llistFree(name) do{\ 70 dArrayFree(&(name)->list);\ 71 dArrayFree(&(name)->freeList);\ 72 (name)->head = (name)->last = NULL;\ 73 } while(0) 74 75 /** 76 * node type for declaring pointers to nodes 77 * 78 * Example: 79 * llistNodeType(name) node; 80 * llistUnlink(name, node); 81 * */ 82 #define llistNodeType(name) typeof((name)->head) 83 84 /** 85 * element count in list 86 */ 87 #define llistCount(name) (dArrayCount(&(name)->list) - dArrayCount(&(name)->freeList)) 88 89 90 /** 91 * is list empty 92 */ 93 #define llistIsEmpty(name) ((name)->head == NULL) 94 95 /** 96 * push element to list (only allocates node) 97 * use llistLast to access the element 98 */ 99 #define llistPush(name) do{\ 100 if (dArrayIsEmpty(&(name)->freeList)) {\ 101 dArrayPush(&(name)->list);\ 102 if (!(name)->last) {\ 103 /* first node */\ 104 dArrayLast(&(name)->list).prev = NULL;\ 105 dArrayLast(&(name)->list).next = NULL;\ 106 (name)->head = &dArrayLast(&(name)->list);\ 107 (name)->last = &dArrayLast(&(name)->list);\ 108 }\ 109 else {\ 110 /* link to previous node */\ 111 dArrayLast(&(name)->list).prev = (name)->last;\ 112 (name)->last->next = &dArrayLast(&(name)->list);\ 113 dArrayLast(&(name)->list).next = NULL;\ 114 (name)->last = &dArrayLast(&(name)->list);\ 115 }\ 116 }\ 117 else {\ 118 /* reuse a free node */\ 119 if (!(name)->last) {\ 120 dArrayLast(&(name)->freeList)->prev = NULL;\ 121 dArrayLast(&(name)->freeList)->next = NULL;\ 122 (name)->head = dArrayLast(&(name)->freeList);\ 123 (name)->last = dArrayLast(&(name)->freeList);\ 124 }\ 125 else {\ 126 dArrayLast(&(name)->freeList)->prev = (name)->last;\ 127 (name)->last->next = dArrayLast(&(name)->freeList);\ 128 dArrayLast(&(name)->freeList)->next = NULL;\ 129 (name)->last = dArrayLast(&(name)->freeList);\ 130 }\ 131 dArrayDelLast(&(name)->freeList);\ 132 }\ 133 } while(0) 134 135 /** 136 * pop element from list (only free node) 137 * 138 * \return 139 * true success, false failed: the list is empty 140 */ 141 #define llistPop(name) ({\ 142 bool UNIQVAR(r) = true;\ 143 if (!(name)->last) {\ 144 /* the list is empty */\ 145 UNIQVAR(r) = false;\ 146 goto UNIQVAR(end);\ 147 }\ 148 dArrayPush(&(name)->freeList);\ 149 dArrayLast(&(name)->freeList) = (name)->last;\ 150 (name)->last = (name)->last->prev;\ 151 if ((name)->last) (name)->last->next = NULL;\ 152 if (!(name)->last) /* the list is empty */ (name)->head = NULL;\ 153 UNIQVAR(end):\ 154 UNIQVAR(r);\ 155 }) 156 157 #define llistDelLast llistPop 158 159 /** 160 * unlink node 161 * 162 * node must be of type llistNodeType(name) 163 * 164 * the node can be freed with llistFreeUnlinked or 165 * inserted in the list with llistInsertAfter or llistInsertBefore 166 */ 167 #define llistUnlink(name, node) do{\ 168 if (!(node)->prev) {\ 169 /* node is head */\ 170 (name)->head = (node)->next;\ 171 }\ 172 else {\ 173 (node)->prev->next = (node)->next;\ 174 }\ 175 if (!(node)->next) {\ 176 /* node is last */\ 177 (name)->last = (node)->prev;\ 178 }\ 179 else {\ 180 (node)->next->prev = (node)->prev;\ 181 }\ 182 } while(0) 183 184 /** 185 * free unlinked node 186 * 187 * node must be of type llistNodeType(name) 188 */ 189 #define llistFreeUnlinked(name, node) do{\ 190 dArrayPush(&(name)->freeList);\ 191 dArrayLast(&(name)->freeList) = node;\ 192 } while(0) 193 194 /** 195 * delete node 196 * 197 * node must be of type llistNodeType(name) 198 * 199 * unlink and free node 200 */ 201 #define llistDelNode(name, node) do{\ 202 llistUnlink(name, node);\ 203 llistFreeUnlinked(name, node);\ 204 } while(0) 205 206 /** first element */ 207 #define llistFirst(name) (name)->head->elem 208 209 /** first node pointer */ 210 #define llistFirstNode(name) (name)->head 211 #define llistHeadNode llistFirstNode 212 213 /** last element */ 214 #define llistLast(name) (name)->last->elem 215 216 /** last node pointer */ 217 #define llistLastNode(name) (name)->last 218 219 /** previous node */ 220 #define llistPrev(node) (node)->prev 221 222 /** next node */ 223 #define llistNext(node) (node)->next 224 225 /** node element (or use node->elem) */ 226 #define llistGetElem(node) (node)->elem 227 228 /** 229 * swap node1 with node2 230 */ 231 #define llistSwap(name, node1, node2) do{\ 232 /* disable sanity checks to keep it simple - if (!node1 or !node2) {*/\ 233 /* return value instead --- (name)->res = false;*/\ 234 /* break;*/\ 235 /*}*/\ 236 if (node1 == node2) /* node1 and node2 are the same node, nothing to do */ break;\ 237 var UNIQVAR(tmp) = (node1)->next;\ 238 (node1)->next = (node2)->next;\ 239 (node2)->next = UNIQVAR(tmp);\ 240 if (!(node1)->next) (name)->last = node1;\ 241 else (node1)->next->prev = node1;\ 242 if (!(node2)->next) (name)->last = node2;\ 243 else (node2)->next->prev = node2;\ 244 UNIQVAR(tmp) = (node1)->prev;\ 245 (node1)->prev = (node2)->prev;\ 246 (node2)->prev = UNIQVAR(tmp);\ 247 if (!(node1)->prev) (name)->head = node1;\ 248 else (node1)->prev->next = node1;\ 249 if (!(node2)->prev) (name)->head = node2;\ 250 else (node2)->prev->next = node2;\ 251 } while(0) 252 253 /** loop from head to last */ 254 #define llistForEach(name, node)\ 255 for(var node = (name)->head; node ; node = llistNext(node)) 256 257 /** loop from last to head */ 258 #define llistForEachDown(name, node)\ 259 for(var node = (name)->last; node ; node = llistPrev(node)) 260 261 /** loop from startNode to last */ 262 #define llistForEachFrom(node, startNode)\ 263 for(var node = startNode; node ; node = (node)->next) 264 265 /** loop from startNode to head */ 266 #define llistForEachFromDown(node, startNode)\ 267 for(var node = startNode; node ; node = (node)->prev) 268 269 /** 270 * insert nodeToInsert after referenceNode 271 * 272 * nodeToInsert and referenceNode must be of type llistNodeType(name) 273 */ 274 #define llistInsertAfter(name, referenceNode, nodeToInsert) do{\ 275 (nodeToInsert)->next = referenceNode->next;\ 276 referenceNode->next = nodeToInsert;\ 277 (nodeToInsert)->prev = referenceNode;\ 278 if ((nodeToInsert)->next) {\ 279 (nodeToInsert)->next->prev = nodeToInsert;\ 280 }\ 281 else {\ 282 /* referenceNode was last node */\ 283 (name)->last = nodeToInsert;\ 284 }\ 285 } while(0) 286 287 /** 288 * insert nodeToInsert before referenceNode 289 * 290 * nodeToInsert and referenceNode must be of type llistNodeType(name) 291 */ 292 #define llistInsertBefore(name, referenceNode, nodeToInsert) do{\ 293 (nodeToInsert)->prev = referenceNode->prev;\ 294 referenceNode->prev = nodeToInsert;\ 295 (nodeToInsert)->next = referenceNode;\ 296 if ((nodeToInsert)->prev) {\ 297 (nodeToInsert)->prev->next = nodeToInsert;\ 298 }\ 299 else {\ 300 /* referenceNode was head node */\ 301 (name)->head = nodeToInsert;\ 302 }\ 303 } while(0) 304 305 306 // Internal 307 // allocate a node 308 #define llistAddNode(name, resultNode) do{\ 309 if (dArrayIsEmpty(&(name)->freeList)) {\ 310 dArrayPush(&(name)->list);\ 311 resultNode = &dArrayLast(&(name)->list);\ 312 }\ 313 else {\ 314 /* reuse a free node */\ 315 resultNode = dArrayLast(&(name)->freeList);\ 316 dArrayPop(&(name)->freeList);\ 317 }\ 318 } while(0) 319 320 /** 321 * add new node after referenceNode 322 * 323 * resultNode and referenceNode must be of type llistNodeType(name) 324 * 325 * \return 326 * resultNode access element in node with resultNode->elem or llistGetElem(resultNode) 327 */ 328 #define llistAddAfter(name, referenceNode, resultNode) do{\ 329 llistAddNode(name, resultNode);\ 330 (resultNode)->next = referenceNode->next;\ 331 referenceNode->next = resultNode;\ 332 (resultNode)->prev = referenceNode;\ 333 if ((resultNode)->next) {\ 334 (resultNode)->next->prev = resultNode;\ 335 }\ 336 else {\ 337 /* referenceNode was last node */\ 338 (name)->last = resultNode;\ 339 }\ 340 } while(0) 341 342 /** 343 * add new node before referenceNode 344 * 345 * resultNode and referenceNode must be of type llistNodeType(name) 346 * 347 * \return 348 * resultNode access element in node with resultNode->elem or llistGetElem(resultNode) 349 */ 350 #define llistAddBefore(name, referenceNode, resultNode) do{\ 351 llistAddNode(name, resultNode);\ 352 (resultNode)->prev = referenceNode->prev;\ 353 referenceNode->prev = resultNode;\ 354 (resultNode)->next = referenceNode;\ 355 if ((resultNode)->prev) {\ 356 (resultNode)->prev->next = resultNode;\ 357 }\ 358 else {\ 359 /* referenceNode was head node */\ 360 (name)->head = resultNode;\ 361 }\ 362 } while(0) 363 364 /** 365 * write the llist content to filename file 366 * No NULL checks are done on the parameters 367 * 368 * \param 369 * filename file name string 370 */ 371 #define llistWriteFilename(name, filename) do {\ 372 FILE *UNIQVAR(f) = fopen(filename, "w");\ 373 if (UNIQVAR(f)) {\ 374 llistForEach(name, UNIQVAR(node)) {\ 375 fwrite(&UNIQVAR(node)->elem, 1, sizeof(UNIQVAR(node)->elem), UNIQVAR(f));\ 376 }\ 377 fclose(UNIQVAR(f));\ 378 }\ 379 } while(0) 380 381 /** 382 * write the llist content to disk 383 * No NULL checks are done on the parameters 384 * 385 * \param 386 * file already opened file 387 */ 388 #define llistWrite(name, file) do {\ 389 llistForEach(name, UNIQVAR(node)) {\ 390 fwrite(&UNIQVAR(node)->elem, 1, sizeof(UNIQVAR(node)->elem), file);\ 391 }\ 392 } while(0) 393 394 /** 395 * read a llist from filename file 396 * No NULL checks are done on the parameters 397 * 398 * \param 399 * filename file name string 400 */ 401 #define llistReadFilename(name, filename) do {\ 402 if (fileExists(filename)) {\ 403 size_t UNIQVAR(sz) = fileSize(filename);\ 404 const size_t UNIQVAR(elemSz) = sizeof(dArrayLast(&(name)->list).elem);\ 405 if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\ 406 UNIQVAR(sz) /= UNIQVAR(elemSz);\ 407 if (UNIQVAR(sz) > (size_t)(name)->list.maxCount) /* file size exceeds capacity */ break;\ 408 FILE *UNIQVAR(f) = fopen(filename, "r");\ 409 if (UNIQVAR(f)) {\ 410 range(UNIQVAR(i), UNIQVAR(sz)) {\ 411 llistPush(name);\ 412 fread(&llistLast(name), 1, UNIQVAR(elemSz), UNIQVAR(f));\ 413 }\ 414 fclose(UNIQVAR(f));\ 415 }\ 416 }\ 417 } while(0) 418 419 /** 420 * read a llist from disk 421 * No NULL checks are done on the parameters 422 * 423 * \param 424 * file already opened file 425 */ 426 #define llistRead(name, file) do {\ 427 fseek(file, 0 , SEEK_END);\ 428 size_t UNIQVAR(sz) = ftell(file);\ 429 fseek(file, 0 , SEEK_SET);\ 430 const size_t UNIQVAR(elemSz) = sizeof(dArrayLast(&(name)->list).elem);\ 431 if ((UNIQVAR(sz) % UNIQVAR(elemSz))) /* file size not a multiple of elem size, wrong*/ break;\ 432 UNIQVAR(sz) /= UNIQVAR(elemSz);\ 433 if (UNIQVAR(sz) > (size_t)(name)->list.maxCount) /* file size exceeds capacity */ break;\ 434 range(UNIQVAR(i), UNIQVAR(sz)) {\ 435 llistPush(name);\ 436 fread(&llistLast(name), 1, UNIQVAR(elemSz), file);\ 437 }\ 438 } while(0) 439