l4/pkg/l4re-core/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   /// Alias for Direction.
  47   typedef Bits::Direction Dir;
  48
  49   // We are a final 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 should 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  * \tparam Node    The data type of the nodes (must inherit from Avl_tree_node).
  94  * \tparam Get_key The meta function to get the key value from a node.
  95  *                 The implementation uses `Get_key::key_of(ptr_to_node)`. The
  96  *                 type of the key values must be defined in `Get_key::Key_type`.
  97  * \tparam Compare Binary relation to establish a total order for the
  98  *                 nodes of the tree. `Compare()(l, r)` must return true if
  99  *                 the key \a l is smaller than the key \a r.
 100  *
 101  * This implementation does not provide any memory management. It is the
 102  * responsibility of the caller to allocate nodes before inserting them and
 103  * to free them when they are removed or when the tree is destroyed.
 104  * Conversely, the caller must also ensure that nodes are removed
 105  * from the tree before they are destroyed.
 106  */
 107 template< typename Node, typename Get_key,
 108           typename Compare = Lt_functor<typename Get_key::Key_type> >
 109 class Avl_tree : public Bits::Bst<Node, Get_key, Compare>
 110 {
 111 private:
 112   typedef Bits::Bst<Node, Get_key, Compare> Bst;
 113
 114   /// Hide this from possible descendants.
 115   using Bst::_head;
 116
 117   /// Provide access to keys of nodes.
 118   using Bst::k;
 119
 120   /// Alias type for balance values.
 121   typedef typename Avl_tree_node::Bal Bal;
 122   /// Alias type for Direction values.
 123   typedef typename Avl_tree_node::Bal Dir;
 124
 125   /// Prohibit simple copy.
 126   Avl_tree(Avl_tree const &o);
 127
 128   /// Prohibit simple copy.
 129   void operator = (Avl_tree const &o);
 130
 131 public:
 132   //@{
 133   typedef typename Bst::Key_type Key_type;
 134   typedef typename Bst::Key_param_type Key_param_type;
 135   //@}
 136
 137   // Grab iterator types from Bst
 138   //@{
 139   /// Forward iterator for the tree.
 140   typedef typename Bst::Iterator Iterator;
 141   /// Constant forward iterator for the tree.
 142   typedef typename Bst::Const_iterator Const_iterator;
 143   /// Backward iterator for the tree.
 144   typedef typename Bst::Rev_iterator Rev_iterator;
 145   /// Constant backward iterator for the tree.
 146   typedef typename Bst::Const_rev_iterator Const_rev_iterator;
 147   //@}
 148
 149   /**
 150    * \brief Insert a new node into this AVL tree.
 151    * \param new_node A pointer to the new node.
 152    * \return A pair, with \a second set to `true` and \a first pointing to
 153    *         \a new_node, on success.  If there is already a node with the
 154    *         same key then \a first points to this node and \a second is 'false'.
 155    */
 156   Pair<Node *, bool> insert(Node *new_node);
 157
 158   /**
 159    * \brief Remove the node with \a key from the tree.
 160    * \param key The key to the node to remove.
 161    * \return The pointer to the removed node on success,
 162    *         or 0 if no node with the \a key exists.
 163    */
 164   Node *remove(Key_param_type key);
 165   /**
 166    * \brief An alias for remove().
 167    */
 168   Node *erase(Key_param_type key) { return remove(key); }
 169
 170   /// Create an empty AVL tree.
 171   Avl_tree() : Bst() {}
 172   /// Destroy the tree.
 173   ~Avl_tree() noexcept
 174   {
 175     this->remove_all([](Node *){});
 176   }
 177
 178 #ifdef __DEBUG_L4_AVL
 179   bool rec_dump(Avl_tree_node *n, int depth, int *dp, bool print, char pfx);
 180   bool rec_dump(bool print)
 181   {
 182     int dp=0;
 183     return rec_dump(static_cast<Avl_tree_node *>(_head), 0, &dp, print, '+');
 184   }
 185 #endif
 186 };
 187
 188
 189 //----------------------------------------------------------------------------
 190 /* IMPLEMENTATION: Bits::__Bst_iter_b */
 191
 192
 193 inline
 194 Bits::Bst_node *
 195 Avl_tree_node::rotate2(Bst_node **t, Bal idir, Bal pre)
 196 {
 197   typedef Bits::Bst_node N;
 198   typedef Avl_tree_node A;
 199   N *tmp[2] = { *t, N::next(*t, idir) };
 200   *t = N::next(tmp[1], !idir);
 201   A *n = static_cast<A*>(*t);
 202
 203   N::next(tmp[0], idir, N::next(n, !idir));
 204   N::next(tmp[1], !idir, N::next(n, idir));
 205   N::next(n, !idir, tmp[0]);
 206   N::next(n, idir, tmp[1]);
 207
 208   n->balance(Bal::N);
 209
 210   if (pre == Bal::N)
 211     {
 212       static_cast<A*>(tmp[0])->balance(Bal::N);
 213       static_cast<A*>(tmp[1])->balance(Bal::N);
 214       return 0;
 215     }
 216
 217   static_cast<A*>(tmp[pre != idir])->balance(!pre);
 218   static_cast<A*>(tmp[pre == idir])->balance(Bal::N);
 219
 220   return N::next(tmp[pre == idir], !pre);
 221 }
 222
 223 //----------------------------------------------------------------------------
 224 /* Implementation of AVL Tree */
 225
 226 /* Insert new _Node. */
 227 template< typename Node, typename Get_key, class Compare>
 228 Pair<Node *, bool>
 229 Avl_tree<Node, Get_key, Compare>::insert(Node *new_node)
 230 {
 231   typedef Avl_tree_node A;
 232   typedef Bits::Bst_node N;
 233   N **t = &_head; /* search variable */
 234   N **s = &_head; /* node where rebalancing may occur */
 235   Key_param_type new_key = Get_key::key_of(new_node);
 236
 237   // search insertion point
 238   for (N *p; (p = *t);)
 239     {
 240       Dir b = this->dir(new_key, p);
 241       if (b == Dir::N)
 242         return pair(static_cast<Node*>(p), false);
 243
 244       if (!static_cast<A const *>(p)->balanced())
 245         s = t;
 246
 247       t = N::next_p(p, b);
 248     }
 249
 250   *static_cast<A*>(new_node) = A(true);
 251   *t = new_node;
 252
 253   N *n = *s;
 254   A *a = static_cast<A*>(n);
 255   if (!a->balanced())
 256     {
 257       A::Bal b(this->greater(new_key, n));
 258       if (a->balance() != b)
 259         {
 260           // ok we got in balance the shorter subtree go higher
 261           a->balance(Bal::N);
 262           // propagate the new balance down to the new node
 263           n = N::next(n, b);
 264         }
 265       else if (b == Bal(this->greater(new_key, N::next(n, b))))
 266         {
 267           // left-left or right-right case -> single rotation
 268           A::rotate(s, b);
 269           a->balance(Bal::N);
 270           static_cast<A*>(*s)->balance(Bal::N);
 271           n = N::next(*s, b);
 272         }
 273       else
 274         {
 275           // need a double rotation
 276           n = N::next(N::next(n, b), !b);
 277           n = A::rotate2(s, b, n == new_node ? Bal::N : Bal(this->greater(new_key, n)));
 278         }
 279     }
 280
 281   for (A::Bal b; n && n != new_node; static_cast<A*>(n)->balance(b), n = N::next(n, b))
 282     b = Bal(this->greater(new_key, n));
 283
 284   return pair(new_node, true);
 285 }
 286
 287
 288 /* remove an element */
 289 template< typename Node, typename Get_key, class Compare>
 290 inline
 291 Node *Avl_tree<Node, Get_key, Compare>::remove(Key_param_type key)
 292 {
 293   typedef Avl_tree_node A;
 294   typedef Bits::Bst_node N;
 295   N **q = &_head; /* search variable */
 296   N **s = &_head; /* last ('deepest') node on the search path to q
 297                    * with balance 0, at this place the rebalancing
 298                    * stops in any case */
 299   N **t = 0;
 300   Dir dir;
 301
 302   // find target node and rebalancing entry
 303   for (N *n; (n = *q); q = N::next_p(n, dir))
 304     {
 305       dir = Dir(this->greater(key, n));
 306       if (dir == Dir::L && !this->greater(k(n), key))
 307         /* found node */
 308         t = q;
 309
 310       if (!N::next(n, dir))
 311         break;
 312
 313       A const *a = static_cast<A const *>(n);
 314       if (a->balanced() || (a->balance() == !dir && N::next<A>(n, !dir)->balanced()))
 315         s = q;
 316     }
 317
 318   // nothing found
 319   if (!t)
 320     return 0;
 321
 322   A *i = static_cast<A*>(*t);
 323
 324   for (N *n; (n = *s); s = N::next_p(n, dir))
 325     {
 326       dir = Dir(this->greater(key, n));
 327
 328       if (!N::next(n, dir))
 329         break;
 330
 331       A *a = static_cast<A*>(n);
 332       // got one out of balance
 333       if (a->balanced())
 334         a->balance(!dir);
 335       else if (a->balance() == dir)
 336         a->balance(Bal::N);
 337       else
 338         {
 339           // we need rotations to get in balance
 340           Bal b = N::next<A>(n, !dir)->balance();
 341           if (b == dir)
 342             A::rotate2(s, !dir, N::next<A>(N::next(n, !dir), dir)->balance());
 343           else
 344             {
 345               A::rotate(s, !dir);
 346               if (b != Bal::N)
 347                 {
 348                   a->balance(Bal::N);
 349                   static_cast<A*>(*s)->balance(Bal::N);
 350                 }
 351               else
 352                 {
 353                   a->balance(!dir);
 354                   static_cast<A*>(*s)->balance(dir);
 355                 }
 356             }
 357           if (n == i)
 358             t = N::next_p(*s, dir);
 359         }
 360     }
 361
 362   A *n = static_cast<A*>(*q);
 363   *t = n;
 364   *q = N::next(n, !dir);
 365   *n = *i;
 366
 367   return static_cast<Node*>(i);
 368 }
 369
 370 #ifdef __DEBUG_L4_AVL
 371 template< typename Node, typename Get_key, class Compare>
 372 bool Avl_tree<Node, Get_key, Compare>::rec_dump(Avl_tree_node *n, int depth, int *dp, bool print, char pfx)
 373 {
 374   typedef Avl_tree_node A;
 375
 376   if (!n)
 377     return true;
 378
 379   int dpx[2] = {depth,depth};
 380   bool res = true;
 381
 382   res = rec_dump(n->next<A>(Dir::R), depth + 1, dpx + 1, print, '/');
 383
 384   if (print)
 385     {
 386       fprintf(stderr, "%2d: [%8p] b=%1d: ", depth, n, (int)n->balance().d);
 387
 388       for (int i = 0; i < depth; ++i)
 389         std::cerr << "    ";
 390
 391       std::cerr << pfx << (static_cast<Node*>(n)->item) << std::endl;
 392     }
 393
 394   res = res & rec_dump(n->next<A>(Dir::L), depth + 1, dpx, print, '\\');
 395
 396   int b = dpx[1] - dpx[0];
 397
 398   if (b < 0)
 399     *dp = dpx[0];
 400   else
 401     *dp = dpx[1];
 402
 403   Bal x = n->balance();
 404   if ((b < -1 || b > 1) ||
 405       (b == 0 && x != Bal::N) ||
 406       (b == -1 && x != Bal::L) ||
 407       (b == 1 && x != Bal::R))
 408     {
 409       if (print)
 410         fprintf(stderr, "%2d: [%8p] b=%1d: balance error %d\n", depth, n, (int)n->balance().d, b);
 411       return false;
 412     }
 413   return res;
 414 }
 415 #endif
 416
 417 }
 418