tests/trie.c

   1 // Copyright © Tavian Barnes <tavianator@tavianator.com>
   2 // SPDX-License-Identifier: 0BSD
   3
   4 #include "../src/trie.h"
   5 #include "../src/config.h"
   6 #include "../src/diag.h"
   7 #include <stdlib.h>
   8 #include <string.h>
   9
  10 const char *keys[] = {
  11         "foo",
  12         "bar",
  13         "baz",
  14         "qux",
  15         "quux",
  16         "quuux",
  17         "quuuux",
  18
  19         "pre",
  20         "pref",
  21         "prefi",
  22         "prefix",
  23
  24         "AAAA",
  25         "AADD",
  26         "ABCD",
  27         "DDAA",
  28         "DDDD",
  29
  30         "<<<",
  31         "<<<>>>",
  32         "<<<<<<",
  33         "<<<<<<>>>>>>",
  34         ">>>>>>",
  35         ">>><<<",
  36         ">>>",
  37 };
  38
  39 const size_t nkeys = countof(keys);
  40
  41 int main(void) {
  42         struct trie trie;
  43         trie_init(&trie);
  44
  45         for (size_t i = 0; i < nkeys; ++i) {
  46                 bfs_verify(!trie_find_str(&trie, keys[i]));
  47
  48                 const char *prefix = NULL;
  49                 for (size_t j = 0; j < i; ++j) {
  50                         if (strncmp(keys[i], keys[j], strlen(keys[j])) == 0) {
  51                                 if (!prefix || strcmp(keys[j], prefix) > 0) {
  52                                         prefix = keys[j];
  53                                 }
  54                         }
  55                 }
  56
  57                 struct trie_leaf *leaf = trie_find_prefix(&trie, keys[i]);
  58                 if (prefix) {
  59                         bfs_verify(leaf);
  60                         bfs_verify(strcmp(prefix, leaf->key) == 0);
  61                 } else {
  62                         bfs_verify(!leaf);
  63                 }
  64
  65                 leaf = trie_insert_str(&trie, keys[i]);
  66                 bfs_verify(leaf);
  67                 bfs_verify(strcmp(keys[i], leaf->key) == 0);
  68                 bfs_verify(leaf->length == strlen(keys[i]) + 1);
  69         }
  70
  71         {
  72                 size_t i = 0;
  73                 for_trie (leaf, &trie) {
  74                         bfs_verify(leaf == trie_find_str(&trie, keys[i]));
  75                         bfs_verify(!leaf->prev || leaf->prev->next == leaf);
  76                         bfs_verify(!leaf->next || leaf->next->prev == leaf);
  77                         ++i;
  78                 }
  79                 bfs_verify(i == nkeys);
  80         }
  81
  82         for (size_t i = 0; i < nkeys; ++i) {
  83                 struct trie_leaf *leaf = trie_find_str(&trie, keys[i]);
  84                 bfs_verify(leaf);
  85                 bfs_verify(strcmp(keys[i], leaf->key) == 0);
  86                 bfs_verify(leaf->length == strlen(keys[i]) + 1);
  87
  88                 trie_remove(&trie, leaf);
  89                 leaf = trie_find_str(&trie, keys[i]);
  90                 bfs_verify(!leaf);
  91
  92                 const char *postfix = NULL;
  93                 for (size_t j = i + 1; j < nkeys; ++j) {
  94                         if (strncmp(keys[i], keys[j], strlen(keys[i])) == 0) {
  95                                 if (!postfix || strcmp(keys[j], postfix) < 0) {
  96                                         postfix = keys[j];
  97                                 }
  98                         }
  99                 }
 100
 101                 leaf = trie_find_postfix(&trie, keys[i]);
 102                 if (postfix) {
 103                         bfs_verify(leaf);
 104                         bfs_verify(strcmp(postfix, leaf->key) == 0);
 105                 } else {
 106                         bfs_verify(!leaf);
 107                 }
 108         }
 109
 110         for_trie (leaf, &trie) {
 111                 bfs_verify(false);
 112         }
 113
 114         // This tests the "jump" node handling on 32-bit platforms
 115         size_t longsize = 1 << 20;
 116         char *longstr = malloc(longsize);
 117         bfs_verify(longstr);
 118
 119         memset(longstr, 0xAC, longsize);
 120         bfs_verify(!trie_find_mem(&trie, longstr, longsize));
 121         bfs_verify(trie_insert_mem(&trie, longstr, longsize));
 122
 123         memset(longstr + longsize / 2, 0xAB, longsize / 2);
 124         bfs_verify(!trie_find_mem(&trie, longstr, longsize));
 125         bfs_verify(trie_insert_mem(&trie, longstr, longsize));
 126
 127         memset(longstr, 0xAA, longsize / 2);
 128         bfs_verify(!trie_find_mem(&trie, longstr, longsize));
 129         bfs_verify(trie_insert_mem(&trie, longstr, longsize));
 130
 131         free(longstr);
 132         trie_destroy(&trie);
 133         return EXIT_SUCCESS;
 134 }