]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
8d9254fc | 3 | // Copyright (C) 2005-2020 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 | /** | |
a345e45d | 37 | * @file rb_tree_map_/split_join_fn_imps.hpp |
4569a895 AT |
38 | * Contains an implementation for rb_tree_. |
39 | */ | |
40 | ||
574dfb67 JW |
41 | #ifdef PB_DS_CLASS_C_DEC |
42 | ||
4569a895 AT |
43 | PB_DS_CLASS_T_DEC |
44 | inline void | |
45 | PB_DS_CLASS_C_DEC:: | |
46 | join(PB_DS_CLASS_C_DEC& other) | |
47 | { | |
f5886803 FD |
48 | PB_DS_ASSERT_VALID((*this)) |
49 | PB_DS_ASSERT_VALID(other) | |
1b24692f | 50 | if (base_type::join_prep(other) == false) |
47bea7b8 | 51 | { |
f5886803 FD |
52 | PB_DS_ASSERT_VALID((*this)) |
53 | PB_DS_ASSERT_VALID(other) | |
47bea7b8 BK |
54 | return; |
55 | } | |
4569a895 AT |
56 | |
57 | const node_pointer p_x = other.split_min(); | |
4569a895 | 58 | join_imp(p_x, other.m_p_head->m_p_parent); |
1b24692f | 59 | base_type::join_finish(other); |
f5886803 FD |
60 | PB_DS_ASSERT_VALID((*this)) |
61 | PB_DS_ASSERT_VALID(other) | |
47bea7b8 | 62 | } |
4569a895 AT |
63 | |
64 | PB_DS_CLASS_T_DEC | |
65 | void | |
66 | PB_DS_CLASS_C_DEC:: | |
67 | join_imp(node_pointer p_x, node_pointer p_r) | |
68 | { | |
8fc81078 PC |
69 | _GLIBCXX_DEBUG_ASSERT(p_x != 0); |
70 | if (p_r != 0) | |
4569a895 AT |
71 | p_r->m_red = false; |
72 | ||
1b24692f | 73 | const size_type h = black_height(base_type::m_p_head->m_p_parent); |
4569a895 | 74 | const size_type other_h = black_height(p_r); |
4569a895 AT |
75 | node_pointer p_x_l; |
76 | node_pointer p_x_r; | |
4569a895 | 77 | std::pair<node_pointer, node_pointer> join_pos; |
4569a895 | 78 | const bool right_join = h >= other_h; |
4569a895 AT |
79 | if (right_join) |
80 | { | |
1b24692f | 81 | join_pos = find_join_pos_right(base_type::m_p_head->m_p_parent, |
47bea7b8 | 82 | h, other_h); |
4569a895 AT |
83 | p_x_l = join_pos.first; |
84 | p_x_r = p_r; | |
85 | } | |
86 | else | |
87 | { | |
1b24692f BK |
88 | p_x_l = base_type::m_p_head->m_p_parent; |
89 | base_type::m_p_head->m_p_parent = p_r; | |
8fc81078 | 90 | if (p_r != 0) |
1b24692f | 91 | p_r->m_p_parent = base_type::m_p_head; |
4569a895 | 92 | |
1b24692f | 93 | join_pos = find_join_pos_left(base_type::m_p_head->m_p_parent, |
47bea7b8 | 94 | h, other_h); |
4569a895 AT |
95 | p_x_r = join_pos.first; |
96 | } | |
97 | ||
98 | node_pointer p_parent = join_pos.second; | |
1b24692f | 99 | if (p_parent == base_type::m_p_head) |
4569a895 | 100 | { |
1b24692f BK |
101 | base_type::m_p_head->m_p_parent = p_x; |
102 | p_x->m_p_parent = base_type::m_p_head; | |
4569a895 AT |
103 | } |
104 | else | |
105 | { | |
106 | p_x->m_p_parent = p_parent; | |
4569a895 AT |
107 | if (right_join) |
108 | p_x->m_p_parent->m_p_right = p_x; | |
109 | else | |
110 | p_x->m_p_parent->m_p_left = p_x; | |
111 | } | |
112 | ||
113 | p_x->m_p_left = p_x_l; | |
8fc81078 | 114 | if (p_x_l != 0) |
4569a895 AT |
115 | p_x_l->m_p_parent = p_x; |
116 | ||
117 | p_x->m_p_right = p_x_r; | |
8fc81078 | 118 | if (p_x_r != 0) |
4569a895 AT |
119 | p_x_r->m_p_parent = p_x; |
120 | ||
121 | p_x->m_red = true; | |
122 | ||
1b24692f | 123 | base_type::initialize_min_max(); |
f5886803 | 124 | PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) |
1b24692f | 125 | base_type::update_to_top(p_x, (node_update* )this); |
4569a895 | 126 | insert_fixup(p_x); |
f5886803 | 127 | PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) |
4569a895 AT |
128 | } |
129 | ||
130 | PB_DS_CLASS_T_DEC | |
131 | inline typename PB_DS_CLASS_C_DEC::node_pointer | |
132 | PB_DS_CLASS_C_DEC:: | |
133 | split_min() | |
134 | { | |
1b24692f | 135 | node_pointer p_min = base_type::m_p_head->m_p_left; |
4569a895 | 136 | |
47bea7b8 | 137 | #ifdef _GLIBCXX_DEBUG |
1b24692f | 138 | const node_pointer p_head = base_type::m_p_head; |
47bea7b8 BK |
139 | _GLIBCXX_DEBUG_ASSERT(p_min != p_head); |
140 | #endif | |
4569a895 AT |
141 | |
142 | remove_node(p_min); | |
1b24692f | 143 | return p_min; |
4569a895 AT |
144 | } |
145 | ||
146 | PB_DS_CLASS_T_DEC | |
147 | std::pair< | |
148 | typename PB_DS_CLASS_C_DEC::node_pointer, | |
149 | typename PB_DS_CLASS_C_DEC::node_pointer> | |
150 | PB_DS_CLASS_C_DEC:: | |
151 | find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r) | |
152 | { | |
47bea7b8 | 153 | _GLIBCXX_DEBUG_ASSERT(h_l >= h_r); |
4569a895 | 154 | |
8fc81078 PC |
155 | if (base_type::m_p_head->m_p_parent == 0) |
156 | return (std::make_pair((node_pointer)0, base_type::m_p_head)); | |
4569a895 | 157 | |
1b24692f | 158 | node_pointer p_l_parent = base_type::m_p_head; |
4569a895 AT |
159 | while (h_l > h_r) |
160 | { | |
161 | if (p_l->m_red == false) | |
162 | { | |
47bea7b8 | 163 | _GLIBCXX_DEBUG_ASSERT(h_l > 0); |
4569a895 AT |
164 | --h_l; |
165 | } | |
166 | ||
167 | p_l_parent = p_l; | |
4569a895 AT |
168 | p_l = p_l->m_p_right; |
169 | } | |
170 | ||
171 | if (!is_effectively_black(p_l)) | |
172 | { | |
173 | p_l_parent = p_l; | |
4569a895 AT |
174 | p_l = p_l->m_p_right; |
175 | } | |
176 | ||
47bea7b8 BK |
177 | _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_l)); |
178 | _GLIBCXX_DEBUG_ASSERT(black_height(p_l) == h_r); | |
8fc81078 | 179 | _GLIBCXX_DEBUG_ASSERT(p_l == 0 || p_l->m_p_parent == p_l_parent); |
47bea7b8 | 180 | return std::make_pair(p_l, p_l_parent); |
4569a895 AT |
181 | } |
182 | ||
183 | PB_DS_CLASS_T_DEC | |
184 | std::pair< | |
185 | typename PB_DS_CLASS_C_DEC::node_pointer, | |
186 | typename PB_DS_CLASS_C_DEC::node_pointer> | |
187 | PB_DS_CLASS_C_DEC:: | |
188 | find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r) | |
189 | { | |
47bea7b8 | 190 | _GLIBCXX_DEBUG_ASSERT(h_r > h_l); |
8fc81078 PC |
191 | if (base_type::m_p_head->m_p_parent == 0) |
192 | return (std::make_pair((node_pointer)0, | |
1b24692f BK |
193 | base_type::m_p_head)); |
194 | node_pointer p_r_parent = base_type::m_p_head; | |
4569a895 AT |
195 | while (h_r > h_l) |
196 | { | |
197 | if (p_r->m_red == false) | |
198 | { | |
47bea7b8 | 199 | _GLIBCXX_DEBUG_ASSERT(h_r > 0); |
4569a895 AT |
200 | --h_r; |
201 | } | |
202 | ||
203 | p_r_parent = p_r; | |
4569a895 AT |
204 | p_r = p_r->m_p_left; |
205 | } | |
206 | ||
207 | if (!is_effectively_black(p_r)) | |
208 | { | |
209 | p_r_parent = p_r; | |
4569a895 AT |
210 | p_r = p_r->m_p_left; |
211 | } | |
212 | ||
47bea7b8 BK |
213 | _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_r)); |
214 | _GLIBCXX_DEBUG_ASSERT(black_height(p_r) == h_l); | |
8fc81078 | 215 | _GLIBCXX_DEBUG_ASSERT(p_r == 0 || p_r->m_p_parent == p_r_parent); |
47bea7b8 | 216 | return std::make_pair(p_r, p_r_parent); |
4569a895 AT |
217 | } |
218 | ||
219 | PB_DS_CLASS_T_DEC | |
220 | inline typename PB_DS_CLASS_C_DEC::size_type | |
221 | PB_DS_CLASS_C_DEC:: | |
222 | black_height(node_pointer p_nd) | |
223 | { | |
224 | size_type h = 1; | |
8fc81078 | 225 | while (p_nd != 0) |
4569a895 AT |
226 | { |
227 | if (p_nd->m_red == false) | |
228 | ++h; | |
4569a895 AT |
229 | p_nd = p_nd->m_p_left; |
230 | } | |
47bea7b8 | 231 | return h; |
4569a895 AT |
232 | } |
233 | ||
234 | PB_DS_CLASS_T_DEC | |
235 | void | |
236 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 237 | split(key_const_reference r_key, PB_DS_CLASS_C_DEC& other) |
4569a895 | 238 | { |
f5886803 FD |
239 | PB_DS_ASSERT_VALID((*this)) |
240 | PB_DS_ASSERT_VALID(other) | |
4569a895 | 241 | |
f5886803 FD |
242 | if (base_type::split_prep(r_key, other) == false) |
243 | { | |
244 | PB_DS_ASSERT_VALID((*this)) | |
245 | PB_DS_ASSERT_VALID(other) | |
246 | return; | |
247 | } | |
4569a895 | 248 | |
f5886803 FD |
249 | PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) |
250 | PB_DS_STRUCT_ONLY_ASSERT_VALID(other) | |
94df301f | 251 | node_pointer p_nd = this->upper_bound(r_key).m_p_nd; |
4569a895 AT |
252 | do |
253 | { | |
254 | node_pointer p_next_nd = p_nd->m_p_parent; | |
47bea7b8 | 255 | if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) |
4569a895 AT |
256 | split_at_node(p_nd, other); |
257 | ||
f5886803 FD |
258 | PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) |
259 | PB_DS_STRUCT_ONLY_ASSERT_VALID(other) | |
47bea7b8 | 260 | p_nd = p_next_nd; |
4569a895 | 261 | } |
1b24692f | 262 | while (p_nd != base_type::m_p_head); |
4569a895 | 263 | |
1b24692f | 264 | base_type::split_finish(other); |
f5886803 | 265 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 266 | } |
4569a895 AT |
267 | |
268 | PB_DS_CLASS_T_DEC | |
269 | void | |
270 | PB_DS_CLASS_C_DEC:: | |
271 | split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other) | |
272 | { | |
8fc81078 | 273 | _GLIBCXX_DEBUG_ASSERT(p_nd != 0); |
4569a895 AT |
274 | |
275 | node_pointer p_l = p_nd->m_p_left; | |
276 | node_pointer p_r = p_nd->m_p_right; | |
4569a895 | 277 | node_pointer p_parent = p_nd->m_p_parent; |
1b24692f | 278 | if (p_parent == base_type::m_p_head) |
4569a895 | 279 | { |
1b24692f | 280 | base_type::m_p_head->m_p_parent = p_l; |
8fc81078 | 281 | if (p_l != 0) |
4569a895 | 282 | { |
1b24692f | 283 | p_l->m_p_parent = base_type::m_p_head; |
4569a895 AT |
284 | p_l->m_red = false; |
285 | } | |
286 | } | |
287 | else | |
288 | { | |
289 | if (p_parent->m_p_left == p_nd) | |
290 | p_parent->m_p_left = p_l; | |
291 | else | |
292 | p_parent->m_p_right = p_l; | |
293 | ||
8fc81078 | 294 | if (p_l != 0) |
4569a895 AT |
295 | p_l->m_p_parent = p_parent; |
296 | ||
94df301f | 297 | this->update_to_top(p_parent, (node_update* )this); |
4569a895 AT |
298 | |
299 | if (!p_nd->m_red) | |
300 | remove_fixup(p_l, p_parent); | |
301 | } | |
302 | ||
1b24692f | 303 | base_type::initialize_min_max(); |
4569a895 | 304 | other.join_imp(p_nd, p_r); |
f5886803 FD |
305 | PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) |
306 | PB_DS_STRUCT_ONLY_ASSERT_VALID(other) | |
4569a895 AT |
307 | } |
308 | ||
574dfb67 | 309 | #endif |