blob: cd1d89473595912566f6cd558dd8493f1b6f3c7e [file] [log] [blame]
HYuana9b85752014-02-26 02:32:30 -06001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
Alexander Afanasyev28d586a2014-07-10 20:10:54 -07003 * Copyright (c) 2014, Regents of the University of California,
4 * 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 Shid9ee45c2014-02-27 15:38:11 -070027#include "tests/test-common.hpp"
HYuana9b85752014-02-26 02:32:30 -060028
29namespace nfd {
Junxiao Shid9ee45c2014-02-27 15:38:11 -070030namespace tests {
HYuana9b85752014-02-26 02:32:30 -060031
32using name_tree::Entry;
33
Junxiao Shid9ee45c2014-02-27 15:38:11 -070034BOOST_FIXTURE_TEST_SUITE(TableNameTree, BaseFixture)
HYuana9b85752014-02-26 02:32:30 -060035
Haowei Yuanf52dac72014-03-24 23:35:03 -050036BOOST_AUTO_TEST_CASE(Hash)
37{
38 Name root("/");
39 root.wireEncode();
40 size_t hashValue = name_tree::computeHash(root);
41 BOOST_CHECK_EQUAL(hashValue, static_cast<size_t>(0));
42
43 Name prefix("/nohello/world/ndn/research");
44 prefix.wireEncode();
45 std::vector<size_t> hashSet = name_tree::computeHashSet(prefix);
46 BOOST_CHECK_EQUAL(hashSet.size(), prefix.size() + 1);
47}
48
Junxiao Shid9ee45c2014-02-27 15:38:11 -070049BOOST_AUTO_TEST_CASE(Entry)
HYuana9b85752014-02-26 02:32:30 -060050{
51 Name prefix("ndn:/named-data/research/abc/def/ghi");
52
Junxiao Shiefceadc2014-03-09 18:52:57 -070053 shared_ptr<name_tree::Entry> npe = make_shared<name_tree::Entry>(prefix);
54 BOOST_CHECK_EQUAL(npe->getPrefix(), prefix);
HYuana9b85752014-02-26 02:32:30 -060055
56 // examine all the get methods
57
Haowei Yuanf52dac72014-03-24 23:35:03 -050058 size_t hash = npe->getHash();
59 BOOST_CHECK_EQUAL(hash, static_cast<size_t>(0));
HYuana9b85752014-02-26 02:32:30 -060060
Junxiao Shiefceadc2014-03-09 18:52:57 -070061 shared_ptr<name_tree::Entry> parent = npe->getParent();
HYuana9b85752014-02-26 02:32:30 -060062 BOOST_CHECK(!static_cast<bool>(parent));
63
Junxiao Shiefceadc2014-03-09 18:52:57 -070064 std::vector<shared_ptr<name_tree::Entry> >& childList = npe->getChildren();
Haowei Yuanf52dac72014-03-24 23:35:03 -050065 BOOST_CHECK_EQUAL(childList.size(), static_cast<size_t>(0));
HYuana9b85752014-02-26 02:32:30 -060066
Junxiao Shiefceadc2014-03-09 18:52:57 -070067 shared_ptr<fib::Entry> fib = npe->getFibEntry();
HYuana9b85752014-02-26 02:32:30 -060068 BOOST_CHECK(!static_cast<bool>(fib));
69
Junxiao Shi9f7455b2014-04-07 21:02:16 -070070 const std::vector< shared_ptr<pit::Entry> >& pitList = npe->getPitEntries();
Haowei Yuanf52dac72014-03-24 23:35:03 -050071 BOOST_CHECK_EQUAL(pitList.size(), static_cast<size_t>(0));
HYuana9b85752014-02-26 02:32:30 -060072
Haowei Yuane1079fc2014-03-08 14:41:25 -060073 // examine all the set method
HYuana9b85752014-02-26 02:32:30 -060074
Haowei Yuanf52dac72014-03-24 23:35:03 -050075 npe->setHash(static_cast<size_t>(12345));
76 BOOST_CHECK_EQUAL(npe->getHash(), static_cast<size_t>(12345));
HYuana9b85752014-02-26 02:32:30 -060077
78 Name parentName("ndn:/named-data/research/abc/def");
79 parent = make_shared<name_tree::Entry>(parentName);
Junxiao Shiefceadc2014-03-09 18:52:57 -070080 npe->setParent(parent);
81 BOOST_CHECK_EQUAL(npe->getParent(), parent);
HYuana9b85752014-02-26 02:32:30 -060082
Haowei Yuane1079fc2014-03-08 14:41:25 -060083 // Insert FIB
HYuana9b85752014-02-26 02:32:30 -060084
85 shared_ptr<fib::Entry> fibEntry(new fib::Entry(prefix));
86 shared_ptr<fib::Entry> fibEntryParent(new fib::Entry(parentName));
Haowei Yuane1079fc2014-03-08 14:41:25 -060087
Junxiao Shiefceadc2014-03-09 18:52:57 -070088 npe->setFibEntry(fibEntry);
89 BOOST_CHECK_EQUAL(npe->getFibEntry(), fibEntry);
HYuana9b85752014-02-26 02:32:30 -060090
Junxiao Shiefceadc2014-03-09 18:52:57 -070091 npe->setFibEntry(shared_ptr<fib::Entry>());
92 BOOST_CHECK(!static_cast<bool>(npe->getFibEntry()));
HYuana9b85752014-02-26 02:32:30 -060093
94 // Insert a PIT
95
Alexander Afanasyev28d586a2014-07-10 20:10:54 -070096 shared_ptr<pit::Entry> pitEntry(make_shared<pit::Entry>(*makeInterest(prefix)));
97 shared_ptr<pit::Entry> pitEntry2(make_shared<pit::Entry>(*makeInterest(parentName)));
HYuana9b85752014-02-26 02:32:30 -060098
Alexander Afanasyev28d586a2014-07-10 20:10:54 -070099 npe->insertPitEntry(pitEntry);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700100 BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 1);
HYuana9b85752014-02-26 02:32:30 -0600101
Alexander Afanasyev28d586a2014-07-10 20:10:54 -0700102 npe->insertPitEntry(pitEntry2);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700103 BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 2);
HYuana9b85752014-02-26 02:32:30 -0600104
Alexander Afanasyev28d586a2014-07-10 20:10:54 -0700105 npe->erasePitEntry(pitEntry);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700106 BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 1);
HYuana9b85752014-02-26 02:32:30 -0600107
Alexander Afanasyev28d586a2014-07-10 20:10:54 -0700108 npe->erasePitEntry(pitEntry2);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700109 BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 0);
HYuana9b85752014-02-26 02:32:30 -0600110}
111
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700112BOOST_AUTO_TEST_CASE(Basic)
HYuana9b85752014-02-26 02:32:30 -0600113{
114 size_t nBuckets = 16;
115 NameTree nt(nBuckets);
116
117 BOOST_CHECK_EQUAL(nt.size(), 0);
Haowei Yuane1079fc2014-03-08 14:41:25 -0600118 BOOST_CHECK_EQUAL(nt.getNBuckets(), nBuckets);
HYuana9b85752014-02-26 02:32:30 -0600119
Haowei Yuane1079fc2014-03-08 14:41:25 -0600120 Name nameABC("ndn:/a/b/c");
HYuana9b85752014-02-26 02:32:30 -0600121 shared_ptr<name_tree::Entry> npeABC = nt.lookup(nameABC);
122 BOOST_CHECK_EQUAL(nt.size(), 4);
Haowei Yuane1079fc2014-03-08 14:41:25 -0600123
124 Name nameABD("/a/b/d");
HYuana9b85752014-02-26 02:32:30 -0600125 shared_ptr<name_tree::Entry> npeABD = nt.lookup(nameABD);
126 BOOST_CHECK_EQUAL(nt.size(), 5);
127
Haowei Yuane1079fc2014-03-08 14:41:25 -0600128 Name nameAE("/a/e/");
HYuana9b85752014-02-26 02:32:30 -0600129 shared_ptr<name_tree::Entry> npeAE = nt.lookup(nameAE);
130 BOOST_CHECK_EQUAL(nt.size(), 6);
131
Haowei Yuane1079fc2014-03-08 14:41:25 -0600132 Name nameF("/f");
HYuana9b85752014-02-26 02:32:30 -0600133 shared_ptr<name_tree::Entry> npeF = nt.lookup(nameF);
134 BOOST_CHECK_EQUAL(nt.size(), 7);
135
Haowei Yuane1079fc2014-03-08 14:41:25 -0600136 // validate lookup() and findExactMatch()
HYuana9b85752014-02-26 02:32:30 -0600137
138 Name nameAB ("/a/b");
139 BOOST_CHECK_EQUAL(npeABC->getParent(), nt.findExactMatch(nameAB));
140 BOOST_CHECK_EQUAL(npeABD->getParent(), nt.findExactMatch(nameAB));
141
142 Name nameA ("/a");
143 BOOST_CHECK_EQUAL(npeAE->getParent(), nt.findExactMatch(nameA));
144
145 Name nameRoot ("/");
146 BOOST_CHECK_EQUAL(npeF->getParent(), nt.findExactMatch(nameRoot));
147 BOOST_CHECK_EQUAL(nt.size(), 7);
148
Haowei Yuane1079fc2014-03-08 14:41:25 -0600149 Name name0("/does/not/exist");
HYuana9b85752014-02-26 02:32:30 -0600150 shared_ptr<name_tree::Entry> npe0 = nt.findExactMatch(name0);
151 BOOST_CHECK(!static_cast<bool>(npe0));
152
153
154 // Longest Prefix Matching
HYuana9b85752014-02-26 02:32:30 -0600155 shared_ptr<name_tree::Entry> temp;
156 Name nameABCLPM("/a/b/c/def/asdf/nlf");
157 temp = nt.findLongestPrefixMatch(nameABCLPM);
158 BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameABC));
159
160 Name nameABDLPM("/a/b/d/def/asdf/nlf");
161 temp = nt.findLongestPrefixMatch(nameABDLPM);
162 BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameABD));
163
164 Name nameABLPM("/a/b/hello/world");
165 temp = nt.findLongestPrefixMatch(nameABLPM);
166 BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameAB));
167
168 Name nameAELPM("/a/e/hello/world");
169 temp = nt.findLongestPrefixMatch(nameAELPM);
170 BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameAE));
171
172 Name nameALPM("/a/hello/world");
173 temp = nt.findLongestPrefixMatch(nameALPM);
174 BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameA));
175
176 Name nameFLPM("/f/hello/world");
177 temp = nt.findLongestPrefixMatch(nameFLPM);
178 BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameF));
179
180 Name nameRootLPM("/does_not_exist");
181 temp = nt.findLongestPrefixMatch(nameRootLPM);
182 BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameRoot));
183
HYuana9b85752014-02-26 02:32:30 -0600184 bool eraseResult = false;
185 temp = nt.findExactMatch(nameABC);
186 if (static_cast<bool>(temp))
187 eraseResult = nt.
188 eraseEntryIfEmpty(temp);
189 BOOST_CHECK_EQUAL(nt.size(), 6);
190 BOOST_CHECK(!static_cast<bool>(nt.findExactMatch(nameABC)));
191 BOOST_CHECK_EQUAL(eraseResult, true);
192
193 eraseResult = false;
194 temp = nt.findExactMatch(nameABCLPM);
Haowei Yuane1079fc2014-03-08 14:41:25 -0600195 if (static_cast<bool>(temp))
HYuana9b85752014-02-26 02:32:30 -0600196 eraseResult = nt.
197 eraseEntryIfEmpty(temp);
198 BOOST_CHECK(!static_cast<bool>(temp));
199 BOOST_CHECK_EQUAL(nt.size(), 6);
200 BOOST_CHECK_EQUAL(eraseResult, false);
201
202 // nt.dump(std::cout);
203
204 nt.lookup(nameABC);
205 BOOST_CHECK_EQUAL(nt.size(), 7);
206
207 eraseResult = false;
208 temp = nt.findExactMatch(nameABC);
Haowei Yuane1079fc2014-03-08 14:41:25 -0600209 if (static_cast<bool>(temp))
HYuana9b85752014-02-26 02:32:30 -0600210 eraseResult = nt.
211 eraseEntryIfEmpty(temp);
212 BOOST_CHECK_EQUAL(nt.size(), 6);
213 BOOST_CHECK_EQUAL(eraseResult, true);
214 BOOST_CHECK(!static_cast<bool>(nt.findExactMatch(nameABC)));
215
HYuana9b85752014-02-26 02:32:30 -0600216 BOOST_CHECK_EQUAL(nt.getNBuckets(), 16);
217
Haowei Yuane1079fc2014-03-08 14:41:25 -0600218 // should resize now
HYuana9b85752014-02-26 02:32:30 -0600219 Name nameABCD("a/b/c/d");
220 nt.lookup(nameABCD);
221 Name nameABCDE("a/b/c/d/e");
222 nt.lookup(nameABCDE);
223 BOOST_CHECK_EQUAL(nt.size(), 9);
224 BOOST_CHECK_EQUAL(nt.getNBuckets(), 32);
225
Haowei Yuane1079fc2014-03-08 14:41:25 -0600226 // try to erase /a/b/c, should return false
HYuana9b85752014-02-26 02:32:30 -0600227 temp = nt.findExactMatch(nameABC);
228 BOOST_CHECK_EQUAL(temp->getPrefix(), nameABC);
229 eraseResult = nt.
230 eraseEntryIfEmpty(temp);
231 BOOST_CHECK_EQUAL(eraseResult, false);
232 temp = nt.findExactMatch(nameABC);
233 BOOST_CHECK_EQUAL(temp->getPrefix(), nameABC);
234
235 temp = nt.findExactMatch(nameABD);
Haowei Yuane1079fc2014-03-08 14:41:25 -0600236 if (static_cast<bool>(temp))
HYuana9b85752014-02-26 02:32:30 -0600237 nt.
238 eraseEntryIfEmpty(temp);
239 BOOST_CHECK_EQUAL(nt.size(), 8);
Haowei Yuane1079fc2014-03-08 14:41:25 -0600240}
HYuana9b85752014-02-26 02:32:30 -0600241
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700242BOOST_AUTO_TEST_CASE(IteratorFullEnumerate)
Haowei Yuane1079fc2014-03-08 14:41:25 -0600243{
Haowei Yuane1079fc2014-03-08 14:41:25 -0600244 size_t nBuckets = 1024;
245 NameTree nt(nBuckets);
HYuana9b85752014-02-26 02:32:30 -0600246
Haowei Yuane1079fc2014-03-08 14:41:25 -0600247 BOOST_CHECK_EQUAL(nt.size(), 0);
248 BOOST_CHECK_EQUAL(nt.getNBuckets(), nBuckets);
249
250 Name nameABC("ndn:/a/b/c");
251 shared_ptr<name_tree::Entry> npeABC = nt.lookup(nameABC);
252 BOOST_CHECK_EQUAL(nt.size(), 4);
253
254 Name nameABD("/a/b/d");
255 shared_ptr<name_tree::Entry> npeABD = nt.lookup(nameABD);
256 BOOST_CHECK_EQUAL(nt.size(), 5);
257
258 Name nameAE("/a/e/");
259 shared_ptr<name_tree::Entry> npeAE = nt.lookup(nameAE);
260 BOOST_CHECK_EQUAL(nt.size(), 6);
261
262 Name nameF("/f");
263 shared_ptr<name_tree::Entry> npeF = nt.lookup(nameF);
264 BOOST_CHECK_EQUAL(nt.size(), 7);
265
266 Name nameRoot("/");
267 shared_ptr<name_tree::Entry> npeRoot = nt.lookup(nameRoot);
268 BOOST_CHECK_EQUAL(nt.size(), 7);
269
270 Name nameA("/a");
271 Name nameAB("/a/b");
272
273 bool hasRoot = false;
274 bool hasA = false;
275 bool hasAB = false;
276 bool hasABC = false;
277 bool hasABD = false;
278 bool hasAE = false;
279 bool hasF = false;
280
281 int counter = 0;
282 NameTree::const_iterator it = nt.fullEnumerate();
283
284 for(; it != nt.end(); it++)
285 {
286 counter++;
287
288 if (it->getPrefix() == nameRoot)
289 hasRoot = true;
290 if (it->getPrefix() == nameA)
291 hasA = true;
292 if (it->getPrefix() == nameAB)
293 hasAB = true;
294 if (it->getPrefix() == nameABC)
295 hasABC = true;
296 if (it->getPrefix() == nameABD)
297 hasABD = true;
298 if (it->getPrefix() == nameAE)
299 hasAE = true;
300 if (it->getPrefix() == nameF)
301 hasF = true;
302 }
303
304 BOOST_CHECK_EQUAL(hasRoot , true);
305 BOOST_CHECK_EQUAL(hasA , true);
306 BOOST_CHECK_EQUAL(hasAB , true);
307 BOOST_CHECK_EQUAL(hasABC , true);
308 BOOST_CHECK_EQUAL(hasABD , true);
309 BOOST_CHECK_EQUAL(hasAE , true);
310 BOOST_CHECK_EQUAL(hasF , true);
311
312 BOOST_CHECK_EQUAL(counter , 7);
313}
314
315// Predicates for testing the partial enumerate function
316
317static inline std::pair<bool, bool>
318predicate_NameTreeEntry_NameA_Only(const name_tree::Entry& entry)
319{
320 Name nameA("/a");
321 bool first = nameA.equals(entry.getPrefix());
322 return std::make_pair(first, true);
323}
324
325static inline std::pair<bool, bool>
326predicate_NameTreeEntry_Except_NameA(const name_tree::Entry& entry)
327{
328 Name nameA("/a");
329 bool first = !(nameA.equals(entry.getPrefix()));
330 return std::make_pair(first, true);
331}
332
333static inline std::pair<bool, bool>
334predicate_NameTreeEntry_NoSubNameA(const name_tree::Entry& entry)
335{
336 Name nameA("/a");
337 bool second = !(nameA.equals(entry.getPrefix()));
338 return std::make_pair(true, second);
339}
340
341static inline std::pair<bool, bool>
342predicate_NameTreeEntry_NoNameA_NoSubNameAB(const name_tree::Entry& entry)
343{
344 Name nameA("/a");
345 Name nameAB("/a/b");
346 bool first = !(nameA.equals(entry.getPrefix()));
347 bool second = !(nameAB.equals(entry.getPrefix()));
348 return std::make_pair(first, second);
349}
350
351static inline std::pair<bool, bool>
352predicate_NameTreeEntry_NoNameA_NoSubNameAC(const name_tree::Entry& entry)
353{
354 Name nameA("/a");
355 Name nameAC("/a/c");
356 bool first = !(nameA.equals(entry.getPrefix()));
357 bool second = !(nameAC.equals(entry.getPrefix()));
358 return std::make_pair(first, second);
359}
360
361static inline std::pair<bool, bool>
362predicate_NameTreeEntry_Example(const name_tree::Entry& entry)
363{
364 Name nameRoot("/");
365 Name nameA("/a");
366 Name nameAB("/a/b");
367 Name nameABC("/a/b/c");
368 Name nameAD("/a/d");
369 Name nameE("/e");
370 Name nameF("/f");
371
372 bool first = false;
373 bool second = false;
374
375 Name name = entry.getPrefix();
376
377 if (name == nameRoot || name == nameAB || name == nameABC || name == nameAD)
378 {
379 first = true;
380 }
381
382 if(name == nameRoot || name == nameA || name == nameF)
383 {
384 second = true;
385 }
386
387 return std::make_pair(first, second);
388}
389
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700390BOOST_AUTO_TEST_CASE(IteratorPartialEnumerate)
Haowei Yuane1079fc2014-03-08 14:41:25 -0600391{
Haowei Yuane1079fc2014-03-08 14:41:25 -0600392 typedef NameTree::const_iterator const_iterator;
393
394 size_t nBuckets = 16;
395 NameTree nameTree(nBuckets);
396 int counter = 0;
397
398 // empty nameTree, should return end();
399 Name nameA("/a");
400 bool hasA = false;
401 const_iterator itA = nameTree.partialEnumerate(nameA);
402 BOOST_CHECK(itA == nameTree.end());
403
404 // We have "/", "/a", "/a/b", "a/c" now.
405 Name nameAB("/a/b");
406 bool hasAB = false;
407 nameTree.lookup(nameAB);
408
409 Name nameAC("/a/c");
410 bool hasAC = false;
411 nameTree.lookup(nameAC);
412 BOOST_CHECK_EQUAL(nameTree.size(), 4);
413
414 // Enumerate on some name that is not in nameTree
415 Name name0="/0";
416 const_iterator it0 = nameTree.partialEnumerate(name0);
417 BOOST_CHECK(it0 == nameTree.end());
418
419 // Accept "root" nameA only
420 const_iterator itAOnly = nameTree.partialEnumerate(nameA, &predicate_NameTreeEntry_NameA_Only);
421 BOOST_CHECK_EQUAL(itAOnly->getPrefix(), nameA);
422 BOOST_CHECK(++itAOnly == nameTree.end());
423
424 // Accept anything except "root" nameA
425 const_iterator itExceptA = nameTree.partialEnumerate(nameA, &predicate_NameTreeEntry_Except_NameA);
426 hasA = false;
427 hasAB = false;
428 hasAC = false;
429
430 counter = 0;
431 for (; itExceptA != nameTree.end(); itExceptA++)
432 {
433 counter++;
434
435 if (itExceptA->getPrefix() == nameA)
436 hasA = true;
437
438 if (itExceptA->getPrefix() == nameAB)
439 hasAB = true;
440
441 if (itExceptA->getPrefix() == nameAC)
442 hasAC = true;
443 }
444 BOOST_CHECK_EQUAL(hasA, false);
445 BOOST_CHECK_EQUAL(hasAB, true);
446 BOOST_CHECK_EQUAL(hasAC, true);
447
448 BOOST_CHECK_EQUAL(counter, 2);
449
450 Name nameAB1("a/b/1");
451 bool hasAB1 = false;
452 nameTree.lookup(nameAB1);
453
454 Name nameAB2("a/b/2");
455 bool hasAB2 = false;
456 nameTree.lookup(nameAB2);
457
458 Name nameAC1("a/c/1");
459 bool hasAC1 = false;
460 nameTree.lookup(nameAC1);
461
462 Name nameAC2("a/c/2");
463 bool hasAC2 = false;
464 nameTree.lookup(nameAC2);
465
466 BOOST_CHECK_EQUAL(nameTree.size(), 8);
467
468 // No NameA
469 // No SubTree from NameAB
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700470 const_iterator itNoNameANoSubNameAB = nameTree.partialEnumerate(nameA,
471 &predicate_NameTreeEntry_NoNameA_NoSubNameAB);
Haowei Yuane1079fc2014-03-08 14:41:25 -0600472 hasA = false;
473 hasAB = false;
474 hasAB1 = false;
475 hasAB2 = false;
476 hasAC = false;
477 hasAC1 = false;
478 hasAC2 = false;
479
480 counter = 0;
481
482 for (; itNoNameANoSubNameAB != nameTree.end(); itNoNameANoSubNameAB++)
483 {
484 counter++;
485
486 if (itNoNameANoSubNameAB->getPrefix() == nameA)
487 hasA = true;
488
489 if (itNoNameANoSubNameAB->getPrefix() == nameAB)
490 hasAB = true;
491
492 if (itNoNameANoSubNameAB->getPrefix() == nameAB1)
493 hasAB1 = true;
494
495 if (itNoNameANoSubNameAB->getPrefix() == nameAB2)
496 hasAB2 = true;
497
498 if (itNoNameANoSubNameAB->getPrefix() == nameAC)
499 hasAC = true;
500
501 if (itNoNameANoSubNameAB->getPrefix() == nameAC1)
502 hasAC1 = true;
503
504 if (itNoNameANoSubNameAB->getPrefix() == nameAC2)
505 hasAC2 = true;
506 }
507
508 BOOST_CHECK_EQUAL(hasA, false);
509 BOOST_CHECK_EQUAL(hasAB, true);
510 BOOST_CHECK_EQUAL(hasAB1, false);
511 BOOST_CHECK_EQUAL(hasAB2, false);
512 BOOST_CHECK_EQUAL(hasAC, true);
513 BOOST_CHECK_EQUAL(hasAC1, true);
514 BOOST_CHECK_EQUAL(hasAC2, true);
515
516 BOOST_CHECK_EQUAL(counter, 4);
517
518 // No NameA
519 // No SubTree from NameAC
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700520 const_iterator itNoNameANoSubNameAC = nameTree.partialEnumerate(nameA,
521 &predicate_NameTreeEntry_NoNameA_NoSubNameAC);
Haowei Yuane1079fc2014-03-08 14:41:25 -0600522 hasA = false;
523 hasAB = false;
524 hasAB1 = false;
525 hasAB2 = false;
526 hasAC = false;
527 hasAC1 = false;
528 hasAC2 = false;
529
530 counter = 0;
531
532 for (; itNoNameANoSubNameAC != nameTree.end(); itNoNameANoSubNameAC++)
533 {
534 counter++;
535
536 if (itNoNameANoSubNameAC->getPrefix() == nameA)
537 hasA = true;
538
539 if (itNoNameANoSubNameAC->getPrefix() == nameAB)
540 hasAB = true;
541
542 if (itNoNameANoSubNameAC->getPrefix() == nameAB1)
543 hasAB1 = true;
544
545 if (itNoNameANoSubNameAC->getPrefix() == nameAB2)
546 hasAB2 = true;
547
548 if (itNoNameANoSubNameAC->getPrefix() == nameAC)
549 hasAC = true;
550
551 if (itNoNameANoSubNameAC->getPrefix() == nameAC1)
552 hasAC1 = true;
553
554 if (itNoNameANoSubNameAC->getPrefix() == nameAC2)
555 hasAC2 = true;
556 }
557
558 BOOST_CHECK_EQUAL(hasA, false);
559 BOOST_CHECK_EQUAL(hasAB, true);
560 BOOST_CHECK_EQUAL(hasAB1, true);
561 BOOST_CHECK_EQUAL(hasAB2, true);
562 BOOST_CHECK_EQUAL(hasAC, true);
563 BOOST_CHECK_EQUAL(hasAC1, false);
564 BOOST_CHECK_EQUAL(hasAC2, false);
565
566 BOOST_CHECK_EQUAL(counter, 4);
567
568 // No Subtree from NameA
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700569 const_iterator itNoANoSubNameA = nameTree.partialEnumerate(nameA,
570 &predicate_NameTreeEntry_NoSubNameA);
Haowei Yuane1079fc2014-03-08 14:41:25 -0600571
572 hasA = false;
573 hasAB = false;
574 hasAB1 = false;
575 hasAB2 = false;
576 hasAC = false;
577 hasAC1 = false;
578 hasAC2 = false;
579
580 counter = 0;
581
582 for (; itNoANoSubNameA != nameTree.end(); itNoANoSubNameA++)
583 {
584 counter++;
585
586 if (itNoANoSubNameA->getPrefix() == nameA)
587 hasA = true;
588
589 if (itNoANoSubNameA->getPrefix() == nameAB)
590 hasAB = true;
591
592 if (itNoANoSubNameA->getPrefix() == nameAB1)
593 hasAB1 = true;
594
595 if (itNoANoSubNameA->getPrefix() == nameAB2)
596 hasAB2 = true;
597
598 if (itNoANoSubNameA->getPrefix() == nameAC)
599 hasAC = true;
600
601 if (itNoANoSubNameA->getPrefix() == nameAC1)
602 hasAC1 = true;
603
604 if (itNoANoSubNameA->getPrefix() == nameAC2)
605 hasAC2 = true;
606 }
607
608 BOOST_CHECK_EQUAL(hasA, true);
609 BOOST_CHECK_EQUAL(hasAB, false);
610 BOOST_CHECK_EQUAL(hasAB1, false);
611 BOOST_CHECK_EQUAL(hasAB2, false);
612 BOOST_CHECK_EQUAL(hasAC, false);
613 BOOST_CHECK_EQUAL(hasAC1, false);
614 BOOST_CHECK_EQUAL(hasAC2, false);
615
616 BOOST_CHECK_EQUAL(counter, 1);
617
618 // Example
619 // /
620 // /A
621 // /A/B x
622 // /A/B/C
623 // /A/D x
624 // /E
625 // /F
626
627 NameTree nameTreeExample(nBuckets);
628
629 Name nameRoot("/");
630 bool hasRoot = false;
631
632 nameTreeExample.lookup(nameA);
633 hasA = false;
634 nameTreeExample.lookup(nameAB);
635 hasAB = false;
636
637 Name nameABC("a/b/c");
638 bool hasABC = false;
639 nameTreeExample.lookup(nameABC);
640
641 Name nameAD("/a/d");
642 nameTreeExample.lookup(nameAD);
643 bool hasAD = false;
644
645 Name nameE("/e");
646 nameTreeExample.lookup(nameE);
647 bool hasE = false;
648
649 Name nameF("/f");
650 nameTreeExample.lookup(nameF);
651 bool hasF = false;
652
653 counter = 0;
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700654 const_iterator itExample = nameTreeExample.partialEnumerate(nameA,
655 &predicate_NameTreeEntry_Example);
Haowei Yuane1079fc2014-03-08 14:41:25 -0600656
657 for (; itExample != nameTreeExample.end(); itExample++)
658 {
659 counter++;
660
661 if (itExample->getPrefix() == nameRoot)
662 hasRoot = true;
663
664 if (itExample->getPrefix() == nameA)
665 hasA = true;
666
667 if (itExample->getPrefix() == nameAB)
668 hasAB = true;
669
670 if (itExample->getPrefix() == nameABC)
671 hasABC = true;
672
673 if (itExample->getPrefix() == nameAD)
674 hasAD = true;
675
676 if (itExample->getPrefix() == nameE)
677 hasE = true;
678
679 if (itExample->getPrefix() == nameF)
680 hasF = true;
681 }
682
683 BOOST_CHECK_EQUAL(hasRoot, false);
684 BOOST_CHECK_EQUAL(hasA, false);
685 BOOST_CHECK_EQUAL(hasAB, true);
686 BOOST_CHECK_EQUAL(hasABC, false);
687 BOOST_CHECK_EQUAL(hasAD, true);
688 BOOST_CHECK_EQUAL(hasE, false);
689 BOOST_CHECK_EQUAL(hasF, false);
690
691 BOOST_CHECK_EQUAL(counter, 2);
692}
693
694
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700695BOOST_AUTO_TEST_CASE(IteratorFindAllMatches)
Haowei Yuane1079fc2014-03-08 14:41:25 -0600696{
Haowei Yuane1079fc2014-03-08 14:41:25 -0600697 size_t nBuckets = 16;
698 NameTree nt(nBuckets);
699 int counter = 0;
700
701 Name nameABCDEF("a/b/c/d/e/f");
702 shared_ptr<name_tree::Entry> npeABCDEF = nt.lookup(nameABCDEF);
703
704 Name nameAAC("a/a/c");
705 shared_ptr<name_tree::Entry> npeAAC = nt.lookup(nameAAC);
706
707 Name nameAAD1("a/a/d/1");
708 shared_ptr<name_tree::Entry> npeAAD1 = nt.lookup(nameAAD1);
709
710 Name nameAAD2("a/a/d/2");
711 shared_ptr<name_tree::Entry> npeAAD2 = nt.lookup(nameAAD2);
712
713
714 BOOST_CHECK_EQUAL(nt.size(), 12);
715
716 Name nameRoot ("/");
717 Name nameA ("/a");
718 Name nameAB ("/a/b");
719 Name nameABC ("/a/b/c");
720 Name nameABCD ("/a/b/c/d");
721 Name nameABCDE("/a/b/c/d/e");
722 Name nameAA ("/a/a");
723 Name nameAAD ("/a/a/d");
724
725 bool hasRoot = false;
726 bool hasA = false;
727 bool hasAB = false;
728 bool hasABC = false;
729 bool hasABCD = false;
730 bool hasABCDE = false;
731 bool hasABCDEF = false;
732 bool hasAA = false;
733 bool hasAAC = false;
734 bool hasAAD = false;
735 bool hasAAD1 = false;
736 bool hasAAD2 = false;
737
738 counter = 0;
739
740 for (NameTree::const_iterator it = nt.findAllMatches(nameABCDEF);
741 it != nt.end(); it++)
742 {
743 counter++;
744
745 if (it->getPrefix() == nameRoot)
746 hasRoot = true;
747 if (it->getPrefix() == nameA)
748 hasA = true;
749 if (it->getPrefix() == nameAB)
750 hasAB = true;
751 if (it->getPrefix() == nameABC)
752 hasABC = true;
753 if (it->getPrefix() == nameABCD)
754 hasABCD = true;
755 if (it->getPrefix() == nameABCDE)
756 hasABCDE = true;
757 if (it->getPrefix() == nameABCDEF)
758 hasABCDEF = true;
759 if (it->getPrefix() == nameAA)
760 hasAA = true;
761 if (it->getPrefix() == nameAAC)
762 hasAAC = true;
763 if (it->getPrefix() == nameAAD)
764 hasAAD = true;
765 if (it->getPrefix() == nameAAD1)
766 hasAAD1 = true;
767 if (it->getPrefix() == nameAAD2)
768 hasAAD2 = true;
769 }
770
771 BOOST_CHECK_EQUAL(hasRoot , true);
772 BOOST_CHECK_EQUAL(hasA , true);
773 BOOST_CHECK_EQUAL(hasAB , true);
774 BOOST_CHECK_EQUAL(hasABC , true);
775 BOOST_CHECK_EQUAL(hasABCD , true);
776 BOOST_CHECK_EQUAL(hasABCDE , true);
777 BOOST_CHECK_EQUAL(hasABCDEF , true);
778 BOOST_CHECK_EQUAL(hasAA , false);
779 BOOST_CHECK_EQUAL(hasAAC , false);
780 BOOST_CHECK_EQUAL(hasAAD , false);
781 BOOST_CHECK_EQUAL(hasAAD1 , false);
782 BOOST_CHECK_EQUAL(hasAAD2 , false);
783
784 BOOST_CHECK_EQUAL(counter, 7);
HYuana9b85752014-02-26 02:32:30 -0600785}
786
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700787BOOST_AUTO_TEST_CASE(HashTableResizeShrink)
Haowei Yuanf52dac72014-03-24 23:35:03 -0500788{
789 size_t nBuckets = 16;
790 NameTree nameTree(nBuckets);
791
792 Name prefix("/a/b/c/d/e/f/g/h"); // requires 9 buckets
793
794 shared_ptr<name_tree::Entry> entry = nameTree.lookup(prefix);
795 BOOST_CHECK_EQUAL(nameTree.size(), 9);
796 BOOST_CHECK_EQUAL(nameTree.getNBuckets(), 32);
797
798 nameTree.eraseEntryIfEmpty(entry);
799 BOOST_CHECK_EQUAL(nameTree.size(), 0);
800 BOOST_CHECK_EQUAL(nameTree.getNBuckets(), 16);
801}
802
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700803// .lookup should not invalidate iterator
804BOOST_AUTO_TEST_CASE(SurvivedIteratorAfterLookup)
805{
806 NameTree nt;
807 nt.lookup("/A/B/C");
808 nt.lookup("/E");
809
810 Name nameB("/A/B");
811 std::set<Name> seenNames;
812 for (NameTree::const_iterator it = nt.begin(); it != nt.end(); ++it) {
813 BOOST_CHECK(seenNames.insert(it->getPrefix()).second);
814 if (it->getPrefix() == nameB) {
815 nt.lookup("/D");
816 }
817 }
818
819 BOOST_CHECK_EQUAL(seenNames.count("/"), 1);
820 BOOST_CHECK_EQUAL(seenNames.count("/A"), 1);
821 BOOST_CHECK_EQUAL(seenNames.count("/A/B"), 1);
822 BOOST_CHECK_EQUAL(seenNames.count("/A/B/C"), 1);
823 BOOST_CHECK_EQUAL(seenNames.count("/E"), 1);
824
825 seenNames.erase("/D"); // /D may or may not appear
826 BOOST_CHECK(seenNames.size() == 5);
827}
828
829// .eraseEntryIfEmpty should not invalidate iterator
830BOOST_AUTO_TEST_CASE(SurvivedIteratorAfterErase)
831{
832 NameTree nt;
833 nt.lookup("/A/B/C");
834 nt.lookup("/A/D/E");
835 nt.lookup("/A/F/G");
836 nt.lookup("/H");
837
838 Name nameD("/A/D");
839 std::set<Name> seenNames;
840 for (NameTree::const_iterator it = nt.begin(); it != nt.end(); ++it) {
841 BOOST_CHECK(seenNames.insert(it->getPrefix()).second);
842 if (it->getPrefix() == nameD) {
843 nt.eraseEntryIfEmpty(nt.findExactMatch("/A/F/G")); // /A/F/G and /A/F are erased
844 }
845 }
846
847 BOOST_CHECK_EQUAL(seenNames.count("/"), 1);
848 BOOST_CHECK_EQUAL(seenNames.count("/A"), 1);
849 BOOST_CHECK_EQUAL(seenNames.count("/A/B"), 1);
850 BOOST_CHECK_EQUAL(seenNames.count("/A/B/C"), 1);
851 BOOST_CHECK_EQUAL(seenNames.count("/A/D"), 1);
852 BOOST_CHECK_EQUAL(seenNames.count("/A/D/E"), 1);
853 BOOST_CHECK_EQUAL(seenNames.count("/H"), 1);
854
855 seenNames.erase("/A/F"); // /A/F may or may not appear
856 seenNames.erase("/A/F/G"); // /A/F/G may or may not appear
857 BOOST_CHECK(seenNames.size() == 7);
858}
859
HYuana9b85752014-02-26 02:32:30 -0600860BOOST_AUTO_TEST_SUITE_END()
861
Junxiao Shid9ee45c2014-02-27 15:38:11 -0700862} // namespace tests
HYuana9b85752014-02-26 02:32:30 -0600863} // namespace nfd