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 <l4/cxx/std_ops>
  28 #include <l4/cxx/pair>
  29 #include <l4/cxx/type_traits>
  30
  31 namespace cxx {
  32
  33 /**
  34  * \internal
  35  * \ingroup cxx_api
  36  * \brief Generic iterator for the AVL-tree based set.
  37  * \param Cmp the type of the comparison functor.
  38  * \param Node the type of a node.
  39  * \param Node_op the type used to determine the direction of the iterator.
  40  */
  41 template< typename Node, typename Node_op >
  42 class __Avl_tree_iter_b
  43 {
  44 protected:
  45   Node const *_n;   ///< Current node
  46   Node const *_r;   ///< Root node of current subtree
  47
  48   /// Create an invalid iterator, used as end marker.
  49   __Avl_tree_iter_b() : _n(0), _r(0) {}
  50
  51   /**
  52    * \brief Create an iterator for the given AVL tree.
  53    * \param t the root node of the tree to iterate.
  54    * \param cmp the comparison functor for tree elements.
  55    */
  56   __Avl_tree_iter_b(Node const *t)
  57     : _n(t), _r(_n)
  58   { _downmost(); }
  59
  60   __Avl_tree_iter_b(Node const *t, Node const *r)
  61     : _n(t), _r(r)
  62   {}
  63
  64   /// traverse the subtree down to the leftmost/rightmost leave.
  65   inline void _downmost();
  66
  67   /// Increment to the next element.
  68   inline void inc();
  69
  70 public:
  71   /// Check two iterators for equality.
  72   bool operator == (__Avl_tree_iter_b const &o) const { return _n == o._n; }
  73   /// Check two iterators for non equality.
  74   bool operator != (__Avl_tree_iter_b const &o) const { return _n != o._n; }
  75 };
  76
  77 /**
  78  * \internal
  79  * \ingroup cxx_api
  80  * \brief Generic iterator for the AVL-tree based set.
  81  * \param Node the type of a node.
  82  * \param Node_type the type of the node to return stored in a node.
  83  * \param Node_op the type used to determine the direction of the iterator.
  84  */
  85 template< typename Node, typename Node_type, typename Node_op >
  86 class __Avl_tree_iter : public __Avl_tree_iter_b<Node, Node_op>
  87 {
  88 private:
  89   /// Super-class type
  90   typedef __Avl_tree_iter_b<Node, Node_op> Base;
  91
  92   using Base::_n;
  93   using Base::_r;
  94   using Base::inc;
  95
  96 public:
  97   /// Create an invalid iterator (end marker)
  98   __Avl_tree_iter() {}
  99
 100   /**
 101    * \brief Create an iterator for the given tree.
 102    * \param t the root node of the tree to iterate.
 103    * \param cmp the conmparison functor for tree elements.
 104    */
 105   __Avl_tree_iter(Node const *t) : Base(t) {}
 106   __Avl_tree_iter(Node const *t, Node const *r) : Base(t, r) {}
 107
 108 //  template<typename Key2>
 109   __Avl_tree_iter(Base const &o) : Base(o) {}
 110
 111   /**
 112    * \brief Dereference the iterator and get the item out of the tree.
 113    * \return A reference to the data stored in the AVL tree.
 114    */
 115   Node_type &operator * () const { return *const_cast<Node *>(_n); }
 116   /**
 117    * \brief Member access to the item the iterator points to.
 118    * \return A pointer to the item in the node.
 119    */
 120   Node_type *operator -> () const { return const_cast<Node *>(_n); }
 121   /**
 122    * \brief Set the iterator to the next element (pre increment).
 123    */
 124   __Avl_tree_iter &operator ++ () { inc(); return *this; }
 125   /**
 126    * \brief Set the iterator to the next element (post increment).
 127    */
 128   __Avl_tree_iter &operator ++ (int)
 129   { __Avl_tree_iter tmp = *this; inc(); return tmp; }
 130
 131 };
 132
 133 class Avl_tree_node
 134 {
 135 private:
 136   template< typename Node, typename Get_key, typename Compare, bool Const_nodes >
 137   friend class Avl_tree;
 138   struct Md
 139   {
 140     Avl_tree_node *left;
 141     Avl_tree_node *right;
 142     unsigned short flags;
 143     short balance;
 144     Md() : left(0), right(0), flags(0), balance(0) {}
 145   } _md;
 146
 147 protected:
 148   Avl_tree_node() : _md() {}
 149
 150   void operator = (Avl_tree_node const &)
 151   {}
 152
 153
 154 private:
 155   Avl_tree_node(Avl_tree_node const &o);
 156
 157   /// Adjust balance value
 158   inline void adj_balance(Avl_tree_node *b, Avl_tree_node *c, int v = -1);
 159   /// Replace the child \a c with \a repl.
 160   inline void replace_child(Avl_tree_node *c, Avl_tree_node *repl);
 161
 162   /// Right rotation of this node.
 163   void r_rotate(Avl_tree_node *r)
 164   { _md.left = r->_md.right; r->_md.right = this; }
 165
 166   /// Left rotation of this node.
 167   void l_rotate(Avl_tree_node *r)
 168   { _md.right = r->_md.left; r->_md.left = this; }
 169
 170   static void swap(Avl_tree_node *a, Avl_tree_node *b)
 171   { Md tmp = a->_md; a->_md = b->_md; b->_md = tmp; }
 172
 173 };
 174
 175 template< typename Node, typename Get_key,
 176           typename Compare = Lt_functor<typename Get_key::Key_type>,
 177           bool Const_nodes = true >
 178 class Avl_tree
 179 {
 180 public:
 181   enum
 182   {
 183     E_noent =  2,
 184     E_exist = 17,
 185     E_nomem = 12,
 186     E_inval = 22
 187   };
 188
 189 private:
 190   /// Current height of the tree.
 191   unsigned long _height;
 192   /// Head node of the tree, the root is \a _head.right.
 193   Avl_tree_node _head;
 194
 195   /// Ops for forward iterators
 196   struct Fwd
 197   {
 198     static Node *child1(Node const *n) { return N(n->_md.left); }
 199     static Node *child2(Node const *n) { return N(n->_md.right); }
 200     static bool cmp(Node const *l, Node const *r)
 201     { return Compare()(Get_key::key_of(l), Get_key::key_of(r)); }
 202   };
 203
 204   /// Ops for Reverse iterators
 205   struct Rev
 206   {
 207     static Node *child1(Node const *n) { return N(n->_md.right); }
 208     static Node *child2(Node const *n) { return N(n->_md.left); }
 209     static bool cmp(Node const *l, Node const *r)
 210     { return Compare()(Get_key::key_of(r), Get_key::key_of(l)); }
 211   };
 212
 213   Avl_tree(Avl_tree const &o);
 214
 215 public:
 216   typedef typename Get_key::Key_type Key_type;
 217   typedef typename Type_traits<Key_type>::Param_type Key_param_type;
 218
 219   typedef Rev Rev_iter_ops;
 220   typedef Fwd Fwd_iter_ops;
 221   /// Forward iterator for the set.
 222   typedef __Avl_tree_iter<Node, Node, Fwd> Iterator;
 223   typedef Iterator iterator;
 224   /// Constant forward iterator for the set.
 225   typedef __Avl_tree_iter<Node, Node const, Fwd> Const_iterator;
 226   typedef Const_iterator const_iterator;
 227   /// Backward iterator for the set.
 228   typedef __Avl_tree_iter<Node, Node, Rev> Rev_iterator;
 229   typedef Rev_iterator reverse_iterator;
 230   /// Constant backward iterator for the set.
 231   typedef __Avl_tree_iter<Node, Node const, Rev> Const_rev_iterator;
 232   typedef Const_rev_iterator const_reverse_iterator;
 233
 234   Avl_tree() : _height(0) {}
 235   cxx::Pair<Iterator, int> insert(Node *new_node);
 236
 237   /**
 238    * \brief Remove an item from the set.
 239    * \param key The item to remove.
 240    * \return 0 on success, -3 if the item does not exist, and
 241    *         -4 on internal error.
 242    */
 243   Node *remove(Key_param_type key);
 244   Node *erase(Key_param_type key) { return remove(key); }
 245
 246   /**
 247    * \brief Lookup a node equal to \a key.
 248    * \param key The value to search for.
 249    * \return A smart pointer to the element found, if no element found the
 250    *         pointer is NULL.
 251    */
 252   Node *find_node(Key_param_type key) const;
 253
 254   /// Destroy, and free the set.
 255   ~Avl_tree()
 256   {
 257     Avl_tree_node const *n;
 258     while ((n = _head._md.right))
 259       remove(Get_key::key_of(N(n)));
 260   }
 261
 262   /**
 263    * \brief Get the constant forward iterator for the first element in the set.
 264    * \return Constant forward iterator for the first element in the set.
 265    */
 266   Const_iterator begin() const { return Const_iterator(N(_head._md.right)); }
 267   /**
 268    * \brief Get the end marker for the constant forward iterator.
 269    * \return The end marker for the constant forward iterator.
 270    */
 271   Const_iterator end() const   { return Const_iterator(); }
 272
 273   /**
 274    * \brief Get the mutable forward iterator for the first element of the set.
 275    * \return The mutable forward iterator for the first element of the set.
 276    */
 277   Iterator begin() { return Iterator(N(_head._md.right)); }
 278   /**
 279    * \brief Get the end marker for the mutable forward iterator.
 280    * \return The end marker for mutable forward iterator.
 281    */
 282   Iterator end()   { return Iterator(); }
 283
 284   /**
 285    * \brief Get the constant backward iterator for the last element in the set.
 286    * \return The constant backward iterator for the last element in the set.
 287    */
 288   Const_rev_iterator rbegin() const { return Const_rev_iterator(N(_head._md.right)); }
 289   /**
 290    * \brief Get the end marker for the constant backward iterator.
 291    * \return The end marker for the constant backward iterator.
 292    */
 293   Const_rev_iterator rend() const   { return Const_rev_iterator(); }
 294
 295   /**
 296    * \brief Get the mutable backward iterator for the last element of the set.
 297    * \return The mutable backward iterator for the last element of the set.
 298    */
 299   Rev_iterator rbegin() { return Rev_iterator(N(_head._md.right)); }
 300   /**
 301    * \brief Get the end marker for the mutable backward iterator.
 302    * \return The end marker for mutable backward iterator.
 303    */
 304   Rev_iterator rend()   { return Rev_iterator(); }
 305
 306   Const_iterator find(Key_param_type key) const;
 307
 308 private:
 309   static Node *N(Avl_tree_node *n) { return static_cast<Node*>(n); }
 310   static Node const *N(Avl_tree_node const *n) { return static_cast<Node const *>(n); }
 311
 312 };
 313
 314
 315 //----------------------------------------------------------------------------
 316 /* IMPLEMENTATION: __Avl_tree_iter_b */
 317
 318 template< typename Node, typename Node_op>
 319 inline
 320 void __Avl_tree_iter_b<Node, Node_op>::_downmost()
 321 {
 322   while (_n)
 323     {
 324       if (Node_op::child1(_n))
 325         _n = Node_op::child1(_n);
 326       else
 327         return;
 328     }
 329 }
 330
 331 template< typename Node, typename Node_op>
 332 void __Avl_tree_iter_b<Node, Node_op>::inc()
 333 {
 334   if (!_n)
 335     return;
 336
 337   if (_n == _r)
 338     {
 339       _r = _n = Node_op::child2(_r);
 340       _downmost();
 341       return;
 342     }
 343
 344   if (Node_op::child2(_n))
 345     {
 346       _n = Node_op::child2(_n);
 347       _downmost();
 348       return;
 349     }
 350
 351   Node const *q = _r;
 352   Node const *p = _r;
 353   while (1)
 354     {
 355       if (Node_op::cmp(_n, q))
 356         {
 357           p = q;
 358           q = Node_op::child1(q);
 359         }
 360       else if (_n == q || Node_op::child2(q) == _n)
 361         {
 362           _n = p;
 363           return;
 364         }
 365       else
 366         q = Node_op::child2(q);
 367     }
 368 }
 369
 370
 371
 372
 373
 374 //----------------------------------------------------------------------------
 375 /* Implementation of Avl_tree_node */
 376 inline
 377 void Avl_tree_node::adj_balance(Avl_tree_node *b, Avl_tree_node *c, int v)
 378 {
 379   if (_md.balance == 0)
 380     {
 381       b->_md.balance = 0;
 382       c->_md.balance = 0;
 383     }
 384   else if (_md.balance == v)
 385     {
 386       b->_md.balance = 0;
 387       c->_md.balance = -v;
 388     }
 389   else
 390     {
 391       b->_md.balance = v;
 392       c->_md.balance = 0;
 393     }
 394   _md.balance = 0;
 395 }
 396
 397 /* Replace left or right child dependent on comparison. */
 398 inline
 399 void Avl_tree_node::replace_child(Avl_tree_node *c, Avl_tree_node *repl)
 400 {
 401   if (_md.right == c)
 402     _md.right = repl;
 403   else
 404     _md.left = repl;
 405 }
 406
 407
 408 //----------------------------------------------------------------------------
 409 /* Implementation of AVL Tree */
 410
 411 /* Insert new _Node. */
 412 template< typename Node, typename Get_key, class Compare, bool Const_nodes>
 413 cxx::Pair<typename Avl_tree<Node, Get_key, Compare, Const_nodes>::Iterator, int>
 414 Avl_tree<Node, Get_key, Compare, Const_nodes>::insert(Node *new_node)
 415 {
 416   if (!_head._md.right)
 417     {
 418       /* empty tree */
 419       _head._md.right = new_node;
 420       _height = 1;
 421     }
 422   else
 423     {
 424       /* non-empty tree */
 425       Avl_tree_node *p = _head._md.right; /* search variable */
 426       Avl_tree_node *q = 0;           /* new node */
 427       Avl_tree_node *r;               /* search variable (balancing) */
 428       Avl_tree_node *s = _head._md.right; /* node where rebalancing may occur */
 429       Avl_tree_node *t = &_head;      /* parent of s */
 430       Compare cmp;
 431       int a;                   /* which subtree of s has grown -1 left ... */
 432       while (p)
 433         {
 434           if (cmp(Get_key::key_of(new_node), Get_key::key_of(N(p))))
 435             {
 436               /* move left */
 437               q = p->_md.left;
 438               if (!q)
 439                 {
 440                   /* found insert position */
 441                   q = new_node;
 442                   p->_md.left = new_node;
 443                   break;
 444                 }
 445             }
 446           else if (cmp(Get_key::key_of(N(p)), Get_key::key_of(new_node)))
 447             {
 448               /* move right */
 449               q = p->_md.right;
 450               if (!q)
 451                 {
 452                   /* found insert position */
 453                   q = new_node;
 454                   p->_md.right = new_node;
 455                   break;
 456                 }
 457             }
 458           else
 459             /* item already exists */
 460             return cxx::pair(end(), -E_exist);
 461
 462           /* insert position not yet found, move on */
 463           if (q->_md.balance)
 464             {
 465               t = p;
 466               s = q;
 467             }
 468
 469           p = q;
 470         }
 471
 472       /* adj balanc factors */
 473       if (s != &_head && cmp(Get_key::key_of(new_node), Get_key::key_of(N(s))))
 474         {
 475           a = -1;
 476           r = p = s->_md.left;
 477         }
 478       else
 479         {
 480           a = +1;
 481           r = p = s->_md.right;
 482         }
 483
 484       /* adj balance factors down to the new node */
 485       while (p != q)
 486         {
 487           if (cmp(Get_key::key_of(new_node), Get_key::key_of(N(p))))
 488             {
 489               p->_md.balance = -1;
 490               p = p->_md.left;
 491             }
 492           else
 493             {
 494               p->_md.balance = +1;
 495               p = p->_md.right;
 496             }
 497         }
 498
 499       /* balancing */
 500       if (!s->_md.balance)
 501         {
 502           /* tree has grown higher */
 503           s->_md.balance = a;
 504           ++_height;
 505           return cxx::pair(Iterator(N(new_node), N(new_node)), 0);
 506         }
 507
 508       if (s->_md.balance == -a)
 509         {
 510           /* node s got balanced (shorter subtree of s has grown) */
 511           s->_md.balance = 0;
 512           return cxx::pair(Iterator(N(new_node), N(new_node)), 0);
 513         }
 514
 515       /* tree got out of balance */
 516       if (r->_md.balance == a)
 517         {
 518           /* single rotation */
 519           p = r;
 520           if (a == -1)
 521             s->r_rotate(r);
 522           else
 523             s->l_rotate(r);
 524
 525           /* set new balance factors */
 526           s->_md.balance = 0;
 527           r->_md.balance = 0;
 528         }
 529       else
 530         {
 531           /* double rotation */
 532           if (a == -1)
 533             {
 534               p = r->_md.right;
 535               r->l_rotate(p);
 536               s->r_rotate(p);
 537             }
 538           else
 539             {
 540               p = r->_md.left;
 541               r->r_rotate(p);
 542               s->l_rotate(p);
 543             }
 544
 545           /* set new balance factors */
 546           p->adj_balance(r, s, a);
 547         }
 548
 549       /* set new subtree head */
 550       if (s == t->_md.left)
 551         t->_md.left = p;
 552       else
 553         t->_md.right = p;
 554     }
 555
 556   return cxx::pair(Iterator(N(new_node), N(new_node)), 0);
 557 }
 558
 559 /* find an element */
 560 template< typename Node, typename Get_key, class Compare, bool Const_nodes>
 561 inline
 562 Node *Avl_tree<Node, Get_key, Compare, Const_nodes>::find_node(Key_param_type key) const
 563 {
 564   Avl_tree_node *q = _head._md.right;
 565   Compare cmp;
 566
 567   while (q)
 568     {
 569       if (cmp(key, Get_key::key_of(N(q))))
 570         q = q->_md.left;
 571       else if (cmp(Get_key::key_of(N(q)), key))
 572         q = q->_md.right;
 573       else
 574         return N(q);
 575     }
 576   return 0;
 577 }
 578
 579 /* find an element */
 580 template< typename Node, typename Get_key, class Compare, bool Const_nodes>
 581 inline
 582 typename Avl_tree<Node, Get_key, Compare, Const_nodes>::Const_iterator
 583 Avl_tree<Node, Get_key, Compare, Const_nodes>::find(Key_param_type key) const
 584 {
 585   Avl_tree_node *q = _head._md.right;
 586   Avl_tree_node *r = q;
 587   Compare cmp;
 588
 589   while (q)
 590     {
 591       if (cmp(key, Get_key::key_of(N(q))))
 592         q = q->_md.left;
 593       else if (cmp(Get_key::key_of(N(q)), key))
 594         {
 595           bool qr = (q == r);
 596           q = q->_md.right;
 597           if (qr)
 598             r = q;
 599         }
 600       else
 601         return Iterator(N(q), N(r));
 602     }
 603   return Iterator();
 604 }
 605
 606
 607 /* remove an element */
 608 template< typename Node, typename Get_key, class Compare, bool Const_nodes>
 609 inline
 610 Node *Avl_tree<Node, Get_key, Compare, Const_nodes>::remove(Key_param_type key)
 611 {
 612   Avl_tree_node *q = _head._md.right; /* search variable */
 613   Avl_tree_node *p = &_head;      /* parent node of q */
 614   Avl_tree_node *r;               /* 'symetric predecessor' of q, subtree to rotate
 615                             * while rebalancing */
 616   Avl_tree_node *s = &_head;      /* last ('deepest') node on the search path to q
 617                             * with balance 0, at this place the rebalancing
 618                             * stops in any case */
 619   Avl_tree_node *t = 0;           /* parent node of p */
 620
 621   Compare cmp;
 622   Node *removed = 0;
 623
 624   /***************************************************************************
 625    * search node with item == k, on the way down also search for the last
 626    * ('deepest') node with balance zero, this is the last node where
 627    * rebalancing might be necessary.
 628    ***************************************************************************/
 629   while (q)
 630     {
 631       if (!cmp(key, Get_key::key_of(N(q))) && !cmp(Get_key::key_of(N(q)), key))
 632         break; /* found */
 633
 634       if (!q->_md.balance)
 635         s = q;
 636
 637       t = p;
 638       p = q;
 639
 640       if (cmp(key, Get_key::key_of(N(p))))
 641         q = q->_md.left;
 642       else if (cmp(Get_key::key_of(N(p)), key))
 643         q = q->_md.right;
 644       else
 645         return 0;
 646     }
 647
 648   if (!q)
 649     return 0;
 650
 651   /***************************************************************************
 652    * remove node
 653    ***************************************************************************/
 654   if (q->_md.left && q->_md.right)
 655     {
 656       /* replace q with its 'symetric predecessor' (the node with the largest
 657        * item in the left subtree of q, its the rightmost item in this subtree) */
 658       if (!q->_md.balance)
 659         s = q;
 660
 661       Avl_tree_node *p2 = p;
 662       t = p;
 663       p = q;
 664       r = q->_md.left;
 665
 666       while (r->_md.right)
 667         {
 668           if (r->_md.balance == 0)
 669             s = r;
 670
 671           t = p;
 672           p = r;
 673           r = r->_md.right;
 674         }
 675
 676       /* found, replace q */
 677       if (Const_nodes)
 678         {
 679           Avl_tree_node::swap(q,r);
 680           p2->replace_child(q, r);
 681           if (s == q) s = r;
 682           if (p == q) p = r;
 683           if (t == q) t = r;
 684           p->replace_child(r, q);
 685         }
 686       else
 687         {
 688           *N(q) = *N(r);
 689           q = r;
 690         }
 691 #if 0
 692       if (!(t->_md.left == p || t->_md.right == p))
 693         enter_kdebug("dumb 1");
 694
 695       if (!(p->_md.left == q || p->_md.right == q))
 696         enter_kdebug("dumb 2");
 697 #endif
 698     }
 699
 700   if (q == _head._md.right)
 701     {
 702       /* remove tree head */
 703       if (!q->_md.left && !q->_md.right)
 704         {
 705           /* got empty tree */
 706           _head._md.right = 0;
 707           _height = 0;
 708         }
 709       else
 710         {
 711           if (q->_md.right)
 712             _head._md.right = q->_md.right;
 713           else
 714             _head._md.right = q->_md.left;
 715
 716           --_height;
 717         }
 718       removed = N(q);
 719     }
 720   else
 721     {
 722       /* q is not the tree head */
 723       int a;  /* changes of the balance factor, -1 right subtree got
 724                * shorter, +1 left subtree got shorter */
 725
 726       if (q == p->_md.right)
 727         {
 728           if (q->_md.left)
 729             p->_md.right = q->_md.left;
 730           else if (q->_md.right)
 731             p->_md.right = q->_md.right;
 732           else
 733             p->_md.right = 0;
 734
 735           /* right subtree of p got shorter */
 736           a = -1;
 737         }
 738       else
 739         {
 740           if (q->_md.left)
 741             p->_md.left = q->_md.left;
 742           else if (q->_md.right)
 743             p->_md.left = q->_md.right;
 744           else
 745             p->_md.left = 0;
 746
 747           /* left subtree of p got shorter */
 748           a = +1;
 749         }
 750       removed = N(q);
 751
 752       /***********************************************************************
 753        * Rebalancing
 754        * q is the removed node
 755        * p points to the node which must be rebalanced,
 756        * t points to the parent node of p
 757        * s points to the last node with balance 0 on the way down to p
 758        ***********************************************************************/
 759
 760       Avl_tree_node *o;          /* subtree while rebalancing */
 761       bool done = false;  /* done with rebalancing */
 762
 763       do
 764         {
 765           if (a == +1)
 766             {
 767               /***************************************************************
 768                * left subtree of p got shorter
 769                ***************************************************************/
 770               if (p->_md.balance == -1)
 771                 /* p got balanced => the whole tree with head p got shorter,
 772                  * must rebalance parent node of p (a.1.) */
 773                 p->_md.balance = 0;
 774               else if (p->_md.balance == 0)
 775                 {
 776                   /* p got out of balance, but kept its overall height
 777                    * => done (a.2.) */
 778                   p->_md.balance = +1;
 779                   done = true;
 780                 }
 781               else
 782                 {
 783                   /* left subtree of p was already shorter than right,
 784                    * need to rotate */
 785                   r = p->_md.right;
 786
 787                   if (!r->_md.balance)
 788                     {
 789                       /* single rotation left and done (a.3.1) */
 790                       p->l_rotate(r);
 791                       p->_md.balance = +1;
 792                       r->_md.balance = -1;
 793
 794                       t->replace_child(p, r);
 795
 796                       done = 1;
 797                     }
 798                   else if (r->_md.balance == +1)
 799                     {
 800                       /* single rotation left and rebalance parent node
 801                        * (a.3.2) */
 802                       p->l_rotate(r);
 803                       p->_md.balance = 0;
 804                       r->_md.balance = 0;
 805
 806                       t->replace_child(p, r);
 807
 808                       p = r;
 809                     }
 810                   else
 811                     {
 812                       /* double rotation right - left and rebalance parent
 813                        * node (a.3.3) */
 814                       o = r->_md.left;
 815                       r->r_rotate(o);
 816                       p->l_rotate(o);
 817                       t->replace_child(p, o);
 818                       o->adj_balance(p, r);
 819                       p = o;
 820                     }
 821                 }
 822
 823             }
 824           else /* a == -1 */
 825             {
 826               /***************************************************************
 827                * right subtree of p got shorter
 828                ***************************************************************/
 829               if (p->_md.balance == +1)
 830                 /* p got balanced,  => the whole tree with head p got
 831                  * shorter, must rebalance parent node of p (b.1.) */
 832                 p->_md.balance = 0;
 833               else if (p->_md.balance == 0)
 834                 {
 835                   /* p got out of balance, but kept its overall height
 836                    * => done (b.2.) */
 837                   p->_md.balance = -1;
 838                   done = true;
 839                 }
 840               else
 841                 {
 842                   /* the right subtree of p already was shorter than the left,
 843                    * need to rotate to rebuild the AVL tree */
 844                   r = p->_md.left;
 845
 846                   if (r->_md.balance == 0)
 847                     {
 848                       /* single rotation right and done (b.3.1) */
 849                       p->r_rotate(r);
 850                       r->_md.balance = +1;
 851                       p->_md.balance = -1;
 852
 853                       t->replace_child(p, r);
 854
 855                       done = true;
 856                     }
 857                   else if (r->_md.balance == -1)
 858                     {
 859                       /* single rotation right and rebalance parent
 860                        * node (b.3.2) */
 861                       p->r_rotate(r);
 862                       r->_md.balance = 0;
 863                       p->_md.balance = 0;
 864
 865                       t->replace_child(p, r);
 866                       p = r;
 867                     }
 868                   else
 869                     {
 870                       /* double rotation left - right and rebalance parent
 871                        * node (b.3.3) */
 872                       o = r->_md.right;
 873                       r->l_rotate(o);
 874                       p->r_rotate(o);
 875                       t->replace_child(p, o);
 876                       o->adj_balance(r, p);
 877                       p = o;
 878                     }
 879                 }
 880             }
 881
 882           if (!done)
 883             {
 884               /* need to rebalance parent node, go one level up in the tree.
 885                * Actually, we go down the tree until we find p and store its
 886                * parent and the parent of the parent. We start at the last
 887                * node with balance 0, because the rebalancing definitely
 888                * stops there.
 889                * Current situation:
 890                * t points to the node which must be rebalanced, p to the
 891                * subtree of t which got shorter */
 892               q = p;
 893               r = t;
 894               if (t == s)
 895                 {
 896                   if (s == &_head)
 897                     {
 898                       /* whole tree got shorter */
 899                       --_height;
 900                       done = true;
 901                     }
 902                   else
 903                     {
 904                       /* reached the last node which needs to be rebalanced */
 905                       p = s;
 906                       if (p->_md.left == q)
 907                         /* left subtree got shorter */
 908                         a = +1;
 909                       else if (p->_md.right == q)
 910                         /* right subtree got shorter */
 911                         a = -1;
 912                       else
 913                         return (Node*)-E_inval;
 914                     }
 915                 }
 916               else
 917                 {
 918                   /* search node q */
 919
 920                   t = p = s;
 921
 922                   if (s == &_head)
 923                     p = s->_md.right;
 924
 925                   while (p && (p != r))
 926                     {
 927                       t = p;
 928                       if (cmp(Get_key::key_of(N(q)), Get_key::key_of(N(p))))
 929                         p = p->_md.left;
 930                       else
 931                         p = p->_md.right;
 932                     }
 933 #if 0
 934                   if (!p) enter_kdebug("dd");
 935 #endif
 936                   if (p->_md.left == q)
 937                     /* left subtree got shorter */
 938                     a = +1;
 939                   else if (p->_md.right == q)
 940                     /* right subtree got shorter */
 941                     a = -1;
 942                   else
 943                     return (Node*)-E_inval;
 944                 }
 945             }
 946         }
 947       while (!done);
 948     }
 949
 950   /* done */
 951   return removed;
 952 }
 953
 954 }
 955