3 // Copyright (C) 2005, 2006, 2009, 2010 Free Software Foundation, Inc.
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
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.
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.
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/>.
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
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
37 * @file insert_fn_imps.hpp
38 * Contains an implementation for thin_heap_.
42 inline typename
PB_DS_CLASS_C_DEC::point_iterator
44 push(const_reference r_val
)
46 _GLIBCXX_DEBUG_ONLY(assert_valid();)
48 node_pointer p_nd
= base_type::get_new_node_for_insert(r_val
);
52 p_nd
->m_p_prev_or_parent
= p_nd
->m_p_l_child
= 0;
54 if (base_type::m_p_root
== 0)
56 p_nd
->m_p_next_sibling
= 0;
58 m_p_max
= base_type::m_p_root
= p_nd
;
60 _GLIBCXX_DEBUG_ONLY(assert_valid();)
62 return point_iterator(p_nd
);
65 p_nd
->m_p_next_sibling
= base_type::m_p_root
;
67 base_type::m_p_root
->m_p_prev_or_parent
= 0;
69 base_type::m_p_root
= p_nd
;
73 _GLIBCXX_DEBUG_ONLY(assert_valid();)
75 return point_iterator(p_nd
);
81 make_root(node_pointer p_nd
)
84 p_nd
->m_p_l_child
== 0?
86 1 + p_nd
->m_p_l_child
->m_metadata
;
92 make_root_and_link(node_pointer p_nd
)
96 p_nd
->m_p_prev_or_parent
= 0;
98 p_nd
->m_p_next_sibling
= base_type::m_p_root
;
100 if (base_type::m_p_root
!= 0)
101 base_type::m_p_root
->m_p_prev_or_parent
= 0;
103 base_type::m_p_root
= p_nd
;
111 fix(node_pointer p_y
)
115 if (p_y
->m_p_prev_or_parent
== 0)
121 else if (p_y
->m_metadata
== 1&& p_y
->m_p_next_sibling
== 0)
123 if (p_y
->m_p_l_child
!= 0)
125 fix_sibling_rank_1_unmarked(p_y
);
130 fix_sibling_rank_1_marked(p_y
);
132 p_y
= p_y
->m_p_prev_or_parent
;
134 else if (p_y
->m_metadata
> p_y
->m_p_next_sibling
->m_metadata
+ 1)
136 _GLIBCXX_DEBUG_ASSERT(p_y
->m_p_l_child
!= 0);
138 if (p_y
->m_metadata
!= p_y
->m_p_l_child
->m_metadata
+ 2)
140 fix_sibling_general_unmarked(p_y
);
145 fix_sibling_general_marked(p_y
);
147 p_y
= p_y
->m_p_prev_or_parent
;
149 else if ((p_y
->m_p_l_child
== 0&&
150 p_y
->m_metadata
== 2) ||(p_y
->m_p_l_child
!= 0&&
151 p_y
->m_metadata
== p_y
->m_p_l_child
->m_metadata
+ 3))
153 node_pointer p_z
= p_y
->m_p_prev_or_parent
;
167 fix_root(node_pointer p_y
)
169 _GLIBCXX_DEBUG_ASSERT(p_y
->m_p_prev_or_parent
== 0);
173 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y
, true);)
179 fix_sibling_rank_1_unmarked(node_pointer p_y
)
181 _GLIBCXX_DEBUG_ASSERT(p_y
->m_p_prev_or_parent
!= 0);
183 _GLIBCXX_DEBUG_ONLY(node_pointer p_w
= p_y
->m_p_l_child
;)
184 _GLIBCXX_DEBUG_ASSERT(p_w
!= 0);
185 _GLIBCXX_DEBUG_ASSERT(p_w
->m_p_next_sibling
== 0);
186 _GLIBCXX_DEBUG_ASSERT(p_y
->m_p_next_sibling
== 0);
188 p_y
->m_p_next_sibling
= p_y
->m_p_l_child
;
190 p_y
->m_p_next_sibling
->m_p_prev_or_parent
= p_y
;
192 p_y
->m_p_l_child
= 0;
194 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y
, false);)
200 fix_sibling_rank_1_marked(node_pointer p_y
)
202 _GLIBCXX_DEBUG_ASSERT(p_y
->m_p_prev_or_parent
!= 0);
203 _GLIBCXX_DEBUG_ASSERT(p_y
->m_p_l_child
== 0);
207 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y
, false);)
213 fix_sibling_general_unmarked(node_pointer p_y
)
215 _GLIBCXX_DEBUG_ASSERT(p_y
->m_p_prev_or_parent
!= 0);
217 node_pointer p_w
= p_y
->m_p_l_child
;
218 _GLIBCXX_DEBUG_ASSERT(p_w
!= 0);
219 _GLIBCXX_DEBUG_ASSERT(p_w
->m_p_next_sibling
!= 0);
221 p_y
->m_p_l_child
= p_w
->m_p_next_sibling
;
222 p_w
->m_p_next_sibling
->m_p_prev_or_parent
= p_y
;
224 p_w
->m_p_next_sibling
= p_y
->m_p_next_sibling
;
225 _GLIBCXX_DEBUG_ASSERT(p_w
->m_p_next_sibling
!= 0);
226 p_w
->m_p_next_sibling
->m_p_prev_or_parent
= p_w
;
228 p_y
->m_p_next_sibling
= p_w
;
229 p_w
->m_p_prev_or_parent
= p_y
;
231 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y
, false);)
237 fix_sibling_general_marked(node_pointer p_y
)
239 _GLIBCXX_DEBUG_ASSERT(p_y
->m_p_prev_or_parent
!= 0);
243 _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y
, false);)
249 fix_child(node_pointer p_y
)
251 _GLIBCXX_DEBUG_ASSERT(p_y
->m_p_prev_or_parent
!= 0);
253 if (p_y
->m_p_next_sibling
!= 0)
254 p_y
->m_p_next_sibling
->m_p_prev_or_parent
= p_y
->m_p_prev_or_parent
;
256 if (p_y
->m_p_prev_or_parent
->m_p_l_child
== p_y
)
257 p_y
->m_p_prev_or_parent
->m_p_l_child
= p_y
->m_p_next_sibling
;
259 p_y
->m_p_prev_or_parent
->m_p_next_sibling
= p_y
->m_p_next_sibling
;
261 make_root_and_link(p_y
);
267 modify(point_iterator it
, const_reference r_new_val
)
269 _GLIBCXX_DEBUG_ONLY(assert_valid();)
270 node_pointer p_nd
= it
.m_p_nd
;
272 _GLIBCXX_DEBUG_ASSERT(p_nd
!= 0);
274 const bool smaller
= Cmp_Fn::operator()(r_new_val
, p_nd
->m_value
);
276 p_nd
->m_value
= r_new_val
;
282 p_nd
->m_p_l_child
= 0;
284 make_root_and_link(p_nd
);
286 _GLIBCXX_DEBUG_ONLY(assert_valid();)
291 if (p_nd
->m_p_prev_or_parent
== 0)
295 _GLIBCXX_DEBUG_ONLY(assert_valid();)
300 node_pointer p_y
= p_nd
->m_p_prev_or_parent
;
301 _GLIBCXX_DEBUG_ASSERT(p_y
!= 0);
303 if (p_nd
->m_p_next_sibling
!= 0)
304 p_nd
->m_p_next_sibling
->m_p_prev_or_parent
= p_y
;
306 if (p_y
->m_p_l_child
== p_nd
)
307 p_y
->m_p_l_child
= p_nd
->m_p_next_sibling
;
309 p_y
->m_p_next_sibling
= p_nd
->m_p_next_sibling
;
313 make_root_and_link(p_nd
);
315 _GLIBCXX_DEBUG_ONLY(assert_valid();)
321 update_max(node_pointer p_nd
)
323 if (m_p_max
== 0 || Cmp_Fn::operator()(m_p_max
->m_value
, p_nd
->m_value
))