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