libstdc++
pat_trie_/constructors_destructor_fn_imps.hpp
Go to the documentation of this file.
00001  // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the terms
00008 // of the GNU General Public License as published by the Free Software
00009 // Foundation; either version 3, or (at your option) any later
00010 // version.
00011 
00012 // This library is distributed in the hope that it will be useful, but
00013 // WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015 // General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00027 
00028 // Permission to use, copy, modify, sell, and distribute this software
00029 // is hereby granted without fee, provided that the above copyright
00030 // notice appears in all copies, and that both that copyright notice
00031 // and this permission notice appear in supporting documentation. None
00032 // of the above authors, nor IBM Haifa Research Laboratories, make any
00033 // representation about the suitability of this software for any
00034 // purpose. It is provided "as is" without express or implied
00035 // warranty.
00036 
00037 /**
00038  * @file pat_trie_/constructors_destructor_fn_imps.hpp
00039  * Contains an implementation class for pat_trie.
00040  */
00041 
00042 PB_DS_CLASS_T_DEC
00043 typename PB_DS_CLASS_C_DEC::head_allocator
00044 PB_DS_CLASS_C_DEC::s_head_allocator;
00045 
00046 PB_DS_CLASS_T_DEC
00047 typename PB_DS_CLASS_C_DEC::inode_allocator
00048 PB_DS_CLASS_C_DEC::s_inode_allocator;
00049 
00050 PB_DS_CLASS_T_DEC
00051 typename PB_DS_CLASS_C_DEC::leaf_allocator
00052 PB_DS_CLASS_C_DEC::s_leaf_allocator;
00053 
00054 PB_DS_CLASS_T_DEC
00055 PB_DS_CLASS_C_DEC::
00056 PB_DS_PAT_TRIE_NAME() :
00057   m_p_head(s_head_allocator.allocate(1)),
00058   m_size(0)
00059 {
00060   initialize();
00061   PB_DS_ASSERT_VALID((*this))
00062 }
00063 
00064 PB_DS_CLASS_T_DEC
00065 PB_DS_CLASS_C_DEC::
00066 PB_DS_PAT_TRIE_NAME(const access_traits& r_access_traits) :
00067   synth_access_traits(r_access_traits),
00068   m_p_head(s_head_allocator.allocate(1)),
00069   m_size(0)
00070 {
00071   initialize();
00072   PB_DS_ASSERT_VALID((*this))
00073 }
00074 
00075 PB_DS_CLASS_T_DEC
00076 PB_DS_CLASS_C_DEC::
00077 PB_DS_PAT_TRIE_NAME(const PB_DS_CLASS_C_DEC& other) :
00078 #ifdef _GLIBCXX_DEBUG
00079   debug_base(other),
00080 #endif
00081   synth_access_traits(other),
00082   node_update(other),
00083   m_p_head(s_head_allocator.allocate(1)),
00084   m_size(0)
00085 {
00086   initialize();
00087   m_size = other.m_size;
00088   PB_DS_ASSERT_VALID(other)
00089     if (other.m_p_head->m_p_parent == 0)
00090       {
00091     PB_DS_ASSERT_VALID((*this))
00092     return;
00093       }
00094   __try
00095     {
00096       m_p_head->m_p_parent = recursive_copy_node(other.m_p_head->m_p_parent);
00097     }
00098   __catch(...)
00099     {
00100       s_head_allocator.deallocate(m_p_head, 1);
00101       __throw_exception_again;
00102     }
00103 
00104   m_p_head->m_p_min = leftmost_descendant(m_p_head->m_p_parent);
00105   m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent);
00106   m_p_head->m_p_parent->m_p_parent = m_p_head;
00107   PB_DS_ASSERT_VALID((*this))
00108 }
00109 
00110 PB_DS_CLASS_T_DEC
00111 void
00112 PB_DS_CLASS_C_DEC::
00113 swap(PB_DS_CLASS_C_DEC& other)
00114 {
00115   PB_DS_ASSERT_VALID((*this))
00116   PB_DS_ASSERT_VALID(other)
00117   value_swap(other);
00118   std::swap((access_traits& )(*this), (access_traits& )other);
00119   PB_DS_ASSERT_VALID((*this))
00120   PB_DS_ASSERT_VALID(other)
00121 }
00122 
00123 PB_DS_CLASS_T_DEC
00124 void
00125 PB_DS_CLASS_C_DEC::
00126 value_swap(PB_DS_CLASS_C_DEC& other)
00127 {
00128   _GLIBCXX_DEBUG_ONLY(debug_base::swap(other);)
00129   std::swap(m_p_head, other.m_p_head);
00130   std::swap(m_size, other.m_size);
00131 }
00132 
00133 PB_DS_CLASS_T_DEC
00134 PB_DS_CLASS_C_DEC::
00135 ~PB_DS_PAT_TRIE_NAME()
00136 {
00137   clear();
00138   s_head_allocator.deallocate(m_p_head, 1);
00139 }
00140 
00141 PB_DS_CLASS_T_DEC
00142 void
00143 PB_DS_CLASS_C_DEC::
00144 initialize()
00145 {
00146   new (m_p_head) head();
00147   m_p_head->m_p_parent = 0;
00148   m_p_head->m_p_min = m_p_head;
00149   m_p_head->m_p_max = m_p_head;
00150   m_size = 0;
00151 }
00152 
00153 PB_DS_CLASS_T_DEC
00154 template<typename It>
00155 void
00156 PB_DS_CLASS_C_DEC::
00157 copy_from_range(It first_it, It last_it)
00158 {
00159   while (first_it != last_it)
00160     insert(*(first_it++));
00161 }
00162 
00163 PB_DS_CLASS_T_DEC
00164 typename PB_DS_CLASS_C_DEC::node_pointer
00165 PB_DS_CLASS_C_DEC::
00166 recursive_copy_node(node_const_pointer p_ncp)
00167 {
00168   _GLIBCXX_DEBUG_ASSERT(p_ncp != 0);
00169   if (p_ncp->m_type == leaf_node)
00170     {
00171       leaf_const_pointer p_other_lf = static_cast<leaf_const_pointer>(p_ncp);
00172       leaf_pointer p_new_lf = s_leaf_allocator.allocate(1);
00173       cond_dealtor cond(p_new_lf);
00174       new (p_new_lf) leaf(p_other_lf->value());
00175       apply_update(p_new_lf, (node_update*)this);
00176       cond.set_no_action_dtor();
00177       return (p_new_lf);
00178     }
00179 
00180   _GLIBCXX_DEBUG_ASSERT(p_ncp->m_type == i_node);
00181   node_pointer a_p_children[inode::arr_size];
00182   size_type child_i = 0;
00183   inode_const_pointer p_icp = static_cast<inode_const_pointer>(p_ncp);
00184 
00185   typename inode::const_iterator child_it = p_icp->begin();
00186 
00187   inode_pointer p_ret;
00188   __try
00189     {
00190       while (child_it != p_icp->end())
00191     a_p_children[child_i++] = recursive_copy_node(*(child_it++));
00192       p_ret = s_inode_allocator.allocate(1);
00193     }
00194   __catch(...)
00195     {
00196       while (child_i-- > 0)
00197     clear_imp(a_p_children[child_i]);
00198       __throw_exception_again;
00199     }
00200 
00201   new (p_ret) inode(p_icp->get_e_ind(), pref_begin(a_p_children[0]));
00202 
00203   --child_i;
00204   _GLIBCXX_DEBUG_ASSERT(child_i >= 1);
00205   do
00206     p_ret->add_child(a_p_children[child_i], pref_begin(a_p_children[child_i]),
00207              pref_end(a_p_children[child_i]), this);
00208   while (child_i-- > 0);
00209   apply_update(p_ret, (node_update*)this);
00210   return p_ret;
00211 }