libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/split_join_fn_imps.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the terms
   8 // of the GNU General Public License as published by the Free Software
   9 // Foundation; either version 3, or (at your option) any later
  10 // version.
  11
  12 // This library is distributed in the hope that it will be useful, but
  13 // WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 // General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  27
  28 // Permission to use, copy, modify, sell, and distribute this software
  29 // is hereby granted without fee, provided that the above copyright
  30 // notice appears in all copies, and that both that copyright notice
  31 // and this permission notice appear in supporting documentation. None
  32 // of the above authors, nor IBM Haifa Research Laboratories, make any
  33 // representation about the suitability of this software for any
  34 // purpose. It is provided "as is" without express or implied
  35 // warranty.
  36
  37 /**
  38  * @file split_join_fn_imps.hpp
  39  * Contains an implementation class for a binary_heap.
  40  */
  41
  42 PB_DS_CLASS_T_DEC
  43 template<typename Pred>
  44 void
  45 PB_DS_CLASS_C_DEC::
  46 split(Pred pred, PB_DS_CLASS_C_DEC& other)
  47 {
  48   PB_DS_ASSERT_VALID((*this))
  49
  50   typedef
  51     typename entry_pred<
  52     value_type,
  53     Pred,
  54     simple_value,
  55     Allocator>::type
  56     pred_t;
  57
  58   const size_type left = partition(pred_t(pred));
  59
  60   _GLIBCXX_DEBUG_ASSERT(m_size >= left);
  61
  62   const size_type ersd = m_size - left;
  63
  64   _GLIBCXX_DEBUG_ASSERT(m_size >= ersd);
  65
  66   const size_type actual_size =
  67     resize_policy::get_new_size_for_arbitrary(left);
  68
  69   const size_type other_actual_size =
  70     other.get_new_size_for_arbitrary(ersd);
  71
  72   entry_pointer a_entries = 0;
  73   entry_pointer a_other_entries = 0;
  74
  75   __try
  76     {
  77       a_entries = s_entry_allocator.allocate(actual_size);
  78
  79       a_other_entries = s_entry_allocator.allocate(other_actual_size);
  80     }
  81   __catch(...)
  82     {
  83       if (a_entries != 0)
  84         s_entry_allocator.deallocate(a_entries, actual_size);
  85
  86       if (a_other_entries != 0)
  87         s_entry_allocator.deallocate(a_other_entries, other_actual_size);
  88
  89       __throw_exception_again;
  90     };
  91
  92   for (size_type i = 0; i < other.m_size; ++i)
  93     erase_at(other.m_a_entries, i, s_no_throw_copies_ind);
  94
  95   _GLIBCXX_DEBUG_ASSERT(actual_size >= left);
  96   std::copy(m_a_entries, m_a_entries + left, a_entries);
  97   std::copy(m_a_entries + left, m_a_entries + m_size, a_other_entries);
  98
  99   s_entry_allocator.deallocate(m_a_entries, m_actual_size);
 100   s_entry_allocator.deallocate(other.m_a_entries, other.m_actual_size);
 101
 102   m_actual_size = actual_size;
 103   other.m_actual_size = other_actual_size;
 104
 105   m_size = left;
 106   other.m_size = ersd;
 107
 108   m_a_entries = a_entries;
 109   other.m_a_entries = a_other_entries;
 110
 111   std::make_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this));
 112   std::make_heap(other.m_a_entries, other.m_a_entries + other.m_size, static_cast<entry_cmp& >(other));
 113
 114   resize_policy::notify_arbitrary(m_actual_size);
 115   other.notify_arbitrary(other.m_actual_size);
 116
 117   PB_DS_ASSERT_VALID((*this))
 118   PB_DS_ASSERT_VALID(other)
 119 }
 120
 121 PB_DS_CLASS_T_DEC
 122 inline void
 123 PB_DS_CLASS_C_DEC::
 124 join(PB_DS_CLASS_C_DEC& other)
 125 {
 126   PB_DS_ASSERT_VALID((*this))
 127   PB_DS_ASSERT_VALID(other)
 128
 129   const size_type len = m_size + other.m_size;
 130   const size_type actual_size = resize_policy::get_new_size_for_arbitrary(len);
 131
 132   entry_pointer a_entries = 0;
 133   entry_pointer a_other_entries = 0;
 134
 135   __try
 136     {
 137       a_entries = s_entry_allocator.allocate(actual_size);
 138       a_other_entries = s_entry_allocator.allocate(resize_policy::min_size);
 139     }
 140   __catch(...)
 141     {
 142       if (a_entries != 0)
 143         s_entry_allocator.deallocate(a_entries, actual_size);
 144
 145       if (a_other_entries != 0)
 146         s_entry_allocator.deallocate(a_other_entries, resize_policy::min_size);
 147
 148       __throw_exception_again;
 149     }
 150
 151   std::copy(m_a_entries, m_a_entries + m_size, a_entries);
 152   std::copy(other.m_a_entries, other.m_a_entries + other.m_size, a_entries + m_size);
 153
 154   s_entry_allocator.deallocate(m_a_entries, m_actual_size);
 155   m_a_entries = a_entries;
 156   m_size = len;
 157   m_actual_size = actual_size;
 158
 159   resize_policy::notify_arbitrary(actual_size);
 160
 161   std::make_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this));
 162
 163   s_entry_allocator.deallocate(other.m_a_entries, other.m_actual_size);
 164   other.m_a_entries = a_other_entries;
 165   other.m_size = 0;
 166   other.m_actual_size = resize_policy::min_size;
 167
 168   other.notify_arbitrary(resize_policy::min_size);
 169
 170   PB_DS_ASSERT_VALID((*this))
 171   PB_DS_ASSERT_VALID(other)
 172 }
 173