libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005-2013 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 pat_trie_/constructors_destructor_fn_imps.hpp 00038 * Contains an implementation class for pat_trie. 00039 */ 00040 00041 PB_DS_CLASS_T_DEC 00042 typename PB_DS_CLASS_C_DEC::head_allocator 00043 PB_DS_CLASS_C_DEC::s_head_allocator; 00044 00045 PB_DS_CLASS_T_DEC 00046 typename PB_DS_CLASS_C_DEC::inode_allocator 00047 PB_DS_CLASS_C_DEC::s_inode_allocator; 00048 00049 PB_DS_CLASS_T_DEC 00050 typename PB_DS_CLASS_C_DEC::leaf_allocator 00051 PB_DS_CLASS_C_DEC::s_leaf_allocator; 00052 00053 PB_DS_CLASS_T_DEC 00054 PB_DS_CLASS_C_DEC:: 00055 PB_DS_PAT_TRIE_NAME() : 00056 m_p_head(s_head_allocator.allocate(1)), 00057 m_size(0) 00058 { 00059 initialize(); 00060 PB_DS_ASSERT_VALID((*this)) 00061 } 00062 00063 PB_DS_CLASS_T_DEC 00064 PB_DS_CLASS_C_DEC:: 00065 PB_DS_PAT_TRIE_NAME(const access_traits& r_access_traits) : 00066 synth_access_traits(r_access_traits), 00067 m_p_head(s_head_allocator.allocate(1)), 00068 m_size(0) 00069 { 00070 initialize(); 00071 PB_DS_ASSERT_VALID((*this)) 00072 } 00073 00074 PB_DS_CLASS_T_DEC 00075 PB_DS_CLASS_C_DEC:: 00076 PB_DS_PAT_TRIE_NAME(const PB_DS_CLASS_C_DEC& other) : 00077 #ifdef _GLIBCXX_DEBUG 00078 debug_base(other), 00079 #endif 00080 synth_access_traits(other), 00081 node_update(other), 00082 m_p_head(s_head_allocator.allocate(1)), 00083 m_size(0) 00084 { 00085 initialize(); 00086 m_size = other.m_size; 00087 PB_DS_ASSERT_VALID(other) 00088 if (other.m_p_head->m_p_parent == 0) 00089 { 00090 PB_DS_ASSERT_VALID((*this)) 00091 return; 00092 } 00093 __try 00094 { 00095 m_p_head->m_p_parent = recursive_copy_node(other.m_p_head->m_p_parent); 00096 } 00097 __catch(...) 00098 { 00099 s_head_allocator.deallocate(m_p_head, 1); 00100 __throw_exception_again; 00101 } 00102 00103 m_p_head->m_p_min = leftmost_descendant(m_p_head->m_p_parent); 00104 m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent); 00105 m_p_head->m_p_parent->m_p_parent = m_p_head; 00106 PB_DS_ASSERT_VALID((*this)) 00107 } 00108 00109 PB_DS_CLASS_T_DEC 00110 void 00111 PB_DS_CLASS_C_DEC:: 00112 swap(PB_DS_CLASS_C_DEC& other) 00113 { 00114 PB_DS_ASSERT_VALID((*this)) 00115 PB_DS_ASSERT_VALID(other) 00116 value_swap(other); 00117 std::swap((access_traits& )(*this), (access_traits& )other); 00118 PB_DS_ASSERT_VALID((*this)) 00119 PB_DS_ASSERT_VALID(other) 00120 } 00121 00122 PB_DS_CLASS_T_DEC 00123 void 00124 PB_DS_CLASS_C_DEC:: 00125 value_swap(PB_DS_CLASS_C_DEC& other) 00126 { 00127 _GLIBCXX_DEBUG_ONLY(debug_base::swap(other);) 00128 std::swap(m_p_head, other.m_p_head); 00129 std::swap(m_size, other.m_size); 00130 } 00131 00132 PB_DS_CLASS_T_DEC 00133 PB_DS_CLASS_C_DEC:: 00134 ~PB_DS_PAT_TRIE_NAME() 00135 { 00136 clear(); 00137 s_head_allocator.deallocate(m_p_head, 1); 00138 } 00139 00140 PB_DS_CLASS_T_DEC 00141 void 00142 PB_DS_CLASS_C_DEC:: 00143 initialize() 00144 { 00145 new (m_p_head) head(); 00146 m_p_head->m_p_parent = 0; 00147 m_p_head->m_p_min = m_p_head; 00148 m_p_head->m_p_max = m_p_head; 00149 m_size = 0; 00150 } 00151 00152 PB_DS_CLASS_T_DEC 00153 template<typename It> 00154 void 00155 PB_DS_CLASS_C_DEC:: 00156 copy_from_range(It first_it, It last_it) 00157 { 00158 while (first_it != last_it) 00159 insert(*(first_it++)); 00160 } 00161 00162 PB_DS_CLASS_T_DEC 00163 typename PB_DS_CLASS_C_DEC::node_pointer 00164 PB_DS_CLASS_C_DEC:: 00165 recursive_copy_node(node_const_pointer p_ncp) 00166 { 00167 _GLIBCXX_DEBUG_ASSERT(p_ncp != 0); 00168 if (p_ncp->m_type == leaf_node) 00169 { 00170 leaf_const_pointer p_other_lf = static_cast<leaf_const_pointer>(p_ncp); 00171 leaf_pointer p_new_lf = s_leaf_allocator.allocate(1); 00172 cond_dealtor cond(p_new_lf); 00173 new (p_new_lf) leaf(p_other_lf->value()); 00174 apply_update(p_new_lf, (node_update*)this); 00175 cond.set_no_action_dtor(); 00176 return (p_new_lf); 00177 } 00178 00179 _GLIBCXX_DEBUG_ASSERT(p_ncp->m_type == i_node); 00180 node_pointer a_p_children[inode::arr_size]; 00181 size_type child_i = 0; 00182 inode_const_pointer p_icp = static_cast<inode_const_pointer>(p_ncp); 00183 00184 typename inode::const_iterator child_it = p_icp->begin(); 00185 00186 inode_pointer p_ret; 00187 __try 00188 { 00189 while (child_it != p_icp->end()) 00190 { 00191 a_p_children[child_i] = recursive_copy_node(*(child_it)); 00192 child_i++; 00193 child_it++; 00194 } 00195 p_ret = s_inode_allocator.allocate(1); 00196 } 00197 __catch(...) 00198 { 00199 while (child_i-- > 0) 00200 clear_imp(a_p_children[child_i]); 00201 __throw_exception_again; 00202 } 00203 00204 new (p_ret) inode(p_icp->get_e_ind(), pref_begin(a_p_children[0])); 00205 00206 --child_i; 00207 _GLIBCXX_DEBUG_ASSERT(child_i >= 1); 00208 do 00209 p_ret->add_child(a_p_children[child_i], pref_begin(a_p_children[child_i]), 00210 pref_end(a_p_children[child_i]), this); 00211 while (child_i-- > 0); 00212 apply_update(p_ret, (node_update*)this); 00213 return p_ret; 00214 }