table: advisory limit of NameTree depth
refs #4262
Change-Id: I691f9615e2b8a3b146a683919c6d5833f53f6122
diff --git a/daemon/table/name-tree-hashtable.cpp b/daemon/table/name-tree-hashtable.cpp
index 67eafcd..421f298 100644
--- a/daemon/table/name-tree-hashtable.cpp
+++ b/daemon/table/name-tree-hashtable.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2016, Regents of the University of California,
+/*
+ * Copyright (c) 2014-2017, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -54,7 +54,7 @@
/** \brief a type with compute static method to compute hash value from a raw buffer
*/
-typedef std::conditional<(sizeof(HashValue) > 4), Hash64, Hash32>::type HashFunc;
+using HashFunc = std::conditional<(sizeof(HashValue) > 4), Hash64, Hash32>::type;
HashValue
computeHash(const Name& name, ssize_t prefixLen)
@@ -70,17 +70,19 @@
}
HashSequence
-computeHashes(const Name& name)
+computeHashes(const Name& name, ssize_t prefixLen)
{
name.wireEncode(); // ensure wire buffer exists
+ size_t last = prefixLen < 0 ? name.size() : std::min(static_cast<size_t>(prefixLen), name.size());
HashSequence seq;
- seq.reserve(name.size() + 1);
+ seq.reserve(last + 1);
HashValue h = 0;
seq.push_back(h);
- for (const name::Component& comp : name) {
+ for (size_t i = 0; i < last; ++i) {
+ const name::Component& comp = name[i];
h ^= HashFunc::compute(comp.wire(), comp.size());
seq.push_back(h);
}
diff --git a/daemon/table/name-tree-hashtable.hpp b/daemon/table/name-tree-hashtable.hpp
index 1ec2d55..d7ca6a6 100644
--- a/daemon/table/name-tree-hashtable.hpp
+++ b/daemon/table/name-tree-hashtable.hpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2016, Regents of the University of California,
+/*
+ * Copyright (c) 2014-2017, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -35,12 +35,12 @@
/** \brief a single hash value
*/
-typedef size_t HashValue;
+using HashValue = size_t;
/** \brief a sequence of hash values
* \sa computeHashes
*/
-typedef std::vector<HashValue> HashSequence;
+using HashSequence = std::vector<HashValue>;
/** \brief computes a single hash value
* \param name base name
@@ -51,10 +51,13 @@
computeHash(const Name& name, ssize_t prefixLen = -1);
/** \brief computes hash values for each prefix of name
+ * \param name base name
+ * \param prefixLen if non-negative, compute up to the first \p prefixLen name components;
+ * if negative, compute all hash values
* \return a hash sequence, where the i-th hash value equals computeHash(name, i)
*/
HashSequence
-computeHashes(const Name& name);
+computeHashes(const Name& name, ssize_t prefixLen = -1);
/** \brief a hashtable node
*
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index db0e3ff..65cafd7 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -41,15 +41,16 @@
}
Entry&
-NameTree::lookup(const Name& name)
+NameTree::lookup(const Name& name, bool enforceMaxDepth)
{
NFD_LOG_TRACE("lookup " << name);
+ size_t depth = enforceMaxDepth ? getMaxDepth() : name.size();
- HashSequence hashes = computeHashes(name);
+ HashSequence hashes = computeHashes(name, depth);
const Node* node = nullptr;
Entry* parent = nullptr;
- for (size_t prefixLen = 0; prefixLen <= name.size(); ++prefixLen) {
+ for (size_t prefixLen = 0; prefixLen <= depth; ++prefixLen) {
bool isNew = false;
std::tie(node, isNew) = m_ht.insert(name, prefixLen, hashes);
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index b5bcc2b..6d04821 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -40,6 +40,22 @@
NameTree(size_t nBuckets = 1024);
public: // information
+ /** \brief Maximum depth of the name tree.
+ *
+ * Calling NameTree::lookup with a name with many components would cause the creation of many
+ * NameTree entries, which could take very long time. This constant limits the maximum number of
+ * name components in the name of a NameTree entry. Thus, it limits the number of NameTree
+ * entries created from a long name, bounding the processing complexity.
+ *
+ * This constant is currently advisory. It is enforced in NameTree::lookup only if
+ * \p enforceMaxDepth is set to true. This will become mandatory later.
+ */
+ static size_t
+ getMaxDepth()
+ {
+ return 32;
+ }
+
/** \return number of name tree entries
*/
size_t
@@ -69,12 +85,13 @@
public: // mutation
/** \brief find or insert an entry with specified name
* \param name a name prefix
+ * \param enforceMaxDepth if true, use \p name.getPrefix(getMaxDepth()) in place of \p name
* \return an entry with \p name
* \post an entry with \p name and all ancestors are created
* \note Existing iterators are unaffected.
*/
Entry&
- lookup(const Name& name);
+ lookup(const Name& name, bool enforceMaxDepth = false);
/** \brief equivalent to .lookup(fibEntry.getPrefix())
* \param fibEntry a FIB entry attached to this name tree, or Fib::s_emptyEntry
@@ -190,7 +207,7 @@
const EntrySelector& entrySelector = AnyEntry()) const;
public: // enumeration
- typedef Iterator const_iterator;
+ using const_iterator = Iterator;
/** \brief enumerate all entries
* \return a range where every entry matches \p entrySelector
diff --git a/tests/daemon/table/name-tree.t.cpp b/tests/daemon/table/name-tree.t.cpp
index 127056d..8b7307a 100644
--- a/tests/daemon/table/name-tree.t.cpp
+++ b/tests/daemon/table/name-tree.t.cpp
@@ -1,6 +1,6 @@
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/**
- * Copyright (c) 2014-2016, Regents of the University of California,
+/*
+ * Copyright (c) 2014-2017, Regents of the University of California,
* Arizona Board of Regents,
* Colorado State University,
* University Pierre & Marie Curie, Sorbonne University,
@@ -47,6 +47,9 @@
prefix.wireEncode();
HashSequence hashes = computeHashes(prefix);
BOOST_CHECK_EQUAL(hashes.size(), prefix.size() + 1);
+
+ hashes = computeHashes(prefix, 2);
+ BOOST_CHECK_EQUAL(hashes.size(), 3);
}
BOOST_AUTO_TEST_SUITE(Hashtable)
@@ -298,7 +301,7 @@
// lookup
- Name nameABC("ndn:/a/b/c");
+ Name nameABC("/a/b/c");
Entry& npeABC = nt.lookup(nameABC);
BOOST_CHECK_EQUAL(nt.size(), 4);
@@ -414,6 +417,20 @@
BOOST_CHECK_EQUAL(nt.size(), 8);
}
+BOOST_AUTO_TEST_CASE(LongName)
+{
+ Name name;
+ for (int i = 0; i < 2000; ++i) {
+ name.append("X");
+ }
+
+ NameTree nt;
+
+ Entry& entry1 = nt.lookup(name, true);
+ BOOST_CHECK_EQUAL(entry1.getName().size(), NameTree::getMaxDepth());
+ BOOST_CHECK_EQUAL(nt.size(), NameTree::getMaxDepth() + 1);
+}
+
/** \brief verify a NameTree enumeration contains expected entries
*
* Example: