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 erase_fn_imps.hpp
44 * Contains an implementation for thin_heap_.
45 */
46
47 PB_DS_CLASS_T_DEC
48 void
49 PB_DS_CLASS_C_DEC::
pop()50 pop()
51 {
52 _GLIBCXX_DEBUG_ONLY(assert_valid();)
53 _GLIBCXX_DEBUG_ASSERT(!base_type::empty());
54
55 _GLIBCXX_DEBUG_ASSERT(m_p_max != NULL);
56
57 node_pointer p_nd = m_p_max;
58
59 remove_max_node();
60
61 base_type::actual_erase_node(p_nd);
62
63 _GLIBCXX_DEBUG_ONLY(assert_valid();)
64 }
65
66 PB_DS_CLASS_T_DEC
67 inline void
68 PB_DS_CLASS_C_DEC::
remove_max_node()69 remove_max_node()
70 {
71 to_aux_except_max();
72
73 make_from_aux();
74 }
75
76 PB_DS_CLASS_T_DEC
77 void
78 PB_DS_CLASS_C_DEC::
to_aux_except_max()79 to_aux_except_max()
80 {
81 node_pointer p_add = base_type::m_p_root;
82
83 while (p_add != m_p_max)
84 {
85 node_pointer p_next_add = p_add->m_p_next_sibling;
86
87 add_to_aux(p_add);
88
89 p_add = p_next_add;
90 }
91
92 p_add = m_p_max->m_p_l_child;
93
94 while (p_add != NULL)
95 {
96 node_pointer p_next_add = p_add->m_p_next_sibling;
97
98 p_add->m_metadata = p_add->m_p_l_child == NULL?
99 0 :
100 p_add->m_p_l_child->m_metadata + 1;
101
102 add_to_aux(p_add);
103
104 p_add = p_next_add;
105 }
106
107 p_add = m_p_max->m_p_next_sibling;
108
109 while (p_add != NULL)
110 {
111 node_pointer p_next_add = p_add->m_p_next_sibling;
112
113 add_to_aux(p_add);
114
115 p_add = p_next_add;
116 }
117 }
118
119 PB_DS_CLASS_T_DEC
120 inline void
121 PB_DS_CLASS_C_DEC::
add_to_aux(node_pointer p_nd)122 add_to_aux(node_pointer p_nd)
123 {
124 size_type r = p_nd->m_metadata;
125
126 while (m_a_aux[r] != NULL)
127 {
128 _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound());
129
130 if (Cmp_Fn::operator()(m_a_aux[r]->m_value, p_nd->m_value))
131 make_child_of(m_a_aux[r], p_nd);
132 else
133 {
134 make_child_of(p_nd, m_a_aux[r]);
135
136 p_nd = m_a_aux[r];
137 }
138
139 m_a_aux[r] = NULL;
140
141 ++r;
142 }
143
144 _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound());
145
146 m_a_aux[r] = p_nd;
147 }
148
149 PB_DS_CLASS_T_DEC
150 inline void
151 PB_DS_CLASS_C_DEC::
make_child_of(node_pointer p_nd,node_pointer p_new_parent)152 make_child_of(node_pointer p_nd, node_pointer p_new_parent)
153 {
154 _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata == p_new_parent->m_metadata);
155 _GLIBCXX_DEBUG_ASSERT(m_a_aux[p_nd->m_metadata] == p_nd ||
156 m_a_aux[p_nd->m_metadata] == p_new_parent);
157
158 ++p_new_parent->m_metadata;
159
160 base_type::make_child_of(p_nd, p_new_parent);
161 }
162
163 PB_DS_CLASS_T_DEC
164 inline void
165 PB_DS_CLASS_C_DEC::
make_from_aux()166 make_from_aux()
167 {
168 base_type::m_p_root = m_p_max = NULL;
169
170 const size_type rnk_bnd = rank_bound();
171
172 size_type i = 0;
173
174 while (i < rnk_bnd)
175 {
176 if (m_a_aux[i] != NULL)
177 {
178 make_root_and_link(m_a_aux[i]);
179
180 m_a_aux[i] = NULL;
181 }
182
183 ++i;
184 }
185
186 _GLIBCXX_DEBUG_ONLY(assert_aux_null();)
187 }
188
189 PB_DS_CLASS_T_DEC
190 inline void
191 PB_DS_CLASS_C_DEC::
remove_node(node_pointer p_nd)192 remove_node(node_pointer p_nd)
193 {
194 node_pointer p_parent = p_nd;
195 while (base_type::parent(p_parent) != NULL)
196 p_parent = base_type::parent(p_parent);
197
198 base_type::bubble_to_top(p_nd);
199
200 m_p_max = p_nd;
201
202 node_pointer p_fix = base_type::m_p_root;
203 while (p_fix != NULL&& p_fix->m_p_next_sibling != p_parent)
204 p_fix = p_fix->m_p_next_sibling;
205
206 if (p_fix != NULL)
207 p_fix->m_p_next_sibling = p_nd;
208
209 remove_max_node();
210 }
211
212 PB_DS_CLASS_T_DEC
213 inline void
214 PB_DS_CLASS_C_DEC::
clear()215 clear()
216 {
217 base_type::clear();
218
219 m_p_max = NULL;
220 }
221
222 PB_DS_CLASS_T_DEC
223 void
224 PB_DS_CLASS_C_DEC::
erase(point_iterator it)225 erase(point_iterator it)
226 {
227 _GLIBCXX_DEBUG_ONLY(assert_valid();)
228 _GLIBCXX_DEBUG_ASSERT(!base_type::empty());
229
230 node_pointer p_nd = it.m_p_nd;
231
232 remove_node(p_nd);
233
234 base_type::actual_erase_node(p_nd);
235
236 _GLIBCXX_DEBUG_ONLY(assert_valid();)
237 }
238
239 PB_DS_CLASS_T_DEC
240 template<typename Pred>
241 typename PB_DS_CLASS_C_DEC::size_type
242 PB_DS_CLASS_C_DEC::
erase_if(Pred pred)243 erase_if(Pred pred)
244 {
245 _GLIBCXX_DEBUG_ONLY(assert_valid();)
246
247 if (base_type::empty())
248 {
249 _GLIBCXX_DEBUG_ONLY(assert_valid();)
250
251 return 0;
252 }
253
254 base_type::to_linked_list();
255
256 node_pointer p_out = base_type::prune(pred);
257
258 size_type ersd = 0;
259
260 while (p_out != NULL)
261 {
262 ++ersd;
263
264 node_pointer p_next = p_out->m_p_next_sibling;
265
266 base_type::actual_erase_node(p_out);
267
268 p_out = p_next;
269 }
270
271 node_pointer p_cur = base_type::m_p_root;
272
273 m_p_max = base_type::m_p_root = NULL;
274
275 while (p_cur != NULL)
276 {
277 node_pointer p_next = p_cur->m_p_next_sibling;
278
279 make_root_and_link(p_cur);
280
281 p_cur = p_next;
282 }
283
284 _GLIBCXX_DEBUG_ONLY(assert_valid();)
285
286 return ersd;
287 }
288
289 PB_DS_CLASS_T_DEC
290 inline typename PB_DS_CLASS_C_DEC::size_type
291 PB_DS_CLASS_C_DEC::
rank_bound()292 rank_bound()
293 {
294 const std::size_t* const p_upper =
295 std::upper_bound( g_a_rank_bounds, g_a_rank_bounds + num_distinct_rank_bounds, base_type::m_size);
296
297 if (p_upper == g_a_rank_bounds + num_distinct_rank_bounds)
298 return max_rank;
299
300 return (p_upper - g_a_rank_bounds);
301 }
302
303