1 /* Copyright (C) 2009-2016 Free Software Foundation, Inc.
2 Contributed by Richard Henderson <rth@redhat.com>.
3
4 This file is part of the GNU Transactional Memory Library (libitm).
5
6 Libitm is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3 of the License, or
9 (at your option) any later version.
10
11 Libitm is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
13 FOR A PARTICULAR PURPOSE. See the GNU General Public License for
14 more details.
15
16 Under Section 7 of GPL version 3, you are granted additional
17 permissions described in the GCC Runtime Library Exception, version
18 3.1, as published by the Free Software Foundation.
19
20 You should have received a copy of the GNU General Public License and
21 a copy of the GCC Runtime Library Exception along with this program;
22 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 <http://www.gnu.org/licenses/>. */
24
25 // Implements an AA tree (http://en.wikipedia.org/wiki/AA_tree) with an
26 // integer key, and data attached to the node via flexible array member.
27
28 #include "libitm_i.h"
29
30 namespace GTM HIDDEN {
31
32 // The code for rebalancing the tree is greatly simplified by never
33 // having to check for null pointers. Instead, leaf node links point
34 // to this node, NIL, which points to itself.
35 const aa_node_base aa_node_base::s_nil(0);
36
37
38 // Remove left horizontal links. Swap the pointers of horizontal left links.
39
40 aa_node_base *
skew()41 aa_node_base::skew ()
42 {
43 aa_node_base *l = this->link(L);
44 if (this->m_level != 0 && l->m_level == this->m_level)
45 {
46 this->set_link(L, l->link(R));
47 l->set_link(R, this);
48 return l;
49 }
50 return this;
51 }
52
53
54 // Remove consecutive horizontal links. Take the middle node,
55 // elevate it, and return it.
56
57 aa_node_base *
split()58 aa_node_base::split ()
59 {
60 aa_node_base *r = this->link(R);
61 if (this->m_level != 0 && r->link(R)->m_level == this->m_level)
62 {
63 this->set_link(R, r->link(L));
64 r->set_link(L, this);
65 r->m_level += 1;
66 return r;
67 }
68 return this;
69 }
70
71 // Decrease the level of THIS to be one more than the level of its children.
72
73 void
decrease_level()74 aa_node_base::decrease_level ()
75 {
76 aa_node_base *l = this->link(L);
77 aa_node_base *r = this->link(R);
78 level_type llev = l->m_level;
79 level_type rlev = r->m_level;
80 level_type should_be = (llev < rlev ? llev : rlev) + 1;
81
82 if (should_be < this->m_level)
83 {
84 this->m_level = should_be;
85 if (should_be < rlev)
86 r->m_level = should_be;
87 }
88 }
89
90 // Find and return the node in the tree with key K.
91
92 template<typename KEY>
93 typename aa_tree_key<KEY>::node_ptr
find(KEY k) const94 aa_tree_key<KEY>::find(KEY k) const
95 {
96 node_ptr t = m_tree;
97 if (t != 0)
98 do
99 {
100 if (t->key == k)
101 return t;
102 t = t->link(k > t->key);
103 }
104 while (!t->is_nil());
105 return 0;
106 }
107
108 // Insert N into T and rebalance. Return the new balanced tree.
109
110 template<typename KEY>
111 typename aa_tree_key<KEY>::node_ptr
insert_1(node_ptr t,node_ptr n)112 aa_tree_key<KEY>::insert_1 (node_ptr t, node_ptr n)
113 {
114 bool dir = n->key > t->key;
115 node_ptr c = t->link(dir);
116
117 // Insert the node, recursively.
118 if (c->is_nil())
119 c = n;
120 else
121 c = insert_1 (c, n);
122 t->set_link(dir, c);
123
124 // Rebalance the tree, as needed.
125 t = t->skew();
126 t = t->split();
127
128 return t;
129 }
130
131 template<typename KEY>
132 void
insert(node_ptr n)133 aa_tree_key<KEY>::insert(node_ptr n)
134 {
135 if (m_tree == 0)
136 m_tree = n;
137 else
138 m_tree = insert_1 (m_tree, n);
139 }
140
141 // Delete K from T and rebalance. Return the new balanced tree.
142
143 template<typename KEY>
144 typename aa_tree_key<KEY>::node_ptr
erase_1(node_ptr t,KEY k,node_ptr * pfree)145 aa_tree_key<KEY>::erase_1 (node_ptr t, KEY k, node_ptr *pfree)
146 {
147 node_ptr r;
148 bool dir;
149
150 // If this is the node we're looking for, delete it. Else recurse.
151 if (k == t->key)
152 {
153 node_ptr l, sub, end;
154
155 l = t->link(node::L);
156 r = t->link(node::R);
157
158 if (pfree)
159 *pfree = t;
160
161 // If this is a leaf node, simply remove the node. Otherwise,
162 // we have to find either a predecessor or a successor node to
163 // replace this one.
164 if (l->is_nil())
165 {
166 if (r->is_nil())
167 return r;
168 sub = r, dir = node::L;
169 }
170 else
171 sub = l, dir = node::R;
172
173 // Find the successor or predecessor.
174 for (end = sub; !end->link(dir)->is_nil(); end = end->link(dir))
175 continue;
176
177 // Remove it (but don't free) from the subtree.
178 sub = erase_1 (sub, end->key, 0);
179
180 // Replace T with the successor we just extracted.
181 end->set_link(!dir, sub);
182 t = end;
183 }
184 else
185 {
186 dir = k > t->key;
187 t->set_link(dir, erase_1 (t->link(dir), k, pfree));
188 }
189
190 // Rebalance the tree.
191 t->decrease_level();
192 t = t->skew();
193 r = t->link(node::R)->skew();
194 t->set_link(node::R, r);
195 r->set_link(node::R, r->link(node::R)->skew());
196 t = t->split ();
197 t->set_link(node::R, t->link(node::R)->split());
198
199 return t;
200 }
201
202 template<typename KEY>
203 typename aa_tree_key<KEY>::node_ptr
erase(KEY k)204 aa_tree_key<KEY>::erase (KEY k)
205 {
206 node_ptr t = m_tree;
207 if (t == 0)
208 return 0;
209
210 node_ptr do_free = 0;
211 t = erase_1 (t, k, &do_free);
212 if (t->is_nil())
213 t = 0;
214 m_tree = t;
215 return do_free;
216 }
217
218 // Instantiate key classes.
219
220 template class aa_tree_key<uintptr_t>;
221
222 } // namespace GTM
223