1  /*
   2   * \brief  AVL tree
   3   * \author Norman Feske
   4   * \date   2006-04-12
   5   */
   6  
   7  /*
   8   * Copyright (C) 2006-2010 Genode Labs GmbH
   9   *
  10   * This file is part of the Genode OS framework, which is distributed
  11   * under the terms of the GNU General Public License version 2.
  12   */
  13  
  14  #ifndef _INCLUDE__UTIL__AVL_TREE_H_
  15  #define _INCLUDE__UTIL__AVL_TREE_H_
  16  
  17  #include <util/misc_math.h>
  18  
  19  namespace Genode {
  20  
  21     class Avl_node_base
  22     {
  23        protected:
  24  
  25           /**
  26            * Internal policy interface
  27            *
  28            * The implementation of this interface is provided by the AVL tree.
  29            */
  30           struct Policy
  31           {
  32              /**
  33               * Compare two nodes
  34               *
  35               * \retval false if n2 is lower than n1
  36               * \retval true  if n2 is higher than or equal to n1
  37               *
  38               * This function must be provided by the derived class.
  39               * It determines the order of nodes inside the avl tree.
  40               */
  41              virtual bool higher(Avl_node_base *n1, Avl_node_base *n2) const = 0;
  42  
  43              /**
  44               * Node recomputation hook
  45               *
  46               * If a node gets rearranged, this function is called.
  47               * It can be used to update avl-tree-position dependent
  48               * meta data.
  49               */
  50              virtual void recompute(Avl_node_base *) { }
  51           };
  52  
  53           Avl_node_base *_child[2];  /* left and right subtrees */
  54           Avl_node_base *_parent;    /* parent of subtree       */
  55           unsigned char  _depth;     /* depth of subtree        */
  56  
  57        public:
  58  
  59           typedef bool Side;
  60  
  61           enum { LEFT = false, RIGHT = true };
  62  
  63        private:
  64  
  65           /**
  66            * Determine depth of subtree
  67            */
  68           inline int _child_depth(Side i) {
  69              return _child[i] ? _child[i]->_depth : 0; }
  70  
  71           /**
  72            * Update depth of node
  73            */
  74           void _recompute_depth(Policy &policy);
  75  
  76           /**
  77            * Determine left-right bias of both subtrees
  78            */
  79           inline Side _bias() {
  80              return (_child_depth(RIGHT) > _child_depth(LEFT)); }
  81  
  82           /**
  83            * Insert subtree into specified side of the node
  84            */
  85           void _adopt(Avl_node_base *node, Side i, Policy &policy);
  86  
  87           /**
  88            * Rotate subtree
  89            *
  90            * \param side   direction of rotate operation
  91            * \param node   subtree to rotate
  92            *
  93            * The local node_* variable names describe node locations for
  94            * the left (default) rotation. For example, node_r_l is the
  95            * left of the right of node.
  96            */
  97           void _rotate_subtree(Avl_node_base *node, Side side, Policy &policy);
  98  
  99           /**
 100            * Rebalance subtree
 101            *
 102            * \param node   immediate child that needs balancing
 103            *
 104            * `this` is parent of the subtree to rebalance
 105            */
 106           void _rebalance_subtree(Avl_node_base *node, Policy &policy);
 107  
 108        public:
 109  
 110           /**
 111            * Constructor
 112            */
 113           Avl_node_base();
 114  
 115           /**
 116            * Insert new node into subtree
 117            */
 118           void insert(Avl_node_base *node, Policy &policy);
 119  
 120           /**
 121            * Remove node from tree
 122            */
 123           void remove(Policy &policy);
 124     };
 125  
 126  
 127     /**
 128      * AVL node
 129      *
 130      * \param NT  type of the class derived from `Avl_node`
 131      *
 132      * Each object to be stored in the avl tree must be derived from
 133      * `Avl_node`. The type of the derived class is to be specified as
 134      * template argument to enable `Avl_node` to call virtual functions
 135      * specific for the derived class.
 136      */
 137     template <typename NT>
 138     class Avl_node : public Avl_node_base
 139     {
 140        public:
 141  
 142           inline NT *child(Side i) const { return static_cast<NT *>(_child[i]); }
 143  
 144           /**
 145            * Default policy
 146            */
 147           void recompute() { }
 148     };
 149  
 150  
 151     /**
 152      * Root node of the AVL tree
 153      *
 154      * The real nodes are always attached at the left branch of
 155      * this root node.
 156      */
 157     template <typename NT>
 158     class Avl_tree : Avl_node<NT>
 159     {
 160        private:
 161  
 162           /**
 163            * Auto-generated policy class specific for NT
 164            */
 165           class Policy : public Avl_node_base::Policy
 166           {
 167              bool higher(Avl_node_base *n1, Avl_node_base *n2) const
 168              {
 169                 return static_cast<NT *>(n1)->higher(static_cast<NT *>(n2));
 170              }
 171  
 172              void recompute(Avl_node_base *node)
 173              {
 174                 static_cast<NT *>(node)->recompute();
 175              }
 176  
 177           } _policy;
 178  
 179        public:
 180  
 181           /**
 182            * Insert node into AVL tree
 183            */
 184           void insert(Avl_node<NT> *node) { Avl_node_base::insert(node, _policy); }
 185  
 186           /**
 187            * Remove node from AVL tree
 188            */
 189           void remove(Avl_node<NT> *node) { node->remove(_policy); }
 190  
 191           /**
 192            * Request first node of the tree
 193            *
 194            * \return  first node
 195            * \retval  NULL if tree is empty
 196            */
 197           inline NT *first() const { return child(Avl_node<NT>::LEFT); }
 198     };
 199  }
 200  
 201  #endif /* _INCLUDE__UTIL__AVL_TREE_H_ */
© 2010 Genode Labs