blob: d51474dd74bbe073ba677223b95237b5e5577f41 [file] [log] [blame]
HYuana9b85752014-02-26 02:32:30 -06001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
Junxiao Shif54d0302017-09-07 18:16:38 +00002/*
Davide Pesaventocf7db2f2019-03-24 23:17:28 -04003 * Copyright (c) 2014-2019, Regents of the University of California,
Spyridon Mastorakisd0381c02015-02-19 10:29:41 -08004 * Arizona Board of Regents,
5 * Colorado State University,
6 * University Pierre & Marie Curie, Sorbonne University,
7 * Washington University in St. Louis,
8 * Beijing Institute of Technology,
9 * The University of Memphis.
Alexander Afanasyev9bcbc7c2014-04-06 19:37:37 -070010 *
11 * This file is part of NFD (Named Data Networking Forwarding Daemon).
12 * See AUTHORS.md for complete list of NFD authors and contributors.
13 *
14 * NFD is free software: you can redistribute it and/or modify it under the terms
15 * of the GNU General Public License as published by the Free Software Foundation,
16 * either version 3 of the License, or (at your option) any later version.
17 *
18 * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
19 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
20 * PURPOSE. See the GNU General Public License for more details.
21 *
22 * You should have received a copy of the GNU General Public License along with
23 * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
Alexander Afanasyev28d586a2014-07-10 20:10:54 -070024 */
HYuana9b85752014-02-26 02:32:30 -060025
26#include "table/name-tree.hpp"
Junxiao Shi60607c72014-11-26 22:40:36 -070027
Junxiao Shid9ee45c2014-02-27 15:38:11 -070028#include "tests/test-common.hpp"
Davide Pesaventocf7db2f2019-03-24 23:17:28 -040029#include "tests/daemon/global-io-fixture.hpp"
HYuana9b85752014-02-26 02:32:30 -060030
31namespace nfd {
Junxiao Shi2570f3e2016-07-27 02:48:29 +000032namespace name_tree {
Junxiao Shid9ee45c2014-02-27 15:38:11 -070033namespace tests {
HYuana9b85752014-02-26 02:32:30 -060034
Junxiao Shi2570f3e2016-07-27 02:48:29 +000035using namespace nfd::tests;
HYuana9b85752014-02-26 02:32:30 -060036
Junxiao Shi2570f3e2016-07-27 02:48:29 +000037BOOST_AUTO_TEST_SUITE(Table)
Davide Pesaventocf7db2f2019-03-24 23:17:28 -040038BOOST_FIXTURE_TEST_SUITE(TestNameTree, GlobalIoFixture)
HYuana9b85752014-02-26 02:32:30 -060039
Junxiao Shib660b4c2016-08-06 20:47:44 +000040BOOST_AUTO_TEST_CASE(ComputeHash)
Haowei Yuanf52dac72014-03-24 23:35:03 -050041{
42 Name root("/");
43 root.wireEncode();
Junxiao Shib660b4c2016-08-06 20:47:44 +000044 HashValue hashValue = computeHash(root);
Junxiao Shi2570f3e2016-07-27 02:48:29 +000045 BOOST_CHECK_EQUAL(hashValue, 0);
Haowei Yuanf52dac72014-03-24 23:35:03 -050046
47 Name prefix("/nohello/world/ndn/research");
48 prefix.wireEncode();
Junxiao Shib660b4c2016-08-06 20:47:44 +000049 HashSequence hashes = computeHashes(prefix);
50 BOOST_CHECK_EQUAL(hashes.size(), prefix.size() + 1);
Junxiao Shif54d0302017-09-07 18:16:38 +000051
52 hashes = computeHashes(prefix, 2);
53 BOOST_CHECK_EQUAL(hashes.size(), 3);
Haowei Yuanf52dac72014-03-24 23:35:03 -050054}
55
Junxiao Shib660b4c2016-08-06 20:47:44 +000056BOOST_AUTO_TEST_SUITE(Hashtable)
57using name_tree::Hashtable;
58
59BOOST_AUTO_TEST_CASE(Modifiers)
60{
61 Hashtable ht(HashtableOptions(16));
62
63 Name name("/A/B/C/D");
64 HashSequence hashes = computeHashes(name);
65
66 BOOST_CHECK_EQUAL(ht.size(), 0);
67 BOOST_CHECK(ht.find(name, 2) == nullptr);
68
69 const Node* node = nullptr;
70 bool isNew = false;
71 std::tie(node, isNew) = ht.insert(name, 2, hashes);
72 BOOST_CHECK_EQUAL(isNew, true);
73 BOOST_CHECK(node != nullptr);
74 BOOST_CHECK_EQUAL(ht.size(), 1);
75 BOOST_CHECK_EQUAL(ht.find(name, 2), node);
76 BOOST_CHECK_EQUAL(ht.find(name, 2, hashes), node);
77
78 BOOST_CHECK(ht.find(name, 0) == nullptr);
79 BOOST_CHECK(ht.find(name, 1) == nullptr);
80 BOOST_CHECK(ht.find(name, 3) == nullptr);
81 BOOST_CHECK(ht.find(name, 4) == nullptr);
82
83 const Node* node2 = nullptr;
84 std::tie(node2, isNew) = ht.insert(name, 2, hashes);
85 BOOST_CHECK_EQUAL(isNew, false);
86 BOOST_CHECK_EQUAL(node2, node);
87 BOOST_CHECK_EQUAL(ht.size(), 1);
88
89 std::tie(node2, isNew) = ht.insert(name, 4, hashes);
90 BOOST_CHECK_EQUAL(isNew, true);
91 BOOST_CHECK(node2 != nullptr);
92 BOOST_CHECK_NE(node2, node);
93 BOOST_CHECK_EQUAL(ht.size(), 2);
94
95 ht.erase(const_cast<Node*>(node2));
96 BOOST_CHECK_EQUAL(ht.size(), 1);
97 BOOST_CHECK(ht.find(name, 4) == nullptr);
98 BOOST_CHECK_EQUAL(ht.find(name, 2), node);
99
100 ht.erase(const_cast<Node*>(node));
101 BOOST_CHECK_EQUAL(ht.size(), 0);
102 BOOST_CHECK(ht.find(name, 2) == nullptr);
103 BOOST_CHECK(ht.find(name, 4) == nullptr);
104}
105
106BOOST_AUTO_TEST_CASE(Resize)
107{
108 HashtableOptions options(9);
109 BOOST_CHECK_EQUAL(options.initialSize, 9);
110 BOOST_CHECK_EQUAL(options.minSize, 9);
111 options.minSize = 6;
112 options.expandLoadFactor = 0.80;
113 options.expandFactor = 5.0;
114 options.shrinkLoadFactor = 0.12;
115 options.shrinkFactor = 0.3;
116
117 Hashtable ht(options);
118
119 auto addNodes = [&ht] (int min, int max) {
120 for (int i = min; i <= max; ++i) {
121 Name name;
122 name.appendNumber(i);
123 HashSequence hashes = computeHashes(name);
124 ht.insert(name, name.size(), hashes);
125 }
126 };
127
128 auto removeNodes = [&ht] (int min, int max) {
129 for (int i = min; i <= max; ++i) {
130 Name name;
131 name.appendNumber(i);
132 const Node* node = ht.find(name, name.size());
133 BOOST_REQUIRE(node != nullptr);
134 ht.erase(const_cast<Node*>(node));
135 }
136 };
137
138 BOOST_CHECK_EQUAL(ht.size(), 0);
139 BOOST_CHECK_EQUAL(ht.getNBuckets(), 9);
140
141 addNodes(1, 1);
142 BOOST_CHECK_EQUAL(ht.size(), 1);
143 BOOST_CHECK_EQUAL(ht.getNBuckets(), 9);
144
145 removeNodes(1, 1);
146 BOOST_CHECK_EQUAL(ht.size(), 0);
147 BOOST_CHECK_EQUAL(ht.getNBuckets(), 6);
148
149 addNodes(1, 4);
150 BOOST_CHECK_EQUAL(ht.size(), 4);
151 BOOST_CHECK_EQUAL(ht.getNBuckets(), 6);
152
153 addNodes(5, 5);
154 BOOST_CHECK_EQUAL(ht.size(), 5);
155 BOOST_CHECK_EQUAL(ht.getNBuckets(), 30);
156
157 addNodes(6, 23);
158 BOOST_CHECK_EQUAL(ht.size(), 23);
159 BOOST_CHECK_EQUAL(ht.getNBuckets(), 30);
160
161 addNodes(24, 25);
162 BOOST_CHECK_EQUAL(ht.size(), 25);
163 BOOST_CHECK_EQUAL(ht.getNBuckets(), 150);
164
165 removeNodes(19, 25);
166 BOOST_CHECK_EQUAL(ht.size(), 18);
167 BOOST_CHECK_EQUAL(ht.getNBuckets(), 150);
168
169 removeNodes(17, 18);
170 BOOST_CHECK_EQUAL(ht.size(), 16);
171 BOOST_CHECK_EQUAL(ht.getNBuckets(), 45);
172
173 removeNodes(7, 16);
174 BOOST_CHECK_EQUAL(ht.size(), 6);
175 BOOST_CHECK_EQUAL(ht.getNBuckets(), 45);
176
177 removeNodes(5, 6);
178 BOOST_CHECK_EQUAL(ht.size(), 4);
179 BOOST_CHECK_EQUAL(ht.getNBuckets(), 13);
180
181 removeNodes(1, 4);
182 BOOST_CHECK_EQUAL(ht.size(), 0);
183 BOOST_CHECK_EQUAL(ht.getNBuckets(), 6);
184}
185
186BOOST_AUTO_TEST_SUITE_END() // Hashtable
187
Junxiao Shi340d5532016-08-13 04:00:35 +0000188BOOST_AUTO_TEST_SUITE(TestEntry)
189
190BOOST_AUTO_TEST_CASE(TreeRelation)
HYuana9b85752014-02-26 02:32:30 -0600191{
Junxiao Shi340d5532016-08-13 04:00:35 +0000192 Name name("ndn:/named-data/research/abc/def/ghi");
193 auto node = make_unique<Node>(0, name);
194 Entry& npe = node->entry;
195 BOOST_CHECK(npe.getParent() == nullptr);
HYuana9b85752014-02-26 02:32:30 -0600196
Junxiao Shi340d5532016-08-13 04:00:35 +0000197 Name parentName = name.getPrefix(-1);
Junxiao Shib660b4c2016-08-06 20:47:44 +0000198 auto parentNode = make_unique<Node>(1, parentName);
Junxiao Shi340d5532016-08-13 04:00:35 +0000199 Entry& parent = parentNode->entry;
200 BOOST_CHECK_EQUAL(parent.hasChildren(), false);
201 BOOST_CHECK_EQUAL(parent.isEmpty(), true);
HYuana9b85752014-02-26 02:32:30 -0600202
Junxiao Shi340d5532016-08-13 04:00:35 +0000203 npe.setParent(parentNode->entry);
204 BOOST_CHECK_EQUAL(npe.getParent(), &parent);
205 BOOST_CHECK_EQUAL(parent.hasChildren(), true);
206 BOOST_CHECK_EQUAL(parent.isEmpty(), false);
207 BOOST_REQUIRE_EQUAL(parent.getChildren().size(), 1);
208 BOOST_CHECK_EQUAL(parent.getChildren().front(), &npe);
HYuana9b85752014-02-26 02:32:30 -0600209
Junxiao Shi340d5532016-08-13 04:00:35 +0000210 npe.unsetParent();
211 BOOST_CHECK(npe.getParent() == nullptr);
212 BOOST_CHECK_EQUAL(parent.hasChildren(), false);
213 BOOST_CHECK_EQUAL(parent.isEmpty(), true);
HYuana9b85752014-02-26 02:32:30 -0600214}
215
Junxiao Shi340d5532016-08-13 04:00:35 +0000216BOOST_AUTO_TEST_CASE(TableEntries)
217{
218 Name name("ndn:/named-data/research/abc/def/ghi");
219 Node node(0, name);
220 Entry& npe = node.entry;
221 BOOST_CHECK_EQUAL(npe.getName(), name);
222
223 BOOST_CHECK_EQUAL(npe.hasTableEntries(), false);
224 BOOST_CHECK_EQUAL(npe.isEmpty(), true);
225 BOOST_CHECK(npe.getFibEntry() == nullptr);
226 BOOST_CHECK_EQUAL(npe.hasPitEntries(), false);
227 BOOST_CHECK_EQUAL(npe.getPitEntries().empty(), true);
228 BOOST_CHECK(npe.getMeasurementsEntry() == nullptr);
229 BOOST_CHECK(npe.getStrategyChoiceEntry() == nullptr);
230
231 npe.setFibEntry(make_unique<fib::Entry>(name));
232 BOOST_REQUIRE(npe.getFibEntry() != nullptr);
233 BOOST_CHECK_EQUAL(npe.getFibEntry()->getPrefix(), name);
234 BOOST_CHECK_EQUAL(npe.hasTableEntries(), true);
235 BOOST_CHECK_EQUAL(npe.isEmpty(), false);
236
237 npe.setFibEntry(nullptr);
238 BOOST_CHECK(npe.getFibEntry() == nullptr);
239 BOOST_CHECK_EQUAL(npe.hasTableEntries(), false);
240 BOOST_CHECK_EQUAL(npe.isEmpty(), true);
241
Junxiao Shi25d97282019-05-14 13:44:46 -0600242 auto interest1 = makeInterest(name);
243 auto pit1 = make_shared<pit::Entry>(*interest1);
244 auto interest2 = makeInterest(name);
245 interest2->setMustBeFresh(true);
Junxiao Shi340d5532016-08-13 04:00:35 +0000246 auto pit2 = make_shared<pit::Entry>(*interest2);
247
248 npe.insertPitEntry(pit1);
249 BOOST_CHECK_EQUAL(npe.hasPitEntries(), true);
250 BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 1);
251 BOOST_CHECK_EQUAL(npe.hasTableEntries(), true);
252 BOOST_CHECK_EQUAL(npe.isEmpty(), false);
253
254 npe.insertPitEntry(pit2);
255 BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 2);
256
Junxiao Shidbef6dc2016-08-15 02:58:36 +0000257 pit::Entry* pit1ptr = pit1.get();
258 weak_ptr<pit::Entry> pit1weak(pit1);
259 pit1.reset();
260 BOOST_CHECK_EQUAL(pit1weak.use_count(), 1); // npe is the sole owner of pit1
261 npe.erasePitEntry(pit1ptr);
Junxiao Shi340d5532016-08-13 04:00:35 +0000262 BOOST_REQUIRE_EQUAL(npe.getPitEntries().size(), 1);
Davide Pesavento7890a9f2019-08-25 23:11:18 -0400263 BOOST_CHECK(&npe.getPitEntries().front()->getInterest() == interest2.get());
Junxiao Shi340d5532016-08-13 04:00:35 +0000264
Junxiao Shidbef6dc2016-08-15 02:58:36 +0000265 npe.erasePitEntry(pit2.get());
Junxiao Shi340d5532016-08-13 04:00:35 +0000266 BOOST_CHECK_EQUAL(npe.hasPitEntries(), false);
267 BOOST_CHECK_EQUAL(npe.getPitEntries().size(), 0);
268 BOOST_CHECK_EQUAL(npe.hasTableEntries(), false);
269 BOOST_CHECK_EQUAL(npe.isEmpty(), true);
270
271 npe.setMeasurementsEntry(make_unique<measurements::Entry>(name));
272 BOOST_REQUIRE(npe.getMeasurementsEntry() != nullptr);
273 BOOST_CHECK_EQUAL(npe.getMeasurementsEntry()->getName(), name);
274 BOOST_CHECK_EQUAL(npe.hasTableEntries(), true);
275 BOOST_CHECK_EQUAL(npe.isEmpty(), false);
276
277 npe.setMeasurementsEntry(nullptr);
278 BOOST_CHECK(npe.getMeasurementsEntry() == nullptr);
279 BOOST_CHECK_EQUAL(npe.hasTableEntries(), false);
280 BOOST_CHECK_EQUAL(npe.isEmpty(), true);
281
282 npe.setStrategyChoiceEntry(make_unique<strategy_choice::Entry>(name));
283 BOOST_REQUIRE(npe.getStrategyChoiceEntry() != nullptr);
284 BOOST_CHECK_EQUAL(npe.getStrategyChoiceEntry()->getPrefix(), name);
285 BOOST_CHECK_EQUAL(npe.hasTableEntries(), true);
286 BOOST_CHECK_EQUAL(npe.isEmpty(), false);
287
288 npe.setStrategyChoiceEntry(nullptr);
289 BOOST_CHECK(npe.getStrategyChoiceEntry() == nullptr);
290 BOOST_CHECK_EQUAL(npe.hasTableEntries(), false);
291 BOOST_CHECK_EQUAL(npe.isEmpty(), true);
292}
293
294BOOST_AUTO_TEST_SUITE_END() // TestEntry
295
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700296BOOST_AUTO_TEST_CASE(Basic)
HYuana9b85752014-02-26 02:32:30 -0600297{
298 size_t nBuckets = 16;
299 NameTree nt(nBuckets);
300
301 BOOST_CHECK_EQUAL(nt.size(), 0);
Haowei Yuane1079fc2014-03-08 14:41:25 -0600302 BOOST_CHECK_EQUAL(nt.getNBuckets(), nBuckets);
HYuana9b85752014-02-26 02:32:30 -0600303
Junxiao Shi7f358432016-08-11 17:06:33 +0000304 // lookup
305
Junxiao Shif54d0302017-09-07 18:16:38 +0000306 Name nameABC("/a/b/c");
Junxiao Shi7f358432016-08-11 17:06:33 +0000307 Entry& npeABC = nt.lookup(nameABC);
HYuana9b85752014-02-26 02:32:30 -0600308 BOOST_CHECK_EQUAL(nt.size(), 4);
Haowei Yuane1079fc2014-03-08 14:41:25 -0600309
310 Name nameABD("/a/b/d");
Junxiao Shi7f358432016-08-11 17:06:33 +0000311 Entry& npeABD = nt.lookup(nameABD);
HYuana9b85752014-02-26 02:32:30 -0600312 BOOST_CHECK_EQUAL(nt.size(), 5);
313
Haowei Yuane1079fc2014-03-08 14:41:25 -0600314 Name nameAE("/a/e/");
Junxiao Shi7f358432016-08-11 17:06:33 +0000315 Entry& npeAE = nt.lookup(nameAE);
HYuana9b85752014-02-26 02:32:30 -0600316 BOOST_CHECK_EQUAL(nt.size(), 6);
317
Haowei Yuane1079fc2014-03-08 14:41:25 -0600318 Name nameF("/f");
Junxiao Shi7f358432016-08-11 17:06:33 +0000319 Entry& npeF = nt.lookup(nameF);
HYuana9b85752014-02-26 02:32:30 -0600320 BOOST_CHECK_EQUAL(nt.size(), 7);
321
Junxiao Shi7f358432016-08-11 17:06:33 +0000322 // getParent and findExactMatch
HYuana9b85752014-02-26 02:32:30 -0600323
Junxiao Shi811c0102016-08-10 04:12:45 +0000324 Name nameAB("/a/b");
Junxiao Shi7f358432016-08-11 17:06:33 +0000325 BOOST_CHECK_EQUAL(npeABC.getParent(), nt.findExactMatch(nameAB));
326 BOOST_CHECK_EQUAL(npeABD.getParent(), nt.findExactMatch(nameAB));
HYuana9b85752014-02-26 02:32:30 -0600327
Junxiao Shi7f358432016-08-11 17:06:33 +0000328 Name nameA("/a");
329 BOOST_CHECK_EQUAL(npeAE.getParent(), nt.findExactMatch(nameA));
HYuana9b85752014-02-26 02:32:30 -0600330
Junxiao Shi7f358432016-08-11 17:06:33 +0000331 Name nameRoot("/");
332 BOOST_CHECK_EQUAL(npeF.getParent(), nt.findExactMatch(nameRoot));
HYuana9b85752014-02-26 02:32:30 -0600333 BOOST_CHECK_EQUAL(nt.size(), 7);
334
Haowei Yuane1079fc2014-03-08 14:41:25 -0600335 Name name0("/does/not/exist");
Junxiao Shi811c0102016-08-10 04:12:45 +0000336 Entry* npe0 = nt.findExactMatch(name0);
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000337 BOOST_CHECK(npe0 == nullptr);
HYuana9b85752014-02-26 02:32:30 -0600338
339
Junxiao Shi7f358432016-08-11 17:06:33 +0000340 // findLongestPrefixMatch
341
Junxiao Shi811c0102016-08-10 04:12:45 +0000342 Entry* temp = nullptr;
HYuana9b85752014-02-26 02:32:30 -0600343 Name nameABCLPM("/a/b/c/def/asdf/nlf");
344 temp = nt.findLongestPrefixMatch(nameABCLPM);
345 BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameABC));
346
347 Name nameABDLPM("/a/b/d/def/asdf/nlf");
348 temp = nt.findLongestPrefixMatch(nameABDLPM);
349 BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameABD));
350
351 Name nameABLPM("/a/b/hello/world");
352 temp = nt.findLongestPrefixMatch(nameABLPM);
353 BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameAB));
354
355 Name nameAELPM("/a/e/hello/world");
356 temp = nt.findLongestPrefixMatch(nameAELPM);
357 BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameAE));
358
359 Name nameALPM("/a/hello/world");
360 temp = nt.findLongestPrefixMatch(nameALPM);
361 BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameA));
362
363 Name nameFLPM("/f/hello/world");
364 temp = nt.findLongestPrefixMatch(nameFLPM);
365 BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameF));
366
367 Name nameRootLPM("/does_not_exist");
368 temp = nt.findLongestPrefixMatch(nameRootLPM);
369 BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameRoot));
370
HYuana9b85752014-02-26 02:32:30 -0600371 bool eraseResult = false;
372 temp = nt.findExactMatch(nameABC);
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000373 if (temp != nullptr)
Junxiao Shi811c0102016-08-10 04:12:45 +0000374 eraseResult = nt.eraseIfEmpty(temp);
HYuana9b85752014-02-26 02:32:30 -0600375 BOOST_CHECK_EQUAL(nt.size(), 6);
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000376 BOOST_CHECK(nt.findExactMatch(nameABC) == nullptr);
HYuana9b85752014-02-26 02:32:30 -0600377 BOOST_CHECK_EQUAL(eraseResult, true);
378
379 eraseResult = false;
380 temp = nt.findExactMatch(nameABCLPM);
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000381 if (temp != nullptr)
Junxiao Shi811c0102016-08-10 04:12:45 +0000382 eraseResult = nt.eraseIfEmpty(temp);
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000383 BOOST_CHECK(temp == nullptr);
HYuana9b85752014-02-26 02:32:30 -0600384 BOOST_CHECK_EQUAL(nt.size(), 6);
385 BOOST_CHECK_EQUAL(eraseResult, false);
386
HYuana9b85752014-02-26 02:32:30 -0600387 nt.lookup(nameABC);
388 BOOST_CHECK_EQUAL(nt.size(), 7);
389
390 eraseResult = false;
391 temp = nt.findExactMatch(nameABC);
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000392 if (temp != nullptr)
Junxiao Shi811c0102016-08-10 04:12:45 +0000393 eraseResult = nt.eraseIfEmpty(temp);
HYuana9b85752014-02-26 02:32:30 -0600394 BOOST_CHECK_EQUAL(nt.size(), 6);
395 BOOST_CHECK_EQUAL(eraseResult, true);
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000396 BOOST_CHECK(nt.findExactMatch(nameABC) == nullptr);
HYuana9b85752014-02-26 02:32:30 -0600397
HYuana9b85752014-02-26 02:32:30 -0600398 BOOST_CHECK_EQUAL(nt.getNBuckets(), 16);
399
Haowei Yuane1079fc2014-03-08 14:41:25 -0600400 // should resize now
HYuana9b85752014-02-26 02:32:30 -0600401 Name nameABCD("a/b/c/d");
402 nt.lookup(nameABCD);
403 Name nameABCDE("a/b/c/d/e");
404 nt.lookup(nameABCDE);
405 BOOST_CHECK_EQUAL(nt.size(), 9);
406 BOOST_CHECK_EQUAL(nt.getNBuckets(), 32);
407
Haowei Yuane1079fc2014-03-08 14:41:25 -0600408 // try to erase /a/b/c, should return false
HYuana9b85752014-02-26 02:32:30 -0600409 temp = nt.findExactMatch(nameABC);
Junxiao Shie3cf2852016-08-09 03:50:56 +0000410 BOOST_CHECK_EQUAL(temp->getName(), nameABC);
Junxiao Shi811c0102016-08-10 04:12:45 +0000411 eraseResult = nt.eraseIfEmpty(temp);
HYuana9b85752014-02-26 02:32:30 -0600412 BOOST_CHECK_EQUAL(eraseResult, false);
413 temp = nt.findExactMatch(nameABC);
Junxiao Shie3cf2852016-08-09 03:50:56 +0000414 BOOST_CHECK_EQUAL(temp->getName(), nameABC);
HYuana9b85752014-02-26 02:32:30 -0600415
416 temp = nt.findExactMatch(nameABD);
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000417 if (temp != nullptr)
Junxiao Shi811c0102016-08-10 04:12:45 +0000418 nt.eraseIfEmpty(temp);
HYuana9b85752014-02-26 02:32:30 -0600419 BOOST_CHECK_EQUAL(nt.size(), 8);
Haowei Yuane1079fc2014-03-08 14:41:25 -0600420}
HYuana9b85752014-02-26 02:32:30 -0600421
Junxiao Shi60607c72014-11-26 22:40:36 -0700422/** \brief verify a NameTree enumeration contains expected entries
423 *
424 * Example:
Junxiao Shie3cf2852016-08-09 03:50:56 +0000425 * \code
Junxiao Shi60607c72014-11-26 22:40:36 -0700426 * auto& enumerable = ...;
427 * EnumerationVerifier(enumerable)
428 * .expect("/A")
429 * .expect("/B")
430 * .end();
431 * // enumerable must have /A /B and nothing else to pass the test.
432 * \endcode
433 */
434class EnumerationVerifier : noncopyable
Haowei Yuane1079fc2014-03-08 14:41:25 -0600435{
Junxiao Shi60607c72014-11-26 22:40:36 -0700436public:
437 template<typename Enumerable>
438 EnumerationVerifier(Enumerable&& enumerable)
439 {
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000440 for (const Entry& entry : enumerable) {
Junxiao Shie3cf2852016-08-09 03:50:56 +0000441 const Name& name = entry.getName();
Junxiao Shi60607c72014-11-26 22:40:36 -0700442 BOOST_CHECK_MESSAGE(m_names.insert(name).second, "duplicate Name " << name);
443 }
444 }
HYuana9b85752014-02-26 02:32:30 -0600445
Junxiao Shi60607c72014-11-26 22:40:36 -0700446 EnumerationVerifier&
447 expect(const Name& name)
448 {
449 BOOST_CHECK_MESSAGE(m_names.erase(name) == 1, "missing Name " << name);
450 return *this;
451 }
Haowei Yuane1079fc2014-03-08 14:41:25 -0600452
Junxiao Shi60607c72014-11-26 22:40:36 -0700453 void
454 end()
455 {
Alexander Afanasyeve84044e2015-02-26 21:52:18 -0800456 BOOST_CHECK(m_names.empty());
Junxiao Shi60607c72014-11-26 22:40:36 -0700457 }
458
459private:
460 std::unordered_set<Name> m_names;
461};
462
Davide Pesaventocf7db2f2019-03-24 23:17:28 -0400463class EnumerationFixture : public GlobalIoFixture
Junxiao Shi60607c72014-11-26 22:40:36 -0700464{
465protected:
466 EnumerationFixture()
467 : nt(N_BUCKETS)
468 {
469 BOOST_CHECK_EQUAL(nt.size(), 0);
470 BOOST_CHECK_EQUAL(nt.getNBuckets(), N_BUCKETS);
471 }
472
473 void
474 insertAbAc()
475 {
476 nt.lookup("/a/b");
477 nt.lookup("/a/c");
478 BOOST_CHECK_EQUAL(nt.size(), 4);
479 // /, /a, /a/b, /a/c
480 }
481
482 void
483 insertAb1Ab2Ac1Ac2()
484 {
485 nt.lookup("/a/b/1");
486 nt.lookup("/a/b/2");
487 nt.lookup("/a/c/1");
488 nt.lookup("/a/c/2");
489 BOOST_CHECK_EQUAL(nt.size(), 8);
490 // /, /a, /a/b, /a/b/1, /a/b/2, /a/c, /a/c/1, /a/c/2
491 }
492
493protected:
494 static const size_t N_BUCKETS = 16;
495 NameTree nt;
496};
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000497
Junxiao Shi60607c72014-11-26 22:40:36 -0700498const size_t EnumerationFixture::N_BUCKETS;
499
500BOOST_FIXTURE_TEST_CASE(IteratorFullEnumerate, EnumerationFixture)
501{
502 nt.lookup("/a/b/c");
Haowei Yuane1079fc2014-03-08 14:41:25 -0600503 BOOST_CHECK_EQUAL(nt.size(), 4);
504
Junxiao Shi60607c72014-11-26 22:40:36 -0700505 nt.lookup("/a/b/d");
Haowei Yuane1079fc2014-03-08 14:41:25 -0600506 BOOST_CHECK_EQUAL(nt.size(), 5);
507
Junxiao Shi60607c72014-11-26 22:40:36 -0700508 nt.lookup("/a/e");
Haowei Yuane1079fc2014-03-08 14:41:25 -0600509 BOOST_CHECK_EQUAL(nt.size(), 6);
510
Junxiao Shi60607c72014-11-26 22:40:36 -0700511 nt.lookup("/f");
Haowei Yuane1079fc2014-03-08 14:41:25 -0600512 BOOST_CHECK_EQUAL(nt.size(), 7);
513
Junxiao Shi60607c72014-11-26 22:40:36 -0700514 nt.lookup("/");
Haowei Yuane1079fc2014-03-08 14:41:25 -0600515 BOOST_CHECK_EQUAL(nt.size(), 7);
516
Junxiao Shi60607c72014-11-26 22:40:36 -0700517 auto&& enumerable = nt.fullEnumerate();
518 EnumerationVerifier(enumerable)
519 .expect("/")
520 .expect("/a")
521 .expect("/a/b")
522 .expect("/a/b/c")
523 .expect("/a/b/d")
524 .expect("/a/e")
525 .expect("/f")
526 .end();
Haowei Yuane1079fc2014-03-08 14:41:25 -0600527}
528
Junxiao Shi60607c72014-11-26 22:40:36 -0700529BOOST_FIXTURE_TEST_SUITE(IteratorPartialEnumerate, EnumerationFixture)
Haowei Yuane1079fc2014-03-08 14:41:25 -0600530
Junxiao Shi60607c72014-11-26 22:40:36 -0700531BOOST_AUTO_TEST_CASE(Empty)
Haowei Yuane1079fc2014-03-08 14:41:25 -0600532{
Junxiao Shi60607c72014-11-26 22:40:36 -0700533 auto&& enumerable = nt.partialEnumerate("/a");
534
535 EnumerationVerifier(enumerable)
536 .end();
Haowei Yuane1079fc2014-03-08 14:41:25 -0600537}
538
Junxiao Shi60607c72014-11-26 22:40:36 -0700539BOOST_AUTO_TEST_CASE(NotIn)
Haowei Yuane1079fc2014-03-08 14:41:25 -0600540{
Junxiao Shi60607c72014-11-26 22:40:36 -0700541 this->insertAbAc();
Haowei Yuane1079fc2014-03-08 14:41:25 -0600542
543 // Enumerate on some name that is not in nameTree
Junxiao Shi60607c72014-11-26 22:40:36 -0700544 Name name0("/0");
545 auto&& enumerable = nt.partialEnumerate("/0");
546
547 EnumerationVerifier(enumerable)
548 .end();
549}
550
551BOOST_AUTO_TEST_CASE(OnlyA)
552{
553 this->insertAbAc();
Haowei Yuane1079fc2014-03-08 14:41:25 -0600554
555 // Accept "root" nameA only
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000556 auto&& enumerable = nt.partialEnumerate("/a", [] (const Entry& entry) {
Junxiao Shie3cf2852016-08-09 03:50:56 +0000557 return std::make_pair(entry.getName() == "/a", true);
Junxiao Shi60607c72014-11-26 22:40:36 -0700558 });
559
560 EnumerationVerifier(enumerable)
561 .expect("/a")
562 .end();
563}
564
565BOOST_AUTO_TEST_CASE(ExceptA)
566{
567 this->insertAbAc();
Haowei Yuane1079fc2014-03-08 14:41:25 -0600568
569 // Accept anything except "root" nameA
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000570 auto&& enumerable = nt.partialEnumerate("/a", [] (const Entry& entry) {
Junxiao Shie3cf2852016-08-09 03:50:56 +0000571 return std::make_pair(entry.getName() != "/a", true);
Junxiao Shi60607c72014-11-26 22:40:36 -0700572 });
Haowei Yuane1079fc2014-03-08 14:41:25 -0600573
Junxiao Shi60607c72014-11-26 22:40:36 -0700574 EnumerationVerifier(enumerable)
575 .expect("/a/b")
576 .expect("/a/c")
577 .end();
578}
Haowei Yuane1079fc2014-03-08 14:41:25 -0600579
Junxiao Shi60607c72014-11-26 22:40:36 -0700580BOOST_AUTO_TEST_CASE(NoNameANoSubTreeAB)
581{
582 this->insertAb1Ab2Ac1Ac2();
Haowei Yuane1079fc2014-03-08 14:41:25 -0600583
584 // No NameA
585 // No SubTree from NameAB
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000586 auto&& enumerable = nt.partialEnumerate("/a", [] (const Entry& entry) {
Junxiao Shie3cf2852016-08-09 03:50:56 +0000587 return std::make_pair(entry.getName() != "/a", entry.getName() != "/a/b");
Junxiao Shi60607c72014-11-26 22:40:36 -0700588 });
Haowei Yuane1079fc2014-03-08 14:41:25 -0600589
Junxiao Shi60607c72014-11-26 22:40:36 -0700590 EnumerationVerifier(enumerable)
591 .expect("/a/b")
592 .expect("/a/c")
593 .expect("/a/c/1")
594 .expect("/a/c/2")
595 .end();
596}
Haowei Yuane1079fc2014-03-08 14:41:25 -0600597
Junxiao Shi60607c72014-11-26 22:40:36 -0700598BOOST_AUTO_TEST_CASE(NoNameANoSubTreeAC)
599{
600 this->insertAb1Ab2Ac1Ac2();
Haowei Yuane1079fc2014-03-08 14:41:25 -0600601
602 // No NameA
603 // No SubTree from NameAC
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000604 auto&& enumerable = nt.partialEnumerate("/a", [] (const Entry& entry) {
Junxiao Shie3cf2852016-08-09 03:50:56 +0000605 return std::make_pair(entry.getName() != "/a", entry.getName() != "/a/c");
Junxiao Shi60607c72014-11-26 22:40:36 -0700606 });
Haowei Yuane1079fc2014-03-08 14:41:25 -0600607
Junxiao Shi60607c72014-11-26 22:40:36 -0700608 EnumerationVerifier(enumerable)
609 .expect("/a/b")
610 .expect("/a/b/1")
611 .expect("/a/b/2")
612 .expect("/a/c")
613 .end();
614}
Haowei Yuane1079fc2014-03-08 14:41:25 -0600615
Junxiao Shi60607c72014-11-26 22:40:36 -0700616BOOST_AUTO_TEST_CASE(NoSubTreeA)
617{
618 this->insertAb1Ab2Ac1Ac2();
Haowei Yuane1079fc2014-03-08 14:41:25 -0600619
620 // No Subtree from NameA
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000621 auto&& enumerable = nt.partialEnumerate("/a", [] (const Entry& entry) {
Junxiao Shie3cf2852016-08-09 03:50:56 +0000622 return std::make_pair(true, entry.getName() != "/a");
Junxiao Shi60607c72014-11-26 22:40:36 -0700623 });
Haowei Yuane1079fc2014-03-08 14:41:25 -0600624
Junxiao Shi60607c72014-11-26 22:40:36 -0700625 EnumerationVerifier(enumerable)
626 .expect("/a")
627 .end();
628}
Haowei Yuane1079fc2014-03-08 14:41:25 -0600629
Junxiao Shi60607c72014-11-26 22:40:36 -0700630BOOST_AUTO_TEST_CASE(Example)
631{
Haowei Yuane1079fc2014-03-08 14:41:25 -0600632 // Example
633 // /
634 // /A
635 // /A/B x
636 // /A/B/C
637 // /A/D x
638 // /E
639 // /F
640
Junxiao Shi60607c72014-11-26 22:40:36 -0700641 nt.lookup("/A");
642 nt.lookup("/A/B");
643 nt.lookup("/A/B/C");
644 nt.lookup("/A/D");
645 nt.lookup("/E");
646 nt.lookup("/F");
Haowei Yuane1079fc2014-03-08 14:41:25 -0600647
Junxiao Shi60607c72014-11-26 22:40:36 -0700648 auto&& enumerable = nt.partialEnumerate("/A",
Junxiao Shi811c0102016-08-10 04:12:45 +0000649 [] (const Entry& entry) {
Junxiao Shi60607c72014-11-26 22:40:36 -0700650 bool visitEntry = false;
651 bool visitChildren = false;
Haowei Yuane1079fc2014-03-08 14:41:25 -0600652
Junxiao Shie3cf2852016-08-09 03:50:56 +0000653 Name name = entry.getName();
Haowei Yuane1079fc2014-03-08 14:41:25 -0600654
Junxiao Shi60607c72014-11-26 22:40:36 -0700655 if (name == "/" || name == "/A/B" || name == "/A/B/C" || name == "/A/D") {
656 visitEntry = true;
657 }
Haowei Yuane1079fc2014-03-08 14:41:25 -0600658
Junxiao Shi60607c72014-11-26 22:40:36 -0700659 if (name == "/" || name == "/A" || name == "/F") {
660 visitChildren = true;
661 }
Haowei Yuane1079fc2014-03-08 14:41:25 -0600662
Junxiao Shi811c0102016-08-10 04:12:45 +0000663 return std::make_pair(visitEntry, visitChildren);
Junxiao Shi60607c72014-11-26 22:40:36 -0700664 });
Haowei Yuane1079fc2014-03-08 14:41:25 -0600665
Junxiao Shi60607c72014-11-26 22:40:36 -0700666 EnumerationVerifier(enumerable)
667 .expect("/A/B")
668 .expect("/A/D")
669 .end();
Haowei Yuane1079fc2014-03-08 14:41:25 -0600670}
671
Davide Pesavento14e71f02019-03-28 17:35:25 -0400672BOOST_AUTO_TEST_SUITE_END() // IteratorPartialEnumerate
Haowei Yuane1079fc2014-03-08 14:41:25 -0600673
Junxiao Shi60607c72014-11-26 22:40:36 -0700674BOOST_FIXTURE_TEST_CASE(IteratorFindAllMatches, EnumerationFixture)
Haowei Yuane1079fc2014-03-08 14:41:25 -0600675{
Junxiao Shi60607c72014-11-26 22:40:36 -0700676 nt.lookup("/a/b/c/d/e/f");
677 nt.lookup("/a/a/c");
678 nt.lookup("/a/a/d/1");
679 nt.lookup("/a/a/d/2");
Haowei Yuane1079fc2014-03-08 14:41:25 -0600680 BOOST_CHECK_EQUAL(nt.size(), 12);
681
Junxiao Shi60607c72014-11-26 22:40:36 -0700682 auto&& allMatches = nt.findAllMatches("/a/b/c/d/e");
Haowei Yuane1079fc2014-03-08 14:41:25 -0600683
Junxiao Shi60607c72014-11-26 22:40:36 -0700684 EnumerationVerifier(allMatches)
685 .expect("/")
686 .expect("/a")
687 .expect("/a/b")
688 .expect("/a/b/c")
689 .expect("/a/b/c/d")
690 .expect("/a/b/c/d/e")
691 .end();
HYuana9b85752014-02-26 02:32:30 -0600692}
693
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700694BOOST_AUTO_TEST_CASE(HashTableResizeShrink)
Haowei Yuanf52dac72014-03-24 23:35:03 -0500695{
696 size_t nBuckets = 16;
697 NameTree nameTree(nBuckets);
698
699 Name prefix("/a/b/c/d/e/f/g/h"); // requires 9 buckets
700
Junxiao Shi7f358432016-08-11 17:06:33 +0000701 Entry& entry = nameTree.lookup(prefix);
Haowei Yuanf52dac72014-03-24 23:35:03 -0500702 BOOST_CHECK_EQUAL(nameTree.size(), 9);
703 BOOST_CHECK_EQUAL(nameTree.getNBuckets(), 32);
704
Junxiao Shi7f358432016-08-11 17:06:33 +0000705 nameTree.eraseIfEmpty(&entry);
Haowei Yuanf52dac72014-03-24 23:35:03 -0500706 BOOST_CHECK_EQUAL(nameTree.size(), 0);
707 BOOST_CHECK_EQUAL(nameTree.getNBuckets(), 16);
708}
709
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700710// .lookup should not invalidate iterator
711BOOST_AUTO_TEST_CASE(SurvivedIteratorAfterLookup)
712{
713 NameTree nt;
714 nt.lookup("/A/B/C");
715 nt.lookup("/E");
716
717 Name nameB("/A/B");
718 std::set<Name> seenNames;
719 for (NameTree::const_iterator it = nt.begin(); it != nt.end(); ++it) {
Junxiao Shie3cf2852016-08-09 03:50:56 +0000720 BOOST_CHECK(seenNames.insert(it->getName()).second);
721 if (it->getName() == nameB) {
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700722 nt.lookup("/D");
723 }
724 }
725
726 BOOST_CHECK_EQUAL(seenNames.count("/"), 1);
727 BOOST_CHECK_EQUAL(seenNames.count("/A"), 1);
728 BOOST_CHECK_EQUAL(seenNames.count("/A/B"), 1);
729 BOOST_CHECK_EQUAL(seenNames.count("/A/B/C"), 1);
730 BOOST_CHECK_EQUAL(seenNames.count("/E"), 1);
731
732 seenNames.erase("/D"); // /D may or may not appear
733 BOOST_CHECK(seenNames.size() == 5);
734}
735
Junxiao Shie3cf2852016-08-09 03:50:56 +0000736// .eraseIfEmpty should not invalidate iterator
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700737BOOST_AUTO_TEST_CASE(SurvivedIteratorAfterErase)
738{
739 NameTree nt;
740 nt.lookup("/A/B/C");
741 nt.lookup("/A/D/E");
742 nt.lookup("/A/F/G");
743 nt.lookup("/H");
744
745 Name nameD("/A/D");
746 std::set<Name> seenNames;
747 for (NameTree::const_iterator it = nt.begin(); it != nt.end(); ++it) {
Junxiao Shie3cf2852016-08-09 03:50:56 +0000748 BOOST_CHECK(seenNames.insert(it->getName()).second);
749 if (it->getName() == nameD) {
Junxiao Shi811c0102016-08-10 04:12:45 +0000750 nt.eraseIfEmpty(nt.findExactMatch("/A/F/G")); // /A/F/G and /A/F are erased
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700751 }
752 }
753
754 BOOST_CHECK_EQUAL(seenNames.count("/"), 1);
755 BOOST_CHECK_EQUAL(seenNames.count("/A"), 1);
756 BOOST_CHECK_EQUAL(seenNames.count("/A/B"), 1);
757 BOOST_CHECK_EQUAL(seenNames.count("/A/B/C"), 1);
758 BOOST_CHECK_EQUAL(seenNames.count("/A/D"), 1);
759 BOOST_CHECK_EQUAL(seenNames.count("/A/D/E"), 1);
760 BOOST_CHECK_EQUAL(seenNames.count("/H"), 1);
761
762 seenNames.erase("/A/F"); // /A/F may or may not appear
763 seenNames.erase("/A/F/G"); // /A/F/G may or may not appear
764 BOOST_CHECK(seenNames.size() == 7);
765}
766
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000767BOOST_AUTO_TEST_SUITE_END() // TestNameTree
768BOOST_AUTO_TEST_SUITE_END() // Table
HYuana9b85752014-02-26 02:32:30 -0600769
Junxiao Shid9ee45c2014-02-27 15:38:11 -0700770} // namespace tests
Junxiao Shi2570f3e2016-07-27 02:48:29 +0000771} // namespace name_tree
HYuana9b85752014-02-26 02:32:30 -0600772} // namespace nfd