]>
Commit | Line | Data |
---|---|---|
cbe34bb5 | 1 | /* Copyright (C) 2009-2017 Free Software Foundation, Inc. |
0a35513e AH |
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 |