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/compare.h" 31 #include <string.h> 32 #include <assert.h> 33 34 #if __STDC_VERSION__ < 202311L 35 // we cannot simply include stdalign.h 36 // because Solaris is not entirely C11 complaint 37 #ifndef __alignof_is_defined 38 #define alignof _Alignof 39 #define __alignof_is_defined 1 40 #endif 41 #endif 42 43 // LOW LEVEL LINKED LIST FUNCTIONS 44 45 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) 46 #define ll_prev(node) CX_LL_PTR(node, loc_prev) 47 #define ll_next(node) CX_LL_PTR(node, loc_next) 48 #define ll_advance(node) CX_LL_PTR(node, loc_advance) 49 #define ll_data(node) (((char*)(node))+loc_data) 50 51 void *cx_linked_list_at( 52 const void *start, 53 size_t start_index, 54 ptrdiff_t loc_advance, 55 size_t index 56 ) { 57 assert(start != NULL); 58 assert(loc_advance >= 0); 59 size_t i = start_index; 60 const void *cur = start; 61 while (i != index && cur != NULL) { 62 cur = ll_advance(cur); 63 i < index ? i++ : i--; 64 } 65 return (void *) cur; 66 } 67 68 void *cx_linked_list_find( 69 const void *start, 70 ptrdiff_t loc_advance, 71 ptrdiff_t loc_data, 72 cx_compare_func cmp_func, 73 const void *elem, 74 size_t *found_index 75 ) { 76 assert(start != NULL); 77 assert(loc_advance >= 0); 78 assert(loc_data >= 0); 79 assert(cmp_func); 80 81 void *node = (void*) start; 82 size_t index = 0; 83 do { 84 void *current = ll_data(node); 85 if (cmp_func(current, elem) == 0) { 86 if (found_index != NULL) { 87 *found_index = index; 88 } 89 return node; 90 } 91 node = ll_advance(node); 92 index++; 93 } while (node != NULL); 94 return NULL; 95 } 96 97 void *cx_linked_list_first( 98 const void *node, 99 ptrdiff_t loc_prev 100 ) { 101 return cx_linked_list_last(node, loc_prev); 102 } 103 104 void *cx_linked_list_last( 105 const void *node, 106 ptrdiff_t loc_next 107 ) { 108 assert(node != NULL); 109 assert(loc_next >= 0); 110 111 const void *cur = node; 112 const void *last; 113 do { 114 last = cur; 115 } while ((cur = ll_next(cur)) != NULL); 116 117 return (void *) last; 118 } 119 120 void *cx_linked_list_prev( 121 const void *begin, 122 ptrdiff_t loc_next, 123 const void *node 124 ) { 125 assert(begin != NULL); 126 assert(node != NULL); 127 assert(loc_next >= 0); 128 if (begin == node) return NULL; 129 const void *cur = begin; 130 const void *next; 131 while (1) { 132 next = ll_next(cur); 133 if (next == node) return (void *) cur; 134 cur = next; 135 } 136 } 137 138 void cx_linked_list_link( 139 void *left, 140 void *right, 141 ptrdiff_t loc_prev, 142 ptrdiff_t loc_next 143 ) { 144 assert(loc_next >= 0); 145 ll_next(left) = right; 146 if (loc_prev >= 0) { 147 ll_prev(right) = left; 148 } 149 } 150 151 void cx_linked_list_unlink( 152 void *left, 153 void *right, 154 ptrdiff_t loc_prev, 155 ptrdiff_t loc_next 156 ) { 157 assert (loc_next >= 0); 158 assert(ll_next(left) == right); 159 ll_next(left) = NULL; 160 if (loc_prev >= 0) { 161 assert(ll_prev(right) == left); 162 ll_prev(right) = NULL; 163 } 164 } 165 166 void cx_linked_list_add( 167 void **begin, 168 void **end, 169 ptrdiff_t loc_prev, 170 ptrdiff_t loc_next, 171 void *new_node 172 ) { 173 void *last; 174 if (end == NULL) { 175 assert(begin != NULL); 176 last = *begin == NULL ? NULL : cx_linked_list_last(*begin, loc_next); 177 } else { 178 last = *end; 179 } 180 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, last, new_node, new_node); 181 } 182 183 void cx_linked_list_prepend( 184 void **begin, 185 void **end, 186 ptrdiff_t loc_prev, 187 ptrdiff_t loc_next, 188 void *new_node 189 ) { 190 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, NULL, new_node, new_node); 191 } 192 193 void cx_linked_list_insert( 194 void **begin, 195 void **end, 196 ptrdiff_t loc_prev, 197 ptrdiff_t loc_next, 198 void *node, 199 void *new_node 200 ) { 201 cx_linked_list_insert_chain(begin, end, loc_prev, loc_next, node, new_node, new_node); 202 } 203 204 void cx_linked_list_insert_chain( 205 void **begin, 206 void **end, 207 ptrdiff_t loc_prev, 208 ptrdiff_t loc_next, 209 void *node, 210 void *insert_begin, 211 void *insert_end 212 ) { 213 // find the end of the chain, if not specified 214 if (insert_end == NULL) { 215 insert_end = cx_linked_list_last(insert_begin, loc_next); 216 } 217 218 // determine the successor 219 void *successor; 220 if (node == NULL) { 221 assert(begin != NULL || (end != NULL && loc_prev >= 0)); 222 if (begin != NULL) { 223 successor = *begin; 224 *begin = insert_begin; 225 } else { 226 successor = *end == NULL ? NULL : cx_linked_list_first(*end, loc_prev); 227 } 228 } else { 229 successor = ll_next(node); 230 cx_linked_list_link(node, insert_begin, loc_prev, loc_next); 231 } 232 233 if (successor == NULL) { 234 // the list ends with the new chain 235 if (end != NULL) { 236 *end = insert_end; 237 } 238 } else { 239 cx_linked_list_link(insert_end, successor, loc_prev, loc_next); 240 } 241 } 242 243 void cx_linked_list_insert_sorted( 244 void **begin, 245 void **end, 246 ptrdiff_t loc_prev, 247 ptrdiff_t loc_next, 248 void *new_node, 249 cx_compare_func cmp_func 250 ) { 251 assert(ll_next(new_node) == NULL); 252 cx_linked_list_insert_sorted_chain( 253 begin, end, loc_prev, loc_next, new_node, cmp_func); 254 } 255 256 static void *cx_linked_list_insert_sorted_chain_impl( 257 void **begin, 258 void **end, 259 ptrdiff_t loc_prev, 260 ptrdiff_t loc_next, 261 void *insert_begin, 262 cx_compare_func cmp_func, 263 bool allow_duplicates 264 ) { 265 assert(begin != NULL); 266 assert(loc_next >= 0); 267 assert(insert_begin != NULL); 268 269 // strategy: build completely new chains from scratch 270 void *source_original = *begin; 271 void *source_argument = insert_begin; 272 void *new_begin = NULL; 273 void *new_end = NULL; 274 void *dup_begin = NULL; 275 void *dup_end = NULL; 276 277 // determine the new start 278 { 279 int d = source_original == NULL ? 1 : cmp_func(source_original, source_argument); 280 if (d <= 0) { 281 // the new chain starts with the original chain 282 new_begin = new_end = source_original; 283 source_original = ll_next(source_original); 284 if (d == 0) { 285 if (allow_duplicates) { 286 // duplicate allowed, append it to the chain 287 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); 288 new_end = source_argument; 289 } else { 290 // duplicate is not allowed, start a duplicate chain with the argument 291 dup_begin = dup_end = source_argument; 292 } 293 source_argument = ll_next(source_argument); 294 } 295 } else { 296 // input is smaller, or there is no original chain; 297 // start the new chain with the source argument 298 new_begin = new_end = source_argument; 299 source_argument = ll_next(source_argument); 300 } 301 } 302 303 // now successively compare the elements and add them to the correct chains 304 while (source_original != NULL && source_argument != NULL) { 305 int d = cmp_func(source_original, source_argument); 306 if (d <= 0) { 307 // the original is not larger, add it to the chain 308 cx_linked_list_link(new_end, source_original, loc_prev, loc_next); 309 new_end = source_original; 310 source_original = ll_next(source_original); 311 if (d == 0) { 312 if (allow_duplicates) { 313 // duplicate allowed, append it to the chain 314 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); 315 new_end = source_argument; 316 } else { 317 // duplicate is not allowed, append it to the duplicate chain 318 if (dup_end == NULL) { 319 dup_begin = dup_end = source_argument; 320 } else { 321 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next); 322 dup_end = source_argument; 323 } 324 } 325 source_argument = ll_next(source_argument); 326 } 327 } else { 328 // the original is larger, append the source argument to the chain 329 // check if we must discard the source argument as duplicate 330 if (!allow_duplicates && cmp_func(new_end, source_argument) == 0) { 331 if (dup_end == NULL) { 332 dup_begin = dup_end = source_argument; 333 } else { 334 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next); 335 dup_end = source_argument; 336 } 337 } else { 338 // no duplicate or duplicates allowed 339 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); 340 new_end = source_argument; 341 } 342 source_argument = ll_next(source_argument); 343 } 344 } 345 346 if (source_original != NULL) { 347 // something is left from the original chain, append it 348 cx_linked_list_link(new_end, source_original, loc_prev, loc_next); 349 new_end = cx_linked_list_last(source_original, loc_next); 350 } else if (source_argument != NULL) { 351 // something is left from the input chain; 352 // when we allow duplicates, append it 353 if (allow_duplicates) { 354 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); 355 new_end = cx_linked_list_last(source_argument, loc_next); 356 } else { 357 // otherwise we must check one-by-one 358 while (source_argument != NULL) { 359 if (cmp_func(new_end, source_argument) == 0) { 360 if (dup_end == NULL) { 361 dup_begin = dup_end = source_argument; 362 } else { 363 cx_linked_list_link(dup_end, source_argument, loc_prev, loc_next); 364 dup_end = source_argument; 365 } 366 } else { 367 cx_linked_list_link(new_end, source_argument, loc_prev, loc_next); 368 new_end = source_argument; 369 } 370 source_argument = ll_next(source_argument); 371 } 372 } 373 } 374 375 // null the next pointers at the end of the chain 376 ll_next(new_end) = NULL; 377 if (dup_end != NULL) { 378 ll_next(dup_end) = NULL; 379 } 380 381 // null the optional prev pointers 382 if (loc_prev >= 0) { 383 ll_prev(new_begin) = NULL; 384 if (dup_begin != NULL) { 385 ll_prev(dup_begin) = NULL; 386 } 387 } 388 389 // output 390 *begin = new_begin; 391 if (end != NULL) { 392 *end = new_end; 393 } 394 return dup_begin; 395 } 396 397 void cx_linked_list_insert_sorted_chain( 398 void **begin, 399 void **end, 400 ptrdiff_t loc_prev, 401 ptrdiff_t loc_next, 402 void *insert_begin, 403 cx_compare_func cmp_func 404 ) { 405 cx_linked_list_insert_sorted_chain_impl( 406 begin, end, loc_prev, loc_next, 407 insert_begin, cmp_func, true); 408 } 409 410 int cx_linked_list_insert_unique( 411 void **begin, 412 void **end, 413 ptrdiff_t loc_prev, 414 ptrdiff_t loc_next, 415 void *new_node, 416 cx_compare_func cmp_func 417 ) { 418 assert(ll_next(new_node) == NULL); 419 return NULL != cx_linked_list_insert_unique_chain( 420 begin, end, loc_prev, loc_next, new_node, cmp_func); 421 } 422 423 void *cx_linked_list_insert_unique_chain( 424 void **begin, 425 void **end, 426 ptrdiff_t loc_prev, 427 ptrdiff_t loc_next, 428 void *insert_begin, 429 cx_compare_func cmp_func 430 ) { 431 return cx_linked_list_insert_sorted_chain_impl( 432 begin, end, loc_prev, loc_next, 433 insert_begin, cmp_func, false); 434 } 435 436 size_t cx_linked_list_remove_chain( 437 void **begin, 438 void **end, 439 ptrdiff_t loc_prev, 440 ptrdiff_t loc_next, 441 void *node, 442 size_t num 443 ) { 444 assert(node != NULL); 445 assert(loc_next >= 0); 446 assert(loc_prev >= 0 || begin != NULL); 447 448 // easy exit 449 if (num == 0) return 0; 450 451 // find adjacent nodes 452 void *prev; 453 if (loc_prev >= 0) { 454 prev = ll_prev(node); 455 } else { 456 prev = cx_linked_list_prev(*begin, loc_next, node); 457 } 458 459 void *next = ll_next(node); 460 size_t removed = 1; 461 for (; removed < num && next != NULL ; removed++) { 462 next = ll_next(next); 463 } 464 465 // update next pointer of prev node, or set begin 466 if (prev == NULL) { 467 if (begin != NULL) { 468 *begin = next; 469 } 470 } else { 471 ll_next(prev) = next; 472 } 473 474 // update prev pointer of next node, or set end 475 if (next == NULL) { 476 if (end != NULL) { 477 *end = prev; 478 } 479 } else if (loc_prev >= 0) { 480 ll_prev(next) = prev; 481 } 482 483 return removed; 484 } 485 486 void cx_linked_list_remove( 487 void **begin, 488 void **end, 489 ptrdiff_t loc_prev, 490 ptrdiff_t loc_next, 491 void *node 492 ) { 493 cx_linked_list_remove_chain(begin, end, loc_prev, loc_next, node, 1); 494 } 495 496 size_t cx_linked_list_size( 497 const void *node, 498 ptrdiff_t loc_next 499 ) { 500 assert(loc_next >= 0); 501 size_t size = 0; 502 while (node != NULL) { 503 node = ll_next(node); 504 size++; 505 } 506 return size; 507 } 508 509 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE 510 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024 511 #endif 512 513 static void cx_linked_list_sort_merge( 514 ptrdiff_t loc_prev, 515 ptrdiff_t loc_next, 516 ptrdiff_t loc_data, 517 size_t length, 518 void *ls, 519 void *le, 520 void *re, 521 cx_compare_func cmp_func, 522 void **begin, 523 void **end 524 ) { 525 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE]; 526 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ? 527 cxMallocDefault(sizeof(void *) * length) : sbo; 528 if (sorted == NULL) abort(); // LCOV_EXCL_LINE 529 void *rc, *lc; 530 531 lc = ls; 532 rc = le; 533 size_t n = 0; 534 while (lc && lc != le && rc != re) { 535 if (cmp_func(ll_data(lc), ll_data(rc)) <= 0) { 536 sorted[n] = lc; 537 lc = ll_next(lc); 538 } else { 539 sorted[n] = rc; 540 rc = ll_next(rc); 541 } 542 n++; 543 } 544 while (lc && lc != le) { 545 sorted[n] = lc; 546 lc = ll_next(lc); 547 n++; 548 } 549 while (rc && rc != re) { 550 sorted[n] = rc; 551 rc = ll_next(rc); 552 n++; 553 } 554 555 // Update pointer 556 if (loc_prev >= 0) ll_prev(sorted[0]) = NULL; 557 for (size_t i = 0 ; i < length - 1; i++) { 558 cx_linked_list_link(sorted[i], sorted[i + 1], loc_prev, loc_next); 559 } 560 ll_next(sorted[length - 1]) = NULL; 561 562 *begin = sorted[0]; 563 *end = sorted[length - 1]; 564 if (sorted != sbo) { 565 cxFreeDefault(sorted); 566 } 567 } 568 569 void cx_linked_list_sort( // NOLINT(misc-no-recursion) - purposely recursive function 570 void **begin, 571 void **end, 572 ptrdiff_t loc_prev, 573 ptrdiff_t loc_next, 574 ptrdiff_t loc_data, 575 cx_compare_func cmp_func 576 ) { 577 assert(begin != NULL); 578 assert(loc_next >= 0); 579 assert(loc_data >= 0); 580 assert(cmp_func); 581 582 void *lc, *ls, *le, *re; 583 584 // set start node 585 ls = *begin; 586 587 // early exit when this list is empty 588 if (ls == NULL) return; 589 590 // check how many elements are already sorted 591 lc = ls; 592 size_t ln = 1; 593 while (ll_next(lc) != NULL && cmp_func(ll_data(ll_next(lc)), ll_data(lc)) > 0) { 594 lc = ll_next(lc); 595 ln++; 596 } 597 le = ll_next(lc); 598 599 // if first unsorted node is NULL, the list is already completely sorted 600 if (le != NULL) { 601 void *rc; 602 size_t rn = 1; 603 rc = le; 604 // skip already sorted elements 605 while (ll_next(rc) != NULL && cmp_func(ll_data(ll_next(rc)), ll_data(rc)) > 0) { 606 rc = ll_next(rc); 607 rn++; 608 } 609 re = ll_next(rc); 610 611 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them 612 void *sorted_begin, *sorted_end; 613 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, 614 ln + rn, ls, le, re, cmp_func, 615 &sorted_begin, &sorted_end); 616 617 // Something left? Sort it! 618 size_t remainder_length = cx_linked_list_size(re, loc_next); 619 if (remainder_length > 0) { 620 void *remainder = re; 621 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func); 622 623 // merge sorted list with (also sorted) remainder 624 cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, 625 ln + rn + remainder_length, 626 sorted_begin, remainder, NULL, cmp_func, 627 &sorted_begin, &sorted_end); 628 } 629 *begin = sorted_begin; 630 if (end) *end = sorted_end; 631 } 632 } 633 634 int cx_linked_list_compare( 635 const void *begin_left, 636 const void *begin_right, 637 ptrdiff_t loc_advance, 638 ptrdiff_t loc_data, 639 cx_compare_func cmp_func 640 ) { 641 const void *left = begin_left, *right = begin_right; 642 643 while (left != NULL && right != NULL) { 644 const void *left_data = ll_data(left); 645 const void *right_data = ll_data(right); 646 int result = cmp_func(left_data, right_data); 647 if (result != 0) return result; 648 left = ll_advance(left); 649 right = ll_advance(right); 650 } 651 652 if (left != NULL) { return 1; } 653 else if (right != NULL) { return -1; } 654 else { return 0; } 655 } 656 657 void cx_linked_list_reverse( 658 void **begin, 659 void **end, 660 ptrdiff_t loc_prev, 661 ptrdiff_t loc_next 662 ) { 663 assert(begin != NULL); 664 assert(loc_next >= 0); 665 666 // swap all links 667 void *prev = NULL; 668 void *cur = *begin; 669 while (cur != NULL) { 670 void *next = ll_next(cur); 671 672 ll_next(cur) = prev; 673 if (loc_prev >= 0) { 674 ll_prev(cur) = next; 675 } 676 677 prev = cur; 678 cur = next; 679 } 680 681 // update begin and end 682 if (end != NULL) { 683 *end = *begin; 684 } 685 *begin = prev; 686 } 687 688 // HIGH LEVEL LINKED LIST IMPLEMENTATION 689 690 static void *cx_ll_node_at( 691 const cx_linked_list *list, 692 size_t index 693 ) { 694 if (index >= list->base.collection.size) { 695 return NULL; 696 } else if (index > list->base.collection.size / 2) { 697 return cx_linked_list_at(list->end, list->base.collection.size - 1, list->loc_prev, index); 698 } else { 699 return cx_linked_list_at(list->begin, 0, list->loc_next, index); 700 } 701 } 702 703 static void *cx_ll_malloc_node(const cx_linked_list *list) { 704 size_t n; 705 if (list->extra_data_len == 0) { 706 n = list->loc_data + list->base.collection.elem_size; 707 } else { 708 n = list->loc_extra + list->extra_data_len; 709 } 710 return cxZalloc(list->base.collection.allocator, n); 711 } 712 713 static int cx_ll_insert_at( 714 struct cx_list_s *list, 715 void *node, 716 const void *elem 717 ) { 718 cx_linked_list *ll = (cx_linked_list *) list; 719 720 // create the new new_node 721 void *new_node = cx_ll_malloc_node(ll); 722 723 // sortir if failed 724 if (new_node == NULL) return 1; 725 726 // copy the data 727 if (elem != NULL) { 728 memcpy((char*)new_node + ll->loc_data, elem, list->collection.elem_size); 729 } 730 731 // insert 732 cx_linked_list_insert_chain( 733 &ll->begin, &ll->end, 734 ll->loc_prev, ll->loc_next, 735 node, new_node, new_node 736 ); 737 738 // increase the size and return 739 list->collection.size++; 740 return 0; 741 } 742 743 static size_t cx_ll_insert_array( 744 struct cx_list_s *list, 745 size_t index, 746 const void *array, 747 size_t n 748 ) { 749 // out-of bounds and corner case check 750 if (index > list->collection.size || n == 0) return 0; 751 752 // find position efficiently 753 void *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); 754 755 // perform first insert 756 if (0 != cx_ll_insert_at(list, node, array)) return 1; 757 758 // is there more? 759 if (n == 1) return 1; 760 761 // we now know exactly where we are 762 cx_linked_list *ll = (cx_linked_list *) list; 763 node = node == NULL ? ((cx_linked_list *) list)->begin : CX_LL_PTR(node, ll->loc_next); 764 765 // we can add the remaining nodes and immediately advance to the inserted node 766 const char *source = array; 767 for (size_t i = 1; i < n; i++) { 768 if (source != NULL) { 769 source += list->collection.elem_size; 770 } 771 if (0 != cx_ll_insert_at(list, node, source)) return i; 772 node = CX_LL_PTR(node, ll->loc_next); 773 } 774 return n; 775 } 776 777 static void *cx_ll_insert_element( 778 struct cx_list_s *list, 779 size_t index, 780 const void *element 781 ) { 782 // out-of-bounds check 783 if (index > list->collection.size) return NULL; 784 785 // find position efficiently 786 void *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); 787 788 // perform first insert 789 if (cx_ll_insert_at(list, node, element)) return NULL; 790 791 // return a pointer to the data of the inserted node 792 cx_linked_list *ll = (cx_linked_list *) list; 793 if (node == NULL) { 794 return (char*)(ll->begin) + ll->loc_data; 795 } else { 796 char *next = CX_LL_PTR(node, ll->loc_next); 797 return next + ll->loc_data; 798 } 799 } 800 801 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func; 802 static _Thread_local off_t cx_ll_insert_sorted_loc_data; 803 804 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) { 805 const char *left = (const char*)l + cx_ll_insert_sorted_loc_data; 806 const char *right = (const char*)r + cx_ll_insert_sorted_loc_data; 807 return cx_ll_insert_sorted_cmp_func(left, right); 808 } 809 810 static size_t cx_ll_insert_sorted_impl( 811 struct cx_list_s *list, 812 const void *array, 813 size_t n, 814 bool allow_duplicates 815 ) { 816 cx_linked_list *ll = (cx_linked_list *) list; 817 818 // special case 819 if (n == 0) return 0; 820 821 // create a new chain of nodes 822 void *chain = cx_ll_malloc_node(ll); 823 if (chain == NULL) return 0; 824 825 memcpy((char*)chain + ll->loc_data, array, list->collection.elem_size); 826 827 // add all elements from the array to that chain 828 void *prev = chain; 829 const char *src = array; 830 size_t inserted = 1; 831 for (; inserted < n; inserted++) { 832 void *next = cx_ll_malloc_node(ll); 833 if (next == NULL) break; 834 src += list->collection.elem_size; 835 memcpy((char*)next + ll->loc_data, src, list->collection.elem_size); 836 CX_LL_PTR(prev, ll->loc_next) = next; 837 CX_LL_PTR(next, ll->loc_prev) = prev; 838 prev = next; 839 } 840 CX_LL_PTR(prev, ll->loc_next) = NULL; 841 842 // invoke the low level function 843 cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc; 844 cx_ll_insert_sorted_loc_data = ll->loc_data; 845 if (allow_duplicates) { 846 cx_linked_list_insert_sorted_chain( 847 &ll->begin, 848 &ll->end, 849 ll->loc_prev, 850 ll->loc_next, 851 chain, 852 cx_ll_insert_sorted_cmp_helper 853 ); 854 list->collection.size += inserted; 855 } else { 856 void *duplicates = cx_linked_list_insert_unique_chain( 857 &ll->begin, 858 &ll->end, 859 ll->loc_prev, 860 ll->loc_next, 861 chain, 862 cx_ll_insert_sorted_cmp_helper 863 ); 864 list->collection.size += inserted; 865 // free the nodes that did not make it into the list 866 while (duplicates != NULL) { 867 void *next = CX_LL_PTR(duplicates, ll->loc_next); 868 cxFree(list->collection.allocator, duplicates); 869 duplicates = next; 870 list->collection.size--; 871 } 872 } 873 874 return inserted; 875 } 876 877 static size_t cx_ll_insert_sorted( 878 struct cx_list_s *list, 879 const void *array, 880 size_t n 881 ) { 882 return cx_ll_insert_sorted_impl(list, array, n, true); 883 } 884 885 static size_t cx_ll_insert_unique( 886 struct cx_list_s *list, 887 const void *array, 888 size_t n 889 ) { 890 return cx_ll_insert_sorted_impl(list, array, n, false); 891 } 892 893 static size_t cx_ll_remove( 894 struct cx_list_s *list, 895 size_t index, 896 size_t num, 897 void *targetbuf 898 ) { 899 cx_linked_list *ll = (cx_linked_list *) list; 900 void *node = cx_ll_node_at(ll, index); 901 902 // out-of-bounds check 903 if (node == NULL) return 0; 904 905 // remove 906 size_t removed = cx_linked_list_remove_chain( 907 (void **) &ll->begin, 908 (void **) &ll->end, 909 ll->loc_prev, 910 ll->loc_next, 911 node, 912 num 913 ); 914 915 // adjust size 916 list->collection.size -= removed; 917 918 // copy or destroy the removed chain 919 if (targetbuf == NULL) { 920 char *n = node; 921 for (size_t i = 0; i < removed; i++) { 922 // element destruction 923 cx_invoke_destructor(list, n + ll->loc_data); 924 925 // free the node and advance 926 void *next = CX_LL_PTR(n, ll->loc_next); 927 cxFree(list->collection.allocator, n); 928 n = next; 929 } 930 } else { 931 char *dest = targetbuf; 932 char *n = node; 933 for (size_t i = 0; i < removed; i++) { 934 // copy payload 935 memcpy(dest, n + ll->loc_data, list->collection.elem_size); 936 937 // advance target buffer 938 dest += list->collection.elem_size; 939 940 // free the node and advance 941 void *next = CX_LL_PTR(n, ll->loc_next); 942 cxFree(list->collection.allocator, n); 943 n = next; 944 } 945 } 946 947 return removed; 948 } 949 950 static void cx_ll_clear(struct cx_list_s *list) { 951 if (list->collection.size == 0) return; 952 953 cx_linked_list *ll = (cx_linked_list *) list; 954 char *node = ll->begin; 955 while (node != NULL) { 956 cx_invoke_destructor(list, node + ll->loc_data); 957 void *next = CX_LL_PTR(node, ll->loc_next); 958 cxFree(list->collection.allocator, node); 959 node = next; 960 } 961 ll->begin = ll->end = NULL; 962 list->collection.size = 0; 963 } 964 965 static int cx_ll_swap( 966 struct cx_list_s *list, 967 size_t i, 968 size_t j 969 ) { 970 if (i >= list->collection.size || j >= list->collection.size) return 1; 971 if (i == j) return 0; 972 973 // perform an optimized search that finds both elements in one run 974 cx_linked_list *ll = (cx_linked_list *) list; 975 size_t mid = list->collection.size / 2; 976 size_t left, right; 977 if (i < j) { 978 left = i; 979 right = j; 980 } else { 981 left = j; 982 right = i; 983 } 984 void *nleft = NULL, *nright = NULL; 985 if (left < mid && right < mid) { 986 // case 1: both items left from mid 987 nleft = cx_ll_node_at(ll, left); 988 assert(nleft != NULL); 989 nright = nleft; 990 for (size_t c = left; c < right; c++) { 991 nright = CX_LL_PTR(nright, ll->loc_next); 992 } 993 } else if (left >= mid && right >= mid) { 994 // case 2: both items right from mid 995 nright = cx_ll_node_at(ll, right); 996 assert(nright != NULL); 997 nleft = nright; 998 for (size_t c = right; c > left; c--) { 999 nleft = CX_LL_PTR(nleft, ll->loc_prev); 1000 } 1001 } else { 1002 // case 3: one item left, one item right 1003 1004 // chose the closest to begin / end 1005 size_t closest; 1006 size_t other; 1007 size_t diff2boundary = list->collection.size - right - 1; 1008 if (left <= diff2boundary) { 1009 closest = left; 1010 other = right; 1011 nleft = cx_ll_node_at(ll, left); 1012 } else { 1013 closest = right; 1014 other = left; 1015 diff2boundary = left; 1016 nright = cx_ll_node_at(ll, right); 1017 } 1018 1019 // is other element closer to us or closer to boundary? 1020 if (right - left <= diff2boundary) { 1021 // search other element starting from already found element 1022 if (closest == left) { 1023 nright = nleft; 1024 for (size_t c = left; c < right; c++) { 1025 nright = CX_LL_PTR(nright, ll->loc_next); 1026 } 1027 } else { 1028 nleft = nright; 1029 for (size_t c = right; c > left; c--) { 1030 nleft = CX_LL_PTR(nleft, ll->loc_prev); 1031 } 1032 } 1033 } else { 1034 // search other element starting at the boundary 1035 if (closest == left) { 1036 nright = cx_ll_node_at(ll, other); 1037 } else { 1038 nleft = cx_ll_node_at(ll, other); 1039 } 1040 } 1041 } 1042 1043 void *prev = CX_LL_PTR(nleft, ll->loc_prev); 1044 void *next = CX_LL_PTR(nright, ll->loc_next); 1045 void *midstart = CX_LL_PTR(nleft, ll->loc_next); 1046 void *midend = CX_LL_PTR(nright, ll->loc_prev); 1047 1048 if (prev == NULL) { 1049 ll->begin = nright; 1050 } else { 1051 CX_LL_PTR(prev, ll->loc_next) = nright; 1052 } 1053 CX_LL_PTR(nright, ll->loc_prev) = prev; 1054 if (midstart == nright) { 1055 // special case: both nodes are adjacent 1056 CX_LL_PTR(nright, ll->loc_next) = nleft; 1057 CX_LL_PTR(nleft, ll->loc_prev) = nright; 1058 } else { 1059 // likely case: a chain is between the two nodes 1060 CX_LL_PTR(nright, ll->loc_next) = midstart; 1061 CX_LL_PTR(midstart, ll->loc_prev) = nright; 1062 CX_LL_PTR(midend, ll->loc_next) = nleft; 1063 CX_LL_PTR(nleft, ll->loc_prev) = midend; 1064 } 1065 CX_LL_PTR(nleft, ll->loc_next) = next; 1066 if (next == NULL) { 1067 ll->end = nleft; 1068 } else { 1069 CX_LL_PTR(next, ll->loc_prev) = nleft; 1070 } 1071 1072 return 0; 1073 } 1074 1075 static void *cx_ll_at( 1076 const struct cx_list_s *list, 1077 size_t index 1078 ) { 1079 cx_linked_list *ll = (cx_linked_list *) list; 1080 char *node = cx_ll_node_at(ll, index); 1081 return node == NULL ? NULL : node + ll->loc_data; 1082 } 1083 1084 static size_t cx_ll_find_remove( 1085 struct cx_list_s *list, 1086 const void *elem, 1087 bool remove 1088 ) { 1089 if (list->collection.size == 0) return 0; 1090 1091 size_t index; 1092 cx_linked_list *ll = (cx_linked_list *) list; 1093 char *node = cx_linked_list_find( 1094 ll->begin, 1095 ll->loc_next, ll->loc_data, 1096 list->collection.cmpfunc, elem, 1097 &index 1098 ); 1099 if (node == NULL) { 1100 return list->collection.size; 1101 } 1102 if (remove) { 1103 cx_invoke_destructor(list, node + ll->loc_data); 1104 cx_linked_list_remove(&ll->begin, &ll->end, 1105 ll->loc_prev, ll->loc_next, node); 1106 list->collection.size--; 1107 cxFree(list->collection.allocator, node); 1108 } 1109 return index; 1110 } 1111 1112 static void cx_ll_sort(struct cx_list_s *list) { 1113 cx_linked_list *ll = (cx_linked_list *) list; 1114 cx_linked_list_sort(&ll->begin, &ll->end, 1115 ll->loc_prev, ll->loc_next, ll->loc_data, 1116 list->collection.cmpfunc); 1117 } 1118 1119 static void cx_ll_reverse(struct cx_list_s *list) { 1120 cx_linked_list *ll = (cx_linked_list *) list; 1121 cx_linked_list_reverse(&ll->begin, &ll->end, ll->loc_prev, ll->loc_next); 1122 } 1123 1124 static int cx_ll_compare( 1125 const struct cx_list_s *list, 1126 const struct cx_list_s *other 1127 ) { 1128 cx_linked_list *left = (cx_linked_list *) list; 1129 cx_linked_list *right = (cx_linked_list *) other; 1130 assert(left->loc_next == right->loc_next); 1131 assert(left->loc_data == right->loc_data); 1132 return cx_linked_list_compare(left->begin, right->begin, 1133 left->loc_next, left->loc_data, 1134 list->collection.cmpfunc); 1135 } 1136 1137 static bool cx_ll_iter_valid(const void *it) { 1138 const struct cx_iterator_s *iter = it; 1139 return iter->elem_handle != NULL; 1140 } 1141 1142 static void cx_ll_iter_next(void *it) { 1143 struct cx_iterator_s *iter = it; 1144 cx_linked_list *ll = iter->src_handle; 1145 if (iter->base.remove) { 1146 iter->base.remove = false; 1147 struct cx_list_s *list = iter->src_handle; 1148 char *node = iter->elem_handle; 1149 iter->elem_handle = CX_LL_PTR(node, ll->loc_next); 1150 cx_invoke_destructor(list, node + ll->loc_data); 1151 cx_linked_list_remove(&ll->begin, &ll->end, 1152 ll->loc_prev, ll->loc_next, node); 1153 list->collection.size--; 1154 iter->elem_count--; 1155 cxFree(list->collection.allocator, node); 1156 } else { 1157 iter->index++; 1158 void *node = iter->elem_handle; 1159 iter->elem_handle = CX_LL_PTR(node, ll->loc_next); 1160 } 1161 } 1162 1163 static void cx_ll_iter_prev(void *it) { 1164 struct cx_iterator_s *iter = it; 1165 cx_linked_list *ll = iter->src_handle; 1166 if (iter->base.remove) { 1167 iter->base.remove = false; 1168 struct cx_list_s *list = iter->src_handle; 1169 char *node = iter->elem_handle; 1170 iter->elem_handle = CX_LL_PTR(node, ll->loc_prev); 1171 iter->index--; 1172 cx_invoke_destructor(list, node + ll->loc_data); 1173 cx_linked_list_remove(&ll->begin, &ll->end, 1174 ll->loc_prev, ll->loc_next, node); 1175 list->collection.size--; 1176 iter->elem_count--; 1177 cxFree(list->collection.allocator, node); 1178 } else { 1179 iter->index--; 1180 char *node = iter->elem_handle; 1181 iter->elem_handle = CX_LL_PTR(node, ll->loc_prev); 1182 } 1183 } 1184 1185 static void *cx_ll_iter_current(const void *it) { 1186 const struct cx_iterator_s *iter = it; 1187 const cx_linked_list *ll = iter->src_handle; 1188 char *node = iter->elem_handle; 1189 return node + ll->loc_data; 1190 } 1191 1192 static CxIterator cx_ll_iterator( 1193 const struct cx_list_s *list, 1194 size_t index, 1195 bool backwards 1196 ) { 1197 CxIterator iter; 1198 iter.index = index; 1199 iter.src_handle = (void*)list; 1200 iter.elem_handle = cx_ll_node_at((const cx_linked_list *) list, index); 1201 iter.elem_size = list->collection.elem_size; 1202 iter.elem_count = list->collection.size; 1203 iter.base.valid = cx_ll_iter_valid; 1204 iter.base.current = cx_ll_iter_current; 1205 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next; 1206 iter.base.allow_remove = true; 1207 iter.base.remove = false; 1208 return iter; 1209 } 1210 1211 static int cx_ll_insert_iter( 1212 CxIterator *iter, 1213 const void *elem, 1214 int prepend 1215 ) { 1216 struct cx_list_s *list = iter->src_handle; 1217 cx_linked_list *ll = iter->src_handle; 1218 void *node = iter->elem_handle; 1219 if (node != NULL) { 1220 assert(prepend >= 0 && prepend <= 1); 1221 void *choice[2] = {node, CX_LL_PTR(node, ll->loc_prev)}; 1222 int result = cx_ll_insert_at(list, choice[prepend], elem); 1223 if (result == 0) { 1224 iter->elem_count++; 1225 if (prepend) { 1226 iter->index++; 1227 } 1228 } 1229 return result; 1230 } else { 1231 if (cx_ll_insert_element(list, list->collection.size, elem) == NULL) { 1232 return 1; // LCOV_EXCL_LINE 1233 } 1234 iter->elem_count++; 1235 iter->index = list->collection.size; 1236 return 0; 1237 } 1238 } 1239 1240 static void cx_ll_destructor(CxList *list) { 1241 cx_linked_list *ll = (cx_linked_list *) list; 1242 1243 char *node = ll->begin; 1244 while (node) { 1245 cx_invoke_destructor(list, node + ll->loc_data); 1246 void *next = CX_LL_PTR(node, ll->loc_next); 1247 cxFree(list->collection.allocator, node); 1248 node = next; 1249 } 1250 1251 cxFree(list->collection.allocator, list); 1252 } 1253 1254 static cx_list_class cx_linked_list_class = { 1255 cx_ll_destructor, 1256 cx_ll_insert_element, 1257 cx_ll_insert_array, 1258 cx_ll_insert_sorted, 1259 cx_ll_insert_unique, 1260 cx_ll_insert_iter, 1261 cx_ll_remove, 1262 cx_ll_clear, 1263 cx_ll_swap, 1264 cx_ll_at, 1265 cx_ll_find_remove, 1266 cx_ll_sort, 1267 cx_ll_compare, 1268 cx_ll_reverse, 1269 NULL, // no overallocation supported 1270 cx_ll_iterator, 1271 }; 1272 1273 CxList *cxLinkedListCreate( 1274 const CxAllocator *allocator, 1275 cx_compare_func comparator, 1276 size_t elem_size 1277 ) { 1278 if (allocator == NULL) { 1279 allocator = cxDefaultAllocator; 1280 } 1281 1282 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); 1283 if (list == NULL) return NULL; 1284 list->loc_prev = 0; 1285 list->loc_next = sizeof(void*); 1286 list->loc_data = sizeof(void*)*2; 1287 list->loc_extra = -1; 1288 list->extra_data_len = 0; 1289 cx_list_init((CxList*)list, &cx_linked_list_class, 1290 allocator, comparator, elem_size); 1291 1292 return (CxList *) list; 1293 } 1294 1295 void cx_linked_list_extra_data(cx_linked_list *list, size_t len) { 1296 list->extra_data_len = len; 1297 1298 off_t loc_extra = list->loc_data + list->base.collection.elem_size; 1299 size_t alignment = alignof(void*); 1300 size_t padding = alignment - (loc_extra % alignment); 1301 list->loc_extra = loc_extra + padding; 1302 } 1303