libstdc++
ov_tree_map_/erase_fn_imps.hpp
Go to the documentation of this file.
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 }