UNIXworkcode

1 /* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. 3 * 4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions are met: 8 * 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 26 * POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29 #include "cx/linked_list.h" 30 #include "cx/utils.h" 31 #include <string.h> 32 #include <assert.h> 33 34 // LOW LEVEL LINKED LIST FUNCTIONS 35 36 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) 37 #define ll_prev(node) CX_LL_PTR(node, loc_prev) 38 #define ll_next(node) CX_LL_PTR(node, loc_next) 39 #define ll_advance(node) CX_LL_PTR(node, loc_advance) 40 #define ll_data(node) (((char*)(node))+loc_data) 41 42 void *cx_linked_list_at( 43 void const *start, 44 size_t start_index, 45 ptrdiff_t loc_advance, 46 size_t index 47 ) { 48 assert(start != NULL); 49 assert(loc_advance >= 0); 50 size_t i = start_index; 51 void const *cur = start; 52 while (i != index && cur != NULL) { 53 cur = ll_advance(cur); 54 i < index ? i++ : i--; 55 } 56 return (void *) cur; 57 } 58 59 ssize_t cx_linked_list_find( 60 void const *start, 61 ptrdiff_t loc_advance, 62 ptrdiff_t loc_data, 63 cx_compare_func cmp_func, 64 void const *elem 65 ) { 66 assert(start != NULL); 67 assert(loc_advance >= 0); 68 assert(loc_data >= 0); 69 assert(cmp_func); 70 71 void const *node = start; 72 ssize_t index = 0; 73 do { 74 void *current = ll_data(node); 75 if (cmp_func(current, elem) == 0) { 76 return index; 77 } 78 node = ll_advance(node); 79 index++; 80 } while (node != NULL); 81 return -1; 82 } 83 84 void *cx_linked_list_first( 85 void const *node, 86 ptrdiff_t loc_prev 87 ) { 88 return cx_linked_list_last(node, loc_prev); 89 } 90 91 void *cx_linked_list_last( 92 void const *node, 93 ptrdiff_t loc_next 94 ) { 95 assert(node != NULL); 96 assert(loc_next >= 0); 97 98 void const *cur = node; 99 void const *last; 100 do { 101 last = cur; 102 } while ((cur = ll_next(cur)) != NULL); 103 104 return (void *) last; 105 } 106 107 void *cx_linked_list_prev( 108 void const *begin, 109 ptrdiff_t loc_next, 110 void const *node 111 ) { 112 assert(begin != NULL); 113 assert(node != NULL); 114 assert(loc_next >= 0); 115 if (begin == node) return NULL; 116 void const *cur = begin; 117 void const *next; 118 while (1) { 119 next = ll_next(cur); 120 if (next == node) return (void *) cur; 121 cur = next; 122 } 123 } 124 125 void cx_linked_list_link( 126 void *left, 127 void *right, 128 ptrdiff_t loc_prev, 129 ptrdiff_t loc_next 130 ) { 131 assert(loc_next >= 0); 132 ll_next(left) = right; 133 if (loc_prev >= 0) { 134 ll_prev(right) = left; 135 } 136 } 137 138 void cx_linked_list_unlink( 139 void *left, 140 void *right, 141 ptrdiff_t loc_prev, 142 ptrdiff_t loc_next 143 ) { 144 assert (loc_next >= 0); 145 assert(ll_next(left) == right); 146 ll_next(left) = NULL; 147 if (loc_prev >= 0) { 148 assert(ll_prev(right) == left); 149 ll_prev(right) = NULL; 150 } 151 } 152 153 void cx_linked_list_add( 154 void **begin, 155 void **end, 156 ptrdiff_t loc_prev, 157 ptrdiff_t loc_next, 158 void *new_node 159 ) { 160 void *last; 161 if (end == NULL) { 162 assert(begin != NULL); 163 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next); 164 } else { 165 last = *end; 166 } 167 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, last, new_node, new_node); 168 } 169 170 void cx_linked_list_prepend( 171 void **begin, 172 void **end, 173 ptrdiff_t loc_prev, 174 ptrdiff_t loc_next, 175 void *new_node 176 ) { 177 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, NULL, new_node, new_node); 178 } 179 180 void cx_linked_list_insert( 181 void **begin, 182 void **end, 183 ptrdiff_t loc_prev, 184 ptrdiff_t loc_next, 185 void *node, 186 void *new_node 187 ) { 188 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, node, new_node, new_node); 189 } 190 191 void cx_linked_list_insert_chain( 192 void **begin, 193 void **end, 194 ptrdiff_t loc_prev, 195 ptrdiff_t loc_next, 196 void *node, 197 void *insert_begin, 198 void *insert_end 199 ) { 200 // find the end of the chain, if not specified 201 if (insert_end == NULL) { 202 insert_end = cx_linked_list_last(insert_begin, loc_next); 203 } 204 205 // determine the successor 206 void *successor; 207 if (node == NULL) { 208 assert(begin != NULL || (end != NULL && loc_prev >= 0)); 209 if (begin != NULL) { 210 successor = *begin; 211 *begin = insert_begin; 212 } else { 213 successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev); 214 } 215 } else { 216 successor = ll_next(node); 217 cx_linked_list_link(node, insert_begin, loc_prev, loc_next); 218 } 219 220 if (successor == NULL) { 221 // the list ends with the new chain 222 if (end != NULL) { 223 *end = insert_end; 224 } 225 } else { 226 cx_linked_list_link(insert_end, successor, loc_prev, loc_next); 227 } 228 } 229 230 void cx_linked_list_remove( 231 void **begin, 232 void **end, 233 ptrdiff_t loc_prev, 234 ptrdiff_t loc_next, 235 void *node 236 ) { 237 assert(node != NULL); 238 assert(loc_next >= 0); 239 assert(loc_prev >= 0 || begin != NULL); 240 241 // find adjacent nodes 242 void *next = ll_next(node); 243 void *prev; 244 if (loc_prev >= 0) { 245 prev = ll_prev(node); 246 } else { 247 prev = cx_linked_list_prev(*begin, loc_next, node); 248 } 249 250 // update next pointer of prev node, or set begin 251 if (prev == NULL) { 252 if (begin != NULL) { 253 *begin = next; 254 } 255 } else { 256 ll_next(prev) = next; 257 } 258 259 // update prev pointer of next node, or set end 260 if (next == NULL) { 261 if (end != NULL) { 262 *end = prev; 263 } 264 } else if (loc_prev >= 0) { 265 ll_prev(next) = prev; 266 } 267 } 268 269 size_t cx_linked_list_size( 270 void const *node, 271 ptrdiff_t loc_next 272 ) { 273 assert(loc_next >= 0); 274 size_t size = 0; 275 while (node != NULL) { 276 node = ll_next(node); 277 size++; 278 } 279 return size; 280 } 281 282 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE 283 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024 284 #endif 285 286 static void cx_linked_list_sort_merge( 287 ptrdiff_t loc_prev, 288 ptrdiff_t loc_next, 289 ptrdiff_t loc_data, 290 size_t length, 291 void *ls, 292 void *le, 293 void *re, 294 cx_compare_func cmp_func, 295 void **begin, 296 void **end 297 ) { 298 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; 299 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? 300 malloc(sizeof(void *) * length) : sbo; 301 if (sorted == NULL) abort(); 302 void *rc, *lc; 303 304 lc = ls; 305 rc = le; 306 size_t n = 0; 307 while (lc && lc != le && rc != re) { 308 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) { 309 sorted[n] = lc; 310 lc = ll_next(lc); 311 } else { 312 sorted[n] = rc; 313 rc = ll_next(rc); 314 } 315 n++; 316 } 317 while (lc && lc != le) { 318 sorted[n] = lc; 319 lc = ll_next(lc); 320 n++; 321 } 322 while (rc && rc != re) { 323 sorted[n] = rc; 324 rc = ll_next(rc); 325 n++; 326 } 327 328 // Update pointer 329 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL; 330 cx_for_n (i, length - 1) { 331 cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next); 332 } 333 ll_next(sorted[length - 1]) = NULL; 334 335 *begin = sorted[0]; 336 *end = sorted[length-1]; 337 if (sorted != sbo) { 338 free(sorted); 339 } 340 } 341 342 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function 343 void **begin, 344 void **end, 345 ptrdiff_t loc_prev, 346 ptrdiff_t loc_next, 347 ptrdiff_t loc_data, 348 cx_compare_func cmp_func 349 ) { 350 assert(begin != NULL); 351 assert(loc_next >= 0); 352 assert(loc_data >= 0); 353 assert(cmp_func); 354 355 void *lc, *ls, *le, *re; 356 357 // set start node 358 ls = *begin; 359 360 // early exit when this list is empty 361 if (ls == NULL) return; 362 363 // check how many elements are already sorted 364 lc = ls; 365 size_t ln = 1; 366 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) { 367 lc = ll_next(lc); 368 ln++; 369 } 370 le = ll_next(lc); 371 372 // if first unsorted node is NULL, the list is already completely sorted 373 if (le != NULL) { 374 void *rc; 375 size_t rn = 1; 376 rc = le; 377 // skip already sorted elements 378 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) { 379 rc = ll_next(rc); 380 rn++; 381 } 382 re = ll_next(rc); 383 384 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them 385 void *sorted_begin, *sorted_end; 386 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, 387 ln + rn, ls, le, re, cmp_func, 388 &sorted_begin, &sorted_end); 389 390 // Something left? Sort it! 391 size_t remainder_length = cx_linked_list_size(re, loc_next); 392 if (remainder_length > 0) { 393 void *remainder = re; 394 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func); 395 396 // merge sorted list with (also sorted) remainder 397 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, 398 ln + rn + remainder_length, 399 sorted_begin, remainder, NULL, cmp_func, 400 &sorted_begin, &sorted_end); 401 } 402 *begin = sorted_begin; 403 if (end) *end = sorted_end; 404 } 405 } 406 407 int cx_linked_list_compare( 408 void const *begin_left, 409 void const *begin_right, 410 ptrdiff_t loc_advance, 411 ptrdiff_t loc_data, 412 cx_compare_func cmp_func 413 ) { 414 void const *left = begin_left, *right = begin_right; 415 416 while (left != NULL && right != NULL) { 417 void const *left_data = ll_data(left); 418 void const *right_data = ll_data(right); 419 int result = cmp_func(left_data, right_data); 420 if (result != 0) return result; 421 left = ll_advance(left); 422 right = ll_advance(right); 423 } 424 425 if (left != NULL) { return 1; } 426 else if (right != NULL) { return -1; } 427 else { return 0; } 428 } 429 430 void cx_linked_list_reverse( 431 void **begin, 432 void **end, 433 ptrdiff_t loc_prev, 434 ptrdiff_t loc_next 435 ) { 436 assert(begin != NULL); 437 assert(loc_next >= 0); 438 439 // swap all links 440 void *prev = NULL; 441 void *cur = *begin; 442 while (cur != NULL) { 443 void *next = ll_next(cur); 444 445 ll_next(cur) = prev; 446 if (loc_prev >= 0) { 447 ll_prev(cur) = next; 448 } 449 450 prev = cur; 451 cur = next; 452 } 453 454 // update begin and end 455 if (end != NULL) { 456 *end = *begin; 457 } 458 *begin = prev; 459 } 460 461 // HIGH LEVEL LINKED LIST IMPLEMENTATION 462 463 bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false; 464 465 typedef struct cx_linked_list_node cx_linked_list_node; 466 struct cx_linked_list_node { 467 cx_linked_list_node *prev; 468 cx_linked_list_node *next; 469 char payload[]; 470 }; 471 472 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev) 473 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next) 474 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload) 475 476 typedef struct { 477 struct cx_list_s base; 478 cx_linked_list_node *begin; 479 cx_linked_list_node *end; 480 } cx_linked_list; 481 482 static cx_linked_list_node *cx_ll_node_at( 483 cx_linked_list const *list, 484 size_t index 485 ) { 486 if (index >= list->base.size) { 487 return NULL; 488 } else if (index > list->base.size / 2) { 489 return cx_linked_list_at(list->end, list->base.size - 1, CX_LL_LOC_PREV, index); 490 } else { 491 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); 492 } 493 } 494 495 static int cx_ll_insert_at( 496 struct cx_list_s *list, 497 cx_linked_list_node *node, 498 void const *elem 499 ) { 500 501 // create the new new_node 502 cx_linked_list_node *new_node = cxMalloc(list->allocator, 503 sizeof(cx_linked_list_node) + list->item_size); 504 505 // sortir if failed 506 if (new_node == NULL) return 1; 507 508 // initialize new new_node 509 new_node->prev = new_node->next = NULL; 510 memcpy(new_node->payload, elem, list->item_size); 511 512 // insert 513 cx_linked_list *ll = (cx_linked_list *) list; 514 cx_linked_list_insert_chain( 515 (void **) &ll->begin, (void **) &ll->end, 516 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, 517 node, new_node, new_node 518 ); 519 520 // increase the size and return 521 list->size++; 522 return 0; 523 } 524 525 static size_t cx_ll_insert_array( 526 struct cx_list_s *list, 527 size_t index, 528 void const *array, 529 size_t n 530 ) { 531 // out-of bounds and corner case check 532 if (index > list->size || n == 0) return 0; 533 534 // find position efficiently 535 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); 536 537 // perform first insert 538 if (0 != cx_ll_insert_at(list, node, array)) { 539 return 1; 540 } 541 542 // is there more? 543 if (n == 1) return 1; 544 545 // we now know exactly where we are 546 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next; 547 548 // we can add the remaining nodes and immedately advance to the inserted node 549 char const *source = array; 550 for (size_t i = 1; i < n; i++) { 551 source += list->item_size; 552 if (0 != cx_ll_insert_at(list, node, source)) { 553 return i; 554 } 555 node = node->next; 556 } 557 return n; 558 } 559 560 static int cx_ll_insert_element( 561 struct cx_list_s *list, 562 size_t index, 563 void const *element 564 ) { 565 return 1 != cx_ll_insert_array(list, index, element, 1); 566 } 567 568 static int cx_ll_remove( 569 struct cx_list_s *list, 570 size_t index 571 ) { 572 cx_linked_list *ll = (cx_linked_list *) list; 573 cx_linked_list_node *node = cx_ll_node_at(ll, index); 574 575 // out-of-bounds check 576 if (node == NULL) return 1; 577 578 // element destruction 579 cx_invoke_destructor(list, node->payload); 580 581 // remove 582 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 583 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 584 585 // adjust size 586 list->size--; 587 588 // free and return 589 cxFree(list->allocator, node); 590 591 return 0; 592 } 593 594 static void cx_ll_clear(struct cx_list_s *list) { 595 if (list->size == 0) return; 596 597 cx_linked_list *ll = (cx_linked_list *) list; 598 cx_linked_list_node *node = ll->begin; 599 while (node != NULL) { 600 cx_invoke_destructor(list, node->payload); 601 cx_linked_list_node *next = node->next; 602 cxFree(list->allocator, node); 603 node = next; 604 } 605 ll->begin = ll->end = NULL; 606 list->size = 0; 607 } 608 609 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE 610 #define CX_LINKED_LIST_SWAP_SBO_SIZE 128 611 #endif 612 613 static int cx_ll_swap( 614 struct cx_list_s *list, 615 size_t i, 616 size_t j 617 ) { 618 if (i >= list->size || j >= list->size) return 1; 619 if (i == j) return 0; 620 621 // perform an optimized search that finds both elements in one run 622 cx_linked_list *ll = (cx_linked_list *) list; 623 size_t mid = list->size / 2; 624 size_t left, right; 625 if (i < j) { 626 left = i; 627 right = j; 628 } else { 629 left = j; 630 right = i; 631 } 632 cx_linked_list_node *nleft, *nright; 633 if (left < mid && right < mid) { 634 // case 1: both items left from mid 635 nleft = cx_ll_node_at(ll, left); 636 nright = nleft; 637 for (size_t c = left; c < right; c++) { 638 nright = nright->next; 639 } 640 } else if (left >= mid && right >= mid) { 641 // case 2: both items right from mid 642 nright = cx_ll_node_at(ll, right); 643 nleft = nright; 644 for (size_t c = right; c > left; c--) { 645 nleft = nleft->prev; 646 } 647 } else { 648 // case 3: one item left, one item right 649 650 // chose the closest to begin / end 651 size_t closest; 652 size_t other; 653 size_t diff2boundary = list->size - right - 1; 654 if (left <= diff2boundary) { 655 closest = left; 656 other = right; 657 nleft = cx_ll_node_at(ll, left); 658 } else { 659 closest = right; 660 other = left; 661 diff2boundary = left; 662 nright = cx_ll_node_at(ll, right); 663 } 664 665 // is other element closer to us or closer to boundary? 666 if (right - left <= diff2boundary) { 667 // search other element starting from already found element 668 if (closest == left) { 669 nright = nleft; 670 for (size_t c = left; c < right; c++) { 671 nright = nright->next; 672 } 673 } else { 674 nleft = nright; 675 for (size_t c = right; c > left; c--) { 676 nleft = nleft->prev; 677 } 678 } 679 } else { 680 // search other element starting at the boundary 681 if (closest == left) { 682 nright = cx_ll_node_at(ll, other); 683 } else { 684 nleft = cx_ll_node_at(ll, other); 685 } 686 } 687 } 688 689 if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) { 690 cx_linked_list_node *prev = nleft->prev; 691 cx_linked_list_node *next = nright->next; 692 cx_linked_list_node *midstart = nleft->next; 693 cx_linked_list_node *midend = nright->prev; 694 695 if (prev == NULL) { 696 ll->begin = nright; 697 } else { 698 prev->next = nright; 699 } 700 nright->prev = prev; 701 if (midstart == nright) { 702 // special case: both nodes are adjacent 703 nright->next = nleft; 704 nleft->prev = nright; 705 } else { 706 // likely case: a chain is between the two nodes 707 nright->next = midstart; 708 midstart->prev = nright; 709 midend->next = nleft; 710 nleft->prev = midend; 711 } 712 nleft->next = next; 713 if (next == NULL) { 714 ll->end = nleft; 715 } else { 716 next->prev = nleft; 717 } 718 } else { 719 // swap payloads to avoid relinking 720 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE]; 721 memcpy(buf, nleft->payload, list->item_size); 722 memcpy(nleft->payload, nright->payload, list->item_size); 723 memcpy(nright->payload, buf, list->item_size); 724 } 725 726 return 0; 727 } 728 729 static void *cx_ll_at( 730 struct cx_list_s const *list, 731 size_t index 732 ) { 733 cx_linked_list *ll = (cx_linked_list *) list; 734 cx_linked_list_node *node = cx_ll_node_at(ll, index); 735 return node == NULL ? NULL : node->payload; 736 } 737 738 static ssize_t cx_ll_find( 739 struct cx_list_s const *list, 740 void const *elem 741 ) { 742 return cx_linked_list_find(((cx_linked_list *) list)->begin, 743 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 744 list->cmpfunc, elem); 745 } 746 747 static void cx_ll_sort(struct cx_list_s *list) { 748 cx_linked_list *ll = (cx_linked_list *) list; 749 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, 750 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 751 list->cmpfunc); 752 } 753 754 static void cx_ll_reverse(struct cx_list_s *list) { 755 cx_linked_list *ll = (cx_linked_list *) list; 756 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT); 757 } 758 759 static int cx_ll_compare( 760 struct cx_list_s const *list, 761 struct cx_list_s const *other 762 ) { 763 cx_linked_list *left = (cx_linked_list *) list; 764 cx_linked_list *right = (cx_linked_list *) other; 765 return cx_linked_list_compare(left->begin, right->begin, 766 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 767 list->cmpfunc); 768 } 769 770 static bool cx_ll_iter_valid(void const *it) { 771 struct cx_iterator_s const *iter = it; 772 return iter->elem_handle != NULL; 773 } 774 775 static void cx_ll_iter_next(void *it) { 776 struct cx_iterator_base_s *itbase = it; 777 if (itbase->remove) { 778 itbase->remove = false; 779 struct cx_mut_iterator_s *iter = it; 780 struct cx_list_s *list = iter->src_handle; 781 cx_linked_list *ll = iter->src_handle; 782 cx_linked_list_node *node = iter->elem_handle; 783 iter->elem_handle = node->next; 784 cx_invoke_destructor(list, node->payload); 785 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 786 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 787 list->size--; 788 cxFree(list->allocator, node); 789 } else { 790 struct cx_iterator_s *iter = it; 791 iter->index++; 792 cx_linked_list_node *node = iter->elem_handle; 793 iter->elem_handle = node->next; 794 } 795 } 796 797 static void cx_ll_iter_prev(void *it) { 798 struct cx_iterator_base_s *itbase = it; 799 if (itbase->remove) { 800 itbase->remove = false; 801 struct cx_mut_iterator_s *iter = it; 802 struct cx_list_s *list = iter->src_handle; 803 cx_linked_list *ll = iter->src_handle; 804 cx_linked_list_node *node = iter->elem_handle; 805 iter->elem_handle = node->prev; 806 iter->index--; 807 cx_invoke_destructor(list, node->payload); 808 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 809 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 810 list->size--; 811 cxFree(list->allocator, node); 812 } else { 813 struct cx_iterator_s *iter = it; 814 iter->index--; 815 cx_linked_list_node *node = iter->elem_handle; 816 iter->elem_handle = node->prev; 817 } 818 } 819 820 static void *cx_ll_iter_current(void const *it) { 821 struct cx_iterator_s const *iter = it; 822 cx_linked_list_node *node = iter->elem_handle; 823 return node->payload; 824 } 825 826 static bool cx_ll_iter_flag_rm(void *it) { 827 struct cx_iterator_base_s *iter = it; 828 if (iter->mutating) { 829 iter->remove = true; 830 return true; 831 } else { 832 return false; 833 } 834 } 835 836 static CxIterator cx_ll_iterator( 837 struct cx_list_s const *list, 838 size_t index, 839 bool backwards 840 ) { 841 CxIterator iter; 842 iter.index = index; 843 iter.src_handle = list; 844 iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); 845 iter.base.valid = cx_ll_iter_valid; 846 iter.base.current = cx_ll_iter_current; 847 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; 848 iter.base.flag_removal = cx_ll_iter_flag_rm; 849 iter.base.mutating = false; 850 iter.base.remove = false; 851 return iter; 852 } 853 854 static int cx_ll_insert_iter( 855 CxMutIterator *iter, 856 void const *elem, 857 int prepend 858 ) { 859 struct cx_list_s *list = iter->src_handle; 860 cx_linked_list_node *node = iter->elem_handle; 861 if (node != NULL) { 862 assert(prepend >= 0 && prepend <= 1); 863 cx_linked_list_node *choice[2] = {node, node->prev}; 864 int result = cx_ll_insert_at(list, choice[prepend], elem); 865 iter->index += prepend * (0 == result); 866 return result; 867 } else { 868 int result = cx_ll_insert_element(list, list->size, elem); 869 iter->index = list->size; 870 return result; 871 } 872 } 873 874 static void cx_ll_destructor(CxList *list) { 875 cx_linked_list *ll = (cx_linked_list *) list; 876 877 cx_linked_list_node *node = ll->begin; 878 while (node) { 879 cx_invoke_destructor(list, node->payload); 880 void *next = node->next; 881 cxFree(list->allocator, node); 882 node = next; 883 } 884 885 cxFree(list->allocator, list); 886 } 887 888 static cx_list_class cx_linked_list_class = { 889 cx_ll_destructor, 890 cx_ll_insert_element, 891 cx_ll_insert_array, 892 cx_ll_insert_iter, 893 cx_ll_remove, 894 cx_ll_clear, 895 cx_ll_swap, 896 cx_ll_at, 897 cx_ll_find, 898 cx_ll_sort, 899 cx_ll_compare, 900 cx_ll_reverse, 901 cx_ll_iterator, 902 }; 903 904 CxList *cxLinkedListCreate( 905 CxAllocator const *allocator, 906 cx_compare_func comparator, 907 size_t item_size 908 ) { 909 if (allocator == NULL) { 910 allocator = cxDefaultAllocator; 911 } 912 913 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); 914 if (list == NULL) return NULL; 915 916 list->base.cl = &cx_linked_list_class; 917 list->base.allocator = allocator; 918 list->base.cmpfunc = comparator; 919 920 if (item_size > 0) { 921 list->base.item_size = item_size; 922 } else { 923 cxListStorePointers((CxList *) list); 924 } 925 926 return (CxList *) list; 927 } 928