daemon/table/name-tree.cpp - NFD - Gitiles

 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /**
  * Copyright (c) 2014-2016,  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 "name-tree.hpp"
 #include "core/logger.hpp"
 #include "core/city-hash.hpp"

 #include <boost/concept/assert.hpp>
 #include <boost/concept_check.hpp>
 #include <type_traits>

 namespace nfd {
 namespace name_tree {

 NFD_LOG_INIT("NameTree");

 // http://en.cppreference.com/w/cpp/concept/ForwardIterator
 BOOST_CONCEPT_ASSERT((boost::ForwardIterator<NameTree::const_iterator>));
 // boost::ForwardIterator follows SGI standard http://www.sgi.com/tech/stl/ForwardIterator.html,
 // which doesn't require DefaultConstructible
 #ifdef HAVE_IS_DEFAULT_CONSTRUCTIBLE
 static_assert(std::is_default_constructible<NameTree::const_iterator>::value,
               "NameTree::const_iterator must be default-constructible");
 #else
 BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<NameTree::const_iterator>));
 #endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE

 class Hash32
 {
 public:
   static size_t
   compute(const char* buffer, size_t length)
   {
     return static_cast<size_t>(CityHash32(buffer, length));
   }
 };

 class Hash64
 {
 public:
   static size_t
   compute(const char* buffer, size_t length)
   {
     return static_cast<size_t>(CityHash64(buffer, length));
   }
 };

 /// @cond NoDocumentation
 typedef boost::mpl::if_c<sizeof(size_t) >= 8, Hash64, Hash32>::type CityHash;
 /// @endcond

 // Interface of different hash functions
 size_t
 computeHash(const Name& prefix)
 {
   prefix.wireEncode();  // guarantees prefix's wire buffer is not empty

   size_t hashValue = 0;
   size_t hashUpdate = 0;

   for (Name::const_iterator it = prefix.begin(); it != prefix.end(); ++it) {
     const char* wireFormat = reinterpret_cast<const char*>( it->wire() );
     hashUpdate = CityHash::compute(wireFormat, it->size());
     hashValue ^= hashUpdate;
   }

   return hashValue;
 }

 std::vector<size_t>
 computeHashSet(const Name& prefix)
 {
   prefix.wireEncode(); // guarantees prefix's wire buffer is not empty

   size_t hashValue = 0;
   size_t hashUpdate = 0;

   std::vector<size_t> hashValueSet;
   hashValueSet.push_back(hashValue);

   for (Name::const_iterator it = prefix.begin(); it != prefix.end(); ++it) {
     const char* wireFormat = reinterpret_cast<const char*>( it->wire() );
     hashUpdate = CityHash::compute(wireFormat, it->size());
     hashValue ^= hashUpdate;
     hashValueSet.push_back(hashValue);
   }

   return hashValueSet;
 }

 NameTree::NameTree(size_t nBuckets)
   : m_nItems(0)
   , m_nBuckets(nBuckets)
   , m_minNBuckets(nBuckets)
   , m_enlargeLoadFactor(0.5) // more than 50% buckets loaded
   , m_enlargeFactor(2)       // double the hash table size
   , m_shrinkLoadFactor(0.1)  // less than 10% buckets loaded
   , m_shrinkFactor(0.5)      // reduce the number of buckets by half
   , m_endIterator(FULL_ENUMERATE_TYPE, *this, m_end)
 {
   m_enlargeThreshold = static_cast<size_t>(m_enlargeLoadFactor * static_cast<double>(m_nBuckets));
   m_shrinkThreshold = static_cast<size_t>(m_shrinkLoadFactor * static_cast<double>(m_nBuckets));

   // array of node pointers
   m_buckets = new Node*[m_nBuckets];
   // Initialize the pointer array
   for (size_t i = 0; i < m_nBuckets; ++i) {
     m_buckets[i] = nullptr;
   }
 }

 NameTree::~NameTree()
 {
   for (size_t i = 0; i < m_nBuckets; ++i) {
     if (m_buckets[i] != nullptr) {
       delete m_buckets[i];
     }
   }

   delete[] m_buckets;
 }

 // insert() is a private function, and called by only lookup()
 std::pair<shared_ptr<Entry>, bool>
 NameTree::insert(const Name& prefix)
 {
   NFD_LOG_TRACE("insert " << prefix);

   size_t hashValue = computeHash(prefix);
   size_t loc = hashValue % m_nBuckets;

   NFD_LOG_TRACE("Name " << prefix << " hash value = " << hashValue << "  location = " << loc);

   // Check if this Name has been stored
   Node* node = m_buckets[loc];
   Node* nodePrev = node;

   for (node = m_buckets[loc]; node != nullptr; node = node->m_next) {
     if (node->m_entry != nullptr) {
       if (prefix == node->m_entry->m_prefix) {
          return {node->m_entry, false}; // false: old entry
       }
     }
     nodePrev = node;
   }

   NFD_LOG_TRACE("Did not find " << prefix << ", need to insert it to the table");

   // If no bucket is empty occupied, we need to create a new node, and it is
   // linked from nodePrev
   node = new Node();
   node->m_prev = nodePrev;

   if (nodePrev == nullptr) {
     m_buckets[loc] = node;
   }
   else{
     nodePrev->m_next = node;
   }

   // Create a new Entry
   auto entry = make_shared<Entry>(prefix);
   entry->setHash(hashValue);
   node->m_entry = entry; // link the Entry to its Node
   entry->m_node = node; // link the node to Entry. Used in eraseEntryIfEmpty.

   return {entry, true}; // true: new entry
 }

 // Name Prefix Lookup. Create Name Tree Entry if not found
 shared_ptr<Entry>
 NameTree::lookup(const Name& prefix)
 {
   NFD_LOG_TRACE("lookup " << prefix);

   shared_ptr<Entry> entry;
   shared_ptr<Entry> parent;

   for (size_t i = 0; i <= prefix.size(); ++i) {
     Name temp = prefix.getPrefix(i);

     // insert() will create the entry if it does not exist.
     bool isNew = false;
     std::tie(entry, isNew) = insert(temp);

     if (isNew) {
       ++m_nItems; // Increase the counter
       entry->m_parent = parent;

       if (parent != nullptr) {
         parent->m_children.push_back(entry);
       }
     }

     if (m_nItems > m_enlargeThreshold) {
       resize(m_enlargeFactor * m_nBuckets);
     }

     parent = entry;
   }
   return entry;
 }

 shared_ptr<Entry>
 NameTree::lookup(const fib::Entry& fibEntry) const
 {
   shared_ptr<Entry> nte = this->getEntry(fibEntry);
   BOOST_ASSERT(nte == nullptr || nte->getFibEntry() == &fibEntry);
   return nte;
 }

 shared_ptr<Entry>
 NameTree::lookup(const pit::Entry& pitEntry)
 {
   shared_ptr<Entry> nte = this->getEntry(pitEntry);
   if (nte == nullptr) {
     return nullptr;
   }

   if (nte->getPrefix().size() == pitEntry.getName().size()) {
     return nte;
   }

   BOOST_ASSERT(pitEntry.getName().at(-1).isImplicitSha256Digest());
   BOOST_ASSERT(nte->getPrefix() == pitEntry.getName().getPrefix(-1));
   return this->lookup(pitEntry.getName());
 }

 shared_ptr<Entry>
 NameTree::lookup(const measurements::Entry& measurementsEntry) const
 {
   shared_ptr<Entry> nte = this->getEntry(measurementsEntry);
   BOOST_ASSERT(nte == nullptr || nte->getMeasurementsEntry() == &measurementsEntry);
   return nte;
 }

 shared_ptr<Entry>
 NameTree::lookup(const strategy_choice::Entry& strategyChoiceEntry) const
 {
   shared_ptr<Entry> nte = this->getEntry(strategyChoiceEntry);
   BOOST_ASSERT(nte == nullptr || nte->getStrategyChoiceEntry() == &strategyChoiceEntry);
   return nte;
 }

 // return {false: this entry is not empty, true: this entry is empty and erased}
 bool
 NameTree::eraseEntryIfEmpty(shared_ptr<Entry> entry)
 {
   BOOST_ASSERT(entry != nullptr);

   NFD_LOG_TRACE("eraseEntryIfEmpty " << entry->getPrefix());

   // first check if this Entry can be erased
   if (entry->isEmpty()) {
     // update child-related info in the parent
     shared_ptr<Entry> parent = entry->getParent();

     if (parent != nullptr) {
       std::vector<shared_ptr<Entry>>& parentChildrenList = parent->getChildren();

       bool isFound = false;
       size_t size = parentChildrenList.size();
       for (size_t i = 0; i < size; ++i) {
         if (parentChildrenList[i] == entry) {
           parentChildrenList[i] = parentChildrenList[size - 1];
           parentChildrenList.pop_back();
           isFound = true;
           break;
         }
       }

       BOOST_VERIFY(isFound == true);
     }

     // remove this Entry and its Name Tree Node
     Node* node = entry->m_node;
     Node* nodePrev = node->m_prev;

     // configure the previous node
     if (nodePrev != nullptr) {
       // link the previous node to the next node
       nodePrev->m_next = node->m_next;
     }
     else {
       m_buckets[entry->getHash() % m_nBuckets] = node->m_next;
     }

     // link the previous node with the next node (skip the erased one)
     if (node->m_next != nullptr) {
       node->m_next->m_prev = nodePrev;
       node->m_next = 0;
     }

     BOOST_ASSERT(node->m_next == nullptr);

     --m_nItems;
     delete node;

     if (parent != nullptr) {
       eraseEntryIfEmpty(parent);
     }

     size_t newNBuckets = static_cast<size_t>(m_shrinkFactor * static_cast<double>(m_nBuckets));

     if (newNBuckets >= m_minNBuckets && m_nItems < m_shrinkThreshold) {
       resize(newNBuckets);
     }

     return true;

   }

   return false;
 }

 // Exact Match
 shared_ptr<Entry>
 NameTree::findExactMatch(const Name& prefix) const
 {
   NFD_LOG_TRACE("findExactMatch " << prefix);

   size_t hashValue = computeHash(prefix);
   size_t loc = hashValue % m_nBuckets;

   NFD_LOG_TRACE("Name " << prefix << " hash value = " << hashValue << "  location = " << loc);

   shared_ptr<Entry> entry;
   Node* node = nullptr;

   for (node = m_buckets[loc]; node != nullptr; node = node->m_next) {
     entry = node->m_entry;
     if (entry != nullptr) {
       if (hashValue == entry->getHash() && prefix == entry->getPrefix()) {
         return entry;
       }
     }
   }

   // if not found, the default value of entry (null pointer) will be returned
   entry.reset();
   return entry;
 }

 // Longest Prefix Match
 shared_ptr<Entry>
 NameTree::findLongestPrefixMatch(const Name& prefix, const EntrySelector& entrySelector) const
 {
   NFD_LOG_TRACE("findLongestPrefixMatch " << prefix);

   shared_ptr<Entry> entry;
   std::vector<size_t> hashValueSet = computeHashSet(prefix);

   size_t hashValue = 0;
   size_t loc = 0;

   for (int i = static_cast<int>(prefix.size()); i >= 0; --i) {
     hashValue = hashValueSet[i];
     loc = hashValue % m_nBuckets;

     Node* node = nullptr;
     for (node = m_buckets[loc]; node != nullptr; node = node->m_next) {
       entry = node->m_entry;
       if (entry != nullptr) {
         // isPrefixOf() is used to avoid making a copy of the name
         if (hashValue == entry->getHash() &&
             entry->getPrefix().isPrefixOf(prefix) &&
             entrySelector(*entry)) {
           return entry;
         }
       }
     }
   }

   return nullptr;
 }

 shared_ptr<Entry>
 NameTree::findLongestPrefixMatch(shared_ptr<Entry> entry,
                                  const EntrySelector& entrySelector) const
 {
   while (entry != nullptr) {
     if (entrySelector(*entry)) {
       return entry;
     }
     entry = entry->getParent();
   }
   return nullptr;
 }

 shared_ptr<Entry>
 NameTree::findLongestPrefixMatch(const pit::Entry& pitEntry) const
 {
   shared_ptr<Entry> nte = this->getEntry(pitEntry);
   BOOST_ASSERT(nte != nullptr);
   if (nte->getPrefix().size() == pitEntry.getName().size()) {
     return nte;
   }

   BOOST_ASSERT(pitEntry.getName().at(-1).isImplicitSha256Digest());
   BOOST_ASSERT(nte->getPrefix() == 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
 {
   NFD_LOG_TRACE("NameTree::findAllMatches" << prefix);

   // As we are using Name Prefix Hash Table, and the current LPM() is
   // implemented as starting from full name, and reduce the number of
   // components by 1 each time, we could use it here.
   // 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);

   if (entry != nullptr) {
     const_iterator begin(FIND_ALL_MATCHES_TYPE, *this, entry, entrySelector);
     return {begin, end()};
   }
   // If none of the entry satisfies the requirements, then return the end() iterator.
   return {end(), end()};
 }

 boost::iterator_range<NameTree::const_iterator>
 NameTree::fullEnumerate(const EntrySelector& entrySelector) const
 {
   NFD_LOG_TRACE("fullEnumerate");

   // find the first eligible entry
   for (size_t i = 0; i < m_nBuckets; ++i) {
     for (Node* node = m_buckets[i]; node != nullptr; node = node->m_next) {
       if (node->m_entry != nullptr && entrySelector(*node->m_entry)) {
         const_iterator it(FULL_ENUMERATE_TYPE, *this, node->m_entry, entrySelector);
         return {it, end()};
       }
     }
   }

   // If none of the entry satisfies the requirements, then return the end() iterator.
   return {end(), end()};
 }

 boost::iterator_range<NameTree::const_iterator>
 NameTree::partialEnumerate(const Name& prefix,
                            const EntrySubTreeSelector& entrySubTreeSelector) const
 {
   // the first step is to process the root node
   shared_ptr<Entry> entry = findExactMatch(prefix);
   if (entry == nullptr) {
     return {end(), end()};
   }

   std::pair<bool, bool> result = entrySubTreeSelector(*entry);
   const_iterator it(PARTIAL_ENUMERATE_TYPE,
                     *this,
                     entry,
                     AnyEntry(),
                     entrySubTreeSelector);

   it.m_shouldVisitChildren = (result.second && entry->hasChildren());

   if (result.first) {
     // root node is acceptable
   }
   else {
     // let the ++ operator handle it
     ++it;
   }
   return {it, end()};
 }

 // Hash Table Resize
 void
 NameTree::resize(size_t newNBuckets)
 {
   NFD_LOG_TRACE("resize");

   Node** newBuckets = new Node*[newNBuckets];
   size_t count = 0;

   // referenced ccnx hashtb.c hashtb_rehash()
   Node** pp = nullptr;
   Node* p = nullptr;
   Node* pre = nullptr;
   Node* q = nullptr; // record p->m_next

   for (size_t i = 0; i < newNBuckets; ++i) {
     newBuckets[i] = nullptr;
   }

   for (size_t i = 0; i < m_nBuckets; ++i) {
     for (p = m_buckets[i]; p != nullptr; p = q) {
       ++count;
       q = p->m_next;
       BOOST_ASSERT(p->m_entry != nullptr);
       uint32_t h = p->m_entry->m_hash;
       uint32_t b = h % newNBuckets;
       pre = nullptr;
       for (pp = &newBuckets[b]; *pp != nullptr; pp = &((*pp)->m_next)) {
         pre = *pp;
       }
       p->m_prev = pre;
       p->m_next = *pp; // Actually *pp always == nullptr in this case
       *pp = p;
     }
   }

   BOOST_ASSERT(count == m_nItems);

   Node** oldBuckets = m_buckets;
   m_buckets = newBuckets;
   delete[] oldBuckets;

   m_nBuckets = newNBuckets;
   m_enlargeThreshold = static_cast<size_t>(m_enlargeLoadFactor * static_cast<double>(m_nBuckets));
   m_shrinkThreshold = static_cast<size_t>(m_shrinkLoadFactor * static_cast<double>(m_nBuckets));
 }

 // For debugging
 void
 NameTree::dump(std::ostream& output) const
 {
   NFD_LOG_TRACE("dump()");

   Node* node = nullptr;
   shared_ptr<Entry> entry;

   for (size_t i = 0; i < m_nBuckets; ++i) {
     for (node = m_buckets[i]; node != nullptr; node = node->m_next) {
       entry = node->m_entry;

       // if the Entry exist, dump its information
       if (entry != nullptr) {
         output << "Bucket" << i << '\t' << entry->m_prefix.toUri() << '\n';
         output << "\t\tHash " << entry->m_hash << '\n';

         if (entry->m_parent != nullptr) {
           output << "\t\tparent->" << entry->m_parent->m_prefix.toUri();
         }
         else {
           output << "\t\tROOT";
         }
         output << '\n';

         if (!entry->m_children.empty()) {
           output << "\t\tchildren = " << entry->m_children.size() << '\n';

           for (size_t j = 0; j < entry->m_children.size(); ++j) {
             output << "\t\t\tChild " << j << " " << entry->m_children[j]->getPrefix() << '\n';
           }
         }

       }

     }
   }

   output << "Bucket count = " << m_nBuckets << '\n';
   output << "Stored item = " << m_nItems << '\n';
   output << "--------------------------\n";
 }

 NameTree::const_iterator::const_iterator()
   : m_nameTree(nullptr)
 {
 }

 NameTree::const_iterator::const_iterator(NameTree::IteratorType type,
                                          const NameTree& nameTree,
                                          shared_ptr<Entry> entry,
                                          const EntrySelector& entrySelector,
                                          const EntrySubTreeSelector& entrySubTreeSelector)
   : m_nameTree(&nameTree)
   , m_entry(entry)
   , m_subTreeRoot(entry)
   , m_entrySelector(make_shared<EntrySelector>(entrySelector))
   , m_entrySubTreeSelector(make_shared<EntrySubTreeSelector>(entrySubTreeSelector))
   , m_type(type)
   , m_shouldVisitChildren(true)
 {
 }

 // operator++()
 NameTree::const_iterator
 NameTree::const_iterator::operator++()
 {
   NFD_LOG_TRACE("const_iterator::operator++()");

   BOOST_ASSERT(m_entry != m_nameTree->m_end);

   if (m_type == FULL_ENUMERATE_TYPE) {
     // process the entries in the same bucket first
     while (m_entry->m_node->m_next != nullptr) {
       m_entry = m_entry->m_node->m_next->m_entry;
       if ((*m_entrySelector)(*m_entry)) {
         return *this;
       }
     }

     // process other buckets

     for (int newLocation = m_entry->m_hash % m_nameTree->m_nBuckets + 1;
          newLocation < static_cast<int>(m_nameTree->m_nBuckets);
          ++newLocation) {
       // process each bucket
       Node* node = m_nameTree->m_buckets[newLocation];
       while (node != nullptr) {
         m_entry = node->m_entry;
         if ((*m_entrySelector)(*m_entry)) {
           return *this;
         }
         node = node->m_next;
       }
     }

     // Reach the end()
     m_entry = m_nameTree->m_end;
     return *this;
   }

   if (m_type == PARTIAL_ENUMERATE_TYPE) {
     // We use pre-order traversal.
     // if at the root, it could have already been accepted, or this
     // iterator was just declared, and root doesn't satisfy the
     // requirement
     // The if() section handles this special case
     // Essentially, we need to check root's fist child, and the rest will
     // be the same as normal process
     if (m_entry == m_subTreeRoot) {
       if (m_shouldVisitChildren) {
         m_entry = m_entry->getChildren()[0];
         std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
         m_shouldVisitChildren = (result.second && m_entry->hasChildren());
         if (result.first) {
           return *this;
         }
         else {
           // the first child did not meet the requirement
           // the rest of the process can just fall through the while loop as normal
         }
       }
       else {
         // no children, should return end();
         // just fall through
       }
     }

     // The first thing to do is to visit its child, or go to find its possible siblings
     while (m_entry != m_subTreeRoot) {
       if (m_shouldVisitChildren) {
         // If this subtree should be visited
         m_entry = m_entry->getChildren()[0];
         std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
         m_shouldVisitChildren = (result.second && m_entry->hasChildren());
         if (result.first) { // if this node is acceptable
           return *this;
         }
         else {
           // do nothing, as this node is essentially ignored
           // send this node to the while loop.
         }
       }
       else {
         // Should try to find its sibling
         shared_ptr<Entry> parent = m_entry->getParent();

         std::vector<shared_ptr<Entry>>& parentChildrenList = parent->getChildren();
         bool isFound = false;
         size_t i = 0;
         for (i = 0; i < parentChildrenList.size(); ++i) {
           if (parentChildrenList[i] == m_entry) {
             isFound = true;
             break;
           }
         }

         BOOST_VERIFY(isFound == true);
         if (i < parentChildrenList.size() - 1) { // m_entry not the last child
           m_entry = parentChildrenList[i + 1];
           std::pair<bool, bool> result = ((*m_entrySubTreeSelector)(*m_entry));
           m_shouldVisitChildren = (result.second && m_entry->hasChildren());
           if (result.first) { // if this node is acceptable
             return *this;
           }
           else {
             // do nothing, as this node is essentially ignored
             // send this node to the while loop.
           }
         }
         else {
           // m_entry is the last child, no more sibling, should try to find parent's sibling
           m_shouldVisitChildren = false;
           m_entry = parent;
         }
       }
     }

     m_entry = m_nameTree->m_end;
     return *this;
   }

   if (m_type == FIND_ALL_MATCHES_TYPE) {
     // Assumption: at the beginning, m_entry was initialized with the first
     // eligible Name Tree entry (i.e., has a PIT entry that can be satisfied
     // by the Data packet)

     while (m_entry->getParent() != nullptr) {
       m_entry = m_entry->getParent();
       if ((*m_entrySelector)(*m_entry)) {
         return *this;
       }
     }

     // Reach to the end (Root)
     m_entry = m_nameTree->m_end;
     return *this;
   }

   BOOST_ASSERT(false); // unknown type
   return *this;
 }

 } // namespace name_tree
 } // namespace nfd
	/* -- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -- */
	/**
	* Copyright (c) 2014-2016, 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 "name-tree.hpp"
	#include "core/logger.hpp"
	#include "core/city-hash.hpp"

	#include <boost/concept/assert.hpp>
	#include <boost/concept_check.hpp>
	#include <type_traits>

	namespace nfd {
	namespace name_tree {

	NFD_LOG_INIT("NameTree");

	// http://en.cppreference.com/w/cpp/concept/ForwardIterator
	BOOST_CONCEPT_ASSERT((boost::ForwardIterator<NameTree::const_iterator>));
	// boost::ForwardIterator follows SGI standard http://www.sgi.com/tech/stl/ForwardIterator.html,
	// which doesn't require DefaultConstructible
	#ifdef HAVE_IS_DEFAULT_CONSTRUCTIBLE
	static_assert(std::is_default_constructible<NameTree::const_iterator>::value,
	"NameTree::const_iterator must be default-constructible");
	#else
	BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<NameTree::const_iterator>));
	#endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE

	class Hash32
	{
	public:
	static size_t
	compute(const char* buffer, size_t length)
	{
	return static_cast<size_t>(CityHash32(buffer, length));
	}
	};

	class Hash64
	{
	public:
	static size_t
	compute(const char* buffer, size_t length)
	{
	return static_cast<size_t>(CityHash64(buffer, length));
	}
	};

	/// @cond NoDocumentation
	typedef boost::mpl::if_c<sizeof(size_t) >= 8, Hash64, Hash32>::type CityHash;
	/// @endcond

	// Interface of different hash functions
	size_t
	computeHash(const Name& prefix)
	{
	prefix.wireEncode(); // guarantees prefix's wire buffer is not empty

	size_t hashValue = 0;
	size_t hashUpdate = 0;

	for (Name::const_iterator it = prefix.begin(); it != prefix.end(); ++it) {
	const char* wireFormat = reinterpret_cast<const char*>( it->wire() );
	hashUpdate = CityHash::compute(wireFormat, it->size());
	hashValue ^= hashUpdate;
	}

	return hashValue;
	}

	std::vector<size_t>
	computeHashSet(const Name& prefix)
	{
	prefix.wireEncode(); // guarantees prefix's wire buffer is not empty

	size_t hashValue = 0;
	size_t hashUpdate = 0;

	std::vector<size_t> hashValueSet;
	hashValueSet.push_back(hashValue);

	for (Name::const_iterator it = prefix.begin(); it != prefix.end(); ++it) {
	const char* wireFormat = reinterpret_cast<const char*>( it->wire() );
	hashUpdate = CityHash::compute(wireFormat, it->size());
	hashValue ^= hashUpdate;
	hashValueSet.push_back(hashValue);
	}

	return hashValueSet;
	}

	NameTree::NameTree(size_t nBuckets)
	: m_nItems(0)
	, m_nBuckets(nBuckets)
	, m_minNBuckets(nBuckets)
	, m_enlargeLoadFactor(0.5) // more than 50% buckets loaded
	, m_enlargeFactor(2) // double the hash table size
	, m_shrinkLoadFactor(0.1) // less than 10% buckets loaded
	, m_shrinkFactor(0.5) // reduce the number of buckets by half
	, m_endIterator(FULL_ENUMERATE_TYPE, *this, m_end)
	{
	m_enlargeThreshold = static_cast<size_t>(m_enlargeLoadFactor * static_cast<double>(m_nBuckets));
	m_shrinkThreshold = static_cast<size_t>(m_shrinkLoadFactor * static_cast<double>(m_nBuckets));

	// array of node pointers
	m_buckets = new Node*[m_nBuckets];
	// Initialize the pointer array
	for (size_t i = 0; i < m_nBuckets; ++i) {
	m_buckets[i] = nullptr;
	}
	}

	NameTree::~NameTree()
	{
	for (size_t i = 0; i < m_nBuckets; ++i) {
	if (m_buckets[i] != nullptr) {
	delete m_buckets[i];
	}
	}

	delete[] m_buckets;
	}

	// insert() is a private function, and called by only lookup()
	std::pair<shared_ptr<Entry>, bool>
	NameTree::insert(const Name& prefix)
	{
	NFD_LOG_TRACE("insert " << prefix);

	size_t hashValue = computeHash(prefix);
	size_t loc = hashValue % m_nBuckets;

	NFD_LOG_TRACE("Name " << prefix << " hash value = " << hashValue << " location = " << loc);

	// Check if this Name has been stored
	Node* node = m_buckets[loc];
	Node* nodePrev = node;

	for (node = m_buckets[loc]; node != nullptr; node = node->m_next) {
	if (node->m_entry != nullptr) {
	if (prefix == node->m_entry->m_prefix) {
	return {node->m_entry, false}; // false: old entry
	}
	}
	nodePrev = node;
	}

	NFD_LOG_TRACE("Did not find " << prefix << ", need to insert it to the table");

	// If no bucket is empty occupied, we need to create a new node, and it is
	// linked from nodePrev
	node = new Node();
	node->m_prev = nodePrev;

	if (nodePrev == nullptr) {
	m_buckets[loc] = node;
	}
	else{
	nodePrev->m_next = node;
	}

	// Create a new Entry
	auto entry = make_shared<Entry>(prefix);
	entry->setHash(hashValue);
	node->m_entry = entry; // link the Entry to its Node
	entry->m_node = node; // link the node to Entry. Used in eraseEntryIfEmpty.

	return {entry, true}; // true: new entry
	}

	// Name Prefix Lookup. Create Name Tree Entry if not found
	shared_ptr<Entry>
	NameTree::lookup(const Name& prefix)
	{
	NFD_LOG_TRACE("lookup " << prefix);

	shared_ptr<Entry> entry;
	shared_ptr<Entry> parent;

	for (size_t i = 0; i <= prefix.size(); ++i) {
	Name temp = prefix.getPrefix(i);

	// insert() will create the entry if it does not exist.
	bool isNew = false;
	std::tie(entry, isNew) = insert(temp);

	if (isNew) {
	++m_nItems; // Increase the counter
	entry->m_parent = parent;

	if (parent != nullptr) {
	parent->m_children.push_back(entry);
	}
	}

	if (m_nItems > m_enlargeThreshold) {
	resize(m_enlargeFactor * m_nBuckets);
	}

	parent = entry;
	}
	return entry;
	}

	shared_ptr<Entry>
	NameTree::lookup(const fib::Entry& fibEntry) const
	{
	shared_ptr<Entry> nte = this->getEntry(fibEntry);
	BOOST_ASSERT(nte == nullptr \|\| nte->getFibEntry() == &fibEntry);
	return nte;
	}

	shared_ptr<Entry>
	NameTree::lookup(const pit::Entry& pitEntry)
	{
	shared_ptr<Entry> nte = this->getEntry(pitEntry);
	if (nte == nullptr) {
	return nullptr;
	}

	if (nte->getPrefix().size() == pitEntry.getName().size()) {
	return nte;
	}

	BOOST_ASSERT(pitEntry.getName().at(-1).isImplicitSha256Digest());
	BOOST_ASSERT(nte->getPrefix() == pitEntry.getName().getPrefix(-1));
	return this->lookup(pitEntry.getName());
	}

	shared_ptr<Entry>
	NameTree::lookup(const measurements::Entry& measurementsEntry) const
	{
	shared_ptr<Entry> nte = this->getEntry(measurementsEntry);
	BOOST_ASSERT(nte == nullptr \|\| nte->getMeasurementsEntry() == &measurementsEntry);
	return nte;
	}

	shared_ptr<Entry>
	NameTree::lookup(const strategy_choice::Entry& strategyChoiceEntry) const
	{
	shared_ptr<Entry> nte = this->getEntry(strategyChoiceEntry);
	BOOST_ASSERT(nte == nullptr \|\| nte->getStrategyChoiceEntry() == &strategyChoiceEntry);
	return nte;
	}

	// return {false: this entry is not empty, true: this entry is empty and erased}
	bool
	NameTree::eraseEntryIfEmpty(shared_ptr<Entry> entry)
	{
	BOOST_ASSERT(entry != nullptr);

	NFD_LOG_TRACE("eraseEntryIfEmpty " << entry->getPrefix());

	// first check if this Entry can be erased
	if (entry->isEmpty()) {
	// update child-related info in the parent
	shared_ptr<Entry> parent = entry->getParent();

	if (parent != nullptr) {
	std::vector<shared_ptr<Entry>>& parentChildrenList = parent->getChildren();

	bool isFound = false;
	size_t size = parentChildrenList.size();
	for (size_t i = 0; i < size; ++i) {
	if (parentChildrenList[i] == entry) {
	parentChildrenList[i] = parentChildrenList[size - 1];
	parentChildrenList.pop_back();
	isFound = true;
	break;
	}
	}

	BOOST_VERIFY(isFound == true);
	}

	// remove this Entry and its Name Tree Node
	Node* node = entry->m_node;
	Node* nodePrev = node->m_prev;

	// configure the previous node
	if (nodePrev != nullptr) {
	// link the previous node to the next node
	nodePrev->m_next = node->m_next;
	}
	else {
	m_buckets[entry->getHash() % m_nBuckets] = node->m_next;
	}

	// link the previous node with the next node (skip the erased one)
	if (node->m_next != nullptr) {
	node->m_next->m_prev = nodePrev;
	node->m_next = 0;
	}

	BOOST_ASSERT(node->m_next == nullptr);

	--m_nItems;
	delete node;

	if (parent != nullptr) {
	eraseEntryIfEmpty(parent);
	}

	size_t newNBuckets = static_cast<size_t>(m_shrinkFactor * static_cast<double>(m_nBuckets));

	if (newNBuckets >= m_minNBuckets && m_nItems < m_shrinkThreshold) {
	resize(newNBuckets);
	}

	return true;

	}

	return false;
	}

	// Exact Match
	shared_ptr<Entry>
	NameTree::findExactMatch(const Name& prefix) const
	{
	NFD_LOG_TRACE("findExactMatch " << prefix);

	size_t hashValue = computeHash(prefix);
	size_t loc = hashValue % m_nBuckets;

	NFD_LOG_TRACE("Name " << prefix << " hash value = " << hashValue << " location = " << loc);

	shared_ptr<Entry> entry;
	Node* node = nullptr;

	for (node = m_buckets[loc]; node != nullptr; node = node->m_next) {
	entry = node->m_entry;
	if (entry != nullptr) {
	if (hashValue == entry->getHash() && prefix == entry->getPrefix()) {
	return entry;
	}
	}
	}

	// if not found, the default value of entry (null pointer) will be returned
	entry.reset();
	return entry;
	}

	// Longest Prefix Match
	shared_ptr<Entry>
	NameTree::findLongestPrefixMatch(const Name& prefix, const EntrySelector& entrySelector) const
	{
	NFD_LOG_TRACE("findLongestPrefixMatch " << prefix);

	shared_ptr<Entry> entry;
	std::vector<size_t> hashValueSet = computeHashSet(prefix);

	size_t hashValue = 0;
	size_t loc = 0;

	for (int i = static_cast<int>(prefix.size()); i >= 0; --i) {
	hashValue = hashValueSet[i];
	loc = hashValue % m_nBuckets;

	Node* node = nullptr;
	for (node = m_buckets[loc]; node != nullptr; node = node->m_next) {
	entry = node->m_entry;
	if (entry != nullptr) {
	// isPrefixOf() is used to avoid making a copy of the name
	if (hashValue == entry->getHash() &&
	entry->getPrefix().isPrefixOf(prefix) &&
	entrySelector(*entry)) {
	return entry;
	}
	}
	}
	}

	return nullptr;
	}

	shared_ptr<Entry>
	NameTree::findLongestPrefixMatch(shared_ptr<Entry> entry,
	const EntrySelector& entrySelector) const
	{
	while (entry != nullptr) {
	if (entrySelector(*entry)) {
	return entry;
	}
	entry = entry->getParent();
	}
	return nullptr;
	}

	shared_ptr<Entry>
	NameTree::findLongestPrefixMatch(const pit::Entry& pitEntry) const
	{
	shared_ptr<Entry> nte = this->getEntry(pitEntry);
	BOOST_ASSERT(nte != nullptr);
	if (nte->getPrefix().size() == pitEntry.getName().size()) {
	return nte;
	}

	BOOST_ASSERT(pitEntry.getName().at(-1).isImplicitSha256Digest());
	BOOST_ASSERT(nte->getPrefix() == 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
	{
	NFD_LOG_TRACE("NameTree::findAllMatches" << prefix);

	// As we are using Name Prefix Hash Table, and the current LPM() is
	// implemented as starting from full name, and reduce the number of
	// components by 1 each time, we could use it here.
	// 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);

	if (entry != nullptr) {
	const_iterator begin(FIND_ALL_MATCHES_TYPE, *this, entry, entrySelector);
	return {begin, end()};
	}
	// If none of the entry satisfies the requirements, then return the end() iterator.
	return {end(), end()};
	}

	boost::iterator_range<NameTree::const_iterator>
	NameTree::fullEnumerate(const EntrySelector& entrySelector) const
	{
	NFD_LOG_TRACE("fullEnumerate");

	// find the first eligible entry
	for (size_t i = 0; i < m_nBuckets; ++i) {
	for (Node* node = m_buckets[i]; node != nullptr; node = node->m_next) {
	if (node->m_entry != nullptr && entrySelector(*node->m_entry)) {
	const_iterator it(FULL_ENUMERATE_TYPE, *this, node->m_entry, entrySelector);
	return {it, end()};
	}
	}
	}

	// If none of the entry satisfies the requirements, then return the end() iterator.
	return {end(), end()};
	}

	boost::iterator_range<NameTree::const_iterator>
	NameTree::partialEnumerate(const Name& prefix,
	const EntrySubTreeSelector& entrySubTreeSelector) const
	{
	// the first step is to process the root node
	shared_ptr<Entry> entry = findExactMatch(prefix);
	if (entry == nullptr) {
	return {end(), end()};
	}

	std::pair<bool, bool> result = entrySubTreeSelector(*entry);
	const_iterator it(PARTIAL_ENUMERATE_TYPE,
	*this,
	entry,
	AnyEntry(),
	entrySubTreeSelector);

	it.m_shouldVisitChildren = (result.second && entry->hasChildren());

	if (result.first) {
	// root node is acceptable
	}
	else {
	// let the ++ operator handle it
	++it;
	}
	return {it, end()};
	}

	// Hash Table Resize
	void
	NameTree::resize(size_t newNBuckets)
	{
	NFD_LOG_TRACE("resize");

	Node** newBuckets = new Node*[newNBuckets];
	size_t count = 0;

	// referenced ccnx hashtb.c hashtb_rehash()
	Node** pp = nullptr;
	Node* p = nullptr;
	Node* pre = nullptr;
	Node* q = nullptr; // record p->m_next

	for (size_t i = 0; i < newNBuckets; ++i) {
	newBuckets[i] = nullptr;
	}

	for (size_t i = 0; i < m_nBuckets; ++i) {
	for (p = m_buckets[i]; p != nullptr; p = q) {
	++count;
	q = p->m_next;
	BOOST_ASSERT(p->m_entry != nullptr);
	uint32_t h = p->m_entry->m_hash;
	uint32_t b = h % newNBuckets;
	pre = nullptr;
	for (pp = &newBuckets[b]; pp != nullptr; pp = &((pp)->m_next)) {
	pre = *pp;
	}
	p->m_prev = pre;
	p->m_next = pp; // Actually pp always == nullptr in this case
	*pp = p;
	}
	}

	BOOST_ASSERT(count == m_nItems);

	Node** oldBuckets = m_buckets;
	m_buckets = newBuckets;
	delete[] oldBuckets;

	m_nBuckets = newNBuckets;
	m_enlargeThreshold = static_cast<size_t>(m_enlargeLoadFactor * static_cast<double>(m_nBuckets));
	m_shrinkThreshold = static_cast<size_t>(m_shrinkLoadFactor * static_cast<double>(m_nBuckets));
	}

	// For debugging
	void
	NameTree::dump(std::ostream& output) const
	{
	NFD_LOG_TRACE("dump()");

	Node* node = nullptr;
	shared_ptr<Entry> entry;

	for (size_t i = 0; i < m_nBuckets; ++i) {
	for (node = m_buckets[i]; node != nullptr; node = node->m_next) {
	entry = node->m_entry;

	// if the Entry exist, dump its information
	if (entry != nullptr) {
	output << "Bucket" << i << '\t' << entry->m_prefix.toUri() << '\n';
	output << "\t\tHash " << entry->m_hash << '\n';

	if (entry->m_parent != nullptr) {
	output << "\t\tparent->" << entry->m_parent->m_prefix.toUri();
	}
	else {
	output << "\t\tROOT";
	}
	output << '\n';

	if (!entry->m_children.empty()) {
	output << "\t\tchildren = " << entry->m_children.size() << '\n';

	for (size_t j = 0; j < entry->m_children.size(); ++j) {
	output << "\t\t\tChild " << j << " " << entry->m_children[j]->getPrefix() << '\n';
	}
	}

	}

	}
	}

	output << "Bucket count = " << m_nBuckets << '\n';
	output << "Stored item = " << m_nItems << '\n';
	output << "--------------------------\n";
	}

	NameTree::const_iterator::const_iterator()
	: m_nameTree(nullptr)
	{
	}

	NameTree::const_iterator::const_iterator(NameTree::IteratorType type,
	const NameTree& nameTree,
	shared_ptr<Entry> entry,
	const EntrySelector& entrySelector,
	const EntrySubTreeSelector& entrySubTreeSelector)
	: m_nameTree(&nameTree)
	, m_entry(entry)
	, m_subTreeRoot(entry)
	, m_entrySelector(make_shared<EntrySelector>(entrySelector))
	, m_entrySubTreeSelector(make_shared<EntrySubTreeSelector>(entrySubTreeSelector))
	, m_type(type)
	, m_shouldVisitChildren(true)
	{
	}

	// operator++()
	NameTree::const_iterator
	NameTree::const_iterator::operator++()
	{
	NFD_LOG_TRACE("const_iterator::operator++()");

	BOOST_ASSERT(m_entry != m_nameTree->m_end);

	if (m_type == FULL_ENUMERATE_TYPE) {
	// process the entries in the same bucket first
	while (m_entry->m_node->m_next != nullptr) {
	m_entry = m_entry->m_node->m_next->m_entry;
	if ((m_entrySelector)(m_entry)) {
	return *this;
	}
	}

	// process other buckets

	for (int newLocation = m_entry->m_hash % m_nameTree->m_nBuckets + 1;
	newLocation < static_cast<int>(m_nameTree->m_nBuckets);
	++newLocation) {
	// process each bucket
	Node* node = m_nameTree->m_buckets[newLocation];
	while (node != nullptr) {
	m_entry = node->m_entry;
	if ((m_entrySelector)(m_entry)) {
	return *this;
	}
	node = node->m_next;
	}
	}

	// Reach the end()
	m_entry = m_nameTree->m_end;
	return *this;
	}

	if (m_type == PARTIAL_ENUMERATE_TYPE) {
	// We use pre-order traversal.
	// if at the root, it could have already been accepted, or this
	// iterator was just declared, and root doesn't satisfy the
	// requirement
	// The if() section handles this special case
	// Essentially, we need to check root's fist child, and the rest will
	// be the same as normal process
	if (m_entry == m_subTreeRoot) {
	if (m_shouldVisitChildren) {
	m_entry = m_entry->getChildren()[0];
	std::pair<bool, bool> result = ((m_entrySubTreeSelector)(m_entry));
	m_shouldVisitChildren = (result.second && m_entry->hasChildren());
	if (result.first) {
	return *this;
	}
	else {
	// the first child did not meet the requirement
	// the rest of the process can just fall through the while loop as normal
	}
	}
	else {
	// no children, should return end();
	// just fall through
	}
	}

	// The first thing to do is to visit its child, or go to find its possible siblings
	while (m_entry != m_subTreeRoot) {
	if (m_shouldVisitChildren) {
	// If this subtree should be visited
	m_entry = m_entry->getChildren()[0];
	std::pair<bool, bool> result = ((m_entrySubTreeSelector)(m_entry));
	m_shouldVisitChildren = (result.second && m_entry->hasChildren());
	if (result.first) { // if this node is acceptable
	return *this;
	}
	else {
	// do nothing, as this node is essentially ignored
	// send this node to the while loop.
	}
	}
	else {
	// Should try to find its sibling
	shared_ptr<Entry> parent = m_entry->getParent();

	std::vector<shared_ptr<Entry>>& parentChildrenList = parent->getChildren();
	bool isFound = false;
	size_t i = 0;
	for (i = 0; i < parentChildrenList.size(); ++i) {
	if (parentChildrenList[i] == m_entry) {
	isFound = true;
	break;
	}
	}

	BOOST_VERIFY(isFound == true);
	if (i < parentChildrenList.size() - 1) { // m_entry not the last child
	m_entry = parentChildrenList[i + 1];
	std::pair<bool, bool> result = ((m_entrySubTreeSelector)(m_entry));
	m_shouldVisitChildren = (result.second && m_entry->hasChildren());
	if (result.first) { // if this node is acceptable
	return *this;
	}
	else {
	// do nothing, as this node is essentially ignored
	// send this node to the while loop.
	}
	}
	else {
	// m_entry is the last child, no more sibling, should try to find parent's sibling
	m_shouldVisitChildren = false;
	m_entry = parent;
	}
	}
	}

	m_entry = m_nameTree->m_end;
	return *this;
	}

	if (m_type == FIND_ALL_MATCHES_TYPE) {
	// Assumption: at the beginning, m_entry was initialized with the first
	// eligible Name Tree entry (i.e., has a PIT entry that can be satisfied
	// by the Data packet)

	while (m_entry->getParent() != nullptr) {
	m_entry = m_entry->getParent();
	if ((m_entrySelector)(m_entry)) {
	return *this;
	}
	}

	// Reach to the end (Root)
	m_entry = m_nameTree->m_end;
	return *this;
	}

	BOOST_ASSERT(false); // unknown type
	return *this;
	}

	} // namespace name_tree
	} // namespace nfd