l4/pkg/cxx/lib/tl/include/avl_tree

   1 // vi:ft=cpp
   2 /**
   3  * \file
   4  * \brief AVL tree
   5  */
   6 /*
   7  * (c) 2008-2009 Alexander Warg <warg@os.inf.tu-dresden.de>,
   8  *               Carsten Weinhold <weinhold@os.inf.tu-dresden.de>
   9  *     economic rights: Technische Universität Dresden (Germany)
  10  *
  11  * This file is part of TUD:OS and distributed under the terms of the
  12  * GNU General Public License 2.
  13  * Please see the COPYING-GPL-2 file for details.
  14  *
  15  * As a special exception, you may use this file as part of a free software
  16  * library without restriction.  Specifically, if other files instantiate
  17  * templates or use macros or inline functions from this file, or you compile
  18  * this file and link it with other files to produce an executable, this
  19  * file does not by itself cause the resulting executable to be covered by
  20  * the GNU General Public License.  This exception does not however
  21  * invalidate any other reasons why the executable file might be covered by
  22  * the GNU General Public License.
  23  */
  24
  25 #pragma once
  26
  27 #include "std_ops"
  28 #include "pair"
  29
  30 #include "bits/bst.h"
  31 #include "bits/bst_iter.h"
  32
  33 namespace cxx {
  34
  35 /**
  36  * \brief Node of an AVL tree.
  37  */
  38 class Avl_tree_node : public Bits::Bst_node
  39 {
  40 private:
  41   template< typename Node, typename Get_key, typename Compare >
  42   friend class Avl_tree;
  43
  44   /// Shortcut for Balance values (we use Direction for that).
  45   typedef Bits::Direction Bal;
  46   /// Alia for Direction.
  47   typedef Bits::Direction Dir;
  48
  49   /// We are a finaly BST node, hide interior.
  50   /*@{*/
  51   using Bits::Bst_node::next;
  52   using Bits::Bst_node::next_p;
  53   using Bits::Bst_node::rotate;
  54   /*@}*/
  55
  56   /// The balance value (#Direction::N is balanced).
  57   Bal _balance;
  58
  59 protected:
  60   /// Create an uninitialized node, this is what you shoulkd do.
  61   Avl_tree_node() {}
  62
  63 private:
  64   /// Hide copy
  65   Avl_tree_node(Avl_tree_node const &o);
  66
  67   /// private assignment for initialization and relinkage.
  68   void operator = (Avl_tree_node const &o)
  69   {
  70     Bits::Bst_node::operator = (o);
  71     _balance = o._balance;
  72   }
  73
  74   /// Create an initialized node (for internal stuff).
  75   explicit Avl_tree_node(bool) : Bits::Bst_node(true), _balance(Dir::N) {}
  76
  77   /// Double rotation of \a t.
  78   static Bits::Bst_node *rotate2(Bst_node **t, Bal idir, Bal pre);
  79
  80   /// Is this subtree balanced?
  81   bool balanced() const { return _balance == Bal::N; }
  82
  83   /// What is the balance of this subtree?
  84   Bal balance() const { return _balance; }
  85
  86   /// Set the balance of this subtree to \a b.
  87   void balance(Bal b) { _balance = b; }
  88 };
  89
  90
  91 /**
  92  * \brief A generic AVL tree.
  93  * \param Node the data type of the nodes (must inherit from Avl_tree_noed).
  94  * \param Get_key the meta fcuntion to get the key value from a node.
  95  *                The implementation uses Get_key::key_of(ptr_to_node).
  96  * \param Compare binary relation to establish a total order for the
  97  *                nodes of the tree. Compare()(l, r) must return true if
  98  *                the key \a l is smaller than the key \a r.
  99  */
 100 template< typename Node, typename Get_key,
 101           typename Compare = Lt_functor<typename Get_key::Key_type> >
 102 class Avl_tree : public Bits::Bst<Node, Get_key, Compare>
 103 {
 104 private:
 105   typedef Bits::Bst<Node, Get_key, Compare> Bst;
 106
 107   /// Hide this from possible descendants.
 108   using Bst::_head;
 109
 110   /// Provide access to keys of nodes.
 111   using Bst::k;
 112
 113   /// Alias type for balance values.
 114   typedef typename Avl_tree_node::Bal Bal;
 115   /// Alias type for Direction values.
 116   typedef typename Avl_tree_node::Bal Dir;
 117
 118   /// Prohibit simple copy.
 119   Avl_tree(Avl_tree const &o);
 120
 121   /// Prohibit simple copy.
 122   void operator = (Avl_tree const &o);
 123
 124 public:
 125   //@{
 126   typedef typename Bst::Key_type Key_type;
 127   typedef typename Bst::Key_param_type Key_param_type;
 128   //@}
 129
 130   /// Grab iterator types from Bst
 131   //@{
 132   /// Forward iterator for the set.
 133   typedef typename Bst::Iterator Iterator;
 134   /// Constant forward iterator for the set.
 135   typedef typename Bst::Const_iterator Const_iterator;
 136   /// Backward iterator for the set.
 137   typedef typename Bst::Rev_iterator Rev_iterator;
 138   /// Constant backward iterator for the set.
 139   typedef typename Bst::Const_rev_iterator Const_rev_iterator;
 140   //@}
 141
 142   /**
 143    * \brief Insert a new node into this AVL tree.
 144    * \param new_node a pointer to the new node. This node must not
 145    *                 already b in an AVL tree.
 146    * \return A pair, with second set to 'true' and first pointing to
 147    *         \a new_node, on success.  If there is already a node with the
 148    *         same key that first point to this node and second is 'false'.
 149    */
 150   Pair<Node *, bool> insert(Node *new_node);
 151
 152   /**
 153    * \brief Remove the node with \a key from the tree.
 154    * \param key The node to remove.
 155    * \return The pointer to the removed node on success,
 156    *         or NULL -3 if no node with the \a key exists.
 157    */
 158   Node *remove(Key_param_type key);
 159   /**
 160    * \brief An alias for remove().
 161    */
 162   Node *erase(Key_param_type key) { return remove(key); }
 163
 164   /// Create an empty AVL tree.
 165   Avl_tree() : Bst() {}
 166   /// Destroy, and free the set.
 167   ~Avl_tree()
 168   {
 169     Bits::Bst_node const *n;
 170     while ((n = _head))
 171       remove(k(n));
 172   }
 173
 174 #ifdef __DEBUG_L4_AVL
 175   bool rec_dump(Avl_tree_node *n, int depth, int *dp, bool print, char pfx);
 176   bool rec_dump(bool print)
 177   {
 178     int dp=0;
 179     return rec_dump(static_cast<Avl_tree_node *>(_head), 0, &dp, print, '+');
 180   }
 181 #endif
 182 };
 183
 184
 185 //----------------------------------------------------------------------------
 186 /* IMPLEMENTATION: Bits::__Bst_iter_b */
 187
 188
 189 inline
 190 Bits::Bst_node *
 191 Avl_tree_node::rotate2(Bst_node **t, Bal idir, Bal pre)
 192 {
 193   typedef Bits::Bst_node N;
 194   typedef Avl_tree_node A;
 195   N *tmp[2] = { *t, N::next(*t, idir) };
 196   *t = N::next(tmp[1], !idir);
 197   A *n = static_cast<A*>(*t);
 198
 199   N::next(tmp[0], idir, N::next(n, !idir));
 200   N::next(tmp[1], !idir, N::next(n, idir));
 201   N::next(n, !idir, tmp[0]);
 202   N::next(n, idir, tmp[1]);
 203
 204   n->balance(Bal::N);
 205
 206   if (pre == Bal::N)
 207     {
 208       static_cast<A*>(tmp[0])->balance(Bal::N);
 209       static_cast<A*>(tmp[1])->balance(Bal::N);
 210       return 0;
 211     }
 212
 213   static_cast<A*>(tmp[pre != idir])->balance(!pre);
 214   static_cast<A*>(tmp[pre == idir])->balance(Bal::N);
 215
 216   return N::next(tmp[pre == idir], !pre);
 217 }
 218
 219 //----------------------------------------------------------------------------
 220 /* Implementation of AVL Tree */
 221
 222 /* Insert new _Node. */
 223 template< typename Node, typename Get_key, class Compare>
 224 Pair<Node *, bool>
 225 Avl_tree<Node, Get_key, Compare>::insert(Node *new_node)
 226 {
 227   typedef Avl_tree_node A;
 228   typedef Bits::Bst_node N;
 229   N **t = &_head; /* search variable */
 230   N **s = &_head; /* node where rebalancing may occur */
 231   Key_param_type new_key = Get_key::key_of(new_node);
 232
 233   // search insertion point
 234   for (N *p; (p = *t);)
 235     {
 236       Dir b = dir(new_key, p);
 237       if (b == Dir::N)
 238         return pair(static_cast<Node*>(p), false);
 239
 240       if (!static_cast<A const *>(p)->balanced())
 241         s = t;
 242
 243       t = N::next_p(p, b);
 244     }
 245
 246   *static_cast<A*>(new_node) = A(true);
 247   *t = new_node;
 248
 249   N *n = *s;
 250   A *a = static_cast<A*>(n);
 251   if (!a->balanced())
 252     {
 253       A::Bal b(greater(new_key, n));
 254       if (a->balance() != b)
 255         {
 256           // ok we got in balance the shorter subtree go higher
 257           a->balance(Bal::N);
 258           // propagate the new balance down to the new node
 259           n = N::next(n, b);
 260         }
 261       else if (b == Bal(greater(new_key, N::next(n, b))))
 262         {
 263           // left-left or right-right case -> single rotation
 264           A::rotate(s, b);
 265           a->balance(Bal::N);
 266           static_cast<A*>(*s)->balance(Bal::N);
 267           n = N::next(*s, b);
 268         }
 269       else
 270         {
 271           // need a double rotation
 272           n = N::next(N::next(n, b), !b);
 273           n = A::rotate2(s, b, n == new_node ? Bal::N : Bal(greater(new_key, n)));
 274         }
 275     }
 276
 277   for (A::Bal b; n && n != new_node; static_cast<A*>(n)->balance(b), n = N::next(n, b))
 278     b = Bal(greater(new_key, n));
 279
 280   return pair(new_node, true);
 281 }
 282
 283
 284 /* remove an element */
 285 template< typename Node, typename Get_key, class Compare>
 286 inline
 287 Node *Avl_tree<Node, Get_key, Compare>::remove(Key_param_type key)
 288 {
 289   typedef Avl_tree_node A;
 290   typedef Bits::Bst_node N;
 291   N **q = &_head; /* search variable */
 292   N **s = &_head; /* last ('deepest') node on the search path to q
 293                    * with balance 0, at this place the rebalancing
 294                    * stops in any case */
 295   N **t = 0;
 296   Dir dir;
 297
 298   // find target node and rebalancing entry
 299   for (N *n; (n = *q); q = N::next_p(n, dir))
 300     {
 301       dir = Dir(greater(key, n));
 302       if (dir == Dir::L && !greater(k(n), key))
 303         /* found node */
 304         t = q;
 305
 306       if (!N::next(n, dir))
 307         break;
 308
 309       A const *a = static_cast<A const *>(n);
 310       if (a->balanced() || (a->balance() == !dir && N::next<A>(n, !dir)->balanced()))
 311         s = q;
 312     }
 313
 314   // noting found
 315   if (!t)
 316     return 0;
 317
 318   A *i = static_cast<A*>(*t);
 319
 320   for (N *n; (n = *s); s = N::next_p(n, dir))
 321     {
 322       dir = Dir(greater(key, n));
 323
 324       if (!N::next(n, dir))
 325         break;
 326
 327       A *a = static_cast<A*>(n);
 328       // got one out of balance
 329       if (a->balanced())
 330         a->balance(!dir);
 331       else if (a->balance() == dir)
 332         a->balance(Bal::N);
 333       else
 334         {
 335           // we need rotations to get in balance
 336           Bal b = N::next<A>(n, !dir)->balance();
 337           if (b == dir)
 338             A::rotate2(s, !dir, N::next<A>(N::next(n, !dir), dir)->balance());
 339           else
 340             {
 341               A::rotate(s, !dir);
 342               if (b != Bal::N)
 343                 {
 344                   a->balance(Bal::N);
 345                   static_cast<A*>(*s)->balance(Bal::N);
 346                 }
 347               else
 348                 {
 349                   a->balance(!dir);
 350                   static_cast<A*>(*s)->balance(dir);
 351                 }
 352             }
 353           if (n == i)
 354             t = N::next_p(*s, dir);
 355         }
 356     }
 357
 358   A *n = static_cast<A*>(*q);
 359   *t = n;
 360   *q = N::next(n, !dir);
 361   *n = *i;
 362
 363   return static_cast<Node*>(i);
 364 }
 365
 366 #ifdef __DEBUG_L4_AVL
 367 template< typename Node, typename Get_key, class Compare>
 368 bool Avl_tree<Node, Get_key, Compare>::rec_dump(Avl_tree_node *n, int depth, int *dp, bool print, char pfx)
 369 {
 370   typedef Avl_tree_node A;
 371
 372   if (!n)
 373     return true;
 374
 375   int dpx[2] = {depth,depth};
 376   bool res = true;
 377
 378   res = rec_dump(n->next<A>(Dir::R), depth + 1, dpx + 1, print, '/');
 379
 380   if (print)
 381     {
 382       fprintf(stderr, "%2d: [%8p] b=%1d: ", depth, n, (int)n->balance().d);
 383
 384       for (int i = 0; i < depth; ++i)
 385         std::cerr << "    ";
 386
 387       std::cerr << pfx << (static_cast<Node*>(n)->item) << std::endl;
 388     }
 389
 390   res = res & rec_dump(n->next<A>(Dir::L), depth + 1, dpx, print, '\\');
 391
 392   int b = dpx[1] - dpx[0];
 393
 394   if (b < 0)
 395     *dp = dpx[0];
 396   else
 397     *dp = dpx[1];
 398
 399   Bal x = n->balance();
 400   if ((b < -1 || b > 1) ||
 401       (b == 0 && x != Bal::N) ||
 402       (b == -1 && x != Bal::L) ||
 403       (b == 1 && x != Bal::R))
 404     {
 405       if (print)
 406         fprintf(stderr, "%2d: [%8p] b=%1d: balance error %d\n", depth, n, (int)n->balance().d, b);
 407       return false;
 408     }
 409   return res;
 410 }
 411 #endif
 412
 413 }
 414