L4Re Operating System Framework
Interface and Usage Documentation
Loading...
Searching...
No Matches
avl_tree
Go to the documentation of this file.
1// vi:set ft=cpp: -*- Mode: C++ -*-
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
33struct Avl_set_tester;
34
35namespace cxx {
36
41{
42 friend struct ::Avl_set_tester;
43
44private:
45 template< typename Node, typename Get_key, typename Compare >
46 friend class Avl_tree;
47
49 typedef Bits::Direction Bal;
51 typedef Bits::Direction Dir;
52
53 // We are a final BST node, hide interior.
61 Bal _balance;
62
63protected:
65 Avl_tree_node() = default;
66
67private:
68 Avl_tree_node(Avl_tree_node const &o) = delete;
69 Avl_tree_node(Avl_tree_node &&o) = delete;
70
72 Avl_tree_node &operator = (Avl_tree_node const &o) = default;
74 Avl_tree_node &operator = (Avl_tree_node &&o) = default;
75
77 explicit Avl_tree_node(bool) : Bits::Bst_node(true), _balance(Dir::N) {}
78
80 static Bits::Bst_node *rotate2(Bst_node **t, Bal idir, Bal pre);
81
83 bool balanced() const { return _balance == Bal::N; }
84
86 Bal balance() const { return _balance; }
87
89 void balance(Bal b) { _balance = b; }
90};
91
92
109template< typename Node, typename Get_key,
110 typename Compare = Lt_functor<typename Get_key::Key_type> >
111class Avl_tree : public Bits::Bst<Node, Get_key, Compare>
112{
113private:
115
117 using Bst::_head;
118
120 using Bst::k;
121
123 typedef typename Avl_tree_node::Bal Bal;
125 typedef typename Avl_tree_node::Bal Dir;
126
127 Avl_tree(Avl_tree const &o) = delete;
128 Avl_tree &operator = (Avl_tree const &o) = delete;
129 Avl_tree(Avl_tree &&o) = delete;
130 Avl_tree &operator = (Avl_tree &&o) = delete;
131
132public:
134 typedef typename Bst::Key_type Key_type;
135 typedef typename Bst::Key_param_type Key_param_type;
137
138 // Grab iterator types from Bst
141 typedef typename Bst::Iterator Iterator;
149
157 Pair<Node *, bool> insert(Node *new_node);
158
165 Node *remove(Key_param_type key);
169 Node *erase(Key_param_type key) { return remove(key); }
170
172 Avl_tree() = default;
173
175 ~Avl_tree() noexcept
176 {
177 this->remove_all([](Node *){});
178 }
179
180#ifdef __DEBUG_L4_AVL
181 bool rec_dump(Avl_tree_node *n, int depth, int *dp, bool print, char pfx);
182 bool rec_dump(bool print)
183 {
184 int dp=0;
185 return rec_dump(static_cast<Avl_tree_node *>(_head), 0, &dp, print, '+');
186 }
187#endif
188};
189
190
191//----------------------------------------------------------------------------
192/* IMPLEMENTATION: Bits::__Bst_iter_b */
193
194
195inline
196Bits::Bst_node *
197Avl_tree_node::rotate2(Bst_node **t, Bal idir, Bal pre)
198{
199 typedef Bits::Bst_node N;
200 typedef Avl_tree_node A;
201 N *tmp[2] = { *t, N::next(*t, idir) };
202 *t = N::next(tmp[1], !idir);
203 A *n = static_cast<A*>(*t);
204
205 N::next(tmp[0], idir, N::next(n, !idir));
206 N::next(tmp[1], !idir, N::next(n, idir));
207 N::next(n, !idir, tmp[0]);
208 N::next(n, idir, tmp[1]);
209
210 n->balance(Bal::N);
211
212 if (pre == Bal::N)
213 {
214 static_cast<A*>(tmp[0])->balance(Bal::N);
215 static_cast<A*>(tmp[1])->balance(Bal::N);
216 return 0;
217 }
218
219 static_cast<A*>(tmp[pre != idir])->balance(!pre);
220 static_cast<A*>(tmp[pre == idir])->balance(Bal::N);
221
222 return N::next(tmp[pre == idir], !pre);
223}
224
225//----------------------------------------------------------------------------
226/* Implementation of AVL Tree */
227
228/* Insert new _Node. */
229template< typename Node, typename Get_key, class Compare>
230Pair<Node *, bool>
232{
233 typedef Avl_tree_node A;
234 typedef Bits::Bst_node N;
235 N **t = &_head; /* search variable */
236 N **s = &_head; /* node where rebalancing may occur */
237 Key_param_type new_key = Get_key::key_of(new_node);
238
239 // search insertion point
240 for (N *p; (p = *t);)
241 {
242 Dir b = this->dir(new_key, p);
243 if (b == Dir::N)
244 return pair(static_cast<Node*>(p), false);
245
246 if (!static_cast<A const *>(p)->balanced())
247 s = t;
248
249 t = A::next_p(p, b);
250 }
251
252 *static_cast<A*>(new_node) = A(true);
253 *t = new_node;
254
255 N *n = *s;
256 A *a = static_cast<A*>(n);
257 if (!a->balanced())
258 {
259 A::Bal b(this->greater(new_key, n));
260 if (a->balance() != b)
261 {
262 // ok we got in balance the shorter subtree go higher
263 a->balance(Bal::N);
264 // propagate the new balance down to the new node
265 n = A::next(n, b);
266 }
267 else if (b == Bal(this->greater(new_key, A::next(n, b))))
268 {
269 // left-left or right-right case -> single rotation
270 A::rotate(s, b);
271 a->balance(Bal::N);
272 static_cast<A*>(*s)->balance(Bal::N);
273 n = A::next(*s, b);
274 }
275 else
276 {
277 // need a double rotation
278 n = A::next(A::next(n, b), !b);
279 n = A::rotate2(s, b, n == new_node ? Bal::N : Bal(this->greater(new_key, n)));
280 }
281 }
282
283 for (A::Bal b; n && n != new_node; static_cast<A*>(n)->balance(b), n = A::next(n, b))
284 b = Bal(this->greater(new_key, n));
285
286 return pair(new_node, true);
287}
288
289
290/* remove an element */
291template< typename Node, typename Get_key, class Compare>
292inline
294{
295 typedef Avl_tree_node A;
296 typedef Bits::Bst_node N;
297 N **q = &_head; /* search variable */
298 N **s = &_head; /* last ('deepest') node on the search path to q
299 * with balance 0, at this place the rebalancing
300 * stops in any case */
301 N **t = 0;
302 Dir dir;
303
304 // find target node and rebalancing entry
305 for (N *n; (n = *q); q = A::next_p(n, dir))
306 {
307 dir = Dir(this->greater(key, n));
308 if (dir == Dir::L && !this->greater(k(n), key))
309 /* found node */
310 t = q;
311
312 if (!A::next(n, dir))
313 break;
314
315 A const *a = static_cast<A const *>(n);
316 if (a->balanced() || (a->balance() == !dir && A::next<A>(n, !dir)->balanced()))
317 s = q;
318 }
319
320 // nothing found
321 if (!t)
322 return 0;
323
324 A *i = static_cast<A*>(*t);
325
326 for (N *n; (n = *s); s = A::next_p(n, dir))
327 {
328 dir = Dir(this->greater(key, n));
329
330 if (!A::next(n, dir))
331 break;
332
333 A *a = static_cast<A*>(n);
334 // got one out of balance
335 if (a->balanced())
336 a->balance(!dir);
337 else if (a->balance() == dir)
338 a->balance(Bal::N);
339 else
340 {
341 // we need rotations to get in balance
342 Bal b = A::next<A>(n, !dir)->balance();
343 if (b == dir)
344 A::rotate2(s, !dir, A::next<A>(A::next(n, !dir), dir)->balance());
345 else
346 {
347 A::rotate(s, !dir);
348 if (b != Bal::N)
349 {
350 a->balance(Bal::N);
351 static_cast<A*>(*s)->balance(Bal::N);
352 }
353 else
354 {
355 a->balance(!dir);
356 static_cast<A*>(*s)->balance(dir);
357 }
358 }
359 if (n == i)
360 t = A::next_p(*s, dir);
361 }
362 }
363
364 A *n = static_cast<A*>(*q);
365 *t = n;
366 *q = A::next(n, !dir);
367 *n = *i;
368
369 return static_cast<Node*>(i);
370}
371
372#ifdef __DEBUG_L4_AVL
373template< typename Node, typename Get_key, class Compare>
374bool Avl_tree<Node, Get_key, Compare>::rec_dump(Avl_tree_node *n, int depth, int *dp, bool print, char pfx)
375{
376 typedef Avl_tree_node A;
377
378 if (!n)
379 return true;
380
381 int dpx[2] = {depth,depth};
382 bool res = true;
383
384 res = rec_dump(A::next<A>(n, Dir::R), depth + 1, dpx + 1, print, '/');
385
386 if (print)
387 {
388 fprintf(stderr, "%2d: [%8p] b=%1d: ", depth, n, (int)n->balance().d);
389
390 for (int i = 0; i < depth; ++i)
391 std::cerr << " ";
392
393 std::cerr << pfx << (static_cast<Node*>(n)->item) << std::endl;
394 }
395
396 res = res & rec_dump(A::next<A>(n, Dir::L), depth + 1, dpx, print, '\\');
397
398 int b = dpx[1] - dpx[0];
399
400 if (b < 0)
401 *dp = dpx[0];
402 else
403 *dp = dpx[1];
404
405 Bal x = n->balance();
406 if ((b < -1 || b > 1) ||
407 (b == 0 && x != Bal::N) ||
408 (b == -1 && x != Bal::L) ||
409 (b == 1 && x != Bal::R))
410 {
411 if (print)
412 fprintf(stderr, "%2d: [%8p] b=%1d: balance error %d\n", depth, n, (int)n->balance().d, b);
413 return false;
414 }
415 return res;
416}
417#endif
418
419}
420
AVL tree.
AVL tree.
Node of an AVL tree.
Definition avl_tree:41
Avl_tree_node()=default
Create an uninitialized node, this is what you should do.
A generic AVL tree.
Definition avl_tree:112
Pair< Node *, bool > insert(Node *new_node)
Insert a new node into this AVL tree.
Definition avl_tree:231
Node * erase(Key_param_type key)
An alias for remove().
Definition avl_tree:169
Node * remove(Key_param_type key)
Remove the node with key from the tree.
Definition avl_tree:293
~Avl_tree() noexcept
Destroy the tree.
Definition avl_tree:175
Avl_tree()=default
Create an empty AVL tree.
Bst::Const_iterator Const_iterator
Constant forward iterator for the tree.
Definition avl_tree:143
Bst::Rev_iterator Rev_iterator
Backward iterator for the tree.
Definition avl_tree:145
Bst::Iterator Iterator
Definition avl_tree:141
Bst::Const_rev_iterator Const_rev_iterator
Constant backward iterator for the tree.
Definition avl_tree:147
Basic type of a node in a binary search tree (BST).
Definition bst_base.h:82
static Bst_node ** next_p(Bst_node *p, Direction d)
Get pointer to link in direction d.
Definition bst_base.h:106
static void rotate(Bst_node **t, Direction idir)
Rotate subtree t in the opposite direction of idir.
Definition bst_base.h:131
Bst_node()
Create uninitialized node.
Definition bst_base.h:123
static Bst_node * next(Bst_node const *p, Direction d)
Get next node in direction d.
Definition bst_base.h:98
Basic binary search tree (BST).
Definition bst.h:43
__Bst_iter< Node, Node const, Rev > Const_rev_iterator
Constant backward.
Definition bst.h:88
Get_key::Key_type Key_type
The type of key values used to generate the total order of the elements.
Definition bst.h:70
__Bst_iter< Node, Node, Fwd > Iterator
Forward iterator.
Definition bst.h:82
Type_traits< Key_type >::Param_type Key_param_type
The type for key parameters.
Definition bst.h:72
Bst_node * _head
The head pointer of the tree.
Definition bst.h:102
__Bst_iter< Node, Node const, Fwd > Const_iterator
Constant forward iterator.
Definition bst.h:84
void remove_all(FUNC &&callback)
Clear the tree.
Definition bst.h:262
static Key_type k(Bst_node const *n)
Get the key value of n.
Definition bst.h:111
__Bst_iter< Node, Node, Rev > Rev_iterator
Backward iterator.
Definition bst.h:86
Our C++ library.
Definition arith:22
Pair implementation.
The direction to go in a binary search tree.
Definition bst_base.h:40
Pair of two values.
Definition pair:39