1 /*
2 Copyright (c) 2018 Contributors as noted in the AUTHORS file
3
4 This file is part of 0MQ.
5
6 0MQ is free software; you can redistribute it and/or modify it under
7 the terms of the GNU Lesser General Public License as published by
8 the Free Software Foundation; either version 3 of the License, or
9 (at your option) any later version.
10
11 0MQ is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU Lesser General Public License for more details.
15
16 You should have received a copy of the GNU Lesser General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #include "../tests/testutil.hpp"
21
22 #include <radix_tree.hpp>
23 #include <stdint.hpp>
24
25 #include <set>
26 #include <string>
27 #include <string.h>
28 #include <unity.h>
29 #include <vector>
30
setUp()31 void setUp ()
32 {
33 }
tearDown()34 void tearDown ()
35 {
36 }
37
tree_add(zmq::radix_tree_t & tree_,const std::string & key_)38 bool tree_add (zmq::radix_tree_t &tree_, const std::string &key_)
39 {
40 return tree_.add (reinterpret_cast<const unsigned char *> (key_.data ()),
41 key_.size ());
42 }
43
tree_rm(zmq::radix_tree_t & tree_,const std::string & key_)44 bool tree_rm (zmq::radix_tree_t &tree_, const std::string &key_)
45 {
46 return tree_.rm (reinterpret_cast<const unsigned char *> (key_.data ()),
47 key_.size ());
48 }
49
tree_check(zmq::radix_tree_t & tree_,const std::string & key_)50 bool tree_check (zmq::radix_tree_t &tree_, const std::string &key_)
51 {
52 return tree_.check (reinterpret_cast<const unsigned char *> (key_.data ()),
53 key_.size ());
54 }
55
test_empty()56 void test_empty ()
57 {
58 zmq::radix_tree_t tree;
59
60 TEST_ASSERT_TRUE (tree.size () == 0);
61 }
62
test_add_single_entry()63 void test_add_single_entry ()
64 {
65 zmq::radix_tree_t tree;
66
67 TEST_ASSERT_TRUE (tree_add (tree, "foo"));
68 }
69
test_add_same_entry_twice()70 void test_add_same_entry_twice ()
71 {
72 zmq::radix_tree_t tree;
73
74 TEST_ASSERT_TRUE (tree_add (tree, "test"));
75 TEST_ASSERT_FALSE (tree_add (tree, "test"));
76 }
77
test_rm_when_empty()78 void test_rm_when_empty ()
79 {
80 zmq::radix_tree_t tree;
81
82 TEST_ASSERT_FALSE (tree_rm (tree, "test"));
83 }
84
test_rm_single_entry()85 void test_rm_single_entry ()
86 {
87 zmq::radix_tree_t tree;
88
89 tree_add (tree, "temporary");
90 TEST_ASSERT_TRUE (tree_rm (tree, "temporary"));
91 }
92
test_rm_unique_entry_twice()93 void test_rm_unique_entry_twice ()
94 {
95 zmq::radix_tree_t tree;
96
97 tree_add (tree, "test");
98 TEST_ASSERT_TRUE (tree_rm (tree, "test"));
99 TEST_ASSERT_FALSE (tree_rm (tree, "test"));
100 }
101
test_rm_duplicate_entry()102 void test_rm_duplicate_entry ()
103 {
104 zmq::radix_tree_t tree;
105
106 tree_add (tree, "test");
107 tree_add (tree, "test");
108 TEST_ASSERT_FALSE (tree_rm (tree, "test"));
109 TEST_ASSERT_TRUE (tree_rm (tree, "test"));
110 }
111
test_rm_common_prefix()112 void test_rm_common_prefix ()
113 {
114 zmq::radix_tree_t tree;
115
116 tree_add (tree, "checkpoint");
117 tree_add (tree, "checklist");
118 TEST_ASSERT_FALSE (tree_rm (tree, "check"));
119 }
120
test_rm_common_prefix_entry()121 void test_rm_common_prefix_entry ()
122 {
123 zmq::radix_tree_t tree;
124
125 tree_add (tree, "checkpoint");
126 tree_add (tree, "checklist");
127 tree_add (tree, "check");
128 TEST_ASSERT_TRUE (tree_rm (tree, "check"));
129 }
130
test_rm_null_entry()131 void test_rm_null_entry ()
132 {
133 zmq::radix_tree_t tree;
134
135 tree_add (tree, "");
136 TEST_ASSERT_TRUE (tree_rm (tree, ""));
137 }
138
test_check_empty()139 void test_check_empty ()
140 {
141 zmq::radix_tree_t tree;
142
143 TEST_ASSERT_FALSE (tree_check (tree, "foo"));
144 }
145
test_check_added_entry()146 void test_check_added_entry ()
147 {
148 zmq::radix_tree_t tree;
149
150 tree_add (tree, "entry");
151 TEST_ASSERT_TRUE (tree_check (tree, "entry"));
152 }
153
test_check_common_prefix()154 void test_check_common_prefix ()
155 {
156 zmq::radix_tree_t tree;
157
158 tree_add (tree, "introduce");
159 tree_add (tree, "introspect");
160 TEST_ASSERT_FALSE (tree_check (tree, "intro"));
161 }
162
test_check_prefix()163 void test_check_prefix ()
164 {
165 zmq::radix_tree_t tree;
166
167 tree_add (tree, "toasted");
168 TEST_ASSERT_FALSE (tree_check (tree, "toast"));
169 TEST_ASSERT_FALSE (tree_check (tree, "toaste"));
170 TEST_ASSERT_FALSE (tree_check (tree, "toaster"));
171 }
172
test_check_nonexistent_entry()173 void test_check_nonexistent_entry ()
174 {
175 zmq::radix_tree_t tree;
176
177 tree_add (tree, "red");
178 TEST_ASSERT_FALSE (tree_check (tree, "blue"));
179 }
180
test_check_query_longer_than_entry()181 void test_check_query_longer_than_entry ()
182 {
183 zmq::radix_tree_t tree;
184
185 tree_add (tree, "foo");
186 TEST_ASSERT_TRUE (tree_check (tree, "foobar"));
187 }
188
test_check_null_entry_added()189 void test_check_null_entry_added ()
190 {
191 zmq::radix_tree_t tree;
192
193 tree_add (tree, "");
194 TEST_ASSERT_TRUE (tree_check (tree, "all queries return true"));
195 }
196
test_size()197 void test_size ()
198 {
199 zmq::radix_tree_t tree;
200
201 // Adapted from the example on wikipedia.
202 std::vector<std::string> keys;
203 keys.push_back ("tester");
204 keys.push_back ("water");
205 keys.push_back ("slow");
206 keys.push_back ("slower");
207 keys.push_back ("test");
208 keys.push_back ("team");
209 keys.push_back ("toast");
210
211 for (size_t i = 0; i < keys.size (); ++i)
212 TEST_ASSERT_TRUE (tree_add (tree, keys[i]));
213 TEST_ASSERT_TRUE (tree.size () == keys.size ());
214 for (size_t i = 0; i < keys.size (); ++i)
215 TEST_ASSERT_FALSE (tree_add (tree, keys[i]));
216 TEST_ASSERT_TRUE (tree.size () == 2 * keys.size ());
217 for (size_t i = 0; i < keys.size (); ++i)
218 TEST_ASSERT_FALSE (tree_rm (tree, keys[i]));
219 TEST_ASSERT_TRUE (tree.size () == keys.size ());
220 for (size_t i = 0; i < keys.size (); ++i)
221 TEST_ASSERT_TRUE (tree_rm (tree, keys[i]));
222 TEST_ASSERT_TRUE (tree.size () == 0);
223 }
224
return_key(unsigned char * data_,size_t size_,void * arg_)225 void return_key (unsigned char *data_, size_t size_, void *arg_)
226 {
227 std::vector<std::string> *vec =
228 reinterpret_cast<std::vector<std::string> *> (arg_);
229 std::string key;
230 for (size_t i = 0; i < size_; ++i)
231 key.push_back (static_cast<char> (data_[i]));
232 vec->push_back (key);
233 }
234
test_apply()235 void test_apply ()
236 {
237 zmq::radix_tree_t tree;
238
239 std::set<std::string> keys;
240 keys.insert ("tester");
241 keys.insert ("water");
242 keys.insert ("slow");
243 keys.insert ("slower");
244 keys.insert ("test");
245 keys.insert ("team");
246 keys.insert ("toast");
247
248 const std::set<std::string>::iterator end = keys.end ();
249 for (std::set<std::string>::iterator it = keys.begin (); it != end; ++it)
250 tree_add (tree, *it);
251
252 std::vector<std::string> *vec = new std::vector<std::string> ();
253 tree.apply (return_key, static_cast<void *> (vec));
254 for (size_t i = 0; i < vec->size (); ++i)
255 TEST_ASSERT_TRUE (keys.count ((*vec)[i]) > 0);
256 delete vec;
257 }
258
main(void)259 int main (void)
260 {
261 setup_test_environment ();
262
263 UNITY_BEGIN ();
264
265 RUN_TEST (test_empty);
266 RUN_TEST (test_add_single_entry);
267 RUN_TEST (test_add_same_entry_twice);
268
269 RUN_TEST (test_rm_when_empty);
270 RUN_TEST (test_rm_single_entry);
271 RUN_TEST (test_rm_unique_entry_twice);
272 RUN_TEST (test_rm_duplicate_entry);
273 RUN_TEST (test_rm_common_prefix);
274 RUN_TEST (test_rm_common_prefix_entry);
275 RUN_TEST (test_rm_null_entry);
276
277 RUN_TEST (test_check_empty);
278 RUN_TEST (test_check_added_entry);
279 RUN_TEST (test_check_common_prefix);
280 RUN_TEST (test_check_prefix);
281 RUN_TEST (test_check_nonexistent_entry);
282 RUN_TEST (test_check_query_longer_than_entry);
283 RUN_TEST (test_check_null_entry_added);
284
285 RUN_TEST (test_size);
286
287 RUN_TEST (test_apply);
288
289 return UNITY_END ();
290 }
291