Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 1 | /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
| 2 | /** |
Junxiao Shi | 4370fde | 2016-02-24 12:20:46 -0700 | [diff] [blame] | 3 | * Copyright (c) 2014-2016, Regents of the University of California, |
Spyridon Mastorakis | d0381c0 | 2015-02-19 10:29:41 -0800 | [diff] [blame] | 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 Afanasyev | 9bcbc7c | 2014-04-06 19:37:37 -0700 | [diff] [blame] | 10 | * |
| 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 Shi | ee5a444 | 2014-07-27 17:13:43 -0700 | [diff] [blame] | 24 | */ |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 25 | |
| 26 | #include "table/fib.hpp" |
Junxiao Shi | 4370fde | 2016-02-24 12:20:46 -0700 | [diff] [blame] | 27 | #include "table/pit.hpp" |
| 28 | #include "table/measurements.hpp" |
Alexander Afanasyev | 613e2a9 | 2014-04-15 13:36:58 -0700 | [diff] [blame] | 29 | #include "tests/daemon/face/dummy-face.hpp" |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 30 | |
Junxiao Shi | d9ee45c | 2014-02-27 15:38:11 -0700 | [diff] [blame] | 31 | #include "tests/test-common.hpp" |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 32 | |
Alexander Afanasyev | 18bbf81 | 2014-01-29 01:40:23 -0800 | [diff] [blame] | 33 | namespace nfd { |
Junxiao Shi | d9ee45c | 2014-02-27 15:38:11 -0700 | [diff] [blame] | 34 | namespace tests { |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 35 | |
Junxiao Shi | 4370fde | 2016-02-24 12:20:46 -0700 | [diff] [blame] | 36 | BOOST_AUTO_TEST_SUITE(Table) |
| 37 | BOOST_FIXTURE_TEST_SUITE(TestFib, BaseFixture) |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 38 | |
| 39 | BOOST_AUTO_TEST_CASE(Entry) |
| 40 | { |
| 41 | Name prefix("ndn:/pxWhfFza"); |
Junxiao Shi | 8c8d218 | 2014-01-30 22:33:00 -0700 | [diff] [blame] | 42 | shared_ptr<Face> face1 = make_shared<DummyFace>(); |
| 43 | shared_ptr<Face> face2 = make_shared<DummyFace>(); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 44 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 45 | fib::Entry entry(prefix); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 46 | BOOST_CHECK_EQUAL(entry.getPrefix(), prefix); |
| 47 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 48 | const fib::NextHopList& nexthops1 = entry.getNextHops(); |
| 49 | // [] |
| 50 | BOOST_CHECK_EQUAL(nexthops1.size(), 0); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 51 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 52 | 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 Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 58 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 59 | 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 Shi | 4370fde | 2016-02-24 12:20:46 -0700 | [diff] [blame] | 72 | it != nexthops4.end(); ++it) { |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 73 | ++i; |
| 74 | switch (i) { |
Junxiao Shi | 4370fde | 2016-02-24 12:20:46 -0700 | [diff] [blame] | 75 | case 0: |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 76 | BOOST_CHECK_EQUAL(it->getFace(), face1); |
| 77 | BOOST_CHECK_EQUAL(it->getCost(), 30); |
| 78 | break; |
Junxiao Shi | 4370fde | 2016-02-24 12:20:46 -0700 | [diff] [blame] | 79 | case 1: |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 80 | 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 Shi | 4370fde | 2016-02-24 12:20:46 -0700 | [diff] [blame] | 92 | it != nexthops5.end(); ++it) { |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 93 | ++i; |
| 94 | switch (i) { |
Junxiao Shi | 4370fde | 2016-02-24 12:20:46 -0700 | [diff] [blame] | 95 | case 0: |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 96 | BOOST_CHECK_EQUAL(it->getFace(), face2); |
| 97 | BOOST_CHECK_EQUAL(it->getCost(), 10); |
| 98 | break; |
Junxiao Shi | 4370fde | 2016-02-24 12:20:46 -0700 | [diff] [blame] | 99 | case 1: |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 100 | BOOST_CHECK_EQUAL(it->getFace(), face1); |
| 101 | BOOST_CHECK_EQUAL(it->getCost(), 30); |
| 102 | break; |
| 103 | } |
| 104 | } |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 105 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 106 | 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 Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 112 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 113 | 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 Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 119 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 120 | entry.removeNextHop(face2); |
| 121 | const fib::NextHopList& nexthops8 = entry.getNextHops(); |
| 122 | // [] |
| 123 | BOOST_CHECK_EQUAL(nexthops8.size(), 0); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 124 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 125 | entry.removeNextHop(face2); |
| 126 | const fib::NextHopList& nexthops9 = entry.getNextHops(); |
| 127 | // [] |
| 128 | BOOST_CHECK_EQUAL(nexthops9.size(), 0); |
| 129 | } |
| 130 | |
| 131 | BOOST_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 Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 139 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 140 | std::pair<shared_ptr<fib::Entry>, bool> insertRes; |
| 141 | shared_ptr<fib::Entry> entry; |
| 142 | |
Haowei Yuan | f52dac7 | 2014-03-24 23:35:03 -0500 | [diff] [blame] | 143 | NameTree nameTree; |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 144 | Fib fib(nameTree); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 145 | // [] |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 146 | BOOST_CHECK_EQUAL(fib.size(), 0); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 147 | |
| 148 | entry = fib.findLongestPrefixMatch(nameA); |
| 149 | BOOST_REQUIRE(static_cast<bool>(entry)); // the empty entry |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 150 | |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 151 | insertRes = fib.insert(nameEmpty); |
| 152 | BOOST_CHECK_EQUAL(insertRes.second, true); |
| 153 | BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameEmpty); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 154 | // ['/'] |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 155 | BOOST_CHECK_EQUAL(fib.size(), 1); |
| 156 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 157 | entry = fib.findLongestPrefixMatch(nameA); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 158 | BOOST_REQUIRE(static_cast<bool>(entry)); |
| 159 | BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 160 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 161 | insertRes = fib.insert(nameA); |
| 162 | BOOST_CHECK_EQUAL(insertRes.second, true); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 163 | BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameA); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 164 | // ['/', '/A'] |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 165 | BOOST_CHECK_EQUAL(fib.size(), 2); |
| 166 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 167 | insertRes = fib.insert(nameA); |
| 168 | BOOST_CHECK_EQUAL(insertRes.second, false); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 169 | BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameA); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 170 | // ['/', '/A'] |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 171 | BOOST_CHECK_EQUAL(fib.size(), 2); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 172 | |
| 173 | entry = fib.findLongestPrefixMatch(nameA); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 174 | BOOST_REQUIRE(static_cast<bool>(entry)); |
| 175 | BOOST_CHECK_EQUAL(entry->getPrefix(), nameA); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 176 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 177 | entry = fib.findLongestPrefixMatch(nameABCD); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 178 | BOOST_REQUIRE(static_cast<bool>(entry)); |
| 179 | BOOST_CHECK_EQUAL(entry->getPrefix(), nameA); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 180 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 181 | insertRes = fib.insert(nameABC); |
| 182 | BOOST_CHECK_EQUAL(insertRes.second, true); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 183 | BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameABC); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 184 | // ['/', '/A', '/A/B/C'] |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 185 | BOOST_CHECK_EQUAL(fib.size(), 3); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 186 | |
| 187 | entry = fib.findLongestPrefixMatch(nameA); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 188 | BOOST_REQUIRE(static_cast<bool>(entry)); |
| 189 | BOOST_CHECK_EQUAL(entry->getPrefix(), nameA); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 190 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 191 | entry = fib.findLongestPrefixMatch(nameAB); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 192 | BOOST_REQUIRE(static_cast<bool>(entry)); |
| 193 | BOOST_CHECK_EQUAL(entry->getPrefix(), nameA); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 194 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 195 | entry = fib.findLongestPrefixMatch(nameABCD); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 196 | BOOST_REQUIRE(static_cast<bool>(entry)); |
| 197 | BOOST_CHECK_EQUAL(entry->getPrefix(), nameABC); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 198 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 199 | entry = fib.findLongestPrefixMatch(nameE); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 200 | BOOST_REQUIRE(static_cast<bool>(entry)); |
| 201 | BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 202 | } |
| 203 | |
Junxiao Shi | 4370fde | 2016-02-24 12:20:46 -0700 | [diff] [blame] | 204 | BOOST_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 | |
| 241 | BOOST_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 Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 262 | BOOST_AUTO_TEST_CASE(RemoveNextHopFromAllEntries) |
| 263 | { |
Junxiao Shi | 8c8d218 | 2014-01-30 22:33:00 -0700 | [diff] [blame] | 264 | shared_ptr<Face> face1 = make_shared<DummyFace>(); |
| 265 | shared_ptr<Face> face2 = make_shared<DummyFace>(); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 266 | Name nameEmpty("ndn:/"); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 267 | Name nameA("ndn:/A"); |
| 268 | Name nameB("ndn:/B"); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 269 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 270 | std::pair<shared_ptr<fib::Entry>, bool> insertRes; |
| 271 | shared_ptr<fib::Entry> entry; |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 272 | |
Haowei Yuan | f52dac7 | 2014-03-24 23:35:03 -0500 | [diff] [blame] | 273 | NameTree nameTree; |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 274 | Fib fib(nameTree); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 275 | // {} |
| 276 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 277 | insertRes = fib.insert(nameA); |
| 278 | insertRes.first->addNextHop(face1, 0); |
| 279 | insertRes.first->addNextHop(face2, 0); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 280 | // {'/A':[1,2]} |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 281 | |
| 282 | insertRes = fib.insert(nameB); |
| 283 | insertRes.first->addNextHop(face1, 0); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 284 | // {'/A':[1,2], '/B':[1]} |
| 285 | BOOST_CHECK_EQUAL(fib.size(), 2); |
| 286 | |
Alexander Afanasyev | b303324 | 2014-08-04 11:09:05 -0700 | [diff] [blame] | 287 | 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 Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 314 | fib.removeNextHopFromAllEntries(face1); |
Alexander Afanasyev | b303324 | 2014-08-04 11:09:05 -0700 | [diff] [blame] | 315 | // {'/A':[2], '/C':[2]} |
| 316 | BOOST_CHECK_EQUAL(fib.size(), 2); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 317 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 318 | entry = fib.findLongestPrefixMatch(nameA); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 319 | BOOST_CHECK_EQUAL(entry->getPrefix(), nameA); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 320 | const fib::NextHopList& nexthopsA = entry->getNextHops(); |
| 321 | BOOST_CHECK_EQUAL(nexthopsA.size(), 1); |
| 322 | BOOST_CHECK_EQUAL(nexthopsA.begin()->getFace(), face2); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 323 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 324 | entry = fib.findLongestPrefixMatch(nameB); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 325 | BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 326 | } |
| 327 | |
Junxiao Shi | 4b2e6cb | 2014-12-03 00:51:45 -0700 | [diff] [blame] | 328 | BOOST_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 DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 344 | void |
| 345 | validateFindExactMatch(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 | |
| 358 | void |
| 359 | validateNoExactMatch(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 | |
| 368 | BOOST_AUTO_TEST_CASE(FindExactMatch) |
| 369 | { |
Haowei Yuan | f52dac7 | 2014-03-24 23:35:03 -0500 | [diff] [blame] | 370 | NameTree nameTree; |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 371 | Fib fib(nameTree); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 372 | 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 Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 379 | validateNoExactMatch(fib, "/"); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 380 | |
| 381 | validateNoExactMatch(fib, "/does/not/exist"); |
| 382 | |
Haowei Yuan | f52dac7 | 2014-03-24 23:35:03 -0500 | [diff] [blame] | 383 | NameTree gapNameTree; |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 384 | Fib gapFib(nameTree); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 385 | fib.insert("/X"); |
| 386 | fib.insert("/X/Y/Z"); |
| 387 | |
| 388 | validateNoExactMatch(gapFib, "/X/Y"); |
| 389 | |
Haowei Yuan | f52dac7 | 2014-03-24 23:35:03 -0500 | [diff] [blame] | 390 | NameTree emptyNameTree; |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 391 | Fib emptyFib(emptyNameTree); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 392 | validateNoExactMatch(emptyFib, "/nothing/here"); |
| 393 | } |
| 394 | |
| 395 | void |
Junxiao Shi | ee5a444 | 2014-07-27 17:13:43 -0700 | [diff] [blame] | 396 | validateErase(Fib& fib, const Name& target) |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 397 | { |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 398 | fib.erase(target); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 399 | |
| 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 Shi | ee5a444 | 2014-07-27 17:13:43 -0700 | [diff] [blame] | 407 | BOOST_AUTO_TEST_CASE(Erase) |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 408 | { |
Haowei Yuan | f52dac7 | 2014-03-24 23:35:03 -0500 | [diff] [blame] | 409 | NameTree emptyNameTree; |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 410 | Fib emptyFib(emptyNameTree); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 411 | |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 412 | emptyFib.erase("/does/not/exist"); // crash test |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 413 | |
Junxiao Shi | ee5a444 | 2014-07-27 17:13:43 -0700 | [diff] [blame] | 414 | validateErase(emptyFib, "/"); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 415 | |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 416 | emptyFib.erase("/still/does/not/exist"); // crash test |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 417 | |
Haowei Yuan | f52dac7 | 2014-03-24 23:35:03 -0500 | [diff] [blame] | 418 | NameTree nameTree; |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 419 | Fib fib(nameTree); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 420 | fib.insert("/"); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 421 | 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 Shi | ee5a444 | 2014-07-27 17:13:43 -0700 | [diff] [blame] | 428 | validateErase(fib, "/A/B"); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 429 | validateFindExactMatch(fib, "/A"); |
| 430 | validateFindExactMatch(fib, "/A/B/C"); |
| 431 | validateFindExactMatch(fib, "/"); |
| 432 | |
Junxiao Shi | ee5a444 | 2014-07-27 17:13:43 -0700 | [diff] [blame] | 433 | validateErase(fib, "/A/B/C"); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 434 | validateFindExactMatch(fib, "/A"); |
| 435 | validateFindExactMatch(fib, "/"); |
| 436 | |
Junxiao Shi | ee5a444 | 2014-07-27 17:13:43 -0700 | [diff] [blame] | 437 | validateErase(fib, "/A"); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 438 | validateFindExactMatch(fib, "/"); |
| 439 | |
Junxiao Shi | ee5a444 | 2014-07-27 17:13:43 -0700 | [diff] [blame] | 440 | validateErase(fib, "/"); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 441 | validateNoExactMatch(fib, "/"); |
| 442 | |
Haowei Yuan | f52dac7 | 2014-03-24 23:35:03 -0500 | [diff] [blame] | 443 | NameTree gapNameTree; |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 444 | Fib gapFib(gapNameTree); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 445 | gapFib.insert("/X"); |
| 446 | gapFib.insert("/X/Y/Z"); |
| 447 | |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 448 | gapFib.erase("/X/Y"); //should do nothing |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 449 | validateFindExactMatch(gapFib, "/X"); |
| 450 | validateFindExactMatch(gapFib, "/X/Y/Z"); |
| 451 | } |
| 452 | |
Junxiao Shi | ee5a444 | 2014-07-27 17:13:43 -0700 | [diff] [blame] | 453 | BOOST_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 | |
HangZhang | 5d46942 | 2014-03-12 09:26:26 +0800 | [diff] [blame] | 464 | BOOST_AUTO_TEST_CASE(Iterator) |
| 465 | { |
Haowei Yuan | f52dac7 | 2014-03-24 23:35:03 -0500 | [diff] [blame] | 466 | NameTree nameTree; |
HangZhang | 5d46942 | 2014-03-12 09:26:26 +0800 | [diff] [blame] | 467 | 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 Shi | 4370fde | 2016-02-24 12:20:46 -0700 | [diff] [blame] | 484 | for (Fib::const_iterator it = fib.begin(); it != fib.end(); it++) { |
HangZhang | 5d46942 | 2014-03-12 09:26:26 +0800 | [diff] [blame] | 485 | 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 Shi | 4370fde | 2016-02-24 12:20:46 -0700 | [diff] [blame] | 493 | BOOST_AUTO_TEST_SUITE_END() // TestFib |
| 494 | BOOST_AUTO_TEST_SUITE_END() // Table |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 495 | |
Junxiao Shi | d9ee45c | 2014-02-27 15:38:11 -0700 | [diff] [blame] | 496 | } // namespace tests |
Alexander Afanasyev | 18bbf81 | 2014-01-29 01:40:23 -0800 | [diff] [blame] | 497 | } // namespace nfd |