libstdc++
split_join_fn_imps.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005-2015 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 binary_heap_/split_join_fn_imps.hpp
00038  * Contains an implementation class for a binary_heap.
00039  */
00040 
00041 PB_DS_CLASS_T_DEC
00042 template<typename Pred>
00043 void
00044 PB_DS_CLASS_C_DEC::
00045 split(Pred pred, PB_DS_CLASS_C_DEC& other)
00046 {
00047   PB_DS_ASSERT_VALID((*this))
00048 
00049   typedef
00050     typename entry_pred<value_type, Pred, _Alloc, simple_value>::type
00051     pred_t;
00052 
00053   const size_type left = partition(pred_t(pred));
00054   _GLIBCXX_DEBUG_ASSERT(m_size >= left);
00055 
00056   const size_type ersd = m_size - left;
00057   _GLIBCXX_DEBUG_ASSERT(m_size >= ersd);
00058 
00059   const size_type new_size = resize_policy::get_new_size_for_arbitrary(left);
00060   const size_type other_actual_size = other.get_new_size_for_arbitrary(ersd);
00061 
00062   entry_pointer a_entries = 0;
00063   entry_pointer a_other_entries = 0;
00064 
00065   __try
00066     {
00067       a_entries = s_entry_allocator.allocate(new_size);
00068       a_other_entries = s_entry_allocator.allocate(other_actual_size);
00069     }
00070   __catch(...)
00071     {
00072       if (a_entries != 0)
00073         s_entry_allocator.deallocate(a_entries, new_size);
00074 
00075       if (a_other_entries != 0)
00076         s_entry_allocator.deallocate(a_other_entries, other_actual_size);
00077 
00078       __throw_exception_again;
00079     };
00080 
00081   for (size_type i = 0; i < other.m_size; ++i)
00082     erase_at(other.m_a_entries, i, s_no_throw_copies_ind);
00083 
00084   _GLIBCXX_DEBUG_ASSERT(new_size >= left);
00085   std::copy(m_a_entries, m_a_entries + left, a_entries);
00086   std::copy(m_a_entries + left, m_a_entries + m_size, a_other_entries);
00087 
00088   s_entry_allocator.deallocate(m_a_entries, m_actual_size);
00089   s_entry_allocator.deallocate(other.m_a_entries, other.m_actual_size);
00090 
00091   m_actual_size = new_size;
00092   other.m_actual_size = other_actual_size;
00093 
00094   m_size = left;
00095   other.m_size = ersd;
00096 
00097   m_a_entries = a_entries;
00098   other.m_a_entries = a_other_entries;
00099 
00100   make_heap();
00101   other.make_heap();
00102 
00103   resize_policy::notify_arbitrary(m_actual_size);
00104   other.notify_arbitrary(other.m_actual_size);
00105 
00106   PB_DS_ASSERT_VALID((*this))
00107   PB_DS_ASSERT_VALID(other)
00108 }
00109 
00110 PB_DS_CLASS_T_DEC
00111 inline void
00112 PB_DS_CLASS_C_DEC::
00113 join(PB_DS_CLASS_C_DEC& other)
00114 {
00115   PB_DS_ASSERT_VALID((*this))
00116   PB_DS_ASSERT_VALID(other)
00117 
00118   const size_type len = m_size + other.m_size;
00119   const size_type new_size = resize_policy::get_new_size_for_arbitrary(len);
00120 
00121   entry_pointer a_entries = 0;
00122   entry_pointer a_other_entries = 0;
00123 
00124   __try
00125     {
00126       a_entries = s_entry_allocator.allocate(new_size);
00127       a_other_entries = s_entry_allocator.allocate(resize_policy::min_size);
00128     }
00129   __catch(...)
00130     {
00131       if (a_entries != 0)
00132         s_entry_allocator.deallocate(a_entries, new_size);
00133 
00134       if (a_other_entries != 0)
00135         s_entry_allocator.deallocate(a_other_entries, resize_policy::min_size);
00136 
00137       __throw_exception_again;
00138     }
00139 
00140   std::copy(m_a_entries, m_a_entries + m_size, a_entries);
00141   std::copy(other.m_a_entries, other.m_a_entries + other.m_size,
00142             a_entries + m_size);
00143 
00144   s_entry_allocator.deallocate(m_a_entries, m_actual_size);
00145   m_a_entries = a_entries;
00146   m_size = len;
00147   m_actual_size = new_size;
00148   resize_policy::notify_arbitrary(new_size);
00149   make_heap();
00150 
00151   s_entry_allocator.deallocate(other.m_a_entries, other.m_actual_size);
00152   other.m_a_entries = a_other_entries;
00153   other.m_size = 0;
00154   other.m_actual_size = resize_policy::min_size;
00155   other.notify_arbitrary(resize_policy::min_size);
00156   other.make_heap();
00157   
00158   PB_DS_ASSERT_VALID((*this))
00159   PB_DS_ASSERT_VALID(other)
00160 }