Mercurial > hg > ucx / file comparison

comparison: tests/test_list.c

tests/test_list.c

changeset 961
bc8b7c5f55fb
parent 912
9533fc293aea
child 962
cd418898af5c
equal deleted inserted replaced
960:a8a5f3dd5c3d 961:bc8b7c5f55fb
195 struct node *next; 195 struct node *next;
196 struct node *prev; 196 struct node *prev;
197 int data; 197 int data;
198 } node; 198 } node;
199 199
200 static int test_cmp_node(const void *l, const void *r) {
201 const node *left = l;
202 const node *right = r;
203 return left->data - right->data;
204 }
205
200 const ptrdiff_t loc_prev = offsetof(struct node, prev); 206 const ptrdiff_t loc_prev = offsetof(struct node, prev);
201 const ptrdiff_t loc_next = offsetof(struct node, next); 207 const ptrdiff_t loc_next = offsetof(struct node, next);
202 const ptrdiff_t loc_data = offsetof(struct node, data); 208 const ptrdiff_t loc_data = offsetof(struct node, data);
203 209
204 static node *create_nodes_test_data(size_t len) { 210 static node *create_nodes_test_data(size_t len) {
566 CX_TEST_ASSERT(nodes[3].prev == NULL); 572 CX_TEST_ASSERT(nodes[3].prev == NULL);
567 CX_TEST_ASSERT(nodes[4].next == &nodes[0]); 573 CX_TEST_ASSERT(nodes[4].next == &nodes[0]);
568 } 574 }
569 } 575 }
570 576
577 CX_TEST(test_linked_list_insert_sorted) {
578 node nodes[5] = {0};
579 void *begin, *end;
580 nodes[0].data = 3;
581 nodes[1].data = 6;
582 nodes[2].data = 10;
583 nodes[3].data = 11;
584 nodes[4].data = 15;
585 for (unsigned i = 0 ; i < 4 ; i++) {
586 cx_linked_list_link(&nodes[i], &nodes[i+1], loc_prev, loc_next);
587 }
588 begin = &nodes[0];
589 end = &nodes[4];
590 CX_TEST_DO {
591 // insert a single node
592 node new_node = {0};
593 new_node.data = 5;
594 cx_linked_list_insert_sorted(
595 &begin, &end,
596 loc_prev, loc_next,
597 &new_node, test_cmp_node
598 );
599 CX_TEST_ASSERT(new_node.prev == &nodes[0]);
600 CX_TEST_ASSERT(new_node.next == &nodes[1]);
601 CX_TEST_ASSERT(nodes[0].next == &new_node);
602 CX_TEST_ASSERT(nodes[1].prev == &new_node);
603 CX_TEST_ASSERT(begin == &nodes[0]);
604 CX_TEST_ASSERT(end == &nodes[4]);
605
606 // insert a new beginning node
607 node new_begin = {0};
608 new_begin.data = 1;
609 cx_linked_list_insert_sorted(
610 &begin, &end,
611 loc_prev, loc_next,
612 &new_begin, test_cmp_node
613 );
614 CX_TEST_ASSERT(new_begin.prev == NULL);
615 CX_TEST_ASSERT(new_begin.next == &nodes[0]);
616 CX_TEST_ASSERT(nodes[0].prev == &new_begin);
617 CX_TEST_ASSERT(begin == &new_begin);
618 CX_TEST_ASSERT(end == &nodes[4]);
619
620 // now insert a chain
621 node chain_start = {NULL, NULL, 8};
622 node chain_mid = {NULL, NULL, 14};
623 node chain_end = {NULL, NULL, 17};
624 cx_linked_list_link(&chain_start, &chain_mid, loc_prev, loc_next);
625 cx_linked_list_link(&chain_mid, &chain_end, loc_prev, loc_next);
626
627 cx_linked_list_insert_sorted_chain(
628 &begin, &end,
629 loc_prev, loc_next,
630 &chain_start, test_cmp_node
631 );
632
633 CX_TEST_ASSERT(chain_start.prev == &nodes[1]);
634 CX_TEST_ASSERT(chain_start.next == &nodes[2]);
635 CX_TEST_ASSERT(chain_mid.prev == &nodes[3]);
636 CX_TEST_ASSERT(chain_mid.next == &nodes[4]);
637 CX_TEST_ASSERT(chain_end.prev == &nodes[4]);
638 CX_TEST_ASSERT(chain_end.next == NULL);
639 CX_TEST_ASSERT(begin == &new_begin);
640 CX_TEST_ASSERT(end == &chain_end);
641 }
642 }
643
571 CX_TEST(test_linked_list_first) { 644 CX_TEST(test_linked_list_first) {
572 node *testdata = create_nodes_test_data(3); 645 node *testdata = create_nodes_test_data(3);
573 void *begin = testdata; 646 void *begin = testdata;
574 CX_TEST_DO { 647 CX_TEST_DO {
575 CX_TEST_ASSERT(begin == cx_linked_list_first(testdata, loc_prev)); 648 CX_TEST_ASSERT(begin == cx_linked_list_first(testdata, loc_prev));
630 } 703 }
631 // list is not intact anymore, we have to free nodes individually 704 // list is not intact anymore, we have to free nodes individually
632 free(first); 705 free(first);
633 free(second); 706 free(second);
634 free(third); 707 free(third);
708 }
709
710 CX_TEST(test_linked_list_remove_chain) {
711 node *testdata = create_nodes_test_data(5);
712 assign_nodes_test_data(testdata, 2, 4, 6, 8, 10);
713 void *begin = testdata;
714 void *end = cx_linked_list_last(testdata, loc_next);
715 void *orig_end = end;
716 // remember what we need to free
717 node *kill_list[5];
718 kill_list[0] = testdata;
719 for (unsigned i = 1 ; i < 5 ; i++) {
720 kill_list[i] = kill_list[i-1]->next;
721 }
722
723 CX_TEST_DO {
724 // remove chain, but pretend that we don't have a prev pointer!
725 size_t result = cx_linked_list_remove_chain(
726 &begin, &end, -1, loc_next,
727 cx_linked_list_at(begin, 0, loc_next, 2),
728 2
729 );
730 CX_TEST_ASSERT(result == 2);
731 CX_TEST_ASSERT(begin == testdata);
732 CX_TEST_ASSERT(end == orig_end);
733 node *new_idx2 = cx_linked_list_at(begin, 0, loc_next, 2);
734 CX_TEST_ASSERT(new_idx2->data == 10);
735 CX_TEST_ASSERT(new_idx2->next == NULL);
736 // we pretended we don't have prev, so it still points to 8!
737 CX_TEST_ASSERT(new_idx2->prev->data == 8);
738
739 // remove last elements and try to remove more than we have
740 result = cx_linked_list_remove_chain(
741 &begin, &end, -1, loc_next,
742 cx_linked_list_at(begin, 0, loc_next, 2),
743 2
744 );
745 CX_TEST_ASSERT(result == 1);
746 CX_TEST_ASSERT(begin == testdata);
747 CX_TEST_ASSERT(end == testdata->next);
748 CX_TEST_ASSERT(NULL == testdata->next->next);
749 }
750
751 for (unsigned i = 0 ; i < 5 ; i++) {
752 free(kill_list[i]);
753 }
635 } 754 }
636 755
637 CX_TEST(test_linked_list_size) { 756 CX_TEST(test_linked_list_size) {
638 node *td5 = create_nodes_test_data(5); 757 node *td5 = create_nodes_test_data(5);
639 node *td13 = create_nodes_test_data(13); 758 node *td13 = create_nodes_test_data(13);
1258 CX_TEST_ASSERT(*(int *) cxListAt(list, 1) == testdata[3]); 1377 CX_TEST_ASSERT(*(int *) cxListAt(list, 1) == testdata[3]);
1259 CX_TEST_ASSERT(cxListRemove(list, testdata_len) != 0); 1378 CX_TEST_ASSERT(cxListRemove(list, testdata_len) != 0);
1260 free(testdata); 1379 free(testdata);
1261 }) 1380 })
1262 1381
1382 static unsigned test_remove_array_destr_ctr;
1383 static void test_remove_array_destr(__attribute__((__unused__)) void *d) {
1384 test_remove_array_destr_ctr++;
1385 }
1386
1387 roll_out_test_combos(remove_array, {
1388 const size_t testdata_len = 32;
1389 int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len);
1390 cxDefineDestructor(list, test_remove_array_destr);
1391 test_remove_array_destr_ctr = 0;
1392
1393 // first, remove and get - no destructor must be called
1394 int targete[8];
1395 int *targetp[8];
1396 memset(targete, 0, sizeof(targete));
1397 memset(targetp, 0, sizeof(targetp));
1398 void *target = isptrlist ? (void*) targetp : targete;
1399 CX_TEST_ASSERT(8 == cxListRemoveArrayAndGet(list, 8, 8, target));
1400 CX_TEST_ASSERT(0 == test_remove_array_destr_ctr);
1401 CX_TEST_ASSERT(24 == cxListSize(list));
1402 for (unsigned int i = 0 ; i < 8 ; i++) {
1403 CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[i]);
1404 }
1405 for (unsigned int i = 8 ; i < 24 ; i++) {
1406 CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[8+i]);
1407 }
1408 for (unsigned int i = 0 ; i < 8 ; i++) {
1409 if (isptrlist) {
1410 CX_TEST_ASSERT(targetp[i] == &testdata[8 + i]);
1411 } else {
1412 CX_TEST_ASSERT(targete[i] == testdata[8 + i]);
1413 }
1414 }
1415
1416 // now, just remove - destructor must be called
1417 CX_TEST_ASSERT(8 == cxListRemoveArray(list, 8, 8));
1418 CX_TEST_ASSERT(8 == test_remove_array_destr_ctr);
1419 CX_TEST_ASSERT(16 == cxListSize(list));
1420 for (unsigned int i = 0 ; i < 8 ; i++) {
1421 CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[i]);
1422 }
1423 for (unsigned int i = 8 ; i < 16 ; i++) {
1424 CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[16+i]);
1425 }
1426
1427 // finally, remove and get out of bounds
1428 test_remove_array_destr_ctr = 0;
1429 memset(targete, 0, sizeof(targete));
1430 memset(targetp, 0, sizeof(targetp));
1431 CX_TEST_ASSERT(4 == cxListRemoveArrayAndGet(list, 12, 8, target));
1432 CX_TEST_ASSERT(0 == test_remove_array_destr_ctr);
1433 CX_TEST_ASSERT(12 == cxListSize(list));
1434 for (unsigned int i = 0 ; i < 8 ; i++) {
1435 CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[i]);
1436 }
1437 for (unsigned int i = 8 ; i < 12 ; i++) {
1438 CX_TEST_ASSERT((*(int*)cxListAt(list, i)) == testdata[16+i]);
1439 }
1440 for (unsigned int i = 0 ; i < 4 ; i++) {
1441 if (isptrlist) {
1442 CX_TEST_ASSERT(targetp[i] == &testdata[28 + i]);
1443 } else {
1444 CX_TEST_ASSERT(targete[i] == testdata[28 + i]);
1445 }
1446 }
1447 for (unsigned int i = 4 ; i < 8 ; i++) {
1448 if (isptrlist) {
1449 CX_TEST_ASSERT(targetp[i] == 0);
1450 } else {
1451 CX_TEST_ASSERT(targete[i] == 0);
1452 }
1453 }
1454
1455 free(testdata);
1456 })
1457
1263 roll_out_test_combos(find_remove, { 1458 roll_out_test_combos(find_remove, {
1264 const size_t testdata_len = 250; 1459 const size_t testdata_len = 250;
1265 int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len); 1460 int *testdata = int_test_data_added_to_list(list, isptrlist, testdata_len);
1266 1461
1267 int exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp) 1462 int exp = rand() % testdata_len; // NOLINT(cert-msc50-cpp)
1644 cx_test_register(suite, test_list_parl_insert_array); 1839 cx_test_register(suite, test_list_parl_insert_array);
1645 cx_test_register(suite, test_list_arl_insert_sorted); 1840 cx_test_register(suite, test_list_arl_insert_sorted);
1646 cx_test_register(suite, test_list_parl_insert_sorted); 1841 cx_test_register(suite, test_list_parl_insert_sorted);
1647 cx_test_register(suite, test_list_arl_remove); 1842 cx_test_register(suite, test_list_arl_remove);
1648 cx_test_register(suite, test_list_parl_remove); 1843 cx_test_register(suite, test_list_parl_remove);
1844 cx_test_register(suite, test_list_arl_remove_array);
1845 cx_test_register(suite, test_list_parl_remove_array);
1649 cx_test_register(suite, test_list_arl_find_remove); 1846 cx_test_register(suite, test_list_arl_find_remove);
1650 cx_test_register(suite, test_list_parl_find_remove); 1847 cx_test_register(suite, test_list_parl_find_remove);
1651 cx_test_register(suite, test_list_arl_clear); 1848 cx_test_register(suite, test_list_arl_clear);
1652 cx_test_register(suite, test_list_parl_clear); 1849 cx_test_register(suite, test_list_parl_clear);
1653 cx_test_register(suite, test_list_arl_at); 1850 cx_test_register(suite, test_list_arl_at);
1711 cx_test_register(suite, test_linked_list_compare); 1908 cx_test_register(suite, test_linked_list_compare);
1712 cx_test_register(suite, test_linked_list_add); 1909 cx_test_register(suite, test_linked_list_add);
1713 cx_test_register(suite, test_linked_list_prepend); 1910 cx_test_register(suite, test_linked_list_prepend);
1714 cx_test_register(suite, test_linked_list_insert); 1911 cx_test_register(suite, test_linked_list_insert);
1715 cx_test_register(suite, test_linked_list_insert_chain); 1912 cx_test_register(suite, test_linked_list_insert_chain);
1913 cx_test_register(suite, test_linked_list_insert_sorted);
1716 cx_test_register(suite, test_linked_list_first); 1914 cx_test_register(suite, test_linked_list_first);
1717 cx_test_register(suite, test_linked_list_last); 1915 cx_test_register(suite, test_linked_list_last);
1718 cx_test_register(suite, test_linked_list_prev); 1916 cx_test_register(suite, test_linked_list_prev);
1719 cx_test_register(suite, test_linked_list_remove); 1917 cx_test_register(suite, test_linked_list_remove);
1918 cx_test_register(suite, test_linked_list_remove_chain);
1720 cx_test_register(suite, test_linked_list_size); 1919 cx_test_register(suite, test_linked_list_size);
1721 cx_test_register(suite, test_linked_list_sort_empty); 1920 cx_test_register(suite, test_linked_list_sort_empty);
1722 cx_test_register(suite, test_linked_list_sort); 1921 cx_test_register(suite, test_linked_list_sort);
1723 cx_test_register(suite, test_linked_list_reverse); 1922 cx_test_register(suite, test_linked_list_reverse);
1724 1923
1738 cx_test_register(suite, test_list_pll_insert_array); 1937 cx_test_register(suite, test_list_pll_insert_array);
1739 cx_test_register(suite, test_list_ll_insert_sorted); 1938 cx_test_register(suite, test_list_ll_insert_sorted);
1740 cx_test_register(suite, test_list_pll_insert_sorted); 1939 cx_test_register(suite, test_list_pll_insert_sorted);
1741 cx_test_register(suite, test_list_ll_remove); 1940 cx_test_register(suite, test_list_ll_remove);
1742 cx_test_register(suite, test_list_pll_remove); 1941 cx_test_register(suite, test_list_pll_remove);
1942 cx_test_register(suite, test_list_ll_remove_array);
1943 cx_test_register(suite, test_list_pll_remove_array);
1743 cx_test_register(suite, test_list_ll_find_remove); 1944 cx_test_register(suite, test_list_ll_find_remove);
1744 cx_test_register(suite, test_list_pll_find_remove); 1945 cx_test_register(suite, test_list_pll_find_remove);
1745 cx_test_register(suite, test_list_ll_clear); 1946 cx_test_register(suite, test_list_ll_clear);
1746 cx_test_register(suite, test_list_pll_clear); 1947 cx_test_register(suite, test_list_pll_clear);
1747 cx_test_register(suite, test_list_ll_at); 1948 cx_test_register(suite, test_list_ll_at);

Mercurial Repository: ucx

mercurial