1 /*
2 * critbit89 - A crit-bit tree implementation for strings in C89
3 * Written by Jonas Gehring <jonas@jgehring.net>
4 * SPDX-License-Identifier: GPL-3.0-or-later
5 */
6
7
8 #include <errno.h>
9 #include <stdio.h>
10 #include <stdlib.h>
11 #include <string.h>
12
13 #include "tests/unit/test.h"
14 #include "lib/generic/set.h"
15 #include "lib/utils.h"
16
17
18 /*
19 * Sample dictionary: 100 random words from /usr/share/dict/words
20 * Generated using random.org:
21 * MAX=`wc -l < /usr/share/dict/words | tr -d " "`
22 * for i in `curl "http://www.random.org/integers/?num=100&min=1&max=$MAX&col=1&base=10&format=plain&rnd=new"`; do
23 * nl /usr/share/dict/words | grep -w $i | tr -d "0-9\t "
24 * done
25 */
26 static const char *dict[] = {
27 "catagmatic", "prevaricator", "statoscope", "workhand", "benzamide",
28 "alluvia", "fanciful", "bladish", "Tarsius", "unfast", "appropriative",
29 "seraphically", "monkeypod", "deflectometer", "tanglesome", "zodiacal",
30 "physiologically", "economizer", "forcepslike", "betrumpet",
31 "Danization", "broadthroat", "randir", "usherette", "nephropyosis",
32 "hematocyanin", "chrysohermidin", "uncave", "mirksome", "podophyllum",
33 "siphonognathous", "indoor", "featheriness", "forwardation",
34 "archruler", "soricoid", "Dailamite", "carmoisin", "controllability",
35 "unpragmatical", "childless", "transumpt", "productive",
36 "thyreotoxicosis", "oversorrow", "disshadow", "osse", "roar",
37 "pantomnesia", "talcer", "hydrorrhoea", "Satyridae", "undetesting",
38 "smoothbored", "widower", "sivathere", "pendle", "saltation",
39 "autopelagic", "campfight", "unexplained", "Macrorhamphosus",
40 "absconsa", "counterflory", "interdependent", "triact", "reconcentration",
41 "oversharpness", "sarcoenchondroma", "superstimulate", "assessory",
42 "pseudepiscopacy", "telescopically", "ventriloque", "politicaster",
43 "Caesalpiniaceae", "inopportunity", "Helion", "uncompatible",
44 "cephaloclasia", "oversearch", "Mahayanistic", "quarterspace",
45 "bacillogenic", "hamartite", "polytheistical", "unescapableness",
46 "Pterophorus", "cradlemaking", "Hippoboscidae", "overindustrialize",
47 "perishless", "cupidity", "semilichen", "gadge", "detrimental",
48 "misencourage", "toparchia", "lurchingly", "apocatastasis"
49 };
50
51 /* Insertions */
test_insert(void ** state)52 static void test_insert(void **state)
53 {
54 set_t *set = *state;
55 int dict_size = sizeof(dict) / sizeof(const char *);
56 int i;
57
58 for (i = 0; i < dict_size; i++) {
59 assert_int_equal(set_add(set, dict[i]), 0);
60 }
61 }
62
63 /* Insertion of duplicate element */
test_insert_dup(void ** state)64 static void test_insert_dup(void **state)
65 {
66 set_t *set = *state;
67 int dict_size = sizeof(dict) / sizeof(const char *);
68 int i;
69
70 for (i = 0; i < dict_size; i++) {
71 if (!set_contains(set, dict[i])) {
72 continue;
73 }
74 assert_int_equal(set_add(set, dict[i]), 1);
75 }
76 }
77
78 /* Searching */
test_contains(void ** state)79 static void test_contains(void **state)
80 {
81 set_t *set = *state;
82 char *in;
83 const char *notin = "not in set";
84
85 in = malloc(strlen(dict[23])+1);
86 strcpy(in, dict[23]);
87
88 assert_true(set_contains(set, in));
89 assert_false(set_contains(set, notin));
90 assert_false(set_contains(set, ""));
91 in[strlen(in)/2] = '\0';
92 assert_false(set_contains(set, in));
93
94 free(in);
95 }
96
97 /* Count number of items */
count_cb(const char * s,void * _,void * n)98 static int count_cb(const char *s, void *_, void *n) { (*(int *)n)++; return 0; }
test_complete(set_t * set,int n)99 static void test_complete(set_t *set, int n)
100 {
101 int i = 0;
102 if (set_walk(set, count_cb, &i) != 0) {
103 abort();
104 }
105 if (i != n) {
106 abort();
107 }
108 }
test_complete_full(void ** state)109 static void test_complete_full(void **state) { test_complete(*state, sizeof(dict) / sizeof(const char *)); }
test_complete_zero(void ** state)110 static void test_complete_zero(void **state) { test_complete(*state, 0); }
111
112 /* Deletion */
test_delete(void ** state)113 static void test_delete(void **state)
114 {
115 set_t *set = *state;
116 assert_int_equal(set_del(set, dict[91]), 0);
117 assert_int_equal(set_del(set, "most likely not in set"), 1);
118 }
119
120 /* Complete deletion */
test_delete_all(void ** state)121 static void test_delete_all(void **state)
122 {
123 set_t *set = *state;
124 int dict_size = sizeof(dict) / sizeof(const char *);
125 int i;
126
127 for (i = 0; i < dict_size; i++) {
128 if (!set_contains(set, dict[i])) {
129 continue;
130 }
131 assert_int_equal(set_del(set, dict[i]), 0);
132 }
133 }
134
135 /* Fake allocator */
fake_malloc(void * b,size_t s)136 static void *fake_malloc(void *b, size_t s) { return NULL; }
test_allocator(void ** state)137 static void test_allocator(void **state)
138 {
139 knot_mm_t fake_pool = { .ctx = NULL, .alloc = fake_malloc, .free = NULL };
140 set_t set = set_make(&fake_pool);
141 assert_int_equal(set_add(&set, dict[0]), ENOMEM);
142 }
143
144 /* Empty set */
test_empty(void ** state)145 static void test_empty(void **state)
146 {
147 set_t *set = *state;
148 assert_int_equal(set_contains(set, dict[1]), 0);
149 assert_int_not_equal(set_del(set, dict[1]), 0);
150 }
151
152 /* Prefix walking */
test_prefixes(void ** state)153 static void test_prefixes(void **state)
154 {
155 set_t *set = *state;
156 int i = 0;
157 if ((set_add(set, "1str") != 0) ||
158 (set_add(set, "11str2") != 0) ||
159 (set_add(set, "12str") != 0) ||
160 (set_add(set, "11str") != 0)) {
161 assert_int_equal(1, 0);
162 }
163
164 assert_int_equal(set_walk_prefixed(set, "11", count_cb, &i), 0);
165 assert_int_equal(i, 2);
166 i = 0;
167 assert_int_equal(set_walk_prefixed(set, "13", count_cb, &i), 0);
168 assert_int_equal(i, 0);
169 i = 0;
170 assert_int_equal(set_walk_prefixed(set, "12345678", count_cb, &i), 0);
171 assert_int_equal(i, 0);
172 i = 0;
173 assert_int_equal(set_walk_prefixed(set, "11str", count_cb, &i), 0);
174 assert_int_equal(i, 2);
175 }
176
test_clear(void ** state)177 static void test_clear(void **state)
178 {
179 set_t *set = *state;
180 set_clear(set);
181 }
182
test_init(void ** state)183 static void test_init(void **state)
184 {
185 static set_t set;
186 set = set_make(NULL);
187 *state = &set;
188 assert_non_null(*state);
189 }
190
test_deinit(void ** state)191 static void test_deinit(void **state)
192 {
193 set_t *set = *state;
194 set_clear(set);
195 }
196
197 /* Program entry point */
main(int argc,char ** argv)198 int main(int argc, char **argv)
199 {
200 const UnitTest tests[] = {
201 group_test_setup(test_init),
202 unit_test(test_insert),
203 unit_test(test_complete_full),
204 unit_test(test_insert_dup),
205 unit_test(test_contains),
206 unit_test(test_delete),
207 unit_test(test_clear),
208 unit_test(test_insert),
209 unit_test(test_complete_full),
210 unit_test(test_delete_all),
211 unit_test(test_complete_zero),
212 unit_test(test_allocator),
213 unit_test(test_clear),
214 unit_test(test_empty),
215 unit_test(test_insert),
216 unit_test(test_prefixes),
217 group_test_teardown(test_deinit)
218 };
219
220 return run_group_tests(tests);
221 }
222