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_/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 }