libstdc++
ov_tree_map_/constructors_destructor_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_/constructors_destructor_fn_imps.hpp
00038  * Contains an implementation class for ov_tree_.
00039  */
00040 
00041 PB_DS_CLASS_T_DEC
00042 typename PB_DS_CLASS_C_DEC::value_allocator
00043 PB_DS_CLASS_C_DEC::s_value_alloc;
00044 
00045 PB_DS_CLASS_T_DEC
00046 typename PB_DS_CLASS_C_DEC::metadata_allocator
00047 PB_DS_CLASS_C_DEC::s_metadata_alloc;
00048 
00049 PB_DS_CLASS_T_DEC
00050 PB_DS_CLASS_C_DEC::
00051 PB_DS_OV_TREE_NAME() :
00052   m_a_values(0),
00053   m_a_metadata(0),
00054   m_end_it(0),
00055   m_size(0)
00056 { PB_DS_ASSERT_VALID((*this)) }
00057 
00058 PB_DS_CLASS_T_DEC
00059 PB_DS_CLASS_C_DEC::
00060 PB_DS_OV_TREE_NAME(const Cmp_Fn& r_cmp_fn) :
00061   cmp_fn(r_cmp_fn),
00062   m_a_values(0),
00063   m_a_metadata(0),
00064   m_end_it(0),
00065   m_size(0)
00066 { PB_DS_ASSERT_VALID((*this)) }
00067 
00068 PB_DS_CLASS_T_DEC
00069 PB_DS_CLASS_C_DEC::
00070 PB_DS_OV_TREE_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_nodeu) :
00071   cmp_fn(r_cmp_fn),
00072   node_update(r_nodeu),
00073   m_a_values(0),
00074   m_a_metadata(0),
00075   m_end_it(0),
00076   m_size(0)
00077 { PB_DS_ASSERT_VALID((*this)) }
00078 
00079 PB_DS_CLASS_T_DEC
00080 PB_DS_CLASS_C_DEC::
00081 PB_DS_OV_TREE_NAME(const PB_DS_CLASS_C_DEC& other) :
00082 #ifdef PB_DS_TREE_TRACE
00083   trace_base(other),
00084 #endif
00085   cmp_fn(other),
00086   node_update(other),
00087   m_a_values(0),
00088   m_a_metadata(0),
00089   m_end_it(0),
00090   m_size(0)
00091 {
00092   copy_from_ordered_range(other.begin(), other.end());
00093   PB_DS_ASSERT_VALID((*this))
00094 }
00095 
00096 PB_DS_CLASS_T_DEC
00097 template<typename It>
00098 inline void
00099 PB_DS_CLASS_C_DEC::
00100 copy_from_range(It first_it, It last_it)
00101 {
00102 #ifdef PB_DS_DATA_TRUE_INDICATOR
00103   typedef std::map<key_type, mapped_type, Cmp_Fn,
00104            typename _Alloc::template rebind<value_type>::other>
00105     map_type;
00106 #else
00107   typedef std::set<key_type, Cmp_Fn,
00108            typename _Alloc::template rebind<Key>::other>
00109     map_type;
00110 #endif
00111 
00112   map_type m(first_it, last_it);
00113   copy_from_ordered_range(m.begin(), m.end());
00114   PB_DS_ASSERT_VALID((*this))
00115 }
00116 
00117 PB_DS_CLASS_T_DEC
00118 template<typename It>
00119 void
00120 PB_DS_CLASS_C_DEC::
00121 copy_from_ordered_range(It first_it, It last_it)
00122 {
00123   const size_type len = std::distance(first_it, last_it);
00124   if (len == 0)
00125     return;
00126 
00127   value_vector a_values = s_value_alloc.allocate(len);
00128   iterator target_it = a_values;
00129   It source_it = first_it;
00130   It source_end_it = last_it;
00131 
00132   cond_dtor<size_type> cd(a_values, target_it, len);
00133   while (source_it != source_end_it)
00134     {
00135       void* __v = const_cast<void*>(static_cast<const void*>(target_it));
00136       new (__v) value_type(*source_it++);
00137       ++target_it;
00138     }
00139 
00140   reallocate_metadata((node_update*)this, len);
00141   cd.set_no_action();
00142   m_a_values = a_values;
00143   m_size = len;
00144   m_end_it = m_a_values + m_size;
00145   update(PB_DS_node_begin_imp(), (node_update*)this);
00146 
00147 #ifdef _GLIBCXX_DEBUG
00148   for (const_iterator dbg_it = m_a_values; dbg_it != m_end_it; ++dbg_it)
00149     debug_base::insert_new(PB_DS_V2F(*dbg_it));
00150 #endif
00151 }
00152 
00153 PB_DS_CLASS_T_DEC
00154 template<typename It>
00155 void
00156 PB_DS_CLASS_C_DEC::
00157 copy_from_ordered_range(It first_it, It last_it, It other_first_it,
00158             It other_last_it)
00159 {
00160   clear();
00161   const size_type len = std::distance(first_it, last_it)
00162                  + std::distance(other_first_it, other_last_it);
00163 
00164   value_vector a_values = s_value_alloc.allocate(len);
00165 
00166   iterator target_it = a_values;
00167   It source_it = first_it;
00168   It source_end_it = last_it;
00169 
00170   cond_dtor<size_type> cd(a_values, target_it, len);
00171   while (source_it != source_end_it)
00172     {
00173       new (const_cast<void* >(static_cast<const void* >(target_it)))
00174     value_type(*source_it++);
00175       ++target_it;
00176     }
00177 
00178   source_it = other_first_it;
00179   source_end_it = other_last_it;
00180 
00181   while (source_it != source_end_it)
00182     {
00183       new (const_cast<void* >(static_cast<const void* >(target_it)))
00184     value_type(*source_it++);
00185       ++target_it;
00186     }
00187 
00188   reallocate_metadata((node_update* )this, len);
00189   cd.set_no_action();
00190   m_a_values = a_values;
00191   m_size = len;
00192   m_end_it = m_a_values + m_size;
00193   update(PB_DS_node_begin_imp(), (node_update* )this);
00194 
00195 #ifdef _GLIBCXX_DEBUG
00196   for (const_iterator dbg_it = m_a_values; dbg_it != m_end_it; ++dbg_it)
00197     debug_base::insert_new(PB_DS_V2F(*dbg_it));
00198 #endif
00199 }
00200 
00201 PB_DS_CLASS_T_DEC
00202 void
00203 PB_DS_CLASS_C_DEC::
00204 swap(PB_DS_CLASS_C_DEC& other)
00205 {
00206   PB_DS_ASSERT_VALID((*this))
00207   PB_DS_ASSERT_VALID(other)
00208   value_swap(other);
00209   std::swap(static_cast<cmp_fn&>(*this),
00210         static_cast<cmp_fn&>(other));
00211   std::swap(static_cast<traits_base&>(*this),
00212         static_cast<traits_base&>(other));
00213   PB_DS_ASSERT_VALID(other)
00214   PB_DS_ASSERT_VALID((*this))
00215 }
00216 
00217 PB_DS_CLASS_T_DEC
00218 void
00219 PB_DS_CLASS_C_DEC::
00220 value_swap(PB_DS_CLASS_C_DEC& other)
00221 {
00222   _GLIBCXX_DEBUG_ONLY(debug_base::swap(other);)
00223   std::swap(m_a_values, other.m_a_values);
00224   std::swap(m_a_metadata, other.m_a_metadata);
00225   std::swap(m_size, other.m_size);
00226   std::swap(m_end_it, other.m_end_it);
00227 }
00228 
00229 PB_DS_CLASS_T_DEC
00230 PB_DS_CLASS_C_DEC::
00231 ~PB_DS_OV_TREE_NAME()
00232 {
00233   PB_DS_ASSERT_VALID((*this))
00234   cond_dtor<size_type> cd(m_a_values, m_end_it, m_size);
00235   reallocate_metadata((node_update*)this, 0);
00236 }
00237 
00238 PB_DS_CLASS_T_DEC
00239 inline void
00240 PB_DS_CLASS_C_DEC::
00241 update(node_iterator, null_node_update_pointer)
00242 { }
00243 
00244 PB_DS_CLASS_T_DEC
00245 template<typename Node_Update>
00246 void
00247 PB_DS_CLASS_C_DEC::
00248 update(node_iterator nd_it, Node_Update* p_update)
00249 {
00250   node_const_iterator end_it = PB_DS_node_end_imp();
00251   if (nd_it != end_it)
00252     {
00253       update(nd_it.get_l_child(), p_update);
00254       update(nd_it.get_r_child(), p_update);
00255       node_update::operator()(nd_it, end_it);
00256     }
00257 }