blob: d1fe068ee8042089313f4f768394d1fa017c2c46 [file] [log] [blame]
Junxiao Shic1e12362014-01-24 20:03:26 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
3 * Copyright (C) 2014 Named Data Networking Project
4 * See COPYING for copyright and distribution information.
5 */
6
7#include "table/fib.hpp"
Junxiao Shicbba04c2014-01-26 14:21:22 -07008#include "../face/dummy-face.hpp"
Junxiao Shic1e12362014-01-24 20:03:26 -07009
10#include <boost/test/unit_test.hpp>
11
Alexander Afanasyev18bbf812014-01-29 01:40:23 -080012namespace nfd {
Junxiao Shic1e12362014-01-24 20:03:26 -070013
Junxiao Shic1e12362014-01-24 20:03:26 -070014BOOST_AUTO_TEST_SUITE(TableFib)
15
16BOOST_AUTO_TEST_CASE(Entry)
17{
18 Name prefix("ndn:/pxWhfFza");
Junxiao Shi8c8d2182014-01-30 22:33:00 -070019 shared_ptr<Face> face1 = make_shared<DummyFace>();
20 shared_ptr<Face> face2 = make_shared<DummyFace>();
Junxiao Shic1e12362014-01-24 20:03:26 -070021
22 fib::Entry entry(prefix);
23 BOOST_CHECK(entry.getPrefix().equals(prefix));
24
25 const fib::NextHopList& nexthops1 = entry.getNextHops();
26 // []
27 BOOST_CHECK_EQUAL(nexthops1.size(), 0);
28
29 entry.addNextHop(face1, 20);
30 const fib::NextHopList& nexthops2 = entry.getNextHops();
31 // [(face1,20)]
32 BOOST_CHECK_EQUAL(nexthops2.size(), 1);
33 BOOST_CHECK_EQUAL(nexthops2.begin()->getFace(), face1);
34 BOOST_CHECK_EQUAL(nexthops2.begin()->getCost(), 20);
35
36 entry.addNextHop(face1, 30);
37 const fib::NextHopList& nexthops3 = entry.getNextHops();
38 // [(face1,30)]
39 BOOST_CHECK_EQUAL(nexthops3.size(), 1);
40 BOOST_CHECK_EQUAL(nexthops3.begin()->getFace(), face1);
41 BOOST_CHECK_EQUAL(nexthops3.begin()->getCost(), 30);
42
43 entry.addNextHop(face2, 40);
44 const fib::NextHopList& nexthops4 = entry.getNextHops();
45 // [(face1,30), (face2,40)]
46 BOOST_CHECK_EQUAL(nexthops4.size(), 2);
47 int i = -1;
48 for (fib::NextHopList::const_iterator it = nexthops4.begin();
49 it != nexthops4.end(); ++it) {
50 ++i;
51 switch (i) {
52 case 0 :
53 BOOST_CHECK_EQUAL(it->getFace(), face1);
54 BOOST_CHECK_EQUAL(it->getCost(), 30);
55 break;
56 case 1 :
57 BOOST_CHECK_EQUAL(it->getFace(), face2);
58 BOOST_CHECK_EQUAL(it->getCost(), 40);
59 break;
60 }
61 }
62
63 entry.addNextHop(face2, 10);
64 const fib::NextHopList& nexthops5 = entry.getNextHops();
65 // [(face2,10), (face1,30)]
66 BOOST_CHECK_EQUAL(nexthops5.size(), 2);
67 i = -1;
68 for (fib::NextHopList::const_iterator it = nexthops5.begin();
69 it != nexthops5.end(); ++it) {
70 ++i;
71 switch (i) {
72 case 0 :
73 BOOST_CHECK_EQUAL(it->getFace(), face2);
74 BOOST_CHECK_EQUAL(it->getCost(), 10);
75 break;
76 case 1 :
77 BOOST_CHECK_EQUAL(it->getFace(), face1);
78 BOOST_CHECK_EQUAL(it->getCost(), 30);
79 break;
80 }
81 }
82
83 entry.removeNextHop(face1);
84 const fib::NextHopList& nexthops6 = entry.getNextHops();
85 // [(face2,10)]
86 BOOST_CHECK_EQUAL(nexthops6.size(), 1);
87 BOOST_CHECK_EQUAL(nexthops6.begin()->getFace(), face2);
88 BOOST_CHECK_EQUAL(nexthops6.begin()->getCost(), 10);
89
90 entry.removeNextHop(face1);
91 const fib::NextHopList& nexthops7 = entry.getNextHops();
92 // [(face2,10)]
93 BOOST_CHECK_EQUAL(nexthops7.size(), 1);
94 BOOST_CHECK_EQUAL(nexthops7.begin()->getFace(), face2);
95 BOOST_CHECK_EQUAL(nexthops7.begin()->getCost(), 10);
96
97 entry.removeNextHop(face2);
98 const fib::NextHopList& nexthops8 = entry.getNextHops();
99 // []
100 BOOST_CHECK_EQUAL(nexthops8.size(), 0);
101
102 entry.removeNextHop(face2);
103 const fib::NextHopList& nexthops9 = entry.getNextHops();
104 // []
105 BOOST_CHECK_EQUAL(nexthops9.size(), 0);
106}
107
108BOOST_AUTO_TEST_CASE(Insert_LongestPrefixMatch)
109{
110 Name nameEmpty;
111 Name nameA ("ndn:/A");
112 Name nameAB ("ndn:/A/B");
113 Name nameABC ("ndn:/A/B/C");
114 Name nameABCD("ndn:/A/B/C/D");
115 Name nameE ("ndn:/E");
116
117 std::pair<shared_ptr<fib::Entry>, bool> insertRes;
118 shared_ptr<fib::Entry> entry;
119
120 Fib fib;
121 // ['/']
122
123 entry = fib.findLongestPrefixMatch(nameA);
124 BOOST_CHECK_NE(entry.get(), static_cast<fib::Entry*>(0));
125 BOOST_CHECK(entry->getPrefix().equals(nameEmpty));
126
127 insertRes = fib.insert(nameA);
128 BOOST_CHECK_EQUAL(insertRes.second, true);
129 BOOST_CHECK(insertRes.first->getPrefix().equals(nameA));
130 // ['/', '/A']
131
132 insertRes = fib.insert(nameA);
133 BOOST_CHECK_EQUAL(insertRes.second, false);
134 BOOST_CHECK(insertRes.first->getPrefix().equals(nameA));
135 // ['/', '/A']
136
137 entry = fib.findLongestPrefixMatch(nameA);
138 BOOST_CHECK_NE(entry.get(), static_cast<fib::Entry*>(0));
139 BOOST_CHECK(entry->getPrefix().equals(nameA));
140
141 entry = fib.findLongestPrefixMatch(nameABCD);
142 BOOST_CHECK_NE(entry.get(), static_cast<fib::Entry*>(0));
143 BOOST_CHECK(entry->getPrefix().equals(nameA));
144
145 insertRes = fib.insert(nameABC);
146 BOOST_CHECK_EQUAL(insertRes.second, true);
147 BOOST_CHECK(insertRes.first->getPrefix().equals(nameABC));
148 // ['/', '/A', '/A/B/C']
149
150 entry = fib.findLongestPrefixMatch(nameA);
151 BOOST_CHECK_NE(entry.get(), static_cast<fib::Entry*>(0));
152 BOOST_CHECK(entry->getPrefix().equals(nameA));
153
154 entry = fib.findLongestPrefixMatch(nameAB);
155 BOOST_CHECK_NE(entry.get(), static_cast<fib::Entry*>(0));
156 BOOST_CHECK(entry->getPrefix().equals(nameA));
157
158 entry = fib.findLongestPrefixMatch(nameABCD);
159 BOOST_CHECK_NE(entry.get(), static_cast<fib::Entry*>(0));
160 BOOST_CHECK(entry->getPrefix().equals(nameABC));
161
162 entry = fib.findLongestPrefixMatch(nameE);
163 BOOST_CHECK_NE(entry.get(), static_cast<fib::Entry*>(0));
164 BOOST_CHECK(entry->getPrefix().equals(nameEmpty));
165}
166
167BOOST_AUTO_TEST_CASE(RemoveNextHopFromAllEntries)
168{
Junxiao Shi8c8d2182014-01-30 22:33:00 -0700169 shared_ptr<Face> face1 = make_shared<DummyFace>();
170 shared_ptr<Face> face2 = make_shared<DummyFace>();
Junxiao Shic1e12362014-01-24 20:03:26 -0700171 Name nameA("ndn:/A");
172 Name nameB("ndn:/B");
173
174 std::pair<shared_ptr<fib::Entry>, bool> insertRes;
175 shared_ptr<fib::Entry> entry;
176
177 Fib fib;
178 // {'/':[]}
179
180 insertRes = fib.insert(nameA);
181 insertRes.first->addNextHop(face1, 0);
182 insertRes.first->addNextHop(face2, 0);
183 // {'/':[], '/A':[1,2]}
184
185 insertRes = fib.insert(nameB);
186 insertRes.first->addNextHop(face1, 0);
187 // {'/':[], '/A':[1,2], '/B':[1]}
188
189 fib.removeNextHopFromAllEntries(face1);
190 // {'/':[], '/A':[2], '/B':[]}
191
192 entry = fib.findLongestPrefixMatch(nameA);
193 BOOST_CHECK(entry->getPrefix().equals(nameA));
194 const fib::NextHopList& nexthopsA = entry->getNextHops();
195 BOOST_CHECK_EQUAL(nexthopsA.size(), 1);
196 BOOST_CHECK_EQUAL(nexthopsA.begin()->getFace(), face2);
197
198 entry = fib.findLongestPrefixMatch(nameB);
199 BOOST_CHECK(entry->getPrefix().equals(nameB));
200 const fib::NextHopList& nexthopsB = entry->getNextHops();
201 BOOST_CHECK_EQUAL(nexthopsB.size(), 0);
202}
203
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700204void
205validateFindExactMatch(const Fib& fib, const Name& target)
206{
207 shared_ptr<fib::Entry> entry = fib.findExactMatch(target);
208 if (static_cast<bool>(entry))
209 {
210 BOOST_CHECK_EQUAL(entry->getPrefix(), target);
211 }
212 else
213 {
214 BOOST_FAIL("No entry found for " << target);
215 }
216}
217
218void
219validateNoExactMatch(const Fib& fib, const Name& target)
220{
221 shared_ptr<fib::Entry> entry = fib.findExactMatch(target);
222 if (static_cast<bool>(entry))
223 {
224 BOOST_FAIL("Found unexpected entry for " << target);
225 }
226}
227
228BOOST_AUTO_TEST_CASE(FindExactMatch)
229{
230 Fib fib;
231 fib.insert("/A");
232 fib.insert("/A/B");
233 fib.insert("/A/B/C");
234
235 validateFindExactMatch(fib, "/A");
236 validateFindExactMatch(fib, "/A/B");
237 validateFindExactMatch(fib, "/A/B/C");
238 validateFindExactMatch(fib, "/");
239
240 validateNoExactMatch(fib, "/does/not/exist");
241
242 Fib gapFib;
243 fib.insert("/X");
244 fib.insert("/X/Y/Z");
245
246 validateNoExactMatch(gapFib, "/X/Y");
247
248 Fib emptyFib;
249 validateNoExactMatch(emptyFib, "/nothing/here");
250}
251
252void
253validateRemove(Fib& fib, const Name& target)
254{
255 fib.remove(target);
256
257 shared_ptr<fib::Entry> entry = fib.findExactMatch(target);
258 if (static_cast<bool>(entry))
259 {
260 BOOST_FAIL("Found \"removed\" entry for " << target);
261 }
262}
263
264BOOST_AUTO_TEST_CASE(Remove)
265{
266 Fib emptyFib;
267
268 emptyFib.remove("/does/not/exist"); // crash test
269
270 validateRemove(emptyFib, "/");
271
272 emptyFib.remove("/still/does/not/exist"); // crash test
273
274 Fib fib;
275 fib.insert("/A");
276 fib.insert("/A/B");
277 fib.insert("/A/B/C");
278
279 // check if we remove the right thing and leave
280 // everything else alone
281
282 validateRemove(fib, "/A/B");
283 validateFindExactMatch(fib, "/A");
284 validateFindExactMatch(fib, "/A/B/C");
285 validateFindExactMatch(fib, "/");
286
287 validateRemove(fib, "/A/B/C");
288 validateFindExactMatch(fib, "/A");
289 validateFindExactMatch(fib, "/");
290
291 validateRemove(fib, "/A");
292 validateFindExactMatch(fib, "/");
293
294 Fib gapFib;
295 gapFib.insert("/X");
296 gapFib.insert("/X/Y/Z");
297
298 gapFib.remove("/X/Y"); //should do nothing
299 validateFindExactMatch(gapFib, "/X");
300 validateFindExactMatch(gapFib, "/X/Y/Z");
301}
302
Junxiao Shic1e12362014-01-24 20:03:26 -0700303BOOST_AUTO_TEST_SUITE_END()
304
Alexander Afanasyev18bbf812014-01-29 01:40:23 -0800305} // namespace nfd