table: delete deprecated functions in NameTree
NameTree::eraseEntryIfEmpty is renamed to eraseIfEmpty;
the deprecated overload that accepts shared_ptr<name_tree::Entry> is deleted.
name_tree::Entry::getPrefix is deleted in favor of getName.
This commit also improves Doxygen in NameTree class.
refs #3687
Change-Id: Ia98ca676ce6d3bc7b2e97328adccac911c8167d7
diff --git a/daemon/table/cleanup.cpp b/daemon/table/cleanup.cpp
index 0ba0725..8317099 100644
--- a/daemon/table/cleanup.cpp
+++ b/daemon/table/cleanup.cpp
@@ -44,7 +44,7 @@
}
if (nte.getFibEntry() == nullptr && !nte.hasPitEntries()) {
- maybeEmptyNtes.emplace(nte.getPrefix().size(), const_pointer_cast<name_tree::Entry>(nte.shared_from_this()));
+ maybeEmptyNtes.emplace(nte.getName().size(), const_pointer_cast<name_tree::Entry>(nte.shared_from_this()));
}
}
@@ -53,7 +53,7 @@
shared_ptr<name_tree::Entry> nte = i->second.lock();
// nte may have been erased when its last child is erased
if (nte != nullptr) {
- nt.eraseEntryIfEmpty(nte);
+ nt.eraseIfEmpty(nte.get());
}
}
}
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index 890bbbe..d18ce94 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -136,7 +136,7 @@
nte->setFibEntry(nullptr);
if (canDeleteNte) {
- m_nameTree.eraseEntryIfEmpty(nte);
+ m_nameTree.eraseIfEmpty(nte.get());
}
--m_nItems;
}
diff --git a/daemon/table/measurements.cpp b/daemon/table/measurements.cpp
index c939b72..d93cc91 100644
--- a/daemon/table/measurements.cpp
+++ b/daemon/table/measurements.cpp
@@ -45,7 +45,7 @@
return *entry;
}
- nte.setMeasurementsEntry(make_unique<Entry>(nte.getPrefix()));
+ nte.setMeasurementsEntry(make_unique<Entry>(nte.getName()));
++m_nItems;
entry = nte.getMeasurementsEntry();
@@ -165,7 +165,7 @@
BOOST_ASSERT(nte != nullptr);
nte->setMeasurementsEntry(nullptr);
- m_nameTree.eraseEntryIfEmpty(nte);
+ m_nameTree.eraseIfEmpty(nte.get());
--m_nItems;
}
diff --git a/daemon/table/name-tree-entry.hpp b/daemon/table/name-tree-entry.hpp
index 9875891..576139c 100644
--- a/daemon/table/name-tree-entry.hpp
+++ b/daemon/table/name-tree-entry.hpp
@@ -48,13 +48,6 @@
return m_name;
}
- /// \deprecated
- const Name&
- getPrefix() const
- {
- return this->getName();
- }
-
/** \return entry of getName().getPrefix(-1)
* \retval nullptr this entry is the root entry, i.e. getName() == Name()
*/
diff --git a/daemon/table/name-tree-iterator.cpp b/daemon/table/name-tree-iterator.cpp
index 9832dcd..e62060a 100644
--- a/daemon/table/name-tree-iterator.cpp
+++ b/daemon/table/name-tree-iterator.cpp
@@ -90,12 +90,12 @@
return os << "uninitialized";
}
- os << "entry=" << i.m_entry->getPrefix();
+ os << "entry=" << i.m_entry->getName();
if (i.m_ref == nullptr) {
os << " ref=null";
}
else {
- os << " ref=" << i.m_ref->getPrefix();
+ os << " ref=" << i.m_ref->getName();
}
os << " state=" << i.m_state;
return os;
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index bbe5784..993a58a 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -77,12 +77,12 @@
return nullptr;
}
- if (nte->getPrefix().size() == pitEntry.getName().size()) {
+ if (nte->getName().size() == pitEntry.getName().size()) {
return nte;
}
BOOST_ASSERT(pitEntry.getName().at(-1).isImplicitSha256Digest());
- BOOST_ASSERT(nte->getPrefix() == pitEntry.getName().getPrefix(-1));
+ BOOST_ASSERT(nte->getName() == pitEntry.getName().getPrefix(-1));
return this->lookup(pitEntry.getName());
}
@@ -103,7 +103,7 @@
}
size_t
-NameTree::eraseEntryIfEmpty(Entry* entry)
+NameTree::eraseIfEmpty(Entry* entry)
{
BOOST_ASSERT(entry != nullptr);
@@ -167,21 +167,20 @@
{
shared_ptr<Entry> nte = this->getEntry(pitEntry);
BOOST_ASSERT(nte != nullptr);
- if (nte->getPrefix().size() == pitEntry.getName().size()) {
+ if (nte->getName().size() == pitEntry.getName().size()) {
return nte;
}
BOOST_ASSERT(pitEntry.getName().at(-1).isImplicitSha256Digest());
- BOOST_ASSERT(nte->getPrefix() == pitEntry.getName().getPrefix(-1));
+ BOOST_ASSERT(nte->getName() == pitEntry.getName().getPrefix(-1));
shared_ptr<Entry> exact = this->findExactMatch(pitEntry.getName());
return exact == nullptr ? nte : exact;
}
boost::iterator_range<NameTree::const_iterator>
-NameTree::findAllMatches(const Name& prefix,
- const EntrySelector& entrySelector) const
+NameTree::findAllMatches(const Name& name, const EntrySelector& entrySelector) const
{
- NFD_LOG_TRACE("NameTree::findAllMatches" << prefix);
+ NFD_LOG_TRACE("NameTree::findAllMatches" << name);
// As we are using Name Prefix Hash Table, and the current LPM() is
// implemented as starting from full name, and reduce the number of
@@ -189,7 +188,7 @@
// For trie-like design, it could be more efficient by walking down the
// trie from the root node.
- shared_ptr<Entry> entry = findLongestPrefixMatch(prefix, entrySelector);
+ shared_ptr<Entry> entry = findLongestPrefixMatch(name, entrySelector);
return {Iterator(make_shared<PrefixMatchImpl>(*this, entrySelector), entry.get()), end()};
}
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index ad9f314..d630cad 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -31,6 +31,8 @@
namespace nfd {
namespace name_tree {
+/** \brief a common index structure for FIB, PIT, StrategyChoice, and Measurements
+ */
class NameTree : noncopyable
{
public:
@@ -40,7 +42,7 @@
NameTree(size_t nBuckets = 1024);
public: // information
- /** \brief Get the number of occupied entries in the Name Tree
+ /** \return number of name tree entries
*/
size_t
size() const
@@ -48,10 +50,7 @@
return m_ht.size();
}
- /** \brief Get the number of buckets in the Name Tree (NPHT)
- *
- * The number of buckets is the one that used to create the hash
- * table, i.e., m_nBuckets.
+ /** \return number of hashtable buckets
*/
size_t
getNBuckets() const
@@ -59,7 +58,7 @@
return m_ht.getNBuckets();
}
- /** \return Name Tree Entry on which a table entry is attached
+ /** \return entry on which a table entry is attached
*/
template<typename ENTRY>
shared_ptr<Entry>
@@ -69,149 +68,152 @@
}
public: // mutation
- /** \brief Look for the Name Tree Entry that contains this name prefix.
- *
- * Starts from the shortest name prefix, and then increase the
- * number of name components by one each time. All non-existing Name Tree
- * Entries will be created.
- *
- * \param name The querying name prefix.
- * \return The pointer to the Name Tree Entry that contains this full name prefix.
+ /** \brief find or insert an entry with specified name
+ * \param name a name prefix
+ * \return an entry with \p name
+ * \post an entry with \p name and all ancestors are created
* \note Existing iterators are unaffected.
*/
shared_ptr<Entry>
lookup(const Name& name);
- /** \brief get NameTree entry from FIB entry
- *
- * This is equivalent to .lookup(fibEntry.getPrefix())
+ /** \brief equivalent to .lookup(fibEntry.getPrefix())
+ * \note This overload is more efficient than .lookup(const Name&) in common cases.
*/
shared_ptr<Entry>
lookup(const fib::Entry& fibEntry) const;
- /** \brief get NameTree entry from PIT entry
- *
- * This is equivalent to .lookup(pitEntry.getName()).
+ /** \brief equivalent to .lookup(pitEntry.getName()).
+ * \note This overload is more efficient than .lookup(const Name&) in common cases.
*/
shared_ptr<Entry>
lookup(const pit::Entry& pitEntry);
- /** \brief get NameTree entry from Measurements entry
- *
- * This is equivalent to .lookup(measurementsEntry.getName())
+ /** \brief equivalent to .lookup(measurementsEntry.getName())
+ * \note This overload is more efficient than .lookup(const Name&) in common cases.
*/
shared_ptr<Entry>
lookup(const measurements::Entry& measurementsEntry) const;
- /** \brief get NameTree entry from StrategyChoice entry
- *
- * This is equivalent to .lookup(strategyChoiceEntry.getName())
+ /** \brief equivalent to .lookup(strategyChoiceEntry.getName())
+ * \note This overload is more efficient than .lookup(const Name&) in common cases.
*/
shared_ptr<Entry>
lookup(const strategy_choice::Entry& strategyChoiceEntry) const;
- /** \brief Delete a Name Tree Entry if this entry is empty.
- * \param entry The entry to be deleted if empty.
- * \note This function must be called after a table entry is detached from Name Tree
- * entry. The function deletes a Name Tree entry if nothing is attached to it and
- * it has no children, then repeats the same process on its ancestors.
+ /** \brief delete the entry if it is empty
+ * \param entry a valid entry
+ * \return number of deleted entries
+ * \sa Entry::isEmpty()
+ * \post If the entry is empty, it's deleted.
+ * Ancestors of the entry are also deleted if they become empty.
+ * \note This function must be called after detaching a table entry from a name tree entry,
* \note Existing iterators, except those pointing to deleted entries, are unaffected.
*/
size_t
- eraseEntryIfEmpty(Entry* entry);
-
- /// \deprecated
- bool
- eraseEntryIfEmpty(shared_ptr<Entry> entry)
- {
- BOOST_ASSERT(entry != nullptr);
- return this->eraseEntryIfEmpty(entry.get()) > 0;
- }
+ eraseIfEmpty(Entry* entry);
public: // matching
- /** \brief Exact match lookup for the given name prefix.
- * \return nullptr if this prefix is not found; otherwise return the Name Tree Entry address
+ /** \brief exact match lookup
+ * \return entry with \p name, or nullptr if it does not exist
*/
shared_ptr<Entry>
findExactMatch(const Name& name) const;
- /** \brief Longest prefix matching for the given name
- *
- * Starts from the full name string, reduce the number of name component
- * by one each time, until an Entry is found.
+ /** \brief longest prefix matching
+ * \return entry whose name is a prefix of \p name and passes \p entrySelector,
+ * where no other entry with a longer name satisfies those requirements;
+ * or nullptr if no entry satisfying those requirements exists
*/
shared_ptr<Entry>
findLongestPrefixMatch(const Name& name,
const EntrySelector& entrySelector = AnyEntry()) const;
+ /** \brief equivalent to .findLongestPrefixMatch(entry->getName(), entrySelector)
+ * \note This overload is more efficient than .findLongestPrefixMatch(const Name&)
+ * in common cases.
+ */
shared_ptr<Entry>
findLongestPrefixMatch(shared_ptr<Entry> entry,
const EntrySelector& entrySelector = AnyEntry()) const;
- /** \brief longest prefix matching for Interest name of the PIT entry
- *
- * This is equivalent to .findLongestPrefixMatch(pitEntry.getName(), AnyEntry()).
+ /** \brief equivalent to .findLongestPrefixMatch(pitEntry.getName(), AnyEntry())
+ * \note This overload is more efficient than .findLongestPrefixMatch(const Name&)
+ * in common cases.
*/
shared_ptr<Entry>
findLongestPrefixMatch(const pit::Entry& pitEntry) const;
- /** \brief Enumerate all the name prefixes that satisfy the prefix and entrySelector
+ /** \brief all-prefixes match lookup
* \return an unspecified type that have .begin() and .end() methods
- * and is usable with range-based for
+ * and is usable with range-based for.
+ * Every entry in the range has a name that is a prefix of \p name ,
+ * and matches \p entrySelector.
*
* Example:
- * \code{.cpp}
- * auto&& allMatches = nt.findAllMatches(Name("/A/B/C"));
+ * \code
+ * Name name("/A/B/C");
+ * auto&& allMatches = nt.findAllMatches(name);
* for (const Entry& nte : allMatches) {
+ * BOOST_ASSERT(nte.getName().isPrefixOf(name));
* ...
* }
* \endcode
- * \note Iteration order is implementation-specific and is undefined
- * \note The returned iterator may get invalidated when NameTree is modified
+ * \note Iteration order is implementation-specific and is undefined.
+ * \warning If a name tree entry whose name is a prefix of \p name is inserted
+ * during the enumeration, it may or may not be visited.
+ * If a name tree entry whose name is a prefix of \p name is deleted
+ * during the enumeration, undefined behavior may occur.
*/
boost::iterator_range<const_iterator>
- findAllMatches(const Name& prefix,
+ findAllMatches(const Name& name,
const EntrySelector& entrySelector = AnyEntry()) const;
public: // enumeration
- /** \brief Enumerate all entries, optionally filtered by an EntrySelector.
+ /** \brief enumerate all entries
* \return an unspecified type that have .begin() and .end() methods
- * and is usable with range-based for
+ * and is usable with range-based for.
+ * Every entry in the range matches \p entrySelector.
*
* Example:
- * \code{.cpp}
+ * \code
* auto&& enumerable = nt.fullEnumerate();
* for (const Entry& nte : enumerable) {
* ...
* }
* \endcode
- * \note Iteration order is implementation-specific and is undefined
- * \note The returned iterator may get invalidated when NameTree is modified
+ * \note Iteration order is implementation-specific and is undefined.
+ * \warning If a name tree entry is inserted or deleted during the enumeration,
+ * it may cause the enumeration to skip entries or visit some entries twice.
*/
boost::iterator_range<const_iterator>
fullEnumerate(const EntrySelector& entrySelector = AnyEntry()) const;
- /** \brief Enumerate all entries under a prefix, optionally filtered by an EntrySubTreeSelector.
+ /** \brief enumerate all entries under a prefix
* \return an unspecified type that have .begin() and .end() methods
- * and is usable with range-based for
+ * and is usable with range-based for.
+ * Every entry in the range has a name that starts with \p prefix,
+ * and matches \p entrySubTreeSelector.
*
* Example:
- * \code{.cpp}
- * auto&& enumerable = nt.partialEnumerate(Name("/A/B/C"));
+ * \code
+ * Name name("/A/B/C");
+ * auto&& enumerable = nt.partialEnumerate(name);
* for (const Entry& nte : enumerable) {
+ * BOOST_ASSERT(name.isPrefixOf(nte.getName()));
* ...
* }
* \endcode
- * \note Iteration order is implementation-specific and is undefined
- * \note The returned iterator may get invalidated when NameTree is modified
+ * \note Iteration order is implementation-specific and is undefined.
+ * \warning If a name tree entry under \p prefix is inserted or deleted during the enumeration,
+ * it may cause the enumeration to skip entries or visit some entries twice.
*/
boost::iterator_range<const_iterator>
partialEnumerate(const Name& prefix,
const EntrySubTreeSelector& entrySubTreeSelector = AnyEntrySubTree()) const;
- /** \brief Get an iterator pointing to the first NameTree entry
- * \note Iteration order is implementation-specific and is undefined
- * \note The returned iterator may get invalidated when NameTree is modified
+ /** \return an iterator to enumerate all entries
+ * \sa fullEnumerate
*/
const_iterator
begin() const
@@ -219,9 +221,7 @@
return fullEnumerate().begin();
}
- /** \brief Get an iterator referring to the past-the-end FIB entry
- * \note Iteration order is implementation-specific and is undefined
- * \note The returned iterator may get invalidated when NameTree is modified
+ /** \return a past-the-end iterator
*/
const_iterator
end() const
diff --git a/daemon/table/pit.cpp b/daemon/table/pit.cpp
index 57cbf53..de6c9da 100644
--- a/daemon/table/pit.cpp
+++ b/daemon/table/pit.cpp
@@ -137,7 +137,7 @@
nte->erasePitEntry(entry);
if (canDeleteNte) {
- m_nameTree.eraseEntryIfEmpty(nte);
+ m_nameTree.eraseIfEmpty(nte.get());
}
--m_nItems;
}
diff --git a/daemon/table/strategy-choice.cpp b/daemon/table/strategy-choice.cpp
index 3c701d4..a8b32d7 100644
--- a/daemon/table/strategy-choice.cpp
+++ b/daemon/table/strategy-choice.cpp
@@ -145,7 +145,7 @@
this->changeStrategy(*entry, oldStrategy, parentStrategy);
nte->setStrategyChoiceEntry(nullptr);
- m_nameTree.eraseEntryIfEmpty(nte);
+ m_nameTree.eraseIfEmpty(nte.get());
--m_nItems;
}
@@ -229,7 +229,7 @@
static inline void
clearStrategyInfo(const name_tree::Entry& nte)
{
- NFD_LOG_TRACE("clearStrategyInfo " << nte.getPrefix());
+ NFD_LOG_TRACE("clearStrategyInfo " << nte.getName());
for (const shared_ptr<pit::Entry>& pitEntry : nte.getPitEntries()) {
pitEntry->clearStrategyInfo();