src: Reorganizing source code in preparation to merge NRD code
Note that as of this commit, there are several changes in location of
compiled binaries in `build/` folder:
* `nfd` has been moved to `build/bin/nfd`
* `unit-tests` has been split into `unit-tests-core` and `unit-tests-daemon`
Change-Id: I2c830c117879edbaa5457d6423c13f0273285919
Refs: #1486
diff --git a/tests/daemon/table/cs.cpp b/tests/daemon/table/cs.cpp
new file mode 100644
index 0000000..cdcc0db
--- /dev/null
+++ b/tests/daemon/table/cs.cpp
@@ -0,0 +1,919 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014 Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ *
+ * \author Ilya Moiseenko <iliamo@ucla.edu>
+ **/
+
+#include "table/cs.hpp"
+#include "table/cs-entry.hpp"
+
+#include "tests/test-common.hpp"
+
+namespace nfd {
+namespace tests {
+
+class CsAccessor : public Cs
+{
+public:
+ bool
+ evictItem_accessor()
+ {
+ return evictItem();
+ }
+};
+
+BOOST_FIXTURE_TEST_SUITE(TableCs, BaseFixture)
+
+BOOST_AUTO_TEST_CASE(Insertion)
+{
+ Cs cs;
+
+ BOOST_CHECK_EQUAL(cs.insert(*makeData("/insertion")), true);
+}
+
+BOOST_AUTO_TEST_CASE(Insertion2)
+{
+ Cs cs;
+
+ cs.insert(*makeData("/a"));
+ cs.insert(*makeData("/b"));
+ cs.insert(*makeData("/c"));
+ cs.insert(*makeData("/d"));
+
+ BOOST_CHECK_EQUAL(cs.size(), 4);
+}
+
+
+BOOST_AUTO_TEST_CASE(DuplicateInsertion)
+{
+ Cs cs;
+
+ shared_ptr<Data> data0 = makeData("/insert/smth");
+ BOOST_CHECK_EQUAL(cs.insert(*data0), true);
+
+ shared_ptr<Data> data = makeData("/insert/duplicate");
+ BOOST_CHECK_EQUAL(cs.insert(*data), true);
+
+ cs.insert(*data);
+ BOOST_CHECK_EQUAL(cs.size(), 2);
+}
+
+
+BOOST_AUTO_TEST_CASE(DuplicateInsertion2)
+{
+ Cs cs;
+
+ shared_ptr<Data> data = makeData("/insert/duplicate");
+ BOOST_CHECK_EQUAL(cs.insert(*data), true);
+
+ cs.insert(*data);
+ BOOST_CHECK_EQUAL(cs.size(), 1);
+
+ shared_ptr<Data> data2 = makeData("/insert/original");
+ BOOST_CHECK_EQUAL(cs.insert(*data2), true);
+ BOOST_CHECK_EQUAL(cs.size(), 2);
+}
+
+BOOST_AUTO_TEST_CASE(InsertAndFind)
+{
+ Cs cs;
+
+ Name name("/insert/and/find");
+
+ shared_ptr<Data> data = makeData(name);
+ BOOST_CHECK_EQUAL(cs.insert(*data), true);
+
+ shared_ptr<Interest> interest = make_shared<Interest>(name);
+
+ const Data* found = cs.find(*interest);
+
+ BOOST_REQUIRE(found != 0);
+ BOOST_CHECK_EQUAL(data->getName(), found->getName());
+}
+
+BOOST_AUTO_TEST_CASE(InsertAndNotFind)
+{
+ Cs cs;
+
+ Name name("/insert/and/find");
+ shared_ptr<Data> data = makeData(name);
+ BOOST_CHECK_EQUAL(cs.insert(*data), true);
+
+ Name name2("/not/find");
+ shared_ptr<Interest> interest = make_shared<Interest>(name2);
+
+ const Data* found = cs.find(*interest);
+
+ BOOST_CHECK_EQUAL(found, static_cast<const Data*>(0));
+}
+
+
+BOOST_AUTO_TEST_CASE(InsertAndErase)
+{
+ CsAccessor cs;
+
+ shared_ptr<Data> data = makeData("/insertandelete");
+ cs.insert(*data);
+ BOOST_CHECK_EQUAL(cs.size(), 1);
+
+ cs.evictItem_accessor();
+ BOOST_CHECK_EQUAL(cs.size(), 0);
+}
+
+BOOST_AUTO_TEST_CASE(StalenessQueue)
+{
+ CsAccessor cs;
+
+ Name name2("/insert/fresh");
+ shared_ptr<Data> data2 = makeData(name2);
+ data2->setFreshnessPeriod(time::milliseconds(5000));
+ cs.insert(*data2);
+
+ Name name("/insert/expire");
+ shared_ptr<Data> data = makeData(name);
+ data->setFreshnessPeriod(time::milliseconds(500));
+ cs.insert(*data);
+
+ BOOST_CHECK_EQUAL(cs.size(), 2);
+
+ sleep(3);
+
+ cs.evictItem_accessor();
+ BOOST_CHECK_EQUAL(cs.size(), 1);
+
+ shared_ptr<Interest> interest = make_shared<Interest>(name2);
+ const Data* found = cs.find(*interest);
+ BOOST_REQUIRE(found != 0);
+ BOOST_CHECK_EQUAL(found->getName(), name2);
+}
+
+//even max size
+BOOST_AUTO_TEST_CASE(ReplacementEvenSize)
+{
+ Cs cs(4);
+
+ shared_ptr<Data> data = makeData("/a");
+ cs.insert(*data);
+
+ shared_ptr<Data> data2 = makeData("/b");
+ cs.insert(*data2);
+
+ shared_ptr<Data> data3 = makeData("/c");
+ cs.insert(*data3);
+
+ shared_ptr<Data> data4 = makeData("/d");
+ cs.insert(*data4);
+
+ shared_ptr<Data> data5 = makeData("/e");
+ cs.insert(*data5);
+
+ BOOST_CHECK_EQUAL(cs.size(), 4);
+}
+
+//odd max size
+BOOST_AUTO_TEST_CASE(Replacement2)
+{
+ Cs cs(3);
+
+ shared_ptr<Data> data = makeData("/a");
+ cs.insert(*data);
+
+ shared_ptr<Data> data2 = makeData("/b");
+ cs.insert(*data2);
+
+ shared_ptr<Data> data3 = makeData("/c");
+ cs.insert(*data3);
+
+ shared_ptr<Data> data4 = makeData("/d");
+ cs.insert(*data4);
+
+ BOOST_CHECK_EQUAL(cs.size(), 3);
+}
+
+BOOST_AUTO_TEST_CASE(InsertAndEraseByName)
+{
+ CsAccessor cs;
+
+ Name name("/insertandremovebyname");
+ shared_ptr<Data> data = makeData(name);
+ cs.insert(*data);
+
+ ndn::ConstBufferPtr digest1 = ndn::crypto::sha256(data->wireEncode().wire(),
+ data->wireEncode().size());
+
+ shared_ptr<Data> data2 = makeData("/a");
+ cs.insert(*data2);
+
+ shared_ptr<Data> data3 = makeData("/z");
+ cs.insert(*data3);
+
+ BOOST_CHECK_EQUAL(cs.size(), 3);
+
+ name.append(digest1->buf(), digest1->size());
+ cs.erase(name);
+ BOOST_CHECK_EQUAL(cs.size(), 2);
+}
+
+BOOST_AUTO_TEST_CASE(DigestCalculation)
+{
+ shared_ptr<Data> data = makeData("/digest/compute");
+
+ ndn::ConstBufferPtr digest1 = ndn::crypto::sha256(data->wireEncode().wire(),
+ data->wireEncode().size());
+ BOOST_CHECK_EQUAL(digest1->size(), 32);
+
+ cs::Entry* entry = new cs::Entry();
+ entry->setData(*data, false);
+
+ BOOST_CHECK_EQUAL_COLLECTIONS(digest1->begin(), digest1->end(),
+ entry->getDigest()->begin(), entry->getDigest()->end());
+}
+
+BOOST_AUTO_TEST_CASE(InsertCanonical)
+{
+ Cs cs;
+
+ shared_ptr<Data> data = makeData("/a");
+ cs.insert(*data);
+
+ shared_ptr<Data> data2 = makeData("/b");
+ cs.insert(*data2);
+
+ shared_ptr<Data> data3 = makeData("/c");
+ cs.insert(*data3);
+
+ shared_ptr<Data> data4 = makeData("/d");
+ cs.insert(*data4);
+
+ shared_ptr<Data> data5 = makeData("/c/c/1/2/3/4/5/6");
+ cs.insert(*data5);
+
+ shared_ptr<Data> data6 = makeData("/c/c/1/2/3");
+ cs.insert(*data6);
+
+ shared_ptr<Data> data7 = makeData("/c/c/1");
+ cs.insert(*data7);
+}
+
+BOOST_AUTO_TEST_CASE(EraseCanonical)
+{
+ Cs cs;
+
+ shared_ptr<Data> data = makeData("/a");
+ cs.insert(*data);
+
+ shared_ptr<Data> data2 = makeData("/b");
+ cs.insert(*data2);
+
+ shared_ptr<Data> data3 = makeData("/c");
+ cs.insert(*data3);
+
+ shared_ptr<Data> data4 = makeData("/d");
+ cs.insert(*data4);
+
+ shared_ptr<Data> data5 = makeData("/c/c/1/2/3/4/5/6");
+ cs.insert(*data5);
+
+ shared_ptr<Data> data6 = makeData("/c/c/1/2/3");
+ cs.insert(*data6);
+
+ shared_ptr<Data> data7 = makeData("/c/c/1");
+ cs.insert(*data7);
+
+ ndn::ConstBufferPtr digest1 = ndn::crypto::sha256(data->wireEncode().wire(),
+ data->wireEncode().size());
+
+ Name name("/a");
+ name.append(digest1->buf(), digest1->size());
+ cs.erase(name);
+ BOOST_CHECK_EQUAL(cs.size(), 6);
+}
+
+BOOST_AUTO_TEST_CASE(ImplicitDigestSelector)
+{
+ CsAccessor cs;
+
+ Name name("/digest/works");
+ shared_ptr<Data> data = makeData(name);
+ cs.insert(*data);
+
+ shared_ptr<Data> data2 = makeData("/a");
+ cs.insert(*data2);
+
+ shared_ptr<Data> data3 = makeData("/z/z/z");
+ cs.insert(*data3);
+
+ ndn::ConstBufferPtr digest1 = ndn::crypto::sha256(data->wireEncode().wire(),
+ data->wireEncode().size());
+ uint8_t digest2[32] = {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1};
+
+ shared_ptr<Interest> interest = make_shared<Interest>();
+ interest->setName(Name(name).append(digest1->buf(), digest1->size()));
+ interest->setMinSuffixComponents(0);
+ interest->setMaxSuffixComponents(0);
+
+ const Data* found = cs.find(*interest);
+ BOOST_CHECK_NE(found, static_cast<const Data*>(0));
+ BOOST_CHECK_EQUAL(found->getName(), name);
+
+ shared_ptr<Interest> interest2 = make_shared<Interest>();
+ interest2->setName(Name(name).append(digest2, 32));
+ interest2->setMinSuffixComponents(0);
+ interest2->setMaxSuffixComponents(0);
+
+ const Data* notfound = cs.find(*interest2);
+ BOOST_CHECK_EQUAL(notfound, static_cast<const Data*>(0));
+}
+
+BOOST_AUTO_TEST_CASE(ChildSelector)
+{
+ Cs cs;
+
+ shared_ptr<Data> data = makeData("/a");
+ cs.insert(*data);
+
+ shared_ptr<Data> data2 = makeData("/b");
+ cs.insert(*data2);
+
+ shared_ptr<Data> data4 = makeData("/d");
+ cs.insert(*data4);
+
+ shared_ptr<Data> data5 = makeData("/c/c");
+ cs.insert(*data5);
+
+ shared_ptr<Data> data6 = makeData("/c/f");
+ cs.insert(*data6);
+
+ shared_ptr<Data> data7 = makeData("/c/n");
+ cs.insert(*data7);
+
+ shared_ptr<Interest> interest = make_shared<Interest>("/c");
+ interest->setChildSelector(1);
+
+ const Data* found = cs.find(*interest);
+ BOOST_CHECK_EQUAL(found->getName(), "/c/n");
+
+ shared_ptr<Interest> interest2 = make_shared<Interest>("/c");
+ interest2->setChildSelector(0);
+
+ const Data* found2 = cs.find(*interest2);
+ BOOST_CHECK_EQUAL(found2->getName(), "/c/c");
+}
+
+BOOST_AUTO_TEST_CASE(ChildSelector2)
+{
+ Cs cs;
+
+ shared_ptr<Data> data = makeData("/a/b/1");
+ cs.insert(*data);
+
+ shared_ptr<Data> data2 = makeData("/a/b/2");
+ cs.insert(*data2);
+
+ shared_ptr<Data> data3 = makeData("/a/z/1");
+ cs.insert(*data3);
+
+ shared_ptr<Data> data4 = makeData("/a/z/2");
+ cs.insert(*data4);
+
+ shared_ptr<Interest> interest = make_shared<Interest>("/a");
+ interest->setChildSelector(1);
+
+ const Data* found = cs.find(*interest);
+ BOOST_CHECK_EQUAL(found->getName(), "/a/z/1");
+}
+
+BOOST_AUTO_TEST_CASE(MustBeFreshSelector)
+{
+ Cs cs;
+
+ Name name("/insert/nonfresh");
+ shared_ptr<Data> data = makeData(name);
+ data->setFreshnessPeriod(time::milliseconds(500));
+ cs.insert(*data);
+
+ sleep(1);
+
+ shared_ptr<Interest> interest = make_shared<Interest>(name);
+ interest->setMustBeFresh(true);
+
+ const Data* found = cs.find(*interest);
+ BOOST_CHECK_EQUAL(found, static_cast<const Data*>(0));
+}
+
+BOOST_AUTO_TEST_CASE(PublisherKeySelector)
+{
+ Cs cs;
+
+ Name name("/insert/withkey");
+ shared_ptr<Data> data = makeData(name);
+ cs.insert(*data);
+
+ shared_ptr<Interest> interest = make_shared<Interest>(name);
+ Name keyName("/somewhere/key");
+
+ ndn::KeyLocator locator(keyName);
+ interest->setPublisherPublicKeyLocator(locator);
+
+ const Data* found = cs.find(*interest);
+ BOOST_CHECK_EQUAL(found, static_cast<const Data*>(0));
+}
+
+BOOST_AUTO_TEST_CASE(PublisherKeySelector2)
+{
+ Cs cs;
+ Name name("/insert/withkey");
+ shared_ptr<Data> data = makeData(name);
+ cs.insert(*data);
+
+ Name name2("/insert/withkey2");
+ shared_ptr<Data> data2 = make_shared<Data>(name2);
+
+ Name keyName("/somewhere/key");
+ const ndn::KeyLocator locator(keyName);
+
+ ndn::SignatureSha256WithRsa fakeSignature;
+ fakeSignature.setValue(ndn::dataBlock(tlv::SignatureValue,
+ reinterpret_cast<const uint8_t*>(0), 0));
+
+ fakeSignature.setKeyLocator(locator);
+ data2->setSignature(fakeSignature);
+
+ cs.insert(*data2);
+
+ shared_ptr<Interest> interest = make_shared<Interest>(name2);
+ interest->setPublisherPublicKeyLocator(locator);
+
+ const Data* found = cs.find(*interest);
+ BOOST_CHECK_NE(found, static_cast<const Data*>(0));
+ BOOST_CHECK_EQUAL(found->getName(), data2->getName());
+}
+
+
+BOOST_AUTO_TEST_CASE(MinMaxComponentsSelector)
+{
+ Cs cs;
+
+ shared_ptr<Data> data = makeData("/a");
+ cs.insert(*data);
+
+ shared_ptr<Data> data2 = makeData("/b");
+ cs.insert(*data2);
+
+ shared_ptr<Data> data4 = makeData("/d");
+ cs.insert(*data4);
+
+ shared_ptr<Data> data5 = makeData("/c/c/1/2/3/4/5/6");
+ cs.insert(*data5);
+
+ shared_ptr<Data> data6 = makeData("/c/c/6/7/8/9");
+ cs.insert(*data6);
+
+ shared_ptr<Data> data7 = makeData("/c/c/1/2/3");
+ cs.insert(*data7);
+
+ shared_ptr<Data> data8 = makeData("/c/c/1");
+ cs.insert(*data8);
+
+ shared_ptr<Interest> interest = make_shared<Interest>("/c/c");
+ interest->setMinSuffixComponents(3);
+ interest->setChildSelector(0);
+
+ const Data* found = cs.find(*interest);
+ BOOST_CHECK_EQUAL(found->getName(), "/c/c/1/2/3/4/5/6");
+
+ shared_ptr<Interest> interest2 = make_shared<Interest>("/c/c");
+ interest2->setMinSuffixComponents(4);
+ interest2->setChildSelector(1);
+
+ const Data* found2 = cs.find(*interest2);
+ BOOST_CHECK_EQUAL(found2->getName(), "/c/c/6/7/8/9");
+
+ shared_ptr<Interest> interest3 = make_shared<Interest>("/c/c");
+ interest3->setMaxSuffixComponents(2);
+ interest3->setChildSelector(1);
+
+ const Data* found3 = cs.find(*interest3);
+ BOOST_CHECK_EQUAL(found3->getName(), "/c/c/1");
+}
+
+BOOST_AUTO_TEST_CASE(ExcludeSelector)
+{
+ Cs cs;
+
+ shared_ptr<Data> data = makeData("/a");
+ cs.insert(*data);
+
+ shared_ptr<Data> data2 = makeData("/b");
+ cs.insert(*data2);
+
+ shared_ptr<Data> data3 = makeData("/c/a");
+ cs.insert(*data3);
+
+ shared_ptr<Data> data4 = makeData("/d");
+ cs.insert(*data4);
+
+ shared_ptr<Data> data5 = makeData("/c/c");
+ cs.insert(*data5);
+
+ shared_ptr<Data> data6 = makeData("/c/f");
+ cs.insert(*data6);
+
+ shared_ptr<Data> data7 = makeData("/c/n");
+ cs.insert(*data7);
+
+ shared_ptr<Interest> interest = make_shared<Interest>("/c");
+ interest->setChildSelector(1);
+ Exclude e;
+ e.excludeOne (Name::Component("n"));
+ interest->setExclude(e);
+
+ const Data* found = cs.find(*interest);
+ BOOST_CHECK_EQUAL(found->getName(), "/c/f");
+
+ shared_ptr<Interest> interest2 = make_shared<Interest>("/c");
+ interest2->setChildSelector(0);
+
+ Exclude e2;
+ e2.excludeOne (Name::Component("a"));
+ interest2->setExclude(e2);
+
+ const Data* found2 = cs.find(*interest2);
+ BOOST_CHECK_EQUAL(found2->getName(), "/c/c");
+
+ shared_ptr<Interest> interest3 = make_shared<Interest>("/c");
+ interest3->setChildSelector(0);
+
+ Exclude e3;
+ e3.excludeOne (Name::Component("c"));
+ interest3->setExclude(e3);
+
+ const Data* found3 = cs.find(*interest3);
+ BOOST_CHECK_EQUAL(found3->getName(), "/c/a");
+}
+
+//
+
+class FindFixture : protected BaseFixture
+{
+protected:
+ void
+ insert(uint32_t id, const Name& name)
+ {
+ shared_ptr<Data> data = makeData(name);
+ data->setFreshnessPeriod(time::milliseconds(99999));
+ data->setContent(reinterpret_cast<const uint8_t*>(&id), sizeof(id));
+
+ m_cs.insert(*data);
+ }
+
+ Interest&
+ startInterest(const Name& name)
+ {
+ m_interest = make_shared<Interest>(name);
+ return *m_interest;
+ }
+
+ uint32_t
+ find()
+ {
+ const Data* found = m_cs.find(*m_interest);
+ if (found == 0) {
+ return 0;
+ }
+ const Block& content = found->getContent();
+ if (content.value_size() != sizeof(uint32_t)) {
+ return 0;
+ }
+ return *reinterpret_cast<const uint32_t*>(content.value());
+ }
+
+protected:
+ Cs m_cs;
+ shared_ptr<Interest> m_interest;
+};
+
+BOOST_FIXTURE_TEST_SUITE(Find, FindFixture)
+
+BOOST_AUTO_TEST_CASE(EmptyDataName)
+{
+ insert(1, "ndn:/");
+
+ startInterest("ndn:/");
+ BOOST_CHECK_EQUAL(find(), 1);
+}
+
+BOOST_AUTO_TEST_CASE(EmptyInterestName)
+{
+ insert(1, "ndn:/A");
+
+ startInterest("ndn:/");
+ BOOST_CHECK_EQUAL(find(), 1);
+}
+
+BOOST_AUTO_TEST_CASE(Leftmost)
+{
+ insert(1, "ndn:/A");
+ insert(2, "ndn:/B/p/1");
+ insert(3, "ndn:/B/p/2");
+ insert(4, "ndn:/B/q/1");
+ insert(5, "ndn:/B/q/2");
+ insert(6, "ndn:/C");
+
+ startInterest("ndn:/B");
+ BOOST_CHECK_EQUAL(find(), 2);
+}
+
+BOOST_AUTO_TEST_CASE(Rightmost)
+{
+ insert(1, "ndn:/A");
+ insert(2, "ndn:/B/p/1");
+ insert(3, "ndn:/B/p/2");
+ insert(4, "ndn:/B/q/1");
+ insert(5, "ndn:/B/q/2");
+ insert(6, "ndn:/C");
+
+ startInterest("ndn:/B")
+ .setChildSelector(1);
+ BOOST_CHECK_EQUAL(find(), 4);
+}
+
+BOOST_AUTO_TEST_CASE(Leftmost_ExactName1)
+{
+ insert(1, "ndn:/");
+ insert(2, "ndn:/A/B");
+ insert(3, "ndn:/A/C");
+ insert(4, "ndn:/A");
+ insert(5, "ndn:/D");
+
+ // Intuitively you would think Data 4 should be between Data 1 and 2,
+ // but Data 4 has full Name ndn:/A/<32-octet hash>.
+ startInterest("ndn:/A");
+ BOOST_CHECK_EQUAL(find(), 2);
+}
+
+BOOST_AUTO_TEST_CASE(Leftmost_ExactName33)
+{
+ insert(1, "ndn:/");
+ insert(2, "ndn:/A");
+ insert(3, "ndn:/A/BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"); // 33 'B's
+ insert(4, "ndn:/A/CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"); // 33 'C's
+ insert(5, "ndn:/D");
+
+ // Data 2 is returned, because <32-octet hash> is less than Data 3.
+ startInterest("ndn:/A");
+ BOOST_CHECK_EQUAL(find(), 2);
+}
+
+BOOST_AUTO_TEST_CASE(MinSuffixComponents)
+{
+ insert(1, "ndn:/A/1/2/3/4");
+ insert(2, "ndn:/B/1/2/3");
+ insert(3, "ndn:/C/1/2");
+ insert(4, "ndn:/D/1");
+ insert(5, "ndn:/E");
+ insert(6, "ndn:/");
+
+ startInterest("ndn:/")
+ .setChildSelector(1)
+ .setMinSuffixComponents(0);
+ BOOST_CHECK_EQUAL(find(), 6);
+
+ startInterest("ndn:/")
+ .setChildSelector(1)
+ .setMinSuffixComponents(1);
+ BOOST_CHECK_EQUAL(find(), 6);
+
+ startInterest("ndn:/")
+ .setChildSelector(1)
+ .setMinSuffixComponents(2);
+ BOOST_CHECK_EQUAL(find(), 5);
+
+ startInterest("ndn:/")
+ .setChildSelector(1)
+ .setMinSuffixComponents(3);
+ BOOST_CHECK_EQUAL(find(), 4);
+
+ startInterest("ndn:/")
+ .setChildSelector(1)
+ .setMinSuffixComponents(4);
+ BOOST_CHECK_EQUAL(find(), 3);
+
+ startInterest("ndn:/")
+ .setChildSelector(1)
+ .setMinSuffixComponents(5);
+ BOOST_CHECK_EQUAL(find(), 2);
+
+ startInterest("ndn:/")
+ .setChildSelector(1)
+ .setMinSuffixComponents(6);
+ BOOST_CHECK_EQUAL(find(), 1);
+
+ startInterest("ndn:/")
+ .setChildSelector(1)
+ .setMinSuffixComponents(7);
+ BOOST_CHECK_EQUAL(find(), 0);
+}
+
+BOOST_AUTO_TEST_CASE(MaxSuffixComponents)
+{
+ insert(1, "ndn:/");
+ insert(2, "ndn:/A");
+ insert(3, "ndn:/A/B");
+ insert(4, "ndn:/A/B/C");
+ insert(5, "ndn:/A/B/C/D");
+ insert(6, "ndn:/A/B/C/D/E");
+ // Order is 6,5,4,3,2,1, because <32-octet hash> is greater than a 1-octet component.
+
+ startInterest("ndn:/")
+ .setMaxSuffixComponents(0);
+ BOOST_CHECK_EQUAL(find(), 0);
+
+ startInterest("ndn:/")
+ .setMaxSuffixComponents(1);
+ BOOST_CHECK_EQUAL(find(), 1);
+
+ startInterest("ndn:/")
+ .setMaxSuffixComponents(2);
+ BOOST_CHECK_EQUAL(find(), 2);
+
+ startInterest("ndn:/")
+ .setMaxSuffixComponents(3);
+ BOOST_CHECK_EQUAL(find(), 3);
+
+ startInterest("ndn:/")
+ .setMaxSuffixComponents(4);
+ BOOST_CHECK_EQUAL(find(), 4);
+
+ startInterest("ndn:/")
+ .setMaxSuffixComponents(5);
+ BOOST_CHECK_EQUAL(find(), 5);
+
+ startInterest("ndn:/")
+ .setMaxSuffixComponents(6);
+ BOOST_CHECK_EQUAL(find(), 6);
+}
+
+BOOST_AUTO_TEST_CASE(DigestOrder)
+{
+ insert(1, "ndn:/A");
+ insert(2, "ndn:/A");
+ // We don't know which comes first, but there must be some order
+
+ startInterest("ndn:/A")
+ .setChildSelector(0);
+ uint32_t leftmost = find();
+
+ startInterest("ndn:/A")
+ .setChildSelector(1);
+ uint32_t rightmost = find();
+
+ BOOST_CHECK_NE(leftmost, rightmost);
+}
+
+BOOST_AUTO_TEST_CASE(DigestExclude)
+{
+ insert(1, "ndn:/A/B");
+ insert(2, "ndn:/A");
+ insert(3, "ndn:/A/CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"); // 33 'C's
+
+ startInterest("ndn:/A")
+ .setExclude(Exclude().excludeBefore(name::Component(reinterpret_cast<const uint8_t*>(
+ "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF"
+ "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF"), 31))); // 31 0xFF's
+ BOOST_CHECK_EQUAL(find(), 2);
+
+ startInterest("ndn:/A")
+ .setChildSelector(1)
+ .setExclude(Exclude().excludeAfter(name::Component(reinterpret_cast<const uint8_t*>(
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00"), 33))); // 33 0x00's
+ BOOST_CHECK_EQUAL(find(), 2);
+}
+
+BOOST_AUTO_TEST_CASE(ExactName32)
+{
+ insert(1, "ndn:/A/BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB"); // 32 'B's
+ insert(2, "ndn:/A/CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC"); // 32 'C's
+
+ startInterest("ndn:/A/BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB");
+ BOOST_CHECK_EQUAL(find(), 1);
+}
+
+BOOST_AUTO_TEST_CASE(MinSuffixComponents32)
+{
+ insert(1, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A/1/2/3/4"); // 32 'x's
+ insert(2, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/B/1/2/3");
+ insert(3, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/C/1/2");
+ insert(4, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/D/1");
+ insert(5, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/E");
+ insert(6, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setChildSelector(1)
+ .setMinSuffixComponents(0);
+ BOOST_CHECK_EQUAL(find(), 6);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setChildSelector(1)
+ .setMinSuffixComponents(1);
+ BOOST_CHECK_EQUAL(find(), 6);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setChildSelector(1)
+ .setMinSuffixComponents(2);
+ BOOST_CHECK_EQUAL(find(), 5);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setChildSelector(1)
+ .setMinSuffixComponents(3);
+ BOOST_CHECK_EQUAL(find(), 4);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setChildSelector(1)
+ .setMinSuffixComponents(4);
+ BOOST_CHECK_EQUAL(find(), 3);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setChildSelector(1)
+ .setMinSuffixComponents(5);
+ BOOST_CHECK_EQUAL(find(), 2);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setChildSelector(1)
+ .setMinSuffixComponents(6);
+ BOOST_CHECK_EQUAL(find(), 1);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setChildSelector(1)
+ .setMinSuffixComponents(7);
+ BOOST_CHECK_EQUAL(find(), 0);
+}
+
+BOOST_AUTO_TEST_CASE(MaxSuffixComponents32)
+{
+ insert(1, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/"); // 32 'x's
+ insert(2, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A");
+ insert(3, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A/B");
+ insert(4, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A/B/C");
+ insert(5, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A/B/C/D");
+ insert(6, "ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/A/B/C/D/E");
+ // Order is 6,5,4,3,2,1, because <32-octet hash> is greater than a 1-octet component.
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setMaxSuffixComponents(0);
+ BOOST_CHECK_EQUAL(find(), 0);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setMaxSuffixComponents(1);
+ BOOST_CHECK_EQUAL(find(), 1);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setMaxSuffixComponents(2);
+ BOOST_CHECK_EQUAL(find(), 2);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setMaxSuffixComponents(3);
+ BOOST_CHECK_EQUAL(find(), 3);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setMaxSuffixComponents(4);
+ BOOST_CHECK_EQUAL(find(), 4);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setMaxSuffixComponents(5);
+ BOOST_CHECK_EQUAL(find(), 5);
+
+ startInterest("ndn:/xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx")
+ .setMaxSuffixComponents(6);
+ BOOST_CHECK_EQUAL(find(), 6);
+}
+
+BOOST_AUTO_TEST_SUITE_END() // Find
+
+BOOST_AUTO_TEST_SUITE_END() // TableCs
+
+} // namespace tests
+} // namespace nfd
diff --git a/tests/daemon/table/fib.cpp b/tests/daemon/table/fib.cpp
new file mode 100644
index 0000000..bdf2fca
--- /dev/null
+++ b/tests/daemon/table/fib.cpp
@@ -0,0 +1,381 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014 Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ **/
+
+#include "table/fib.hpp"
+#include "tests/daemon/face/dummy-face.hpp"
+
+#include "tests/test-common.hpp"
+
+namespace nfd {
+namespace tests {
+
+BOOST_FIXTURE_TEST_SUITE(TableFib, BaseFixture)
+
+BOOST_AUTO_TEST_CASE(Entry)
+{
+ Name prefix("ndn:/pxWhfFza");
+ shared_ptr<Face> face1 = make_shared<DummyFace>();
+ shared_ptr<Face> face2 = make_shared<DummyFace>();
+
+ fib::Entry entry(prefix);
+ BOOST_CHECK_EQUAL(entry.getPrefix(), prefix);
+
+ const fib::NextHopList& nexthops1 = entry.getNextHops();
+ // []
+ BOOST_CHECK_EQUAL(nexthops1.size(), 0);
+
+ entry.addNextHop(face1, 20);
+ const fib::NextHopList& nexthops2 = entry.getNextHops();
+ // [(face1,20)]
+ BOOST_CHECK_EQUAL(nexthops2.size(), 1);
+ BOOST_CHECK_EQUAL(nexthops2.begin()->getFace(), face1);
+ BOOST_CHECK_EQUAL(nexthops2.begin()->getCost(), 20);
+
+ entry.addNextHop(face1, 30);
+ const fib::NextHopList& nexthops3 = entry.getNextHops();
+ // [(face1,30)]
+ BOOST_CHECK_EQUAL(nexthops3.size(), 1);
+ BOOST_CHECK_EQUAL(nexthops3.begin()->getFace(), face1);
+ BOOST_CHECK_EQUAL(nexthops3.begin()->getCost(), 30);
+
+ entry.addNextHop(face2, 40);
+ const fib::NextHopList& nexthops4 = entry.getNextHops();
+ // [(face1,30), (face2,40)]
+ BOOST_CHECK_EQUAL(nexthops4.size(), 2);
+ int i = -1;
+ for (fib::NextHopList::const_iterator it = nexthops4.begin();
+ it != nexthops4.end(); ++it) {
+ ++i;
+ switch (i) {
+ case 0 :
+ BOOST_CHECK_EQUAL(it->getFace(), face1);
+ BOOST_CHECK_EQUAL(it->getCost(), 30);
+ break;
+ case 1 :
+ BOOST_CHECK_EQUAL(it->getFace(), face2);
+ BOOST_CHECK_EQUAL(it->getCost(), 40);
+ break;
+ }
+ }
+
+ entry.addNextHop(face2, 10);
+ const fib::NextHopList& nexthops5 = entry.getNextHops();
+ // [(face2,10), (face1,30)]
+ BOOST_CHECK_EQUAL(nexthops5.size(), 2);
+ i = -1;
+ for (fib::NextHopList::const_iterator it = nexthops5.begin();
+ it != nexthops5.end(); ++it) {
+ ++i;
+ switch (i) {
+ case 0 :
+ BOOST_CHECK_EQUAL(it->getFace(), face2);
+ BOOST_CHECK_EQUAL(it->getCost(), 10);
+ break;
+ case 1 :
+ BOOST_CHECK_EQUAL(it->getFace(), face1);
+ BOOST_CHECK_EQUAL(it->getCost(), 30);
+ break;
+ }
+ }
+
+ entry.removeNextHop(face1);
+ const fib::NextHopList& nexthops6 = entry.getNextHops();
+ // [(face2,10)]
+ BOOST_CHECK_EQUAL(nexthops6.size(), 1);
+ BOOST_CHECK_EQUAL(nexthops6.begin()->getFace(), face2);
+ BOOST_CHECK_EQUAL(nexthops6.begin()->getCost(), 10);
+
+ entry.removeNextHop(face1);
+ const fib::NextHopList& nexthops7 = entry.getNextHops();
+ // [(face2,10)]
+ BOOST_CHECK_EQUAL(nexthops7.size(), 1);
+ BOOST_CHECK_EQUAL(nexthops7.begin()->getFace(), face2);
+ BOOST_CHECK_EQUAL(nexthops7.begin()->getCost(), 10);
+
+ entry.removeNextHop(face2);
+ const fib::NextHopList& nexthops8 = entry.getNextHops();
+ // []
+ BOOST_CHECK_EQUAL(nexthops8.size(), 0);
+
+ entry.removeNextHop(face2);
+ const fib::NextHopList& nexthops9 = entry.getNextHops();
+ // []
+ BOOST_CHECK_EQUAL(nexthops9.size(), 0);
+}
+
+BOOST_AUTO_TEST_CASE(Insert_LongestPrefixMatch)
+{
+ Name nameEmpty;
+ Name nameA ("ndn:/A");
+ Name nameAB ("ndn:/A/B");
+ Name nameABC ("ndn:/A/B/C");
+ Name nameABCD("ndn:/A/B/C/D");
+ Name nameE ("ndn:/E");
+
+ std::pair<shared_ptr<fib::Entry>, bool> insertRes;
+ shared_ptr<fib::Entry> entry;
+
+ NameTree nameTree;
+ Fib fib(nameTree);
+ // []
+ BOOST_CHECK_EQUAL(fib.size(), 0);
+
+ entry = fib.findLongestPrefixMatch(nameA);
+ BOOST_REQUIRE(static_cast<bool>(entry)); // the empty entry
+
+ insertRes = fib.insert(nameEmpty);
+ BOOST_CHECK_EQUAL(insertRes.second, true);
+ BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameEmpty);
+ // ['/']
+ BOOST_CHECK_EQUAL(fib.size(), 1);
+
+ entry = fib.findLongestPrefixMatch(nameA);
+ BOOST_REQUIRE(static_cast<bool>(entry));
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty);
+
+ insertRes = fib.insert(nameA);
+ BOOST_CHECK_EQUAL(insertRes.second, true);
+ BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameA);
+ // ['/', '/A']
+ BOOST_CHECK_EQUAL(fib.size(), 2);
+
+ insertRes = fib.insert(nameA);
+ BOOST_CHECK_EQUAL(insertRes.second, false);
+ BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameA);
+ // ['/', '/A']
+ BOOST_CHECK_EQUAL(fib.size(), 2);
+
+ entry = fib.findLongestPrefixMatch(nameA);
+ BOOST_REQUIRE(static_cast<bool>(entry));
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
+
+ entry = fib.findLongestPrefixMatch(nameABCD);
+ BOOST_REQUIRE(static_cast<bool>(entry));
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
+
+ insertRes = fib.insert(nameABC);
+ BOOST_CHECK_EQUAL(insertRes.second, true);
+ BOOST_CHECK_EQUAL(insertRes.first->getPrefix(), nameABC);
+ // ['/', '/A', '/A/B/C']
+ BOOST_CHECK_EQUAL(fib.size(), 3);
+
+ entry = fib.findLongestPrefixMatch(nameA);
+ BOOST_REQUIRE(static_cast<bool>(entry));
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
+
+ entry = fib.findLongestPrefixMatch(nameAB);
+ BOOST_REQUIRE(static_cast<bool>(entry));
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
+
+ entry = fib.findLongestPrefixMatch(nameABCD);
+ BOOST_REQUIRE(static_cast<bool>(entry));
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameABC);
+
+ entry = fib.findLongestPrefixMatch(nameE);
+ BOOST_REQUIRE(static_cast<bool>(entry));
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty);
+}
+
+BOOST_AUTO_TEST_CASE(RemoveNextHopFromAllEntries)
+{
+ shared_ptr<Face> face1 = make_shared<DummyFace>();
+ shared_ptr<Face> face2 = make_shared<DummyFace>();
+ Name nameEmpty("ndn:/");
+ Name nameA("ndn:/A");
+ Name nameB("ndn:/B");
+
+ std::pair<shared_ptr<fib::Entry>, bool> insertRes;
+ shared_ptr<fib::Entry> entry;
+
+ NameTree nameTree;
+ Fib fib(nameTree);
+ // {}
+
+ insertRes = fib.insert(nameA);
+ insertRes.first->addNextHop(face1, 0);
+ insertRes.first->addNextHop(face2, 0);
+ // {'/A':[1,2]}
+
+ insertRes = fib.insert(nameB);
+ insertRes.first->addNextHop(face1, 0);
+ // {'/A':[1,2], '/B':[1]}
+ BOOST_CHECK_EQUAL(fib.size(), 2);
+
+ fib.removeNextHopFromAllEntries(face1);
+ // {'/A':[2]}
+ BOOST_CHECK_EQUAL(fib.size(), 1);
+
+ entry = fib.findLongestPrefixMatch(nameA);
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameA);
+ const fib::NextHopList& nexthopsA = entry->getNextHops();
+ BOOST_CHECK_EQUAL(nexthopsA.size(), 1);
+ BOOST_CHECK_EQUAL(nexthopsA.begin()->getFace(), face2);
+
+ entry = fib.findLongestPrefixMatch(nameB);
+ BOOST_CHECK_EQUAL(entry->getPrefix(), nameEmpty);
+}
+
+void
+validateFindExactMatch(const Fib& fib, const Name& target)
+{
+ shared_ptr<fib::Entry> entry = fib.findExactMatch(target);
+ if (static_cast<bool>(entry))
+ {
+ BOOST_CHECK_EQUAL(entry->getPrefix(), target);
+ }
+ else
+ {
+ BOOST_FAIL("No entry found for " << target);
+ }
+}
+
+void
+validateNoExactMatch(const Fib& fib, const Name& target)
+{
+ shared_ptr<fib::Entry> entry = fib.findExactMatch(target);
+ if (static_cast<bool>(entry))
+ {
+ BOOST_FAIL("Found unexpected entry for " << target);
+ }
+}
+
+BOOST_AUTO_TEST_CASE(FindExactMatch)
+{
+ NameTree nameTree;
+ Fib fib(nameTree);
+ fib.insert("/A");
+ fib.insert("/A/B");
+ fib.insert("/A/B/C");
+
+ validateFindExactMatch(fib, "/A");
+ validateFindExactMatch(fib, "/A/B");
+ validateFindExactMatch(fib, "/A/B/C");
+ validateNoExactMatch(fib, "/");
+
+ validateNoExactMatch(fib, "/does/not/exist");
+
+ NameTree gapNameTree;
+ Fib gapFib(nameTree);
+ fib.insert("/X");
+ fib.insert("/X/Y/Z");
+
+ validateNoExactMatch(gapFib, "/X/Y");
+
+ NameTree emptyNameTree;
+ Fib emptyFib(emptyNameTree);
+ validateNoExactMatch(emptyFib, "/nothing/here");
+}
+
+void
+validateRemove(Fib& fib, const Name& target)
+{
+ fib.erase(target);
+
+ shared_ptr<fib::Entry> entry = fib.findExactMatch(target);
+ if (static_cast<bool>(entry))
+ {
+ BOOST_FAIL("Found \"removed\" entry for " << target);
+ }
+}
+
+BOOST_AUTO_TEST_CASE(Remove)
+{
+ NameTree emptyNameTree;
+ Fib emptyFib(emptyNameTree);
+
+ emptyFib.erase("/does/not/exist"); // crash test
+
+ validateRemove(emptyFib, "/");
+
+ emptyFib.erase("/still/does/not/exist"); // crash test
+
+ NameTree nameTree;
+ Fib fib(nameTree);
+ fib.insert("/");
+ fib.insert("/A");
+ fib.insert("/A/B");
+ fib.insert("/A/B/C");
+
+ // check if we remove the right thing and leave
+ // everything else alone
+
+ validateRemove(fib, "/A/B");
+ validateFindExactMatch(fib, "/A");
+ validateFindExactMatch(fib, "/A/B/C");
+ validateFindExactMatch(fib, "/");
+
+ validateRemove(fib, "/A/B/C");
+ validateFindExactMatch(fib, "/A");
+ validateFindExactMatch(fib, "/");
+
+ validateRemove(fib, "/A");
+ validateFindExactMatch(fib, "/");
+
+ validateRemove(fib, "/");
+ validateNoExactMatch(fib, "/");
+
+ NameTree gapNameTree;
+ Fib gapFib(gapNameTree);
+ gapFib.insert("/X");
+ gapFib.insert("/X/Y/Z");
+
+ gapFib.erase("/X/Y"); //should do nothing
+ validateFindExactMatch(gapFib, "/X");
+ validateFindExactMatch(gapFib, "/X/Y/Z");
+}
+
+BOOST_AUTO_TEST_CASE(Iterator)
+{
+ NameTree nameTree;
+ Fib fib(nameTree);
+ Name nameA("/A");
+ Name nameAB("/A/B");
+ Name nameABC("/A/B/C");
+ Name nameRoot("/");
+
+ fib.insert(nameA);
+ fib.insert(nameAB);
+ fib.insert(nameABC);
+ fib.insert(nameRoot);
+
+ std::set<Name> expected;
+ expected.insert(nameA);
+ expected.insert(nameAB);
+ expected.insert(nameABC);
+ expected.insert(nameRoot);
+
+ for (Fib::const_iterator it = fib.begin(); it != fib.end(); it++)
+ {
+ bool isInSet = expected.find(it->getPrefix()) != expected.end();
+ BOOST_CHECK(isInSet);
+ expected.erase(it->getPrefix());
+ }
+
+ BOOST_CHECK_EQUAL(expected.size(), 0);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nfd
diff --git a/tests/daemon/table/measurements-accessor.cpp b/tests/daemon/table/measurements-accessor.cpp
new file mode 100644
index 0000000..6dc8ff3
--- /dev/null
+++ b/tests/daemon/table/measurements-accessor.cpp
@@ -0,0 +1,110 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014 Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ **/
+
+#include "table/measurements-accessor.hpp"
+#include "fw/strategy.hpp"
+
+#include "tests/test-common.hpp"
+
+namespace nfd {
+namespace tests {
+
+BOOST_FIXTURE_TEST_SUITE(TableMeasurementsAccessor, BaseFixture)
+
+class MeasurementsAccessorTestStrategy : public fw::Strategy
+{
+public:
+ MeasurementsAccessorTestStrategy(Forwarder& forwarder, const Name& name)
+ : Strategy(forwarder, name)
+ {
+ }
+
+ virtual
+ ~MeasurementsAccessorTestStrategy()
+
+ {
+ }
+
+ virtual void
+ afterReceiveInterest(const Face& inFace,
+ const Interest& interest,
+ shared_ptr<fib::Entry> fibEntry,
+ shared_ptr<pit::Entry> pitEntry)
+ {
+ BOOST_ASSERT(false);
+ }
+
+public: // accessors
+ MeasurementsAccessor&
+ getMeasurements_accessor()
+ {
+ return this->getMeasurements();
+ }
+};
+
+BOOST_AUTO_TEST_CASE(Access)
+{
+ Forwarder forwarder;
+
+ shared_ptr<MeasurementsAccessorTestStrategy> strategy1 =
+ make_shared<MeasurementsAccessorTestStrategy>(boost::ref(forwarder), "ndn:/strategy1");
+ shared_ptr<MeasurementsAccessorTestStrategy> strategy2 =
+ make_shared<MeasurementsAccessorTestStrategy>(boost::ref(forwarder), "ndn:/strategy2");
+
+ Name nameRoot("ndn:/");
+ Name nameA ("ndn:/A");
+ Name nameAB ("ndn:/A/B");
+ Name nameABC ("ndn:/A/B/C");
+ Name nameAD ("ndn:/A/D");
+
+ StrategyChoice& strategyChoice = forwarder.getStrategyChoice();
+ strategyChoice.install(strategy1);
+ strategyChoice.install(strategy2);
+ strategyChoice.insert(nameRoot, strategy1->getName());
+ strategyChoice.insert(nameA , strategy2->getName());
+ strategyChoice.insert(nameAB , strategy1->getName());
+
+ MeasurementsAccessor& accessor1 = strategy1->getMeasurements_accessor();
+ MeasurementsAccessor& accessor2 = strategy2->getMeasurements_accessor();
+
+ BOOST_CHECK_EQUAL(static_cast<bool>(accessor1.get(nameRoot)), true);
+ BOOST_CHECK_EQUAL(static_cast<bool>(accessor1.get(nameA )), false);
+ BOOST_CHECK_EQUAL(static_cast<bool>(accessor1.get(nameAB )), true);
+ BOOST_CHECK_EQUAL(static_cast<bool>(accessor1.get(nameABC )), true);
+ BOOST_CHECK_EQUAL(static_cast<bool>(accessor1.get(nameAD )), false);
+
+ shared_ptr<measurements::Entry> entryRoot = forwarder.getMeasurements().get(nameRoot);
+ BOOST_CHECK_NO_THROW(accessor1.getParent(entryRoot));
+
+ BOOST_CHECK_EQUAL(static_cast<bool>(accessor2.get(nameRoot)), false);
+ BOOST_CHECK_EQUAL(static_cast<bool>(accessor2.get(nameA )), true);
+ BOOST_CHECK_EQUAL(static_cast<bool>(accessor2.get(nameAB )), false);
+ BOOST_CHECK_EQUAL(static_cast<bool>(accessor2.get(nameABC )), false);
+ BOOST_CHECK_EQUAL(static_cast<bool>(accessor2.get(nameAD )), true);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nfd
diff --git a/tests/daemon/table/measurements.cpp b/tests/daemon/table/measurements.cpp
new file mode 100644
index 0000000..98676b5
--- /dev/null
+++ b/tests/daemon/table/measurements.cpp
@@ -0,0 +1,61 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014 Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ **/
+
+#include "table/measurements.hpp"
+
+#include "tests/test-common.hpp"
+
+namespace nfd {
+namespace tests {
+
+BOOST_FIXTURE_TEST_SUITE(TableMeasurements, BaseFixture)
+
+BOOST_AUTO_TEST_CASE(Get_Parent)
+{
+ NameTree nameTree;
+ Measurements measurements(nameTree);
+
+ Name name0;
+ Name nameA ("ndn:/A");
+ Name nameAB("ndn:/A/B");
+
+ shared_ptr<measurements::Entry> entryAB = measurements.get(nameAB);
+ BOOST_REQUIRE(static_cast<bool>(entryAB));
+ BOOST_CHECK_EQUAL(entryAB->getName(), nameAB);
+
+ shared_ptr<measurements::Entry> entry0 = measurements.get(name0);
+ BOOST_REQUIRE(static_cast<bool>(entry0));
+
+ shared_ptr<measurements::Entry> entryA = measurements.getParent(entryAB);
+ BOOST_REQUIRE(static_cast<bool>(entryA));
+ BOOST_CHECK_EQUAL(entryA->getName(), nameA);
+
+ shared_ptr<measurements::Entry> entry0c = measurements.getParent(entryA);
+ BOOST_CHECK_EQUAL(entry0, entry0c);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nfd
diff --git a/tests/daemon/table/name-tree.cpp b/tests/daemon/table/name-tree.cpp
new file mode 100644
index 0000000..e5e9089
--- /dev/null
+++ b/tests/daemon/table/name-tree.cpp
@@ -0,0 +1,801 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014 Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ **/
+
+#include "table/name-tree.hpp"
+#include "tests/test-common.hpp"
+
+namespace nfd {
+namespace tests {
+
+using name_tree::Entry;
+
+BOOST_FIXTURE_TEST_SUITE(TableNameTree, BaseFixture)
+
+BOOST_AUTO_TEST_CASE(Hash)
+{
+ Name root("/");
+ root.wireEncode();
+ size_t hashValue = name_tree::computeHash(root);
+ BOOST_CHECK_EQUAL(hashValue, static_cast<size_t>(0));
+
+ Name prefix("/nohello/world/ndn/research");
+ prefix.wireEncode();
+ std::vector<size_t> hashSet = name_tree::computeHashSet(prefix);
+ BOOST_CHECK_EQUAL(hashSet.size(), prefix.size() + 1);
+}
+
+BOOST_AUTO_TEST_CASE(Entry)
+{
+ Name prefix("ndn:/named-data/research/abc/def/ghi");
+
+ shared_ptr<name_tree::Entry> npe = make_shared<name_tree::Entry>(prefix);
+ BOOST_CHECK_EQUAL(npe->getPrefix(), prefix);
+
+ // examine all the get methods
+
+ size_t hash = npe->getHash();
+ BOOST_CHECK_EQUAL(hash, static_cast<size_t>(0));
+
+ shared_ptr<name_tree::Entry> parent = npe->getParent();
+ BOOST_CHECK(!static_cast<bool>(parent));
+
+ std::vector<shared_ptr<name_tree::Entry> >& childList = npe->getChildren();
+ BOOST_CHECK_EQUAL(childList.size(), static_cast<size_t>(0));
+
+ shared_ptr<fib::Entry> fib = npe->getFibEntry();
+ BOOST_CHECK(!static_cast<bool>(fib));
+
+ const std::vector< shared_ptr<pit::Entry> >& pitList = npe->getPitEntries();
+ BOOST_CHECK_EQUAL(pitList.size(), static_cast<size_t>(0));
+
+ // examine all the set method
+
+ npe->setHash(static_cast<size_t>(12345));
+ BOOST_CHECK_EQUAL(npe->getHash(), static_cast<size_t>(12345));
+
+ Name parentName("ndn:/named-data/research/abc/def");
+ parent = make_shared<name_tree::Entry>(parentName);
+ npe->setParent(parent);
+ BOOST_CHECK_EQUAL(npe->getParent(), parent);
+
+ // Insert FIB
+
+ shared_ptr<fib::Entry> fibEntry(new fib::Entry(prefix));
+ shared_ptr<fib::Entry> fibEntryParent(new fib::Entry(parentName));
+
+ npe->setFibEntry(fibEntry);
+ BOOST_CHECK_EQUAL(npe->getFibEntry(), fibEntry);
+
+ npe->setFibEntry(shared_ptr<fib::Entry>());
+ BOOST_CHECK(!static_cast<bool>(npe->getFibEntry()));
+
+ // Insert a PIT
+
+ shared_ptr<pit::Entry> PitEntry(make_shared<pit::Entry>(prefix));
+ shared_ptr<pit::Entry> PitEntry2(make_shared<pit::Entry>(parentName));
+
+ npe->insertPitEntry(PitEntry);
+ BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 1);
+
+ npe->insertPitEntry(PitEntry2);
+ BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 2);
+
+ npe->erasePitEntry(PitEntry);
+ BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 1);
+
+ npe->erasePitEntry(PitEntry2);
+ BOOST_CHECK_EQUAL(npe->getPitEntries().size(), 0);
+}
+
+BOOST_AUTO_TEST_CASE(NameTreeBasic)
+{
+ size_t nBuckets = 16;
+ NameTree nt(nBuckets);
+
+ BOOST_CHECK_EQUAL(nt.size(), 0);
+ BOOST_CHECK_EQUAL(nt.getNBuckets(), nBuckets);
+
+ Name nameABC("ndn:/a/b/c");
+ shared_ptr<name_tree::Entry> npeABC = nt.lookup(nameABC);
+ BOOST_CHECK_EQUAL(nt.size(), 4);
+
+ Name nameABD("/a/b/d");
+ shared_ptr<name_tree::Entry> npeABD = nt.lookup(nameABD);
+ BOOST_CHECK_EQUAL(nt.size(), 5);
+
+ Name nameAE("/a/e/");
+ shared_ptr<name_tree::Entry> npeAE = nt.lookup(nameAE);
+ BOOST_CHECK_EQUAL(nt.size(), 6);
+
+ Name nameF("/f");
+ shared_ptr<name_tree::Entry> npeF = nt.lookup(nameF);
+ BOOST_CHECK_EQUAL(nt.size(), 7);
+
+ // validate lookup() and findExactMatch()
+
+ Name nameAB ("/a/b");
+ BOOST_CHECK_EQUAL(npeABC->getParent(), nt.findExactMatch(nameAB));
+ BOOST_CHECK_EQUAL(npeABD->getParent(), nt.findExactMatch(nameAB));
+
+ Name nameA ("/a");
+ BOOST_CHECK_EQUAL(npeAE->getParent(), nt.findExactMatch(nameA));
+
+ Name nameRoot ("/");
+ BOOST_CHECK_EQUAL(npeF->getParent(), nt.findExactMatch(nameRoot));
+ BOOST_CHECK_EQUAL(nt.size(), 7);
+
+ Name name0("/does/not/exist");
+ shared_ptr<name_tree::Entry> npe0 = nt.findExactMatch(name0);
+ BOOST_CHECK(!static_cast<bool>(npe0));
+
+
+ // Longest Prefix Matching
+ shared_ptr<name_tree::Entry> temp;
+ Name nameABCLPM("/a/b/c/def/asdf/nlf");
+ temp = nt.findLongestPrefixMatch(nameABCLPM);
+ BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameABC));
+
+ Name nameABDLPM("/a/b/d/def/asdf/nlf");
+ temp = nt.findLongestPrefixMatch(nameABDLPM);
+ BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameABD));
+
+ Name nameABLPM("/a/b/hello/world");
+ temp = nt.findLongestPrefixMatch(nameABLPM);
+ BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameAB));
+
+ Name nameAELPM("/a/e/hello/world");
+ temp = nt.findLongestPrefixMatch(nameAELPM);
+ BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameAE));
+
+ Name nameALPM("/a/hello/world");
+ temp = nt.findLongestPrefixMatch(nameALPM);
+ BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameA));
+
+ Name nameFLPM("/f/hello/world");
+ temp = nt.findLongestPrefixMatch(nameFLPM);
+ BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameF));
+
+ Name nameRootLPM("/does_not_exist");
+ temp = nt.findLongestPrefixMatch(nameRootLPM);
+ BOOST_CHECK_EQUAL(temp, nt.findExactMatch(nameRoot));
+
+ bool eraseResult = false;
+ temp = nt.findExactMatch(nameABC);
+ if (static_cast<bool>(temp))
+ eraseResult = nt.
+ eraseEntryIfEmpty(temp);
+ BOOST_CHECK_EQUAL(nt.size(), 6);
+ BOOST_CHECK(!static_cast<bool>(nt.findExactMatch(nameABC)));
+ BOOST_CHECK_EQUAL(eraseResult, true);
+
+ eraseResult = false;
+ temp = nt.findExactMatch(nameABCLPM);
+ if (static_cast<bool>(temp))
+ eraseResult = nt.
+ eraseEntryIfEmpty(temp);
+ BOOST_CHECK(!static_cast<bool>(temp));
+ BOOST_CHECK_EQUAL(nt.size(), 6);
+ BOOST_CHECK_EQUAL(eraseResult, false);
+
+ // nt.dump(std::cout);
+
+ nt.lookup(nameABC);
+ BOOST_CHECK_EQUAL(nt.size(), 7);
+
+ eraseResult = false;
+ temp = nt.findExactMatch(nameABC);
+ if (static_cast<bool>(temp))
+ eraseResult = nt.
+ eraseEntryIfEmpty(temp);
+ BOOST_CHECK_EQUAL(nt.size(), 6);
+ BOOST_CHECK_EQUAL(eraseResult, true);
+ BOOST_CHECK(!static_cast<bool>(nt.findExactMatch(nameABC)));
+
+ BOOST_CHECK_EQUAL(nt.getNBuckets(), 16);
+
+ // should resize now
+ Name nameABCD("a/b/c/d");
+ nt.lookup(nameABCD);
+ Name nameABCDE("a/b/c/d/e");
+ nt.lookup(nameABCDE);
+ BOOST_CHECK_EQUAL(nt.size(), 9);
+ BOOST_CHECK_EQUAL(nt.getNBuckets(), 32);
+
+ // try to erase /a/b/c, should return false
+ temp = nt.findExactMatch(nameABC);
+ BOOST_CHECK_EQUAL(temp->getPrefix(), nameABC);
+ eraseResult = nt.
+ eraseEntryIfEmpty(temp);
+ BOOST_CHECK_EQUAL(eraseResult, false);
+ temp = nt.findExactMatch(nameABC);
+ BOOST_CHECK_EQUAL(temp->getPrefix(), nameABC);
+
+ temp = nt.findExactMatch(nameABD);
+ if (static_cast<bool>(temp))
+ nt.
+ eraseEntryIfEmpty(temp);
+ BOOST_CHECK_EQUAL(nt.size(), 8);
+}
+
+BOOST_AUTO_TEST_CASE(NameTreeIteratorFullEnumerate)
+{
+ size_t nBuckets = 1024;
+ NameTree nt(nBuckets);
+
+ BOOST_CHECK_EQUAL(nt.size(), 0);
+ BOOST_CHECK_EQUAL(nt.getNBuckets(), nBuckets);
+
+ Name nameABC("ndn:/a/b/c");
+ shared_ptr<name_tree::Entry> npeABC = nt.lookup(nameABC);
+ BOOST_CHECK_EQUAL(nt.size(), 4);
+
+ Name nameABD("/a/b/d");
+ shared_ptr<name_tree::Entry> npeABD = nt.lookup(nameABD);
+ BOOST_CHECK_EQUAL(nt.size(), 5);
+
+ Name nameAE("/a/e/");
+ shared_ptr<name_tree::Entry> npeAE = nt.lookup(nameAE);
+ BOOST_CHECK_EQUAL(nt.size(), 6);
+
+ Name nameF("/f");
+ shared_ptr<name_tree::Entry> npeF = nt.lookup(nameF);
+ BOOST_CHECK_EQUAL(nt.size(), 7);
+
+ Name nameRoot("/");
+ shared_ptr<name_tree::Entry> npeRoot = nt.lookup(nameRoot);
+ BOOST_CHECK_EQUAL(nt.size(), 7);
+
+ Name nameA("/a");
+ Name nameAB("/a/b");
+
+ bool hasRoot = false;
+ bool hasA = false;
+ bool hasAB = false;
+ bool hasABC = false;
+ bool hasABD = false;
+ bool hasAE = false;
+ bool hasF = false;
+
+ int counter = 0;
+ NameTree::const_iterator it = nt.fullEnumerate();
+
+ for(; it != nt.end(); it++)
+ {
+ counter++;
+
+ if (it->getPrefix() == nameRoot)
+ hasRoot = true;
+ if (it->getPrefix() == nameA)
+ hasA = true;
+ if (it->getPrefix() == nameAB)
+ hasAB = true;
+ if (it->getPrefix() == nameABC)
+ hasABC = true;
+ if (it->getPrefix() == nameABD)
+ hasABD = true;
+ if (it->getPrefix() == nameAE)
+ hasAE = true;
+ if (it->getPrefix() == nameF)
+ hasF = true;
+ }
+
+ BOOST_CHECK_EQUAL(hasRoot , true);
+ BOOST_CHECK_EQUAL(hasA , true);
+ BOOST_CHECK_EQUAL(hasAB , true);
+ BOOST_CHECK_EQUAL(hasABC , true);
+ BOOST_CHECK_EQUAL(hasABD , true);
+ BOOST_CHECK_EQUAL(hasAE , true);
+ BOOST_CHECK_EQUAL(hasF , true);
+
+ BOOST_CHECK_EQUAL(counter , 7);
+}
+
+// Predicates for testing the partial enumerate function
+
+static inline std::pair<bool, bool>
+predicate_NameTreeEntry_NameA_Only(const name_tree::Entry& entry)
+{
+ Name nameA("/a");
+ bool first = nameA.equals(entry.getPrefix());
+ return std::make_pair(first, true);
+}
+
+static inline std::pair<bool, bool>
+predicate_NameTreeEntry_Except_NameA(const name_tree::Entry& entry)
+{
+ Name nameA("/a");
+ bool first = !(nameA.equals(entry.getPrefix()));
+ return std::make_pair(first, true);
+}
+
+static inline std::pair<bool, bool>
+predicate_NameTreeEntry_NoSubNameA(const name_tree::Entry& entry)
+{
+ Name nameA("/a");
+ bool second = !(nameA.equals(entry.getPrefix()));
+ return std::make_pair(true, second);
+}
+
+static inline std::pair<bool, bool>
+predicate_NameTreeEntry_NoNameA_NoSubNameAB(const name_tree::Entry& entry)
+{
+ Name nameA("/a");
+ Name nameAB("/a/b");
+ bool first = !(nameA.equals(entry.getPrefix()));
+ bool second = !(nameAB.equals(entry.getPrefix()));
+ return std::make_pair(first, second);
+}
+
+static inline std::pair<bool, bool>
+predicate_NameTreeEntry_NoNameA_NoSubNameAC(const name_tree::Entry& entry)
+{
+ Name nameA("/a");
+ Name nameAC("/a/c");
+ bool first = !(nameA.equals(entry.getPrefix()));
+ bool second = !(nameAC.equals(entry.getPrefix()));
+ return std::make_pair(first, second);
+}
+
+static inline std::pair<bool, bool>
+predicate_NameTreeEntry_Example(const name_tree::Entry& entry)
+{
+ Name nameRoot("/");
+ Name nameA("/a");
+ Name nameAB("/a/b");
+ Name nameABC("/a/b/c");
+ Name nameAD("/a/d");
+ Name nameE("/e");
+ Name nameF("/f");
+
+ bool first = false;
+ bool second = false;
+
+ Name name = entry.getPrefix();
+
+ if (name == nameRoot || name == nameAB || name == nameABC || name == nameAD)
+ {
+ first = true;
+ }
+
+ if(name == nameRoot || name == nameA || name == nameF)
+ {
+ second = true;
+ }
+
+ return std::make_pair(first, second);
+}
+
+BOOST_AUTO_TEST_CASE(NameTreeIteratorPartialEnumerate)
+{
+ typedef NameTree::const_iterator const_iterator;
+
+ size_t nBuckets = 16;
+ NameTree nameTree(nBuckets);
+ int counter = 0;
+
+ // empty nameTree, should return end();
+ Name nameA("/a");
+ bool hasA = false;
+ const_iterator itA = nameTree.partialEnumerate(nameA);
+ BOOST_CHECK(itA == nameTree.end());
+
+ // We have "/", "/a", "/a/b", "a/c" now.
+ Name nameAB("/a/b");
+ bool hasAB = false;
+ nameTree.lookup(nameAB);
+
+ Name nameAC("/a/c");
+ bool hasAC = false;
+ nameTree.lookup(nameAC);
+ BOOST_CHECK_EQUAL(nameTree.size(), 4);
+
+ // Enumerate on some name that is not in nameTree
+ Name name0="/0";
+ const_iterator it0 = nameTree.partialEnumerate(name0);
+ BOOST_CHECK(it0 == nameTree.end());
+
+ // Accept "root" nameA only
+ const_iterator itAOnly = nameTree.partialEnumerate(nameA, &predicate_NameTreeEntry_NameA_Only);
+ BOOST_CHECK_EQUAL(itAOnly->getPrefix(), nameA);
+ BOOST_CHECK(++itAOnly == nameTree.end());
+
+ // Accept anything except "root" nameA
+ const_iterator itExceptA = nameTree.partialEnumerate(nameA, &predicate_NameTreeEntry_Except_NameA);
+ hasA = false;
+ hasAB = false;
+ hasAC = false;
+
+ counter = 0;
+ for (; itExceptA != nameTree.end(); itExceptA++)
+ {
+ counter++;
+
+ if (itExceptA->getPrefix() == nameA)
+ hasA = true;
+
+ if (itExceptA->getPrefix() == nameAB)
+ hasAB = true;
+
+ if (itExceptA->getPrefix() == nameAC)
+ hasAC = true;
+ }
+ BOOST_CHECK_EQUAL(hasA, false);
+ BOOST_CHECK_EQUAL(hasAB, true);
+ BOOST_CHECK_EQUAL(hasAC, true);
+
+ BOOST_CHECK_EQUAL(counter, 2);
+
+ Name nameAB1("a/b/1");
+ bool hasAB1 = false;
+ nameTree.lookup(nameAB1);
+
+ Name nameAB2("a/b/2");
+ bool hasAB2 = false;
+ nameTree.lookup(nameAB2);
+
+ Name nameAC1("a/c/1");
+ bool hasAC1 = false;
+ nameTree.lookup(nameAC1);
+
+ Name nameAC2("a/c/2");
+ bool hasAC2 = false;
+ nameTree.lookup(nameAC2);
+
+ BOOST_CHECK_EQUAL(nameTree.size(), 8);
+
+ // No NameA
+ // No SubTree from NameAB
+ const_iterator itNoNameANoSubNameAB = nameTree.partialEnumerate(nameA, &predicate_NameTreeEntry_NoNameA_NoSubNameAB);
+ hasA = false;
+ hasAB = false;
+ hasAB1 = false;
+ hasAB2 = false;
+ hasAC = false;
+ hasAC1 = false;
+ hasAC2 = false;
+
+ counter = 0;
+
+ for (; itNoNameANoSubNameAB != nameTree.end(); itNoNameANoSubNameAB++)
+ {
+ counter++;
+
+ if (itNoNameANoSubNameAB->getPrefix() == nameA)
+ hasA = true;
+
+ if (itNoNameANoSubNameAB->getPrefix() == nameAB)
+ hasAB = true;
+
+ if (itNoNameANoSubNameAB->getPrefix() == nameAB1)
+ hasAB1 = true;
+
+ if (itNoNameANoSubNameAB->getPrefix() == nameAB2)
+ hasAB2 = true;
+
+ if (itNoNameANoSubNameAB->getPrefix() == nameAC)
+ hasAC = true;
+
+ if (itNoNameANoSubNameAB->getPrefix() == nameAC1)
+ hasAC1 = true;
+
+ if (itNoNameANoSubNameAB->getPrefix() == nameAC2)
+ hasAC2 = true;
+ }
+
+ BOOST_CHECK_EQUAL(hasA, false);
+ BOOST_CHECK_EQUAL(hasAB, true);
+ BOOST_CHECK_EQUAL(hasAB1, false);
+ BOOST_CHECK_EQUAL(hasAB2, false);
+ BOOST_CHECK_EQUAL(hasAC, true);
+ BOOST_CHECK_EQUAL(hasAC1, true);
+ BOOST_CHECK_EQUAL(hasAC2, true);
+
+ BOOST_CHECK_EQUAL(counter, 4);
+
+ // No NameA
+ // No SubTree from NameAC
+ const_iterator itNoNameANoSubNameAC = nameTree.partialEnumerate(nameA, &predicate_NameTreeEntry_NoNameA_NoSubNameAC);
+ hasA = false;
+ hasAB = false;
+ hasAB1 = false;
+ hasAB2 = false;
+ hasAC = false;
+ hasAC1 = false;
+ hasAC2 = false;
+
+ counter = 0;
+
+ for (; itNoNameANoSubNameAC != nameTree.end(); itNoNameANoSubNameAC++)
+ {
+ counter++;
+
+ if (itNoNameANoSubNameAC->getPrefix() == nameA)
+ hasA = true;
+
+ if (itNoNameANoSubNameAC->getPrefix() == nameAB)
+ hasAB = true;
+
+ if (itNoNameANoSubNameAC->getPrefix() == nameAB1)
+ hasAB1 = true;
+
+ if (itNoNameANoSubNameAC->getPrefix() == nameAB2)
+ hasAB2 = true;
+
+ if (itNoNameANoSubNameAC->getPrefix() == nameAC)
+ hasAC = true;
+
+ if (itNoNameANoSubNameAC->getPrefix() == nameAC1)
+ hasAC1 = true;
+
+ if (itNoNameANoSubNameAC->getPrefix() == nameAC2)
+ hasAC2 = true;
+ }
+
+ BOOST_CHECK_EQUAL(hasA, false);
+ BOOST_CHECK_EQUAL(hasAB, true);
+ BOOST_CHECK_EQUAL(hasAB1, true);
+ BOOST_CHECK_EQUAL(hasAB2, true);
+ BOOST_CHECK_EQUAL(hasAC, true);
+ BOOST_CHECK_EQUAL(hasAC1, false);
+ BOOST_CHECK_EQUAL(hasAC2, false);
+
+ BOOST_CHECK_EQUAL(counter, 4);
+
+ // No Subtree from NameA
+ const_iterator itNoANoSubNameA = nameTree.partialEnumerate(nameA, &predicate_NameTreeEntry_NoSubNameA);
+
+ hasA = false;
+ hasAB = false;
+ hasAB1 = false;
+ hasAB2 = false;
+ hasAC = false;
+ hasAC1 = false;
+ hasAC2 = false;
+
+ counter = 0;
+
+ for (; itNoANoSubNameA != nameTree.end(); itNoANoSubNameA++)
+ {
+ counter++;
+
+ if (itNoANoSubNameA->getPrefix() == nameA)
+ hasA = true;
+
+ if (itNoANoSubNameA->getPrefix() == nameAB)
+ hasAB = true;
+
+ if (itNoANoSubNameA->getPrefix() == nameAB1)
+ hasAB1 = true;
+
+ if (itNoANoSubNameA->getPrefix() == nameAB2)
+ hasAB2 = true;
+
+ if (itNoANoSubNameA->getPrefix() == nameAC)
+ hasAC = true;
+
+ if (itNoANoSubNameA->getPrefix() == nameAC1)
+ hasAC1 = true;
+
+ if (itNoANoSubNameA->getPrefix() == nameAC2)
+ hasAC2 = true;
+ }
+
+ BOOST_CHECK_EQUAL(hasA, true);
+ BOOST_CHECK_EQUAL(hasAB, false);
+ BOOST_CHECK_EQUAL(hasAB1, false);
+ BOOST_CHECK_EQUAL(hasAB2, false);
+ BOOST_CHECK_EQUAL(hasAC, false);
+ BOOST_CHECK_EQUAL(hasAC1, false);
+ BOOST_CHECK_EQUAL(hasAC2, false);
+
+ BOOST_CHECK_EQUAL(counter, 1);
+
+ // Example
+ // /
+ // /A
+ // /A/B x
+ // /A/B/C
+ // /A/D x
+ // /E
+ // /F
+
+ NameTree nameTreeExample(nBuckets);
+
+ Name nameRoot("/");
+ bool hasRoot = false;
+
+ nameTreeExample.lookup(nameA);
+ hasA = false;
+ nameTreeExample.lookup(nameAB);
+ hasAB = false;
+
+ Name nameABC("a/b/c");
+ bool hasABC = false;
+ nameTreeExample.lookup(nameABC);
+
+ Name nameAD("/a/d");
+ nameTreeExample.lookup(nameAD);
+ bool hasAD = false;
+
+ Name nameE("/e");
+ nameTreeExample.lookup(nameE);
+ bool hasE = false;
+
+ Name nameF("/f");
+ nameTreeExample.lookup(nameF);
+ bool hasF = false;
+
+ counter = 0;
+ const_iterator itExample = nameTreeExample.partialEnumerate(nameA, &predicate_NameTreeEntry_Example);
+
+ for (; itExample != nameTreeExample.end(); itExample++)
+ {
+ counter++;
+
+ if (itExample->getPrefix() == nameRoot)
+ hasRoot = true;
+
+ if (itExample->getPrefix() == nameA)
+ hasA = true;
+
+ if (itExample->getPrefix() == nameAB)
+ hasAB = true;
+
+ if (itExample->getPrefix() == nameABC)
+ hasABC = true;
+
+ if (itExample->getPrefix() == nameAD)
+ hasAD = true;
+
+ if (itExample->getPrefix() == nameE)
+ hasE = true;
+
+ if (itExample->getPrefix() == nameF)
+ hasF = true;
+ }
+
+ BOOST_CHECK_EQUAL(hasRoot, false);
+ BOOST_CHECK_EQUAL(hasA, false);
+ BOOST_CHECK_EQUAL(hasAB, true);
+ BOOST_CHECK_EQUAL(hasABC, false);
+ BOOST_CHECK_EQUAL(hasAD, true);
+ BOOST_CHECK_EQUAL(hasE, false);
+ BOOST_CHECK_EQUAL(hasF, false);
+
+ BOOST_CHECK_EQUAL(counter, 2);
+}
+
+
+BOOST_AUTO_TEST_CASE(NameTreeIteratorFindAllMatches)
+{
+ size_t nBuckets = 16;
+ NameTree nt(nBuckets);
+ int counter = 0;
+
+ Name nameABCDEF("a/b/c/d/e/f");
+ shared_ptr<name_tree::Entry> npeABCDEF = nt.lookup(nameABCDEF);
+
+ Name nameAAC("a/a/c");
+ shared_ptr<name_tree::Entry> npeAAC = nt.lookup(nameAAC);
+
+ Name nameAAD1("a/a/d/1");
+ shared_ptr<name_tree::Entry> npeAAD1 = nt.lookup(nameAAD1);
+
+ Name nameAAD2("a/a/d/2");
+ shared_ptr<name_tree::Entry> npeAAD2 = nt.lookup(nameAAD2);
+
+
+ BOOST_CHECK_EQUAL(nt.size(), 12);
+
+ Name nameRoot ("/");
+ Name nameA ("/a");
+ Name nameAB ("/a/b");
+ Name nameABC ("/a/b/c");
+ Name nameABCD ("/a/b/c/d");
+ Name nameABCDE("/a/b/c/d/e");
+ Name nameAA ("/a/a");
+ Name nameAAD ("/a/a/d");
+
+ bool hasRoot = false;
+ bool hasA = false;
+ bool hasAB = false;
+ bool hasABC = false;
+ bool hasABCD = false;
+ bool hasABCDE = false;
+ bool hasABCDEF = false;
+ bool hasAA = false;
+ bool hasAAC = false;
+ bool hasAAD = false;
+ bool hasAAD1 = false;
+ bool hasAAD2 = false;
+
+ counter = 0;
+
+ for (NameTree::const_iterator it = nt.findAllMatches(nameABCDEF);
+ it != nt.end(); it++)
+ {
+ counter++;
+
+ if (it->getPrefix() == nameRoot)
+ hasRoot = true;
+ if (it->getPrefix() == nameA)
+ hasA = true;
+ if (it->getPrefix() == nameAB)
+ hasAB = true;
+ if (it->getPrefix() == nameABC)
+ hasABC = true;
+ if (it->getPrefix() == nameABCD)
+ hasABCD = true;
+ if (it->getPrefix() == nameABCDE)
+ hasABCDE = true;
+ if (it->getPrefix() == nameABCDEF)
+ hasABCDEF = true;
+ if (it->getPrefix() == nameAA)
+ hasAA = true;
+ if (it->getPrefix() == nameAAC)
+ hasAAC = true;
+ if (it->getPrefix() == nameAAD)
+ hasAAD = true;
+ if (it->getPrefix() == nameAAD1)
+ hasAAD1 = true;
+ if (it->getPrefix() == nameAAD2)
+ hasAAD2 = true;
+ }
+
+ BOOST_CHECK_EQUAL(hasRoot , true);
+ BOOST_CHECK_EQUAL(hasA , true);
+ BOOST_CHECK_EQUAL(hasAB , true);
+ BOOST_CHECK_EQUAL(hasABC , true);
+ BOOST_CHECK_EQUAL(hasABCD , true);
+ BOOST_CHECK_EQUAL(hasABCDE , true);
+ BOOST_CHECK_EQUAL(hasABCDEF , true);
+ BOOST_CHECK_EQUAL(hasAA , false);
+ BOOST_CHECK_EQUAL(hasAAC , false);
+ BOOST_CHECK_EQUAL(hasAAD , false);
+ BOOST_CHECK_EQUAL(hasAAD1 , false);
+ BOOST_CHECK_EQUAL(hasAAD2 , false);
+
+ BOOST_CHECK_EQUAL(counter, 7);
+}
+
+BOOST_AUTO_TEST_CASE(NameTreeHashTableResizeShrink)
+{
+ size_t nBuckets = 16;
+ NameTree nameTree(nBuckets);
+
+ Name prefix("/a/b/c/d/e/f/g/h"); // requires 9 buckets
+
+ shared_ptr<name_tree::Entry> entry = nameTree.lookup(prefix);
+ BOOST_CHECK_EQUAL(nameTree.size(), 9);
+ BOOST_CHECK_EQUAL(nameTree.getNBuckets(), 32);
+
+ nameTree.eraseEntryIfEmpty(entry);
+ BOOST_CHECK_EQUAL(nameTree.size(), 0);
+ BOOST_CHECK_EQUAL(nameTree.getNBuckets(), 16);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nfd
diff --git a/tests/daemon/table/pit.cpp b/tests/daemon/table/pit.cpp
new file mode 100644
index 0000000..c77c909
--- /dev/null
+++ b/tests/daemon/table/pit.cpp
@@ -0,0 +1,383 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014 Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ **/
+
+#include "table/pit.hpp"
+#include "tests/daemon/face/dummy-face.hpp"
+
+#include "tests/test-common.hpp"
+
+namespace nfd {
+namespace tests {
+
+BOOST_FIXTURE_TEST_SUITE(TablePit, BaseFixture)
+
+BOOST_AUTO_TEST_CASE(EntryInOutRecords)
+{
+ shared_ptr<Face> face1 = make_shared<DummyFace>();
+ shared_ptr<Face> face2 = make_shared<DummyFace>();
+ Name name("ndn:/KuYfjtRq");
+ shared_ptr<Interest> interest = makeInterest(name);
+ shared_ptr<Interest> interest1 = makeInterest(name);
+ interest1->setInterestLifetime(time::milliseconds(2528));
+ interest1->setNonce(25559);
+ shared_ptr<Interest> interest2 = makeInterest(name);
+ interest2->setInterestLifetime(time::milliseconds(6464));
+ interest2->setNonce(19004);
+ shared_ptr<Interest> interest3 = makeInterest(name);
+ interest3->setInterestLifetime(time::milliseconds(3585));
+ interest3->setNonce(24216);
+ shared_ptr<Interest> interest4 = makeInterest(name);
+ interest4->setInterestLifetime(time::milliseconds(8795));
+ interest4->setNonce(17365);
+
+ pit::Entry entry(*interest);
+
+ BOOST_CHECK_EQUAL(entry.getInterest().getName(), name);
+ BOOST_CHECK_EQUAL(entry.getName(), name);
+
+ const pit::InRecordCollection& inRecords1 = entry.getInRecords();
+ BOOST_CHECK_EQUAL(inRecords1.size(), 0);
+ const pit::OutRecordCollection& outRecords1 = entry.getOutRecords();
+ BOOST_CHECK_EQUAL(outRecords1.size(), 0);
+
+ // insert InRecord
+ time::steady_clock::TimePoint before1 = time::steady_clock::now();
+ pit::InRecordCollection::iterator in1 =
+ entry.insertOrUpdateInRecord(face1, *interest1);
+ time::steady_clock::TimePoint after1 = time::steady_clock::now();
+ const pit::InRecordCollection& inRecords2 = entry.getInRecords();
+ BOOST_CHECK_EQUAL(inRecords2.size(), 1);
+ BOOST_CHECK(in1 == inRecords2.begin());
+ BOOST_CHECK_EQUAL(in1->getFace(), face1);
+ BOOST_CHECK_EQUAL(in1->getLastNonce(), interest1->getNonce());
+ BOOST_CHECK_GE(in1->getLastRenewed(), before1);
+ BOOST_CHECK_LE(in1->getLastRenewed(), after1);
+ BOOST_CHECK_LE(in1->getExpiry() - in1->getLastRenewed()
+ - interest1->getInterestLifetime(),
+ (after1 - before1));
+
+ // insert OutRecord
+ time::steady_clock::TimePoint before2 = time::steady_clock::now();
+ pit::OutRecordCollection::iterator out1 =
+ entry.insertOrUpdateOutRecord(face1, *interest1);
+ time::steady_clock::TimePoint after2 = time::steady_clock::now();
+ const pit::OutRecordCollection& outRecords2 = entry.getOutRecords();
+ BOOST_CHECK_EQUAL(outRecords2.size(), 1);
+ BOOST_CHECK(out1 == outRecords2.begin());
+ BOOST_CHECK_EQUAL(out1->getFace(), face1);
+ BOOST_CHECK_EQUAL(out1->getLastNonce(), interest1->getNonce());
+ BOOST_CHECK_GE(out1->getLastRenewed(), before2);
+ BOOST_CHECK_LE(out1->getLastRenewed(), after2);
+ BOOST_CHECK_LE(out1->getExpiry() - out1->getLastRenewed()
+ - interest1->getInterestLifetime(),
+ (after2 - before2));
+
+ // update InRecord
+ time::steady_clock::TimePoint before3 = time::steady_clock::now();
+ pit::InRecordCollection::iterator in2 =
+ entry.insertOrUpdateInRecord(face1, *interest2);
+ time::steady_clock::TimePoint after3 = time::steady_clock::now();
+ const pit::InRecordCollection& inRecords3 = entry.getInRecords();
+ BOOST_CHECK_EQUAL(inRecords3.size(), 1);
+ BOOST_CHECK(in2 == inRecords3.begin());
+ BOOST_CHECK_EQUAL(in2->getFace(), face1);
+ BOOST_CHECK_EQUAL(in2->getLastNonce(), interest2->getNonce());
+ BOOST_CHECK_LE(in2->getExpiry() - in2->getLastRenewed()
+ - interest2->getInterestLifetime(),
+ (after3 - before3));
+
+ // insert another InRecord
+ pit::InRecordCollection::iterator in3 =
+ entry.insertOrUpdateInRecord(face2, *interest3);
+ const pit::InRecordCollection& inRecords4 = entry.getInRecords();
+ BOOST_CHECK_EQUAL(inRecords4.size(), 2);
+ BOOST_CHECK_EQUAL(in3->getFace(), face2);
+
+ // delete all InRecords
+ entry.deleteInRecords();
+ const pit::InRecordCollection& inRecords5 = entry.getInRecords();
+ BOOST_CHECK_EQUAL(inRecords5.size(), 0);
+
+ // insert another OutRecord
+ pit::OutRecordCollection::iterator out2 =
+ entry.insertOrUpdateOutRecord(face2, *interest4);
+ const pit::OutRecordCollection& outRecords3 = entry.getOutRecords();
+ BOOST_CHECK_EQUAL(outRecords3.size(), 2);
+ BOOST_CHECK_EQUAL(out2->getFace(), face2);
+
+ // delete OutRecord
+ entry.deleteOutRecord(face2);
+ const pit::OutRecordCollection& outRecords4 = entry.getOutRecords();
+ BOOST_REQUIRE_EQUAL(outRecords4.size(), 1);
+ BOOST_CHECK_EQUAL(outRecords4.begin()->getFace(), face1);
+}
+
+BOOST_AUTO_TEST_CASE(EntryNonce)
+{
+ shared_ptr<Interest> interest = makeInterest("ndn:/qtCQ7I1c");
+
+ pit::Entry entry(*interest);
+
+ BOOST_CHECK_EQUAL(entry.addNonce(25559), true);
+ BOOST_CHECK_EQUAL(entry.addNonce(25559), false);
+ BOOST_CHECK_EQUAL(entry.addNonce(19004), true);
+ BOOST_CHECK_EQUAL(entry.addNonce(19004), false);
+}
+
+BOOST_AUTO_TEST_CASE(EntryLifetime)
+{
+ shared_ptr<Interest> interest = makeInterest("ndn:/7oIEurbgy6");
+ BOOST_ASSERT(interest->getInterestLifetime() < time::milliseconds::zero()); // library uses -1 to indicate unset lifetime
+
+ shared_ptr<Face> face = make_shared<DummyFace>();
+ pit::Entry entry(*interest);
+
+ pit::InRecordCollection::iterator inIt = entry.insertOrUpdateInRecord(face, *interest);
+ BOOST_CHECK_GT(inIt->getExpiry(), time::steady_clock::now());
+
+ pit::OutRecordCollection::iterator outIt = entry.insertOrUpdateOutRecord(face, *interest);
+ BOOST_CHECK_GT(outIt->getExpiry(), time::steady_clock::now());
+}
+
+BOOST_AUTO_TEST_CASE(EntryCanForwardTo)
+{
+ shared_ptr<Interest> interest = makeInterest("ndn:/WDsuBLIMG");
+ pit::Entry entry(*interest);
+
+ shared_ptr<Face> face1 = make_shared<DummyFace>();
+ shared_ptr<Face> face2 = make_shared<DummyFace>();
+
+ entry.insertOrUpdateInRecord(face1, *interest);
+ BOOST_CHECK_EQUAL(entry.canForwardTo(*face1), false);
+ BOOST_CHECK_EQUAL(entry.canForwardTo(*face2), true);
+
+ entry.insertOrUpdateInRecord(face2, *interest);
+ BOOST_CHECK_EQUAL(entry.canForwardTo(*face1), true);
+ BOOST_CHECK_EQUAL(entry.canForwardTo(*face2), true);
+
+ entry.insertOrUpdateOutRecord(face1, *interest);
+ BOOST_CHECK_EQUAL(entry.canForwardTo(*face1), false);
+ BOOST_CHECK_EQUAL(entry.canForwardTo(*face2), true);
+}
+
+BOOST_AUTO_TEST_CASE(Insert)
+{
+ Name name1("ndn:/5vzBNnMst");
+ Name name2("ndn:/igSGfEIM62");
+ Exclude exclude1;
+ exclude1.excludeOne(Name::Component("u26p47oep"));
+ Exclude exclude2;
+ exclude2.excludeBefore(Name::Component("u26p47oep"));
+ ndn::KeyLocator keyLocator1("ndn:/sGAE3peMHA");
+ ndn::KeyLocator keyLocator2("ndn:/nIJH6pr4");
+
+ NameTree nameTree(16);
+ Pit pit(nameTree);
+ BOOST_CHECK_EQUAL(pit.size(), 0);
+ std::pair<shared_ptr<pit::Entry>, bool> insertResult;
+
+ // base
+ shared_ptr<Interest> interestA = make_shared<Interest>(name1);
+ insertResult = pit.insert(*interestA);
+ BOOST_CHECK_EQUAL(insertResult.second, true);
+ BOOST_CHECK_EQUAL(pit.size(), 1);
+
+ // A+MinSuffixComponents
+ shared_ptr<Interest> interestB = make_shared<Interest>(*interestA);
+ interestB->setMinSuffixComponents(2);
+ insertResult = pit.insert(*interestB);
+ BOOST_CHECK_EQUAL(insertResult.second, true);
+ BOOST_CHECK_EQUAL(pit.size(), 2);
+
+ // A+MaxSuffixComponents
+ shared_ptr<Interest> interestC = make_shared<Interest>(*interestA);
+ interestC->setMaxSuffixComponents(4);
+ insertResult = pit.insert(*interestC);
+ BOOST_CHECK_EQUAL(insertResult.second, true);
+ BOOST_CHECK_EQUAL(pit.size(), 3);
+
+ // A+KeyLocator1
+ shared_ptr<Interest> interestD = make_shared<Interest>(*interestA);
+ interestD->setPublisherPublicKeyLocator(keyLocator1);
+ insertResult = pit.insert(*interestD);
+ BOOST_CHECK_EQUAL(insertResult.second, true);
+ BOOST_CHECK_EQUAL(pit.size(), 4);
+
+ // A+KeyLocator2
+ shared_ptr<Interest> interestE = make_shared<Interest>(*interestA);
+ interestE->setPublisherPublicKeyLocator(keyLocator2);
+ insertResult = pit.insert(*interestE);
+ BOOST_CHECK_EQUAL(insertResult.second, true);
+ BOOST_CHECK_EQUAL(pit.size(), 5);
+
+ // A+Exclude1
+ shared_ptr<Interest> interestF = make_shared<Interest>(*interestA);
+ interestF->setExclude(exclude1);
+ insertResult = pit.insert(*interestF);
+ BOOST_CHECK_EQUAL(insertResult.second, true);
+ BOOST_CHECK_EQUAL(pit.size(), 6);
+
+ // A+Exclude2
+ shared_ptr<Interest> interestG = make_shared<Interest>(*interestA);
+ interestG->setExclude(exclude2);
+ insertResult = pit.insert(*interestG);
+ BOOST_CHECK_EQUAL(insertResult.second, true);
+ BOOST_CHECK_EQUAL(pit.size(), 7);
+
+ // A+ChildSelector0
+ shared_ptr<Interest> interestH = make_shared<Interest>(*interestA);
+ interestH->setChildSelector(0);
+ insertResult = pit.insert(*interestH);
+ BOOST_CHECK_EQUAL(insertResult.second, true);
+ BOOST_CHECK_EQUAL(pit.size(), 8);
+
+ // A+ChildSelector1
+ shared_ptr<Interest> interestI = make_shared<Interest>(*interestA);
+ interestI->setChildSelector(1);
+ insertResult = pit.insert(*interestI);
+ BOOST_CHECK_EQUAL(insertResult.second, true);
+ BOOST_CHECK_EQUAL(pit.size(), 9);
+
+ // A+MustBeFresh
+ shared_ptr<Interest> interestJ = make_shared<Interest>(*interestA);
+ interestJ->setMustBeFresh(true);
+ insertResult = pit.insert(*interestJ);
+ BOOST_CHECK_EQUAL(insertResult.second, true);
+ BOOST_CHECK_EQUAL(pit.size(), 10);
+
+ // A+InterestLifetime
+ shared_ptr<Interest> interestK = make_shared<Interest>(*interestA);
+ interestK->setInterestLifetime(time::milliseconds(1000));
+ insertResult = pit.insert(*interestK);
+ BOOST_CHECK_EQUAL(insertResult.second, false);// only guiders differ
+ BOOST_CHECK_EQUAL(pit.size(), 10);
+
+ // A+Nonce
+ shared_ptr<Interest> interestL = make_shared<Interest>(*interestA);
+ interestL->setNonce(2192);
+ insertResult = pit.insert(*interestL);
+ BOOST_CHECK_EQUAL(insertResult.second, false);// only guiders differ
+ BOOST_CHECK_EQUAL(pit.size(), 10);
+
+ // different Name+Exclude1
+ shared_ptr<Interest> interestM = make_shared<Interest>(name2);
+ interestM->setExclude(exclude1);
+ insertResult = pit.insert(*interestM);
+ BOOST_CHECK_EQUAL(insertResult.second, true);
+ BOOST_CHECK_EQUAL(pit.size(), 11);
+}
+
+BOOST_AUTO_TEST_CASE(Erase)
+{
+ Interest interest(Name("ndn:/z88Admz6A2"));
+
+ NameTree nameTree(16);
+ Pit pit(nameTree);
+
+ std::pair<shared_ptr<pit::Entry>, bool> insertResult;
+
+ BOOST_CHECK_EQUAL(pit.size(), 0);
+
+ insertResult = pit.insert(interest);
+ BOOST_CHECK_EQUAL(insertResult.second, true);
+ BOOST_CHECK_EQUAL(pit.size(), 1);
+
+ insertResult = pit.insert(interest);
+ BOOST_CHECK_EQUAL(insertResult.second, false);
+ BOOST_CHECK_EQUAL(pit.size(), 1);
+
+ pit.erase(insertResult.first);
+ BOOST_CHECK_EQUAL(pit.size(), 0);
+
+ insertResult = pit.insert(interest);
+ BOOST_CHECK_EQUAL(insertResult.second, true);
+ BOOST_CHECK_EQUAL(pit.size(), 1);
+
+}
+
+BOOST_AUTO_TEST_CASE(FindAllDataMatches)
+{
+ Name nameA ("ndn:/A");
+ Name nameAB ("ndn:/A/B");
+ Name nameABC ("ndn:/A/B/C");
+ Name nameABCD("ndn:/A/B/C/D");
+ Name nameD ("ndn:/D");
+
+ Interest interestA (nameA );
+ Interest interestABC(nameABC);
+ Interest interestD (nameD );
+
+ NameTree nameTree(16);
+ Pit pit(nameTree);
+ int count = 0;
+
+ BOOST_CHECK_EQUAL(pit.size(), 0);
+
+ pit.insert(interestA );
+ pit.insert(interestABC);
+ pit.insert(interestD );
+
+ nameTree.lookup(nameABCD); // make sure /A/B/C/D is in nameTree
+
+ BOOST_CHECK_EQUAL(pit.size(), 3);
+
+ Data data(nameABCD);
+
+ shared_ptr<pit::DataMatchResult> matches = pit.findAllDataMatches(data);
+
+ bool hasA = false;
+ bool hasAB = false;
+ bool hasABC = false;
+ bool hasD = false;
+
+ for (pit::DataMatchResult::iterator it = matches->begin();
+ it != matches->end(); ++it) {
+ ++count;
+ shared_ptr<pit::Entry> entry = *it;
+
+ if (entry->getName().equals(nameA ))
+ hasA = true;
+
+ if (entry->getName().equals(nameAB))
+ hasAB = true;
+
+ if (entry->getName().equals(nameABC))
+ hasABC = true;
+
+ if (entry->getName().equals(nameD))
+ hasD = true;
+ }
+ BOOST_CHECK_EQUAL(hasA , true);
+ BOOST_CHECK_EQUAL(hasAB , false);
+ BOOST_CHECK_EQUAL(hasABC, true);
+ BOOST_CHECK_EQUAL(hasD , false);
+
+ BOOST_CHECK_EQUAL(count, 2);
+
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nfd
diff --git a/tests/daemon/table/strategy-choice.cpp b/tests/daemon/table/strategy-choice.cpp
new file mode 100644
index 0000000..6927375
--- /dev/null
+++ b/tests/daemon/table/strategy-choice.cpp
@@ -0,0 +1,155 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014 Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ **/
+
+#include "table/strategy-choice.hpp"
+#include "tests/daemon/fw/dummy-strategy.hpp"
+
+#include "tests/test-common.hpp"
+
+namespace nfd {
+namespace tests {
+
+BOOST_FIXTURE_TEST_SUITE(TableStrategyChoice, BaseFixture)
+
+using fw::Strategy;
+
+BOOST_AUTO_TEST_CASE(Effective)
+{
+ Forwarder forwarder;
+ Name nameP("ndn:/strategy/P");
+ Name nameQ("ndn:/strategy/Q");
+ Name nameZ("ndn:/strategy/Z");
+ shared_ptr<Strategy> strategyP = make_shared<DummyStrategy>(boost::ref(forwarder), nameP);
+ shared_ptr<Strategy> strategyQ = make_shared<DummyStrategy>(boost::ref(forwarder), nameQ);
+
+ StrategyChoice& table = forwarder.getStrategyChoice();
+
+ // install
+ BOOST_CHECK_EQUAL(table.install(strategyP), true);
+ BOOST_CHECK_EQUAL(table.install(strategyQ), true);
+ BOOST_CHECK_EQUAL(table.install(strategyQ), false);
+
+ BOOST_CHECK(table.insert("ndn:/", nameP));
+ // { '/'=>P }
+
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/") .getName(), nameP);
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/A") .getName(), nameP);
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/A/B").getName(), nameP);
+
+ BOOST_CHECK(table.insert("ndn:/A/B", nameP));
+ // { '/'=>P, '/A/B'=>P }
+
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/") .getName(), nameP);
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/A") .getName(), nameP);
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/A/B").getName(), nameP);
+ // same instance
+ BOOST_CHECK_EQUAL(&table.findEffectiveStrategy("ndn:/"), strategyP.get());
+ BOOST_CHECK_EQUAL(&table.findEffectiveStrategy("ndn:/A"), strategyP.get());
+ BOOST_CHECK_EQUAL(&table.findEffectiveStrategy("ndn:/A/B"), strategyP.get());
+
+ table.erase("ndn:/A"); // no effect
+ // { '/'=>P, '/A/B'=>P }
+
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/") .getName(), nameP);
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/A") .getName(), nameP);
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/A/B").getName(), nameP);
+
+ BOOST_CHECK(table.insert("ndn:/A", nameQ));
+ // { '/'=>P, '/A/B'=>P, '/A'=>Q }
+
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/") .getName(), nameP);
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/A") .getName(), nameQ);
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/A/B").getName(), nameP);
+
+ table.erase("ndn:/A/B");
+ // { '/'=>P, '/A'=>Q }
+
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/") .getName(), nameP);
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/A") .getName(), nameQ);
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/A/B").getName(), nameQ);
+
+ BOOST_CHECK(!table.insert("ndn:/", nameZ)); // non existent strategy
+
+ BOOST_CHECK(table.insert("ndn:/", nameQ));
+ BOOST_CHECK(table.insert("ndn:/A", nameP));
+ // { '/'=>Q, '/A'=>P }
+
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/") .getName(), nameQ);
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/A") .getName(), nameP);
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/A/B").getName(), nameP);
+ BOOST_CHECK_EQUAL(table.findEffectiveStrategy("ndn:/D") .getName(), nameQ);
+}
+
+class PStrategyInfo : public fw::StrategyInfo
+{
+};
+
+BOOST_AUTO_TEST_CASE(ClearStrategyInfo)
+{
+ Forwarder forwarder;
+ Name nameP("ndn:/strategy/P");
+ Name nameQ("ndn:/strategy/Q");
+ shared_ptr<Strategy> strategyP = make_shared<DummyStrategy>(boost::ref(forwarder), nameP);
+ shared_ptr<Strategy> strategyQ = make_shared<DummyStrategy>(boost::ref(forwarder), nameQ);
+
+ StrategyChoice& table = forwarder.getStrategyChoice();
+ Measurements& measurements = forwarder.getMeasurements();
+
+ // install
+ table.install(strategyP);
+ table.install(strategyQ);
+
+ BOOST_CHECK(table.insert("ndn:/", nameP));
+ // { '/'=>P }
+ measurements.get("ndn:/") ->getOrCreateStrategyInfo<PStrategyInfo>();
+ measurements.get("ndn:/A") ->getOrCreateStrategyInfo<PStrategyInfo>();
+ measurements.get("ndn:/A/B") ->getOrCreateStrategyInfo<PStrategyInfo>();
+ measurements.get("ndn:/A/C") ->getOrCreateStrategyInfo<PStrategyInfo>();
+
+ BOOST_CHECK(table.insert("ndn:/A/B", nameP));
+ // { '/'=>P, '/A/B'=>P }
+ BOOST_CHECK( static_cast<bool>(measurements.get("ndn:/") ->getStrategyInfo<PStrategyInfo>()));
+ BOOST_CHECK( static_cast<bool>(measurements.get("ndn:/A") ->getStrategyInfo<PStrategyInfo>()));
+ BOOST_CHECK( static_cast<bool>(measurements.get("ndn:/A/B")->getStrategyInfo<PStrategyInfo>()));
+ BOOST_CHECK( static_cast<bool>(measurements.get("ndn:/A/C")->getStrategyInfo<PStrategyInfo>()));
+
+ BOOST_CHECK(table.insert("ndn:/A", nameQ));
+ // { '/'=>P, '/A/B'=>P, '/A'=>Q }
+ BOOST_CHECK( static_cast<bool>(measurements.get("ndn:/") ->getStrategyInfo<PStrategyInfo>()));
+ BOOST_CHECK(!static_cast<bool>(measurements.get("ndn:/A") ->getStrategyInfo<PStrategyInfo>()));
+ BOOST_CHECK( static_cast<bool>(measurements.get("ndn:/A/B")->getStrategyInfo<PStrategyInfo>()));
+ BOOST_CHECK(!static_cast<bool>(measurements.get("ndn:/A/C")->getStrategyInfo<PStrategyInfo>()));
+
+ table.erase("ndn:/A/B");
+ // { '/'=>P, '/A'=>Q }
+ BOOST_CHECK( static_cast<bool>(measurements.get("ndn:/") ->getStrategyInfo<PStrategyInfo>()));
+ BOOST_CHECK(!static_cast<bool>(measurements.get("ndn:/A") ->getStrategyInfo<PStrategyInfo>()));
+ BOOST_CHECK(!static_cast<bool>(measurements.get("ndn:/A/B")->getStrategyInfo<PStrategyInfo>()));
+ BOOST_CHECK(!static_cast<bool>(measurements.get("ndn:/A/C")->getStrategyInfo<PStrategyInfo>()));
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nfd
diff --git a/tests/daemon/table/strategy-info-host.cpp b/tests/daemon/table/strategy-info-host.cpp
new file mode 100644
index 0000000..82d4fcc
--- /dev/null
+++ b/tests/daemon/table/strategy-info-host.cpp
@@ -0,0 +1,79 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/**
+ * Copyright (c) 2014 Regents of the University of California,
+ * Arizona Board of Regents,
+ * Colorado State University,
+ * University Pierre & Marie Curie, Sorbonne University,
+ * Washington University in St. Louis,
+ * Beijing Institute of Technology
+ *
+ * This file is part of NFD (Named Data Networking Forwarding Daemon).
+ * See AUTHORS.md for complete list of NFD authors and contributors.
+ *
+ * NFD is free software: you can redistribute it and/or modify it under the terms
+ * of the GNU General Public License as published by the Free Software Foundation,
+ * either version 3 of the License, or (at your option) any later version.
+ *
+ * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+ * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
+ **/
+
+#include "table/strategy-info-host.hpp"
+
+#include "tests/test-common.hpp"
+
+namespace nfd {
+namespace tests {
+
+static int g_DummyStrategyInfo_count = 0;
+
+class DummyStrategyInfo : public fw::StrategyInfo
+{
+public:
+ DummyStrategyInfo(int id)
+ : m_id(id)
+ {
+ ++g_DummyStrategyInfo_count;
+ }
+
+ virtual ~DummyStrategyInfo()
+ {
+ --g_DummyStrategyInfo_count;
+ }
+
+ int m_id;
+};
+
+BOOST_FIXTURE_TEST_SUITE(TableStrategyInfoHost, BaseFixture)
+
+BOOST_AUTO_TEST_CASE(SetGetClear)
+{
+ StrategyInfoHost host;
+
+ BOOST_CHECK(!static_cast<bool>(host.getStrategyInfo<DummyStrategyInfo>()));
+
+ g_DummyStrategyInfo_count = 0;
+
+ shared_ptr<DummyStrategyInfo> info = make_shared<DummyStrategyInfo>(7591);
+ host.setStrategyInfo(info);
+ BOOST_REQUIRE(static_cast<bool>(host.getStrategyInfo<DummyStrategyInfo>()));
+ BOOST_CHECK_EQUAL(host.getStrategyInfo<DummyStrategyInfo>()->m_id, 7591);
+
+ info.reset(); // unlink local reference
+ // host should still have a reference to info
+ BOOST_REQUIRE(static_cast<bool>(host.getStrategyInfo<DummyStrategyInfo>()));
+ BOOST_CHECK_EQUAL(host.getStrategyInfo<DummyStrategyInfo>()->m_id, 7591);
+
+ host.clearStrategyInfo();
+ BOOST_CHECK(!static_cast<bool>(host.getStrategyInfo<DummyStrategyInfo>()));
+ BOOST_CHECK_EQUAL(g_DummyStrategyInfo_count, 0);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+} // namespace tests
+} // namespace nfd