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 ov_tree_map_/erase_fn_imps.hpp 00038 * Contains an implementation class for ov_tree_. 00039 */ 00040 00041 PB_DS_CLASS_T_DEC 00042 void 00043 PB_DS_CLASS_C_DEC:: 00044 clear() 00045 { 00046 PB_DS_ASSERT_VALID((*this)) 00047 if (m_size == 0) 00048 { 00049 return; 00050 } 00051 else 00052 { 00053 reallocate_metadata((node_update* )this, 0); 00054 cond_dtor<size_type> cd(m_a_values, m_end_it, m_size); 00055 } 00056 00057 _GLIBCXX_DEBUG_ONLY(debug_base::clear();) 00058 m_a_values = 0; 00059 m_size = 0; 00060 m_end_it = m_a_values; 00061 PB_DS_ASSERT_VALID((*this)) 00062 } 00063 00064 PB_DS_CLASS_T_DEC 00065 template<typename Pred> 00066 inline typename PB_DS_CLASS_C_DEC::size_type 00067 PB_DS_CLASS_C_DEC:: 00068 erase_if(Pred pred) 00069 { 00070 PB_DS_ASSERT_VALID((*this)) 00071 00072 #ifdef PB_DS_REGRESSION 00073 typename _Alloc::group_adjustor adjust(m_size); 00074 #endif 00075 00076 size_type new_size = 0; 00077 size_type num_val_ersd = 0; 00078 00079 for (iterator source_it = begin(); source_it != m_end_it; ++source_it) 00080 if (!pred(*source_it)) 00081 ++new_size; 00082 else 00083 ++num_val_ersd; 00084 00085 if (new_size == 0) 00086 { 00087 clear(); 00088 return num_val_ersd; 00089 } 00090 00091 value_vector a_new_values = s_value_alloc.allocate(new_size); 00092 iterator target_it = a_new_values; 00093 cond_dtor<size_type> cd(a_new_values, target_it, new_size); 00094 _GLIBCXX_DEBUG_ONLY(debug_base::clear()); 00095 for (iterator source_it = begin(); source_it != m_end_it; ++source_it) 00096 { 00097 if (!pred(*source_it)) 00098 { 00099 new (const_cast<void*>(static_cast<const void*>(target_it))) 00100 value_type(*source_it); 00101 00102 _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(*source_it))); 00103 ++target_it; 00104 } 00105 } 00106 00107 reallocate_metadata((node_update*)this, new_size); 00108 cd.set_no_action(); 00109 00110 { 00111 cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size); 00112 } 00113 00114 m_a_values = a_new_values; 00115 m_size = new_size; 00116 m_end_it = target_it; 00117 update(node_begin(), (node_update*)this); 00118 PB_DS_ASSERT_VALID((*this)) 00119 return num_val_ersd; 00120 } 00121 00122 PB_DS_CLASS_T_DEC 00123 template<typename It> 00124 It 00125 PB_DS_CLASS_C_DEC:: 00126 erase_imp(It it) 00127 { 00128 PB_DS_ASSERT_VALID((*this)) 00129 if (it == end()) 00130 return end(); 00131 00132 PB_DS_CHECK_KEY_EXISTS(PB_DS_V2F(*it)) 00133 00134 #ifdef PB_DS_REGRESSION 00135 typename _Alloc::group_adjustor adjust(m_size); 00136 #endif 00137 00138 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 00139 value_vector a_values = s_value_alloc.allocate(m_size - 1); 00140 iterator source_it = begin(); 00141 iterator source_end_it = end(); 00142 iterator target_it = a_values; 00143 iterator ret_it = end(); 00144 00145 cond_dtor<size_type> cd(a_values, target_it, m_size - 1); 00146 00147 _GLIBCXX_DEBUG_ONLY(size_type cnt = 0;) 00148 00149 while (source_it != source_end_it) 00150 { 00151 if (source_it != it) 00152 { 00153 _GLIBCXX_DEBUG_ONLY(++cnt;) 00154 _GLIBCXX_DEBUG_ASSERT(cnt != m_size); 00155 new (const_cast<void*>(static_cast<const void*>(target_it))) 00156 value_type(*source_it); 00157 00158 ++target_it; 00159 } 00160 else 00161 ret_it = target_it; 00162 ++source_it; 00163 } 00164 00165 _GLIBCXX_DEBUG_ASSERT(m_size > 0); 00166 reallocate_metadata((node_update*)this, m_size - 1); 00167 cd.set_no_action(); 00168 _GLIBCXX_DEBUG_ONLY(debug_base::erase_existing(PB_DS_V2F(*it));) 00169 { 00170 cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size); 00171 } 00172 00173 m_a_values = a_values; 00174 --m_size; 00175 m_end_it = m_a_values + m_size; 00176 update(node_begin(), (node_update*)this); 00177 PB_DS_ASSERT_VALID((*this)) 00178 return It(ret_it); 00179 } 00180 00181 PB_DS_CLASS_T_DEC 00182 bool 00183 PB_DS_CLASS_C_DEC:: 00184 erase(key_const_reference r_key) 00185 { 00186 point_iterator it = find(r_key); 00187 if (it == end()) 00188 return false; 00189 erase(it); 00190 return true; 00191 }