]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
d652f226 | 3 | // Copyright (C) 2005, 2006, 2009, 2010 Free Software Foundation, Inc. |
4569a895 AT |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the terms | |
7 | // of the GNU General Public License as published by the Free Software | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
9 | // version. |
10 | ||
11 | // This library is distributed in the hope that it will be useful, but | |
12 | // WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
14 | // General Public License for more details. | |
15 | ||
748086b7 JJ |
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. | |
4569a895 | 19 | |
748086b7 JJ |
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/>. | |
4569a895 AT |
24 | |
25 | // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. | |
26 | ||
27 | // Permission to use, copy, modify, sell, and distribute this software | |
28 | // is hereby granted without fee, provided that the above copyright | |
29 | // notice appears in all copies, and that both that copyright notice | |
30 | // and this permission notice appear in supporting documentation. None | |
31 | // of the above authors, nor IBM Haifa Research Laboratories, make any | |
32 | // representation about the suitability of this software for any | |
33 | // purpose. It is provided "as is" without express or implied | |
34 | // warranty. | |
35 | ||
36 | /** | |
37 | * @file split_join_fn_imps.hpp | |
38 | * Contains an implementation for rb_tree_. | |
39 | */ | |
40 | ||
41 | PB_DS_CLASS_T_DEC | |
42 | inline void | |
43 | PB_DS_CLASS_C_DEC:: | |
44 | join(PB_DS_CLASS_C_DEC& other) | |
45 | { | |
47bea7b8 BK |
46 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
47 | _GLIBCXX_DEBUG_ONLY(other.assert_valid();) | |
1b24692f BK |
48 | _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();) |
49 | if (base_type::join_prep(other) == false) | |
47bea7b8 BK |
50 | { |
51 | _GLIBCXX_DEBUG_ONLY(assert_valid();) | |
52 | _GLIBCXX_DEBUG_ONLY(other.assert_valid();) | |
53 | return; | |
54 | } | |
4569a895 AT |
55 | |
56 | const node_pointer p_x = other.split_min(); | |
4569a895 | 57 | join_imp(p_x, other.m_p_head->m_p_parent); |
1b24692f | 58 | base_type::join_finish(other); |
47bea7b8 | 59 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
1b24692f | 60 | _GLIBCXX_DEBUG_ONLY(base_type::assert_valid();) |
47bea7b8 | 61 | _GLIBCXX_DEBUG_ONLY(other.assert_valid();) |
1b24692f | 62 | _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();) |
47bea7b8 | 63 | } |
4569a895 AT |
64 | |
65 | PB_DS_CLASS_T_DEC | |
66 | void | |
67 | PB_DS_CLASS_C_DEC:: | |
68 | join_imp(node_pointer p_x, node_pointer p_r) | |
69 | { | |
8fc81078 PC |
70 | _GLIBCXX_DEBUG_ASSERT(p_x != 0); |
71 | if (p_r != 0) | |
4569a895 AT |
72 | p_r->m_red = false; |
73 | ||
1b24692f | 74 | const size_type h = black_height(base_type::m_p_head->m_p_parent); |
4569a895 | 75 | const size_type other_h = black_height(p_r); |
4569a895 AT |
76 | node_pointer p_x_l; |
77 | node_pointer p_x_r; | |
4569a895 | 78 | std::pair<node_pointer, node_pointer> join_pos; |
4569a895 | 79 | const bool right_join = h >= other_h; |
4569a895 AT |
80 | if (right_join) |
81 | { | |
1b24692f | 82 | join_pos = find_join_pos_right(base_type::m_p_head->m_p_parent, |
47bea7b8 | 83 | h, other_h); |
4569a895 AT |
84 | p_x_l = join_pos.first; |
85 | p_x_r = p_r; | |
86 | } | |
87 | else | |
88 | { | |
1b24692f BK |
89 | p_x_l = base_type::m_p_head->m_p_parent; |
90 | base_type::m_p_head->m_p_parent = p_r; | |
8fc81078 | 91 | if (p_r != 0) |
1b24692f | 92 | p_r->m_p_parent = base_type::m_p_head; |
4569a895 | 93 | |
1b24692f | 94 | join_pos = find_join_pos_left(base_type::m_p_head->m_p_parent, |
47bea7b8 | 95 | h, other_h); |
4569a895 AT |
96 | p_x_r = join_pos.first; |
97 | } | |
98 | ||
99 | node_pointer p_parent = join_pos.second; | |
1b24692f | 100 | if (p_parent == base_type::m_p_head) |
4569a895 | 101 | { |
1b24692f BK |
102 | base_type::m_p_head->m_p_parent = p_x; |
103 | p_x->m_p_parent = base_type::m_p_head; | |
4569a895 AT |
104 | } |
105 | else | |
106 | { | |
107 | p_x->m_p_parent = p_parent; | |
4569a895 AT |
108 | if (right_join) |
109 | p_x->m_p_parent->m_p_right = p_x; | |
110 | else | |
111 | p_x->m_p_parent->m_p_left = p_x; | |
112 | } | |
113 | ||
114 | p_x->m_p_left = p_x_l; | |
8fc81078 | 115 | if (p_x_l != 0) |
4569a895 AT |
116 | p_x_l->m_p_parent = p_x; |
117 | ||
118 | p_x->m_p_right = p_x_r; | |
8fc81078 | 119 | if (p_x_r != 0) |
4569a895 AT |
120 | p_x_r->m_p_parent = p_x; |
121 | ||
122 | p_x->m_red = true; | |
123 | ||
1b24692f BK |
124 | base_type::initialize_min_max(); |
125 | _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();) | |
126 | base_type::update_to_top(p_x, (node_update* )this); | |
4569a895 | 127 | insert_fixup(p_x); |
1b24692f | 128 | _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid()); |
4569a895 AT |
129 | } |
130 | ||
131 | PB_DS_CLASS_T_DEC | |
132 | inline typename PB_DS_CLASS_C_DEC::node_pointer | |
133 | PB_DS_CLASS_C_DEC:: | |
134 | split_min() | |
135 | { | |
1b24692f | 136 | node_pointer p_min = base_type::m_p_head->m_p_left; |
4569a895 | 137 | |
47bea7b8 | 138 | #ifdef _GLIBCXX_DEBUG |
1b24692f | 139 | const node_pointer p_head = base_type::m_p_head; |
47bea7b8 BK |
140 | _GLIBCXX_DEBUG_ASSERT(p_min != p_head); |
141 | #endif | |
4569a895 AT |
142 | |
143 | remove_node(p_min); | |
1b24692f | 144 | return p_min; |
4569a895 AT |
145 | } |
146 | ||
147 | PB_DS_CLASS_T_DEC | |
148 | std::pair< | |
149 | typename PB_DS_CLASS_C_DEC::node_pointer, | |
150 | typename PB_DS_CLASS_C_DEC::node_pointer> | |
151 | PB_DS_CLASS_C_DEC:: | |
152 | find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r) | |
153 | { | |
47bea7b8 | 154 | _GLIBCXX_DEBUG_ASSERT(h_l >= h_r); |
4569a895 | 155 | |
8fc81078 PC |
156 | if (base_type::m_p_head->m_p_parent == 0) |
157 | return (std::make_pair((node_pointer)0, base_type::m_p_head)); | |
4569a895 | 158 | |
1b24692f | 159 | node_pointer p_l_parent = base_type::m_p_head; |
4569a895 AT |
160 | while (h_l > h_r) |
161 | { | |
162 | if (p_l->m_red == false) | |
163 | { | |
47bea7b8 | 164 | _GLIBCXX_DEBUG_ASSERT(h_l > 0); |
4569a895 AT |
165 | --h_l; |
166 | } | |
167 | ||
168 | p_l_parent = p_l; | |
4569a895 AT |
169 | p_l = p_l->m_p_right; |
170 | } | |
171 | ||
172 | if (!is_effectively_black(p_l)) | |
173 | { | |
174 | p_l_parent = p_l; | |
4569a895 AT |
175 | p_l = p_l->m_p_right; |
176 | } | |
177 | ||
47bea7b8 BK |
178 | _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_l)); |
179 | _GLIBCXX_DEBUG_ASSERT(black_height(p_l) == h_r); | |
8fc81078 | 180 | _GLIBCXX_DEBUG_ASSERT(p_l == 0 || p_l->m_p_parent == p_l_parent); |
47bea7b8 | 181 | return std::make_pair(p_l, p_l_parent); |
4569a895 AT |
182 | } |
183 | ||
184 | PB_DS_CLASS_T_DEC | |
185 | std::pair< | |
186 | typename PB_DS_CLASS_C_DEC::node_pointer, | |
187 | typename PB_DS_CLASS_C_DEC::node_pointer> | |
188 | PB_DS_CLASS_C_DEC:: | |
189 | find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r) | |
190 | { | |
47bea7b8 | 191 | _GLIBCXX_DEBUG_ASSERT(h_r > h_l); |
8fc81078 PC |
192 | if (base_type::m_p_head->m_p_parent == 0) |
193 | return (std::make_pair((node_pointer)0, | |
1b24692f BK |
194 | base_type::m_p_head)); |
195 | node_pointer p_r_parent = base_type::m_p_head; | |
4569a895 AT |
196 | while (h_r > h_l) |
197 | { | |
198 | if (p_r->m_red == false) | |
199 | { | |
47bea7b8 | 200 | _GLIBCXX_DEBUG_ASSERT(h_r > 0); |
4569a895 AT |
201 | --h_r; |
202 | } | |
203 | ||
204 | p_r_parent = p_r; | |
4569a895 AT |
205 | p_r = p_r->m_p_left; |
206 | } | |
207 | ||
208 | if (!is_effectively_black(p_r)) | |
209 | { | |
210 | p_r_parent = p_r; | |
4569a895 AT |
211 | p_r = p_r->m_p_left; |
212 | } | |
213 | ||
47bea7b8 BK |
214 | _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_r)); |
215 | _GLIBCXX_DEBUG_ASSERT(black_height(p_r) == h_l); | |
8fc81078 | 216 | _GLIBCXX_DEBUG_ASSERT(p_r == 0 || p_r->m_p_parent == p_r_parent); |
47bea7b8 | 217 | return std::make_pair(p_r, p_r_parent); |
4569a895 AT |
218 | } |
219 | ||
220 | PB_DS_CLASS_T_DEC | |
221 | inline typename PB_DS_CLASS_C_DEC::size_type | |
222 | PB_DS_CLASS_C_DEC:: | |
223 | black_height(node_pointer p_nd) | |
224 | { | |
225 | size_type h = 1; | |
8fc81078 | 226 | while (p_nd != 0) |
4569a895 AT |
227 | { |
228 | if (p_nd->m_red == false) | |
229 | ++h; | |
4569a895 AT |
230 | p_nd = p_nd->m_p_left; |
231 | } | |
47bea7b8 | 232 | return h; |
4569a895 AT |
233 | } |
234 | ||
235 | PB_DS_CLASS_T_DEC | |
236 | void | |
237 | PB_DS_CLASS_C_DEC:: | |
238 | split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other) | |
239 | { | |
47bea7b8 | 240 | _GLIBCXX_DEBUG_ONLY(assert_valid()); |
1b24692f | 241 | _GLIBCXX_DEBUG_ONLY(base_type::assert_valid();) |
4569a895 | 242 | |
47bea7b8 | 243 | _GLIBCXX_DEBUG_ONLY(other.assert_valid()); |
1b24692f | 244 | _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();) |
4569a895 | 245 | |
1b24692f | 246 | if (base_type::split_prep(r_key, other) == false) |
4569a895 | 247 | { |
47bea7b8 BK |
248 | _GLIBCXX_DEBUG_ONLY(assert_valid()); |
249 | _GLIBCXX_DEBUG_ONLY(other.assert_valid()); | |
4569a895 AT |
250 | return; |
251 | } | |
252 | ||
1b24692f BK |
253 | _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();) |
254 | _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid();) | |
47bea7b8 | 255 | node_pointer p_nd = upper_bound(r_key).m_p_nd; |
4569a895 AT |
256 | do |
257 | { | |
258 | node_pointer p_next_nd = p_nd->m_p_parent; | |
47bea7b8 | 259 | if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) |
4569a895 AT |
260 | split_at_node(p_nd, other); |
261 | ||
1b24692f BK |
262 | _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();) |
263 | _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid();) | |
47bea7b8 | 264 | p_nd = p_next_nd; |
4569a895 | 265 | } |
1b24692f | 266 | while (p_nd != base_type::m_p_head); |
4569a895 | 267 | |
1b24692f | 268 | base_type::split_finish(other); |
47bea7b8 BK |
269 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
270 | _GLIBCXX_DEBUG_ONLY(assert_valid();) | |
271 | } | |
4569a895 AT |
272 | |
273 | PB_DS_CLASS_T_DEC | |
274 | void | |
275 | PB_DS_CLASS_C_DEC:: | |
276 | split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other) | |
277 | { | |
8fc81078 | 278 | _GLIBCXX_DEBUG_ASSERT(p_nd != 0); |
4569a895 AT |
279 | |
280 | node_pointer p_l = p_nd->m_p_left; | |
281 | node_pointer p_r = p_nd->m_p_right; | |
4569a895 | 282 | node_pointer p_parent = p_nd->m_p_parent; |
1b24692f | 283 | if (p_parent == base_type::m_p_head) |
4569a895 | 284 | { |
1b24692f | 285 | base_type::m_p_head->m_p_parent = p_l; |
8fc81078 | 286 | if (p_l != 0) |
4569a895 | 287 | { |
1b24692f | 288 | p_l->m_p_parent = base_type::m_p_head; |
4569a895 AT |
289 | p_l->m_red = false; |
290 | } | |
291 | } | |
292 | else | |
293 | { | |
294 | if (p_parent->m_p_left == p_nd) | |
295 | p_parent->m_p_left = p_l; | |
296 | else | |
297 | p_parent->m_p_right = p_l; | |
298 | ||
8fc81078 | 299 | if (p_l != 0) |
4569a895 AT |
300 | p_l->m_p_parent = p_parent; |
301 | ||
302 | update_to_top(p_parent, (node_update* )this); | |
303 | ||
304 | if (!p_nd->m_red) | |
305 | remove_fixup(p_l, p_parent); | |
306 | } | |
307 | ||
1b24692f | 308 | base_type::initialize_min_max(); |
4569a895 | 309 | other.join_imp(p_nd, p_r); |
1b24692f BK |
310 | _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid()); |
311 | _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid()); | |
4569a895 AT |
312 | } |
313 |