Mercurial > hg > ucx / file comparison

comparison: tests/test_tree.c

tests/test_tree.c

changeset 1690
7d41291b3095
parent 1689
a5b7cf49dea7
equal deleted inserted replaced
1689:a5b7cf49dea7 1690:7d41291b3095
441 441
442 int s; 442 int s;
443 int r; 443 int r;
444 tree_node *n; 444 tree_node *n;
445 CX_TEST_DO { 445 CX_TEST_DO {
446 // special case: search an empty tree
447 n = (void*)0x1337;
448 r = cx_tree_search(NULL, 0, &s, test_tree_search_function,
449 (void **) &n, tree_children(tree_node));
450 CX_TEST_ASSERT(r < 0);
451 CX_TEST_ASSERT(n == NULL);
452
453 // search for the test data (exact matches)
446 for (unsigned i = 0 ; i <= 10 ; i++) { 454 for (unsigned i = 0 ; i <= 10 ; i++) {
447 s = testdata[i]; 455 s = testdata[i];
448 r = cx_tree_search(&root, 0, &s, test_tree_search_function, 456 r = cx_tree_search(&root, 0, &s, test_tree_search_function,
449 (void **) &n, tree_children(tree_node)); 457 (void **) &n, tree_children(tree_node));
450 CX_TEST_ASSERT(r == 0); 458 CX_TEST_ASSERT(r == 0);
1047 CX_TEST_ASSERT(iter.queue_next == NULL); 1055 CX_TEST_ASSERT(iter.queue_next == NULL);
1048 CX_TEST_ASSERT(iter.queue_last == NULL); 1056 CX_TEST_ASSERT(iter.queue_last == NULL);
1049 } 1057 }
1050 } 1058 }
1051 1059
1060 CX_TEST(test_tree_visitor_create_for_empty_tree) {
1061 CX_TEST_DO {
1062 CxTreeIterator iter = cx_tree_visitor(NULL, tree_children(tree_node));
1063 CX_TEST_ASSERT(!iter.visit_on_exit);
1064 CX_TEST_ASSERT(!iter.exiting);
1065 CX_TEST_ASSERT(iter.counter == 0);
1066 CX_TEST_ASSERT(iter.node == NULL);
1067 CX_TEST_ASSERT(!iter.base.allow_remove);
1068 CX_TEST_ASSERT(!iter.base.remove);
1069 CX_TEST_ASSERT(iter.queue_next == NULL);
1070 CX_TEST_ASSERT(iter.queue_last == 0);
1071 CX_TEST_ASSERT(iter.depth == 0);
1072 CX_TEST_ASSERT(iter.loc_next == offsetof(tree_node, next));
1073 CX_TEST_ASSERT(iter.loc_children == offsetof(tree_node, children));
1074 CX_TEST_ASSERT(!cxIteratorValid(iter));
1075 // disposing this iterator should also be harmless
1076 cxTreeIteratorDispose(&iter);
1077 }
1078 }
1079
1052 CX_TEST(test_tree_visitor_no_children) { 1080 CX_TEST(test_tree_visitor_no_children) {
1053 tree_node root = {0}; 1081 tree_node root = {0};
1054 1082
1055 CX_TEST_DO { 1083 CX_TEST_DO {
1056 CxTreeIterator iter = cx_tree_visitor(&root, tree_children(tree_node)); 1084 CxTreeIterator iter = cx_tree_visitor(&root, tree_children(tree_node));
1371 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1399 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1372 } 1400 }
1373 cx_testing_allocator_destroy(&talloc); 1401 cx_testing_allocator_destroy(&talloc);
1374 } 1402 }
1375 1403
1404 CX_TEST(test_tree_high_create_root) {
1405 CxTestingAllocator talloc;
1406 cx_testing_allocator_init(&talloc);
1407 CX_TEST_DO {
1408 CxTree *tree = cxTreeCreate(
1409 &talloc.base,
1410 sizeof(tree_node_file),
1411 CX_STORE_POINTERS,
1412 NULL, -1,
1413 cx_tree_node_layout(tree_node_file)
1414 );
1415
1416 CX_TEST_ASSERT(tree->root == NULL);
1417 // create root without data
1418 tree_node_file *root = cxTreeCreateRoot(tree);
1419 CX_TEST_ASSERT(root != NULL);
1420 CX_TEST_ASSERT(root == tree->root);
1421 // re-create same root (does nothing)
1422 tree_node_file *root2 = cxTreeCreateRoot(tree);
1423 CX_TEST_ASSERT(root2 == root);
1424
1425 // next test
1426 cxTreeClear(tree);
1427
1428 // try to create with data, but loc_data is not known
1429 root = cxTreeCreateRootData(tree, "/");
1430 CX_TEST_ASSERT(root == NULL);
1431
1432 // set the loc_data
1433 tree->loc_data = offsetof(tree_node_file, path);
1434 root = cxTreeCreateRootData(tree, "/");
1435 CX_TEST_ASSERT(root != NULL);
1436 CX_TEST_ASSERT(strcmp(root->path, "/") == 0);
1437
1438 cxTreeFree(tree);
1439 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1440 }
1441 }
1442
1443 CX_TEST(test_tree_high_set_root) {
1444 CxTestingAllocator talloc;
1445 cx_testing_allocator_init(&talloc);
1446 CX_TEST_DO {
1447 CxTree *tree = cxTreeCreate(
1448 &talloc.base,
1449 sizeof(tree_node_file),
1450 CX_STORE_POINTERS,
1451 NULL, -1,
1452 cx_tree_node_layout(tree_node_file)
1453 );
1454
1455 CX_TEST_ASSERT(tree->root == NULL);
1456
1457 tree_node_file *root = cxTreeCreateRoot(tree);
1458 CX_TEST_ASSERT(root != NULL);
1459 CX_TEST_ASSERT(root == tree->root);
1460
1461 // create a different root externally
1462 tree_node_file *root2 = cxZalloc(&talloc.base, sizeof(tree_node_file));
1463
1464 // replace the root
1465 tree_node_file *old = cxTreeSetRoot(tree, root2);
1466 CX_TEST_ASSERT(old == root);
1467
1468 // free the tree, check that there is memory leaking
1469 cxTreeFree(tree);
1470 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
1471
1472 // free the old root, check that memory is fine
1473 cxFree(&talloc.base, old);
1474 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1475 }
1476 }
1477
1376 CX_TEST(test_tree_high_tree_depth) { 1478 CX_TEST(test_tree_high_tree_depth) {
1377 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0}; 1479 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0};
1378 cx_tree_add(&root, &child1, tree_node_layout); 1480 cx_tree_add(&root, &child1, tree_node_layout);
1379 cx_tree_add(&root, &child2, tree_node_layout); 1481 cx_tree_add(&root, &child2, tree_node_layout);
1380 cx_tree_add(&child1, &child3, tree_node_layout); 1482 cx_tree_add(&child1, &child3, tree_node_layout);
1614 CX_TEST_CALL_SUBROUTINE(validate_tree_high_add_find_destroy_nodes, alloc, true); 1716 CX_TEST_CALL_SUBROUTINE(validate_tree_high_add_find_destroy_nodes, alloc, true);
1615 CX_TEST_CALL_SUBROUTINE(validate_tree_high_add_find_destroy_nodes, alloc, false); 1717 CX_TEST_CALL_SUBROUTINE(validate_tree_high_add_find_destroy_nodes, alloc, false);
1616 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1718 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1617 } 1719 }
1618 cx_testing_allocator_destroy(&talloc); 1720 cx_testing_allocator_destroy(&talloc);
1721 }
1722
1723 CX_TEST(test_tree_high_add_find_without_loc_data) {
1724 CxTestingAllocator talloc;
1725 cx_testing_allocator_init(&talloc);
1726 CxAllocator *alloc = &talloc.base;
1727 CX_TEST_DO {
1728 CxTree *tree = cxTreeCreate(alloc,
1729 sizeof(tree_node_file),
1730 CX_STORE_POINTERS,
1731 NULL, offsetof(tree_node_file, path),
1732 cx_tree_node_layout(tree_node_file)
1733 );
1734 cxSetCompareFunc(tree, strcmp);
1735 tree_node_file *root = cxTreeCreateRootData(tree, "/");
1736 tree_node_file *home = cxTreeAddData(tree, root, "/home/");
1737 tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
1738 cxTreeAddData(tree, foo, "/home/foo/bar/");
1739 tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
1740 cxTreeAddData(tree, usr, "/usr/lib/");
1741
1742 void *found = cxTreeFind(tree, "/home/foo/", true);
1743 CX_TEST_ASSERT(found == foo);
1744
1745 // now remove the loc_data
1746 tree->loc_data = -1;
1747 found = cxTreeFind(tree, "/home/foo/", true);
1748 CX_TEST_ASSERT(found == NULL);
1749
1750 CX_TEST_ASSERT(NULL == cxTreeAddData(tree, root, "/usr/local/"));
1751
1752 cxTreeFree(tree);
1753 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1754 }
1755 cx_testing_allocator_destroy(&talloc);
1756 }
1757
1758 CX_TEST(test_tree_high_find_max_depth) {
1759 CxTree *tree = cxTreeCreate(NULL,
1760 sizeof(tree_node_file),
1761 CX_STORE_POINTERS,
1762 NULL, offsetof(tree_node_file, path),
1763 cx_tree_node_layout(tree_node_file)
1764 );
1765 cxSetCompareFunc(tree, strcmp);
1766 tree_node_file *root = cxTreeCreateRootData(tree, "/");
1767 tree_node_file *home = cxTreeAddData(tree, root, "/home/");
1768 tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
1769 tree_node_file *bar = cxTreeAddData(tree, foo, "/home/foo/bar/");
1770 tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
1771 cxTreeAddData(tree, usr, "/usr/lib/");
1772 CX_TEST_DO {
1773 CX_TEST_ASSERT(bar == cxTreeFindInSubtree(tree, "/home/foo/bar/", tree->root, 4, true));
1774 CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/home/foo/bar/", tree->root, 3, true));
1775 CX_TEST_ASSERT(bar == cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 3, true));
1776 CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/home/foo/bar/", home, 2, true));
1777 }
1778 cxTreeFree(tree);
1779 }
1780
1781 CX_TEST(test_tree_high_find_fast) {
1782 CxTree *tree = cxTreeCreate(NULL,
1783 sizeof(tree_node_file),
1784 CX_STORE_POINTERS,
1785 NULL, offsetof(tree_node_file, path),
1786 cx_tree_node_layout(tree_node_file)
1787 );
1788 cxSetCompareFunc(tree, strcmp);
1789 tree_node_file *root = cxTreeCreateRootData(tree, "/");
1790 tree_node_file *home = cxTreeAddData(tree, root, "/home/");
1791 tree_node_file *foo = cxTreeAddData(tree, home, "/home/foo/");
1792 tree_node_file *bar = cxTreeAddData(tree, foo, "/home/foo/bar/");
1793 tree_node_file *baz = cxTreeAddData(tree, home, "/home/baz/");
1794 tree_node_file *usr = cxTreeAddData(tree, root, "/usr/");
1795 tree_node_file *lib = cxTreeAddData(tree, usr, "/usr/lib/");
1796 CX_TEST_DO {
1797 // test that loc_data not needed for FindFast!
1798 tree->loc_data = -1;
1799
1800 // find from root
1801 CX_TEST_ASSERT(root == cxTreeFindFast(tree, "/",
1802 tree_node_file_search_func));
1803 CX_TEST_ASSERT(home == cxTreeFindFast(tree, "/home/",
1804 tree_node_file_search_func));
1805 CX_TEST_ASSERT(foo == cxTreeFindFast(tree, "/home/foo/",
1806 tree_node_file_search_func));
1807 CX_TEST_ASSERT(bar == cxTreeFindFast(tree, "/home/foo/bar/",
1808 tree_node_file_search_func));
1809 CX_TEST_ASSERT(usr == cxTreeFindFast(tree, "/usr/",
1810 tree_node_file_search_func));
1811 CX_TEST_ASSERT(lib == cxTreeFindFast(tree, "/usr/lib/",
1812 tree_node_file_search_func));
1813
1814 // find from correct subtree
1815 CX_TEST_ASSERT(foo == cxTreeFindFastInSubtree(tree, "/home/foo/",
1816 tree_node_file_search_func, home, 0));
1817 CX_TEST_ASSERT(bar == cxTreeFindFastInSubtree(tree, "/home/foo/bar/",
1818 tree_node_file_search_func, home, 0));
1819 CX_TEST_ASSERT(lib == cxTreeFindFastInSubtree(tree, "/usr/lib/",
1820 tree_node_file_search_func, usr, 0));
1821
1822 // find in wrong subtree
1823 CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/",
1824 tree_node_file_search_func, usr, 0));
1825 CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/bar/",
1826 tree_node_file_search_func, baz, 0));
1827 CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/usr/lib/",
1828 tree_node_file_search_func, home, 0));
1829
1830 // some tests with max depth
1831 // -------------------------
1832 CX_TEST_ASSERT(bar == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, tree->root, 4));
1833 CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, tree->root, 3));
1834 CX_TEST_ASSERT(bar == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, home, 3));
1835 CX_TEST_ASSERT(NULL == cxTreeFindFastInSubtree(tree, "/home/foo/bar/", tree_node_file_search_func, home, 2));
1836 }
1837 cxTreeFree(tree);
1619 } 1838 }
1620 1839
1621 CX_TEST(test_tree_high_remove_or_destroy_root) { 1840 CX_TEST(test_tree_high_remove_or_destroy_root) {
1622 CxTestingAllocator talloc; 1841 CxTestingAllocator talloc;
1623 cx_testing_allocator_init(&talloc); 1842 cx_testing_allocator_init(&talloc);
1726 actual_order[iter.counter-1] = p->path; 1945 actual_order[iter.counter-1] = p->path;
1727 } 1946 }
1728 CX_TEST_ASSERT(iter.counter == 9); 1947 CX_TEST_ASSERT(iter.counter == 9);
1729 for (unsigned i = 0; i < 9; i++) { 1948 for (unsigned i = 0; i < 9; i++) {
1730 CX_TEST_ASSERT(strcmp(expected_order[i], actual_order[i]) == 0); 1949 CX_TEST_ASSERT(strcmp(expected_order[i], actual_order[i]) == 0);
1950 }
1951 }
1952 cxTreeFree(tree);
1953 }
1954
1955 CX_TEST(test_tree_high_iterator_large_depth) {
1956 CxTree *tree = cxTreeCreate(NULL,
1957 sizeof(tree_node),
1958 sizeof(int),
1959 NULL, offsetof(tree_node, data),
1960 tree_node_layout
1961 );
1962 int c = 0;
1963 tree_node *root = cxTreeCreateRootData(tree, &c);
1964 unsigned depths[6] = {10, 20, 15, 30, 25, 5};
1965 for (unsigned b = 0 ; b < 3 ; b++) {
1966 c++;
1967 tree_node *branch = cxTreeAddData(tree, root, &c);
1968 tree_node *p = branch;
1969 for (unsigned d = 0; d < depths[b*2+0] ; d++) {
1970 c++;
1971 p = cxTreeAddData(tree, p, &c);
1972 }
1973 p = branch;
1974 for (unsigned d = 0; d < depths[b*2+1] ; d++) {
1975 c++;
1976 p = cxTreeAddData(tree, p, &c);
1977 }
1978 }
1979 CX_TEST_DO {
1980 CX_TEST_ASSERT(cxTreeSize(tree) == 109);
1981 CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root) == 109);
1982 CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root->children) == 1+depths[0]+depths[1]);
1983 CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root->children->next) == 1+depths[2]+depths[3]);
1984 CX_TEST_ASSERT(cxTreeSubtreeSize(tree, root->children->next->next) == 1+depths[4]+depths[5]);
1985 CxTreeIterator iter = cxTreeIterate(tree, false);
1986 cx_foreach(tree_node*, n, iter) {
1987 CX_TEST_ASSERT((size_t)n->data == iter.counter - 1);
1731 } 1988 }
1732 } 1989 }
1733 cxTreeFree(tree); 1990 cxTreeFree(tree);
1734 } 1991 }
1735 1992
1796 cx_test_register(suite, test_tree_iterator_subtree_enter_and_exit); 2053 cx_test_register(suite, test_tree_iterator_subtree_enter_and_exit);
1797 cx_test_register(suite, test_tree_iterator_xml); 2054 cx_test_register(suite, test_tree_iterator_xml);
1798 cx_test_register(suite, test_tree_iterator_free_nodes); 2055 cx_test_register(suite, test_tree_iterator_free_nodes);
1799 cx_test_register(suite, test_tree_visitor_create_and_dispose); 2056 cx_test_register(suite, test_tree_visitor_create_and_dispose);
1800 cx_test_register(suite, test_tree_visitor); 2057 cx_test_register(suite, test_tree_visitor);
2058 cx_test_register(suite, test_tree_visitor_create_for_empty_tree);
1801 cx_test_register(suite, test_tree_visitor_no_children); 2059 cx_test_register(suite, test_tree_visitor_no_children);
1802 cx_test_register(suite, test_tree_visitor_no_branching); 2060 cx_test_register(suite, test_tree_visitor_no_branching);
1803 cx_test_register(suite, test_tree_visitor_subtree); 2061 cx_test_register(suite, test_tree_visitor_subtree);
1804 cx_test_register(suite, test_tree_visitor_continue); 2062 cx_test_register(suite, test_tree_visitor_continue);
1805 cx_test_register(suite, test_tree_iterator_continue); 2063 cx_test_register(suite, test_tree_iterator_continue);
1810 2068
1811 CxTestSuite *cx_test_suite_tree_high_level(void) { 2069 CxTestSuite *cx_test_suite_tree_high_level(void) {
1812 CxTestSuite *suite = cx_test_suite_new("tree (high level)"); 2070 CxTestSuite *suite = cx_test_suite_new("tree (high level)");
1813 2071
1814 cx_test_register(suite, test_tree_high_create); 2072 cx_test_register(suite, test_tree_high_create);
2073 cx_test_register(suite, test_tree_high_create_root);
2074 cx_test_register(suite, test_tree_high_set_root);
1815 cx_test_register(suite, test_tree_high_tree_depth); 2075 cx_test_register(suite, test_tree_high_tree_depth);
1816 cx_test_register(suite, test_tree_high_set_parent); 2076 cx_test_register(suite, test_tree_high_set_parent);
1817 cx_test_register(suite, test_tree_high_add_find_remove_nodes); 2077 cx_test_register(suite, test_tree_high_add_find_remove_nodes);
1818 cx_test_register(suite, test_tree_high_add_find_destroy_nodes); 2078 cx_test_register(suite, test_tree_high_add_find_destroy_nodes);
2079 cx_test_register(suite, test_tree_high_add_find_without_loc_data);
2080 cx_test_register(suite, test_tree_high_find_max_depth);
2081 cx_test_register(suite, test_tree_high_find_fast);
1819 cx_test_register(suite, test_tree_high_remove_or_destroy_root); 2082 cx_test_register(suite, test_tree_high_remove_or_destroy_root);
1820 cx_test_register(suite, test_tree_high_simple_destructor); 2083 cx_test_register(suite, test_tree_high_simple_destructor);
1821 cx_test_register(suite, test_tree_high_iterator); 2084 cx_test_register(suite, test_tree_high_iterator);
2085 cx_test_register(suite, test_tree_high_iterator_large_depth);
1822 cx_test_register(suite, test_tree_high_visitor); 2086 cx_test_register(suite, test_tree_high_visitor);
1823 2087
1824 return suite; 2088 return suite;
1825 } 2089 }

Mercurial Repository: ucx

mercurial