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 #if HAVE_CONFIG_H
  29 #       include "config.h"
  30 #endif
  31
  32 #include "utils/avltree.h"
  33 #include "testutils.h"
  34
  35 #include <check.h>
  36
  37 static sdb_avltree_t *tree;
  38
  39 static void
  40 setup(void)
  41 {
  42         tree = sdb_avltree_create();
  43         fail_unless(tree != NULL,
  44                         "sdb_avltree_create() = NULL; expected AVL-tree object");
  45 } /* setup */
  46
  47 static void
  48 teardown(void)
  49 {
  50         sdb_avltree_destroy(tree);
  51         tree = NULL;
  52 } /* teardown */
  53
  54 /* 'a' thru 'o' */
  55 static sdb_object_t test_data[] = {
  56         SDB_OBJECT_STATIC("h"),
  57         SDB_OBJECT_STATIC("j"),
  58         SDB_OBJECT_STATIC("i"),
  59         SDB_OBJECT_STATIC("f"),
  60         SDB_OBJECT_STATIC("e"),
  61         SDB_OBJECT_STATIC("g"),
  62         SDB_OBJECT_STATIC("k"),
  63         SDB_OBJECT_STATIC("l"),
  64         SDB_OBJECT_STATIC("m"),
  65         SDB_OBJECT_STATIC("n"),
  66         SDB_OBJECT_STATIC("o"),
  67         SDB_OBJECT_STATIC("d"),
  68         SDB_OBJECT_STATIC("c"),
  69         SDB_OBJECT_STATIC("b"),
  70         SDB_OBJECT_STATIC("a"),
  71 };
  72
  73 static char *unused_names[] = { "x", "y", "z" };
  74
  75 static void
  76 populate(void)
  77 {
  78         size_t i;
  79         for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i)
  80                 sdb_avltree_insert(tree, &test_data[i]);
  81 } /* populate */
  82
  83 START_TEST(test_null)
  84 {
  85         sdb_object_t o1 = SDB_OBJECT_STATIC("obj");
  86         sdb_object_t *o2;
  87         sdb_avltree_iter_t *iter;
  88         int check;
  89
  90         /* all functions should work even when passed null values */
  91         sdb_avltree_destroy(NULL);
  92         sdb_avltree_clear(NULL);
  93
  94         check = sdb_avltree_insert(NULL, NULL);
  95         fail_unless(check < 0,
  96                         "sdb_avltree_insert(NULL, NULL) = %d; expected: <0", check);
  97         check = sdb_avltree_insert(NULL, &o1);
  98         fail_unless(check < 0,
  99                         "sdb_avltree_insert(NULL, <obj>) = %d; expected: <0", check);
 100         fail_unless(o1.ref_cnt == 1,
 101                         "sdb_avltree_insert(NULL, <obj>) incremented ref-cnt");
 102         /* it's acceptable to insert NULL */
 103
 104         iter = sdb_avltree_get_iter(NULL);
 105         fail_unless(iter == NULL,
 106                         "sdb_avltree_get_iter(NULL) = %p; expected: NULL", iter);
 107
 108         check = sdb_avltree_iter_has_next(NULL) != 0;
 109         fail_unless(check == 0,
 110                         "sdb_avltree_iter_has_next(NULL) = %d; expected: 0", check);
 111         o2 = sdb_avltree_iter_get_next(NULL);
 112         fail_unless(o2 == NULL,
 113                         "sdb_avltree_iter_get_next(NULL) = %p; expected: NULL", o2);
 114
 115         sdb_avltree_iter_destroy(NULL);
 116
 117         check = (int)sdb_avltree_size(NULL);
 118         fail_unless(check == 0,
 119                         "sdb_avltree_size(NULL) = %d; expected: 0", check);
 120 }
 121 END_TEST
 122
 123 START_TEST(test_insert)
 124 {
 125         size_t i;
 126
 127         for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) {
 128                 int check;
 129
 130                 check = sdb_avltree_insert(tree, &test_data[i]);
 131                 fail_unless(check == 0,
 132                                 "sdb_avltree_insert(<tree>, <%s>) = %d; expected: 0",
 133                                 test_data[i].name, check);
 134
 135                 check = (int)sdb_avltree_size(tree);
 136                 fail_unless(check == (int)i + 1,
 137                                 "sdb_avltree_size(<tree>) = %d; expected: %zu",
 138                                 check, i + 1);
 139
 140                 fail_unless(sdb_avltree_valid(tree),
 141                                 "sdb_avltree_insert(<tree>, <%s>) left behind invalid tree",
 142                                 test_data[i].name);
 143         }
 144
 145         /* and again ... now reporting errors because of duplicates */
 146         for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) {
 147                 int check;
 148
 149                 check = sdb_avltree_insert(tree, &test_data[i]);
 150                 fail_unless(check < 0,
 151                                 "sdb_avltree_insert(<tree>, <%s>) = %d (redo); expected: <0",
 152                                 test_data[i].name, check);
 153
 154                 check = (int)sdb_avltree_size(tree);
 155                 fail_unless(check == SDB_STATIC_ARRAY_LEN(test_data),
 156                                 "sdb_avltree_size(<tree>) = %d; expected: %zu",
 157                                 check, SDB_STATIC_ARRAY_LEN(test_data));
 158         }
 159 }
 160 END_TEST
 161
 162 START_TEST(test_lookup)
 163 {
 164         size_t i;
 165
 166         populate();
 167
 168         for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) {
 169                 sdb_object_t *obj;
 170
 171                 obj = sdb_avltree_lookup(tree, test_data[i].name);
 172                 fail_unless(obj != NULL,
 173                                 "sdb_avltree_lookup(<tree>, %s) = NULL; "
 174                                 "expected: <obj>", test_data[i].name);
 175                 fail_unless(obj == &test_data[i],
 176                                 "sdb_avltree_lookup(<tree>, %s) = %p (%s); "
 177                                 "expected: %p, (%s)", test_data[i].name, obj, obj->name,
 178                                 &test_data[i], test_data[i].name);
 179         }
 180
 181         for (i = 0; i < SDB_STATIC_ARRAY_LEN(unused_names); ++i) {
 182                 sdb_object_t *obj;
 183
 184                 obj = sdb_avltree_lookup(tree, unused_names[i]);
 185                 fail_unless(obj == NULL,
 186                                 "sdb_avltree_lookup(<tree>, %s) = %p (%s); "
 187                                 "expected: NULL", unused_names[i],
 188                                 obj, obj ? obj->name : "<nil>");
 189         }
 190 }
 191 END_TEST
 192
 193 START_TEST(test_iter)
 194 {
 195         sdb_avltree_iter_t *iter;
 196         sdb_object_t *obj;
 197
 198         size_t check, i;
 199
 200         populate();
 201         check = sdb_avltree_size(tree);
 202         fail_unless(check == SDB_STATIC_ARRAY_LEN(test_data),
 203                         "INTERNAL ERROR: AVL tree size (after populate) = %zu; "
 204                         "expected: %zu", check, SDB_STATIC_ARRAY_LEN(test_data));
 205
 206         iter = sdb_avltree_get_iter(tree);
 207         fail_unless(iter != NULL,
 208                         "sdb_avltree_get_iter(<tree>) = NULL; expected: <iter>");
 209
 210         for (i = 0; i < SDB_STATIC_ARRAY_LEN(test_data); ++i) {
 211                 char expected_name[] = { (char)('a' + (int)i), '\0' };
 212
 213                 _Bool c = sdb_avltree_iter_has_next(iter);
 214                 fail_unless(c, "sdb_avltree_iter_has_next(<iter[%zu]>) = false; "
 215                                 "expected: true", i);
 216
 217                 obj = sdb_avltree_iter_get_next(iter);
 218                 fail_unless(obj != NULL,
 219                                 "sdb_avltree_iter_get_next(<iter[%zu]>) = NULL; "
 220                                 "expected: <obj>", i);
 221                 fail_unless(!strcmp(obj->name, expected_name),
 222                                 "sdb_avltree_iter[%zu] = %s; expected: %s",
 223                                 i, obj->name, expected_name);
 224         }
 225
 226         check = sdb_avltree_iter_has_next(iter) != 0;
 227         fail_unless(check == 0, "sdb_avltree_iter_has_next(<iter>) = true; "
 228                         "expected: false");
 229         obj = sdb_avltree_iter_get_next(iter);
 230         fail_unless(obj == NULL,
 231                         "sdb_avltree_iter_get_next(<iter>) = <obj>; expected: NULL");
 232
 233         sdb_avltree_iter_destroy(iter);
 234
 235         sdb_avltree_clear(tree);
 236         check = sdb_avltree_size(tree);
 237         fail_unless(check == 0,
 238                         "sdb_avltree_clear(<tree>) left %zu nodes in the tree; "
 239                         "expected: 0", check);
 240 }
 241 END_TEST
 242
 243 TEST_MAIN("utils::avltree")
 244 {
 245         TCase *tc = tcase_create("core");
 246         tcase_add_checked_fixture(tc, setup, teardown);
 247         tcase_add_test(tc, test_null);
 248         tcase_add_test(tc, test_insert);
 249         tcase_add_test(tc, test_lookup);
 250         tcase_add_test(tc, test_iter);
 251         ADD_TCASE(tc);
 252 }
 253 TEST_MAIN_END
 254
 255 /* vim: set tw=78 sw=4 ts=4 noexpandtab : */
 256