blob: 30846f4fd1bd62eeb8a266507d1330f1efaef57b [file] [log] [blame]
Junxiao Shic1e12362014-01-24 20:03:26 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
Junxiao Shi4370fde2016-02-24 12:20:46 -07003 * Copyright (c) 2014-2016, 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/>.
Junxiao Shiee5a4442014-07-27 17:13:43 -070024 */
Junxiao Shic1e12362014-01-24 20:03:26 -070025
26#include "table/fib.hpp"
Junxiao Shi4370fde2016-02-24 12:20:46 -070027#include "table/pit.hpp"
28#include "table/measurements.hpp"
Alexander Afanasyev613e2a92014-04-15 13:36:58 -070029#include "tests/daemon/face/dummy-face.hpp"
Junxiao Shic1e12362014-01-24 20:03:26 -070030
Junxiao Shid9ee45c2014-02-27 15:38:11 -070031#include "tests/test-common.hpp"
Junxiao Shic1e12362014-01-24 20:03:26 -070032
Alexander Afanasyev18bbf812014-01-29 01:40:23 -080033namespace nfd {
Junxiao Shid9ee45c2014-02-27 15:38:11 -070034namespace tests {
Junxiao Shic1e12362014-01-24 20:03:26 -070035
Junxiao Shi4370fde2016-02-24 12:20:46 -070036BOOST_AUTO_TEST_SUITE(Table)
37BOOST_FIXTURE_TEST_SUITE(TestFib, BaseFixture)
Junxiao Shic1e12362014-01-24 20:03:26 -070038
39BOOST_AUTO_TEST_CASE(Entry)
40{
41 Name prefix("ndn:/pxWhfFza");
Junxiao Shi8c8d2182014-01-30 22:33:00 -070042 shared_ptr<Face> face1 = make_shared<DummyFace>();
43 shared_ptr<Face> face2 = make_shared<DummyFace>();
Junxiao Shiefceadc2014-03-09 18:52:57 -070044
Junxiao Shic1e12362014-01-24 20:03:26 -070045 fib::Entry entry(prefix);
Junxiao Shiefceadc2014-03-09 18:52:57 -070046 BOOST_CHECK_EQUAL(entry.getPrefix(), prefix);
47
Junxiao Shic1e12362014-01-24 20:03:26 -070048 const fib::NextHopList& nexthops1 = entry.getNextHops();
49 // []
50 BOOST_CHECK_EQUAL(nexthops1.size(), 0);
Junxiao Shiefceadc2014-03-09 18:52:57 -070051
Junxiao Shic1e12362014-01-24 20:03:26 -070052 entry.addNextHop(face1, 20);
53 const fib::NextHopList& nexthops2 = entry.getNextHops();
54 // [(face1,20)]
55 BOOST_CHECK_EQUAL(nexthops2.size(), 1);
56 BOOST_CHECK_EQUAL(nexthops2.begin()->getFace(), face1);
57 BOOST_CHECK_EQUAL(nexthops2.begin()->getCost(), 20);
Junxiao Shiefceadc2014-03-09 18:52:57 -070058
Junxiao Shic1e12362014-01-24 20:03:26 -070059 entry.addNextHop(face1, 30);
60 const fib::NextHopList& nexthops3 = entry.getNextHops();
61 // [(face1,30)]
62 BOOST_CHECK_EQUAL(nexthops3.size(), 1);
63 BOOST_CHECK_EQUAL(nexthops3.begin()->getFace(), face1);
64 BOOST_CHECK_EQUAL(nexthops3.begin()->getCost(), 30);
65
66 entry.addNextHop(face2, 40);
67 const fib::NextHopList& nexthops4 = entry.getNextHops();
68 // [(face1,30), (face2,40)]
69 BOOST_CHECK_EQUAL(nexthops4.size(), 2);
70 int i = -1;
71 for (fib::NextHopList::const_iterator it = nexthops4.begin();
Junxiao Shi4370fde2016-02-24 12:20:46 -070072 it != nexthops4.end(); ++it) {
Junxiao Shic1e12362014-01-24 20:03:26 -070073 ++i;
74 switch (i) {
Junxiao Shi4370fde2016-02-24 12:20:46 -070075 case 0:
Junxiao Shic1e12362014-01-24 20:03:26 -070076 BOOST_CHECK_EQUAL(it->getFace(), face1);
77 BOOST_CHECK_EQUAL(it->getCost(), 30);
78 break;
Junxiao Shi4370fde2016-02-24 12:20:46 -070079 case 1:
Junxiao Shic1e12362014-01-24 20:03:26 -070080 BOOST_CHECK_EQUAL(it->getFace(), face2);
81 BOOST_CHECK_EQUAL(it->getCost(), 40);
82 break;
83 }
84 }
85
86 entry.addNextHop(face2, 10);
87 const fib::NextHopList& nexthops5 = entry.getNextHops();
88 // [(face2,10), (face1,30)]
89 BOOST_CHECK_EQUAL(nexthops5.size(), 2);
90 i = -1;
91 for (fib::NextHopList::const_iterator it = nexthops5.begin();
Junxiao Shi4370fde2016-02-24 12:20:46 -070092 it != nexthops5.end(); ++it) {
Junxiao Shic1e12362014-01-24 20:03:26 -070093 ++i;
94 switch (i) {
Junxiao Shi4370fde2016-02-24 12:20:46 -070095 case 0:
Junxiao Shic1e12362014-01-24 20:03:26 -070096 BOOST_CHECK_EQUAL(it->getFace(), face2);
97 BOOST_CHECK_EQUAL(it->getCost(), 10);
98 break;
Junxiao Shi4370fde2016-02-24 12:20:46 -070099 case 1:
Junxiao Shic1e12362014-01-24 20:03:26 -0700100 BOOST_CHECK_EQUAL(it->getFace(), face1);
101 BOOST_CHECK_EQUAL(it->getCost(), 30);
102 break;
103 }
104 }
Junxiao Shiefceadc2014-03-09 18:52:57 -0700105
Junxiao Shic1e12362014-01-24 20:03:26 -0700106 entry.removeNextHop(face1);
107 const fib::NextHopList& nexthops6 = entry.getNextHops();
108 // [(face2,10)]
109 BOOST_CHECK_EQUAL(nexthops6.size(), 1);
110 BOOST_CHECK_EQUAL(nexthops6.begin()->getFace(), face2);
111 BOOST_CHECK_EQUAL(nexthops6.begin()->getCost(), 10);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700112
Junxiao Shic1e12362014-01-24 20:03:26 -0700113 entry.removeNextHop(face1);
114 const fib::NextHopList& nexthops7 = entry.getNextHops();
115 // [(face2,10)]
116 BOOST_CHECK_EQUAL(nexthops7.size(), 1);
117 BOOST_CHECK_EQUAL(nexthops7.begin()->getFace(), face2);
118 BOOST_CHECK_EQUAL(nexthops7.begin()->getCost(), 10);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700119
Junxiao Shic1e12362014-01-24 20:03:26 -0700120 entry.removeNextHop(face2);
121 const fib::NextHopList& nexthops8 = entry.getNextHops();
122 // []
123 BOOST_CHECK_EQUAL(nexthops8.size(), 0);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700124
Junxiao Shic1e12362014-01-24 20:03:26 -0700125 entry.removeNextHop(face2);
126 const fib::NextHopList& nexthops9 = entry.getNextHops();
127 // []
128 BOOST_CHECK_EQUAL(nexthops9.size(), 0);
129}
130
131BOOST_AUTO_TEST_CASE(Insert_LongestPrefixMatch)
132{
133 Name nameEmpty;
134 Name nameA ("ndn:/A");
135 Name nameAB ("ndn:/A/B");
136 Name nameABC ("ndn:/A/B/C");
137 Name nameABCD("ndn:/A/B/C/D");
138 Name nameE ("ndn:/E");
Junxiao Shiefceadc2014-03-09 18:52:57 -0700139
Junxiao Shic1e12362014-01-24 20:03:26 -0700140 std::pair<shared_ptr<fib::Entry>, bool> insertRes;
141 shared_ptr<fib::Entry> entry;
142
Haowei Yuanf52dac72014-03-24 23:35:03 -0500143 NameTree nameTree;
HangZhangad4afd12014-03-01 11:03:08 +0800144 Fib fib(nameTree);
Junxiao Shi40631842014-03-01 13:52:37 -0700145 // []
Junxiao Shiefceadc2014-03-09 18:52:57 -0700146 BOOST_CHECK_EQUAL(fib.size(), 0);
Junxiao Shi40631842014-03-01 13:52:37 -0700147
148 entry = fib.findLongestPrefixMatch(nameA);
149 BOOST_REQUIRE(static_cast<bool>(entry)); // the empty entry
Junxiao Shiefceadc2014-03-09 18:52:57 -0700150
Junxiao Shi40631842014-03-01 13:52:37 -0700151 insertRes = fib.insert(nameEmpty);
152 BOOST_CHECK_EQUAL(insertRes.second, true);
153 BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameEmpty);
Junxiao Shic1e12362014-01-24 20:03:26 -0700154 // ['/']
Junxiao Shiefceadc2014-03-09 18:52:57 -0700155 BOOST_CHECK_EQUAL(fib.size(), 1);
156
Junxiao Shic1e12362014-01-24 20:03:26 -0700157 entry = fib.findLongestPrefixMatch(nameA);
Junxiao Shi40631842014-03-01 13:52:37 -0700158 BOOST_REQUIRE(static_cast<bool>(entry));
159 BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700160
Junxiao Shic1e12362014-01-24 20:03:26 -0700161 insertRes = fib.insert(nameA);
162 BOOST_CHECK_EQUAL(insertRes.second, true);
Junxiao Shi40631842014-03-01 13:52:37 -0700163 BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameA);
Junxiao Shic1e12362014-01-24 20:03:26 -0700164 // ['/', '/A']
Junxiao Shiefceadc2014-03-09 18:52:57 -0700165 BOOST_CHECK_EQUAL(fib.size(), 2);
166
Junxiao Shic1e12362014-01-24 20:03:26 -0700167 insertRes = fib.insert(nameA);
168 BOOST_CHECK_EQUAL(insertRes.second, false);
Junxiao Shi40631842014-03-01 13:52:37 -0700169 BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameA);
Junxiao Shic1e12362014-01-24 20:03:26 -0700170 // ['/', '/A']
Junxiao Shiefceadc2014-03-09 18:52:57 -0700171 BOOST_CHECK_EQUAL(fib.size(), 2);
Junxiao Shic1e12362014-01-24 20:03:26 -0700172
173 entry = fib.findLongestPrefixMatch(nameA);
Junxiao Shi40631842014-03-01 13:52:37 -0700174 BOOST_REQUIRE(static_cast<bool>(entry));
175 BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700176
Junxiao Shic1e12362014-01-24 20:03:26 -0700177 entry = fib.findLongestPrefixMatch(nameABCD);
Junxiao Shi40631842014-03-01 13:52:37 -0700178 BOOST_REQUIRE(static_cast<bool>(entry));
179 BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700180
Junxiao Shic1e12362014-01-24 20:03:26 -0700181 insertRes = fib.insert(nameABC);
182 BOOST_CHECK_EQUAL(insertRes.second, true);
Junxiao Shi40631842014-03-01 13:52:37 -0700183 BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameABC);
Junxiao Shic1e12362014-01-24 20:03:26 -0700184 // ['/', '/A', '/A/B/C']
Junxiao Shiefceadc2014-03-09 18:52:57 -0700185 BOOST_CHECK_EQUAL(fib.size(), 3);
Junxiao Shic1e12362014-01-24 20:03:26 -0700186
187 entry = fib.findLongestPrefixMatch(nameA);
Junxiao Shi40631842014-03-01 13:52:37 -0700188 BOOST_REQUIRE(static_cast<bool>(entry));
189 BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700190
Junxiao Shic1e12362014-01-24 20:03:26 -0700191 entry = fib.findLongestPrefixMatch(nameAB);
Junxiao Shi40631842014-03-01 13:52:37 -0700192 BOOST_REQUIRE(static_cast<bool>(entry));
193 BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700194
Junxiao Shic1e12362014-01-24 20:03:26 -0700195 entry = fib.findLongestPrefixMatch(nameABCD);
Junxiao Shi40631842014-03-01 13:52:37 -0700196 BOOST_REQUIRE(static_cast<bool>(entry));
197 BOOST_CHECK_EQUAL(entry->getPrefix(), nameABC);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700198
Junxiao Shic1e12362014-01-24 20:03:26 -0700199 entry = fib.findLongestPrefixMatch(nameE);
Junxiao Shi40631842014-03-01 13:52:37 -0700200 BOOST_REQUIRE(static_cast<bool>(entry));
201 BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty);
Junxiao Shic1e12362014-01-24 20:03:26 -0700202}
203
Junxiao Shi4370fde2016-02-24 12:20:46 -0700204BOOST_AUTO_TEST_CASE(LongestPrefixMatchWithPitEntry)
205{
206 NameTree nameTree;
207 Fib fib(nameTree);
208
209 shared_ptr<Data> dataABC = makeData("/A/B/C");
210 Name fullNameABC = dataABC->getFullName();
211 shared_ptr<Data> dataADE = makeData("/A/D/E");
212 Name fullNameADE = dataADE->getFullName();
213 fib.insert("/A");
214 fib.insert(fullNameABC);
215
216 Pit pit(nameTree);
217 shared_ptr<Interest> interestAB = makeInterest("/A/B");
218 shared_ptr<pit::Entry> pitAB = pit.insert(*interestAB).first;
219 shared_ptr<Interest> interestABC = makeInterest(fullNameABC);
220 shared_ptr<pit::Entry> pitABC = pit.insert(*interestABC).first;
221 shared_ptr<Interest> interestADE = makeInterest(fullNameADE);
222 shared_ptr<pit::Entry> pitADE = pit.insert(*interestADE).first;
223
224 size_t nNameTreeEntries = nameTree.size();
225
226 shared_ptr<fib::Entry> entry = fib.findLongestPrefixMatch(*pitAB);
227 BOOST_REQUIRE(entry != nullptr);
228 BOOST_CHECK_EQUAL(entry->getPrefix(), "/A");
229
230 entry = fib.findLongestPrefixMatch(*pitABC);
231 BOOST_REQUIRE(entry != nullptr);
232 BOOST_CHECK_EQUAL(entry->getPrefix(), fullNameABC);
233
234 entry = fib.findLongestPrefixMatch(*pitADE);
235 BOOST_REQUIRE(entry != nullptr);
236 BOOST_CHECK_EQUAL(entry->getPrefix(), "/A");
237
238 BOOST_CHECK_EQUAL(nameTree.size(), nNameTreeEntries);
239}
240
241BOOST_AUTO_TEST_CASE(LongestPrefixMatchWithMeasurementsEntry)
242{
243 NameTree nameTree;
244 Fib fib(nameTree);
245
246 fib.insert("/A");
247 fib.insert("/A/B/C");
248
249 Measurements measurements(nameTree);
250 shared_ptr<measurements::Entry> mAB = measurements.get("/A/B");
251 shared_ptr<measurements::Entry> mABCD = measurements.get("/A/B/C/D");
252
253 shared_ptr<fib::Entry> entry = fib.findLongestPrefixMatch(*mAB);
254 BOOST_REQUIRE(entry != nullptr);
255 BOOST_CHECK_EQUAL(entry->getPrefix(), "/A");
256
257 entry = fib.findLongestPrefixMatch(*mABCD);
258 BOOST_REQUIRE(entry != nullptr);
259 BOOST_CHECK_EQUAL(entry->getPrefix(), "/A/B/C");
260}
261
Junxiao Shic1e12362014-01-24 20:03:26 -0700262BOOST_AUTO_TEST_CASE(RemoveNextHopFromAllEntries)
263{
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700264 shared_ptr<Face> face1 = make_shared<DummyFace>();
265 shared_ptr<Face> face2 = make_shared<DummyFace>();
Junxiao Shiefceadc2014-03-09 18:52:57 -0700266 Name nameEmpty("ndn:/");
Junxiao Shic1e12362014-01-24 20:03:26 -0700267 Name nameA("ndn:/A");
268 Name nameB("ndn:/B");
Junxiao Shiefceadc2014-03-09 18:52:57 -0700269
Junxiao Shic1e12362014-01-24 20:03:26 -0700270 std::pair<shared_ptr<fib::Entry>, bool> insertRes;
271 shared_ptr<fib::Entry> entry;
Junxiao Shiefceadc2014-03-09 18:52:57 -0700272
Haowei Yuanf52dac72014-03-24 23:35:03 -0500273 NameTree nameTree;
HangZhangad4afd12014-03-01 11:03:08 +0800274 Fib fib(nameTree);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700275 // {}
276
Junxiao Shic1e12362014-01-24 20:03:26 -0700277 insertRes = fib.insert(nameA);
278 insertRes.first->addNextHop(face1, 0);
279 insertRes.first->addNextHop(face2, 0);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700280 // {'/A':[1,2]}
Junxiao Shic1e12362014-01-24 20:03:26 -0700281
282 insertRes = fib.insert(nameB);
283 insertRes.first->addNextHop(face1, 0);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700284 // {'/A':[1,2], '/B':[1]}
285 BOOST_CHECK_EQUAL(fib.size(), 2);
286
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700287 insertRes = fib.insert("/C");
288 insertRes.first->addNextHop(face2, 1);
289 // {'/A':[1,2], '/B':[1], '/C':[2]}
290 BOOST_CHECK_EQUAL(fib.size(), 3);
291
292 insertRes = fib.insert("/B/1");
293 insertRes.first->addNextHop(face1, 0);
294 // {'/A':[1,2], '/B':[1], '/B/1':[1], '/C':[2]}
295 BOOST_CHECK_EQUAL(fib.size(), 4);
296
297 insertRes = fib.insert("/B/1/2");
298 insertRes.first->addNextHop(face1, 0);
299 // {'/A':[1,2], '/B':[1], '/B/1':[1], '/B/1/2':[1], '/C':[2]}
300 BOOST_CHECK_EQUAL(fib.size(), 5);
301
302 insertRes = fib.insert("/B/1/2/3");
303 insertRes.first->addNextHop(face1, 0);
304 // {'/A':[1,2], '/B':[1], '/B/1':[1], '/B/1/2':[1], '/B/1/3':[1], '/C':[2]}
305 BOOST_CHECK_EQUAL(fib.size(), 6);
306
307 insertRes = fib.insert("/B/1/2/3/4");
308 insertRes.first->addNextHop(face1, 0);
309 // {'/A':[1,2], '/B':[1], '/B/1':[1], '/B/1/2':[1], '/B/1/2/3':[1], '/B/1/2/3/4':[1], '/C':[2]}
310 BOOST_CHECK_EQUAL(fib.size(), 7);
311
312 /////////////
313
Junxiao Shic1e12362014-01-24 20:03:26 -0700314 fib.removeNextHopFromAllEntries(face1);
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700315 // {'/A':[2], '/C':[2]}
316 BOOST_CHECK_EQUAL(fib.size(), 2);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700317
Junxiao Shic1e12362014-01-24 20:03:26 -0700318 entry = fib.findLongestPrefixMatch(nameA);
Junxiao Shi40631842014-03-01 13:52:37 -0700319 BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
Junxiao Shic1e12362014-01-24 20:03:26 -0700320 const fib::NextHopList& nexthopsA = entry->getNextHops();
321 BOOST_CHECK_EQUAL(nexthopsA.size(), 1);
322 BOOST_CHECK_EQUAL(nexthopsA.begin()->getFace(), face2);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700323
Junxiao Shic1e12362014-01-24 20:03:26 -0700324 entry = fib.findLongestPrefixMatch(nameB);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700325 BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty);
Junxiao Shic1e12362014-01-24 20:03:26 -0700326}
327
Junxiao Shi4b2e6cb2014-12-03 00:51:45 -0700328BOOST_AUTO_TEST_CASE(RemoveNextHopFromManyEntries)
329{
330 NameTree nameTree(16);
331 Fib fib(nameTree);
332 shared_ptr<Face> face1 = make_shared<DummyFace>();
333
334 for (uint64_t i = 0; i < 300; ++i) {
335 shared_ptr<fib::Entry> entry = fib.insert(Name("/P").appendVersion(i)).first;
336 entry->addNextHop(face1, 0);
337 }
338 BOOST_CHECK_EQUAL(fib.size(), 300);
339
340 fib.removeNextHopFromAllEntries(face1);
341 BOOST_CHECK_EQUAL(fib.size(), 0);
342}
343
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700344void
345validateFindExactMatch(const Fib& fib, const Name& target)
346{
347 shared_ptr<fib::Entry> entry = fib.findExactMatch(target);
348 if (static_cast<bool>(entry))
349 {
350 BOOST_CHECK_EQUAL(entry->getPrefix(), target);
351 }
352 else
353 {
354 BOOST_FAIL("No entry found for " << target);
355 }
356}
357
358void
359validateNoExactMatch(const Fib& fib, const Name& target)
360{
361 shared_ptr<fib::Entry> entry = fib.findExactMatch(target);
362 if (static_cast<bool>(entry))
363 {
364 BOOST_FAIL("Found unexpected entry for " << target);
365 }
366}
367
368BOOST_AUTO_TEST_CASE(FindExactMatch)
369{
Haowei Yuanf52dac72014-03-24 23:35:03 -0500370 NameTree nameTree;
HangZhangad4afd12014-03-01 11:03:08 +0800371 Fib fib(nameTree);
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700372 fib.insert("/A");
373 fib.insert("/A/B");
374 fib.insert("/A/B/C");
375
376 validateFindExactMatch(fib, "/A");
377 validateFindExactMatch(fib, "/A/B");
378 validateFindExactMatch(fib, "/A/B/C");
Junxiao Shi40631842014-03-01 13:52:37 -0700379 validateNoExactMatch(fib, "/");
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700380
381 validateNoExactMatch(fib, "/does/not/exist");
382
Haowei Yuanf52dac72014-03-24 23:35:03 -0500383 NameTree gapNameTree;
HangZhangad4afd12014-03-01 11:03:08 +0800384 Fib gapFib(nameTree);
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700385 fib.insert("/X");
386 fib.insert("/X/Y/Z");
387
388 validateNoExactMatch(gapFib, "/X/Y");
389
Haowei Yuanf52dac72014-03-24 23:35:03 -0500390 NameTree emptyNameTree;
HangZhangad4afd12014-03-01 11:03:08 +0800391 Fib emptyFib(emptyNameTree);
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700392 validateNoExactMatch(emptyFib, "/nothing/here");
393}
394
395void
Junxiao Shiee5a4442014-07-27 17:13:43 -0700396validateErase(Fib& fib, const Name& target)
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700397{
HangZhangad4afd12014-03-01 11:03:08 +0800398 fib.erase(target);
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700399
400 shared_ptr<fib::Entry> entry = fib.findExactMatch(target);
401 if (static_cast<bool>(entry))
402 {
403 BOOST_FAIL("Found \"removed\" entry for " << target);
404 }
405}
406
Junxiao Shiee5a4442014-07-27 17:13:43 -0700407BOOST_AUTO_TEST_CASE(Erase)
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700408{
Haowei Yuanf52dac72014-03-24 23:35:03 -0500409 NameTree emptyNameTree;
HangZhangad4afd12014-03-01 11:03:08 +0800410 Fib emptyFib(emptyNameTree);
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700411
HangZhangad4afd12014-03-01 11:03:08 +0800412 emptyFib.erase("/does/not/exist"); // crash test
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700413
Junxiao Shiee5a4442014-07-27 17:13:43 -0700414 validateErase(emptyFib, "/");
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700415
HangZhangad4afd12014-03-01 11:03:08 +0800416 emptyFib.erase("/still/does/not/exist"); // crash test
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700417
Haowei Yuanf52dac72014-03-24 23:35:03 -0500418 NameTree nameTree;
HangZhangad4afd12014-03-01 11:03:08 +0800419 Fib fib(nameTree);
Junxiao Shi40631842014-03-01 13:52:37 -0700420 fib.insert("/");
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700421 fib.insert("/A");
422 fib.insert("/A/B");
423 fib.insert("/A/B/C");
424
425 // check if we remove the right thing and leave
426 // everything else alone
427
Junxiao Shiee5a4442014-07-27 17:13:43 -0700428 validateErase(fib, "/A/B");
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700429 validateFindExactMatch(fib, "/A");
430 validateFindExactMatch(fib, "/A/B/C");
431 validateFindExactMatch(fib, "/");
432
Junxiao Shiee5a4442014-07-27 17:13:43 -0700433 validateErase(fib, "/A/B/C");
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700434 validateFindExactMatch(fib, "/A");
435 validateFindExactMatch(fib, "/");
436
Junxiao Shiee5a4442014-07-27 17:13:43 -0700437 validateErase(fib, "/A");
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700438 validateFindExactMatch(fib, "/");
439
Junxiao Shiee5a4442014-07-27 17:13:43 -0700440 validateErase(fib, "/");
Junxiao Shi40631842014-03-01 13:52:37 -0700441 validateNoExactMatch(fib, "/");
442
Haowei Yuanf52dac72014-03-24 23:35:03 -0500443 NameTree gapNameTree;
HangZhangad4afd12014-03-01 11:03:08 +0800444 Fib gapFib(gapNameTree);
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700445 gapFib.insert("/X");
446 gapFib.insert("/X/Y/Z");
447
HangZhangad4afd12014-03-01 11:03:08 +0800448 gapFib.erase("/X/Y"); //should do nothing
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700449 validateFindExactMatch(gapFib, "/X");
450 validateFindExactMatch(gapFib, "/X/Y/Z");
451}
452
Junxiao Shiee5a4442014-07-27 17:13:43 -0700453BOOST_AUTO_TEST_CASE(EraseNameTreeEntry)
454{
455 NameTree nameTree;
456 Fib fib(nameTree);
457 size_t nNameTreeEntriesBefore = nameTree.size();
458
459 fib.insert("ndn:/A/B/C");
460 fib.erase("ndn:/A/B/C");
461 BOOST_CHECK_EQUAL(nameTree.size(), nNameTreeEntriesBefore);
462}
463
HangZhang5d469422014-03-12 09:26:26 +0800464BOOST_AUTO_TEST_CASE(Iterator)
465{
Haowei Yuanf52dac72014-03-24 23:35:03 -0500466 NameTree nameTree;
HangZhang5d469422014-03-12 09:26:26 +0800467 Fib fib(nameTree);
468 Name nameA("/A");
469 Name nameAB("/A/B");
470 Name nameABC("/A/B/C");
471 Name nameRoot("/");
472
473 fib.insert(nameA);
474 fib.insert(nameAB);
475 fib.insert(nameABC);
476 fib.insert(nameRoot);
477
478 std::set<Name> expected;
479 expected.insert(nameA);
480 expected.insert(nameAB);
481 expected.insert(nameABC);
482 expected.insert(nameRoot);
483
Junxiao Shi4370fde2016-02-24 12:20:46 -0700484 for (Fib::const_iterator it = fib.begin(); it != fib.end(); it++) {
HangZhang5d469422014-03-12 09:26:26 +0800485 bool isInSet = expected.find(it->getPrefix()) != expected.end();
486 BOOST_CHECK(isInSet);
487 expected.erase(it->getPrefix());
488 }
489
490 BOOST_CHECK_EQUAL(expected.size(), 0);
491}
492
Junxiao Shi4370fde2016-02-24 12:20:46 -0700493BOOST_AUTO_TEST_SUITE_END() // TestFib
494BOOST_AUTO_TEST_SUITE_END() // Table
Junxiao Shic1e12362014-01-24 20:03:26 -0700495
Junxiao Shid9ee45c2014-02-27 15:38:11 -0700496} // namespace tests
Alexander Afanasyev18bbf812014-01-29 01:40:23 -0800497} // namespace nfd