Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 1 | /* -*- 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 Shi | d9ee45c | 2014-02-27 15:38:11 -0700 | [diff] [blame] | 8 | #include "tests/face/dummy-face.hpp" |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 9 | |
Junxiao Shi | d9ee45c | 2014-02-27 15:38:11 -0700 | [diff] [blame] | 10 | #include "tests/test-common.hpp" |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 11 | |
Alexander Afanasyev | 18bbf81 | 2014-01-29 01:40:23 -0800 | [diff] [blame] | 12 | namespace nfd { |
Junxiao Shi | d9ee45c | 2014-02-27 15:38:11 -0700 | [diff] [blame] | 13 | namespace tests { |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 14 | |
Junxiao Shi | d9ee45c | 2014-02-27 15:38:11 -0700 | [diff] [blame] | 15 | BOOST_FIXTURE_TEST_SUITE(TableFib, BaseFixture) |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 16 | |
| 17 | BOOST_AUTO_TEST_CASE(Entry) |
| 18 | { |
| 19 | Name prefix("ndn:/pxWhfFza"); |
Junxiao Shi | 8c8d218 | 2014-01-30 22:33:00 -0700 | [diff] [blame] | 20 | shared_ptr<Face> face1 = make_shared<DummyFace>(); |
| 21 | shared_ptr<Face> face2 = make_shared<DummyFace>(); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 22 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 23 | fib::Entry entry(prefix); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 24 | BOOST_CHECK_EQUAL(entry.getPrefix(), prefix); |
| 25 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 26 | const fib::NextHopList& nexthops1 = entry.getNextHops(); |
| 27 | // [] |
| 28 | BOOST_CHECK_EQUAL(nexthops1.size(), 0); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 29 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 30 | entry.addNextHop(face1, 20); |
| 31 | const fib::NextHopList& nexthops2 = entry.getNextHops(); |
| 32 | // [(face1,20)] |
| 33 | BOOST_CHECK_EQUAL(nexthops2.size(), 1); |
| 34 | BOOST_CHECK_EQUAL(nexthops2.begin()->getFace(), face1); |
| 35 | BOOST_CHECK_EQUAL(nexthops2.begin()->getCost(), 20); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 36 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 37 | entry.addNextHop(face1, 30); |
| 38 | const fib::NextHopList& nexthops3 = entry.getNextHops(); |
| 39 | // [(face1,30)] |
| 40 | BOOST_CHECK_EQUAL(nexthops3.size(), 1); |
| 41 | BOOST_CHECK_EQUAL(nexthops3.begin()->getFace(), face1); |
| 42 | BOOST_CHECK_EQUAL(nexthops3.begin()->getCost(), 30); |
| 43 | |
| 44 | entry.addNextHop(face2, 40); |
| 45 | const fib::NextHopList& nexthops4 = entry.getNextHops(); |
| 46 | // [(face1,30), (face2,40)] |
| 47 | BOOST_CHECK_EQUAL(nexthops4.size(), 2); |
| 48 | int i = -1; |
| 49 | for (fib::NextHopList::const_iterator it = nexthops4.begin(); |
| 50 | it != nexthops4.end(); ++it) { |
| 51 | ++i; |
| 52 | switch (i) { |
| 53 | case 0 : |
| 54 | BOOST_CHECK_EQUAL(it->getFace(), face1); |
| 55 | BOOST_CHECK_EQUAL(it->getCost(), 30); |
| 56 | break; |
| 57 | case 1 : |
| 58 | BOOST_CHECK_EQUAL(it->getFace(), face2); |
| 59 | BOOST_CHECK_EQUAL(it->getCost(), 40); |
| 60 | break; |
| 61 | } |
| 62 | } |
| 63 | |
| 64 | entry.addNextHop(face2, 10); |
| 65 | const fib::NextHopList& nexthops5 = entry.getNextHops(); |
| 66 | // [(face2,10), (face1,30)] |
| 67 | BOOST_CHECK_EQUAL(nexthops5.size(), 2); |
| 68 | i = -1; |
| 69 | for (fib::NextHopList::const_iterator it = nexthops5.begin(); |
| 70 | it != nexthops5.end(); ++it) { |
| 71 | ++i; |
| 72 | switch (i) { |
| 73 | case 0 : |
| 74 | BOOST_CHECK_EQUAL(it->getFace(), face2); |
| 75 | BOOST_CHECK_EQUAL(it->getCost(), 10); |
| 76 | break; |
| 77 | case 1 : |
| 78 | BOOST_CHECK_EQUAL(it->getFace(), face1); |
| 79 | BOOST_CHECK_EQUAL(it->getCost(), 30); |
| 80 | break; |
| 81 | } |
| 82 | } |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 83 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 84 | entry.removeNextHop(face1); |
| 85 | const fib::NextHopList& nexthops6 = entry.getNextHops(); |
| 86 | // [(face2,10)] |
| 87 | BOOST_CHECK_EQUAL(nexthops6.size(), 1); |
| 88 | BOOST_CHECK_EQUAL(nexthops6.begin()->getFace(), face2); |
| 89 | BOOST_CHECK_EQUAL(nexthops6.begin()->getCost(), 10); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 90 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 91 | entry.removeNextHop(face1); |
| 92 | const fib::NextHopList& nexthops7 = entry.getNextHops(); |
| 93 | // [(face2,10)] |
| 94 | BOOST_CHECK_EQUAL(nexthops7.size(), 1); |
| 95 | BOOST_CHECK_EQUAL(nexthops7.begin()->getFace(), face2); |
| 96 | BOOST_CHECK_EQUAL(nexthops7.begin()->getCost(), 10); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 97 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 98 | entry.removeNextHop(face2); |
| 99 | const fib::NextHopList& nexthops8 = entry.getNextHops(); |
| 100 | // [] |
| 101 | BOOST_CHECK_EQUAL(nexthops8.size(), 0); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 102 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 103 | entry.removeNextHop(face2); |
| 104 | const fib::NextHopList& nexthops9 = entry.getNextHops(); |
| 105 | // [] |
| 106 | BOOST_CHECK_EQUAL(nexthops9.size(), 0); |
| 107 | } |
| 108 | |
| 109 | BOOST_AUTO_TEST_CASE(Insert_LongestPrefixMatch) |
| 110 | { |
| 111 | Name nameEmpty; |
| 112 | Name nameA ("ndn:/A"); |
| 113 | Name nameAB ("ndn:/A/B"); |
| 114 | Name nameABC ("ndn:/A/B/C"); |
| 115 | Name nameABCD("ndn:/A/B/C/D"); |
| 116 | Name nameE ("ndn:/E"); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 117 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 118 | std::pair<shared_ptr<fib::Entry>, bool> insertRes; |
| 119 | shared_ptr<fib::Entry> entry; |
| 120 | |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 121 | NameTree nameTree(1024); |
| 122 | Fib fib(nameTree); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 123 | // [] |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 124 | BOOST_CHECK_EQUAL(fib.size(), 0); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 125 | |
| 126 | entry = fib.findLongestPrefixMatch(nameA); |
| 127 | BOOST_REQUIRE(static_cast<bool>(entry)); // the empty entry |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 128 | |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 129 | insertRes = fib.insert(nameEmpty); |
| 130 | BOOST_CHECK_EQUAL(insertRes.second, true); |
| 131 | BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameEmpty); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 132 | // ['/'] |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 133 | BOOST_CHECK_EQUAL(fib.size(), 1); |
| 134 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 135 | entry = fib.findLongestPrefixMatch(nameA); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 136 | BOOST_REQUIRE(static_cast<bool>(entry)); |
| 137 | BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 138 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 139 | insertRes = fib.insert(nameA); |
| 140 | BOOST_CHECK_EQUAL(insertRes.second, true); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 141 | BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameA); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 142 | // ['/', '/A'] |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 143 | BOOST_CHECK_EQUAL(fib.size(), 2); |
| 144 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 145 | insertRes = fib.insert(nameA); |
| 146 | BOOST_CHECK_EQUAL(insertRes.second, false); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 147 | BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameA); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 148 | // ['/', '/A'] |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 149 | BOOST_CHECK_EQUAL(fib.size(), 2); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 150 | |
| 151 | entry = fib.findLongestPrefixMatch(nameA); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 152 | BOOST_REQUIRE(static_cast<bool>(entry)); |
| 153 | BOOST_CHECK_EQUAL(entry->getPrefix(), nameA); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 154 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 155 | entry = fib.findLongestPrefixMatch(nameABCD); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 156 | BOOST_REQUIRE(static_cast<bool>(entry)); |
| 157 | BOOST_CHECK_EQUAL(entry->getPrefix(), nameA); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 158 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 159 | insertRes = fib.insert(nameABC); |
| 160 | BOOST_CHECK_EQUAL(insertRes.second, true); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 161 | BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameABC); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 162 | // ['/', '/A', '/A/B/C'] |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 163 | BOOST_CHECK_EQUAL(fib.size(), 3); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 164 | |
| 165 | entry = fib.findLongestPrefixMatch(nameA); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 166 | BOOST_REQUIRE(static_cast<bool>(entry)); |
| 167 | BOOST_CHECK_EQUAL(entry->getPrefix(), nameA); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 168 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 169 | entry = fib.findLongestPrefixMatch(nameAB); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 170 | BOOST_REQUIRE(static_cast<bool>(entry)); |
| 171 | BOOST_CHECK_EQUAL(entry->getPrefix(), nameA); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 172 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 173 | entry = fib.findLongestPrefixMatch(nameABCD); |
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(), nameABC); |
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(nameE); |
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(), nameEmpty); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 180 | } |
| 181 | |
| 182 | BOOST_AUTO_TEST_CASE(RemoveNextHopFromAllEntries) |
| 183 | { |
Junxiao Shi | 8c8d218 | 2014-01-30 22:33:00 -0700 | [diff] [blame] | 184 | shared_ptr<Face> face1 = make_shared<DummyFace>(); |
| 185 | shared_ptr<Face> face2 = make_shared<DummyFace>(); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 186 | Name nameEmpty("ndn:/"); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 187 | Name nameA("ndn:/A"); |
| 188 | Name nameB("ndn:/B"); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 189 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 190 | std::pair<shared_ptr<fib::Entry>, bool> insertRes; |
| 191 | shared_ptr<fib::Entry> entry; |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 192 | |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 193 | NameTree nameTree(1024); |
| 194 | Fib fib(nameTree); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 195 | // {} |
| 196 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 197 | insertRes = fib.insert(nameA); |
| 198 | insertRes.first->addNextHop(face1, 0); |
| 199 | insertRes.first->addNextHop(face2, 0); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 200 | // {'/A':[1,2]} |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 201 | |
| 202 | insertRes = fib.insert(nameB); |
| 203 | insertRes.first->addNextHop(face1, 0); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 204 | // {'/A':[1,2], '/B':[1]} |
| 205 | BOOST_CHECK_EQUAL(fib.size(), 2); |
| 206 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 207 | fib.removeNextHopFromAllEntries(face1); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 208 | // {'/A':[2]} |
| 209 | BOOST_CHECK_EQUAL(fib.size(), 1); |
| 210 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 211 | entry = fib.findLongestPrefixMatch(nameA); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 212 | BOOST_CHECK_EQUAL(entry->getPrefix(), nameA); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 213 | const fib::NextHopList& nexthopsA = entry->getNextHops(); |
| 214 | BOOST_CHECK_EQUAL(nexthopsA.size(), 1); |
| 215 | BOOST_CHECK_EQUAL(nexthopsA.begin()->getFace(), face2); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 216 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 217 | entry = fib.findLongestPrefixMatch(nameB); |
Junxiao Shi | efceadc | 2014-03-09 18:52:57 -0700 | [diff] [blame] | 218 | BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty); |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 219 | } |
| 220 | |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 221 | void |
| 222 | validateFindExactMatch(const Fib& fib, const Name& target) |
| 223 | { |
| 224 | shared_ptr<fib::Entry> entry = fib.findExactMatch(target); |
| 225 | if (static_cast<bool>(entry)) |
| 226 | { |
| 227 | BOOST_CHECK_EQUAL(entry->getPrefix(), target); |
| 228 | } |
| 229 | else |
| 230 | { |
| 231 | BOOST_FAIL("No entry found for " << target); |
| 232 | } |
| 233 | } |
| 234 | |
| 235 | void |
| 236 | validateNoExactMatch(const Fib& fib, const Name& target) |
| 237 | { |
| 238 | shared_ptr<fib::Entry> entry = fib.findExactMatch(target); |
| 239 | if (static_cast<bool>(entry)) |
| 240 | { |
| 241 | BOOST_FAIL("Found unexpected entry for " << target); |
| 242 | } |
| 243 | } |
| 244 | |
| 245 | BOOST_AUTO_TEST_CASE(FindExactMatch) |
| 246 | { |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 247 | NameTree nameTree(1024); |
| 248 | Fib fib(nameTree); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 249 | fib.insert("/A"); |
| 250 | fib.insert("/A/B"); |
| 251 | fib.insert("/A/B/C"); |
| 252 | |
| 253 | validateFindExactMatch(fib, "/A"); |
| 254 | validateFindExactMatch(fib, "/A/B"); |
| 255 | validateFindExactMatch(fib, "/A/B/C"); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 256 | validateNoExactMatch(fib, "/"); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 257 | |
| 258 | validateNoExactMatch(fib, "/does/not/exist"); |
| 259 | |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 260 | NameTree gapNameTree(1024); |
| 261 | Fib gapFib(nameTree); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 262 | fib.insert("/X"); |
| 263 | fib.insert("/X/Y/Z"); |
| 264 | |
| 265 | validateNoExactMatch(gapFib, "/X/Y"); |
| 266 | |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 267 | NameTree emptyNameTree(1024); |
| 268 | Fib emptyFib(emptyNameTree); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 269 | validateNoExactMatch(emptyFib, "/nothing/here"); |
| 270 | } |
| 271 | |
| 272 | void |
| 273 | validateRemove(Fib& fib, const Name& target) |
| 274 | { |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 275 | fib.erase(target); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 276 | |
| 277 | shared_ptr<fib::Entry> entry = fib.findExactMatch(target); |
| 278 | if (static_cast<bool>(entry)) |
| 279 | { |
| 280 | BOOST_FAIL("Found \"removed\" entry for " << target); |
| 281 | } |
| 282 | } |
| 283 | |
| 284 | BOOST_AUTO_TEST_CASE(Remove) |
| 285 | { |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 286 | NameTree emptyNameTree(1024); |
| 287 | Fib emptyFib(emptyNameTree); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 288 | |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 289 | emptyFib.erase("/does/not/exist"); // crash test |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 290 | |
| 291 | validateRemove(emptyFib, "/"); |
| 292 | |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 293 | emptyFib.erase("/still/does/not/exist"); // crash test |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 294 | |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 295 | NameTree nameTree(1024); |
| 296 | Fib fib(nameTree); |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 297 | fib.insert("/"); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 298 | fib.insert("/A"); |
| 299 | fib.insert("/A/B"); |
| 300 | fib.insert("/A/B/C"); |
| 301 | |
| 302 | // check if we remove the right thing and leave |
| 303 | // everything else alone |
| 304 | |
| 305 | validateRemove(fib, "/A/B"); |
| 306 | validateFindExactMatch(fib, "/A"); |
| 307 | validateFindExactMatch(fib, "/A/B/C"); |
| 308 | validateFindExactMatch(fib, "/"); |
| 309 | |
| 310 | validateRemove(fib, "/A/B/C"); |
| 311 | validateFindExactMatch(fib, "/A"); |
| 312 | validateFindExactMatch(fib, "/"); |
| 313 | |
| 314 | validateRemove(fib, "/A"); |
| 315 | validateFindExactMatch(fib, "/"); |
| 316 | |
Junxiao Shi | 4063184 | 2014-03-01 13:52:37 -0700 | [diff] [blame] | 317 | validateRemove(fib, "/"); |
| 318 | validateNoExactMatch(fib, "/"); |
| 319 | |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 320 | NameTree gapNameTree(1024); |
| 321 | Fib gapFib(gapNameTree); |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 322 | gapFib.insert("/X"); |
| 323 | gapFib.insert("/X/Y/Z"); |
| 324 | |
HangZhang | ad4afd1 | 2014-03-01 11:03:08 +0800 | [diff] [blame] | 325 | gapFib.erase("/X/Y"); //should do nothing |
Steve DiBenedetto | d5f8793 | 2014-02-05 15:11:39 -0700 | [diff] [blame] | 326 | validateFindExactMatch(gapFib, "/X"); |
| 327 | validateFindExactMatch(gapFib, "/X/Y/Z"); |
| 328 | } |
| 329 | |
HangZhang | 5d46942 | 2014-03-12 09:26:26 +0800 | [diff] [blame] | 330 | BOOST_AUTO_TEST_CASE(Iterator) |
| 331 | { |
| 332 | NameTree nameTree(1024); |
| 333 | Fib fib(nameTree); |
| 334 | Name nameA("/A"); |
| 335 | Name nameAB("/A/B"); |
| 336 | Name nameABC("/A/B/C"); |
| 337 | Name nameRoot("/"); |
| 338 | |
| 339 | fib.insert(nameA); |
| 340 | fib.insert(nameAB); |
| 341 | fib.insert(nameABC); |
| 342 | fib.insert(nameRoot); |
| 343 | |
| 344 | std::set<Name> expected; |
| 345 | expected.insert(nameA); |
| 346 | expected.insert(nameAB); |
| 347 | expected.insert(nameABC); |
| 348 | expected.insert(nameRoot); |
| 349 | |
| 350 | for (Fib::const_iterator it = fib.begin(); it != fib.end(); it++) |
| 351 | { |
| 352 | bool isInSet = expected.find(it->getPrefix()) != expected.end(); |
| 353 | BOOST_CHECK(isInSet); |
| 354 | expected.erase(it->getPrefix()); |
| 355 | } |
| 356 | |
| 357 | BOOST_CHECK_EQUAL(expected.size(), 0); |
| 358 | } |
| 359 | |
Junxiao Shi | c1e1236 | 2014-01-24 20:03:26 -0700 | [diff] [blame] | 360 | BOOST_AUTO_TEST_SUITE_END() |
| 361 | |
Junxiao Shi | d9ee45c | 2014-02-27 15:38:11 -0700 | [diff] [blame] | 362 | } // namespace tests |
Alexander Afanasyev | 18bbf81 | 2014-01-29 01:40:23 -0800 | [diff] [blame] | 363 | } // namespace nfd |