git.ozlabs.org Git - ccan/blob - ccan/btree/test/run-trivial.c

   1 /* Include the main header first, to test it works */
   2 #include <ccan/btree/btree.h>
   3 /* Include the C files directly. */
   4 #include <ccan/btree/btree.c>
   5 #include <ccan/tap/tap.h>
   6
   7 #include <string.h>
   8
   9 struct test_item {
  10         int key;
  11         int value;
  12 };
  13
  14 static btree_search_implement(
  15         order_by_key,
  16         struct test_item *,
  17         ,
  18         a->key == b->key,
  19         a->key < b->key
  20 )
  21
  22 static int insert_test_item(struct btree *btree, int key, int value)
  23 {
  24         struct test_item key_item = {key, -101};
  25         struct test_item *item;
  26         btree_iterator iter;
  27
  28         if (btree_find_first(btree, &key_item, iter)) {
  29                 /* Don't insert new item, but do update its value. */
  30                 item = iter->item;
  31                 item->value = value;
  32                 return 0;
  33         }
  34
  35         item = malloc(sizeof(*item));
  36         item->key = key;
  37         item->value = value;
  38
  39         btree_insert_at(iter, item);
  40
  41         return 1;
  42 }
  43
  44 static int lookup_test_item(const struct btree *btree, int key)
  45 {
  46         struct test_item key_item = {key, -102};
  47         struct test_item *item;
  48         btree_iterator iter;
  49
  50         if (!btree_find_first(btree, &key_item, iter))
  51                 return -100;
  52
  53         item = iter->item;
  54         return item->value;
  55 }
  56
  57 static int destroy_test_item(void *item, void *ctx) {
  58         (void) ctx;
  59         free(item);
  60         return 1;
  61 }
  62
  63 struct test_insert_entry {
  64         int key;
  65         int value;
  66         int expected_return;
  67 };
  68
  69 struct test_traverse_entry {
  70         int key;
  71         int value;
  72 };
  73
  74 static void print_indent(unsigned int indent) {
  75         while (indent--)
  76                 fputs("\t", stdout);
  77 }
  78
  79 static void btree_node_trace(struct btree_node *node, unsigned int indent)
  80 {
  81         unsigned int i;
  82         for (i=0; i<node->count; i++) {
  83                 if (node->depth)
  84                         btree_node_trace(node->branch[i], indent+1);
  85                 print_indent(indent);
  86                 puts(node->item[i]);
  87         }
  88         if (node->depth)
  89                 btree_node_trace(node->branch[node->count], indent+1);
  90 }
  91
  92 static void btree_trace(struct btree *btree)
  93 {
  94         btree_node_trace(btree->root, 0);
  95 }
  96
  97 static void test_insert(struct btree *btree)
  98 {
  99         struct test_insert_entry ent[] = {
 100                 {3, 1, 1}, {4, 1, 1}, {5, 9, 1}, {2, 6, 1}, {5, 3, 0}, {5, 8, 0},
 101                 {9, 7, 1}, {9, 3, 0}, {2, 3, 0}, {8, 4, 1}, {6, 2, 1}, {6, 4, 0},
 102                 {3, 3, 0}, {8, 3, 0}, {2, 7, 0}, {9, 5, 0}, {0, 2, 1}, {8, 8, 0},
 103                 {4, 1, 0}, {9, 7, 0}, {1, 6, 1}, {9, 3, 0}, {9, 9, 0}, {3, 7, 0},
 104                 {5, 1, 0}, {0, 5, 0}, {8, 2, 0}, {0, 9, 0}, {7, 4, 1}, {9, 4, 0},
 105                 {4, 5, 0}, {9, 2, 0}
 106         };
 107         size_t i, count = sizeof(ent) / sizeof(*ent);
 108
 109         for (i = 0; i < count; i++) {
 110                 int ret = insert_test_item(btree, ent[i].key, ent[i].value);
 111                 ok1(ret == ent[i].expected_return);
 112         }
 113 }
 114
 115 static void test_find_traverse(struct btree *btree)
 116 {
 117         struct test_traverse_entry ent[] = {
 118                 {0, 9}, {1, 6}, {2, 7}, {3, 7}, {4, 5},
 119                 {5, 1}, {6, 4}, {7, 4}, {8, 2}, {9, 2}
 120         };
 121         size_t i, count = sizeof(ent) / sizeof(*ent);
 122         btree_iterator iter;
 123
 124         i = 0;
 125         for (btree_begin(btree, iter); btree_next(iter);) {
 126                 struct test_item *item = iter->item;
 127
 128                 if (i >= count) {
 129                         fail("Too many items in btree according to forward traversal");
 130                         break;
 131                 }
 132
 133                 ok1(lookup_test_item(btree, item->key) == item->value);
 134                 ok1(item->key == ent[i].key && item->value == ent[i].value);
 135
 136                 i++;
 137         }
 138
 139         if (i != count)
 140                 fail("Not enough items in btree according to forward traversal");
 141
 142         i = count;
 143         for (btree_end(btree, iter); btree_prev(iter);) {
 144                 struct test_item *item = iter->item;
 145
 146                 if (!i--) {
 147                         fail("Too many items in btree according to backward traversal");
 148                         break;
 149                 }
 150
 151                 ok1(lookup_test_item(btree, item->key) == item->value);
 152                 ok1(item->key == ent[i].key && item->value == ent[i].value);
 153         }
 154
 155         if (i != 0)
 156                 fail("Not enough items in btree according to backward traversal");
 157 }
 158
 159 static btree_search_proto order_by_string;
 160
 161 static btree_search_implement(
 162         order_by_string, //function name
 163         const char*, //key type
 164         int c = strcmp(a, b), //setup
 165         c == 0, // a == b predicate
 166         c < 0 // a < b predicate
 167 )
 168
 169 //used in the test case to sort the test strings
 170 static int compare_by_string(const void *ap, const void *bp)
 171 {
 172         const char * const *a = ap;
 173         const char * const *b = bp;
 174         return strcmp(*a, *b);
 175 }
 176
 177 static void test_traverse(struct btree *btree, const char *sorted[], size_t count)
 178 {
 179         btree_iterator iter, iter2;
 180         size_t i;
 181
 182         i = 0;
 183         for (btree_begin(btree, iter); btree_next(iter);) {
 184                 if (i >= count) {
 185                         fail("Too many items in btree according to forward traversal");
 186                         break;
 187                 }
 188
 189                 ok1(iter->item == sorted[i]);
 190
 191                 btree_find_first(btree, sorted[i], iter2);
 192                 ok1(iter2->item == sorted[i]);
 193
 194                 i++;
 195         }
 196
 197         if (i != count)
 198                 fail("Not enough items in btree according to forward traversal");
 199
 200         i = count;
 201         for (btree_end(btree, iter); btree_prev(iter);) {
 202                 if (!i--) {
 203                         fail("Too many items in btree according to backward traversal");
 204                         break;
 205                 }
 206
 207                 ok1(iter->item == sorted[i]);
 208
 209                 btree_find_first(btree, sorted[i], iter2);
 210                 ok1(iter2->item == sorted[i]);
 211         }
 212
 213         if (i != 0)
 214                 fail("Not enough items in btree according to backward traversal");
 215 }
 216
 217 #if 0
 218 //(tries to) remove the key from both the btree and the test array.  Returns 1 on success, 0 on failure.
 219 //success is when an item is removed from the btree and the array, or when none is removed from either
 220 //failure is when an item is removed from the btree but not the array or vice versa
 221 //after removing, it tries removing again to make sure that removal returns 0
 222 static int test_remove(struct btree *btree, struct btree_item items[], size_t *count, const char *key)
 223 {
 224         size_t i;
 225
 226         for (i = *count; i--;) {
 227                 if (!strcmp(items[i].key, key)) {
 228                         //item found in array
 229                         memmove(&items[i], &items[i+1], (*count-(i+1))*sizeof(*items));
 230                         (*count)--;
 231
 232                         //puts("----------");
 233                         //btree_trace(btree);
 234
 235                         //removal should succeed, as the key should be there
 236                         //this is not a contradiction; the test is performed twice
 237                         return btree_remove(btree, key) && !btree_remove(btree, key);
 238                 }
 239         }
 240
 241         //removal should fail, as the key should not be there
 242         //this is not redundant; the test is performed twice
 243         return !btree_remove(btree, key) && !btree_remove(btree, key);
 244 }
 245 #endif
 246
 247 static void test_search_implement(void)
 248 {
 249         struct btree *btree = btree_new(order_by_string);
 250         size_t i;
 251
 252         const char *unsorted[] = {
 253                 "md4",
 254                 "isaac",
 255                 "noerr",
 256                 "talloc_link",
 257                 "asearch",
 258                 "tap",
 259                 "crcsync",
 260                 "wwviaudio",
 261                 "array_size",
 262                 "alignof",
 263                 "str",
 264                 "read_write_all",
 265                 "grab_file",
 266                 "out",
 267                 "daemonize",
 268                 "array",
 269                 "crc",
 270                 "str_talloc",
 271                 "build_assert",
 272                 "talloc",
 273                 "alloc",
 274                 "endian",
 275                 "btree",
 276                 "typesafe_cb",
 277                 "check_type",
 278                 "list",
 279                 "ciniparser",
 280                 "ilog",
 281                 "ccan_tokenizer",
 282                 "tdb",
 283                 "block_pool",
 284                 "sparse_bsearch",
 285                 "container_of",
 286                 "stringmap",
 287                 "hash",
 288                 "short_types",
 289                 "ogg_to_pcm",
 290                 "antithread",
 291         };
 292         size_t count = sizeof(unsorted) / sizeof(*unsorted);
 293         const char *sorted[count];
 294
 295         memcpy(sorted, unsorted, sizeof(sorted));
 296         qsort(sorted, count, sizeof(*sorted), compare_by_string);
 297
 298         for (i=0; i<count; i++) {
 299                 btree_iterator iter;
 300
 301                 if (btree_find_first(btree, unsorted[i], iter))
 302                         fail("btree_insert thinks the test array has duplicates, but it doesn't");
 303                 else
 304                         btree_insert_at(iter, unsorted[i]);
 305         }
 306         btree_trace(btree);
 307
 308         test_traverse(btree, sorted, count);
 309
 310         /*
 311         //try removing items that should be in the tree
 312         ok1(test_remove(btree, sorted, &count, "btree"));
 313         ok1(test_remove(btree, sorted, &count, "ccan_tokenizer"));
 314         ok1(test_remove(btree, sorted, &count, "endian"));
 315         ok1(test_remove(btree, sorted, &count, "md4"));
 316         ok1(test_remove(btree, sorted, &count, "asearch"));
 317         ok1(test_remove(btree, sorted, &count, "alloc"));
 318         ok1(test_remove(btree, sorted, &count, "build_assert"));
 319         ok1(test_remove(btree, sorted, &count, "typesafe_cb"));
 320         ok1(test_remove(btree, sorted, &count, "sparse_bsearch"));
 321         ok1(test_remove(btree, sorted, &count, "stringmap"));
 322
 323         //try removing items that should not be in the tree
 324         ok1(test_remove(btree, sorted, &count, "java"));
 325         ok1(test_remove(btree, sorted, &count, "openoffice"));
 326         ok1(test_remove(btree, sorted, &count, "firefox"));
 327         ok1(test_remove(btree, sorted, &count, "linux"));
 328         ok1(test_remove(btree, sorted, &count, ""));
 329
 330         //test the traversal again to make sure things are okay
 331         test_traverse(btree, sorted, count);
 332
 333         //remove the rest of the items, then make sure tree is empty
 334         while (count)
 335                 ok1(test_remove(btree, sorted, &count, sorted[count-1].key));
 336         ok1(btree->root == NULL);
 337         */
 338
 339         btree_delete(btree);
 340 }
 341
 342 int main(void)
 343 {
 344         struct btree *btree;
 345
 346         plan_tests(224);
 347
 348         btree = btree_new(order_by_key);
 349         btree->destroy = destroy_test_item;
 350         test_insert(btree);
 351         test_find_traverse(btree);
 352         btree_delete(btree);
 353
 354         test_search_implement();
 355
 356         return exit_status();
 357 }