Mercurial > hg > ucx / file comparison

comparison: src/linked_list.c

src/linked_list.c

changeset 500
eb9e7bd40a8e
parent 499
3dc9075df822
child 503
a89857072ace
equal deleted inserted replaced
499:3dc9075df822 500:eb9e7bd40a8e
461 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev) 461 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
462 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next) 462 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
463 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload) 463 #define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
464 464
465 typedef struct { 465 typedef struct {
466 cx_list_s base; 466 struct cx_list_s base;
467 cx_linked_list_node *begin; 467 cx_linked_list_node *begin;
468 cx_linked_list_node *end; 468 cx_linked_list_node *end;
469 } cx_linked_list; 469 } cx_linked_list;
470 470
471 static cx_linked_list_node *cx_ll_node_at( 471 static cx_linked_list_node *cx_ll_node_at(
480 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); 480 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
481 } 481 }
482 } 482 }
483 483
484 static int cx_ll_insert_at( 484 static int cx_ll_insert_at(
485 cx_list_s *list, 485 struct cx_list_s *list,
486 cx_linked_list_node *node, 486 cx_linked_list_node *node,
487 void const *elem 487 void const *elem
488 ) { 488 ) {
489 489
490 // create the new new_node 490 // create the new new_node
510 list->size++; 510 list->size++;
511 return 0; 511 return 0;
512 } 512 }
513 513
514 static int cx_ll_insert( 514 static int cx_ll_insert(
515 cx_list_s *list, 515 struct cx_list_s *list,
516 size_t index, 516 size_t index,
517 void const *elem 517 void const *elem
518 ) { 518 ) {
519 // out-of bounds check 519 // out-of bounds check
520 if (index > list->size) return 1; 520 if (index > list->size) return 1;
525 // perform insert 525 // perform insert
526 return cx_ll_insert_at(list, node, elem); 526 return cx_ll_insert_at(list, node, elem);
527 } 527 }
528 528
529 static int cx_ll_add( 529 static int cx_ll_add(
530 cx_list_s *list, 530 struct cx_list_s *list,
531 void const *elem 531 void const *elem
532 ) { 532 ) {
533 return cx_ll_insert(list, list->size, elem); 533 return cx_ll_insert(list, list->size, elem);
534 } 534 }
535 535
536 static int cx_pll_insert( 536 static int cx_pll_insert(
537 cx_list_s *list, 537 struct cx_list_s *list,
538 size_t index, 538 size_t index,
539 void const *elem 539 void const *elem
540 ) { 540 ) {
541 return cx_ll_insert(list, index, &elem); 541 return cx_ll_insert(list, index, &elem);
542 } 542 }
543 543
544 static int cx_pll_add( 544 static int cx_pll_add(
545 cx_list_s *list, 545 struct cx_list_s *list,
546 void const *elem 546 void const *elem
547 ) { 547 ) {
548 return cx_ll_insert(list, list->size, &elem); 548 return cx_ll_insert(list, list->size, &elem);
549 } 549 }
550 550
551 static int cx_ll_remove( 551 static int cx_ll_remove(
552 cx_list_s *list, 552 struct cx_list_s *list,
553 size_t index 553 size_t index
554 ) { 554 ) {
555 cx_linked_list *ll = (cx_linked_list *) list; 555 cx_linked_list *ll = (cx_linked_list *) list;
556 cx_linked_list_node *node = cx_ll_node_at(ll, index); 556 cx_linked_list_node *node = cx_ll_node_at(ll, index);
557 557
570 570
571 return 0; 571 return 0;
572 } 572 }
573 573
574 static void *cx_ll_at( 574 static void *cx_ll_at(
575 cx_list_s const *list, 575 struct cx_list_s const *list,
576 size_t index 576 size_t index
577 ) { 577 ) {
578 cx_linked_list *ll = (cx_linked_list *) list; 578 cx_linked_list *ll = (cx_linked_list *) list;
579 cx_linked_list_node *node = cx_ll_node_at(ll, index); 579 cx_linked_list_node *node = cx_ll_node_at(ll, index);
580 return node == NULL ? NULL : node->payload; 580 return node == NULL ? NULL : node->payload;
581 } 581 }
582 582
583 static void *cx_pll_at( 583 static void *cx_pll_at(
584 cx_list_s const *list, 584 struct cx_list_s const *list,
585 size_t index 585 size_t index
586 ) { 586 ) {
587 cx_linked_list *ll = (cx_linked_list *) list; 587 cx_linked_list *ll = (cx_linked_list *) list;
588 cx_linked_list_node *node = cx_ll_node_at(ll, index); 588 cx_linked_list_node *node = cx_ll_node_at(ll, index);
589 return node == NULL ? NULL : *(void **) node->payload; 589 return node == NULL ? NULL : *(void **) node->payload;
590 } 590 }
591 591
592 static size_t cx_ll_find( 592 static size_t cx_ll_find(
593 cx_list_s const *list, 593 struct cx_list_s const *list,
594 void const *elem 594 void const *elem
595 ) { 595 ) {
596 return cx_linked_list_find(((cx_linked_list *) list)->begin, 596 return cx_linked_list_find(((cx_linked_list *) list)->begin,
597 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 597 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
598 false, list->cmpfunc, elem); 598 false, list->cmpfunc, elem);
599 } 599 }
600 600
601 static size_t cx_pll_find( 601 static size_t cx_pll_find(
602 cx_list_s const *list, 602 struct cx_list_s const *list,
603 void const *elem 603 void const *elem
604 ) { 604 ) {
605 return cx_linked_list_find(((cx_linked_list *) list)->begin, 605 return cx_linked_list_find(((cx_linked_list *) list)->begin,
606 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 606 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
607 true, list->cmpfunc, elem); 607 true, list->cmpfunc, elem);
608 } 608 }
609 609
610 static void cx_ll_sort(cx_list_s *list) { 610 static void cx_ll_sort(struct cx_list_s *list) {
611 cx_linked_list *ll = (cx_linked_list *) list; 611 cx_linked_list *ll = (cx_linked_list *) list;
612 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, 612 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
613 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 613 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
614 false, list->cmpfunc); 614 false, list->cmpfunc);
615 } 615 }
616 616
617 static void cx_pll_sort(cx_list_s *list) { 617 static void cx_pll_sort(struct cx_list_s *list) {
618 cx_linked_list *ll = (cx_linked_list *) list; 618 cx_linked_list *ll = (cx_linked_list *) list;
619 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end, 619 cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
620 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 620 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
621 true, list->cmpfunc); 621 true, list->cmpfunc);
622 } 622 }
623 623
624 static void cx_ll_reverse(cx_list_s *list) { 624 static void cx_ll_reverse(struct cx_list_s *list) {
625 cx_linked_list *ll = (cx_linked_list *) list; 625 cx_linked_list *ll = (cx_linked_list *) list;
626 cx_linked_list_reverse((void **) &ll->begin, (void **) ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT); 626 cx_linked_list_reverse((void **) &ll->begin, (void **) ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
627 } 627 }
628 628
629 static int cx_ll_compare( 629 static int cx_ll_compare(
630 cx_list_s const *list, 630 struct cx_list_s const *list,
631 cx_list_s const *other 631 struct cx_list_s const *other
632 ) { 632 ) {
633 cx_linked_list *left = (cx_linked_list *) list; 633 cx_linked_list *left = (cx_linked_list *) list;
634 cx_linked_list *right = (cx_linked_list *) other; 634 cx_linked_list *right = (cx_linked_list *) other;
635 return cx_linked_list_compare(left->begin, right->begin, 635 return cx_linked_list_compare(left->begin, right->begin,
636 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 636 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
637 false, list->cmpfunc); 637 false, list->cmpfunc);
638 } 638 }
639 639
640 static int cx_pll_compare( 640 static int cx_pll_compare(
641 cx_list_s const *list, 641 struct cx_list_s const *list,
642 cx_list_s const *other 642 struct cx_list_s const *other
643 ) { 643 ) {
644 cx_linked_list *left = (cx_linked_list *) list; 644 cx_linked_list *left = (cx_linked_list *) list;
645 cx_linked_list *right = (cx_linked_list *) other; 645 cx_linked_list *right = (cx_linked_list *) other;
646 return cx_linked_list_compare(left->begin, right->begin, 646 return cx_linked_list_compare(left->begin, right->begin,
647 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, 647 CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
678 cx_linked_list_node *node = iter->elem_handle; 678 cx_linked_list_node *node = iter->elem_handle;
679 return *(void **) node->payload; 679 return *(void **) node->payload;
680 } 680 }
681 681
682 static CxIterator cx_ll_iterator( 682 static CxIterator cx_ll_iterator(
683 cx_list_s *list, 683 struct cx_list_s *list,
684 size_t index 684 size_t index
685 ) { 685 ) {
686 CxIterator iter; 686 CxIterator iter;
687 iter.index = index; 687 iter.index = index;
688 iter.src_handle = list; 688 iter.src_handle = list;
693 iter.remove = false; 693 iter.remove = false;
694 return iter; 694 return iter;
695 } 695 }
696 696
697 static CxIterator cx_pll_iterator( 697 static CxIterator cx_pll_iterator(
698 cx_list_s *list, 698 struct cx_list_s *list,
699 size_t index 699 size_t index
700 ) { 700 ) {
701 CxIterator iter = cx_ll_iterator(list, index); 701 CxIterator iter = cx_ll_iterator(list, index);
702 iter.current = cx_pll_iter_current; 702 iter.current = cx_pll_iter_current;
703 return iter; 703 return iter;
706 static int cx_ll_insert_iter( 706 static int cx_ll_insert_iter(
707 CxIterator *iter, 707 CxIterator *iter,
708 void const *elem, 708 void const *elem,
709 int prepend 709 int prepend
710 ) { 710 ) {
711 cx_list_s *list = iter->src_handle; 711 struct cx_list_s *list = iter->src_handle;
712 cx_linked_list_node *node = iter->elem_handle; 712 cx_linked_list_node *node = iter->elem_handle;
713 if (node != NULL) { 713 if (node != NULL) {
714 assert(prepend >= 0 && prepend <= 1); 714 assert(prepend >= 0 && prepend <= 1);
715 cx_linked_list_node *choice[2] = {node, node->prev}; 715 cx_linked_list_node *choice[2] = {node, node->prev};
716 int result = cx_ll_insert_at(list, choice[prepend], elem); 716 int result = cx_ll_insert_at(list, choice[prepend], elem);
755 cx_pll_compare, 755 cx_pll_compare,
756 cx_ll_reverse, 756 cx_ll_reverse,
757 cx_pll_iterator, 757 cx_pll_iterator,
758 }; 758 };
759 759
760 CxList cxLinkedListCreate( 760 CxList *cxLinkedListCreate(
761 CxAllocator allocator, 761 CxAllocator *allocator,
762 CxListComparator comparator, 762 CxListComparator comparator,
763 size_t item_size 763 size_t item_size
764 ) { 764 ) {
765 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list)); 765 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
766 if (list == NULL) 766 if (list == NULL)
774 list->base.size = 0; 774 list->base.size = 0;
775 775
776 list->begin = NULL; 776 list->begin = NULL;
777 list->end = NULL; 777 list->end = NULL;
778 778
779 return (CxList) list; 779 return (CxList *) list;
780 } 780 }
781 781
782 CxList cxPointerLinkedListCreate( 782 CxList *cxPointerLinkedListCreate(
783 CxAllocator allocator, 783 CxAllocator *allocator,
784 CxListComparator comparator 784 CxListComparator comparator
785 ) { 785 ) {
786 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list)); 786 cx_linked_list *list = cxMalloc(allocator, sizeof(cx_linked_list));
787 if (list == NULL) 787 if (list == NULL)
788 return NULL; 788 return NULL;
795 list->base.size = 0; 795 list->base.size = 0;
796 796
797 list->begin = NULL; 797 list->begin = NULL;
798 list->end = NULL; 798 list->end = NULL;
799 799
800 return (CxList) list; 800 return (CxList *) list;
801 } 801 }
802 802
803 CxList cxLinkedListFromArray( 803 CxList *cxLinkedListFromArray(
804 CxAllocator allocator, 804 CxAllocator *allocator,
805 CxListComparator comparator, 805 CxListComparator comparator,
806 size_t item_size, 806 size_t item_size,
807 size_t num_items, 807 size_t num_items,
808 void const *array 808 void const *array
809 ) { 809 ) {
810 CxList list = cxLinkedListCreate(allocator, comparator, item_size); 810 CxList *list = cxLinkedListCreate(allocator, comparator, item_size);
811 if (list == NULL) return NULL; 811 if (list == NULL) return NULL;
812 for (size_t i = 0; i < num_items; i++) { 812 for (size_t i = 0; i < num_items; i++) {
813 if (0 != cxListAdd(list, ((const unsigned char *) array) + i * item_size)) { 813 if (0 != cxListAdd(list, ((const unsigned char *) array) + i * item_size)) {
814 cxLinkedListDestroy(list); 814 cxLinkedListDestroy(list);
815 return NULL; 815 return NULL;
816 } 816 }
817 } 817 }
818 return list; 818 return list;
819 } 819 }
820 820
821 void cxLinkedListDestroy(CxList list) { 821 void cxLinkedListDestroy(CxList *list) {
822 cx_linked_list *ll = (cx_linked_list *) list; 822 cx_linked_list *ll = (cx_linked_list *) list;
823 823
824 cx_linked_list_node *node = ll->begin; 824 cx_linked_list_node *node = ll->begin;
825 while (node) { 825 while (node) {
826 void *next = node->next; 826 void *next = node->next;

Mercurial Repository: ucx

mercurial