OpenCores
URL https://opencores.org/ocsvn/altor32/altor32/trunk

Subversion Repositories altor32

[/] [altor32/] [trunk/] [gcc-x64/] [or1knd-elf/] [or1knd-elf/] [include/] [c++/] [4.8.0/] [ext/] [pb_ds/] [detail/] [binary_heap_/] [erase_fn_imps.hpp] - Blame information for rev 35

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 35 ultra_embe
// -*- C++ -*-
2
 
3
// Copyright (C) 2005, 2006, 2007, 2008, 2009, 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 binary_heap_/erase_fn_imps.hpp
39
 * Contains an implementation class for a binary_heap.
40
 */
41
 
42
PB_DS_CLASS_T_DEC
43
void
44
PB_DS_CLASS_C_DEC::
45
clear()
46
{
47
  for (size_type i = 0; i < m_size; ++i)
48
    erase_at(m_a_entries, i, s_no_throw_copies_ind);
49
 
50
  __try
51
    {
52
      const size_type new_size = resize_policy::get_new_size_for_arbitrary(0);
53
      entry_pointer new_entries = s_entry_allocator.allocate(new_size);
54
      resize_policy::notify_arbitrary(new_size);
55
      s_entry_allocator.deallocate(m_a_entries, m_actual_size);
56
      m_actual_size = new_size;
57
      m_a_entries = new_entries;
58
    }
59
  __catch(...)
60
    { }
61
 
62
  m_size = 0;
63
  PB_DS_ASSERT_VALID((*this))
64
}
65
 
66
PB_DS_CLASS_T_DEC
67
void
68
PB_DS_CLASS_C_DEC::
69
erase_at(entry_pointer a_entries, size_type i, false_type)
70
{
71
  a_entries[i]->~value_type();
72
  s_value_allocator.deallocate(a_entries[i], 1);
73
}
74
 
75
PB_DS_CLASS_T_DEC
76
void
77
PB_DS_CLASS_C_DEC::
78
erase_at(entry_pointer, size_type, true_type)
79
{ }
80
 
81
PB_DS_CLASS_T_DEC
82
inline void
83
PB_DS_CLASS_C_DEC::
84
pop()
85
{
86
  PB_DS_ASSERT_VALID((*this))
87
  _GLIBCXX_DEBUG_ASSERT(!empty());
88
 
89
  pop_heap();
90
  erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind);
91
  resize_for_erase_if_needed();
92
  _GLIBCXX_DEBUG_ASSERT(m_size > 0);
93
  --m_size;
94
 
95
  PB_DS_ASSERT_VALID((*this))
96
}
97
 
98
PB_DS_CLASS_T_DEC
99
template<typename Pred>
100
typename PB_DS_CLASS_C_DEC::size_type
101
PB_DS_CLASS_C_DEC::
102
erase_if(Pred pred)
103
{
104
  PB_DS_ASSERT_VALID((*this))
105
 
106
  typedef typename entry_pred<value_type, Pred, _Alloc, simple_value>::type
107
    pred_t;
108
 
109
  const size_type left = partition(pred_t(pred));
110
  _GLIBCXX_DEBUG_ASSERT(m_size >= left);
111
  const size_type ersd = m_size - left;
112
  for (size_type i = left; i < m_size; ++i)
113
    erase_at(m_a_entries, i, s_no_throw_copies_ind);
114
 
115
  __try
116
    {
117
      const size_type new_size =
118
        resize_policy::get_new_size_for_arbitrary(left);
119
 
120
      entry_pointer new_entries = s_entry_allocator.allocate(new_size);
121
      std::copy(m_a_entries, m_a_entries + left, new_entries);
122
      s_entry_allocator.deallocate(m_a_entries, m_actual_size);
123
      m_actual_size = new_size;
124
      resize_policy::notify_arbitrary(m_actual_size);
125
    }
126
  __catch(...)
127
    { };
128
 
129
  m_size = left;
130
  make_heap();
131
  PB_DS_ASSERT_VALID((*this))
132
  return ersd;
133
}
134
 
135
PB_DS_CLASS_T_DEC
136
inline void
137
PB_DS_CLASS_C_DEC::
138
erase(point_iterator it)
139
{
140
  PB_DS_ASSERT_VALID((*this))
141
  _GLIBCXX_DEBUG_ASSERT(!empty());
142
 
143
  const size_type fix_pos = it.m_p_e - m_a_entries;
144
  std::swap(*it.m_p_e, m_a_entries[m_size - 1]);
145
  erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind);
146
  resize_for_erase_if_needed();
147
 
148
  _GLIBCXX_DEBUG_ASSERT(m_size > 0);
149
  --m_size;
150
  _GLIBCXX_DEBUG_ASSERT(fix_pos <= m_size);
151
 
152
  if (fix_pos != m_size)
153
    fix(m_a_entries + fix_pos);
154
 
155
  PB_DS_ASSERT_VALID((*this))
156
}
157
 
158
PB_DS_CLASS_T_DEC
159
inline void
160
PB_DS_CLASS_C_DEC::
161
resize_for_erase_if_needed()
162
{
163
  if (!resize_policy::resize_needed_for_shrink(m_size))
164
    return;
165
 
166
  __try
167
    {
168
      const size_type new_size = resize_policy::get_new_size_for_shrink();
169
      entry_pointer new_entries = s_entry_allocator.allocate(new_size);
170
      resize_policy::notify_shrink_resize();
171
 
172
      _GLIBCXX_DEBUG_ASSERT(m_size > 0);
173
      std::copy(m_a_entries, m_a_entries + m_size - 1, new_entries);
174
      s_entry_allocator.deallocate(m_a_entries, m_actual_size);
175
      m_actual_size = new_size;
176
      m_a_entries = new_entries;
177
    }
178
  __catch(...)
179
    { }
180
}
181
 
182
PB_DS_CLASS_T_DEC
183
template<typename Pred>
184
typename PB_DS_CLASS_C_DEC::size_type
185
PB_DS_CLASS_C_DEC::
186
partition(Pred pred)
187
{
188
  size_type left = 0;
189
  size_type right = m_size - 1;
190
 
191
  while (right + 1 != left)
192
    {
193
      _GLIBCXX_DEBUG_ASSERT(left <= m_size);
194
 
195
      if (!pred(m_a_entries[left]))
196
        ++left;
197
      else if (pred(m_a_entries[right]))
198
        --right;
199
      else
200
        {
201
          _GLIBCXX_DEBUG_ASSERT(left < right);
202
          std::swap(m_a_entries[left], m_a_entries[right]);
203
          ++left;
204
          --right;
205
        }
206
    }
207
 
208
  return left;
209
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.