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