libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file rb_tree_map_/split_join_fn_imps.hpp 00038 * Contains an implementation for rb_tree_. 00039 */ 00040 00041 PB_DS_CLASS_T_DEC 00042 inline void 00043 PB_DS_CLASS_C_DEC:: 00044 join(PB_DS_CLASS_C_DEC& other) 00045 { 00046 PB_DS_ASSERT_VALID((*this)) 00047 PB_DS_ASSERT_VALID(other) 00048 if (base_type::join_prep(other) == false) 00049 { 00050 PB_DS_ASSERT_VALID((*this)) 00051 PB_DS_ASSERT_VALID(other) 00052 return; 00053 } 00054 00055 const node_pointer p_x = other.split_min(); 00056 join_imp(p_x, other.m_p_head->m_p_parent); 00057 base_type::join_finish(other); 00058 PB_DS_ASSERT_VALID((*this)) 00059 PB_DS_ASSERT_VALID(other) 00060 } 00061 00062 PB_DS_CLASS_T_DEC 00063 void 00064 PB_DS_CLASS_C_DEC:: 00065 join_imp(node_pointer p_x, node_pointer p_r) 00066 { 00067 _GLIBCXX_DEBUG_ASSERT(p_x != 0); 00068 if (p_r != 0) 00069 p_r->m_red = false; 00070 00071 const size_type h = black_height(base_type::m_p_head->m_p_parent); 00072 const size_type other_h = black_height(p_r); 00073 node_pointer p_x_l; 00074 node_pointer p_x_r; 00075 std::pair<node_pointer, node_pointer> join_pos; 00076 const bool right_join = h >= other_h; 00077 if (right_join) 00078 { 00079 join_pos = find_join_pos_right(base_type::m_p_head->m_p_parent, 00080 h, other_h); 00081 p_x_l = join_pos.first; 00082 p_x_r = p_r; 00083 } 00084 else 00085 { 00086 p_x_l = base_type::m_p_head->m_p_parent; 00087 base_type::m_p_head->m_p_parent = p_r; 00088 if (p_r != 0) 00089 p_r->m_p_parent = base_type::m_p_head; 00090 00091 join_pos = find_join_pos_left(base_type::m_p_head->m_p_parent, 00092 h, other_h); 00093 p_x_r = join_pos.first; 00094 } 00095 00096 node_pointer p_parent = join_pos.second; 00097 if (p_parent == base_type::m_p_head) 00098 { 00099 base_type::m_p_head->m_p_parent = p_x; 00100 p_x->m_p_parent = base_type::m_p_head; 00101 } 00102 else 00103 { 00104 p_x->m_p_parent = p_parent; 00105 if (right_join) 00106 p_x->m_p_parent->m_p_right = p_x; 00107 else 00108 p_x->m_p_parent->m_p_left = p_x; 00109 } 00110 00111 p_x->m_p_left = p_x_l; 00112 if (p_x_l != 0) 00113 p_x_l->m_p_parent = p_x; 00114 00115 p_x->m_p_right = p_x_r; 00116 if (p_x_r != 0) 00117 p_x_r->m_p_parent = p_x; 00118 00119 p_x->m_red = true; 00120 00121 base_type::initialize_min_max(); 00122 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 00123 base_type::update_to_top(p_x, (node_update* )this); 00124 insert_fixup(p_x); 00125 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 00126 } 00127 00128 PB_DS_CLASS_T_DEC 00129 inline typename PB_DS_CLASS_C_DEC::node_pointer 00130 PB_DS_CLASS_C_DEC:: 00131 split_min() 00132 { 00133 node_pointer p_min = base_type::m_p_head->m_p_left; 00134 00135 #ifdef _GLIBCXX_DEBUG 00136 const node_pointer p_head = base_type::m_p_head; 00137 _GLIBCXX_DEBUG_ASSERT(p_min != p_head); 00138 #endif 00139 00140 remove_node(p_min); 00141 return p_min; 00142 } 00143 00144 PB_DS_CLASS_T_DEC 00145 std::pair< 00146 typename PB_DS_CLASS_C_DEC::node_pointer, 00147 typename PB_DS_CLASS_C_DEC::node_pointer> 00148 PB_DS_CLASS_C_DEC:: 00149 find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r) 00150 { 00151 _GLIBCXX_DEBUG_ASSERT(h_l >= h_r); 00152 00153 if (base_type::m_p_head->m_p_parent == 0) 00154 return (std::make_pair((node_pointer)0, base_type::m_p_head)); 00155 00156 node_pointer p_l_parent = base_type::m_p_head; 00157 while (h_l > h_r) 00158 { 00159 if (p_l->m_red == false) 00160 { 00161 _GLIBCXX_DEBUG_ASSERT(h_l > 0); 00162 --h_l; 00163 } 00164 00165 p_l_parent = p_l; 00166 p_l = p_l->m_p_right; 00167 } 00168 00169 if (!is_effectively_black(p_l)) 00170 { 00171 p_l_parent = p_l; 00172 p_l = p_l->m_p_right; 00173 } 00174 00175 _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_l)); 00176 _GLIBCXX_DEBUG_ASSERT(black_height(p_l) == h_r); 00177 _GLIBCXX_DEBUG_ASSERT(p_l == 0 || p_l->m_p_parent == p_l_parent); 00178 return std::make_pair(p_l, p_l_parent); 00179 } 00180 00181 PB_DS_CLASS_T_DEC 00182 std::pair< 00183 typename PB_DS_CLASS_C_DEC::node_pointer, 00184 typename PB_DS_CLASS_C_DEC::node_pointer> 00185 PB_DS_CLASS_C_DEC:: 00186 find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r) 00187 { 00188 _GLIBCXX_DEBUG_ASSERT(h_r > h_l); 00189 if (base_type::m_p_head->m_p_parent == 0) 00190 return (std::make_pair((node_pointer)0, 00191 base_type::m_p_head)); 00192 node_pointer p_r_parent = base_type::m_p_head; 00193 while (h_r > h_l) 00194 { 00195 if (p_r->m_red == false) 00196 { 00197 _GLIBCXX_DEBUG_ASSERT(h_r > 0); 00198 --h_r; 00199 } 00200 00201 p_r_parent = p_r; 00202 p_r = p_r->m_p_left; 00203 } 00204 00205 if (!is_effectively_black(p_r)) 00206 { 00207 p_r_parent = p_r; 00208 p_r = p_r->m_p_left; 00209 } 00210 00211 _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_r)); 00212 _GLIBCXX_DEBUG_ASSERT(black_height(p_r) == h_l); 00213 _GLIBCXX_DEBUG_ASSERT(p_r == 0 || p_r->m_p_parent == p_r_parent); 00214 return std::make_pair(p_r, p_r_parent); 00215 } 00216 00217 PB_DS_CLASS_T_DEC 00218 inline typename PB_DS_CLASS_C_DEC::size_type 00219 PB_DS_CLASS_C_DEC:: 00220 black_height(node_pointer p_nd) 00221 { 00222 size_type h = 1; 00223 while (p_nd != 0) 00224 { 00225 if (p_nd->m_red == false) 00226 ++h; 00227 p_nd = p_nd->m_p_left; 00228 } 00229 return h; 00230 } 00231 00232 PB_DS_CLASS_T_DEC 00233 void 00234 PB_DS_CLASS_C_DEC:: 00235 split(key_const_reference r_key, PB_DS_CLASS_C_DEC& other) 00236 { 00237 PB_DS_ASSERT_VALID((*this)) 00238 PB_DS_ASSERT_VALID(other) 00239 00240 if (base_type::split_prep(r_key, other) == false) 00241 { 00242 PB_DS_ASSERT_VALID((*this)) 00243 PB_DS_ASSERT_VALID(other) 00244 return; 00245 } 00246 00247 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 00248 PB_DS_STRUCT_ONLY_ASSERT_VALID(other) 00249 node_pointer p_nd = this->upper_bound(r_key).m_p_nd; 00250 do 00251 { 00252 node_pointer p_next_nd = p_nd->m_p_parent; 00253 if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value))) 00254 split_at_node(p_nd, other); 00255 00256 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 00257 PB_DS_STRUCT_ONLY_ASSERT_VALID(other) 00258 p_nd = p_next_nd; 00259 } 00260 while (p_nd != base_type::m_p_head); 00261 00262 base_type::split_finish(other); 00263 PB_DS_ASSERT_VALID((*this)) 00264 } 00265 00266 PB_DS_CLASS_T_DEC 00267 void 00268 PB_DS_CLASS_C_DEC:: 00269 split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other) 00270 { 00271 _GLIBCXX_DEBUG_ASSERT(p_nd != 0); 00272 00273 node_pointer p_l = p_nd->m_p_left; 00274 node_pointer p_r = p_nd->m_p_right; 00275 node_pointer p_parent = p_nd->m_p_parent; 00276 if (p_parent == base_type::m_p_head) 00277 { 00278 base_type::m_p_head->m_p_parent = p_l; 00279 if (p_l != 0) 00280 { 00281 p_l->m_p_parent = base_type::m_p_head; 00282 p_l->m_red = false; 00283 } 00284 } 00285 else 00286 { 00287 if (p_parent->m_p_left == p_nd) 00288 p_parent->m_p_left = p_l; 00289 else 00290 p_parent->m_p_right = p_l; 00291 00292 if (p_l != 0) 00293 p_l->m_p_parent = p_parent; 00294 00295 this->update_to_top(p_parent, (node_update* )this); 00296 00297 if (!p_nd->m_red) 00298 remove_fixup(p_l, p_parent); 00299 } 00300 00301 base_type::initialize_min_max(); 00302 other.join_imp(p_nd, p_r); 00303 PB_DS_STRUCT_ONLY_ASSERT_VALID((*this)) 00304 PB_DS_STRUCT_ONLY_ASSERT_VALID(other) 00305 } 00306