RadixTree.h

Go to the documentation of this file.

/*
 * Copyright (c) 2008-2014, Pedigree Developers
 *
 * Please see the CONTRIB file in the root of the source tree for a full
 * list of contributors.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
 
#ifndef KERNEL_UTILITIES_RADIX_TREE_H
#define KERNEL_UTILITIES_RADIX_TREE_H
 
#include "pedigree/kernel/Log.h"
#include "pedigree/kernel/compiler.h"
#include "pedigree/kernel/processor/types.h"
#include "pedigree/kernel/utilities/Cord.h"
#include "pedigree/kernel/utilities/Iterator.h"
#include "pedigree/kernel/utilities/ObjectPool.h"
#include "pedigree/kernel/utilities/Result.h"
#include "pedigree/kernel/utilities/String.h"
#include "pedigree/kernel/utilities/Vector.h"
#include "pedigree/kernel/utilities/utility.h"
 
template <class T>
class EXPORTED_PUBLIC RadixTree {
 private:
  class Node {
   public:
    typedef Vector<Node*> childlist_t;
    enum MatchType {
      ExactMatch,    
      NoMatch,       
      PartialMatch,  
      OverMatch      
    };
 
    Node(bool bCaseSensitive)
        : m_Key(),
          value(T()),
          m_Children(),
          m_pParent(0),
          m_bCaseSensitive(bCaseSensitive),
          m_pParentTree(0),
          m_bHasValue(false) {}
 
    ~Node();
 
    // Clears all known children and returns them to the parent ObjectPool
    void returnAllChildren();
 
    Node* next() {
      return doNext();
    }
    Node* previous() {
      return 0;
    }
 
    Node* findChild(const char* cpKey) const;
 
    void addChild(Node* pNode);
 
    void replaceChild(Node* pNodeOld, Node* pNodeNew);
 
    void removeChild(Node* pChild);
 
    MatchType matchKey(const char* cpKey, size_t& offset) const;
 
    Node* getFirstChild() const;
 
    void prependKey(const String& cpKey);
 
    void setKey(const char* cpKey);
    void setKey(const char* cpKey, size_t lengthHint);
    void setKey(const String& cpKey);
    inline const char* getKey() const {
      return m_Key.cstr();
    }
    const String& getKeyStr() const {
      return m_Key;
    }
    inline void setValue(const T& pV) {
      value = pV;
      m_bHasValue = true;
    }
    inline void removeValue() {
      value = T();
      m_bHasValue = false;
    }
    inline const T& getValue() const {
      return value;
    }
    inline void setParent(Node* pP) {
      m_pParent = pP;
    }
    inline Node* getParent() const {
      return m_pParent;
    }
    inline bool hasValue() const {
      return m_bHasValue;
    }
 
    void dump(void (*emit_line)(const char* s)) const;
 
    String m_Key;
    T value;
    childlist_t m_Children;
    Node* m_pParent;
    const bool m_bCaseSensitive;
 
    RadixTree* m_pParentTree;
 
    bool m_bHasValue;
 
   private:
    Node(const Node&);
    Node& operator=(const Node&);
 
    Node* doNext() const;
 
    Node* getNextSibling() const;
  };
 
 public:
  typedef ::Iterator<T, Node> Iterator;
  typedef typename Iterator::Const ConstIterator;
  typedef Result<T, bool> LookupType;
 
  RadixTree();
  RadixTree(const RadixTree<T>& x);
  RadixTree(bool bCaseSensitive);
  ~RadixTree();
 
  RadixTree& operator=(const RadixTree& x);
 
  size_t count() const;
  void insert(const String& key, const T& value);
  MUST_USE_RESULT bool lookup(const String& key, T& value) const;
 
  template <typename U = T>
  typename pedigree_std::enable_if<pedigree_std::is_same<U, T>::value &&
                                       !pedigree_std::is_same<U, void*>::value,
                                   LookupType>::type
  lookup(const String& key) const {
    T value = T();
    if (lookup(key, value)) {
      return LookupType::withValue(value);
    }
    return LookupType::withError(true);
  }
  void remove(const String& key);
 
  void clear();
 
  Iterator erase(Iterator iter) {
    Node* iterNode = iter.__getNode();
    Node* next = iterNode->next();
    remove(iterNode->getKeyStr());
    Iterator ret(next);
    return ret;
  }
 
  inline Iterator begin() {
    if (!m_pRoot) {
      return Iterator(0);
    }
    return Iterator(m_pRoot->hasValue() ? m_pRoot : m_pRoot->next());
  }
  inline ConstIterator begin() const {
    if (!m_pRoot) {
      return ConstIterator(0);
    }
    return ConstIterator(m_pRoot->hasValue() ? m_pRoot : m_pRoot->next());
  }
  inline Iterator end() {
    return Iterator(0);
  }
  inline ConstIterator end() const {
    return ConstIterator(0);
  }
 
  void dump(void (*emit_line)(const char* s)) const;
 
 private:
  Node* cloneNode(Node* node, Node* parent);
  Node* getNewNode() {
    Node* p = m_NodePool.allocate(m_bCaseSensitive);
    p->m_pParent = 0;
    p->m_pParentTree = this;
    return p;
  }
  void returnNode(Node* p) {
    if (p) {
      p->returnAllChildren();
      // wipe out info that shouldn't go back to the pool
      p->m_Key.clear();
      p->value = T();
      p->m_pParent = 0;
      p->m_bHasValue = false;
      m_NodePool.deallocate(p);
    }
  }
 
  size_t m_nItems;
  Node* m_pRoot;
  const bool m_bCaseSensitive;
  ObjectPool<Node> m_NodePool;
};
 
template <class T>
RadixTree<T>::RadixTree() : m_nItems(0), m_pRoot(0), m_bCaseSensitive(true), m_NodePool() {}
 
template <class T>
RadixTree<T>::RadixTree(bool bCaseSensitive)
    : m_nItems(0), m_pRoot(0), m_bCaseSensitive(bCaseSensitive), m_NodePool() {}
 
template <class T>
RadixTree<T>::~RadixTree() {
  clear();
  returnNode(m_pRoot);
}
 
template <class T>
RadixTree<T>::RadixTree(const RadixTree& x)
    : m_nItems(0), m_pRoot(0), m_bCaseSensitive(x.m_bCaseSensitive), m_NodePool() {
  clear();
  returnNode(m_pRoot);
  m_pRoot = cloneNode(x.m_pRoot, 0);
  m_nItems = x.m_nItems;
}
 
template <class T>
RadixTree<T>& RadixTree<T>::operator=(const RadixTree& x) {
  if (this == &x)
    return *this;
 
  clear();
  returnNode(m_pRoot);
  m_pRoot = cloneNode(x.m_pRoot, 0);
  m_nItems = x.m_nItems;
  return *this;
}
 
template <class T>
size_t RadixTree<T>::count() const {
  return m_nItems;
}
 
template <class T>
void RadixTree<T>::insert(const String& key, const T& value) {
  if (!m_pRoot) {
    // The root node always exists and is a lambda transition node
    // (zero-length key). This removes the need for most special cases.
    m_pRoot = getNewNode();
    m_pRoot->setKey(0);
  }
 
  if (!key.length()) {
    if (!m_pRoot->hasValue())
      ++m_nItems;
    m_pRoot->setValue(value);
    return;
  }
 
  Node* pNode = m_pRoot;
 
  const char* cpKey = static_cast<const char*>(key);
  const char* cpKeyOrig = cpKey;
  size_t cpKeyLength = key.length();
 
  while (true) {
    size_t partialOffset = 0;
    switch (pNode->matchKey(cpKey, partialOffset)) {
      case Node::ExactMatch: {
        if (!pNode->hasValue()) {
          m_nItems++;
        }
 
        pNode->setValue(value);
        return;
      }
      case Node::NoMatch: {
        FATAL("RadixTree: algorithmic error!");
        break;
      }
      case Node::PartialMatch: {
        // We need to create an intermediate node that contains the
        // partial match, then adjust the key of this node.
 
        // Find the common key prefix.
        size_t i = partialOffset;
 
        Node* pInter = getNewNode();
 
        // Intermediate node's key is the common prefix of both keys.
        pInter->m_Key.assign(cpKey, partialOffset);
 
        // Must do this before pNode's key is changed.
        pNode->getParent()->replaceChild(pNode, pInter);
 
        // pNode's new key is the uncommon postfix.
        size_t len = pNode->m_Key.length();
 
        pNode->m_Key.ltrim(partialOffset);
 
        // If the uncommon postfix of the key is non-zero length, we
        // have to create another node, a child of pInter.
        if (cpKey[partialOffset] != 0) {
          Node* pChild = getNewNode();
          pChild->setKey(&cpKey[partialOffset],
                         (cpKeyLength - partialOffset - (cpKey - cpKeyOrig)));
          pChild->setValue(value);
          pChild->setParent(pInter);
          pInter->addChild(pChild);
        } else {
          pInter->setValue(value);
        }
 
        pInter->setParent(pNode->getParent());
        pInter->addChild(pNode);
        pNode->setParent(pInter);
 
        m_nItems++;
        return;
      }
      case Node::OverMatch: {
        cpKey += pNode->m_Key.length();
 
        Node* pChild = pNode->findChild(cpKey);
        if (pChild) {
          pNode = pChild;
          // Iterative case.
          break;
        } else {
          // No child - create a new one.
          pChild = getNewNode();
          pChild->setKey(cpKey, cpKeyLength - (cpKey - cpKeyOrig));
          pChild->setValue(value);
          pChild->setParent(pNode);
          pNode->addChild(pChild);
 
          m_nItems++;
          return;
        }
      }
    }
  }
}
 
template <class T>
bool RadixTree<T>::lookup(const String& key, T& value) const {
  value = T();
 
  if (!m_pRoot) {
    return false;
  }
 
  if (!key.length()) {
    if (m_pRoot->hasValue()) {
      value = m_pRoot->getValue();
      return true;
    }
    return false;
  }
 
  Node* pNode = m_pRoot;
 
  const char* cpKey = static_cast<const char*>(key);
 
  while (true) {
    size_t offset = 0;
    switch (pNode->matchKey(cpKey, offset)) {
      case Node::ExactMatch:
        if (!pNode->hasValue()) {
          // No value here, exact match on key. This can happen in
          // cases where we needed to create a node to split a key
          // but nothing was attached to the split node.
          return false;
        }
        value = pNode->getValue();
        return true;
      case Node::NoMatch:
      case Node::PartialMatch:
        return false;
      case Node::OverMatch: {
        cpKey += pNode->m_Key.length();
 
        Node* pChild = pNode->findChild(cpKey);
        if (pChild) {
          pNode = pChild;
          // Iterative case.
          break;
        } else {
          return false;
        }
      }
    }
  }
}
 
template <class T>
void RadixTree<T>::remove(const String& key) {
  if (!m_pRoot) {
    // The root node always exists and is a lambda transition node
    // (zero-length key). This removes the need for most special cases.
    m_pRoot = getNewNode();
    m_pRoot->setKey(0);
  }
 
  Node* pNode = m_pRoot;
 
  const char* cpKey = static_cast<const char*>(key);
 
  // Our invariant is that the root node always exists. Therefore we must
  // special case here so it doesn't get deleted.
  if (!cpKey || (*cpKey == 0)) {
    if (m_pRoot->hasValue()) {
      m_pRoot->removeValue();
      --m_nItems;
    }
    return;
  }
 
  while (true) {
    size_t offset = 0;
    switch (pNode->matchKey(cpKey, offset)) {
      case Node::ExactMatch: {
        if (!pNode->hasValue())
          return;
 
        // Delete this node. If we set the value to zero, it is
        // effectively removed from the map. There are only certain
        // cases in which we can delete the node completely, however.
        pNode->removeValue();
        m_nItems--;
 
        // We have the invariant that the tree is always optimised. This
        // means that when we delete a node we only have to optimise the
        // local branch. There are two situations that need covering:
        //   (a) No children. This means it's a leaf node and can be
        //   deleted. We then need to consider its parent,
        //       which, if its value is zero and now has zero or one
        //       children can be optimised itself.
        //   (b) One child. This is a linear progression and the child
        //   node's key can be changed to be concatenation of
        //       pNode's and its. This doesn't affect anything farther
        //       up the tree and so no recursion is needed.
 
        Node* pParent = 0;
        if (pNode->m_Children.count() == 0) {
          // Leaf node, can just delete.
          pParent = pNode->getParent();
          pParent->removeChild(pNode);
          returnNode(pNode);
 
          pNode = pParent;
          // Optimise up the tree.
          while (true) {
            if (pNode == m_pRoot)
              return;
 
            if (pNode->m_Children.count() == 1 && !pNode->hasValue())
              // Break out of this loop and get caught in the next
              // if(pNode->m_nChildren == 1)
              break;
 
            if (pNode->m_Children.count() == 0 && !pNode->hasValue()) {
              // Leaf node, can just delete.
              pParent = pNode->getParent();
              pParent->removeChild(pNode);
              returnNode(pNode);
 
              pNode = pParent;
              continue;
            }
            return;
          }
        }
 
        if (pNode->m_Children.count() == 1) {
          // Change the child's key to be the concatenation of ours
          // and its.
          Node* pChild = pNode->getFirstChild();
          pParent = pNode->getParent();
 
          // Must call this before delete, so pChild doesn't get
          // deleted.
          pNode->removeChild(pChild);
 
          pChild->prependKey(pNode->getKeyStr());
          pChild->setParent(pParent);
          pParent->removeChild(pNode);
          pParent->addChild(pChild);
 
          returnNode(pNode);
        }
        return;
      }
      case Node::NoMatch:
      case Node::PartialMatch:
        // Can't happen unless the key didn't actually exist.
        return;
      case Node::OverMatch: {
        cpKey += pNode->m_Key.length();
 
        Node* pChild = pNode->findChild(cpKey);
        if (pChild) {
          pNode = pChild;
          // Iterative case.
          break;
        } else
          return;
      }
    }
  }
}
 
template <class T>
typename RadixTree<T>::Node* RadixTree<T>::cloneNode(Node* pNode, Node* pParent) {
  // Deal with the easy case first.
  if (!pNode)
    return 0;
 
  Node* n = getNewNode();
  n->setKey(pNode->m_Key);
  if (pNode->hasValue())
    n->setValue(pNode->value);
  n->setParent(pParent);
 
  for (typename RadixTree<T>::Node::childlist_t::Iterator it = pNode->m_Children.begin();
       it != pNode->m_Children.end(); ++it) {
    n->addChild(cloneNode((*it), n));
  }
 
  return n;
}
 
template <class T>
void RadixTree<T>::clear() {
  if (!m_pRoot)
    m_pRoot = getNewNode();
  else
    m_pRoot->returnAllChildren();
 
  m_pRoot->setKey(0);
  m_pRoot->removeValue();
  m_pRoot->setParent(0);
  m_nItems = 0;
}
 
template <class T>
void RadixTree<T>::dump(void (*emit_line)(const char* s)) const {
  if (m_pRoot) {
    m_pRoot->dump(emit_line);
  }
}
 
//
// RadixTree::Node implementation.
//
 
template <class T>
RadixTree<T>::Node::~Node() {
  returnAllChildren();
}
 
template <class T>
void RadixTree<T>::Node::returnAllChildren() {
  // Returns depth-first, which ensures we're not returning any children
  // while the ObjectPool lock is held.
  for (auto it : m_Children) {
    it->returnAllChildren();
    m_pParentTree->returnNode(it);
  }
 
  m_Children.clear();
}
 
template <class T>
typename RadixTree<T>::Node* RadixTree<T>::Node::findChild(const char* cpKey) const {
  for (auto it : m_Children) {
    size_t offset = 0;
    if (it->matchKey(cpKey, offset) != NoMatch) {
      return it;
    }
  }
  return 0;
}
 
template <class T>
void RadixTree<T>::Node::addChild(Node* pNode) {
  if (pNode)
    m_Children.pushBack(pNode);
}
 
template <class T>
void RadixTree<T>::Node::replaceChild(Node* pNodeOld, Node* pNodeNew) {
  for (auto it = m_Children.begin(); it != m_Children.end(); ++it) {
    if (*it == pNodeOld) {
      *it = pNodeNew;
      break;
    }
  }
}
 
template <class T>
void RadixTree<T>::Node::removeChild(Node* pChild) {
  for (typename RadixTree<T>::Node::childlist_t::Iterator it = m_Children.begin();
       it != m_Children.end();) {
    if ((*it) == pChild) {
      it = m_Children.erase(it);
    } else
      ++it;
  }
}
 
template <class T>
typename RadixTree<T>::Node::MatchType RadixTree<T>::Node::matchKey(const char* cpKey,
                                                                    size_t& offset) const {
  // Cannot partially match (e.g. toast/toastier == PartialMatch if the
  // cpKey is longer (e.g. toastier/toast == OverMatch)).
  if (!m_Key.length()) {
    return OverMatch;
  }
 
  const char* myKey = getKey();
 
  // Do some quick checks early.
  if ((m_bCaseSensitive && (cpKey[0] != myKey[0])) ||
      ((!m_bCaseSensitive) && (toLower(cpKey[0]) != toLower(myKey[0])))) {
    // non-partial, first character didn't even match
    return NoMatch;
  }
 
  size_t i = 0;
  int r = StringCompareCase(cpKey, myKey, m_bCaseSensitive, m_Key.length() + 1, &i);
 
  if (r == 0) {
    // exact match, all characters & null terminators matched
    return ExactMatch;
  } else if (m_Key[i] == 0) {
    return OverMatch;
  } else {
    // partial, both strings share a common prefix
    offset = i;
    return PartialMatch;
  }
}
 
template <class T>
void RadixTree<T>::Node::setKey(const char* cpKey) {
  m_Key.assign(cpKey);
}
 
template <class T>
void RadixTree<T>::Node::setKey(const char* cpKey, size_t lengthHint) {
  m_Key.assign(cpKey, lengthHint);
}
 
template <class T>
void RadixTree<T>::Node::setKey(const String& cpKey) {
  m_Key.assign(cpKey);
}
 
template <class T>
typename RadixTree<T>::Node* RadixTree<T>::Node::getFirstChild() const {
  return *(m_Children.begin());
}
 
template <class T>
void RadixTree<T>::Node::prependKey(const String& cpKey) {
  String tmp = pedigree_std::move(m_Key);
  m_Key.assign(cpKey);
  m_Key += tmp;
}
 
template <class T>
typename RadixTree<T>::Node* RadixTree<T>::Node::doNext() const {
  // pNode needs to be settable, but not what it points to!
  Node const* pNode = this;
  while ((pNode == this) || (pNode && !pNode->hasValue())) {
    Node const* tmp;
    if (pNode->m_Children.count())
      pNode = pNode->getFirstChild();
    else {
      tmp = pNode;
      pNode = 0;
      while (tmp && tmp->m_pParent != 0 /* Root node */) {
        if ((pNode = tmp->getNextSibling()) != 0)
          break;
        tmp = tmp->m_pParent;
      }
      if (tmp->m_pParent == 0)
        return 0;
    }
  }
  return const_cast<Node*>(pNode);
}
 
template <class T>
typename RadixTree<T>::Node* RadixTree<T>::Node::getNextSibling() const {
  if (!m_pParent)
    return 0;
 
  bool b = false;
  for (typename RadixTree<T>::Node::childlist_t::Iterator it = m_pParent->m_Children.begin();
       it != m_pParent->m_Children.end(); ++it) {
    if (b)
      return (*it);
    if ((*it) == this)
      b = true;
  }
 
  return 0;
}
 
template <class T>
void RadixTree<T>::Node::dump(void (*emit_line)(const char* s)) const {
  for (auto it : m_Children) {
    // depth-first dump the next node
    it->dump(emit_line);
 
    // dump this connection
    String s;
    s.Format("  \"Node<%p: %s>\" -> \"Node<%p: %s>\";", static_cast<const void*>(it), it->getKey(),
             static_cast<const void*>(this), static_cast<const char*>(m_Key));
    emit_line(static_cast<const char*>(s));
  }
}
 
// Explicitly instantiate RadixTree<void*> early.
extern template class RadixTree<void*>;  // IWYU pragma: keep
 
#endif