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