L4Re - L4 Runtime Environment
avl_tree
Go to the documentation of this file.
1 // vi:set ft=cpp: -*- Mode: C++ -*-
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