/* Unit tests of tree.c Copyright © 2021-2024 Samuel Lidén Borell Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ #include #include "../tree.c" #include "unittest.h" #include "alltests.h" #include "testcommon.h" static struct CSlul *ctx; static struct TreeNode *root; static struct TreeNode na, nb, nc, nd, ne, nf, ng, nh, ni; static void create_ctx(void) { ctx = tctx(cslul_create(NULL)); tassert(ctx != NULL); } static void run_ncmp_long(size_t len) { char *longstr1 = tmalloc(len); char *longstr2 = tmalloc(len); na.length = len; na.name.ptr = longstr1; memset(longstr1, 'a', len); memset(longstr2, 'a', len); tsoftassert(ncmp(ctx, &na, 22, len, longstr2) == 0); longstr2[len-1] = 'b'; tsoftassert(ncmp(ctx, &na, 22, len, longstr2) < 0); longstr1[len-1] = 'c'; tsoftassert(ncmp(ctx, &na, 22, len, longstr2) > 0); tfree(longstr2); tfree(longstr1); } static void test_nodecmp(void) { char shortstr[PTRSIZE]; na.hashcode = 22; create_ctx(); tsoftassert(ncmp(ctx, &na, 11, 0, "") > 0); tsoftassert(ncmp(ctx, &na, 33, 0, "") < 0); na.length = 2; tsoftassert(ncmp(ctx, &na, 22, 1, "x") > 0); tsoftassert(ncmp(ctx, &na, 22, 3, "xxx") < 0); /* Short string. These are stored in a buffer where the pointer would be otherwise. */ memcpy(na.name.copy, "ab", 2); tsoftassert(ncmp(ctx, &na, 22, 2, "aa") > 0); tsoftassert(ncmp(ctx, &na, 22, 2, "ab") == 0); tsoftassert(ncmp(ctx, &na, 22, 2, "ac") < 0); tsoftassert(ncmp(ctx, &na, 22, 3, "abb") < 0); na.length = PTRSIZE; memset(na.name.copy, 'a', PTRSIZE); memset(shortstr, 'a', PTRSIZE); tsoftassert(ncmp(ctx, &na, 22, PTRSIZE, shortstr) == 0); shortstr[PTRSIZE-1] = 'b'; tsoftassert(ncmp(ctx, &na, 22, PTRSIZE, shortstr) < 0); na.name.copy[PTRSIZE-1] = 'c'; tsoftassert(ncmp(ctx, &na, 22, PTRSIZE, shortstr) > 0); /* Long strings */ run_ncmp_long(PTRSIZE+1); run_ncmp_long(20); cslul_free(ctx); } /** Tests case insensitive node name comparison */ static void test_nodecmp_caseinsens(void) { char longstr1[20]; char longstr2[20]; na.hashcode = 22; create_ctx(); ctx->case_insens = 1; tsoftassert(ncmp(ctx, &na, 11, 0, "") > 0); tsoftassert(ncmp(ctx, &na, 33, 0, "") < 0); na.length = 2; tsoftassert(ncmp(ctx, &na, 22, 1, "x") > 0); tsoftassert(ncmp(ctx, &na, 22, 3, "xxx") < 0); /* Short string - Case insensitive */ memcpy(na.name.copy, "Ab", 2); tsoftassert(ncmp(ctx, &na, 22, 2, "aa") > 0); tsoftassert(ncmp(ctx, &na, 22, 2, "aB") == 0); tsoftassert(ncmp(ctx, &na, 22, 2, "ac") < 0); /* Long string - Case insensitive */ na.length = 20; na.name.ptr = longstr1; memset(longstr1, 'a', sizeof(longstr1)); memset(longstr2, 'A', sizeof(longstr2)); tsoftassert(ncmp(ctx, &na, 22, 20, longstr2) == 0); longstr2[19] = 'B'; tsoftassert(ncmp(ctx, &na, 22, 20, longstr2) < 0); longstr1[19] = 'C'; tsoftassert(ncmp(ctx, &na, 22, 20, longstr2) > 0); cslul_free(ctx); } /* Debugging aid */ static void tree_dump(const char *s, struct TreeNode *n) { if (s) fprintf(stderr, "---- %s ----\n", s); if (n) { const char *name; if (n == &na) name = "A"; else if (n == &nb) name = "B"; else if (n == &nc) name = "C"; else if (n == &nd) name = "D"; else if (n == &ne) name = "E"; else if (n == &nf) name = "F"; else if (n == &ng) name = "G"; else if (n == &nh) name = "H"; else if (n == &ni) name = "I"; else name = "O"; fprintf(stderr, "%s", name); if (n->hashcode == 999) { fprintf(stderr, "[cycle]"); } else if (n->lower || n->higher) { HashCode saved = n->hashcode; fputc('(', stderr); n->hashcode = 999; tree_dump(NULL, n->lower); fputc(',', stderr); tree_dump(NULL, n->higher); n->hashcode = saved; fputc(')', stderr); } } if (s) fputc('\n', stderr); } static void node_clear(struct TreeNode *tn) { memset(tn, 0, sizeof(*tn)); tn->lower = NULL; tn->higher = NULL; tn->hashcode = 0; tn->length = 0; } static void start(void) { create_ctx(); root = NULL; node_clear(&na); node_clear(&nb); node_clear(&nc); node_clear(&nd); node_clear(&ne); node_clear(&nf); node_clear(&ng); node_clear(&nh); node_clear(&ni); } static void check(struct TreeNode *n) { if (n->lower) tsoftassert(n->lower->hashcode <= n->hashcode); if (n->higher) tsoftassert(n->higher->hashcode >= n->hashcode); if (n->hashcode) { struct TreeNode *res = tree_search_node(ctx, root, n); if (!tsoftassert(res == n) && !quiet) { const char *name = node_nameptr(n); fprintf(stderr, "node '%.*s' (h:%u, l:%u) was not found.\n", n->length, name, n->hashcode, n->length); tree_dump("tree with missing node", root); } } } static void end(void) { check(&na); check(&nb); check(&nc); check(&nd); check(&ne); check(&nf); check(&ng); check(&nh); check(&ni); cslul_free(ctx); } #define ASSERT_LEAF(n) do { \ tassert((n)->lower == NULL); \ tassert((n)->higher == NULL); \ } while (0) #define ASSERT_1_LEFT(p, c) do { \ tassert((p) != (c)); \ tassert((p)->lower == (c)); \ tassert((p)->higher == NULL); \ } while (0) #define ASSERT_1_RIGHT(p, c) do { \ tassert((p) != (c)); \ tassert((p)->lower == NULL); \ tassert((p)->higher == (c)); \ } while (0) #define ASSERT_BOTH(p, l, r) do { \ tassert((p) != (l)); \ tassert((p) != (r)); \ tassert((l) != (r)); \ tassert((p)->lower == (l)); \ tassert((p)->higher == (r)); \ } while (0) #define TEST_INSERT(h, s, node) \ do { \ struct TreeNode *_tn = tree_insert(ctx, &root, h, sizeof(s)-1, s, \ node, 0); \ tassert(_tn != NULL); \ tsoftassert(_tn->is_new); \ } while (0) #define INSERT_A TEST_INSERT(11, "aa", &na) #define INSERT_B TEST_INSERT(22, "bb", &nb) #define INSERT_C TEST_INSERT(33, "cc", &nc) #define INSERT_D TEST_INSERT(44, "dd", &nd) #define INSERT_E TEST_INSERT(55, "ee", &ne) #define INSERT_F TEST_INSERT(66, "ff", &nf) #define INSERT_G TEST_INSERT(77, "gg", &ng) #define INSERT_H TEST_INSERT(88, "hh", &nh) #define INSERT_I TEST_INSERT(99, "ii", &ni) static void test_rotate_left(void) { nb.lower = &na; nb.higher = &nd; nd.lower = &nc; nd.higher = ≠ tsoftassert(rotate_left(&nb) == &nd); ASSERT_BOTH(&nd, &nb, &ne); ASSERT_BOTH(&nb, &na, &nc); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); ASSERT_LEAF(&ne); } static void test_rotate_right(void) { nd.lower = &nb; nd.higher = ≠ nb.lower = &na; nb.higher = &nc; tsoftassert(rotate_right(&nd) == &nb); ASSERT_BOTH(&nb, &na, &nd); ASSERT_BOTH(&nd, &nc, &ne); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); ASSERT_LEAF(&ne); } static void test_rotate_leftright(void) { nf.lower = &nb; nf.higher = &ng; nb.lower = &na; nb.higher = &nd; nd.lower = &nc; nd.higher = ≠ tsoftassert(rotate_leftright(&nf) == &nd); ASSERT_BOTH(&nd, &nb, &nf); ASSERT_BOTH(&nb, &na, &nc); ASSERT_BOTH(&nf, &ne, &ng); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); ASSERT_LEAF(&ne); ASSERT_LEAF(&ng); } static void test_rotate_rightleft(void) { nb.lower = &na; nb.higher = &nf; nf.lower = &nd; nf.higher = &ng; nd.lower = &nc; nd.higher = ≠ tsoftassert(rotate_rightleft(&nb) == &nd); ASSERT_BOTH(&nd, &nb, &nf); ASSERT_BOTH(&nb, &na, &nc); ASSERT_BOTH(&nf, &ne, &ng); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); ASSERT_LEAF(&ne); ASSERT_LEAF(&ng); } static void test_insert_empty(void) { start(); INSERT_C; tassert(root == &nc); ASSERT_LEAF(&nc); end(); } static void test_insert_empty_existing(void) { struct TreeNode *insresult; start(); nc.length = 1; nc.name.copy[0] = 'E'; nc.hashcode = 123; insresult = tree_insert(ctx, &root, 0, USE_EXISTING, NULL, &nc, 0); tassert(insresult == &nc); tassert(root == &nc); ASSERT_LEAF(&nc); tsoftassert(nc.hashcode == 123); tassert(nc.length == 1); tsoftassert(nc.name.copy[0] == 'E'); end(); } struct LargeNode { struct TreeNode node; char extra[100]; }; static void test_insert_empty_alloc(void) { struct TreeNode *newnode; create_ctx(); root = NULL; newnode = tree_insert(ctx, &root, 33, 2, "cc", NULL, sizeof(struct LargeNode)); tassert(newnode); tsoftassert(newnode->is_new); tassert(root == newnode); ASSERT_LEAF(newnode); /* Trigger valgrind error on incorrect allocation */ memset(newnode, 1, sizeof(struct LargeNode)); /* If struct protection is enabled: Restore the struct trailer */ PROTECT_STACK_STRUCT(*newnode); cslul_free(ctx); } static void test_insert_left(void) { start(); INSERT_C; INSERT_B; tassert(root == &nc); ASSERT_1_LEFT(root, &nb); ASSERT_LEAF(&nb); end(); } static void test_insert_left_existing(void) { struct TreeNode *insresult; start(); INSERT_C; nb.length = 1; nb.name.copy[0] = 'E'; nb.hashcode = 32; /* less than 33 */ nb.lower = &na; /* should be overwritten */ nb.higher = &na; /* should be overwritten */ insresult = tree_insert(ctx, &root, 0, USE_EXISTING, NULL, &nb, 0); tassert(insresult == &nb); tassert(root == &nc); ASSERT_1_LEFT(root, &nb); ASSERT_LEAF(&nb); tsoftassert(nb.hashcode == 32); tassert(nb.length == 1); tsoftassert(nb.name.copy[0] == 'E'); end(); } static void test_insert_left_alloc(void) { struct TreeNode *newc, *newb; create_ctx(); root = NULL; newc = tree_insert(ctx, &root, 33, 2, "cc", NULL, sizeof(struct LargeNode)); newb = tree_insert(ctx, &root, 22, 2, "bb", NULL, sizeof(struct LargeNode)); tassert(newb); tassert(newc); tsoftassert(newb->is_new); tsoftassert(newc->is_new); tassert(root == newc); ASSERT_1_LEFT(root, newb); ASSERT_LEAF(newb); /* Basic allocation check */ tsoftassert(((uintptr)(newb+1) <= (uintptr)newc) || ((uintptr)(newc+1) <= (uintptr)newb)); cslul_free(ctx); } static void test_insert_right(void) { start(); INSERT_C; INSERT_D; tassert(root == &nc); ASSERT_1_RIGHT(root, &nd); ASSERT_LEAF(&nd); end(); } static void test_insert_lr(void) { start(); INSERT_C; INSERT_B; INSERT_D; tassert(root == &nc); ASSERT_BOTH(root, &nb, &nd); ASSERT_LEAF(&nb); ASSERT_LEAF(&nd); end(); } static void test_insert_rl(void) { start(); INSERT_C; INSERT_D; INSERT_B; tassert(root == &nc); ASSERT_BOTH(root, &nb, &nd); ASSERT_LEAF(&nb); ASSERT_LEAF(&nd); end(); } static void test_insert_ll(void) { start(); INSERT_C; INSERT_B; INSERT_A; tassert(root == &nb); ASSERT_BOTH(root, &na, &nc); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); end(); } static void test_insert_rr(void) { start(); INSERT_C; INSERT_D; INSERT_E; tassert(root == &nd); ASSERT_BOTH(root, &nc, &ne); ASSERT_LEAF(&nc); ASSERT_LEAF(&ne); end(); } static void test_insert_abcd(void) { start(); INSERT_A; INSERT_B; INSERT_C; INSERT_D; tassert(root == &nb); ASSERT_BOTH(root, &na, &nc); ASSERT_1_RIGHT(&nc, &nd); ASSERT_LEAF(&na); ASSERT_LEAF(&nd); end(); } static void test_insert_abdc(void) { start(); INSERT_A; INSERT_B; INSERT_D; INSERT_C; tassert(root == &nb); ASSERT_BOTH(root, &na, &nd); ASSERT_1_LEFT(&nd, &nc); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); end(); } static void test_insert_acbd(void) { start(); INSERT_A; INSERT_C; INSERT_B; INSERT_D; tassert(root == &nb); ASSERT_BOTH(root, &na, &nd); ASSERT_1_LEFT(&nd, &nc); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); end(); } static void test_insert_acdb(void) { start(); INSERT_A; INSERT_C; INSERT_D; INSERT_B; tassert(root == &nc); ASSERT_BOTH(root, &na, &nd); ASSERT_1_RIGHT(&na, &nb); ASSERT_LEAF(&nb); ASSERT_LEAF(&nd); end(); } static void test_insert_adbc(void) { start(); INSERT_A; INSERT_D; INSERT_B; INSERT_C; tassert(root == &nb); ASSERT_BOTH(root, &na, &nd); ASSERT_1_LEFT(&nd, &nc); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); end(); } static void test_insert_adcb(void) { start(); INSERT_A; INSERT_D; INSERT_C; INSERT_B; tassert(root == &nc); ASSERT_BOTH(root, &na, &nd); ASSERT_1_RIGHT(&na, &nb); ASSERT_LEAF(&nb); ASSERT_LEAF(&nd); end(); } static void test_insert_bacd(void) { start(); INSERT_B; INSERT_A; INSERT_C; INSERT_D; tassert(root == &nb); ASSERT_BOTH(root, &na, &nc); ASSERT_1_RIGHT(&nc, &nd); ASSERT_LEAF(&na); ASSERT_LEAF(&nd); end(); } static void test_insert_badc(void) { start(); INSERT_B; INSERT_A; INSERT_D; INSERT_C; tassert(root == &nb); ASSERT_BOTH(root, &na, &nd); ASSERT_1_LEFT(&nd, &nc); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); end(); } static void test_insert_bcad(void) { start(); INSERT_B; INSERT_C; INSERT_A; INSERT_D; tassert(root == &nb); ASSERT_BOTH(root, &na, &nc); ASSERT_1_RIGHT(&nc, &nd); ASSERT_LEAF(&na); ASSERT_LEAF(&nd); end(); } static void test_insert_bcda(void) { start(); INSERT_B; INSERT_C; INSERT_D; INSERT_A; tassert(root == &nc); ASSERT_BOTH(root, &nb, &nd); ASSERT_1_LEFT(&nb, &na); ASSERT_LEAF(&na); ASSERT_LEAF(&nd); end(); } static void test_insert_bdac(void) { start(); INSERT_B; INSERT_D; INSERT_A; INSERT_C; tassert(root == &nb); ASSERT_BOTH(root, &na, &nd); ASSERT_1_LEFT(&nd, &nc); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); end(); } static void test_insert_bdca(void) { start(); INSERT_B; INSERT_D; INSERT_C; INSERT_A; tassert(root == &nc); ASSERT_BOTH(root, &nb, &nd); ASSERT_1_LEFT(&nb, &na); ASSERT_LEAF(&na); ASSERT_LEAF(&nd); end(); } static void test_insert_cabd(void) { start(); INSERT_C; INSERT_A; INSERT_B; INSERT_D; tassert(root == &nb); ASSERT_BOTH(root, &na, &nc); ASSERT_1_RIGHT(&nc, &nd); ASSERT_LEAF(&na); ASSERT_LEAF(&nd); end(); } static void test_insert_cadb(void) { start(); INSERT_C; INSERT_A; INSERT_D; INSERT_B; tassert(root == &nc); ASSERT_BOTH(root, &na, &nd); ASSERT_1_RIGHT(&na, &nb); ASSERT_LEAF(&nb); ASSERT_LEAF(&nd); end(); } static void test_insert_cbad(void) { start(); INSERT_C; INSERT_B; INSERT_A; INSERT_D; tassert(root == &nb); ASSERT_BOTH(root, &na, &nc); ASSERT_1_RIGHT(&nc, &nd); ASSERT_LEAF(&na); ASSERT_LEAF(&nd); end(); } static void test_insert_cbda(void) { start(); INSERT_C; INSERT_B; INSERT_D; INSERT_A; tassert(root == &nc); ASSERT_BOTH(root, &nb, &nd); ASSERT_1_LEFT(&nb, &na); ASSERT_LEAF(&na); ASSERT_LEAF(&nd); end(); } static void test_insert_cdab(void) { start(); INSERT_C; INSERT_D; INSERT_A; INSERT_B; tassert(root == &nc); ASSERT_BOTH(root, &na, &nd); ASSERT_1_RIGHT(&na, &nb); ASSERT_LEAF(&nb); ASSERT_LEAF(&nd); end(); } static void test_insert_cdba(void) { start(); INSERT_C; INSERT_D; INSERT_B; INSERT_A; tassert(root == &nc); ASSERT_BOTH(root, &nb, &nd); ASSERT_1_LEFT(&nb, &na); ASSERT_LEAF(&na); ASSERT_LEAF(&nd); end(); } static void test_insert_dabc(void) { start(); INSERT_D; INSERT_A; INSERT_B; INSERT_C; tassert(root == &nb); ASSERT_BOTH(root, &na, &nd); ASSERT_1_LEFT(&nd, &nc); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); end(); } static void test_insert_dacb(void) { struct TreeNode *tn; start(); INSERT_D; tn = tree_insert(ctx, &root, 22, 2, "aa", &na, 0); tassert(tn != NULL); tsoftassert(tn->is_new); INSERT_C; INSERT_B; tassert(root == &nc); ASSERT_BOTH(root, &na, &nd); ASSERT_1_RIGHT(&na, &nb); ASSERT_LEAF(&nb); ASSERT_LEAF(&nd); end(); } static void test_insert_dbac(void) { start(); INSERT_D; INSERT_B; INSERT_A; INSERT_C; tassert(root == &nb); ASSERT_BOTH(root, &na, &nd); ASSERT_1_LEFT(&nd, &nc); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); end(); } static void test_insert_dbca(void) { start(); INSERT_D; INSERT_B; INSERT_C; INSERT_A; tassert(root == &nc); ASSERT_BOTH(root, &na, &nd); ASSERT_1_RIGHT(&na, &nb); ASSERT_LEAF(&nb); ASSERT_LEAF(&nd); end(); } static void test_insert_dcab(void) { start(); INSERT_D; INSERT_C; INSERT_A; INSERT_B; tassert(root == &nc); ASSERT_BOTH(root, &na, &nd); ASSERT_1_RIGHT(&na, &nb); ASSERT_LEAF(&nb); ASSERT_LEAF(&nd); end(); } static void test_insert_dcba(void) { start(); INSERT_D; INSERT_C; INSERT_B; INSERT_A; tassert(root == &nc); ASSERT_BOTH(root, &nb, &nd); ASSERT_1_LEFT(&nb, &na); ASSERT_LEAF(&na); ASSERT_LEAF(&nd); end(); } static void test_insert_l7(void) { start(); INSERT_G; INSERT_F; INSERT_E; INSERT_D; INSERT_C; INSERT_B; INSERT_A; tassert(root == &nd); ASSERT_BOTH(root, &nb, &nf); ASSERT_BOTH(&nb, &na, &nc); ASSERT_BOTH(&nf, &ne, &ng); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); ASSERT_LEAF(&ne); ASSERT_LEAF(&ng); end(); } static void test_insert_r7(void) { start(); INSERT_A; INSERT_B; INSERT_C; INSERT_D; INSERT_E; INSERT_F; INSERT_G; tassert(root == &nd); ASSERT_BOTH(root, &nb, &nf); ASSERT_BOTH(&nb, &na, &nc); ASSERT_BOTH(&nf, &ne, &ng); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); ASSERT_LEAF(&ne); ASSERT_LEAF(&ng); end(); } static void verify_not_overwritten(void) { tsoftassert(na.hashcode != 0); tsoftassert(nb.hashcode != 0); tsoftassert(nc.hashcode != 0); tsoftassert(nd.hashcode != 0); tsoftassert(ne.hashcode != 0); tsoftassert(nf.hashcode != 0); tsoftassert(ng.hashcode != 0); tsoftassert(nh.hashcode != 0); tsoftassert(ni.hashcode != 0); } static void test_insert_deep_lrrot(void) { start(); INSERT_A; /* First make the tree look like this */ INSERT_B; INSERT_C; /* _____d____ */ INSERT_D; /* __b__ __f__ */ INSERT_E; /* a c e i */ INSERT_F; INSERT_I; tassert(root == &nd); ASSERT_BOTH(root, &nb, &nf); ASSERT_BOTH(&nb, &na, &nc); ASSERT_BOTH(&nf, &ne, &ni); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); ASSERT_LEAF(&ne); ASSERT_LEAF(&ng); /* Now insert G. Should NOT trigger rebalance */ INSERT_G; tassert(root == &nd); ASSERT_BOTH(root, &nb, &nf); ASSERT_BOTH(&nf, &ne, &ni); ASSERT_1_LEFT(&ni, &ng); ASSERT_LEAF(&ng); /* Now insert H. This should trigger a left-right rotation */ INSERT_H; tassert(root == &nd); ASSERT_BOTH(root, &nb, &nf); /* The tree should now look like this */ ASSERT_BOTH(&nb, &na, &nc); ASSERT_BOTH(&nf, &ne, &nh); /* _____d____ */ ASSERT_BOTH(&nh, &ng, &ni); /* __b__ __f____ */ ASSERT_LEAF(&na); /* a c e __h__ */ ASSERT_LEAF(&nc); /* g i */ ASSERT_LEAF(&ne); ASSERT_LEAF(&ng); ASSERT_LEAF(&ni); verify_not_overwritten(); /* ensures that end will also test searching */ end(); } static void test_insert_deep_rlrot(void) { start(); INSERT_A; /* First make the tree look like this */ INSERT_D; INSERT_E; /* _____f____ */ INSERT_F; /* __d__ __h__ */ INSERT_G; /* a e g i */ INSERT_H; INSERT_I; tassert(root == &nf); ASSERT_BOTH(root, &nd, &nh); ASSERT_BOTH(&nd, &na, &ne); ASSERT_BOTH(&nh, &ng, &ni); ASSERT_LEAF(&na); ASSERT_LEAF(&ne); ASSERT_LEAF(&ng); ASSERT_LEAF(&ni); /* Now insert C. Should NOT trigger rebalance */ INSERT_C; tassert(root == &nf); ASSERT_BOTH(root, &nd, &nh); ASSERT_BOTH(&nd, &na, &ne); ASSERT_1_RIGHT(&na, &nc); ASSERT_LEAF(&nc); /* Now insert B. This should trigger a right-left rotation */ INSERT_B; tassert(root == &nf); ASSERT_BOTH(root, &nd, &nh); /* The tree should now look like this */ ASSERT_BOTH(&nd, &nb, &ne); ASSERT_BOTH(&nb, &na, &nc); /* _____f____ */ ASSERT_BOTH(&nh, &ng, &ni); /* __d__ __h__ */ ASSERT_LEAF(&na); /* __b__ e g i */ ASSERT_LEAF(&nc); /* a c */ ASSERT_LEAF(&ne); ASSERT_LEAF(&ng); ASSERT_LEAF(&ni); verify_not_overwritten(); /* ensures that end will also test searching */ end(); } /** Tests double rotation with right-heavy subtrees */ static void test_insert_lrrot_rheavy(void) { start(); INSERT_G; INSERT_F; tassert(root == &ng); INSERT_E; tassert(root == &nf); INSERT_B; tassert(root == &nf); INSERT_A; tassert(root == &nf); INSERT_C; tassert(root == &ne); INSERT_D; tassert(root == &ne); /* 1 level of un-balancedness is allowed */ ASSERT_BOTH(root, &nb, &nf); ASSERT_BOTH(&nb, &na, &nc); ASSERT_1_RIGHT(&nf, &ng); /* _______e__ */ ASSERT_LEAF(&na); /* __b__ f__ */ ASSERT_1_RIGHT(&nc, &nd); /* a c__ g */ ASSERT_LEAF(&nd); /* d */ ASSERT_LEAF(&ng); end(); } /** Tests double rotation with left-heavy subtrees */ static void test_insert_rlrot_lheavy(void) { start(); INSERT_A; INSERT_B; tassert(root == &na); INSERT_C; tassert(root == &nb); INSERT_F; tassert(root == &nb); INSERT_G; tassert(root == &nb); INSERT_E; tassert(root == &nc); INSERT_D; tassert(root == &nc); /* 1 level of un-balancedness is allowed */ ASSERT_BOTH(root, &nb, &nf); ASSERT_BOTH(&nf, &ne, &ng); ASSERT_1_LEFT(&nb, &na); /* __c_______ */ ASSERT_LEAF(&na); /* __b __f__ */ ASSERT_1_LEFT(&ne, &nd); /* a __e g */ ASSERT_LEAF(&nd); /* d */ ASSERT_LEAF(&ng); end(); } /** Tests that the rotated subtree is inserted in the correct place */ static void test_insert_subtree_inspoint1(void) { start(); INSERT_A; INSERT_B; INSERT_C; INSERT_E; tassert(root == &nb); ASSERT_BOTH(root, &na, &nc); ASSERT_1_RIGHT(&nc, &ne); INSERT_D; tassert(root == &nb); ASSERT_BOTH(root, &na, &nd); ASSERT_BOTH(&nd, &nc, &ne); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); ASSERT_LEAF(&ne); end(); } /** Tests that the rotated subtree is inserted in the correct place */ static void test_insert_subtree_inspoint2(void) { start(); INSERT_A; INSERT_D; INSERT_E; INSERT_B; tassert(root == &nd); ASSERT_BOTH(root, &na, &ne); ASSERT_1_RIGHT(&na, &nb); INSERT_C; tassert(root == &nd); ASSERT_BOTH(root, &nb, &ne); ASSERT_BOTH(&nb, &na, &nc); ASSERT_LEAF(&na); ASSERT_LEAF(&nc); ASSERT_LEAF(&ne); end(); } /** Tests node allocation and name copying of a long name */ static void test_insert_allocated(void) { const char name[] = "long_name_of_node"; struct TreeNode *tn; start(); INSERT_A; INSERT_B; INSERT_C; INSERT_D; tn = tree_insert(ctx, &root, 1234, sizeof(name)-1, name, NULL, sizeof(struct TreeNode)); tassert(tn != NULL); tsoftassert(tn->is_new); tassert(tn->length == sizeof(name)-1); tassert(tn->name.ptr != NULL); tassert(tn->name.ptr != name); tassert(!memcmp(tn->name.ptr, name, sizeof(name)-1)); end(); } #if 0 static void insnode(int i) { switch (i) { case 0: INSERT_A; break; case 1: INSERT_B; break; case 2: INSERT_C; break; case 3: INSERT_D; break; case 4: INSERT_E; break; case 5: INSERT_F; break; case 6: INSERT_G; break; case 7: INSERT_H; break; case 8: INSERT_I; break; default: tsoftfail("Bad node index"); } } static void check_depth(struct TreeNode *tn, int depth) { /* We can have up to 1 level of "unbalancedness" in an AVL tree, in addition to the theorethical minimum unbalancedness of all trees whose number of nodes is not a power of two. */ if (!tn) { tassert(depth <= 2); return; } tassert(depth-- >= 0); check_depth(tn->lower, depth); check_depth(tn->higher, depth); } static void test_insert_bruteforce(void) { int n0, n1, n2, n3, n4, n5, n6, n7, n8; for (n0 = 0; n0 <= 8; n0++) { for (n1 = 0; n1 <= 8; n1++) { if (n1==n0) continue; for (n2 = 0; n2 <= 8; n2++) { if (n2==n0 || n2==n1) continue; for (n3 = 0; n3 <= 8; n3++) { if (n3==n0 || n3==n1 || n3==n2) continue; for (n4 = 0; n4 <= 8; n4++) { if (n4==n0 || n4==n1 || n4==n2 || n4==n3) continue; for (n5 = 0; n5 <= 8; n5++) { if (n5==n0 || n5==n1 || n5==n2 || n5==n3 || n5==n4) continue; for (n6 = 0; n6 <= 8; n6++) { if (n6==n0 || n6==n1 || n6==n2 || n6==n3 || n6==n4 || n6==n5) continue; for (n7 = 0; n7 <= 8; n7++) { if (n7==n0 || n7==n1 || n7==n2 || n7==n3 || n7==n4 || n7==n5 || n7==n6) continue; for (n8 = 0; n8 <= 8; n8++) { if (n8==n0 || n8==n1 || n8==n2 || n8==n3 || n8==n4 || n8==n5 || n8==n6 || n8==n7) continue; start(); /*if (n0 > 4 ||n1 >4 || n2 > 4 || n3 > 4 || n4 > 4) continue;*/ /*if (65+n0=='A' && 65+n1=='B' && 65+n2=='C' && 65+n3=='E' && 65+n4=='D') continue;*/ /*fprintf(stderr, "%c -> %c -> %c -> %c -> %c\n",'A'+n0,'A'+n1,'A'+n2,'A'+n3,'A'+n4);*/ insnode(n0); insnode(n1); insnode(n2); insnode(n3); insnode(n4); insnode(n5); insnode(n6); insnode(n7); insnode(n8); check_depth(root, 4); end(); } } } } } } } } } } #endif static void test_insert_duplicate_root(void) { start(); INSERT_A; tassert(tree_insert(ctx, &root, 11, 2, "aa", &ng, 0) == &na); tsoftassert(!na.is_new); node_clear(&ng); /* prevent check of failed node */ end(); } static void test_insert_duplicate_level2(void) { start(); INSERT_B; INSERT_A; INSERT_C; tassert(tree_insert(ctx, &root, 11, 2, "aa", &ng, 0) == &na); tsoftassert(!na.is_new); node_clear(&ng); /* prevent check of failed node */ end(); } static void test_search_empty(void) { start(); tassert(tree_search(ctx, root, 11, 2, "aa") == NULL); end(); } static void test_search_root_existent(void) { start(); INSERT_A; tassert(tree_search(ctx, root, 11, 2, "aa") == &na); end(); } static void test_search_root_nonexistent(void) { start(); INSERT_B; tassert(tree_search(ctx, root, 22, 2, "ba") == NULL); tassert(tree_search(ctx, root, 22, 2, "bc") == NULL); end(); } static void test_search_nested_existent(void) { start(); INSERT_A; INSERT_B; INSERT_C; tassert(tree_search(ctx, root, 11, 2, "aa") == &na); tassert(tree_search(ctx, root, 33, 2, "cc") == &nc); end(); } static void test_search_nested_nonexistent(void) { start(); INSERT_A; INSERT_B; INSERT_C; tassert(tree_search(ctx, root, 11, 2, "ax") == NULL); tassert(tree_search(ctx, root, 11, 2, "aA") == NULL); tassert(tree_search(ctx, root, 33, 2, "cx") == NULL); tassert(tree_search(ctx, root, 33, 2, "Cc") == NULL); end(); } static void test_search_caseinsens(void) { start(); ctx->case_insens = 1; INSERT_A; INSERT_B; INSERT_C; tassert(tree_search(ctx, root, 11, 2, "AA") == &na); tassert(tree_search(ctx, root, 22, 2, "BB") == &nb); tassert(tree_search(ctx, root, 33, 2, "CC") == &nc); end(); } #define ASSERT_ITER(expected_node) do { \ tassert(tree_iter_next(&it, &n)); \ tsoftassert(n == (expected_node)); \ } while (0) #define ASSERT_ITER_END() tassert(!tree_iter_next(&it, &n)) static void test_iter_empty(void) { struct TreeIter it; struct TreeNode *n; tree_iter_init(&it, NULL); tassert(it.depth == -1); ASSERT_ITER_END(); } static void test_iter_one(void) { struct TreeIter it; struct TreeNode *n; start(); INSERT_A; tree_iter_init(&it, root); tsoftassert(it.depth == 0); ASSERT_ITER(&na); ASSERT_ITER_END(); end(); } static void test_iter_ll(void) { struct TreeIter it; struct TreeNode *n; start(); INSERT_B; INSERT_A; tassert(root == &nb); tree_iter_init(&it, root); tsoftassert(it.depth == 1); ASSERT_ITER(&na); ASSERT_ITER(&nb); ASSERT_ITER_END(); end(); } static void test_iter_hh(void) { struct TreeIter it; struct TreeNode *n; na.lower = NULL; na.higher = &nb; nb.lower = NULL; nb.higher = NULL; tree_iter_init(&it, &na); tsoftassert(it.depth == 0); ASSERT_ITER(&na); ASSERT_ITER(&nb); ASSERT_ITER_END(); } static void test_iter_lh_h(void) { struct TreeIter it; struct TreeNode *n; na.lower = NULL; na.higher = &nb; nb.lower = NULL; nb.higher = NULL; nc.lower = &na; nc.higher = &nd; nd.lower = NULL; nd.higher = NULL; tree_iter_init(&it, &nc); tsoftassert(it.depth == 1); ASSERT_ITER(&na); tsoftassert(it.depth == 1); ASSERT_ITER(&nb); tsoftassert(it.depth == 0); ASSERT_ITER(&nc); tsoftassert(it.depth == 0); ASSERT_ITER(&nd); tsoftassert(it.depth == -1); ASSERT_ITER_END(); } static void test_iter_big(void) { struct TreeIter it; struct TreeNode *n; start(); INSERT_E; INSERT_B; INSERT_A; INSERT_D; INSERT_F; INSERT_C; INSERT_G; tree_iter_init(&it, root); tsoftassert(it.depth == 2); ASSERT_ITER(&na); ASSERT_ITER(&nb); ASSERT_ITER(&nc); ASSERT_ITER(&nd); ASSERT_ITER(&ne); ASSERT_ITER(&nf); ASSERT_ITER(&ng); ASSERT_ITER_END(); end(); } const TestFunctionInfo tests_tree[] = { TEST_INFO(test_nodecmp) TEST_INFO(test_nodecmp_caseinsens) TEST_INFO(test_rotate_left) TEST_INFO(test_rotate_right) TEST_INFO(test_rotate_leftright) TEST_INFO(test_rotate_rightleft) TEST_INFO(test_insert_empty) TEST_INFO(test_insert_empty_existing) TEST_INFO(test_insert_empty_alloc) TEST_INFO(test_insert_left) TEST_INFO(test_insert_left_existing) TEST_INFO(test_insert_left_alloc) TEST_INFO(test_insert_right) TEST_INFO(test_insert_lr) TEST_INFO(test_insert_rl) TEST_INFO(test_insert_ll) TEST_INFO(test_insert_rr) TEST_INFO(test_insert_abcd) TEST_INFO(test_insert_abdc) TEST_INFO(test_insert_acbd) TEST_INFO(test_insert_acdb) TEST_INFO(test_insert_adbc) TEST_INFO(test_insert_adcb) TEST_INFO(test_insert_bacd) TEST_INFO(test_insert_badc) TEST_INFO(test_insert_bcad) TEST_INFO(test_insert_bcda) TEST_INFO(test_insert_bdac) TEST_INFO(test_insert_bdca) TEST_INFO(test_insert_cabd) TEST_INFO(test_insert_cadb) TEST_INFO(test_insert_cbad) TEST_INFO(test_insert_cbda) TEST_INFO(test_insert_cdab) TEST_INFO(test_insert_cdba) TEST_INFO(test_insert_dabc) TEST_INFO(test_insert_dacb) TEST_INFO(test_insert_dbac) TEST_INFO(test_insert_dbca) TEST_INFO(test_insert_dcab) TEST_INFO(test_insert_dcba) TEST_INFO(test_insert_l7) TEST_INFO(test_insert_r7) TEST_INFO(test_insert_deep_lrrot) TEST_INFO(test_insert_deep_rlrot) TEST_INFO(test_insert_lrrot_rheavy) TEST_INFO(test_insert_rlrot_lheavy) TEST_INFO(test_insert_subtree_inspoint1) TEST_INFO(test_insert_subtree_inspoint2) TEST_INFO(test_insert_allocated) /*TEST_INFO(test_insert_bruteforce)*/ TEST_INFO(test_insert_duplicate_root) TEST_INFO(test_insert_duplicate_level2) TEST_INFO(test_search_empty) TEST_INFO(test_search_root_existent) TEST_INFO(test_search_root_nonexistent) TEST_INFO(test_search_nested_existent) TEST_INFO(test_search_nested_nonexistent) TEST_INFO(test_search_caseinsens) TEST_INFO(test_iter_empty) TEST_INFO(test_iter_one) TEST_INFO(test_iter_ll) TEST_INFO(test_iter_hh) TEST_INFO(test_iter_lh_h) TEST_INFO(test_iter_big) TEST_END };