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