Mercurial > hg > CbC > CbC_gcc
comparison libitm/aatree.cc @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
1 /* Copyright (C) 2009-2017 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 * | |
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 |