1/*
2Copyright (c) 2018 Contributors as noted in the AUTHORS file
3
4This file is part of 0MQ.
5
60MQ is free software; you can redistribute it and/or modify it under
7the terms of the GNU Lesser General Public License as published by
8the Free Software Foundation; either version 3 of the License, or
9(at your option) any later version.
10
110MQ is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14GNU Lesser General Public License for more details.
15
16You should have received a copy of the GNU Lesser General Public License
17along 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
31void setUp ()
32{
33}
34void tearDown ()
35{
36}
37
38bool 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
44bool 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
50bool 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
56void test_empty ()
57{
58 zmq::radix_tree_t tree;
59
60 TEST_ASSERT_TRUE (tree.size () == 0);
61}
62
63void test_add_single_entry ()
64{
65 zmq::radix_tree_t tree;
66
67 TEST_ASSERT_TRUE (tree_add (tree, "foo"));
68}
69
70void 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
78void test_rm_when_empty ()
79{
80 zmq::radix_tree_t tree;
81
82 TEST_ASSERT_FALSE (tree_rm (tree, "test"));
83}
84
85void 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
93void 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
102void 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
112void 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
121void 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
131void 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
139void test_check_empty ()
140{
141 zmq::radix_tree_t tree;
142
143 TEST_ASSERT_FALSE (tree_check (tree, "foo"));
144}
145
146void 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
154void 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
163void 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
173void 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
181void 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
189void 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
197void 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
225void 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
235void 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
259int 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