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/] [thin_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, 2009, 2010, 2011 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 3, 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 
// Under Section 7 of GPL version 3, you are granted additional
17 
// permissions described in the GCC Runtime Library Exception, version
18 
// 3.1, as published by the Free Software Foundation.
19 
 
20 
// You should have received a copy of the GNU General Public License and
21 
// a copy of the GCC Runtime Library Exception along with this program;
22 
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23 
// <http://www.gnu.org/licenses/>.
24 
 
25 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26 
 
27 
// Permission to use, copy, modify, sell, and distribute this software
28 
// is hereby granted without fee, provided that the above copyright
29 
// notice appears in all copies, and that both that copyright notice
30 
// and this permission notice appear in supporting documentation. None
31 
// of the above authors, nor IBM Haifa Research Laboratories, make any
32 
// representation about the suitability of this software for any
33 
// purpose. It is provided "as is" without express or implied
34 
// warranty.
35 
 
36 
/**
37 
 * @file thin_heap_/erase_fn_imps.hpp
38 
 * Contains an implementation for thin_heap_.
39 
 */
40 
 
41 
PB_DS_CLASS_T_DEC
42 
void
43 
PB_DS_CLASS_C_DEC::
44 
pop()
45 
{
46 
  PB_DS_ASSERT_VALID((*this))
47 
  _GLIBCXX_DEBUG_ASSERT(!base_type::empty());
48 
  _GLIBCXX_DEBUG_ASSERT(m_p_max != 0);
49 
 
50 
  node_pointer p_nd = m_p_max;
51 
  remove_max_node();
52 
  base_type::actual_erase_node(p_nd);
53 
  PB_DS_ASSERT_VALID((*this))
54 
}
55 
 
56 
PB_DS_CLASS_T_DEC
57 
inline void
58 
PB_DS_CLASS_C_DEC::
59 
remove_max_node()
60 
{
61 
  to_aux_except_max();
62 
  make_from_aux();
63 
}
64 
 
65 
PB_DS_CLASS_T_DEC
66 
void
67 
PB_DS_CLASS_C_DEC::
68 
to_aux_except_max()
69 
{
70 
  node_pointer p_add = base_type::m_p_root;
71 
  while (p_add != m_p_max)
72 
    {
73 
      node_pointer p_next_add = p_add->m_p_next_sibling;
74 
      add_to_aux(p_add);
75 
      p_add = p_next_add;
76 
    }
77 
 
78 
  p_add = m_p_max->m_p_l_child;
79 
  while (p_add != 0)
80 
    {
81 
      node_pointer p_next_add = p_add->m_p_next_sibling;
82 
      p_add->m_metadata = p_add->m_p_l_child == 0 ?
83 
 
84 
 
85 
      add_to_aux(p_add);
86 
      p_add = p_next_add;
87 
    }
88 
 
89 
  p_add = m_p_max->m_p_next_sibling;
90 
  while (p_add != 0)
91 
    {
92 
      node_pointer p_next_add = p_add->m_p_next_sibling;
93 
      add_to_aux(p_add);
94 
      p_add = p_next_add;
95 
    }
96 
}
97 
 
98 
PB_DS_CLASS_T_DEC
99 
inline void
100 
PB_DS_CLASS_C_DEC::
101 
add_to_aux(node_pointer p_nd)
102 
{
103 
  size_type r = p_nd->m_metadata;
104 
  while (m_a_aux[r] != 0)
105 
    {
106 
      _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound());
107 
      if (Cmp_Fn::operator()(m_a_aux[r]->m_value, p_nd->m_value))
108 
        make_child_of(m_a_aux[r], p_nd);
109 
      else
110 
        {
111 
          make_child_of(p_nd, m_a_aux[r]);
112 
          p_nd = m_a_aux[r];
113 
        }
114 
 
115 
      m_a_aux[r] = 0;
116 
      ++r;
117 
    }
118 
 
119 
  _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound());
120 
 
121 
  m_a_aux[r] = p_nd;
122 
}
123 
 
124 
PB_DS_CLASS_T_DEC
125 
inline void
126 
PB_DS_CLASS_C_DEC::
127 
make_child_of(node_pointer p_nd, node_pointer p_new_parent)
128 
{
129 
  _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata == p_new_parent->m_metadata);
130 
  _GLIBCXX_DEBUG_ASSERT(m_a_aux[p_nd->m_metadata] == p_nd ||
131 
                   m_a_aux[p_nd->m_metadata] == p_new_parent);
132 
 
133 
  ++p_new_parent->m_metadata;
