daemon/table/name-tree.cpp

/* -*- 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