erase_fn_imps.hpp revision 169692
1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING. If not, write to 18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19// MA 02111-1307, USA. 20 21// As a special exception, you may use this file as part of a free 22// software library without restriction. Specifically, if other files 23// instantiate templates or use macros or inline functions from this 24// file, or you compile this file and link it with other files to 25// produce an executable, this file does not by itself cause the 26// resulting executable to be covered by the GNU General Public 27// License. This exception does not however invalidate any other 28// reasons why the executable file might be covered by the GNU General 29// Public License. 30 31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33// Permission to use, copy, modify, sell, and distribute this software 34// is hereby granted without fee, provided that the above copyright 35// notice appears in all copies, and that both that copyright notice 36// and this permission notice appear in supporting documentation. None 37// of the above authors, nor IBM Haifa Research Laboratories, make any 38// representation about the suitability of this software for any 39// purpose. It is provided "as is" without express or implied 40// warranty. 41 42/** 43 * @file erase_fn_imps.hpp 44 * Contains an implementation class for bin_search_tree_. 45 */ 46 47PB_DS_CLASS_T_DEC 48inline bool 49PB_DS_CLASS_C_DEC:: 50erase(const_key_reference r_key) 51{ 52 node_pointer p_nd = find_imp(r_key); 53 if (p_nd == NULL || p_nd->m_type == pat_trie_internal_node_type) 54 { 55 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key)); 56 return false; 57 } 58 59 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type); 60 if (!synth_e_access_traits::equal_keys(PB_DS_V2F(reinterpret_cast<leaf_pointer>(p_nd)->value()), r_key)) 61 { 62 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key)); 63 return false; 64 } 65 66 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); 67 erase_leaf(static_cast<leaf_pointer>(p_nd)); 68 _GLIBCXX_DEBUG_ONLY(assert_valid();) 69 return true; 70} 71 72PB_DS_CLASS_T_DEC 73void 74PB_DS_CLASS_C_DEC:: 75erase_fixup(internal_node_pointer p_nd) 76{ 77 _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) >= 1); 78 if (std::distance(p_nd->begin(), p_nd->end()) == 1) 79 { 80 node_pointer p_parent = p_nd->m_p_parent; 81 if (p_parent == m_p_head) 82 m_p_head->m_p_parent =* p_nd->begin(); 83 else 84 { 85 _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == pat_trie_internal_node_type); 86 node_pointer p_new_child =* p_nd->begin(); 87 static_cast<internal_node_pointer>(p_parent)->replace_child( 88 p_new_child, 89 pref_begin(p_new_child), 90 pref_end(p_new_child), 91 this); 92 } 93 (*p_nd->begin())->m_p_parent = p_nd->m_p_parent; 94 p_nd->~internal_node(); 95 s_internal_node_allocator.deallocate(p_nd, 1); 96 97 if (p_parent == m_p_head) 98 return; 99 100 _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == pat_trie_internal_node_type); 101 p_nd = static_cast<internal_node_pointer>(p_parent); 102 } 103 104 while (true) 105 { 106 _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) > 1); 107 p_nd->update_prefixes(this); 108 apply_update(p_nd, (node_update* )this); 109 _GLIBCXX_DEBUG_ONLY(p_nd->assert_valid(this);) 110 if (p_nd->m_p_parent->m_type == pat_trie_head_node_type) 111 return; 112 113 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent->m_type == 114 pat_trie_internal_node_type); 115 116 p_nd = static_cast<internal_node_pointer>(p_nd->m_p_parent); 117 } 118} 119 120PB_DS_CLASS_T_DEC 121inline void 122PB_DS_CLASS_C_DEC:: 123actual_erase_leaf(leaf_pointer p_l) 124{ 125 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 126 --m_size; 127 _GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_l->value()))); 128 p_l->~leaf(); 129 s_leaf_allocator.deallocate(p_l, 1); 130} 131 132PB_DS_CLASS_T_DEC 133void 134PB_DS_CLASS_C_DEC:: 135clear() 136{ 137 _GLIBCXX_DEBUG_ONLY(assert_valid();) 138 if (empty()) 139 return; 140 141 clear_imp(m_p_head->m_p_parent); 142 m_size = 0; 143 initialize(); 144 _GLIBCXX_DEBUG_ONLY(map_debug_base::clear();) 145 _GLIBCXX_DEBUG_ONLY(assert_valid();) 146} 147 148PB_DS_CLASS_T_DEC 149void 150PB_DS_CLASS_C_DEC:: 151clear_imp(node_pointer p_nd) 152{ 153 if (p_nd->m_type == pat_trie_internal_node_type) 154 { 155 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); 156 for (typename internal_node::iterator it = 157 static_cast<internal_node_pointer>(p_nd)->begin(); 158 it != static_cast<internal_node_pointer>(p_nd)->end(); 159 ++it) 160 { 161 node_pointer p_child =* it; 162 clear_imp(p_child); 163 } 164 s_internal_node_allocator.deallocate(static_cast<internal_node_pointer>(p_nd), 1); 165 return; 166 } 167 168 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type); 169 static_cast<leaf_pointer>(p_nd)->~leaf(); 170 s_leaf_allocator.deallocate(static_cast<leaf_pointer>(p_nd), 1); 171} 172 173PB_DS_CLASS_T_DEC 174inline typename PB_DS_CLASS_C_DEC::const_iterator 175PB_DS_CLASS_C_DEC:: 176erase(const_iterator it) 177{ 178 _GLIBCXX_DEBUG_ONLY(assert_valid()); 179 180 if (it == end()) 181 return it; 182 183 const_iterator ret_it = it; 184 ++ret_it; 185 _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); 186 erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); 187 _GLIBCXX_DEBUG_ONLY(assert_valid()); 188 return ret_it; 189} 190 191#ifdef PB_DS_DATA_TRUE_INDICATOR 192PB_DS_CLASS_T_DEC 193inline typename PB_DS_CLASS_C_DEC::iterator 194PB_DS_CLASS_C_DEC:: 195erase(iterator it) 196{ 197 _GLIBCXX_DEBUG_ONLY(assert_valid()); 198 199 if (it == end()) 200 return it; 201 iterator ret_it = it; 202 ++ret_it; 203 _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); 204 erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); 205 _GLIBCXX_DEBUG_ONLY(assert_valid()); 206 return ret_it; 207} 208#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR 209 210PB_DS_CLASS_T_DEC 211inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator 212PB_DS_CLASS_C_DEC:: 213erase(const_reverse_iterator it) 214{ 215 _GLIBCXX_DEBUG_ONLY(assert_valid()); 216 217 if (it.m_p_nd == m_p_head) 218 return it; 219 const_reverse_iterator ret_it = it; 220 ++ret_it; 221 222 _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); 223 erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); 224 _GLIBCXX_DEBUG_ONLY(assert_valid()); 225 return ret_it; 226} 227 228#ifdef PB_DS_DATA_TRUE_INDICATOR 229PB_DS_CLASS_T_DEC 230inline typename PB_DS_CLASS_C_DEC::reverse_iterator 231PB_DS_CLASS_C_DEC:: 232erase(reverse_iterator it) 233{ 234 _GLIBCXX_DEBUG_ONLY(assert_valid()); 235 236 if (it.m_p_nd == m_p_head) 237 return it; 238 reverse_iterator ret_it = it; 239 ++ret_it; 240 241 _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); 242 erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); 243 _GLIBCXX_DEBUG_ONLY(assert_valid()); 244 return ret_it; 245} 246#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR 247 248PB_DS_CLASS_T_DEC 249template<typename Pred> 250inline typename PB_DS_CLASS_C_DEC::size_type 251PB_DS_CLASS_C_DEC:: 252erase_if(Pred pred) 253{ 254 size_type num_ersd = 0; 255 _GLIBCXX_DEBUG_ONLY(assert_valid();) 256 257 iterator it = begin(); 258 while (it != end()) 259 { 260 _GLIBCXX_DEBUG_ONLY(assert_valid();) 261 if (pred(*it)) 262 { 263 ++num_ersd; 264 it = erase(it); 265 } 266 else 267 ++it; 268 } 269 270 _GLIBCXX_DEBUG_ONLY(assert_valid();) 271 return num_ersd; 272} 273 274PB_DS_CLASS_T_DEC 275void 276PB_DS_CLASS_C_DEC:: 277erase_leaf(leaf_pointer p_l) 278{ 279 update_min_max_for_erased_leaf(p_l); 280 if (p_l->m_p_parent->m_type == pat_trie_head_node_type) 281 { 282 _GLIBCXX_DEBUG_ASSERT(size() == 1); 283 clear(); 284 return; 285 } 286 287 _GLIBCXX_DEBUG_ASSERT(size() > 1); 288 _GLIBCXX_DEBUG_ASSERT(p_l->m_p_parent->m_type == 289 pat_trie_internal_node_type); 290 291 internal_node_pointer p_parent = 292 static_cast<internal_node_pointer>(p_l->m_p_parent); 293 294 p_parent->remove_child(p_l); 295 erase_fixup(p_parent); 296 actual_erase_leaf(p_l); 297} 298 299PB_DS_CLASS_T_DEC 300void 301PB_DS_CLASS_C_DEC:: 302update_min_max_for_erased_leaf(leaf_pointer p_l) 303{ 304 if (m_size == 1) 305 { 306 m_p_head->m_p_min = m_p_head; 307 m_p_head->m_p_max = m_p_head; 308 return; 309 } 310 311 if (p_l == static_cast<const_leaf_pointer>(m_p_head->m_p_min)) 312 { 313 iterator it(p_l); 314 ++it; 315 m_p_head->m_p_min = it.m_p_nd; 316 return; 317 } 318 319 if (p_l == static_cast<const_leaf_pointer>(m_p_head->m_p_max)) 320 { 321 iterator it(p_l); 322 --it; 323 m_p_head->m_p_max = it.m_p_nd; 324 } 325} 326