134 
  base_type::make_child_of(p_nd, p_new_parent);
135 
}
136 
 
137 
PB_DS_CLASS_T_DEC
138 
inline void
139 
PB_DS_CLASS_C_DEC::
140 
make_from_aux()
141 
{
142 
  base_type::m_p_root = m_p_max = 0;
143 
  const size_type rnk_bnd = rank_bound();
144 
  size_type i = 0;
145 
  while (i < rnk_bnd)
146 
    {
147 
      if (m_a_aux[i] != 0)
148 
        {
149 
          make_root_and_link(m_a_aux[i]);
150 
          m_a_aux[i] = 0;
151 
        }
152 
      ++i;
153 
    }
154 
 
155 
  PB_DS_ASSERT_AUX_NULL((*this))
156 
}
157 
 
158 
PB_DS_CLASS_T_DEC
159 
inline void
160 
PB_DS_CLASS_C_DEC::
161 
remove_node(node_pointer p_nd)
162 
{
163 
  node_pointer p_parent = p_nd;
164 
  while (base_type::parent(p_parent) != 0)
165 
    p_parent = base_type::parent(p_parent);
166 
 
167 
  base_type::bubble_to_top(p_nd);
168 
  m_p_max = p_nd;
169 
 
170 
  node_pointer p_fix = base_type::m_p_root;
171 
  while (p_fix != 0&&  p_fix->m_p_next_sibling != p_parent)
172 
    p_fix = p_fix->m_p_next_sibling;
173 
 
174 
  if (p_fix != 0)
175 
    p_fix->m_p_next_sibling = p_nd;
176 
 
177 
  remove_max_node();
178 
}
179 
 
180 
PB_DS_CLASS_T_DEC
181 
inline void
182 
PB_DS_CLASS_C_DEC::
183 
clear()
184 
{
185 
  base_type::clear();
186 
  m_p_max = 0;
187 
}
188 
 
189 
PB_DS_CLASS_T_DEC
190 
void
191 
PB_DS_CLASS_C_DEC::
192 
erase(point_iterator it)
193 
{
194 
  PB_DS_ASSERT_VALID((*this))
195 
  _GLIBCXX_DEBUG_ASSERT(!base_type::empty());
196 
 
197 
  node_pointer p_nd = it.m_p_nd;
198 
  remove_node(p_nd);
199 
  base_type::actual_erase_node(p_nd);
200 
  PB_DS_ASSERT_VALID((*this))
201 
}
202 
 
203 
PB_DS_CLASS_T_DEC
204 
template<typename Pred>
205 
typename PB_DS_CLASS_C_DEC::size_type
206 
PB_DS_CLASS_C_DEC::
207 
erase_if(Pred pred)
208 
{
209 
  PB_DS_ASSERT_VALID((*this))
210 
  if (base_type::empty())
211 
    {
212 
      PB_DS_ASSERT_VALID((*this))
213 
      return 0;
214 
    }
215 
 
216 
  base_type::to_linked_list();
217 
  node_pointer p_out = base_type::prune(pred);
218 
  size_type ersd = 0;
219 
  while (p_out != 0)
220 
    {
221 
      ++ersd;
222 
      node_pointer p_next = p_out->m_p_next_sibling;
223 
      base_type::actual_erase_node(p_out);
224 
      p_out = p_next;
225 
    }
226 
 
227 
  node_pointer p_cur = base_type::m_p_root;
228 
  m_p_max = base_type::m_p_root = 0;
229 
  while (p_cur != 0)
230 
    {
231 
      node_pointer p_next = p_cur->m_p_next_sibling;
232 
      make_root_and_link(p_cur);
233 
      p_cur = p_next;
234 
    }
235 
 
236 
  PB_DS_ASSERT_VALID((*this))
237 
  return ersd;
238 
}
239 
 
240 
PB_DS_CLASS_T_DEC
241 
inline typename PB_DS_CLASS_C_DEC::size_type
242 
PB_DS_CLASS_C_DEC::
243 
rank_bound()
244 
{
245 
  using namespace std;
246 
  const size_t* const p_upper =
247 
    std::upper_bound(g_a_rank_bounds,
248 
                     g_a_rank_bounds + num_distinct_rank_bounds,
249 
                     base_type::m_size);
250 
 
251 
  if (p_upper == g_a_rank_bounds + num_distinct_rank_bounds)
252 
    return max_rank;
253 
 
254 
  return (p_upper - g_a_rank_bounds);
255 
}

powered by: WebSVN 2.1.0

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