avl.hxx

Go to the documentation of this file.

#ifndef UTIL_AVL_HXX
#define UTIL_AVL_HXX

/*
 * Copyright (c) 2004, The EROS Group, LLC and Johns Hopkins
 * University. All rights reserved.
 * 
 * This software was developed to support the EROS secure operating
 * system project (http://www.eros-os.org). The latest version of
 * the OpenCM software can be found at http://www.opencm.org.
 * 
 * Redistribution and use in source and binary forms, with or
 * without modification, are permitted provided that the following
 * conditions are met:
 * 
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 
 * 2. Redistributions in binary form must reproduce the above
 *    copyright notice, this list of conditions and the following
 *    disclaimer in the documentation and/or other materials
 *    provided with the distribution.
 * 
 * 3. Neither the name of the The EROS Group, LLC nor the name of
 *    Johns Hopkins University, nor the names of its contributors
 *    may be used to endorse or promote products derived from this
 *    software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

/* This is mildly tricky, because we really don't want to have to
 * polyinstantiate the source code for the whole AVL
 * implementation. We therefore divide matters into a generic
 * BaseAvlNode structure and a generic BaseAvlTree data structure --
 * the latter serves as the container and stores a pointer to the
 * comparison routine.
 *
 * We then use templates to instantiate type-specific avl trees.
 */

// FIX: Following comment needs repair

class BaseAvlNode {
  friend class BaseAvlTree;
  BaseAvlNode *lchild;
  BaseAvlNode *rchild;
  short    balance;             /* legal values are 0, 1, -1 */

  static BaseAvlNode *left_rotate(BaseAvlNode *);
  static BaseAvlNode *right_rotate(BaseAvlNode *);
  static int rebalance_right(BaseAvlNode ** theRoot);
  static int rebalance_left(BaseAvlNode ** theRoot);

 public:
  BaseAvlNode();
  virtual ~BaseAvlNode();

  unsigned short user;          /* user-available field */
};

class BaseAvlNode;

class BaseAvlTree {
protected:
  typedef int (*BaseCmpFn_t)(const BaseAvlNode& n1, const BaseAvlNode& n2);
private:
  BaseCmpFn_t cmpfn;
  BaseAvlNode *root;

  int do_insert(BaseAvlNode **theRoot, BaseAvlNode *nd);
  int do_remove(BaseAvlNode **theRoot, BaseAvlNode *nd);

  static BaseAvlNode** find_greatest(BaseAvlNode**pnd);
public:
  BaseAvlTree(BaseCmpFn_t cmp);
  ~BaseAvlTree();

protected:
  void insert(BaseAvlNode *nd);

  BaseAvlNode *choose();

  BaseAvlNode *least();

  BaseAvlNode *greatest();

  void remove(BaseAvlNode& node);

  BaseAvlNode *lookup(const BaseAvlNode& key);

  BaseAvlNode *lookupGLE(const BaseAvlNode& key);

  /* When iterating over an AvlTree, this function is called on every
     node. If it returns zero, no attempt will be made to reinsert the
     node into the tree, and the called procedure should free the occupied
     storage. */
  typedef int (*AvlIterFunc)(BaseAvlNode&);

  /* calls avlFunc on every node in a tree */
  void iterate(AvlIterFunc avlFunc);
};

// Forward declaration:
template<typename KeyType> class AvlTree;

template<typename KeyType>
class AvlNode : public BaseAvlNode {
  friend class AvlTree<KeyType>;

 public:
  KeyType key;

  AvlNode(KeyType k)
    : key(k)
  {
  }
  ~AvlNode()
  {
  }

protected:
  inline static int compare(const AvlNode& n1, const AvlNode& n2)
  {
      if (n1.key < n2.key)
        return -1;
      if (n1.key > n2.key)
        return 1;
      return 0;
  }
};

// Forward declaration
template<typename KeyType, typename ValueType> class AvlMap;

template<typename KeyType, typename ValueType>
class AvlMapNode : public AvlNode<KeyType> {
  friend class AvlMap<KeyType, ValueType>;

 public:
  ValueType value;

  AvlMapNode(KeyType k, ValueType v)
    : AvlNode<KeyType>(k), value(v)
  {
  }
  ~AvlMapNode()
  {
  }
};

