comparison: src/linked_list.c
src/linked_list.c
- changeset 489
- af6be1e123aa
- parent 488
- 9138acaa494b
- child 490
- e66551b47466
equal
deleted
inserted
replaced
| 488:9138acaa494b | 489:af6be1e123aa |
|---|---|
| 55 } | 55 } |
| 56 return cur; | 56 return cur; |
| 57 } | 57 } |
| 58 | 58 |
| 59 size_t cx_linked_list_find( | 59 size_t cx_linked_list_find( |
| 60 void *start, | 60 void const *start, |
| 61 ptrdiff_t loc_advance, | 61 ptrdiff_t loc_advance, |
| 62 ptrdiff_t loc_data, | 62 ptrdiff_t loc_data, |
| 63 bool follow_ptr, | 63 bool follow_ptr, |
| 64 CxListComparator cmp_func, | 64 CxListComparator cmp_func, |
| 65 void *elem | 65 void const *elem |
| 66 ) { | 66 ) { |
| 67 assert(start != NULL); | 67 assert(start != NULL); |
| 68 assert(loc_advance >= 0); | 68 assert(loc_advance >= 0); |
| 69 assert(loc_data >= 0); | 69 assert(loc_data >= 0); |
| 70 assert(cmp_func); | 70 assert(cmp_func); |
| 71 | 71 |
| 72 void *node = start; | 72 void const *node = start; |
| 73 size_t index = 0; | 73 size_t index = 0; |
| 74 do { | 74 do { |
| 75 void *current = ll_data(node); | 75 void *current = ll_data(node); |
| 76 if (cmp_func(current, elem) == 0) { | 76 if (cmp_func(current, elem) == 0) { |
| 77 return index; | 77 return index; |
| 266 ll_prev(next) = prev; | 266 ll_prev(next) = prev; |
| 267 } | 267 } |
| 268 } | 268 } |
| 269 | 269 |
| 270 size_t cx_linked_list_size( | 270 size_t cx_linked_list_size( |
| 271 void *node, | 271 void const *node, |
| 272 ptrdiff_t loc_next | 272 ptrdiff_t loc_next |
| 273 ) { | 273 ) { |
| 274 assert(loc_next >= 0); | 274 assert(loc_next >= 0); |
| 275 size_t size = 0; | 275 size_t size = 0; |
| 276 while (node != NULL) { | 276 while (node != NULL) { |
| 395 if (end) *end = cx_linked_list_last(sorted, loc_next); | 395 if (end) *end = cx_linked_list_last(sorted, loc_next); |
| 396 } | 396 } |
| 397 } | 397 } |
| 398 | 398 |
| 399 int cx_linked_list_compare( | 399 int cx_linked_list_compare( |
| 400 void *begin_left, | 400 void const *begin_left, |
| 401 void *begin_right, | 401 void const *begin_right, |
| 402 ptrdiff_t loc_advance, | 402 ptrdiff_t loc_advance, |
| 403 ptrdiff_t loc_data, | 403 ptrdiff_t loc_data, |
| 404 bool follow_ptr, | 404 bool follow_ptr, |
| 405 CxListComparator cmp_func | 405 CxListComparator cmp_func |
| 406 ) { | 406 ) { |
| 407 void *left = begin_left, *right = begin_right; | 407 void const *left = begin_left, *right = begin_right; |
| 408 | 408 |
| 409 while (left != NULL && right != NULL) { | 409 while (left != NULL && right != NULL) { |
| 410 int result = cmp_func(ll_data(left), ll_data(right)); | 410 int result = cmp_func(ll_data(left), ll_data(right)); |
| 411 if (result != 0) return result; | 411 if (result != 0) return result; |
| 412 left = ll_advance(left); | 412 left = ll_advance(left); |
| 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( |
| 472 cx_linked_list *list, | 472 cx_linked_list const *list, |
| 473 size_t index | 473 size_t index |
| 474 ) { | 474 ) { |
| 475 if (index >= list->base.size) { | 475 if (index >= list->base.size) { |
| 476 return NULL; | 476 return NULL; |
| 477 } else if (index > list->base.size / 2) { | 477 } else if (index > list->base.size / 2) { |
| 482 } | 482 } |
| 483 | 483 |
| 484 static int cx_ll_insert( | 484 static int cx_ll_insert( |
| 485 cx_list_s *list, | 485 cx_list_s *list, |
| 486 size_t index, | 486 size_t index, |
| 487 void *elem | 487 void const *elem |
| 488 ) { | 488 ) { |
| 489 // out-of bounds check | 489 // out-of bounds check |
| 490 if (index > list->size) return 1; | 490 if (index > list->size) return 1; |
| 491 | 491 |
| 492 // cast a linked list pointer | 492 // cast a linked list pointer |
| 518 return 0; | 518 return 0; |
| 519 } | 519 } |
| 520 | 520 |
| 521 static int cx_ll_add( | 521 static int cx_ll_add( |
| 522 cx_list_s *list, | 522 cx_list_s *list, |
| 523 void *elem | 523 void const *elem |
| 524 ) { | 524 ) { |
| 525 return cx_ll_insert(list, list->size, elem); | 525 return cx_ll_insert(list, list->size, elem); |
| 526 } | 526 } |
| 527 | 527 |
| 528 static int cx_pll_insert( | 528 static int cx_pll_insert( |
| 529 cx_list_s *list, | 529 cx_list_s *list, |
| 530 size_t index, | 530 size_t index, |
| 531 void *elem | 531 void const *elem |
| 532 ) { | 532 ) { |
| 533 return cx_ll_insert(list, index, &elem); | 533 return cx_ll_insert(list, index, &elem); |
| 534 } | 534 } |
| 535 | 535 |
| 536 static int cx_pll_add( | 536 static int cx_pll_add( |
| 537 cx_list_s *list, | 537 cx_list_s *list, |
| 538 void *elem | 538 void const *elem |
| 539 ) { | 539 ) { |
| 540 return cx_ll_insert(list, list->size, &elem); | 540 return cx_ll_insert(list, list->size, &elem); |
| 541 } | 541 } |
| 542 | 542 |
| 543 static int cx_ll_remove( | 543 static int cx_ll_remove( |
| 562 | 562 |
| 563 return 0; | 563 return 0; |
| 564 } | 564 } |
| 565 | 565 |
| 566 static void *cx_ll_at( | 566 static void *cx_ll_at( |
| 567 cx_list_s *list, | 567 cx_list_s const *list, |
| 568 size_t index | 568 size_t index |
| 569 ) { | 569 ) { |
| 570 cx_linked_list *ll = (cx_linked_list *) list; | 570 cx_linked_list *ll = (cx_linked_list *) list; |
| 571 cx_linked_list_node *node = cx_ll_node_at(ll, index); | 571 cx_linked_list_node *node = cx_ll_node_at(ll, index); |
| 572 return node == NULL ? NULL : node->payload; | 572 return node == NULL ? NULL : node->payload; |
| 573 } | 573 } |
| 574 | 574 |
| 575 static void *cx_pll_at( | 575 static void *cx_pll_at( |
| 576 cx_list_s *list, | 576 cx_list_s const *list, |
| 577 size_t index | 577 size_t index |
| 578 ) { | 578 ) { |
| 579 cx_linked_list *ll = (cx_linked_list *) list; | 579 cx_linked_list *ll = (cx_linked_list *) list; |
| 580 cx_linked_list_node *node = cx_ll_node_at(ll, index); | 580 cx_linked_list_node *node = cx_ll_node_at(ll, index); |
| 581 return node == NULL ? NULL : *(void **) node->payload; | 581 return node == NULL ? NULL : *(void **) node->payload; |
| 582 } | 582 } |
| 583 | 583 |
| 584 static size_t cx_ll_find( | 584 static size_t cx_ll_find( |
| 585 cx_list_s *list, | 585 cx_list_s const *list, |
| 586 void *elem | 586 void const *elem |
| 587 ) { | 587 ) { |
| 588 return cx_linked_list_find(((cx_linked_list *) list)->begin, | 588 return cx_linked_list_find(((cx_linked_list *) list)->begin, |
| 589 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, | 589 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, |
| 590 false, list->cmpfunc, elem); | 590 false, list->cmpfunc, elem); |
| 591 } | 591 } |
| 592 | 592 |
| 593 static size_t cx_pll_find( | 593 static size_t cx_pll_find( |
| 594 cx_list_s *list, | 594 cx_list_s const *list, |
| 595 void *elem | 595 void const *elem |
| 596 ) { | 596 ) { |
| 597 return cx_linked_list_find(((cx_linked_list *) list)->begin, | 597 return cx_linked_list_find(((cx_linked_list *) list)->begin, |
| 598 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, | 598 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, |
| 599 true, list->cmpfunc, elem); | 599 true, list->cmpfunc, elem); |
| 600 } | 600 } |
| 612 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, | 612 CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA, |
| 613 true, list->cmpfunc); | 613 true, list->cmpfunc); |
| 614 } | 614 } |
| 615 | 615 |
| 616 static int cx_ll_compare( | 616 static int cx_ll_compare( |
| 617 cx_list_s *list, | 617 cx_list_s const *list, |
| 618 cx_list_s *other | 618 cx_list_s const *other |
| 619 ) { | 619 ) { |
| 620 cx_linked_list *left = (cx_linked_list *) list; | 620 cx_linked_list *left = (cx_linked_list *) list; |
| 621 cx_linked_list *right = (cx_linked_list *) other; | 621 cx_linked_list *right = (cx_linked_list *) other; |
| 622 return cx_linked_list_compare(left->begin, right->begin, | 622 return cx_linked_list_compare(left->begin, right->begin, |
| 623 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, | 623 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, |
| 624 false, list->cmpfunc); | 624 false, list->cmpfunc); |
| 625 } | 625 } |
| 626 | 626 |
| 627 static int cx_pll_compare( | 627 static int cx_pll_compare( |
| 628 cx_list_s *list, | 628 cx_list_s const *list, |
| 629 cx_list_s *other | 629 cx_list_s const *other |
| 630 ) { | 630 ) { |
| 631 cx_linked_list *left = (cx_linked_list *) list; | 631 cx_linked_list *left = (cx_linked_list *) list; |
| 632 cx_linked_list *right = (cx_linked_list *) other; | 632 cx_linked_list *right = (cx_linked_list *) other; |
| 633 return cx_linked_list_compare(left->begin, right->begin, | 633 return cx_linked_list_compare(left->begin, right->begin, |
| 634 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, | 634 CX_LL_LOC_NEXT, CX_LL_LOC_DATA, |
| 701 CxList cxLinkedListFromArray( | 701 CxList cxLinkedListFromArray( |
| 702 CxAllocator allocator, | 702 CxAllocator allocator, |
| 703 CxListComparator comparator, | 703 CxListComparator comparator, |
| 704 size_t item_size, | 704 size_t item_size, |
| 705 size_t num_items, | 705 size_t num_items, |
| 706 const void *array | 706 void const *array |
| 707 ) { | 707 ) { |
| 708 CxList list = cxLinkedListCreate(allocator, comparator, item_size); | 708 CxList list = cxLinkedListCreate(allocator, comparator, item_size); |
| 709 if (list == NULL) return NULL; | 709 if (list == NULL) return NULL; |
| 710 for (size_t i = 0; i < num_items; i++) { | 710 for (size_t i = 0; i < num_items; i++) { |
| 711 if (0 != cxListAdd(list, ((const unsigned char *) array) + i * item_size)) { | 711 if (0 != cxListAdd(list, ((const unsigned char *) array) + i * item_size)) { |
