Mercurial > hg > ucx / file comparison

comparison: tests/test_tree.c

tests/test_tree.c

changeset 905
39aa4f106a71
parent 904
cdc49211d87f
child 906
b51e5268bd9b
equal deleted inserted replaced
904:cdc49211d87f 905:39aa4f106a71
90 return -1; 90 return -1;
91 } 91 }
92 } else { 92 } else {
93 return -1; 93 return -1;
94 } 94 }
95 }
96
97 static int tree_node_file_search_data(const void *l, const void *d) {
98 tree_node_file r;
99 r.path = d;
100 return tree_node_file_search(l, &r);
95 } 101 }
96 102
97 #define tree_node_layout \ 103 #define tree_node_layout \
98 offsetof(tree_node, parent), offsetof(tree_node, children), -1, \ 104 offsetof(tree_node, parent), offsetof(tree_node, children), -1, \
99 offsetof(tree_node, prev), offsetof(tree_node, next) 105 offsetof(tree_node, prev), offsetof(tree_node, next)
1538 CX_TEST_DO { 1544 CX_TEST_DO {
1539 CxTree *tree = cxTreeCreate( 1545 CxTree *tree = cxTreeCreate(
1540 &talloc.base, 1546 &talloc.base,
1541 tree_node_file_create_hl, 1547 tree_node_file_create_hl,
1542 tree_node_file_search, 1548 tree_node_file_search,
1549 tree_node_file_search_data,
1543 tree_node_file_layout 1550 tree_node_file_layout
1544 ); 1551 );
1545 CX_TEST_ASSERT(tree->cl != NULL); 1552 CX_TEST_ASSERT(tree->cl != NULL);
1546 CX_TEST_ASSERT(tree->allocator == &talloc.base); 1553 CX_TEST_ASSERT(tree->allocator == &talloc.base);
1547 CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl); 1554 CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl);
1548 CX_TEST_ASSERT(tree->search == tree_node_file_search); 1555 CX_TEST_ASSERT(tree->search == tree_node_file_search);
1556 CX_TEST_ASSERT(tree->search_data == tree_node_file_search_data);
1549 CX_TEST_ASSERT(tree->size == 0); 1557 CX_TEST_ASSERT(tree->size == 0);
1550 CX_TEST_ASSERT(tree->simple_destructor == NULL); 1558 CX_TEST_ASSERT(tree->simple_destructor == NULL);
1551 CX_TEST_ASSERT(tree->advanced_destructor == (cx_destructor_func2) cxFree); 1559 CX_TEST_ASSERT(tree->advanced_destructor == (cx_destructor_func2) cxFree);
1552 CX_TEST_ASSERT(tree->destructor_data == &talloc.base); 1560 CX_TEST_ASSERT(tree->destructor_data == &talloc.base);
1553 CX_TEST_ASSERT(tree->root == NULL); 1561 CX_TEST_ASSERT(tree->root == NULL);
1569 CX_TEST(test_tree_high_create_simple) { 1577 CX_TEST(test_tree_high_create_simple) {
1570 CX_TEST_DO { 1578 CX_TEST_DO {
1571 CxTree *tree = cxTreeCreateSimple( 1579 CxTree *tree = cxTreeCreateSimple(
1572 cxDefaultAllocator, 1580 cxDefaultAllocator,
1573 tree_node_file_create_hl, 1581 tree_node_file_create_hl,
1574 tree_node_file_search 1582 tree_node_file_search,
1583 tree_node_file_search_data
1575 ); 1584 );
1576 CX_TEST_ASSERT(tree->cl != NULL); 1585 CX_TEST_ASSERT(tree->cl != NULL);
1577 CX_TEST_ASSERT(tree->allocator == cxDefaultAllocator); 1586 CX_TEST_ASSERT(tree->allocator == cxDefaultAllocator);
1578 CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl); 1587 CX_TEST_ASSERT(tree->node_create == tree_node_file_create_hl);
1579 CX_TEST_ASSERT(tree->search == tree_node_file_search); 1588 CX_TEST_ASSERT(tree->search == tree_node_file_search);
1589 CX_TEST_ASSERT(tree->search_data == tree_node_file_search_data);
1580 CX_TEST_ASSERT(tree->size == 0); 1590 CX_TEST_ASSERT(tree->size == 0);
1581 CX_TEST_ASSERT(tree->simple_destructor == NULL); 1591 CX_TEST_ASSERT(tree->simple_destructor == NULL);
1582 CX_TEST_ASSERT(tree->advanced_destructor == (cx_destructor_func2) cxFree); 1592 CX_TEST_ASSERT(tree->advanced_destructor == (cx_destructor_func2) cxFree);
1583 CX_TEST_ASSERT(tree->destructor_data == cxDefaultAllocator); 1593 CX_TEST_ASSERT(tree->destructor_data == cxDefaultAllocator);
1584 CX_TEST_ASSERT(tree->root == NULL); 1594 CX_TEST_ASSERT(tree->root == NULL);
1595 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0}; 1605 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0};
1596 cx_tree_link(&root, &child1, tree_node_layout); 1606 cx_tree_link(&root, &child1, tree_node_layout);
1597 cx_tree_link(&root, &child2, tree_node_layout); 1607 cx_tree_link(&root, &child2, tree_node_layout);
1598 cx_tree_link(&child1, &child3, tree_node_layout); 1608 cx_tree_link(&child1, &child3, tree_node_layout);
1599 CX_TEST_DO { 1609 CX_TEST_DO {
1600 CxTree *tree = cxTreeCreateWrapped(&root, tree_node_layout); 1610 CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout);
1601 CX_TEST_ASSERT(tree->cl != NULL); 1611 CX_TEST_ASSERT(tree->cl != NULL);
1602 CX_TEST_ASSERT(tree->allocator == cxDefaultAllocator); 1612 CX_TEST_ASSERT(tree->allocator == cxDefaultAllocator);
1603 CX_TEST_ASSERT(tree->node_create == NULL); 1613 CX_TEST_ASSERT(tree->node_create == NULL);
1604 CX_TEST_ASSERT(tree->search == NULL); 1614 CX_TEST_ASSERT(tree->search == NULL);
1615 CX_TEST_ASSERT(tree->search_data == NULL);
1605 CX_TEST_ASSERT(tree->root == &root); 1616 CX_TEST_ASSERT(tree->root == &root);
1606 CX_TEST_ASSERT(tree->size == 4); 1617 CX_TEST_ASSERT(tree->size == 4);
1607 CX_TEST_ASSERT(tree->simple_destructor == NULL); 1618 CX_TEST_ASSERT(tree->simple_destructor == NULL);
1608 CX_TEST_ASSERT(tree->advanced_destructor == NULL); 1619 CX_TEST_ASSERT(tree->advanced_destructor == NULL);
1609 CX_TEST_ASSERT(tree->destructor_data == NULL); 1620 CX_TEST_ASSERT(tree->destructor_data == NULL);
1614 CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node, next)); 1625 CX_TEST_ASSERT(tree->loc_next == offsetof(tree_node, next));
1615 cxTreeDestroy(tree); 1626 cxTreeDestroy(tree);
1616 } 1627 }
1617 } 1628 }
1618 1629
1619 CX_TEST(test_tree_high_subtree_depth) { 1630 CX_TEST(test_tree_high_tree_depth) {
1620 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0}; 1631 tree_node root = {0}, child1 = {0}, child2 = {0}, child3 = {0};
1621 cx_tree_link(&root, &child1, tree_node_layout); 1632 cx_tree_link(&root, &child1, tree_node_layout);
1622 cx_tree_link(&root, &child2, tree_node_layout); 1633 cx_tree_link(&root, &child2, tree_node_layout);
1623 cx_tree_link(&child1, &child3, tree_node_layout); 1634 cx_tree_link(&child1, &child3, tree_node_layout);
1624 CxTree *tree = cxTreeCreateWrapped(&root, tree_node_layout); 1635 CxTree *tree = cxTreeCreateWrapped(cxDefaultAllocator, &root, tree_node_layout);
1625 CX_TEST_DO { 1636 CX_TEST_DO {
1637 CX_TEST_ASSERT(cxTreeDepth(tree) == 3);
1626 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3); 1638 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &root) == 3);
1627 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 2); 1639 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child1) == 2);
1628 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 1); 1640 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child2) == 1);
1629 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1); 1641 CX_TEST_ASSERT(cxTreeSubtreeDepth(tree, &child3) == 1);
1642
1643 CxTree *empty = cxTreeCreate(
1644 cxDefaultAllocator,
1645 tree_node_file_create_hl,
1646 tree_node_file_search,
1647 tree_node_file_search_data,
1648 tree_node_file_layout
1649 );
1650 CX_TEST_ASSERT(cxTreeDepth(empty) == 0);
1651 cxTreeDestroy(empty);
1630 } 1652 }
1631 cxTreeDestroy(tree); 1653 cxTreeDestroy(tree);
1632 } 1654 }
1633 1655
1634 CX_TEST(test_tree_high_insert_one) { 1656 CX_TEST(test_tree_high_insert_one) {
1636 cx_testing_allocator_init(&talloc); 1658 cx_testing_allocator_init(&talloc);
1637 CxAllocator *alloc = &talloc.base; 1659 CxAllocator *alloc = &talloc.base;
1638 1660
1639 CX_TEST_DO { 1661 CX_TEST_DO {
1640 CxTree *tree = cxTreeCreate( 1662 CxTree *tree = cxTreeCreate(
1641 alloc, tree_node_file_create_hl, tree_node_file_search, 1663 alloc, tree_node_file_create_hl,
1664 tree_node_file_search, tree_node_file_search_data,
1642 tree_node_file_layout 1665 tree_node_file_layout
1643 ); 1666 );
1644 1667
1645 int result = 0; 1668 int result = 0;
1646 result |= cxTreeInsert(tree, "/"); 1669 result |= cxTreeInsert(tree, "/");
1668 cx_testing_allocator_init(&talloc); 1691 cx_testing_allocator_init(&talloc);
1669 CxAllocator *alloc = &talloc.base; 1692 CxAllocator *alloc = &talloc.base;
1670 1693
1671 CX_TEST_DO { 1694 CX_TEST_DO {
1672 CxTree *tree = cxTreeCreate( 1695 CxTree *tree = cxTreeCreate(
1673 alloc, tree_node_file_create_hl, tree_node_file_search, 1696 alloc, tree_node_file_create_hl,
1697 tree_node_file_search, tree_node_file_search_data,
1674 tree_node_file_layout 1698 tree_node_file_layout
1675 ); 1699 );
1676 1700
1677 const char *paths[] = { 1701 const char *paths[] = {
1678 "/", 1702 "/",
1688 1712
1689 CX_TEST_ASSERT(talloc.alloc_total == 8); 1713 CX_TEST_ASSERT(talloc.alloc_total == 8);
1690 CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added 1714 CX_TEST_ASSERT(talloc.free_total == 1); // the one that could not be added
1691 1715
1692 cxTreeDestroy(tree); 1716 cxTreeDestroy(tree);
1717 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1718 }
1719 cx_testing_allocator_destroy(&talloc);
1720 }
1721
1722 CX_TEST(test_tree_high_add_find_remove_nodes) {
1723 CxTestingAllocator talloc;
1724 cx_testing_allocator_init(&talloc);
1725 CxAllocator *alloc = &talloc.base;
1726
1727 CX_TEST_DO {
1728 CxTree *tree = cxTreeCreate(
1729 alloc, tree_node_file_create_hl,
1730 tree_node_file_search, tree_node_file_search_data,
1731 tree_node_file_layout
1732 );
1733
1734 const char *paths[] = {
1735 "/",
1736 "/usr/",
1737 "/home/",
1738 "/usr/lib/",
1739 "/home/foo/",
1740 "/home/foo/bar/"
1741 };
1742 cxTreeInsertArray(tree, paths, sizeof(const char*), 6);
1743
1744 tree_node_file *foo = cxTreeFind(tree, "/home/foo/");
1745 CX_TEST_ASSERT(NULL != foo);
1746 CX_TEST_ASSERT(0 == strcmp("/home/foo/", foo->path));
1747 CX_TEST_ASSERT(NULL != foo->parent);
1748 CX_TEST_ASSERT(0 == strcmp("/home/", foo->parent->path));
1749 CX_TEST_ASSERT(tree->size == 6);
1750
1751 CX_TEST_ASSERT(0 == cxTreeAddChild(tree, foo->parent, "/home/baz/"));
1752 tree_node_file *baz = cxTreeFind(tree, "/home/baz/");
1753 CX_TEST_ASSERT(NULL != baz);
1754 CX_TEST_ASSERT(0 == strcmp("/home/baz/", baz->path));
1755 CX_TEST_ASSERT(NULL != baz->parent);
1756 CX_TEST_ASSERT(0 == strcmp("/home/", baz->parent->path));
1757 CX_TEST_ASSERT(tree->size == 7);
1758
1759 tree_node_file *home = cxTreeFind(tree, "/home/");
1760 CX_TEST_ASSERT(NULL == cxTreeFindInSubtree(tree, "/usr/", foo));
1761 tree_node_file *bar = cxTreeFindInSubtree(tree, "/home/foo/bar/", home);
1762 CX_TEST_ASSERT(NULL != bar);
1763 CX_TEST_ASSERT(0 == strcmp("/home/foo/bar/", bar->path));
1764 CX_TEST_ASSERT(bar->parent == foo);
1765
1766 tree_node_file *share = cxCalloc(alloc, 1, sizeof(tree_node_file));
1767 share->path = "/usr/share/";
1768 cxTreeAddChildNode(tree, cxTreeFind(tree, "/usr/"), share);
1769 CX_TEST_ASSERT(tree->size == 8);
1770
1771 cxTreeRemove(tree, foo);
1772 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/"));
1773 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/foo/bar/"));
1774 CX_TEST_ASSERT(NULL == cxTreeFind(tree, "/home/bar/"));
1775 CX_TEST_ASSERT(tree->size == 6);
1776
1777 cxTreeDestroy(tree);
1778 // we are not done yet, because we need to free the removed subtree
1779 CX_TEST_ASSERT(!cx_testing_allocator_verify(&talloc));
1780
1781 // for this, we use a little trick and wrap the removed subtree
1782 CxTree *foo_tree = cxTreeCreateWrapped(alloc, foo, tree_node_file_layout);
1783 foo_tree->allocator = alloc;
1784 foo_tree->advanced_destructor = (cx_destructor_func2 ) cxFree;
1785 foo_tree->destructor_data = alloc;
1786 cxTreeDestroy(foo_tree);
1693 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc)); 1787 CX_TEST_ASSERT(cx_testing_allocator_verify(&talloc));
1694 } 1788 }
1695 cx_testing_allocator_destroy(&talloc); 1789 cx_testing_allocator_destroy(&talloc);
1696 } 1790 }
1697 1791
1735 CxTestSuite *suite = cx_test_suite_new("tree (high level)"); 1829 CxTestSuite *suite = cx_test_suite_new("tree (high level)");
1736 1830
1737 cx_test_register(suite, test_tree_high_create); 1831 cx_test_register(suite, test_tree_high_create);
1738 cx_test_register(suite, test_tree_high_create_simple); 1832 cx_test_register(suite, test_tree_high_create_simple);
1739 cx_test_register(suite, test_tree_high_create_wrapped); 1833 cx_test_register(suite, test_tree_high_create_wrapped);
1740 cx_test_register(suite, test_tree_high_subtree_depth); 1834 cx_test_register(suite, test_tree_high_tree_depth);
1741 cx_test_register(suite, test_tree_high_insert_one); 1835 cx_test_register(suite, test_tree_high_insert_one);
1742 cx_test_register(suite, test_tree_high_insert_many); 1836 cx_test_register(suite, test_tree_high_insert_many);
1837 cx_test_register(suite, test_tree_high_add_find_remove_nodes);
1743 1838
1744 return suite; 1839 return suite;
1745 } 1840 }

Mercurial Repository: ucx

mercurial