]>
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 | { | |
52 | PB_DS_DBG_ONLY(assert_valid();) | |
53 | ||
54 | PB_DS_DBG_ONLY(other.assert_valid();) | |
55 | PB_DS_DBG_ONLY(other.PB_DS_BASE_C_DEC::assert_valid();) | |
56 | ||
57 | if (PB_DS_BASE_C_DEC::join_prep(other) == false) | |
58 | { | |
59 | PB_DS_DBG_ONLY(assert_valid();) | |
60 | PB_DS_DBG_ONLY(other.assert_valid();) | |
61 | ||
62 | return; | |
63 | } | |
64 | ||
65 | const node_pointer p_x = other.split_min(); | |
66 | ||
67 | join_imp(p_x, other.m_p_head->m_p_parent); | |
68 | ||
69 | PB_DS_BASE_C_DEC::join_finish(other); | |
70 | ||
71 | PB_DS_DBG_ONLY(assert_valid();) | |
72 | PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::assert_valid();) | |
73 | ||
74 | PB_DS_DBG_ONLY(other.assert_valid();) | |
75 | PB_DS_DBG_ONLY(other.PB_DS_BASE_C_DEC::assert_valid();) | |
76 | } | |
77 | ||
78 | PB_DS_CLASS_T_DEC | |
79 | void | |
80 | PB_DS_CLASS_C_DEC:: | |
81 | join_imp(node_pointer p_x, node_pointer p_r) | |
82 | { | |
83 | PB_DS_DBG_ASSERT(p_x != NULL); | |
84 | ||
85 | if (p_r != NULL) | |
86 | p_r->m_red = false; | |
87 | ||
88 | const size_type h = | |
89 | black_height(PB_DS_BASE_C_DEC::m_p_head->m_p_parent); | |
90 | const size_type other_h = black_height(p_r); | |
91 | ||
92 | node_pointer p_x_l; | |
93 | node_pointer p_x_r; | |
94 | ||
95 | std::pair<node_pointer, node_pointer> join_pos; | |
96 | ||
97 | const bool right_join = h >= other_h; | |
98 | ||
99 | if (right_join) | |
100 | { | |
101 | join_pos = find_join_pos_right( PB_DS_BASE_C_DEC::m_p_head->m_p_parent, h, other_h); | |
102 | ||
103 | p_x_l = join_pos.first; | |
104 | p_x_r = p_r; | |
105 | } | |
106 | else | |
107 | { | |
108 | p_x_l = PB_DS_BASE_C_DEC::m_p_head->m_p_parent; | |
109 | ||
110 | PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_r; | |
111 | if (p_r != NULL) | |
112 | p_r->m_p_parent = PB_DS_BASE_C_DEC::m_p_head; | |
113 | ||
114 | join_pos = find_join_pos_left( PB_DS_BASE_C_DEC::m_p_head->m_p_parent, h, other_h); | |
115 | ||
116 | p_x_r = join_pos.first; | |
117 | } | |
118 | ||
119 | node_pointer p_parent = join_pos.second; | |
120 | ||
121 | if (p_parent == PB_DS_BASE_C_DEC::m_p_head) | |
122 | { | |
123 | PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_x; | |
124 | ||
125 | p_x->m_p_parent = PB_DS_BASE_C_DEC::m_p_head; | |
126 | } | |
127 | else | |
128 | { | |
129 | p_x->m_p_parent = p_parent; | |
130 | ||
131 | if (right_join) | |
132 | p_x->m_p_parent->m_p_right = p_x; | |
133 | else | |
134 | p_x->m_p_parent->m_p_left = p_x; | |
135 | } | |
136 | ||
137 | p_x->m_p_left = p_x_l; | |
138 | if (p_x_l != NULL) | |
139 | p_x_l->m_p_parent = p_x; | |
140 | ||
141 | p_x->m_p_right = p_x_r; | |
142 | if (p_x_r != NULL) | |
143 | p_x_r->m_p_parent = p_x; | |
144 | ||
145 | p_x->m_red = true; | |
146 | ||
147 | PB_DS_BASE_C_DEC::initialize_min_max(); | |
148 | ||
149 | PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid();) | |
150 | ||
151 | PB_DS_BASE_C_DEC::update_to_top(p_x, (node_update* )this); | |
152 | ||
153 | insert_fixup(p_x); | |
154 | ||
155 | PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid()); | |
156 | } | |
157 | ||
158 | PB_DS_CLASS_T_DEC | |
159 | inline typename PB_DS_CLASS_C_DEC::node_pointer | |
160 | PB_DS_CLASS_C_DEC:: | |
161 | split_min() | |
162 | { | |
163 | node_pointer p_min = PB_DS_BASE_C_DEC::m_p_head->m_p_left; | |
164 | ||
165 | #ifdef PB_DS_RB_TREE_DEBUG_ | |
166 | const node_pointer p_head = PB_DS_BASE_C_DEC::m_p_head; | |
167 | ||
168 | PB_DS_DBG_ASSERT(p_min != p_head); | |
169 | #endif // #ifdef PB_DS_RB_TREE_DEBUG_ | |
170 | ||
171 | remove_node(p_min); | |
172 | ||
173 | return (p_min); | |
174 | } | |
175 | ||
176 | PB_DS_CLASS_T_DEC | |
177 | std::pair< | |
178 | typename PB_DS_CLASS_C_DEC::node_pointer, | |
179 | typename PB_DS_CLASS_C_DEC::node_pointer> | |
180 | PB_DS_CLASS_C_DEC:: | |
181 | find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r) | |
182 | { | |
183 | PB_DS_DBG_ASSERT(h_l >= h_r); | |
184 | ||
185 | if (PB_DS_BASE_C_DEC::m_p_head->m_p_parent == NULL) | |
186 | return (std::make_pair((node_pointer)NULL, | |
187 | PB_DS_BASE_C_DEC::m_p_head)); | |
188 | ||
189 | node_pointer p_l_parent = PB_DS_BASE_C_DEC::m_p_head; | |
190 | ||
191 | while (h_l > h_r) | |
192 | { | |
193 | if (p_l->m_red == false) | |
194 | { | |
195 | PB_DS_DBG_ASSERT(h_l > 0); | |
196 | ||
197 | --h_l; | |
198 | } | |
199 | ||
200 | p_l_parent = p_l; | |
201 | ||
202 | p_l = p_l->m_p_right; | |
203 | } | |
204 | ||
205 | if (!is_effectively_black(p_l)) | |
206 | { | |
207 | p_l_parent = p_l; | |
208 | ||
209 | p_l = p_l->m_p_right; | |
210 | } | |
211 | ||
212 | PB_DS_DBG_ASSERT(is_effectively_black(p_l)); | |
213 | PB_DS_DBG_ASSERT(black_height(p_l) == h_r); | |
214 | PB_DS_DBG_ASSERT(p_l == NULL || p_l->m_p_parent == p_l_parent); | |
215 | ||
216 | return (std::make_pair(p_l, p_l_parent)); | |
217 | } | |
218 | ||
219 | PB_DS_CLASS_T_DEC | |
220 | std::pair< | |
221 | typename PB_DS_CLASS_C_DEC::node_pointer, | |
222 | typename PB_DS_CLASS_C_DEC::node_pointer> | |
223 | PB_DS_CLASS_C_DEC:: | |
224 | find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r) | |
225 | { | |
226 | PB_DS_DBG_ASSERT(h_r > h_l); | |
227 | ||
228 | if (PB_DS_BASE_C_DEC::m_p_head->m_p_parent == NULL) | |
229 | return (std::make_pair((node_pointer)NULL, | |
230 | PB_DS_BASE_C_DEC::m_p_head)); | |
231 | ||
232 | node_pointer p_r_parent = PB_DS_BASE_C_DEC::m_p_head; | |
233 | ||
234 | while (h_r > h_l) | |
235 | { | |
236 | if (p_r->m_red == false) | |
237 | { | |
238 | PB_DS_DBG_ASSERT(h_r > 0); | |
239 | ||
240 | --h_r; | |
241 | } | |
242 | ||
243 | p_r_parent = p_r; | |
244 | ||
245 | p_r = p_r->m_p_left; | |
246 | } | |
247 | ||
248 | if (!is_effectively_black(p_r)) | |
249 | { | |
250 | p_r_parent = p_r; | |
251 | ||
252 | p_r = p_r->m_p_left; | |
253 | } | |
254 | ||
255 | PB_DS_DBG_ASSERT(is_effectively_black(p_r)); | |
256 | PB_DS_DBG_ASSERT(black_height(p_r) == h_l); | |
257 | PB_DS_DBG_ASSERT(p_r == NULL || p_r->m_p_parent == p_r_parent); | |
258 | ||
259 | return (std::make_pair(p_r, p_r_parent)); | |
260 | } | |
261 | ||
262 | PB_DS_CLASS_T_DEC | |
263 | inline typename PB_DS_CLASS_C_DEC::size_type | |
264 | PB_DS_CLASS_C_DEC:: | |
265 | black_height(node_pointer p_nd) | |
266 | { | |
267 | size_type h = 1; | |
268 | ||
269 | while (p_nd != NULL) | |
270 | { | |
271 | if (p_nd->m_red == false) | |
272 | ++h; | |
273 | ||
274 | p_nd = p_nd->m_p_left; | |
275 | } | |
276 | ||
277 | return (h); | |
278 | } | |
279 | ||
280 | PB_DS_CLASS_T_DEC | |
281 | void | |
282 | PB_DS_CLASS_C_DEC:: | |
283 | split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other) | |
284 | { | |
285 | PB_DS_DBG_ONLY(assert_valid()); | |
286 | PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::assert_valid();) | |
287 | ||
288 | PB_DS_DBG_ONLY(other.assert_valid()); | |
289 | PB_DS_DBG_ONLY(other.PB_DS_BASE_C_DEC::assert_valid();) | |
290 | ||
291 | if (PB_DS_BASE_C_DEC::split_prep(r_key, other) == false) | |
292 | { | |
293 | PB_DS_DBG_ONLY(assert_valid()); | |
294 | PB_DS_DBG_ONLY(other.assert_valid()); | |
295 | ||
296 | return; | |
297 | } | |
298 | ||
299 | PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid();) | |
300 | ||
301 | PB_DS_DBG_ONLY(other.PB_DS_BASE_C_DEC::structure_only_assert_valid();) | |
302 | ||
303 | node_pointer p_nd = upper_bound(r_key).m_p_nd; | |
304 | ||
305 | do | |
306 | { | |
307 | node_pointer p_next_nd = p_nd->m_p_parent; | |
308 | ||
309 | if (Cmp_Fn::operator()( | |
310 | r_key, | |
311 | PB_DS_V2F(p_nd->m_value))) | |
312 | split_at_node(p_nd, other); | |
313 | ||
314 | PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid();) | |
315 | PB_DS_DBG_ONLY(other.PB_DS_BASE_C_DEC::structure_only_assert_valid();) | |
316 | ||
317 | p_nd = p_next_nd; | |
318 | } | |
319 | while (p_nd != PB_DS_BASE_C_DEC::m_p_head); | |
320 | ||
321 | PB_DS_BASE_C_DEC::split_finish(other); | |
322 | ||
323 | PB_DS_DBG_ONLY(assert_valid();) | |
324 | PB_DS_DBG_ONLY(assert_valid();) | |
325 | } | |
326 | ||
327 | PB_DS_CLASS_T_DEC | |
328 | void | |
329 | PB_DS_CLASS_C_DEC:: | |
330 | split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other) | |
331 | { | |
332 | PB_DS_DBG_ASSERT(p_nd != NULL); | |
333 | ||
334 | node_pointer p_l = p_nd->m_p_left; | |
335 | node_pointer p_r = p_nd->m_p_right; | |
336 | ||
337 | node_pointer p_parent = p_nd->m_p_parent; | |
338 | ||
339 | if (p_parent == PB_DS_BASE_C_DEC::m_p_head) | |
340 | { | |
341 | PB_DS_BASE_C_DEC::m_p_head->m_p_parent = p_l; | |
342 | ||
343 | if (p_l != NULL) | |
344 | { | |
345 | p_l->m_p_parent = PB_DS_BASE_C_DEC::m_p_head; | |
346 | ||
347 | p_l->m_red = false; | |
348 | } | |
349 | } | |
350 | else | |
351 | { | |
352 | if (p_parent->m_p_left == p_nd) | |
353 | p_parent->m_p_left = p_l; | |
354 | else | |
355 | p_parent->m_p_right = p_l; | |
356 | ||
357 | if (p_l != NULL) | |
358 | p_l->m_p_parent = p_parent; | |
359 | ||
360 | update_to_top(p_parent, (node_update* )this); | |
361 | ||
362 | if (!p_nd->m_red) | |
363 | remove_fixup(p_l, p_parent); | |
364 | } | |
365 | ||
366 | PB_DS_BASE_C_DEC::initialize_min_max(); | |
367 | ||
368 | other.join_imp(p_nd, p_r); | |
369 | ||
370 | PB_DS_DBG_ONLY(PB_DS_BASE_C_DEC::structure_only_assert_valid()); | |
371 | ||
372 | PB_DS_DBG_ONLY(other.PB_DS_BASE_C_DEC::structure_only_assert_valid()); | |
373 | } | |
374 |