1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file split_join_fn_imps.hpp 44169691Skan * Contains an implementation for rb_tree_. 45169691Skan */ 46169691Skan 47169691SkanPB_DS_CLASS_T_DEC 48169691Skaninline void 49169691SkanPB_DS_CLASS_C_DEC:: 50169691Skanjoin(PB_DS_CLASS_C_DEC& other) 51169691Skan{ 52169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 53169691Skan _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 54169691Skan _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();) 55169691Skan if (base_type::join_prep(other) == false) 56169691Skan { 57169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 58169691Skan _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 59169691Skan return; 60169691Skan } 61169691Skan 62169691Skan const node_pointer p_x = other.split_min(); 63169691Skan join_imp(p_x, other.m_p_head->m_p_parent); 64169691Skan base_type::join_finish(other); 65169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 66169691Skan _GLIBCXX_DEBUG_ONLY(base_type::assert_valid();) 67169691Skan _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 68169691Skan _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();) 69169691Skan } 70169691Skan 71169691SkanPB_DS_CLASS_T_DEC 72169691Skanvoid 73169691SkanPB_DS_CLASS_C_DEC:: 74169691Skanjoin_imp(node_pointer p_x, node_pointer p_r) 75169691Skan{ 76169691Skan _GLIBCXX_DEBUG_ASSERT(p_x != NULL); 77169691Skan if (p_r != NULL) 78169691Skan p_r->m_red = false; 79169691Skan 80169691Skan const size_type h = black_height(base_type::m_p_head->m_p_parent); 81169691Skan const size_type other_h = black_height(p_r); 82169691Skan node_pointer p_x_l; 83169691Skan node_pointer p_x_r; 84169691Skan std::pair<node_pointer, node_pointer> join_pos; 85169691Skan const bool right_join = h >= other_h; 86169691Skan if (right_join) 87169691Skan { 88169691Skan join_pos = find_join_pos_right(base_type::m_p_head->m_p_parent, 89169691Skan h, other_h); 90169691Skan p_x_l = join_pos.first; 91169691Skan p_x_r = p_r; 92169691Skan } 93169691Skan else 94169691Skan { 95169691Skan p_x_l = base_type::m_p_head->m_p_parent; 96169691Skan base_type::m_p_head->m_p_parent = p_r; 97169691Skan if (p_r != NULL) 98169691Skan p_r->m_p_parent = base_type::m_p_head; 99169691Skan 100169691Skan join_pos = find_join_pos_left(base_type::m_p_head->m_p_parent, 101169691Skan h, other_h); 102169691Skan p_x_r = join_pos.first; 103169691Skan } 104169691Skan 105169691Skan node_pointer p_parent = join_pos.second; 106169691Skan if (p_parent == base_type::m_p_head) 107169691Skan { 108169691Skan base_type::m_p_head->m_p_parent = p_x; 109169691Skan p_x->m_p_parent = base_type::m_p_head; 110169691Skan } 111169691Skan else 112169691Skan { 113169691Skan p_x->m_p_parent = p_parent; 114169691Skan if (right_join) 115169691Skan p_x->m_p_parent->m_p_right = p_x; 116169691Skan else 117169691Skan p_x->m_p_parent->m_p_left = p_x; 118169691Skan } 119169691Skan 120169691Skan p_x->m_p_left = p_x_l; 121169691Skan if (p_x_l != NULL) 122169691Skan p_x_l->m_p_parent = p_x; 123169691Skan 124169691Skan p_x->m_p_right = p_x_r; 125169691Skan if (p_x_r != NULL) 126169691Skan p_x_r->m_p_parent = p_x; 127169691Skan 128169691Skan p_x->m_red = true; 129169691Skan 130169691Skan base_type::initialize_min_max(); 131169691Skan _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();) 132169691Skan base_type::update_to_top(p_x, (node_update* )this); 133169691Skan insert_fixup(p_x); 134169691Skan _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid()); 135169691Skan} 136169691Skan 137169691SkanPB_DS_CLASS_T_DEC 138169691Skaninline typename PB_DS_CLASS_C_DEC::node_pointer 139169691SkanPB_DS_CLASS_C_DEC:: 140169691Skansplit_min() 141169691Skan{ 142169691Skan node_pointer p_min = base_type::m_p_head->m_p_left; 143169691Skan 144169691Skan#ifdef _GLIBCXX_DEBUG 145169691Skan const node_pointer p_head = base_type::m_p_head; 146169691Skan _GLIBCXX_DEBUG_ASSERT(p_min != p_head); 147169691Skan#endif 148169691Skan 149169691Skan remove_node(p_min); 150169691Skan return p_min; 151169691Skan} 152169691Skan 153169691SkanPB_DS_CLASS_T_DEC 154169691Skanstd::pair< 155169691Skan typename PB_DS_CLASS_C_DEC::node_pointer, 156169691Skan typename PB_DS_CLASS_C_DEC::node_pointer> 157169691SkanPB_DS_CLASS_C_DEC:: 158169691Skanfind_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r) 159169691Skan{ 160169691Skan _GLIBCXX_DEBUG_ASSERT(h_l >= h_r); 161169691Skan 162169691Skan if (base_type::m_p_head->m_p_parent == NULL) 163169691Skan return (std::make_pair((node_pointer)NULL, base_type::m_p_head)); 164169691Skan 165169691Skan node_pointer p_l_parent = base_type::m_p_head; 166169691Skan while (h_l > h_r) 167169691Skan { 168169691Skan if (p_l->m_red == false) 169169691Skan { 170169691Skan _GLIBCXX_DEBUG_ASSERT(h_l > 0); 171169691Skan --h_l; 172169691Skan } 173169691Skan 174169691Skan p_l_parent = p_l; 175169691Skan p_l = p_l->m_p_right; 176169691Skan } 177169691Skan 178169691Skan if (!is_effectively_black(p_l)) 179169691Skan { 180169691Skan p_l_parent = p_l; 181169691Skan p_l = p_l->m_p_right; 182169691Skan } 183169691Skan 184169691Skan _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_l)); 185169691Skan _GLIBCXX_DEBUG_ASSERT(black_height(p_l) == h_r); 186169691Skan _GLIBCXX_DEBUG_ASSERT(p_l == NULL || p_l->m_p_parent == p_l_parent); 187169691Skan return std::make_pair(p_l, p_l_parent); 188169691Skan} 189169691Skan 190169691SkanPB_DS_CLASS_T_DEC 191169691Skanstd::pair< 192169691Skan typename PB_DS_CLASS_C_DEC::node_pointer, 193169691Skan typename PB_DS_CLASS_C_DEC::node_pointer> 194169691SkanPB_DS_CLASS_C_DEC:: 195169691Skanfind_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r) 196169691Skan{ 197169691Skan _GLIBCXX_DEBUG_ASSERT(h_r > h_l); 198169691Skan if (base_type::m_p_head->m_p_parent == NULL) 199169691Skan return (std::make_pair((node_pointer)NULL, 200169691Skan base_type::m_p_head)); 201169691Skan node_pointer p_r_parent = base_type::m_p_head; 202169691Skan while (h_r > h_l) 203169691Skan { 204169691Skan if (p_r->m_red == false) 205169691Skan { 206169691Skan _GLIBCXX_DEBUG_ASSERT(h_r > 0); 207169691Skan --h_r; 208169691Skan } 209169691Skan 210169691Skan p_r_parent = p_r; 211169691Skan p_r = p_r->m_p_left; 212169691Skan } 213169691Skan 214169691Skan if (!is_effectively_black(p_r)) 215169691Skan { 216169691Skan p_r_parent = p_r; 217169691Skan p_r = p_r->m_p_left; 218169691Skan } 219169691Skan 220169691Skan _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_r)); 221169691Skan _GLIBCXX_DEBUG_ASSERT(black_height(p_r) == h_l); 222169691Skan _GLIBCXX_DEBUG_ASSERT(p_r == NULL || p_r->m_p_parent == p_r_parent); 223169691Skan return std::make_pair(p_r, p_r_parent); 224169691Skan} 225169691Skan 226169691SkanPB_DS_CLASS_T_DEC 227169691Skaninline typename PB_DS_CLASS_C_DEC::size_type 228169691SkanPB_DS_CLASS_C_DEC:: 229169691Skanblack_height(node_pointer p_nd) 230169691Skan{ 231169691Skan size_type h = 1; 232169691Skan while (p_nd != NULL) 233169691Skan { 234169691Skan if (p_nd->m_red == false) 235169691Skan ++h; 236169691Skan p_nd = p_nd->m_p_left; 237169691Skan } 238169691Skan return h; 239169691Skan} 240169691Skan 241169691SkanPB_DS_CLASS_T_DEC 242169691Skanvoid 243169691SkanPB_DS_CLASS_C_DEC:: 244169691Skansplit(const_key_reference r_key, PB_DS_CLASS_C_DEC& other) 245169691Skan{ 246169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid()); 247169691Skan _GLIBCXX_DEBUG_ONLY(base_type::assert_valid();) 248169691Skan 249169691Skan _GLIBCXX_DEBUG_ONLY(other.assert_valid()); 250169691Skan _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();) 251169691Skan 252169691Skan if (base_type::split_prep(r_key, other) == false) 253169691Skan { 254169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid()); 255169691Skan _GLIBCXX_DEBUG_ONLY(other.assert_valid()); 256169691Skan return; 257169691Skan } 258169691Skan 259169691Skan _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();) 260169691Skan _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid();) 261169691Skan node_pointer p_nd = upper_bound(r_key).m_p_nd; 262169691Skan do 263169691Skan { 264169691Skan node_pointer p_next_nd = p_nd->m_p_parent; 265169691Skan if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) 266169691Skan split_at_node(p_nd, other); 267169691Skan 268169691Skan _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();) 269169691Skan _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid();) 270169691Skan p_nd = p_next_nd; 271169691Skan } 272169691Skan while (p_nd != base_type::m_p_head); 273169691Skan 274169691Skan base_type::split_finish(other); 275169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 276169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 277169691Skan} 278169691Skan 279169691SkanPB_DS_CLASS_T_DEC 280169691Skanvoid 281169691SkanPB_DS_CLASS_C_DEC:: 282169691Skansplit_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other) 283169691Skan{ 284169691Skan _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); 285169691Skan 286169691Skan node_pointer p_l = p_nd->m_p_left; 287169691Skan node_pointer p_r = p_nd->m_p_right; 288169691Skan node_pointer p_parent = p_nd->m_p_parent; 289169691Skan if (p_parent == base_type::m_p_head) 290169691Skan { 291169691Skan base_type::m_p_head->m_p_parent = p_l; 292169691Skan if (p_l != NULL) 293169691Skan { 294169691Skan p_l->m_p_parent = base_type::m_p_head; 295169691Skan p_l->m_red = false; 296169691Skan } 297169691Skan } 298169691Skan else 299169691Skan { 300169691Skan if (p_parent->m_p_left == p_nd) 301169691Skan p_parent->m_p_left = p_l; 302169691Skan else 303169691Skan p_parent->m_p_right = p_l; 304169691Skan 305169691Skan if (p_l != NULL) 306169691Skan p_l->m_p_parent = p_parent; 307169691Skan 308169691Skan update_to_top(p_parent, (node_update* )this); 309169691Skan 310169691Skan if (!p_nd->m_red) 311169691Skan remove_fixup(p_l, p_parent); 312169691Skan } 313169691Skan 314169691Skan base_type::initialize_min_max(); 315169691Skan other.join_imp(p_nd, p_r); 316169691Skan _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid()); 317169691Skan _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid()); 318169691Skan} 319169691Skan 320