1 /*
2 * \brief AVL tree
3 * \author Norman Feske
4 * \date 2006-04-12
5 */
6
7 /*
8 * Copyright (C) 2006-2013 Genode Labs GmbH
9 *
10 * This file is part of the Genode OS framework, which is distributed
11 * under the terms of the GNU General Public License version 2.
12 */
13
14 #ifndef _INCLUDE__UTIL__AVL_TREE_H_
15 #define _INCLUDE__UTIL__AVL_TREE_H_
16
17 #include <util/misc_math.h>
18
19 namespace Genode {
20
21 class Avl_node_base;
22 template <typename>class Avl_node;
23 template <typename>class Avl_tree;
24 }
25
26
27 class Genode::Avl_node_base
28 {
29 protected:
30
31 /**
32 * Internal policy interface
33 *
34 * The implementation of this interface is provided by the AVL tree.
35 */
36 struct Policy
37 {
38 virtual ~Policy() { }
39
40 /**
41 * Compare two nodes
42 *
43 * \retval false if n2 is lower than n1
44 * \retval true if n2 is higher than or equal to n1
45 *
46 * This method must be provided by the derived class.
47 * It determines the order of nodes inside the AVL tree.
48 */
49 virtual bool higher(Avl_node_base *n1, Avl_node_base *n2) const = 0
50
51 /**
52 * Node recomputation hook
53 *
54 * If a node gets rearranged, this method is called.
55 * It can be used to update AVL-tree-position dependent
56 * meta data.
57 */
58 virtual void recompute(Avl_node_base *) { }
59 }
60
61 Avl_node_base *_child[2]; /* left and right subtrees */
62 Avl_node_base *_parent; /* parent of subtree */
63 unsigned char _depth;/* depth of subtree */
64
65 public:
66
67 typedef bool Side;
68
69 enum { LEFT = false, RIGHT = true }
70
71 private:
72
73 /**
74 * Determine depth of subtree
75 */
76 inline int _child_depth(Side i) {
77 return _child[i] ? _child[i]->_depth : 0}
78
79 /**
80 * Update depth of node
81 */
82 void _recompute_depth(Policy &policy);
83
84 /**
85 * Determine left-right bias of both subtrees
86 */
87 inline Side _bias() {
88 return (_child_depth(RIGHT)> _child_depth(LEFT))}
89
90 /**
91 * Insert subtree into specified side of the node
92 */
93 void _adopt(Avl_node_base *node, Side i, Policy &policy);
94
95 /**
96 * Rotate subtree
97 *
98 * \param side direction of rotate operation
99 * \param node subtree to rotate
100 *
101 * The local node_* variable names describe node locations for
102 * the left (default) rotation. For example, node_r_l is the
103 * left of the right of node.
104 */
105 void _rotate_subtree(Avl_node_base *node, Side side, Policy &policy);
106
107 /**
108 * Rebalance subtree
109 *
110 * \param node immediate child that needs balancing
111 *
112 * `this` is parent of the subtree to rebalance
113 */
114 void _rebalance_subtree(Avl_node_base *node, Policy &policy);
115
116 public:
117
118 /**
119 * Constructor
120 */
121 Avl_node_base();
122
123 /**
124 * Insert new node into subtree
125 */
126 void insert(Avl_node_base *node, Policy &policy);
127
128 /**
129 * Remove node from tree
130 */
131 void remove(Policy &policy);
132 }
133
134
135 /**
136 * AVL node
137 *
138 * \param NT type of the class derived from `Avl_node`
139 *
140 * Each object to be stored in the AVL tree must be derived from `Avl_node`.
141 * The type of the derived class is to be specified as template argument to
142 * enable `Avl_node` to call virtual methods specific for the derived class.
143 *
144 * The NT class must implement a method called `higher` that takes a pointer to
145 * another NT object as argument and returns a bool value. The bool value is
146 * true if the specified node is higher or equal in the tree order.
147 */
148 template <typename NT>
149 struct Genode::Avl_node : Avl_node_base
150 {
151 /**
152 * Return child of specified side, or nullptr if there is no child
153 *
154 * This method can be called by the NT objects to traverse the tree.
155 */
156 inline NT *child(Side i) const { return static_cast<NT *>(_child[i])}
157
158 /**
159 * Default policy
160 *
161 * \noapi
162 */
163 void recompute() { }
164 }
165
166
167 /**
168 * Root node of the AVL tree
169 *
170 * The real nodes are always attached at the left branch of this root node.
171 */
172 template <typename NT>
173 class Genode::Avl_tree : Avl_node<NT>
174 {
175 private:
176
177 /**
178 * Auto-generated policy class specific for NT
179 */
180 class Policy : public Avl_node_base::Policy
181 {
182 bool higher(Avl_node_base *n1, Avl_node_base *n2) const
183 {
184 return static_cast<NT *>(n1)->higher(static_cast<NT *>(n2))
185 }
186
187 void recompute(Avl_node_base *node)
188 {
189 static_cast<NT *>(node)->recompute();
190 }
191
192 }
193
194 public:
195
196 /**
197 * Insert node into AVL tree
198 */
199 void insert(Avl_node<NT>*node) { Avl_node_base::insert(node, _policy);}
200
201 /**
202 * Remove node from AVL tree
203 */
204 void remove(Avl_node<NT>*node) { node->remove(_policy);}
205
206 /**
207 * Request first node of the tree
208 *
209 * \return first node, or nullptr if the tree is empty
210 */
211 inline NT *first() const { return this->child(Avl_node<NT>::LEFT)}
212 }
213
214 #endif /* _INCLUDE__UTIL__AVL_TREE_H_ */