ucw/trie-test.c

   1 /*
   2  *      UCW Library -- Byte-based trie -- Testing utility
   3  *
   4  *      (c) 2008 Pavel Charvat <pchar@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #undef LOCAL_DEBUG
  11
  12 #include "ucw/lib.h"
  13 #include "ucw/getopt.h"
  14
  15 #include <stdlib.h>
  16 #include <string.h>
  17 #include <time.h>
  18
  19 #define TRIE_PREFIX(x) basic_##x
  20 #define TRIE_NODE_TYPE char
  21 #define TRIE_WANT_CLEANUP
  22 #define TRIE_WANT_ADD
  23 #define TRIE_WANT_DELETE
  24 #define TRIE_WANT_FIND
  25 #define TRIE_WANT_AUDIT
  26 #ifdef LOCAL_DEBUG
  27 #define TRIE_TRACE
  28 #endif
  29 #include "ucw/trie.h"
  30
  31 static void
  32 basic_test(void)
  33 {
  34   basic_init();
  35   basic_add("str1");
  36   basic_add("str2");
  37   if (!basic_find("str1") || !basic_find("str2") || basic_find("x") || basic_find("str123"))
  38     ASSERT(0);
  39   basic_audit();
  40   basic_delete("str1");
  41   if (basic_find("str1") || !basic_find("str2"))
  42     ASSERT(0);
  43   basic_audit();
  44   basic_cleanup();
  45 }
  46
  47 #define TRIE_PREFIX(x) dynamic_##x
  48 #define TRIE_NODE_TYPE char
  49 #define TRIE_REV
  50 #define TRIE_DYNAMIC
  51 #define TRIE_WANT_CLEANUP
  52 #define TRIE_WANT_ADD
  53 #define TRIE_WANT_FIND
  54 #define TRIE_WANT_AUDIT
  55 #ifdef LOCAL_DEBUG
  56 #define TRIE_TRACE
  57 #endif
  58 #include "ucw/trie.h"
  59
  60 static void
  61 dynamic_test(void)
  62 {
  63   struct dynamic_trie trie1, trie2;
  64   dynamic_init(&trie1);
  65   dynamic_init(&trie2);
  66   dynamic_add(&trie1, "str1");
  67   dynamic_add(&trie2, "str2");
  68   if (!dynamic_find(&trie1, "str1") || dynamic_find(&trie1, "str2") || !dynamic_find(&trie2, "str2"))
  69     ASSERT(0);
  70   dynamic_audit(&trie1);
  71   dynamic_audit(&trie2);
  72   dynamic_cleanup(&trie1);
  73   dynamic_cleanup(&trie2);
  74 }
  75
  76
  77 #define TRIE_PREFIX(x) random_##x
  78 #define TRIE_NODE_TYPE char
  79 #define TRIE_LEN_TYPE u16
  80 #undef TRIE_REV
  81 #define TRIE_WANT_CLEANUP
  82 #define TRIE_WANT_FIND
  83 #define TRIE_WANT_ADD
  84 #define TRIE_WANT_REMOVE
  85 #define TRIE_WANT_AUDIT
  86 #ifdef LOCAL_DEBUG
  87 #define TRIE_TRACE
  88 #endif
  89 #include "ucw/trie.h"
  90
  91 #define MAX_STRINGS 200
  92
  93 static uns count;
  94 static char *str[MAX_STRINGS];
  95
  96 static char *
  97 gen_string(void)
  98 {
  99   uns l = random_max(11);
 100   char *s = xmalloc(l + 1);
 101   for (uns i = 0; i < l; i++)
 102     s[i] = random_max('z' - 'a') + 'a';
 103   s[l] = 0;
 104   return s;
 105 }
 106
 107 static char *
 108 gen_unique_string(void)
 109 {
 110   char *s;
 111 again:
 112   s = gen_string();
 113   for (uns i = 0; i < count; i++)
 114     if (!strcmp(s, str[i]))
 115       {
 116         xfree(s);
 117         goto again;
 118       }
 119   return s;
 120 }
 121
 122 static void
 123 insert(void)
 124 {
 125   if (count == MAX_STRINGS)
 126     return;
 127   char *s = gen_unique_string();
 128   str[count++] = s;
 129   DBG("add '%s'", s);
 130   random_add(s);
 131   random_audit();
 132 }
 133
 134 static void
 135 delete(void)
 136 {
 137   if (!count)
 138     return;
 139   uns i = random_max(count);
 140   DBG("remove '%s'", str[i]);
 141   random_remove(str[i]);
 142   random_audit();
 143   xfree(str[i]);
 144   str[i] = str[--count];
 145 }
 146
 147 static void
 148 find(void)
 149 {
 150   if (!count || !random_max(4))
 151     {
 152       char *s = gen_unique_string();
 153       DBG("negative find '%s'", s);
 154       if (random_find(s))
 155         ASSERT(0);
 156       xfree(s);
 157     }
 158   else
 159     {
 160       uns i = random_max(count);
 161       DBG("positive find '%s'", str[i]);
 162       if (random_find(str[i]) != str[i])
 163         ASSERT(0);
 164     }
 165 }
 166
 167 static void
 168 reset(void)
 169 {
 170   DBG("reset");
 171   random_cleanup();
 172   for (uns i = 0; i < count; i++)
 173     xfree(str[i]);
 174   count = 0;
 175   random_init();
 176   random_audit();
 177 }
 178
 179 static void
 180 random_test(void)
 181 {
 182   random_init();
 183   for (uns i = 0; i < 10000; i++)
 184     {
 185       int r = random_max(1000);
 186       if ((r -= 300) < 0)
 187         insert();
 188       else if ((r -= 150) < 0)
 189         delete();
 190       else if ((r -= 300) < 0)
 191         find();
 192       else if ((r -= 1) < 0)
 193         reset();
 194     }
 195   random_cleanup();
 196 }
 197
 198 int main(int argc, char **argv)
 199 {
 200   log_init(argv[0]);
 201   if (cf_getopt(argc, argv, CF_SHORT_OPTS, CF_NO_LONG_OPTS, NULL) >= 0 || optind + 1 != argc)
 202     die("Invalid usage, see the source code");
 203   srandom(time(NULL));
 204
 205   char *test = argv[optind];
 206   if (!strcmp(test, "basic"))
 207     basic_test();
 208   else if (!strcmp(test, "dynamic"))
 209     dynamic_test();
 210   else if (!strcmp(test, "random"))
 211     random_test();
 212   else
 213     die("Unknown test case");
 214
 215   return 0;
 216 }