Mercurial > hg > webserver / file comparison

comparison: src/ucx/linked_list.c

src/ucx/linked_list.c

changeset 490
d218607f5a7e
parent 438
22eca559aded
child 491
5454ae7bf86b
equal deleted inserted replaced
489:921f83a8943f 490:d218607f5a7e
26 * POSSIBILITY OF SUCH DAMAGE. 26 * POSSIBILITY OF SUCH DAMAGE.
27 */ 27 */
28 28
29 #include "cx/linked_list.h" 29 #include "cx/linked_list.h"
30 #include "cx/utils.h" 30 #include "cx/utils.h"
31 #include <stdint.h>
32 #include <string.h> 31 #include <string.h>
33 #include <assert.h> 32 #include <assert.h>
34 33
35 // LOW LEVEL LINKED LIST FUNCTIONS 34 // LOW LEVEL LINKED LIST FUNCTIONS
36 35
37 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off))) 36 #define CX_LL_PTR(cur, off) (*(void**)(((char*)(cur))+(off)))
38 #define ll_prev(node) CX_LL_PTR(node, loc_prev) 37 #define ll_prev(node) CX_LL_PTR(node, loc_prev)
39 #define ll_next(node) CX_LL_PTR(node, loc_next) 38 #define ll_next(node) CX_LL_PTR(node, loc_next)
40 #define ll_advance(node) CX_LL_PTR(node, loc_advance) 39 #define ll_advance(node) CX_LL_PTR(node, loc_advance)
41 #define ll_data_f(node, follow_ptr) ((follow_ptr)?CX_LL_PTR(node, loc_data):(((char*)(node))+loc_data)) 40 #define ll_data(node) (((char*)(node))+loc_data)
42 #define ll_data(node) ll_data_f(node,follow_ptr)
43 41
44 void *cx_linked_list_at( 42 void *cx_linked_list_at(
45 void const *start, 43 void const *start,
46 size_t start_index, 44 size_t start_index,
47 ptrdiff_t loc_advance, 45 ptrdiff_t loc_advance,
56 i < index ? i++ : i--; 54 i < index ? i++ : i--;
57 } 55 }
58 return (void *) cur; 56 return (void *) cur;
59 } 57 }
60 58
61 size_t cx_linked_list_find( 59 ssize_t cx_linked_list_find(
62 void const *start, 60 void const *start,
63 ptrdiff_t loc_advance, 61 ptrdiff_t loc_advance,
64 ptrdiff_t loc_data, 62 ptrdiff_t loc_data,
65 bool follow_ptr, 63 cx_compare_func cmp_func,
66 CxListComparator cmp_func,
67 void const *elem 64 void const *elem
68 ) { 65 ) {
69 assert(start != NULL); 66 assert(start != NULL);
70 assert(loc_advance >= 0); 67 assert(loc_advance >= 0);
71 assert(loc_data >= 0); 68 assert(loc_data >= 0);
72 assert(cmp_func); 69 assert(cmp_func);
73 70
74 void const *node = start; 71 void const *node = start;
75 size_t index = 0; 72 ssize_t index = 0;
76 do { 73 do {
77 void *current = ll_data(node); 74 void *current = ll_data(node);
78 if (cmp_func(current, elem) == 0) { 75 if (cmp_func(current, elem) == 0) {
79 return index; 76 return index;
80 } 77 }
81 node = ll_advance(node); 78 node = ll_advance(node);
82 index++; 79 index++;
83 } while (node != NULL); 80 } while (node != NULL);
84 return index; 81 return -1;
85 } 82 }
86 83
87 void *cx_linked_list_first( 84 void *cx_linked_list_first(
88 void const *node, 85 void const *node,
89 ptrdiff_t loc_prev 86 ptrdiff_t loc_prev
280 size++; 277 size++;
281 } 278 }
282 return size; 279 return size;
283 } 280 }
284 281
282 #ifndef CX_LINKED_LIST_SORT_SBO_SIZE
283 #define CX_LINKED_LIST_SORT_SBO_SIZE 1024
284 #endif
285
285 static void *cx_linked_list_sort_merge( 286 static void *cx_linked_list_sort_merge(
286 ptrdiff_t loc_prev, 287 ptrdiff_t loc_prev,
287 ptrdiff_t loc_next, 288 ptrdiff_t loc_next,
288 ptrdiff_t loc_data, 289 ptrdiff_t loc_data,
289 bool follow_ptr,
290 size_t length, 290 size_t length,
291 void *ls, 291 void *ls,
292 void *le, 292 void *le,
293 void *re, 293 void *re,
294 CxListComparator cmp_func 294 cx_compare_func cmp_func
295 ) { 295 ) {
296 const size_t sbo_len = 1024; 296 void *sbo[CX_LINKED_LIST_SORT_SBO_SIZE];
297 void *sbo[sbo_len]; 297 void **sorted = length >= CX_LINKED_LIST_SORT_SBO_SIZE ?
298 void **sorted = (length >= sbo_len) ? malloc(sizeof(void *) * length) : sbo; 298 malloc(sizeof(void *) * length) : sbo;
299 if (sorted == NULL) abort(); 299 if (sorted == NULL) abort();
300 void *rc, *lc; 300 void *rc, *lc;
301 301
302 lc = ls; 302 lc = ls;
303 rc = le; 303 rc = le;
341 void **begin, 341 void **begin,
342 void **end, 342 void **end,
343 ptrdiff_t loc_prev, 343 ptrdiff_t loc_prev,
344 ptrdiff_t loc_next, 344 ptrdiff_t loc_next,
345 ptrdiff_t loc_data, 345 ptrdiff_t loc_data,
346 bool follow_ptr, 346 cx_compare_func cmp_func
347 CxListComparator cmp_func
348 ) { 347 ) {
349 assert(begin != NULL); 348 assert(begin != NULL);
350 assert(loc_next >= 0); 349 assert(loc_next >= 0);
351 assert(loc_data >= 0); 350 assert(loc_data >= 0);
352 assert(cmp_func); 351 assert(cmp_func);
376 rn++; 375 rn++;
377 } 376 }
378 re = ll_next(rc); 377 re = ll_next(rc);
379 378
380 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them 379 // {ls,...,le->prev} and {rs,...,re->prev} are sorted - merge them
381 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr, 380 void *sorted = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
382 ln + rn, ls, le, re, cmp_func); 381 ln + rn, ls, le, re, cmp_func);
383 382
384 // Something left? Sort it! 383 // Something left? Sort it!
385 size_t remainder_length = cx_linked_list_size(re, loc_next); 384 size_t remainder_length = cx_linked_list_size(re, loc_next);
386 if (remainder_length > 0) { 385 if (remainder_length > 0) {
387 void *remainder = re; 386 void *remainder = re;
388 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, follow_ptr, cmp_func); 387 cx_linked_list_sort(&remainder, NULL, loc_prev, loc_next, loc_data, cmp_func);
389 388
390 // merge sorted list with (also sorted) remainder 389 // merge sorted list with (also sorted) remainder
391 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data, follow_ptr, 390 *begin = cx_linked_list_sort_merge(loc_prev, loc_next, loc_data,
392 ln + rn + remainder_length, 391 ln + rn + remainder_length,
393 sorted, remainder, NULL, cmp_func); 392 sorted, remainder, NULL, cmp_func);
394 } else { 393 } else {
395 // no remainder - we've got our sorted list 394 // no remainder - we've got our sorted list
396 *begin = sorted; 395 *begin = sorted;
402 int cx_linked_list_compare( 401 int cx_linked_list_compare(
403 void const *begin_left, 402 void const *begin_left,
404 void const *begin_right, 403 void const *begin_right,
405 ptrdiff_t loc_advance, 404 ptrdiff_t loc_advance,
406 ptrdiff_t loc_data, 405 ptrdiff_t loc_data,
407 bool follow_ptr_left, 406 cx_compare_func cmp_func
408 bool follow_ptr_right,
409 CxListComparator cmp_func
410 ) { 407 ) {
411 void const *left = begin_left, *right = begin_right; 408 void const *left = begin_left, *right = begin_right;
412 409
413 while (left != NULL && right != NULL) { 410 while (left != NULL && right != NULL) {
414 void const *left_data = ll_data_f(left, follow_ptr_left); 411 void const *left_data = ll_data(left);
415 void const *right_data = ll_data_f(right, follow_ptr_right); 412 void const *right_data = ll_data(right);
416 int result = cmp_func(left_data, right_data); 413 int result = cmp_func(left_data, right_data);
417 if (result != 0) return result; 414 if (result != 0) return result;
418 left = ll_advance(left); 415 left = ll_advance(left);
419 right = ll_advance(right); 416 right = ll_advance(right);
420 } 417 }
454 } 451 }
455 *begin = prev; 452 *begin = prev;
456 } 453 }
457 454
458 // HIGH LEVEL LINKED LIST IMPLEMENTATION 455 // HIGH LEVEL LINKED LIST IMPLEMENTATION
456
457 bool CX_DISABLE_LINKED_LIST_SWAP_SBO = false;
459 458
460 typedef struct cx_linked_list_node cx_linked_list_node; 459 typedef struct cx_linked_list_node cx_linked_list_node;
461 struct cx_linked_list_node { 460 struct cx_linked_list_node {
462 cx_linked_list_node *prev; 461 cx_linked_list_node *prev;
463 cx_linked_list_node *next; 462 cx_linked_list_node *next;
470 469
471 typedef struct { 470 typedef struct {
472 struct cx_list_s base; 471 struct cx_list_s base;
473 cx_linked_list_node *begin; 472 cx_linked_list_node *begin;
474 cx_linked_list_node *end; 473 cx_linked_list_node *end;
475 bool follow_ptr;
476 } cx_linked_list; 474 } cx_linked_list;
477 475
478 static cx_linked_list_node *cx_ll_node_at( 476 static cx_linked_list_node *cx_ll_node_at(
479 cx_linked_list const *list, 477 cx_linked_list const *list,
480 size_t index 478 size_t index
494 void const *elem 492 void const *elem
495 ) { 493 ) {
496 494
497 // create the new new_node 495 // create the new new_node
498 cx_linked_list_node *new_node = cxMalloc(list->allocator, 496 cx_linked_list_node *new_node = cxMalloc(list->allocator,
499 sizeof(cx_linked_list_node) + list->itemsize); 497 sizeof(cx_linked_list_node) + list->item_size);
500 498
501 // sortir if failed 499 // sortir if failed
502 if (new_node == NULL) return 1; 500 if (new_node == NULL) return 1;
503 501
504 // initialize new new_node 502 // initialize new new_node
505 new_node->prev = new_node->next = NULL; 503 new_node->prev = new_node->next = NULL;
506 memcpy(new_node->payload, elem, list->itemsize); 504 memcpy(new_node->payload, elem, list->item_size);
507 505
508 // insert 506 // insert
509 cx_linked_list *ll = (cx_linked_list *) list; 507 cx_linked_list *ll = (cx_linked_list *) list;
510 cx_linked_list_insert_chain( 508 cx_linked_list_insert_chain(
511 (void **) &ll->begin, (void **) &ll->end, 509 (void **) &ll->begin, (void **) &ll->end,
516 // increase the size and return 514 // increase the size and return
517 list->size++; 515 list->size++;
518 return 0; 516 return 0;
519 } 517 }
520 518
521 static int cx_ll_insert( 519 static size_t cx_ll_insert_array(
522 struct cx_list_s *list, 520 struct cx_list_s *list,
523 size_t index, 521 size_t index,
524 void const *elem 522 void const *array,
525 ) { 523 size_t n
526 // out-of bounds check 524 ) {
527 if (index > list->size) return 1; 525 // out-of bounds and corner case check
526 if (index > list->size || n == 0) return 0;
528 527
529 // find position efficiently 528 // find position efficiently
530 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1); 529 cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
531 530
532 // perform insert 531 // perform first insert
533 return cx_ll_insert_at(list, node, elem); 532 if (0 != cx_ll_insert_at(list, node, array)) {
534 } 533 return 1;
535 534 }
536 static int cx_ll_add( 535
537 struct cx_list_s *list, 536 // is there more?
538 void const *elem 537 if (n == 1) return 1;
539 ) { 538
540 return cx_ll_insert(list, list->size, elem); 539 // we now know exactly where we are
541 } 540 node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
542 541
543 static size_t cx_ll_add_array( 542 // we can add the remaining nodes and immedately advance to the inserted node
544 struct cx_list_s *list, 543 char const *source = array;
545 void const *array, 544 for (size_t i = 1; i < n; i++) {
546 size_t n 545 source += list->item_size;
547 ) { 546 if (0 != cx_ll_insert_at(list, node, source)) {
548 // TODO: redirect to cx_ll_insert_array
549 cx_for_n (i, n) {
550 if (cx_ll_add(list, ((char const *) array) + i * list->itemsize)) {
551 return i; 547 return i;
552 } 548 }
549 node = node->next;
553 } 550 }
554 return n; 551 return n;
555 } 552 }
556 553
557 static int cx_pll_insert( 554 static int cx_ll_insert_element(
558 struct cx_list_s *list, 555 struct cx_list_s *list,
559 size_t index, 556 size_t index,
560 void const *elem 557 void const *element
561 ) { 558 ) {
562 return cx_ll_insert(list, index, &elem); 559 return 1 != cx_ll_insert_array(list, index, element, 1);
563 }
564
565 static int cx_pll_add(
566 struct cx_list_s *list,
567 void const *elem
568 ) {
569 return cx_ll_insert(list, list->size, &elem);
570 } 560 }
571 561
572 static int cx_ll_remove( 562 static int cx_ll_remove(
573 struct cx_list_s *list, 563 struct cx_list_s *list,
574 size_t index 564 size_t index
577 cx_linked_list_node *node = cx_ll_node_at(ll, index); 567 cx_linked_list_node *node = cx_ll_node_at(ll, index);
578 568
579 // out-of-bounds check 569 // out-of-bounds check
580 if (node == NULL) return 1; 570 if (node == NULL) return 1;
581 571
572 // element destruction
573 cx_invoke_destructor(list, node->payload);
574
582 // remove 575 // remove
583 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 576 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
584 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 577 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
585 578
586 // adjust size 579 // adjust size
590 cxFree(list->allocator, node); 583 cxFree(list->allocator, node);
591 584
592 return 0; 585 return 0;
593 } 586 }
594 587
588 static void cx_ll_clear(struct cx_list_s *list) {
589 if (list->size == 0) return;
590
591 cx_linked_list *ll = (cx_linked_list *) list;
592 cx_linked_list_node *node = ll->begin;
593 while (node != NULL) {
594 cx_invoke_destructor(list, node->payload);
595 cx_linked_list_node *next = node->next;
596 cxFree(list->allocator, node);
597 node = next;
598 }
599 ll->begin = ll->end = NULL;
600 list->size = 0;
601 }
602
603 #ifndef CX_LINKED_LIST_SWAP_SBO_SIZE
604 #define CX_LINKED_LIST_SWAP_SBO_SIZE 16
605 #endif
606
607 static int cx_ll_swap(
608 struct cx_list_s *list,
609 size_t i,
610 size_t j
611 ) {
612 if (i >= list->size || j >= list->size) return 1;
613 if (i == j) return 0;
614
615 // perform an optimized search that finds both elements in one run
616 cx_linked_list *ll = (cx_linked_list *) list;
617 size_t mid = list->size / 2;
618 size_t left, right;
619 if (i < j) {
620 left = i;
621 right = j;
622 } else {
623 left = j;
624 right = i;
625 }
626 cx_linked_list_node *nleft, *nright;
627 if (left < mid && right < mid) {
628 // case 1: both items left from mid
629 nleft = cx_ll_node_at(ll, left);
630 nright = nleft;
631 for (size_t c = left; c < right; c++) {
632 nright = nright->next;
633 }
634 } else if (left >= mid && right >= mid) {
635 // case 2: both items right from mid
636 nright = cx_ll_node_at(ll, right);
637 nleft = nright;
638 for (size_t c = right; c > left; c--) {
639 nleft = nleft->prev;
640 }
641 } else {
642 // case 3: one item left, one item right
643
644 // chose the closest to begin / end
645 size_t closest;
646 size_t other;
647 size_t diff2boundary = list->size - right - 1;
648 if (left <= diff2boundary) {
649 closest = left;
650 other = right;
651 nleft = cx_ll_node_at(ll, left);
652 } else {
653 closest = right;
654 other = left;
655 diff2boundary = left;
656 nright = cx_ll_node_at(ll, right);
657 }
658
659 // is other element closer to us or closer to boundary?
660 if (right - left <= diff2boundary) {
661 // search other element starting from already found element
662 if (closest == left) {
663 nright = nleft;
664 for (size_t c = left; c < right; c++) {
665 nright = nright->next;
666 }
667 } else {
668 nleft = nright;
669 for (size_t c = right; c > left; c--) {
670 nleft = nleft->prev;
671 }
672 }
673 } else {
674 // search other element starting at the boundary
675 if (closest == left) {
676 nright = cx_ll_node_at(ll, other);
677 } else {
678 nleft = cx_ll_node_at(ll, other);
679 }
680 }
681 }
682
683 if (list->item_size > CX_LINKED_LIST_SWAP_SBO_SIZE || CX_DISABLE_LINKED_LIST_SWAP_SBO) {
684 cx_linked_list_node *prev = nleft->prev;
685 cx_linked_list_node *next = nright->next;
686 cx_linked_list_node *midstart = nleft->next;
687 cx_linked_list_node *midend = nright->prev;
688
689 if (prev == NULL) {
690 ll->begin = nright;
691 } else {
692 prev->next = nright;
693 }
694 nright->prev = prev;
695 if (midstart == nright) {
696 // special case: both nodes are adjacent
697 nright->next = nleft;
698 nleft->prev = nright;
699 } else {
700 // likely case: a chain is between the two nodes
701 nright->next = midstart;
702 midstart->prev = nright;
703 midend->next = nleft;
704 nleft->prev = midend;
705 }
706 nleft->next = next;
707 if (next == NULL) {
708 ll->end = nleft;
709 } else {
710 next->prev = nleft;
711 }
712 } else {
713 // swap payloads to avoid relinking
714 char buf[CX_LINKED_LIST_SWAP_SBO_SIZE];
715 memcpy(buf, nleft->payload, list->item_size);
716 memcpy(nleft->payload, nright->payload, list->item_size);
717 memcpy(nright->payload, buf, list->item_size);
718 }
719
720 return 0;
721 }
722
595 static void *cx_ll_at( 723 static void *cx_ll_at(
596 struct cx_list_s const *list, 724 struct cx_list_s const *list,
597 size_t index 725 size_t index
598 ) { 726 ) {
599 cx_linked_list *ll = (cx_linked_list *) list; 727 cx_linked_list *ll = (cx_linked_list *) list;
600 cx_linked_list_node *node = cx_ll_node_at(ll, index); 728 cx_linked_list_node *node = cx_ll_node_at(ll, index);
601 return node == NULL ? NULL : node->payload; 729 return node == NULL ? NULL : node->payload;
602 } 730 }
603 731
604 static void *cx_pll_at( 732 static ssize_t cx_ll_find(
605 struct cx_list_s const *list,
606 size_t index
607 ) {
608 cx_linked_list *ll = (cx_linked_list *) list;
609 cx_linked_list_node *node = cx_ll_node_at(ll, index);
610 return node == NULL ? NULL : *(void **) node->payload;
611 }
612
613 static size_t cx_ll_find(
614 struct cx_list_s const *list, 733 struct cx_list_s const *list,
615 void const *elem 734 void const *elem
616 ) { 735 ) {
617 cx_linked_list *ll = (cx_linked_list *) list;
618 return cx_linked_list_find(((cx_linked_list *) list)->begin, 736 return cx_linked_list_find(((cx_linked_list *) list)->begin,
619 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 737 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
620 ll->follow_ptr, list->cmpfunc, elem); 738 list->cmpfunc, elem);
621 } 739 }
622 740
623 static void cx_ll_sort(struct cx_list_s *list) { 741 static void cx_ll_sort(struct cx_list_s *list) {
624 cx_linked_list *ll = (cx_linked_list *) list; 742 cx_linked_list *ll = (cx_linked_list *) list;
625 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, 743 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
626 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 744 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
627 ll->follow_ptr, list->cmpfunc); 745 list->cmpfunc);
628 } 746 }
629 747
630 static void cx_ll_reverse(struct cx_list_s *list) { 748 static void cx_ll_reverse(struct cx_list_s *list) {
631 cx_linked_list *ll = (cx_linked_list *) list; 749 cx_linked_list *ll = (cx_linked_list *) list;
632 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT); 750 cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
638 ) { 756 ) {
639 cx_linked_list *left = (cx_linked_list *) list; 757 cx_linked_list *left = (cx_linked_list *) list;
640 cx_linked_list *right = (cx_linked_list *) other; 758 cx_linked_list *right = (cx_linked_list *) other;
641 return cx_linked_list_compare(left->begin, right->begin, 759 return cx_linked_list_compare(left->begin, right->begin,
642 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 760 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
643 left->follow_ptr, right->follow_ptr, list->cmpfunc); 761 list->cmpfunc);
644 } 762 }
645 763
646 static bool cx_ll_iter_valid(void const *it) { 764 static bool cx_ll_iter_valid(void const *it) {
647 struct cx_iterator_s const *iter = it; 765 struct cx_iterator_s const *iter = it;
648 return iter->elem_handle != NULL; 766 return iter->elem_handle != NULL;
651 static void cx_ll_iter_next(void *it) { 769 static void cx_ll_iter_next(void *it) {
652 struct cx_iterator_base_s *itbase = it; 770 struct cx_iterator_base_s *itbase = it;
653 if (itbase->remove) { 771 if (itbase->remove) {
654 itbase->remove = false; 772 itbase->remove = false;
655 struct cx_mut_iterator_s *iter = it; 773 struct cx_mut_iterator_s *iter = it;
774 struct cx_list_s *list = iter->src_handle;
656 cx_linked_list *ll = iter->src_handle; 775 cx_linked_list *ll = iter->src_handle;
657 cx_linked_list_node *node = iter->elem_handle; 776 cx_linked_list_node *node = iter->elem_handle;
658 iter->elem_handle = node->next; 777 iter->elem_handle = node->next;
778 cx_invoke_destructor(list, node->payload);
659 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end, 779 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
660 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node); 780 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
661 ll->base.size--; 781 list->size--;
662 cxFree(ll->base.allocator, node); 782 cxFree(list->allocator, node);
663 } else { 783 } else {
664 struct cx_iterator_s *iter = it; 784 struct cx_iterator_s *iter = it;
665 iter->index++; 785 iter->index++;
666 cx_linked_list_node *node = iter->elem_handle; 786 cx_linked_list_node *node = iter->elem_handle;
667 iter->elem_handle = node->next; 787 iter->elem_handle = node->next;
668 } 788 }
669 } 789 }
670 790
791 static void cx_ll_iter_prev(void *it) {
792 struct cx_iterator_base_s *itbase = it;
793 if (itbase->remove) {
794 itbase->remove = false;
795 struct cx_mut_iterator_s *iter = it;
796 struct cx_list_s *list = iter->src_handle;
797 cx_linked_list *ll = iter->src_handle;
798 cx_linked_list_node *node = iter->elem_handle;
799 iter->elem_handle = node->prev;
800 iter->index--;
801 cx_invoke_destructor(list, node->payload);
802 cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
803 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
804 list->size--;
805 cxFree(list->allocator, node);
806 } else {
807 struct cx_iterator_s *iter = it;
808 iter->index--;
809 cx_linked_list_node *node = iter->elem_handle;
810 iter->elem_handle = node->prev;
811 }
812 }
813
671 static void *cx_ll_iter_current(void const *it) { 814 static void *cx_ll_iter_current(void const *it) {
672 struct cx_iterator_s const *iter = it; 815 struct cx_iterator_s const *iter = it;
673 cx_linked_list_node *node = iter->elem_handle; 816 cx_linked_list_node *node = iter->elem_handle;
674 return node->payload; 817 return node->payload;
675 }
676
677 static void *cx_pll_iter_current(void const *it) {
678 struct cx_iterator_s const *iter = it;
679 cx_linked_list_node *node = iter->elem_handle;
680 return *(void **) node->payload;
681 } 818 }
682 819
683 static bool cx_ll_iter_flag_rm(void *it) { 820 static bool cx_ll_iter_flag_rm(void *it) {
684 struct cx_iterator_base_s *iter = it; 821 struct cx_iterator_base_s *iter = it;
685 if (iter->mutating) { 822 if (iter->mutating) {
690 } 827 }
691 } 828 }
692 829
693 static CxIterator cx_ll_iterator( 830 static CxIterator cx_ll_iterator(
694 struct cx_list_s const *list, 831 struct cx_list_s const *list,
695 size_t index 832 size_t index,
833 bool backwards
696 ) { 834 ) {
697 CxIterator iter; 835 CxIterator iter;
698 iter.index = index; 836 iter.index = index;
699 iter.src_handle = list; 837 iter.src_handle = list;
700 iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index); 838 iter.elem_handle = cx_ll_node_at((cx_linked_list const *) list, index);
701 iter.base.valid = cx_ll_iter_valid; 839 iter.base.valid = cx_ll_iter_valid;
702 iter.base.current = cx_ll_iter_current; 840 iter.base.current = cx_ll_iter_current;
703 iter.base.next = cx_ll_iter_next; 841 iter.base.next = backwards ? cx_ll_iter_prev : cx_ll_iter_next;
704 iter.base.flag_removal = cx_ll_iter_flag_rm; 842 iter.base.flag_removal = cx_ll_iter_flag_rm;
705 iter.base.mutating = false; 843 iter.base.mutating = false;
706 iter.base.remove = false; 844 iter.base.remove = false;
707 return iter;
708 }
709
710 static CxIterator cx_pll_iterator(
711 struct cx_list_s const *list,
712 size_t index
713 ) {
714 CxIterator iter = cx_ll_iterator(list, index);
715 iter.base.current = cx_pll_iter_current;
716 return iter;
717 }
718
719 static CxMutIterator cx_ll_mut_iterator(
720 struct cx_list_s *list,
721 size_t index
722 ) {
723 CxIterator it = cx_ll_iterator(list, index);
724 it.base.mutating = true;
725
726 // we know the iterators share the same memory layout
727 CxMutIterator iter;
728 memcpy(&iter, &it, sizeof(CxMutIterator));
729 return iter;
730 }
731
732 static CxMutIterator cx_pll_mut_iterator(
733 struct cx_list_s *list,
734 size_t index
735 ) {
736 CxMutIterator iter = cx_ll_mut_iterator(list, index);
737 iter.base.current = cx_pll_iter_current;
738 return iter; 845 return iter;
739 } 846 }
740 847
741 static int cx_ll_insert_iter( 848 static int cx_ll_insert_iter(
742 CxMutIterator *iter, 849 CxMutIterator *iter,
750 cx_linked_list_node *choice[2] = {node, node->prev}; 857 cx_linked_list_node *choice[2] = {node, node->prev};
751 int result = cx_ll_insert_at(list, choice[prepend], elem); 858 int result = cx_ll_insert_at(list, choice[prepend], elem);
752 iter->index += prepend * (0 == result); 859 iter->index += prepend * (0 == result);
753 return result; 860 return result;
754 } else { 861 } else {
755 int result = cx_ll_insert(list, list->size, elem); 862 int result = cx_ll_insert_element(list, list->size, elem);
756 iter->index = list->size; 863 iter->index = list->size;
757 return result; 864 return result;
758 } 865 }
759 }
760
761 static int cx_pll_insert_iter(
762 CxMutIterator *iter,
763 void const *elem,
764 int prepend
765 ) {
766 return cx_ll_insert_iter(iter, &elem, prepend);
767 } 866 }
768 867
769 static void cx_ll_destructor(CxList *list) { 868 static void cx_ll_destructor(CxList *list) {
770 cx_linked_list *ll = (cx_linked_list *) list; 869 cx_linked_list *ll = (cx_linked_list *) list;
771 870
778 // do not free the list pointer, this is just a destructor! 877 // do not free the list pointer, this is just a destructor!
779 } 878 }
780 879
781 static cx_list_class cx_linked_list_class = { 880 static cx_list_class cx_linked_list_class = {
782 cx_ll_destructor, 881 cx_ll_destructor,
783 cx_ll_add, 882 cx_ll_insert_element,
784 cx_ll_add_array, 883 cx_ll_insert_array,
785 cx_ll_insert,
786 cx_ll_insert_iter, 884 cx_ll_insert_iter,
787 cx_ll_remove, 885 cx_ll_remove,
886 cx_ll_clear,
887 cx_ll_swap,
788 cx_ll_at, 888 cx_ll_at,
789 cx_ll_find, 889 cx_ll_find,
790 cx_ll_sort, 890 cx_ll_sort,
791 cx_ll_compare, 891 cx_ll_compare,
792 cx_ll_reverse, 892 cx_ll_reverse,
793 cx_ll_iterator, 893 cx_ll_iterator,
794 cx_ll_mut_iterator,
795 };
796
797 static cx_list_class cx_pointer_linked_list_class = {
798 cx_ll_destructor,
799 cx_pll_add,
800 cx_ll_add_array,
801 cx_pll_insert,
802 cx_pll_insert_iter,
803 cx_ll_remove,
804 cx_pll_at,
805 cx_ll_find,
806 cx_ll_sort,
807 cx_ll_compare,
808 cx_ll_reverse,
809 cx_pll_iterator,
810 cx_pll_mut_iterator,
811 }; 894 };
812 895
813 CxList *cxLinkedListCreate( 896 CxList *cxLinkedListCreate(
814 CxAllocator const *allocator, 897 CxAllocator const *allocator,
815 CxListComparator comparator, 898 cx_compare_func comparator,
816 size_t item_size 899 size_t item_size
817 ) { 900 ) {
901 if (allocator == NULL) {
902 allocator = cxDefaultAllocator;
903 }
904
818 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list)); 905 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
819 if (list == NULL) return NULL; 906 if (list == NULL) return NULL;
820 907
821 list->follow_ptr = false;
822 list->base.cl = &cx_linked_list_class; 908 list->base.cl = &cx_linked_list_class;
823 list->base.allocator = allocator; 909 list->base.allocator = allocator;
824 list->base.cmpfunc = comparator; 910 list->base.cmpfunc = comparator;
825 list->base.itemsize = item_size; 911
826 list->base.capacity = SIZE_MAX; 912 if (item_size > 0) {
913 list->base.item_size = item_size;
914 } else {
915 cxListStorePointers((CxList *) list);
916 }
827 917
828 return (CxList *) list; 918 return (CxList *) list;
829 } 919 }
830
831 CxList *cxPointerLinkedListCreate(
832 CxAllocator const *allocator,
833 CxListComparator comparator
834 ) {
835 cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
836 if (list == NULL) return NULL;
837
838 list->follow_ptr = true;
839 list->base.cl = &cx_pointer_linked_list_class;
840 list->base.allocator = allocator;
841 list->base.cmpfunc = comparator;
842 list->base.itemsize = sizeof(void *);
843 list->base.capacity = SIZE_MAX;
844
845 return (CxList *) list;
846 }

Mercurial Repository: webserver

mercurial