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