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