template<typename KeyType>
class AvlTree : public BaseAvlTree {
  typedef AvlNode<KeyType> NodeType;
  typedef AvlNode<KeyType> KeyNodeType;
 public:
  AvlTree()
    : BaseAvlTree((BaseCmpFn_t) AvlNode<KeyType>::compare)
    {
    }
  ~AvlTree()
    {
    }

  inline void insert(const KeyType& key)
    {
      BaseAvlNode::insert(new NodeType(key));
    }

  inline NodeType *choose()
    {
      return (NodeType *) BaseAvlNode::choose();
    }

  inline NodeType *least()
    {
      return (NodeType *) BaseAvlNode::least();
    }

  inline NodeType *greatest()
    {
      return (NodeType *) BaseAvlNode::greatest();
    }

  inline void remove(NodeType &node)
    {
      BaseAvlNode::remove(node);
    }

  inline NodeType *lookup(const KeyNodeType& key)
    {
      return (NodeType *)BaseAvlNode::lookup(key);
    }
  inline NodeType *lookup(KeyType key)
    {
      return lookup(NodeType(key));
    }

  inline NodeType *lookupGLE(const NodeType& key)
    {
      return (NodeType *)BaseAvlNode::lookupGLE(key);
    }
  inline NodeType *lookupGLE(KeyType key)
    {
      return lookupGLE(NodeType(key));
    }

  /* When iterating over an AvlTree, this function is called on every
     node. If it returns zero, no attempt will be made to reinsert the
     node into the tree, and the called procedure should free the occupied
     storage. */
  typedef int (*AvlIterFunc)(NodeType*);

  /* calls avlFunc on every node in a tree */
  inline void iterate(AvlIterFunc avlFunc)
    {
      BaseAvlTree::iterate(avlFunc);
    }
};

template<typename KeyType, typename ValueType>
class AvlMap : public BaseAvlTree {
 public:
  typedef AvlMapNode<KeyType, ValueType> NodeType;
  typedef AvlNode<KeyType> KeyNodeType;

  AvlMap()
    : BaseAvlTree((BaseCmpFn_t) AvlMapNode<KeyType,ValueType>::compare)
    {
    }
  ~AvlMap()
    {
    }

  bool contains(const KeyType& key)
  {
    return lookup(key) ? true : false;
  }

  inline void insert(const KeyType& key, const ValueType& v)
    {
      BaseAvlTree::insert(new NodeType(key,v));
    }

  inline NodeType *choose()
    {
      return (NodeType *) BaseAvlTree::choose();
    }

  inline NodeType *least()
    {
      return (NodeType *) BaseAvlTree::least();
    }

  inline NodeType *greatest()
    {
      return (NodeType *) BaseAvlTree::greatest();
    }

  inline void remove(NodeType &node)
    {
      BaseAvlTree::remove(node);
    }

#if 0
  inline void removeByKey(const KeyType& key)
    {
      NodeType *nd = lookup(key);
      if (!nd)
        THROW(ExBadValue, "Key not in map");
      BaseAvlTree::remove(*nd);
    }
#endif

  inline NodeType *lookup(const KeyNodeType& key)
    {
      return (NodeType *)BaseAvlTree::lookup(key);
    }
  inline NodeType *lookup(const KeyType& key)
    {
      return lookup(KeyNodeType(key));
    }

  inline NodeType *lookupGLE(const NodeType& key)
    {
      return (NodeType *)BaseAvlTree::lookupGLE(key);
    }
  inline NodeType *lookupGLE(KeyType key)
    {
      return lookupGLE(NodeType(key));
    }

  /* When iterating over an AvlMap, this function is called on every
     node. If it returns zero, no attempt will be made to reinsert the
     node into the tree, and the called procedure should free the occupied
     storage. */
  typedef int (*AvlIterFunc)(NodeType*);

  /* calls avlFunc on every node in a tree */
  inline void iterate(AvlIterFunc avlFunc)
    {
      BaseAvlTree::iterate(avlFunc);
    }
};

template<typename KeyType>
struct AvlSet : public AvlMap<KeyType, bool> {
  typedef AvlMapNode<KeyType, bool> NodeType;

  void insert(const KeyType& key)
  {
    if (!contains(key))
      AvlMap<KeyType, bool>::insert(key, true);
  }

  void remove(const KeyType& key)
  {
    NodeType *nd = lookup(key);
    if (!nd)
      THROW(ExBadValue, "Key not in set");
    AvlMap<KeyType, bool>::remove(*nd);
  }
};

// Local Variables:
// mode:c++
// End:

#endif /* UTIL_AVL_HXX */

---