30 #include <boost/concept/assert.hpp> 31 #include <boost/concept_check.hpp> 32 #include <type_traits> 39 BOOST_CONCEPT_ASSERT((boost::ForwardIterator<NameTree::const_iterator>));
42 #ifdef HAVE_IS_DEFAULT_CONSTRUCTIBLE 43 static_assert(std::is_default_constructible<NameTree::const_iterator>::value,
44 "NameTree::const_iterator must be default-constructible");
46 BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<NameTree::const_iterator>));
47 #endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE 55 compute(
const char* buffer,
size_t length)
57 return static_cast<size_t>(
CityHash32(buffer, length));
65 compute(
const char* buffer,
size_t length)
67 return static_cast<size_t>(
CityHash64(buffer, length));
80 size_t hashUpdate = 0;
84 const char* wireFormat =
reinterpret_cast<const char*
>( it->wire() );
85 hashUpdate = CityHash::compute(wireFormat, it->size());
86 hashValue ^= hashUpdate;
98 size_t hashUpdate = 0;
100 std::vector<size_t> hashValueSet;
101 hashValueSet.push_back(hashValue);
105 const char* wireFormat =
reinterpret_cast<const char*
>( it->wire() );
106 hashUpdate = CityHash::compute(wireFormat, it->size());
107 hashValue ^= hashUpdate;
108 hashValueSet.push_back(hashValue);
118 , m_nBuckets(nBuckets)
119 , m_minNBuckets(nBuckets)
120 , m_enlargeLoadFactor(0.5)
122 , m_shrinkLoadFactor(0.1)
123 , m_shrinkFactor(0.5)
124 , m_endIterator(FULL_ENUMERATE_TYPE, *this, m_end)
126 m_enlargeThreshold =
static_cast<size_t>(m_enlargeLoadFactor *
127 static_cast<double>(m_nBuckets));
129 m_shrinkThreshold =
static_cast<size_t>(m_shrinkLoadFactor *
130 static_cast<double>(m_nBuckets));
135 for (
size_t i = 0; i < m_nBuckets; i++)
141 for (
size_t i = 0; i < m_nBuckets; i++)
143 if (m_buckets[i] != 0) {
152 std::pair<shared_ptr<name_tree::Entry>,
bool>
153 NameTree::insert(
const Name& prefix)
158 size_t loc = hashValue % m_nBuckets;
160 NFD_LOG_TRACE(
"Name " << prefix <<
" hash value = " << hashValue <<
" location = " << loc);
166 for (node = m_buckets[loc]; node != 0; node = node->
m_next)
168 if (static_cast<bool>(node->
m_entry))
170 if (prefix == node->
m_entry->m_prefix)
172 return std::make_pair(node->
m_entry,
false);
178 NFD_LOG_TRACE(
"Did not find " << prefix <<
", need to insert it to the table");
187 m_buckets[loc] = node;
195 shared_ptr<name_tree::Entry> entry(make_shared<name_tree::Entry>(prefix));
196 entry->setHash(hashValue);
198 entry->m_node = node;
200 return std::make_pair(entry,
true);
204 shared_ptr<name_tree::Entry>
209 shared_ptr<name_tree::Entry> entry;
210 shared_ptr<name_tree::Entry> parent;
212 for (
size_t i = 0; i <= prefix.
size(); i++)
217 std::pair<shared_ptr<name_tree::Entry>,
bool> ret = insert(temp);
220 if (ret.second ==
true)
223 entry->m_parent = parent;
225 if (static_cast<bool>(parent))
227 parent->m_children.push_back(entry);
231 if (m_nItems > m_enlargeThreshold)
233 resize(m_enlargeFactor * m_nBuckets);
242 shared_ptr<name_tree::Entry>
248 size_t loc = hashValue % m_nBuckets;
250 NFD_LOG_TRACE(
"Name " << prefix <<
" hash value = " << hashValue <<
251 " location = " << loc);
253 shared_ptr<name_tree::Entry> entry;
256 for (node = m_buckets[loc]; node != 0; node = node->
m_next)
259 if (static_cast<bool>(entry))
261 if (hashValue == entry->getHash() && prefix == entry->
getPrefix())
274 shared_ptr<name_tree::Entry>
279 shared_ptr<name_tree::Entry> entry;
282 size_t hashValue = 0;
285 for (
int i = static_cast<int>(prefix.
size()); i >= 0; i--)
287 hashValue = hashValueSet[i];
288 loc = hashValue % m_nBuckets;
291 for (node = m_buckets[loc]; node != 0; node = node->
m_next)
294 if (static_cast<bool>(entry))
297 if (hashValue == entry->getHash() &&
298 entry->getPrefix().isPrefixOf(prefix) &&
299 entrySelector(*entry))
312 shared_ptr<name_tree::Entry>
316 while (static_cast<bool>(entry))
318 if (entrySelector(*entry))
320 entry = entry->getParent();
322 return shared_ptr<name_tree::Entry>();
329 BOOST_ASSERT(static_cast<bool>(entry));
334 if (entry->isEmpty())
337 shared_ptr<name_tree::Entry> parent = entry->getParent();
339 if (static_cast<bool>(parent))
341 std::vector<shared_ptr<name_tree::Entry> >& parentChildrenList =
342 parent->getChildren();
344 bool isFound =
false;
345 size_t size = parentChildrenList.size();
346 for (
size_t i = 0; i <
size; i++)
348 if (parentChildrenList[i] == entry)
350 parentChildrenList[i] = parentChildrenList[size - 1];
351 parentChildrenList.pop_back();
357 BOOST_VERIFY(isFound ==
true);
372 m_buckets[entry->getHash() % m_nBuckets] = node->
m_next;
382 BOOST_ASSERT(node->
m_next == 0);
387 if (static_cast<bool>(parent))
390 size_t newNBuckets =
static_cast<size_t>(m_shrinkFactor *
391 static_cast<double>(m_nBuckets));
393 if (newNBuckets >= m_minNBuckets && m_nItems < m_shrinkThreshold)
405 boost::iterator_range<NameTree::const_iterator>
411 for (
size_t i = 0; i < m_nBuckets; i++) {
413 if (static_cast<bool>(node->m_entry) && entrySelector(*node->m_entry)) {
424 boost::iterator_range<NameTree::const_iterator>
430 if (!static_cast<bool>(entry)) {
434 std::pair<bool, bool>result = entrySubTreeSelector(*entry);
439 entrySubTreeSelector);
441 it.m_shouldVisitChildren = (result.second && entry->hasChildren());
453 boost::iterator_range<NameTree::const_iterator>
467 if (static_cast<bool>(entry)) {
477 NameTree::resize(
size_t newNBuckets)
493 for (i = 0; i < newNBuckets; i++)
498 for (i = 0; i < m_nBuckets; i++)
500 for (p = m_buckets[i]; p != 0; p = q)
504 BOOST_ASSERT(static_cast<bool>(p->
m_entry));
508 for (pp = &newBuckets[b]; *pp != 0; pp = &((*pp)->m_next))
519 BOOST_ASSERT(count == m_nItems);
522 m_buckets = newBuckets;
523 delete [] oldBuckets;
525 m_nBuckets = newNBuckets;
527 m_enlargeThreshold =
static_cast<size_t>(m_enlargeLoadFactor *
528 static_cast<double>(m_nBuckets));
529 m_shrinkThreshold =
static_cast<size_t>(m_shrinkLoadFactor *
530 static_cast<double>(m_nBuckets));
540 shared_ptr<name_tree::Entry> entry;
544 for (
size_t i = 0; i < m_nBuckets; i++)
546 for (node = m_buckets[i]; node != 0; node = node->
m_next)
551 if (static_cast<bool>(entry))
553 output <<
"Bucket" << i <<
"\t" << entry->m_prefix.toUri() << endl;
554 output <<
"\t\tHash " << entry->m_hash << endl;
556 if (static_cast<bool>(entry->m_parent))
558 output <<
"\t\tparent->" << entry->m_parent->m_prefix.toUri();
562 output <<
"\t\tROOT";
566 if (entry->m_children.size() != 0)
568 output <<
"\t\tchildren = " << entry->m_children.size() << endl;
570 for (
size_t j = 0; j < entry->m_children.size(); j++)
572 output <<
"\t\t\tChild " << j <<
" " <<
573 entry->m_children[j]->getPrefix() << endl;
582 output <<
"Bucket count = " << m_nBuckets << endl;
583 output <<
"Stored item = " << m_nItems << endl;
584 output <<
"--------------------------\n";
588 : m_nameTree(nullptr)
594 shared_ptr<name_tree::Entry> entry,
597 : m_nameTree(&nameTree)
599 , m_subTreeRoot(entry)
600 , m_entrySelector(make_shared<name_tree::
EntrySelector>(entrySelector))
603 , m_shouldVisitChildren(true)
613 BOOST_ASSERT(m_entry != m_nameTree->m_end);
618 while (m_entry->m_node->m_next != 0)
620 m_entry = m_entry->m_node->m_next->m_entry;
621 if ((*m_entrySelector)(*m_entry))
629 for (
int newLocation = m_entry->m_hash % m_nameTree->m_nBuckets + 1;
630 newLocation < static_cast<int>(m_nameTree->m_nBuckets);
638 if ((*m_entrySelector)(*m_entry))
647 m_entry = m_nameTree->m_end;
660 if (m_entry == m_subTreeRoot)
662 if (m_shouldVisitChildren)
664 m_entry = m_entry->getChildren()[0];
665 std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
666 m_shouldVisitChildren = (result.second && m_entry->hasChildren());
687 while (m_entry != m_subTreeRoot)
689 if (m_shouldVisitChildren)
692 m_entry = m_entry->getChildren()[0];
693 std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
694 m_shouldVisitChildren = (result.second && m_entry->hasChildren());
708 shared_ptr<name_tree::Entry> parent = m_entry->getParent();
710 std::vector<shared_ptr<name_tree::Entry> >& parentChildrenList = parent->getChildren();
711 bool isFound =
false;
713 for (i = 0; i < parentChildrenList.size(); i++)
715 if (parentChildrenList[i] == m_entry)
722 BOOST_VERIFY(isFound ==
true);
723 if (i < parentChildrenList.size() - 1)
725 m_entry = parentChildrenList[i + 1];
726 std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
727 m_shouldVisitChildren = (result.second && m_entry->hasChildren());
741 m_shouldVisitChildren =
false;
747 m_entry = m_nameTree->m_end;
757 while (static_cast<bool>(m_entry->getParent()))
759 m_entry = m_entry->getParent();
760 if ((*m_entrySelector)(*m_entry))
765 m_entry = m_nameTree->m_end;
boost::iterator_range< const_iterator > partialEnumerate(const Name &prefix, const name_tree::EntrySubTreeSelector &entrySubTreeSelector=name_tree::AnyEntrySubTree()) const
Enumerate all entries under a prefix, optionally filtered by an EntrySubTreeSelector.
size_t computeHash(const Name &prefix)
Compute the hash value of the given name prefix's WIRE FORMAT.
NameTree(size_t nBuckets=1024)
const_iterator begin() const
Begin iterator (const).
static size_t compute(const char *buffer, size_t length)
const_iterator begin() const
Get an iterator pointing to the first NameTree entry.
shared_ptr< Entry > m_entry
bool eraseEntryIfEmpty(shared_ptr< name_tree::Entry > entry)
Delete a Name Tree Entry if this entry is empty.
uint32 CityHash32(const char *s, size_t len)
boost::iterator_range< const_iterator > findAllMatches(const Name &prefix, const name_tree::EntrySelector &entrySelector=name_tree::AnyEntry()) const
Enumerate all the name prefixes that satisfy the prefix and entrySelector.
function< std::pair< bool, bool >const Entry &entry)> EntrySubTreeSelector
a predicate to accept or reject an Entry and its children
const_iterator end() const
Get an iterator referring to the past-the-end FIB entry.
size_t wireEncode(EncodingImpl< TAG > &encoder) const
Fast encoding or block size estimation.
shared_ptr< name_tree::Entry > findLongestPrefixMatch(const Name &prefix, const name_tree::EntrySelector &entrySelector=name_tree::AnyEntry()) const
Longest prefix matching for the given name.
std::vector< size_t > computeHashSet(const Name &prefix)
Incrementally compute hash values.
size_t size() const
Get the number of occupied entries in the Name Tree.
uint64 CityHash64(const char *s, size_t len)
const_iterator end() const
End iterator (const).
Copyright (c) 2011-2015 Regents of the University of California.
void dump(std::ostream &output) const
Dump all the information stored in the Name Tree for debugging.
size_t size() const
Get the number of components.
Name abstraction to represent an absolute name.
shared_ptr< name_tree::Entry > lookup(const Name &prefix)
Look for the Name Tree Entry that contains this name prefix.
const_iterator operator++()
Component holds a read-only name component value.
static size_t compute(const char *buffer, size_t length)
#define NFD_LOG_INIT(name)
#define NFD_LOG_TRACE(expression)
function< bool(const Entry &entry)> EntrySelector
a predicate to accept or reject an Entry in find operations
PartialName getPrefix(ssize_t nComponents) const
Extract a prefix (PartialName) of the name, containing first nComponents components.
shared_ptr< name_tree::Entry > findExactMatch(const Name &prefix) const
Exact match lookup for the given name prefix.
boost::iterator_range< const_iterator > fullEnumerate(const name_tree::EntrySelector &entrySelector=name_tree::AnyEntry()) const
Enumerate all entries, optionally filtered by an EntrySelector.