|
145
|
1 /* Copyright (C) 2009-2020 Free Software Foundation, Inc.
|
|
111
|
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 *
|
|
|
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 *
|
|
|
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
|
|
|
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
|
|
|
94 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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
