t/unit/utils/avltree_test.c

   1 /*
   2  * SysDB - t/unit/utils/avltree_test.c
   3  * Copyright (C) 2015 Sebastian 'tokkee' Harl <sh@tokkee.org>
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  *
  15  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  16  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  17  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  18  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
  19  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  20  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  21  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
  22  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  23  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  24  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  25  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include "utils/avltree.h"
  29 #include "libsysdb_test.h"
  30
  31 #include <check.h>
  32
  33 static sdb_avltree_t *tree;
  34
  35 static void
  36 setup(void)
  37 {
  38         tree = sdb_avltree_create(NULL);
  39         fail_unless(tree != NULL,
  40                         "sdb_avltree_create() = NULL; expected AVL-tree object");
  41 } /* setup */
  42
  43 static void
  44 teardown(void)
  45 {
  46         sdb_avltree_destroy(tree);
  47         tree = NULL;
  48 } /* teardown */
  49
  50 /* 'a' thru 'o' */
  51 static sdb_object_t test_data[] = {
  52         SSTRING_OBJ("h"),
  53         SSTRING_OBJ("j"),
  54         SSTRING_OBJ("i"),
  55         SSTRING_OBJ("f"),
  56         SSTRING_OBJ("e"),
  57         SSTRING_OBJ("g"),
  58         SSTRING_OBJ("k"),
  59         SSTRING_OBJ("l"),
  60         SSTRING_OBJ("m"),
  61         SSTRING_OBJ("n"),
  62         SSTRING_OBJ("o"),
  63         SSTRING_OBJ("d"),
  64         SSTRING_OBJ("c"),
  65         SSTRING_OBJ("b"),
  66         SSTRING_OBJ("a"),
  67 };
  68
  69 static void
  70 populate(void)
  71 {
  72         size_t i;
  73         for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i)
  74                 sdb_avltree_insert(tree, &test_data[i]);
  75 } /* populate */
  76
  77 START_TEST(test_null)
  78 {
  79         sdb_object_t o1 = SSTRING_OBJ("obj");
  80         sdb_object_t *o2;
  81         sdb_avltree_iter_t *iter;
  82         int check;
  83
  84         /* all functions should work even when passed null values */
  85         sdb_avltree_destroy(NULL);
  86         sdb_avltree_clear(NULL);
  87
  88         check = sdb_avltree_insert(NULL, NULL);
  89         fail_unless(check < 0,
  90                         "sdb_avltree_insert(NULL, NULL) = %d; expected: <0", check);
  91         check = sdb_avltree_insert(NULL, &o1);
  92         fail_unless(check < 0,
  93                         "sdb_avltree_insert(NULL, <obj>) = %d; expected: <0", check);
  94         fail_unless(o1.ref_cnt == 1,
  95                         "sdb_avltree_insert(NULL, <obj>) incremented ref-cnt");
  96         /* it's acceptable to insert NULL */
  97
  98         iter = sdb_avltree_get_iter(NULL);
  99         fail_unless(iter == NULL,
 100                         "sdb_avltree_get_iter(NULL) = %p; expected: NULL", iter);
 101
 102         check = sdb_avltree_iter_has_next(NULL) != 0;
 103         fail_unless(check == 0,
 104                         "sdb_avltree_iter_has_next(NULL) = %d; expected: 0", check);
 105         o2 = sdb_avltree_iter_get_next(NULL);
 106         fail_unless(o2 == NULL,
 107                         "sdb_avltree_iter_get_next(NULL) = %p; expected: NULL", o2);
 108
 109         sdb_avltree_iter_destroy(NULL);
 110
 111         check = (int)sdb_avltree_size(NULL);
 112         fail_unless(check == 0,
 113                         "sdb_avltree_size(NULL) = %d; expected: 0", check);
 114 }
 115 END_TEST
 116
 117 START_TEST(test_insert)
 118 {
 119         size_t i;
 120
 121         for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) {
 122                 int check;
 123
 124                 check = sdb_avltree_insert(tree, &test_data[i]);
 125                 fail_unless(check == 0,
 126                                 "sdb_avltree_insert(<tree>, <%s>) = %d; expected: 0",
 127                                 test_data[i].name, check);
 128
 129                 check = (int)sdb_avltree_size(tree);
 130                 fail_unless(check == (int)i + 1,
 131                                 "sdb_avltree_size(<tree>) = %d; expected: %zu",
 132                                 check, i + 1);
 133
 134                 fail_unless(sdb_avltree_valid(tree),
 135                                 "sdb_avltree_insert(<tree>, <%s>) left behind invalid tree",
 136                                 test_data[i].name);
 137         }
 138
 139         /* and again ... now reporting errors because of duplicates */
 140         for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) {
 141                 int check;
 142
 143                 check = sdb_avltree_insert(tree, &test_data[i]);
 144                 fail_unless(check < 0,
 145                                 "sdb_avltree_insert(<tree>, <%s>) = %d (redo); expected: <0",
 146                                 test_data[i].name, check);
 147
 148                 check = (int)sdb_avltree_size(tree);
 149                 fail_unless(check == SDB_STATIC_ARRAY_LEN(test_data),
 150                                 "sdb_avltree_size(<tree>) = %d; expected: %zu",
 151                                 check, SDB_STATIC_ARRAY_LEN(test_data));
 152         }
 153 }
 154 END_TEST
 155
 156 START_TEST(test_iter)
 157 {
 158         sdb_avltree_iter_t *iter;
 159         sdb_object_t *obj;
 160
 161         size_t check, i;
 162
 163         populate();
 164         check = sdb_avltree_size(tree);
 165         fail_unless(check == SDB_STATIC_ARRAY_LEN(test_data),
 166                         "INTERNAL ERROR: AVL tree size (after populate) = %zu; "
 167                         "expected: %zu", check, SDB_STATIC_ARRAY_LEN(test_data));
 168
 169         iter = sdb_avltree_get_iter(tree);
 170         fail_unless(iter != NULL,
 171                         "sdb_avltree_get_iter(<tree>) = NULL; expected: <iter>");
 172
 173         for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) {
 174                 char expected_name[] = { (char)('a' + (int)i), '\0' };
 175
 176                 _Bool c = sdb_avltree_iter_has_next(iter);
 177                 fail_unless(c, "sdb_avltree_iter_has_next(<iter[%zu]>) = false; "
 178                                 "expected: true", i);
 179
 180                 obj = sdb_avltree_iter_get_next(iter);
 181                 fail_unless(obj != NULL,
 182                                 "sdb_avltree_iter_get_next(<iter[%zu]>) = NULL; "
 183                                 "expected: <obj>", i);
 184                 fail_unless(!strcmp(obj->name, expected_name),
 185                                 "sdb_avltree_iter[%zu] = %s; expected: %s",
 186                                 i, obj->name, expected_name);
 187         }
 188
 189         check = sdb_avltree_iter_has_next(iter) != 0;
 190         fail_unless(check == 0, "sdb_avltree_iter_has_next(<iter>) = true; "
 191                         "expected: false");
 192         obj = sdb_avltree_iter_get_next(iter);
 193         fail_unless(obj == NULL,
 194                         "sdb_avltree_iter_get_next(<iter>) = <obj>; expected: NULL");
 195
 196         sdb_avltree_iter_destroy(iter);
 197
 198         sdb_avltree_clear(tree);
 199         check = sdb_avltree_size(tree);
 200         fail_unless(check == 0,
 201                         "sdb_avltree_clear(<tree>) left %zu nodes in the tree; "
 202                         "expected: 0", check);
 203 }
 204 END_TEST
 205
 206 Suite *
 207 util_avltree_suite(void)
 208 {
 209         Suite *s = suite_create("utils::avltree");
 210         TCase *tc;
 211
 212         tc = tcase_create("core");
 213         tcase_add_checked_fixture(tc, setup, teardown);
 214         tcase_add_test(tc, test_null);
 215         tcase_add_test(tc, test_insert);
 216         tcase_add_test(tc, test_iter);
 217         suite_add_tcase(s, tc);
 218
 219         return s;
 220 } /* util_avltree_suite */
 221
 222 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 223