rib: Implement RIB as trie
refs: #1271
Change-Id: Idbd6d4d67f8a88b474ea0b20280c79e367bc98e5
diff --git a/rib/face-entry.hpp b/rib/face-entry.hpp
new file mode 100644
index 0000000..88531f6
--- /dev/null
+++ b/rib/face-entry.hpp
@@ -0,0 +1,70 @@
+/* -*- 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,
+ * The University of Memphis
+ *
+ * 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/>.
+ */
+
+#ifndef NFD_RIB_FACE_ENTRY_HPP
+#define NFD_RIB_FACE_ENTRY_HPP
+
+namespace nfd {
+namespace rib {
+
+/** \class FaceEntry
+ * \brief represents a route for a name prefix
+ */
+class FaceEntry
+{
+public:
+ FaceEntry()
+ : faceId(0)
+ , origin(0)
+ , flags(0)
+ , cost(0)
+ , expires(time::steady_clock::TimePoint::min())
+ {
+ }
+
+public:
+ uint64_t faceId;
+ uint64_t origin;
+ uint64_t flags;
+ uint64_t cost;
+ time::steady_clock::TimePoint expires;
+};
+
+inline bool
+compareFaceIdAndOrigin(const FaceEntry& entry1, const FaceEntry& entry2)
+{
+ return (entry1.faceId == entry2.faceId && entry1.origin == entry2.origin);
+}
+
+inline bool
+compareFaceId(const FaceEntry& entry, const uint64_t faceId)
+{
+ return (entry.faceId == faceId);
+}
+
+} // namespace rib
+} // namespace nfd
+
+#endif // NFD_RIB_RIB_ENTRY_HPP
diff --git a/rib/rib-entry.cpp b/rib/rib-entry.cpp
new file mode 100644
index 0000000..db72d37
--- /dev/null
+++ b/rib/rib-entry.cpp
@@ -0,0 +1,131 @@
+/* -*- 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,
+ * The University of Memphis
+ *
+ * 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 "rib-entry.hpp"
+
+#include <ndn-cxx/management/nfd-control-command.hpp>
+
+namespace nfd {
+namespace rib {
+
+RibEntry::FaceList::iterator
+RibEntry::findFace(const FaceEntry& face)
+{
+ return std::find_if(begin(), end(), bind(&compareFaceIdAndOrigin, _1, face));
+}
+
+bool
+RibEntry::insertFace(const FaceEntry& entry)
+{
+ iterator it = findFace(entry);
+
+ if (it == end())
+ {
+ m_faces.push_back(entry);
+ return true;
+ }
+ else
+ {
+ return false;
+ }
+}
+
+bool
+RibEntry::eraseFace(const FaceEntry& face)
+{
+ RibEntry::iterator it = std::find_if(begin(), end(), bind(&compareFaceIdAndOrigin, _1, face));
+ if (it != m_faces.end())
+ {
+ m_faces.erase(it);
+ return true;
+ }
+ else
+ {
+ return false;
+ }
+}
+
+bool
+RibEntry::hasFaceId(const uint64_t faceId) const
+{
+ RibEntry::const_iterator it = std::find_if(cbegin(), cend(), bind(&compareFaceId, _1, faceId));
+
+ return (it != cend());
+}
+
+void
+RibEntry::addChild(shared_ptr<RibEntry> child)
+{
+ BOOST_ASSERT(!static_cast<bool>(child->getParent()));
+ child->setParent(this->shared_from_this());
+ m_children.push_back(child);
+}
+
+void
+RibEntry::removeChild(shared_ptr<RibEntry> child)
+{
+ BOOST_ASSERT(child->getParent().get() == this);
+ child->setParent(shared_ptr<RibEntry>());
+ m_children.remove(child);
+}
+
+RibEntry::FaceList::iterator
+RibEntry::eraseFace(FaceList::iterator face)
+{
+ return m_faces.erase(face);
+}
+
+std::ostream&
+operator<<(std::ostream& os, const FaceEntry& entry)
+{
+ os << "FaceEntry("
+ << " faceid: " << entry.faceId
+ << " origin: " << entry.origin
+ << " cost: " << entry.cost
+ << " flags: " << entry.flags
+ << " expires in: " << (entry.expires - time::steady_clock::now())
+ << ")";
+
+ return os;
+}
+
+std::ostream&
+operator<<(std::ostream& os, const RibEntry& entry)
+{
+ os << "RibEntry{\n";
+ os << "\tName: " << entry.getName() << "\n";
+
+ for (RibEntry::FaceList::const_iterator faceIt = entry.cbegin(); faceIt != entry.cend(); ++faceIt)
+ {
+ os << "\t" << (*faceIt) << "\n";
+ }
+
+ os << "}";
+
+ return os;
+}
+
+} // namespace rib
+} // namespace nfd
diff --git a/rib/rib-entry.hpp b/rib/rib-entry.hpp
new file mode 100644
index 0000000..4726a04
--- /dev/null
+++ b/rib/rib-entry.hpp
@@ -0,0 +1,188 @@
+/* -*- 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,
+ * The University of Memphis
+ *
+ * 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/>.
+ */
+
+#ifndef NFD_RIB_RIB_ENTRY_HPP
+#define NFD_RIB_RIB_ENTRY_HPP
+
+#include "face-entry.hpp"
+
+namespace nfd {
+namespace rib {
+
+/** \class RibEntry
+ * \brief represents a namespace
+ */
+class RibEntry : public enable_shared_from_this<RibEntry>
+{
+public:
+ typedef std::list<FaceEntry> FaceList;
+ typedef FaceList::iterator iterator;
+ typedef FaceList::const_iterator const_iterator;
+
+ RibEntry()
+ {
+ }
+
+ void
+ setName(const Name& prefix);
+
+ const Name&
+ getName() const;
+
+ shared_ptr<RibEntry>
+ getParent() const;
+
+ bool
+ hasParent() const;
+
+ void
+ addChild(shared_ptr<RibEntry> child);
+
+ void
+ removeChild(shared_ptr<RibEntry> child);
+
+ std::list<shared_ptr<RibEntry> >&
+ getChildren();
+
+ bool
+ hasChildren() const;
+
+ /** \brief inserts a new face into the entry's face list
+ * If another entry already exists with the same faceId and origin,
+ * the new face is not inserted.
+ * \return{ true if the face is inserted, false otherwise }
+ */
+ bool
+ insertFace(const FaceEntry& face);
+
+ /** \brief erases a FaceEntry with the same faceId and origin
+ * \return{ true if the face is removed, false otherwise }
+ */
+ bool
+ eraseFace(const FaceEntry& face);
+
+ /** \brief erases a FaceEntry with the passed iterator
+ * \return{ an iterator to the element that followed the erased iterator }
+ */
+ iterator
+ eraseFace(FaceList::iterator face);
+
+ bool
+ hasFaceId(const uint64_t faceId) const;
+
+ FaceList&
+ getFaces();
+
+ iterator
+ findFace(const FaceEntry& face);
+
+ const_iterator
+ cbegin() const;
+
+ const_iterator
+ cend() const;
+
+ iterator
+ begin();
+
+ iterator
+ end();
+
+private:
+ void
+ setParent(shared_ptr<RibEntry> parent);
+
+private:
+ Name m_name;
+ std::list<shared_ptr<RibEntry> > m_children;
+ shared_ptr<RibEntry> m_parent;
+ FaceList m_faces;
+ FaceList m_inheritedFaces;
+};
+
+inline void
+RibEntry::setName(const Name& prefix)
+{
+ m_name = prefix;
+}
+
+inline const Name&
+RibEntry::getName() const
+{
+ return m_name;
+}
+
+inline void
+RibEntry::setParent(shared_ptr<RibEntry> parent)
+{
+ m_parent = parent;
+}
+
+inline shared_ptr<RibEntry>
+RibEntry::getParent() const
+{
+ return m_parent;
+}
+
+inline std::list<shared_ptr<RibEntry> >&
+RibEntry::getChildren()
+{
+ return m_children;
+}
+
+inline RibEntry::FaceList&
+RibEntry::getFaces()
+{
+ return m_faces;
+}
+
+inline RibEntry::const_iterator
+RibEntry::cbegin() const
+{
+ return m_faces.begin();
+}
+
+inline RibEntry::const_iterator
+RibEntry::cend() const
+{
+ return m_faces.end();
+}
+
+inline RibEntry::iterator
+RibEntry::begin()
+{
+ return m_faces.begin();
+}
+
+inline RibEntry::iterator
+RibEntry::end()
+{
+ return m_faces.end();
+}
+
+} // namespace rib
+} // namespace nfd
+
+#endif // NFD_RIB_RIB_ENTRY_HPP
diff --git a/rib/rib-manager.cpp b/rib/rib-manager.cpp
index a84d7f6..b89b619 100644
--- a/rib/rib-manager.cpp
+++ b/rib/rib-manager.cpp
@@ -1,12 +1,12 @@
/* -*- 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,
- * The University of Memphis
+ * 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,
+ * The University of Memphis
*
* This file is part of NFD (Named Data Networking Forwarding Daemon).
* See AUTHORS.md for complete list of NFD authors and contributors.
@@ -21,7 +21,7 @@
*
* 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 "rib-manager.hpp"
#include "core/global-io.hpp"
@@ -216,28 +216,27 @@
return;
}
- RibEntry ribEntry;
- ribEntry.name = parameters.getName();
- ribEntry.faceId = parameters.getFaceId();
- ribEntry.origin = parameters.getOrigin();
- ribEntry.cost = parameters.getCost();
- ribEntry.flags = parameters.getFlags();
- ribEntry.expires = time::steady_clock::now() + parameters.getExpirationPeriod();
+ FaceEntry faceEntry;
+ faceEntry.faceId = parameters.getFaceId();
+ faceEntry.origin = parameters.getOrigin();
+ faceEntry.cost = parameters.getCost();
+ faceEntry.flags = parameters.getFlags();
+ faceEntry.expires = time::steady_clock::now() + parameters.getExpirationPeriod();
- NFD_LOG_TRACE("register prefix: " << ribEntry);
+ NFD_LOG_TRACE("register prefix: " << faceEntry);
- // For right now, just pass the options to fib as it is,
- // without processing flags. Later options will be first added to
- // Rib tree, then nrd will generate fib updates based on flags and then
- // will add next hops one by one..
- m_managedRib.insert(ribEntry);
+ /// \todo For right now, just pass the options to fib as is
+ /// without processing flags. Later, options will first be added to
+ /// Rib tree, nrd will generate fib updates based on flags, and
+ /// will then add next hops one by one.
+ m_managedRib.insert(parameters.getName(), faceEntry);
m_nfdController.start<ndn::nfd::FibAddNextHopCommand>(
ControlParameters()
- .setName(ribEntry.name)
- .setFaceId(ribEntry.faceId)
- .setCost(ribEntry.cost),
- bind(&RibManager::onRegSuccess, this, request, parameters, ribEntry),
- bind(&RibManager::onCommandError, this, _1, _2, request, ribEntry));
+ .setName(parameters.getName())
+ .setFaceId(faceEntry.faceId)
+ .setCost(faceEntry.cost),
+ bind(&RibManager::onRegSuccess, this, request, parameters, faceEntry),
+ bind(&RibManager::onCommandError, this, _1, _2, request, faceEntry));
}
void
@@ -253,19 +252,18 @@
return;
}
- RibEntry ribEntry;
- ribEntry.name = parameters.getName();
- ribEntry.faceId = parameters.getFaceId();
- ribEntry.origin = parameters.getOrigin();
+ FaceEntry faceEntry;
+ faceEntry.faceId = parameters.getFaceId();
+ faceEntry.origin = parameters.getOrigin();
- NFD_LOG_TRACE("unregister prefix: " << ribEntry);
+ NFD_LOG_TRACE("unregister prefix: " << faceEntry);
m_nfdController.start<ndn::nfd::FibRemoveNextHopCommand>(
ControlParameters()
- .setName(ribEntry.name)
- .setFaceId(ribEntry.faceId),
- bind(&RibManager::onUnRegSuccess, this, request, parameters, ribEntry),
- bind(&RibManager::onCommandError, this, _1, _2, request, ribEntry));
+ .setName(parameters.getName())
+ .setFaceId(faceEntry.faceId),
+ bind(&RibManager::onUnRegSuccess, this, request, parameters, faceEntry),
+ bind(&RibManager::onCommandError, this, _1, _2, request, faceEntry));
}
void
@@ -316,7 +314,7 @@
void
RibManager::onCommandError(uint32_t code, const std::string& error,
const shared_ptr<const Interest>& request,
- const RibEntry& ribEntry)
+ const FaceEntry& faceEntry)
{
NFD_LOG_ERROR("NFD returned an error: " << error << " (code: " << code << ")");
@@ -336,13 +334,13 @@
}
sendResponse(request->getName(), response);
- m_managedRib.erase(ribEntry);
+ m_managedRib.erase(request->getName(), faceEntry);
}
void
RibManager::onRegSuccess(const shared_ptr<const Interest>& request,
const ControlParameters& parameters,
- const RibEntry& ribEntry)
+ const FaceEntry& faceEntry)
{
ControlResponse response;
@@ -350,7 +348,7 @@
response.setText("Success");
response.setBody(parameters.wireEncode());
- NFD_LOG_TRACE("onRegSuccess: registered " << ribEntry);
+ NFD_LOG_TRACE("onRegSuccess: registered " << faceEntry);
sendResponse(request->getName(), response);
}
@@ -359,7 +357,7 @@
void
RibManager::onUnRegSuccess(const shared_ptr<const Interest>& request,
const ControlParameters& parameters,
- const RibEntry& ribEntry)
+ const FaceEntry& faceEntry)
{
ControlResponse response;
@@ -367,10 +365,10 @@
response.setText("Success");
response.setBody(parameters.wireEncode());
- NFD_LOG_TRACE("onUnRegSuccess: unregistered " << ribEntry);
+ NFD_LOG_TRACE("onUnRegSuccess: unregistered " << faceEntry);
sendResponse(request->getName(), response);
- m_managedRib.erase(ribEntry);
+ m_managedRib.erase(request->getName(), faceEntry);
}
void
diff --git a/rib/rib-manager.hpp b/rib/rib-manager.hpp
index bcd43d7..7721436 100644
--- a/rib/rib-manager.hpp
+++ b/rib/rib-manager.hpp
@@ -1,12 +1,12 @@
/* -*- 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,
- * The University of Memphis
+ * 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,
+ * The University of Memphis
*
* This file is part of NFD (Named Data Networking Forwarding Daemon).
* See AUTHORS.md for complete list of NFD authors and contributors.
@@ -21,7 +21,7 @@
*
* 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/>.
- **/
+ */
#ifndef NFD_RIB_RIB_MANAGER_HPP
#define NFD_RIB_RIB_MANAGER_HPP
@@ -110,17 +110,17 @@
void
onCommandError(uint32_t code, const std::string& error,
const shared_ptr<const Interest>& request,
- const RibEntry& ribEntry);
+ const FaceEntry& faceEntry);
void
onRegSuccess(const shared_ptr<const Interest>& request,
const ControlParameters& parameters,
- const RibEntry& ribEntry);
+ const FaceEntry& faceEntry);
void
onUnRegSuccess(const shared_ptr<const Interest>& request,
const ControlParameters& parameters,
- const RibEntry& ribEntry);
+ const FaceEntry& faceEntry);
void
onNrdCommandPrefixAddNextHopSuccess(const Name& prefix);
diff --git a/rib/rib.cpp b/rib/rib.cpp
index 4dc4175..f47d840 100644
--- a/rib/rib.cpp
+++ b/rib/rib.cpp
@@ -1,12 +1,12 @@
/* -*- 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,
- * The University of Memphis
+ * 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,
+ * The University of Memphis
*
* This file is part of NFD (Named Data Networking Forwarding Daemon).
* See AUTHORS.md for complete list of NFD authors and contributors.
@@ -21,7 +21,7 @@
*
* 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 "rib.hpp"
@@ -29,6 +29,7 @@
namespace rib {
Rib::Rib()
+ : m_nItems(0)
{
}
@@ -37,84 +38,270 @@
{
}
-static inline bool
-compareNameFaceProtocol(const RibEntry& entry1, const RibEntry& entry2)
-{
- return (entry1.name == entry2.name &&
- entry1.faceId == entry2.faceId &&
- entry1.origin == entry2.origin);
-}
-
-
Rib::const_iterator
-Rib::find(const RibEntry& entry) const
+Rib::find(const Name& prefix) const
{
- RibTable::const_iterator it = std::find_if(m_rib.begin(), m_rib.end(),
- bind(&compareNameFaceProtocol, _1, entry));
- if (it == m_rib.end())
+ return m_rib.find(prefix);
+}
+
+shared_ptr<FaceEntry>
+Rib::find(const Name& prefix, const FaceEntry& face) const
+{
+ RibTable::const_iterator ribIt = m_rib.find(prefix);
+
+ // Name prefix exists
+ if (ribIt != m_rib.end())
{
- return end();
+ shared_ptr<RibEntry> entry(ribIt->second);
+
+ RibEntry::const_iterator faceIt = std::find_if(entry->begin(), entry->end(),
+ bind(&compareFaceIdAndOrigin, _1, face));
+
+ if (faceIt != entry->end())
+ {
+ return make_shared<FaceEntry>(*faceIt);
+ }
}
- else
- return it;
+
+ return shared_ptr<FaceEntry>();
}
void
-Rib::insert(const RibEntry& entry)
+Rib::insert(const Name& prefix, const FaceEntry& face)
{
- RibTable::iterator it = std::find_if(m_rib.begin(), m_rib.end(),
- bind(&compareNameFaceProtocol, _1, entry));
- if (it == m_rib.end())
+ RibTable::iterator ribIt = m_rib.find(prefix);
+
+ // Name prefix exists
+ if (ribIt != m_rib.end())
{
- m_rib.push_front(entry);
+ shared_ptr<RibEntry> entry(ribIt->second);
+
+ RibEntry::iterator faceIt = std::find_if(entry->getFaces().begin(),
+ entry->getFaces().end(),
+ bind(&compareFaceIdAndOrigin, _1, face));
+
+ if (faceIt == entry->end())
+ {
+ // New face
+ entry->insertFace(face);
+ m_nItems++;
+
+ // Register with face lookup table
+ m_faceMap[face.faceId].push_back(entry);
+ }
+ else
+ {
+ // Entry exists, update other fields
+ faceIt->flags = face.flags;
+ faceIt->cost = face.cost;
+ faceIt->expires = face.expires;
+ }
}
- else
+ else // New name prefix
{
- // entry exist, update other fields
- it->flags = entry.flags;
- it->cost = entry.cost;
- it->expires = entry.expires;
+ shared_ptr<RibEntry> entry(make_shared<RibEntry>(RibEntry()));
+
+ m_rib[prefix] = entry;
+ m_nItems++;
+
+ entry->setName(prefix);
+ entry->insertFace(face);
+
+ // Find prefix's parent
+ shared_ptr<RibEntry> parent = findParent(prefix);
+
+ // Add self to parent's children
+ if (static_cast<bool>(parent))
+ {
+ parent->addChild(entry);
+ }
+
+ RibEntryList children = findDescendants(prefix);
+
+ for (std::list<shared_ptr<RibEntry> >::iterator child = children.begin();
+ child != children.end(); ++child)
+ {
+ if ((*child)->getParent() == parent)
+ {
+ // Remove child from parent and inherit parent's child
+ if (static_cast<bool>(parent))
+ {
+ parent->removeChild((*child));
+ }
+
+ entry->addChild((*child));
+ }
+ }
+
+ // Register with face lookup table
+ m_faceMap[face.faceId].push_back(entry);
}
}
void
-Rib::erase(const RibEntry& entry)
+Rib::erase(const Name& prefix, const FaceEntry& face)
{
- RibTable::iterator it = std::find_if(m_rib.begin(), m_rib.end(),
- bind(&compareNameFaceProtocol, _1, entry));
+ RibTable::iterator ribIt = m_rib.find(prefix);
+
+ // Name prefix exists
+ if (ribIt != m_rib.end())
+ {
+ shared_ptr<RibEntry> entry(ribIt->second);
+
+ if (entry->eraseFace(face))
+ {
+ m_nItems--;
+
+ // If this RibEntry no longer has this faceId, unregister from face lookup table
+ if (!entry->hasFaceId(face.faceId))
+ {
+ m_faceMap[face.faceId].remove(entry);
+ }
+
+ // If a RibEntry's facelist is empty, remove it from the tree
+ if (entry->getFaces().size() == 0)
+ {
+ eraseEntry(ribIt);
+ }
+ }
+ }
+}
+
+void
+Rib::erase(const uint64_t faceId)
+{
+ FaceLookupTable::iterator lookupIt = m_faceMap.find(faceId);
+
+ // No RIB entries have this face
+ if (lookupIt == m_faceMap.end())
+ {
+ return;
+ }
+
+ RibEntryList& ribEntries = lookupIt->second;
+
+ // For each RIB entry that has faceId, remove the face from the entry
+ for (RibEntryList::iterator entryIt = ribEntries.begin(); entryIt != ribEntries.end(); ++entryIt)
+ {
+ shared_ptr<RibEntry> entry = *entryIt;
+
+ // Find the faces in the entry
+ for (RibEntry::iterator faceIt = entry->begin(); faceIt != entry->end(); ++faceIt)
+ {
+ if (faceIt->faceId == faceId)
+ {
+ faceIt = entry->eraseFace(faceIt);
+ }
+ }
+
+ // If a RibEntry's facelist is empty, remove it from the tree
+ if (entry->getFaces().size() == 0)
+ {
+ eraseEntry(m_rib.find(entry->getName()));
+ }
+ }
+
+ // Face no longer exists, remove from face lookup table
+ FaceLookupTable::iterator entryToDelete = m_faceMap.find(faceId);
+
+ if (entryToDelete != m_faceMap.end())
+ {
+ m_faceMap.erase(entryToDelete);
+ }
+}
+
+shared_ptr<RibEntry>
+Rib::findParent(const Name& prefix) const
+{
+ for (int i = prefix.size() - 1; i >= 0; i--)
+ {
+ RibTable::const_iterator it = m_rib.find(prefix.getPrefix(i));
+ if (it != m_rib.end())
+ {
+ return (it->second);
+ }
+ }
+
+ return shared_ptr<RibEntry>();
+}
+
+std::list<shared_ptr<RibEntry> >
+Rib::findDescendants(const Name& prefix) const
+{
+ std::list<shared_ptr<RibEntry> > children;
+
+ RibTable::const_iterator it = m_rib.find(prefix);
+
if (it != m_rib.end())
{
- m_rib.erase(it);
+ ++it;
+ for (; it != m_rib.end(); ++it)
+ {
+ if (prefix.isPrefixOf(it->first))
+ {
+ children.push_back((it->second));
+ }
+ else
+ {
+ break;
+ }
+ }
}
+
+ return children;
}
-void
-Rib::erase(uint64_t faceId)
+Rib::RibTable::iterator
+Rib::eraseEntry(RibTable::iterator it)
{
- // Keep it simple for now, with Trie this will be changed.
- RibTable::iterator it = m_rib.begin();
- while (it != m_rib.end())
- {
- if (it->faceId == faceId)
- it = m_rib.erase(it);
- else
- ++it;
- }
+ // Entry does not exist
+ if (it == m_rib.end())
+ {
+ return m_rib.end();
+ }
+
+ shared_ptr<RibEntry> entry(it->second);
+
+ shared_ptr<RibEntry> parent = entry->getParent();
+
+ // Remove self from parent's children
+ if (static_cast<bool>(parent))
+ {
+ parent->removeChild(entry);
+ }
+
+ std::list<shared_ptr<RibEntry> > children = entry->getChildren();
+
+ for (RibEntryList::iterator child = children.begin(); child != children.end(); ++child)
+ {
+ // Remove children from self
+ entry->removeChild(*child);
+
+ // Update parent's children
+ if (static_cast<bool>(parent))
+ {
+ parent->addChild(*child);
+ }
+ }
+
+ // Must save and advance iterator to return a valid iterator
+ RibTable::iterator nextIt = it;
+ nextIt++;
+
+ m_rib.erase(it);
+
+ return nextIt;
}
std::ostream&
-operator<<(std::ostream& os, const RibEntry& entry)
+operator<<(std::ostream& os, const Rib& rib)
{
- os << "RibEntry("
- << "name: " << entry.name
- << " faceid: " << entry.faceId
- << " origin: " << entry.origin
- << " cost: " << entry.cost
- << " flags: " << entry.flags
- << " expires in: " << (entry.expires - time::steady_clock::now())
- << ")";
+ for (Rib::RibTable::const_iterator it = rib.begin(); it != rib.end(); ++it)
+ {
+ os << *(it->second) << "\n";
+ }
return os;
}
diff --git a/rib/rib.hpp b/rib/rib.hpp
index 7c19c9f..37136bc 100644
--- a/rib/rib.hpp
+++ b/rib/rib.hpp
@@ -1,12 +1,12 @@
/* -*- 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,
- * The University of Memphis
+ * 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,
+ * The University of Memphis
*
* This file is part of NFD (Named Data Networking Forwarding Daemon).
* See AUTHORS.md for complete list of NFD authors and contributors.
@@ -21,61 +21,46 @@
*
* 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/>.
- **/
+ */
#ifndef NFD_RIB_RIB_HPP
#define NFD_RIB_RIB_HPP
#include "common.hpp"
+#include "rib-entry.hpp"
#include <ndn-cxx/management/nfd-control-command.hpp>
namespace nfd {
namespace rib {
-class RibEntry
-{
-public:
- RibEntry()
- : faceId(0)
- , origin(0)
- , flags(0)
- , cost(0)
- , expires(time::steady_clock::TimePoint::min())
- {
- }
-
-public:
- Name name;
- uint64_t faceId;
- uint64_t origin;
- uint64_t flags;
- uint64_t cost;
- time::steady_clock::TimePoint expires;
-};
-
/** \brief represents the RIB
*/
class Rib : noncopyable
{
public:
- typedef std::list<RibEntry> RibTable;
+ typedef std::list<shared_ptr<RibEntry> > RibEntryList;
+ typedef std::map<Name, shared_ptr<RibEntry> > RibTable;
typedef RibTable::const_iterator const_iterator;
+ typedef std::map<uint64_t, std::list<shared_ptr<RibEntry> > > FaceLookupTable;
Rib();
~Rib();
const_iterator
- find(const RibEntry& entry) const;
+ find(const Name& prefix) const;
+
+ shared_ptr<FaceEntry>
+ find(const Name& prefix, const FaceEntry& face) const;
void
- insert(const RibEntry& entry);
+ insert(const Name& prefix, const FaceEntry& face);
void
- erase(const RibEntry& entry);
+ erase(const Name& prefix, const FaceEntry& face);
void
- erase(uint64_t faceId);
+ erase(const uint64_t faceId);
const_iterator
begin() const;
@@ -86,13 +71,29 @@
size_t
size() const;
- size_t
+ bool
empty() const;
+
+ shared_ptr<RibEntry>
+ findParent(const Name& prefix) const;
+
+ /** \brief finds namespaces under the passed prefix
+ * \return{ a list of entries which are under the passed prefix }
+ */
+ std::list<shared_ptr<RibEntry> >
+ findDescendants(const Name& prefix) const;
+
+ RibTable::iterator
+ eraseEntry(RibTable::iterator it);
+
+ void
+ eraseEntry(const Name& name);
+
private:
- // Note: Taking a list right now. A Trie will be used later to store
- // prefixes
RibTable m_rib;
+ FaceLookupTable m_faceMap;
+ size_t m_nItems;
};
inline Rib::const_iterator
@@ -110,18 +111,24 @@
inline size_t
Rib::size() const
{
- return m_rib.size();
+ return m_nItems;
}
-inline size_t
+inline bool
Rib::empty() const
{
return m_rib.empty();
}
std::ostream&
+operator<<(std::ostream& os, const FaceEntry& entry);
+
+std::ostream&
operator<<(std::ostream& os, const RibEntry& entry);
+std::ostream&
+operator<<(std::ostream& os, const Rib& rib);
+
} // namespace rib
} // namespace nfd
diff --git a/tests/rib/rib.cpp b/tests/rib/rib.cpp
index a8a0110..c3b0eab 100644
--- a/tests/rib/rib.cpp
+++ b/tests/rib/rib.cpp
@@ -1,12 +1,12 @@
/* -*- 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,
- * The University of Memphis
+ * 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,
+ * The University of Memphis
*
* This file is part of NFD (Named Data Networking Forwarding Daemon).
* See AUTHORS.md for complete list of NFD authors and contributors.
@@ -21,7 +21,7 @@
*
* 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 "rib/rib.hpp"
@@ -33,62 +33,296 @@
BOOST_FIXTURE_TEST_SUITE(Rib, nfd::tests::BaseFixture)
+BOOST_AUTO_TEST_CASE(RibEntry)
+{
+ rib::RibEntry entry;
+
+ rib::FaceEntry face1;
+ face1.faceId = 1;
+ face1.origin = 0;
+
+ entry.insertFace(face1);
+ BOOST_CHECK_EQUAL(entry.getFaces().size(), 1);
+
+ FaceEntry face2;
+ face2.faceId = 1;
+ face2.origin = 128;
+
+ entry.insertFace(face2);
+ BOOST_CHECK_EQUAL(entry.getFaces().size(), 2);
+
+ entry.eraseFace(face1);
+ BOOST_CHECK_EQUAL(entry.getFaces().size(), 1);
+
+ BOOST_CHECK(entry.findFace(face1) == entry.getFaces().end());
+ BOOST_CHECK(entry.findFace(face2) != entry.getFaces().end());
+
+ entry.insertFace(face2);
+ BOOST_CHECK_EQUAL(entry.getFaces().size(), 1);
+
+ BOOST_CHECK_EQUAL(entry.eraseFace(face1), false);
+}
+
+BOOST_AUTO_TEST_CASE(Rib_Parent)
+{
+ rib::Rib rib;
+
+ FaceEntry root;
+ Name name1("/");
+ root.faceId = 1;
+ root.origin = 20;
+ rib.insert(name1, root);
+
+ FaceEntry entry1;
+ Name name2("/hello");
+ entry1.faceId = 2;
+ entry1.origin = 20;
+ rib.insert(name2, entry1);
+
+ FaceEntry entry2;
+ Name name3("/hello/world");
+ entry2.faceId = 3;
+ entry2.origin = 20;
+ rib.insert(name3, entry2);
+
+ shared_ptr<rib::RibEntry> ribEntry = rib.findParent(name3);
+ BOOST_REQUIRE(static_cast<bool>(ribEntry));
+ BOOST_CHECK_EQUAL(ribEntry->getFaces().front().faceId, 2);
+
+ ribEntry = rib.findParent(name2);
+ BOOST_REQUIRE(static_cast<bool>(ribEntry));
+ BOOST_CHECK_EQUAL(ribEntry->getFaces().front().faceId, 1);
+
+ FaceEntry entry3;
+ Name name4("/hello/test/foo/bar");
+ entry2.faceId = 3;
+ entry2.origin = 20;
+ rib.insert(name4, entry3);
+
+ ribEntry = rib.findParent(name4);
+ BOOST_CHECK(ribEntry != shared_ptr<rib::RibEntry>());
+ BOOST_CHECK(ribEntry->getFaces().front().faceId == 2);
+}
+
+BOOST_AUTO_TEST_CASE(Rib_Children)
+{
+ rib::Rib rib;
+
+ FaceEntry entry1;
+ Name name1("/");
+ entry1.faceId = 1;
+ entry1.origin = 20;
+ rib.insert(name1, entry1);
+
+ FaceEntry entry2;
+ Name name2("/hello/world");
+ entry2.faceId = 2;
+ entry2.origin = 20;
+ rib.insert(name2, entry2);
+
+ FaceEntry entry3;
+ Name name3("/hello/test/foo/bar");
+ entry3.faceId = 3;
+ entry3.origin = 20;
+ rib.insert(name3, entry3);
+
+ BOOST_CHECK_EQUAL((rib.find(name1)->second)->getChildren().size(), 2);
+ BOOST_CHECK_EQUAL((rib.find(name2)->second)->getChildren().size(), 0);
+ BOOST_CHECK_EQUAL((rib.find(name3)->second)->getChildren().size(), 0);
+
+ FaceEntry entry4;
+ Name name4("/hello");
+ entry4.faceId = 4;
+ entry4.origin = 20;
+ rib.insert(name4, entry4);
+
+ BOOST_CHECK_EQUAL((rib.find(name1)->second)->getChildren().size(), 1);
+ BOOST_CHECK_EQUAL((rib.find(name2)->second)->getChildren().size(), 0);
+ BOOST_CHECK_EQUAL((rib.find(name3)->second)->getChildren().size(), 0);
+ BOOST_CHECK_EQUAL((rib.find(name4)->second)->getChildren().size(), 2);
+
+ BOOST_CHECK_EQUAL((rib.find(name1)->second)->getChildren().front()->getName(), "/hello");
+ BOOST_CHECK_EQUAL((rib.find(name4)->second)->getParent()->getName(), "/");
+
+ BOOST_REQUIRE(static_cast<bool>((rib.find(name2)->second)->getParent()));
+ BOOST_CHECK_EQUAL((rib.find(name2)->second)->getParent()->getName(), name4);
+ BOOST_REQUIRE(static_cast<bool>((rib.find(name3)->second)->getParent()));
+ BOOST_CHECK_EQUAL((rib.find(name3)->second)->getParent()->getName(), name4);
+}
+
+BOOST_AUTO_TEST_CASE(Rib_EraseFace)
+{
+ rib::Rib rib;
+
+ FaceEntry entry1;
+ Name name1("/");
+ entry1.faceId = 1;
+ entry1.origin = 20;
+ rib.insert(name1, entry1);
+
+ FaceEntry entry2;
+ Name name2("/hello/world");
+ entry2.faceId = 2;
+ entry2.origin = 20;
+ rib.insert(name2, entry2);
+
+ FaceEntry entry3;
+ Name name3("/hello/world");
+ entry3.faceId = 1;
+ entry3.origin = 20;
+ rib.insert(name3, entry3);
+
+ FaceEntry entry4;
+ Name name4("/not/inserted");
+ entry4.faceId = 1;
+ entry4.origin = 20;
+
+ rib.erase(name4, entry4);
+ rib.erase(name1, entry1);
+
+ BOOST_CHECK(rib.find(name1) == rib.end());
+ BOOST_CHECK_EQUAL((rib.find(name2)->second)->getFaces().size(), 2);
+
+ rib.erase(name2, entry2);
+
+ BOOST_CHECK_EQUAL((rib.find(name2)->second)->getFaces().size(), 1);
+ BOOST_CHECK_EQUAL((rib.find(name2)->second)->getFaces().front().faceId, 1);
+
+ rib.erase(name3, entry3);
+
+ BOOST_CHECK(rib.find(name2) == rib.end());
+
+ rib.erase(name4, entry4);
+}
+
+BOOST_AUTO_TEST_CASE(Rib_EraseRibEntry)
+{
+ rib::Rib rib;
+
+ FaceEntry entry1;
+ Name name1("/");
+ entry1.faceId = 1;
+ entry1.origin = 20;
+ rib.insert(name1, entry1);
+
+ FaceEntry entry2;
+ Name name2("/hello");
+ entry2.faceId = 2;
+ entry2.origin = 20;
+ rib.insert(name2, entry2);
+
+ FaceEntry entry3;
+ Name name3("/hello/world");
+ entry3.faceId = 1;
+ entry3.origin = 20;
+ rib.insert(name3, entry3);
+
+ shared_ptr<rib::RibEntry> ribEntry1 = rib.find(name1)->second;
+ shared_ptr<rib::RibEntry> ribEntry2 = rib.find(name2)->second;
+ shared_ptr<rib::RibEntry> ribEntry3 = rib.find(name3)->second;
+
+ BOOST_CHECK(ribEntry1->getChildren().front() == ribEntry2);
+ BOOST_CHECK(ribEntry3->getParent() == ribEntry2);
+
+ rib.erase(name2, entry2);
+ BOOST_CHECK(ribEntry1->getChildren().front() == ribEntry3);
+ BOOST_CHECK(ribEntry3->getParent() == ribEntry1);
+}
+
+BOOST_AUTO_TEST_CASE(Rib_EraseByFaceId)
+{
+ rib::Rib rib;
+
+ FaceEntry entry1;
+ Name name1("/");
+ entry1.faceId = 1;
+ entry1.origin = 20;
+ rib.insert(name1, entry1);
+
+ FaceEntry entry2;
+ Name name2("/hello/world");
+ entry2.faceId = 2;
+ entry2.origin = 20;
+ rib.insert(name2, entry2);
+
+ FaceEntry entry3;
+ Name name3("/hello/world");
+ entry3.faceId = 1;
+ entry3.origin = 20;
+ rib.insert(name3, entry3);
+
+ rib.erase(1);
+ BOOST_CHECK(rib.find(name1) == rib.end());
+ BOOST_CHECK_EQUAL((rib.find(name2)->second)->getFaces().size(), 1);
+
+ rib.erase(3);
+ BOOST_CHECK_EQUAL((rib.find(name2)->second)->getFaces().size(), 1);
+
+ rib.erase(2);
+ BOOST_CHECK(rib.find(name2) == rib.end());
+
+ rib.erase(3);
+}
+
BOOST_AUTO_TEST_CASE(Basic)
{
rib::Rib rib;
- RibEntry entry1;
- entry1.name = "/hello/world";
+ FaceEntry entry1;
+ Name name1("/hello/world");
entry1.faceId = 1;
entry1.origin = 20;
entry1.cost = 10;
entry1.flags = ndn::nfd::ROUTE_FLAG_CHILD_INHERIT | ndn::nfd::ROUTE_FLAG_CAPTURE;
entry1.expires = time::steady_clock::now() + time::milliseconds(1500);
- rib.insert(entry1);
+ rib.insert(name1, entry1);
BOOST_CHECK_EQUAL(rib.size(), 1);
- rib.insert(entry1);
+ rib.insert(name1, entry1);
BOOST_CHECK_EQUAL(rib.size(), 1);
- RibEntry entry2;
- entry2.name = "/hello/world";
+ FaceEntry entry2;
+ Name name2("/hello/world");
entry2.faceId = 1;
entry2.origin = 20;
entry2.cost = 100;
entry2.flags = ndn::nfd::ROUTE_FLAG_CHILD_INHERIT;
entry2.expires = time::steady_clock::now() + time::seconds(0);
- rib.insert(entry2);
+ rib.insert(name2, entry2);
BOOST_CHECK_EQUAL(rib.size(), 1);
entry2.faceId = 2;
- rib.insert(entry2);
+ rib.insert(name2, entry2);
BOOST_CHECK_EQUAL(rib.size(), 2);
- entry2.name = "/foo/bar";
- rib.insert(entry2);
+ BOOST_CHECK(rib.find(name1)->second->hasFaceId(entry1.faceId));
+ BOOST_CHECK(rib.find(name1)->second->hasFaceId(entry2.faceId));
+
+ Name name3("/foo/bar");
+ rib.insert(name3, entry2);
BOOST_CHECK_EQUAL(rib.size(), 3);
entry2.origin = 1;
- rib.insert(entry2);
+ rib.insert(name3, entry2);
BOOST_CHECK_EQUAL(rib.size(), 4);
- rib.erase(entry2);
+ rib.erase(name3, entry2);
BOOST_CHECK_EQUAL(rib.size(), 3);
- entry2.name = "/hello/world";
- rib.erase(entry2);
+ Name name4("/hello/world");
+ rib.erase(name4, entry2);
BOOST_CHECK_EQUAL(rib.size(), 3);
entry2.origin = 20;
- rib.erase(entry2);
+ rib.erase(name4, entry2);
BOOST_CHECK_EQUAL(rib.size(), 2);
- BOOST_CHECK(rib.find(entry2) == rib.end());
- BOOST_CHECK(rib.find(entry1) != rib.end());
+ BOOST_CHECK(rib.find(name2, entry2) == shared_ptr<rib::FaceEntry>());
+ BOOST_CHECK(rib.find(name1, entry1) != shared_ptr<rib::FaceEntry>());
- rib.erase(entry1);
+ rib.erase(name1, entry1);
BOOST_CHECK_EQUAL(rib.size(), 1);
}