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