1// -*- C++ -*- 2 3// Copyright (C) 2005-2015 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 pat_trie_/erase_fn_imps.hpp 38 * Contains an implementation class for pat_trie. 39 */ 40 41PB_DS_CLASS_T_DEC 42inline bool 43PB_DS_CLASS_C_DEC:: 44erase(key_const_reference r_key) 45{ 46 node_pointer p_nd = find_imp(r_key); 47 if (p_nd == 0 || p_nd->m_type == i_node) 48 { 49 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 50 return false; 51 } 52 53 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == leaf_node); 54 if (!synth_access_traits::equal_keys(PB_DS_V2F(reinterpret_cast<leaf_pointer>(p_nd)->value()), r_key)) 55 { 56 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) 57 return false; 58 } 59 60 PB_DS_CHECK_KEY_EXISTS(r_key) 61 erase_leaf(static_cast<leaf_pointer>(p_nd)); 62 PB_DS_ASSERT_VALID((*this)) 63 return true; 64} 65 66PB_DS_CLASS_T_DEC 67void 68PB_DS_CLASS_C_DEC:: 69erase_fixup(inode_pointer p_nd) 70{ 71 _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) >= 1); 72 if (std::distance(p_nd->begin(), p_nd->end()) == 1) 73 { 74 node_pointer p_parent = p_nd->m_p_parent; 75 if (p_parent == m_p_head) 76 m_p_head->m_p_parent = *p_nd->begin(); 77 else 78 { 79 _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == i_node); 80 node_pointer p_new_child = *p_nd->begin(); 81 82 typedef inode_pointer inode_ptr; 83 inode_ptr p_internal = static_cast<inode_ptr>(p_parent); 84 p_internal->replace_child(p_new_child, pref_begin(p_new_child), 85 pref_end(p_new_child), this); 86 } 87 (*p_nd->begin())->m_p_parent = p_nd->m_p_parent; 88 p_nd->~inode(); 89 s_inode_allocator.deallocate(p_nd, 1); 90 91 if (p_parent == m_p_head) 92 return; 93 94 _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == i_node); 95 p_nd = static_cast<inode_pointer>(p_parent); 96 } 97 98 while (true) 99 { 100 _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) > 1); 101 p_nd->update_prefixes(this); 102 apply_update(p_nd, (node_update*)this); 103 PB_DS_ASSERT_NODE_VALID(p_nd) 104 if (p_nd->m_p_parent->m_type == head_node) 105 return; 106 107 _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent->m_type == i_node); 108 109 p_nd = static_cast<inode_pointer>(p_nd->m_p_parent); 110 } 111} 112 113PB_DS_CLASS_T_DEC 114inline void 115PB_DS_CLASS_C_DEC:: 116actual_erase_leaf(leaf_pointer p_l) 117{ 118 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 119 --m_size; 120 _GLIBCXX_DEBUG_ONLY(debug_base::erase_existing(PB_DS_V2F(p_l->value()))); 121 p_l->~leaf(); 122 s_leaf_allocator.deallocate(p_l, 1); 123} 124 125PB_DS_CLASS_T_DEC 126void 127PB_DS_CLASS_C_DEC:: 128clear() 129{ 130 if (!empty()) 131 { 132 clear_imp(m_p_head->m_p_parent); 133 m_size = 0; 134 initialize(); 135 _GLIBCXX_DEBUG_ONLY(debug_base::clear();) 136 PB_DS_ASSERT_VALID((*this)) 137 } 138} 139 140PB_DS_CLASS_T_DEC 141void 142PB_DS_CLASS_C_DEC:: 143clear_imp(node_pointer p_nd) 144{ 145 if (p_nd->m_type == i_node) 146 { 147 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == i_node); 148 for (typename inode::iterator it = 149 static_cast<inode_pointer>(p_nd)->begin(); 150 it != static_cast<inode_pointer>(p_nd)->end(); 151 ++it) 152 { 153 node_pointer p_child =* it; 154 clear_imp(p_child); 155 } 156 s_inode_allocator.deallocate(static_cast<inode_pointer>(p_nd), 1); 157 return; 158 } 159 160 _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == leaf_node); 161 static_cast<leaf_pointer>(p_nd)->~leaf(); 162 s_leaf_allocator.deallocate(static_cast<leaf_pointer>(p_nd), 1); 163} 164 165PB_DS_CLASS_T_DEC 166inline typename PB_DS_CLASS_C_DEC::const_iterator 167PB_DS_CLASS_C_DEC:: 168erase(const_iterator it) 169{ 170 PB_DS_ASSERT_VALID((*this)) 171 172 if (it == end()) 173 return it; 174 175 const_iterator ret_it = it; 176 ++ret_it; 177 _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == leaf_node); 178 erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); 179 PB_DS_ASSERT_VALID((*this)) 180 return ret_it; 181} 182 183#ifdef PB_DS_DATA_TRUE_INDICATOR 184PB_DS_CLASS_T_DEC 185inline typename PB_DS_CLASS_C_DEC::iterator 186PB_DS_CLASS_C_DEC:: 187erase(iterator it) 188{ 189 PB_DS_ASSERT_VALID((*this)) 190 191 if (it == end()) 192 return it; 193 iterator ret_it = it; 194 ++ret_it; 195 _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == leaf_node); 196 erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); 197 PB_DS_ASSERT_VALID((*this)) 198 return ret_it; 199} 200#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR 201 202PB_DS_CLASS_T_DEC 203inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator 204PB_DS_CLASS_C_DEC:: 205erase(const_reverse_iterator it) 206{ 207 PB_DS_ASSERT_VALID((*this)) 208 209 if (it.m_p_nd == m_p_head) 210 return it; 211 const_reverse_iterator ret_it = it; 212 ++ret_it; 213 214 _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == leaf_node); 215 erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); 216 PB_DS_ASSERT_VALID((*this)) 217 return ret_it; 218} 219 220#ifdef PB_DS_DATA_TRUE_INDICATOR 221PB_DS_CLASS_T_DEC 222inline typename PB_DS_CLASS_C_DEC::reverse_iterator 223PB_DS_CLASS_C_DEC:: 224erase(reverse_iterator it) 225{ 226 PB_DS_ASSERT_VALID((*this)) 227 228 if (it.m_p_nd == m_p_head) 229 return it; 230 reverse_iterator ret_it = it; 231 ++ret_it; 232 233 _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == leaf_node); 234 erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); 235 PB_DS_ASSERT_VALID((*this)) 236 return ret_it; 237} 238#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR 239 240PB_DS_CLASS_T_DEC 241template<typename Pred> 242inline typename PB_DS_CLASS_C_DEC::size_type 243PB_DS_CLASS_C_DEC:: 244erase_if(Pred pred) 245{ 246 size_type num_ersd = 0; 247 PB_DS_ASSERT_VALID((*this)) 248 249 iterator it = begin(); 250 while (it != end()) 251 { 252 PB_DS_ASSERT_VALID((*this)) 253 if (pred(*it)) 254 { 255 ++num_ersd; 256 it = erase(it); 257 } 258 else 259 ++it; 260 } 261 262 PB_DS_ASSERT_VALID((*this)) 263 return num_ersd; 264} 265 266PB_DS_CLASS_T_DEC 267void 268PB_DS_CLASS_C_DEC:: 269erase_leaf(leaf_pointer p_l) 270{ 271 update_min_max_for_erased_leaf(p_l); 272 if (p_l->m_p_parent->m_type == head_node) 273 { 274 _GLIBCXX_DEBUG_ASSERT(size() == 1); 275 clear(); 276 return; 277 } 278 279 _GLIBCXX_DEBUG_ASSERT(size() > 1); 280 _GLIBCXX_DEBUG_ASSERT(p_l->m_p_parent->m_type == i_node); 281 282 inode_pointer p_parent = static_cast<inode_pointer>(p_l->m_p_parent); 283 284 p_parent->remove_child(p_l); 285 erase_fixup(p_parent); 286 actual_erase_leaf(p_l); 287} 288 289PB_DS_CLASS_T_DEC 290void 291PB_DS_CLASS_C_DEC:: 292update_min_max_for_erased_leaf(leaf_pointer p_l) 293{ 294 if (m_size == 1) 295 { 296 m_p_head->m_p_min = m_p_head; 297 m_p_head->m_p_max = m_p_head; 298 return; 299 } 300 301 if (p_l == static_cast<leaf_const_pointer>(m_p_head->m_p_min)) 302 { 303 iterator it(p_l); 304 ++it; 305 m_p_head->m_p_min = it.m_p_nd; 306 return; 307 } 308 309 if (p_l == static_cast<leaf_const_pointer>(m_p_head->m_p_max)) 310 { 311 iterator it(p_l); 312 --it; 313 m_p_head->m_p_max = it.m_p_nd; 314 } 315} 316