update ChangeLogs for previous commit
[official-gcc.git] / libitm / aatree.cc
blob791b15410d5fd65c0e4556a2e93517ac4757e990
1 /* Copyright (C) 2009-2015 Free Software Foundation, Inc.
2 Contributed by Richard Henderson <rth@redhat.com>.
4 This file is part of the GNU Transactional Memory Library (libitm).
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.
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.
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.
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/>. */
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.
28 #include "libitm_i.h"
30 namespace GTM HIDDEN {
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);
38 // Remove left horizontal links. Swap the pointers of horizontal left links.
40 aa_node_base *
41 aa_node_base::skew ()
43 aa_node_base *l = this->link(L);
44 if (this->m_level != 0 && l->m_level == this->m_level)
46 this->set_link(L, l->link(R));
47 l->set_link(R, this);
48 return l;
50 return this;
54 // Remove consecutive horizontal links. Take the middle node,
55 // elevate it, and return it.
57 aa_node_base *
58 aa_node_base::split ()
60 aa_node_base *r = this->link(R);
61 if (this->m_level != 0 && r->link(R)->m_level == this->m_level)
63 this->set_link(R, r->link(L));
64 r->set_link(L, this);
65 r->m_level += 1;
66 return r;
68 return this;
71 // Decrease the level of THIS to be one more than the level of its children.
73 void
74 aa_node_base::decrease_level ()
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;
82 if (should_be < this->m_level)
84 this->m_level = should_be;
85 if (should_be < rlev)
86 r->m_level = should_be;
90 // Find and return the node in the tree with key K.
92 template<typename KEY>
93 typename aa_tree_key<KEY>::node_ptr
94 aa_tree_key<KEY>::find(KEY k) const
96 node_ptr t = m_tree;
97 if (t != 0)
100 if (t->key == k)
101 return t;
102 t = t->link(k > t->key);
104 while (!t->is_nil());
105 return 0;
108 // Insert N into T and rebalance. Return the new balanced tree.
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)
114 bool dir = n->key > t->key;
115 node_ptr c = t->link(dir);
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);
124 // Rebalance the tree, as needed.
125 t = t->skew();
126 t = t->split();
128 return t;
131 template<typename KEY>
132 void
133 aa_tree_key<KEY>::insert(node_ptr n)
135 if (m_tree == 0)
136 m_tree = n;
137 else
138 m_tree = insert_1 (m_tree, n);
141 // Delete K from T and rebalance. Return the new balanced tree.
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)
147 node_ptr r;
148 bool dir;
150 // If this is the node we're looking for, delete it. Else recurse.
151 if (k == t->key)
153 node_ptr l, sub, end;
155 l = t->link(node::L);
156 r = t->link(node::R);
158 if (pfree)
159 *pfree = t;
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())
166 if (r->is_nil())
167 return r;
168 sub = r, dir = node::L;
170 else
171 sub = l, dir = node::R;
173 // Find the successor or predecessor.
174 for (end = sub; !end->link(dir)->is_nil(); end = end->link(dir))
175 continue;
177 // Remove it (but don't free) from the subtree.
178 sub = erase_1 (sub, end->key, 0);
180 // Replace T with the successor we just extracted.
181 end->set_link(!dir, sub);
182 t = end;
184 else
186 dir = k > t->key;
187 t->set_link(dir, erase_1 (t->link(dir), k, pfree));
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());
199 return t;
202 template<typename KEY>
203 typename aa_tree_key<KEY>::node_ptr
204 aa_tree_key<KEY>::erase (KEY k)
206 node_ptr t = m_tree;
207 if (t == 0)
208 return 0;
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;
218 // Instantiate key classes.
220 template class aa_tree_key<uintptr_t>;
222 } // namespace GTM