rib: Implement RIB as trie
refs: #1271
Change-Id: Idbd6d4d67f8a88b474ea0b20280c79e367bc98e5
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