split_join_fn_imps.hpp revision 302408
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 47PB_DS_CLASS_T_DEC 48inline void 49PB_DS_CLASS_C_DEC:: 50join(PB_DS_CLASS_C_DEC& other) 51{ 52 _GLIBCXX_DEBUG_ONLY(assert_valid();) 53 _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 54 _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();) 55 if (base_type::join_prep(other) == false) 56 { 57 _GLIBCXX_DEBUG_ONLY(assert_valid();) 58 _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 59 return; 60 } 61 62 const node_pointer p_x = other.split_min(); 63 join_imp(p_x, other.m_p_head->m_p_parent); 64 base_type::join_finish(other); 65 _GLIBCXX_DEBUG_ONLY(assert_valid();) 66 _GLIBCXX_DEBUG_ONLY(base_type::assert_valid();) 67 _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 68 _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();) 69 } 70 71PB_DS_CLASS_T_DEC 72void 73PB_DS_CLASS_C_DEC:: 74join_imp(node_pointer p_x, node_pointer p_r) 75{ 76 _GLIBCXX_DEBUG_ASSERT(p_x != NULL); 77 if (p_r != NULL) 78 p_r->m_red = false; 79 80 const size_type h = black_height(base_type::m_p_head->m_p_parent); 81 const size_type other_h = black_height(p_r); 82 node_pointer p_x_l; 83 node_pointer p_x_r; 84 std::pair<node_pointer, node_pointer> join_pos; 85 const bool right_join = h >= other_h; 86 if (right_join) 87 { 88 join_pos = find_join_pos_right(base_type::m_p_head->m_p_parent, 89 h, other_h); 90 p_x_l = join_pos.first; 91 p_x_r = p_r; 92 } 93 else 94 { 95 p_x_l = base_type::m_p_head->m_p_parent; 96 base_type::m_p_head->m_p_parent = p_r; 97 if (p_r != NULL) 98 p_r->m_p_parent = base_type::m_p_head; 99 100 join_pos = find_join_pos_left(base_type::m_p_head->m_p_parent, 101 h, other_h); 102 p_x_r = join_pos.first; 103 } 104 105 node_pointer p_parent = join_pos.second; 106 if (p_parent == base_type::m_p_head) 107 { 108 base_type::m_p_head->m_p_parent = p_x; 109 p_x->m_p_parent = base_type::m_p_head; 110 } 111 else 112 { 113 p_x->m_p_parent = p_parent; 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 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); 133 insert_fixup(p_x); 134 _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid()); 135} 136 137PB_DS_CLASS_T_DEC 138inline typename PB_DS_CLASS_C_DEC::node_pointer 139PB_DS_CLASS_C_DEC:: 140split_min() 141{ 142 node_pointer p_min = base_type::m_p_head->m_p_left; 143 144#ifdef _GLIBCXX_DEBUG 145 const node_pointer p_head = base_type::m_p_head; 146 _GLIBCXX_DEBUG_ASSERT(p_min != p_head); 147#endif 148 149 remove_node(p_min); 150 return p_min; 151} 152 153PB_DS_CLASS_T_DEC 154std::pair< 155 typename PB_DS_CLASS_C_DEC::node_pointer, 156 typename PB_DS_CLASS_C_DEC::node_pointer> 157PB_DS_CLASS_C_DEC:: 158find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r) 159{ 160 _GLIBCXX_DEBUG_ASSERT(h_l >= h_r); 161 162 if (base_type::m_p_head->m_p_parent == NULL) 163 return (std::make_pair((node_pointer)NULL, base_type::m_p_head)); 164 165 node_pointer p_l_parent = base_type::m_p_head; 166 while (h_l > h_r) 167 { 168 if (p_l->m_red == false) 169 { 170 _GLIBCXX_DEBUG_ASSERT(h_l > 0); 171 --h_l; 172 } 173 174 p_l_parent = p_l; 175 p_l = p_l->m_p_right; 176 } 177 178 if (!is_effectively_black(p_l)) 179 { 180 p_l_parent = p_l; 181 p_l = p_l->m_p_right; 182 } 183 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); 188} 189 190PB_DS_CLASS_T_DEC 191std::pair< 192 typename PB_DS_CLASS_C_DEC::node_pointer, 193 typename PB_DS_CLASS_C_DEC::node_pointer> 194PB_DS_CLASS_C_DEC:: 195find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r) 196{ 197 _GLIBCXX_DEBUG_ASSERT(h_r > h_l); 198 if (base_type::m_p_head->m_p_parent == NULL) 199 return (std::make_pair((node_pointer)NULL, 200 base_type::m_p_head)); 201 node_pointer p_r_parent = base_type::m_p_head; 202 while (h_r > h_l) 203 { 204 if (p_r->m_red == false) 205 { 206 _GLIBCXX_DEBUG_ASSERT(h_r > 0); 207 --h_r; 208 } 209 210 p_r_parent = p_r; 211 p_r = p_r->m_p_left; 212 } 213 214 if (!is_effectively_black(p_r)) 215 { 216 p_r_parent = p_r; 217 p_r = p_r->m_p_left; 218 } 219 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); 224} 225 226PB_DS_CLASS_T_DEC 227inline typename PB_DS_CLASS_C_DEC::size_type 228PB_DS_CLASS_C_DEC:: 229black_height(node_pointer p_nd) 230{ 231 size_type h = 1; 232 while (p_nd != NULL) 233 { 234 if (p_nd->m_red == false) 235 ++h; 236 p_nd = p_nd->m_p_left; 237 } 238 return h; 239} 240 241PB_DS_CLASS_T_DEC 242void 243PB_DS_CLASS_C_DEC:: 244split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other) 245{ 246 _GLIBCXX_DEBUG_ONLY(assert_valid()); 247 _GLIBCXX_DEBUG_ONLY(base_type::assert_valid();) 248 249 _GLIBCXX_DEBUG_ONLY(other.assert_valid()); 250 _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();) 251 252 if (base_type::split_prep(r_key, other) == false) 253 { 254 _GLIBCXX_DEBUG_ONLY(assert_valid()); 255 _GLIBCXX_DEBUG_ONLY(other.assert_valid()); 256 return; 257 } 258 259 _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();) 260 _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid();) 261 node_pointer p_nd = upper_bound(r_key).m_p_nd; 262 do 263 { 264 node_pointer p_next_nd = p_nd->m_p_parent; 265 if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) 266 split_at_node(p_nd, other); 267 268 _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();) 269 _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid();) 270 p_nd = p_next_nd; 271 } 272 while (p_nd != base_type::m_p_head); 273 274 base_type::split_finish(other); 275 _GLIBCXX_DEBUG_ONLY(assert_valid();) 276 _GLIBCXX_DEBUG_ONLY(assert_valid();) 277} 278 279PB_DS_CLASS_T_DEC 280void 281PB_DS_CLASS_C_DEC:: 282split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other) 283{ 284 _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); 285 286 node_pointer p_l = p_nd->m_p_left; 287 node_pointer p_r = p_nd->m_p_right; 288 node_pointer p_parent = p_nd->m_p_parent; 289 if (p_parent == base_type::m_p_head) 290 { 291 base_type::m_p_head->m_p_parent = p_l; 292 if (p_l != NULL) 293 { 294 p_l->m_p_parent = base_type::m_p_head; 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 314 base_type::initialize_min_max(); 315 other.join_imp(p_nd, p_r); 316 _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid()); 317 _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid()); 318} 319 320