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