1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2013 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 41 PB_DS_CLASS_T_DEC 42 inline bool 43 PB_DS_CLASS_C_DEC:: 44 erase(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 66 PB_DS_CLASS_T_DEC 67 void 68 PB_DS_CLASS_C_DEC:: 69 erase_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 113 PB_DS_CLASS_T_DEC 114 inline void 115 PB_DS_CLASS_C_DEC:: 116 actual_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 125 PB_DS_CLASS_T_DEC 126 void 127 PB_DS_CLASS_C_DEC:: 128 clear() 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 140 PB_DS_CLASS_T_DEC 141 void 142 PB_DS_CLASS_C_DEC:: 143 clear_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 165 PB_DS_CLASS_T_DEC 166 inline typename PB_DS_CLASS_C_DEC::const_iterator 167 PB_DS_CLASS_C_DEC:: 168 erase(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 184 PB_DS_CLASS_T_DEC 185 inline typename PB_DS_CLASS_C_DEC::iterator 186 PB_DS_CLASS_C_DEC:: 187 erase(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 202 PB_DS_CLASS_T_DEC 203 inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator 204 PB_DS_CLASS_C_DEC:: 205 erase(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 221 PB_DS_CLASS_T_DEC 222 inline typename PB_DS_CLASS_C_DEC::reverse_iterator 223 PB_DS_CLASS_C_DEC:: 224 erase(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 240 PB_DS_CLASS_T_DEC 241 template<typename Pred> 242 inline typename PB_DS_CLASS_C_DEC::size_type 243 PB_DS_CLASS_C_DEC:: 244 erase_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 266 PB_DS_CLASS_T_DEC 267 void 268 PB_DS_CLASS_C_DEC:: 269 erase_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 289 PB_DS_CLASS_T_DEC 290 void 291 PB_DS_CLASS_C_DEC:: 292 update_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
