libstdc++
thin_heap_/insert_fn_imps.hpp
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2005-2021 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_/insert_fn_imps.hpp
38 * Contains an implementation for thin_heap_.
39 */
40
41#ifdef PB_DS_CLASS_C_DEC
42
43PB_DS_CLASS_T_DEC
44inline typename PB_DS_CLASS_C_DEC::point_iterator
45PB_DS_CLASS_C_DEC::
46push(const_reference r_val)
47{
48 PB_DS_ASSERT_VALID((*this))
49 node_pointer p_nd = base_type::get_new_node_for_insert(r_val);
50 p_nd->m_metadata = 0;
51 p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = 0;
52 if (base_type::m_p_root == 0)
53 {
54 p_nd->m_p_next_sibling = 0;
55 m_p_max = base_type::m_p_root = p_nd;
56 PB_DS_ASSERT_VALID((*this))
57 return point_iterator(p_nd);
58 }
59
60 p_nd->m_p_next_sibling = base_type::m_p_root;
61 base_type::m_p_root->m_p_prev_or_parent = 0;
62 base_type::m_p_root = p_nd;
63 update_max(p_nd);
64 PB_DS_ASSERT_VALID((*this))
65 return point_iterator(p_nd);
66}
67
68PB_DS_CLASS_T_DEC
69inline void
70PB_DS_CLASS_C_DEC::
71make_root(node_pointer p_nd)
72{
73 p_nd->m_metadata = p_nd->m_p_l_child == 0
74 ? 0 : 1 + p_nd->m_p_l_child->m_metadata;
75}
76
77PB_DS_CLASS_T_DEC
78inline void
79PB_DS_CLASS_C_DEC::
80make_root_and_link(node_pointer p_nd)
81{
82 make_root(p_nd);
83 p_nd->m_p_prev_or_parent = 0;
84 p_nd->m_p_next_sibling = base_type::m_p_root;
85 if (base_type::m_p_root != 0)
86 base_type::m_p_root->m_p_prev_or_parent = 0;
87
88 base_type::m_p_root = p_nd;
89 update_max(p_nd);
90}
91
92PB_DS_CLASS_T_DEC
93inline void
94PB_DS_CLASS_C_DEC::
95fix(node_pointer p_y)
96{
97 while (true)
98 {
99 if (p_y->m_p_prev_or_parent == 0)
100 {
101 fix_root(p_y);
102 return;
103 }
104 else if (p_y->m_metadata == 1&& p_y->m_p_next_sibling == 0)
105 {
106 if (p_y->m_p_l_child != 0)
107 {
108 fix_sibling_rank_1_unmarked(p_y);
109 return;
110 }
111
112 fix_sibling_rank_1_marked(p_y);
113 p_y = p_y->m_p_prev_or_parent;
114 }
115 else if (p_y->m_metadata > p_y->m_p_next_sibling->m_metadata + 1)
116 {
117 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child != 0);
118 if (p_y->m_metadata != p_y->m_p_l_child->m_metadata + 2)
119 {
120 fix_sibling_general_unmarked(p_y);
121 return;
122 }
123
124 fix_sibling_general_marked(p_y);
125 p_y = p_y->m_p_prev_or_parent;
126 }
127 else if ((p_y->m_p_l_child == 0&&
128 p_y->m_metadata == 2) ||(p_y->m_p_l_child != 0&&
129 p_y->m_metadata == p_y->m_p_l_child->m_metadata + 3))
130 {
131 node_pointer p_z = p_y->m_p_prev_or_parent;
132 fix_child(p_y);
133 p_y = p_z;
134 }
135 else
136 return;
137 }
138}
139
140PB_DS_CLASS_T_DEC
141inline void
142PB_DS_CLASS_C_DEC::
143fix_root(node_pointer p_y)
144{
145 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent == 0);
146 make_root(p_y);
147 PB_DS_ASSERT_NODE_CONSISTENT(p_y, true)
148}
149
150PB_DS_CLASS_T_DEC
151inline void
152PB_DS_CLASS_C_DEC::
153fix_sibling_rank_1_unmarked(node_pointer p_y)
154{
155 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0);
156
157 _GLIBCXX_DEBUG_ONLY(node_pointer p_w = p_y->m_p_l_child;)
158 _GLIBCXX_DEBUG_ASSERT(p_w != 0);
159 _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling == 0);
160 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_next_sibling == 0);
161
162 p_y->m_p_next_sibling = p_y->m_p_l_child;
163 p_y->m_p_next_sibling->m_p_prev_or_parent = p_y;
164 p_y->m_p_l_child = 0;
165 PB_DS_ASSERT_NODE_CONSISTENT(p_y, false)
166}
167
168PB_DS_CLASS_T_DEC
169inline void
170PB_DS_CLASS_C_DEC::
171fix_sibling_rank_1_marked(node_pointer p_y)
172{
173 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0);
174 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child == 0);
175 p_y->m_metadata = 0;
176 PB_DS_ASSERT_NODE_CONSISTENT(p_y, false)
177}
178
179PB_DS_CLASS_T_DEC
180inline void
181PB_DS_CLASS_C_DEC::
182fix_sibling_general_unmarked(node_pointer p_y)
183{
184 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0);
185
186 node_pointer p_w = p_y->m_p_l_child;
187 _GLIBCXX_DEBUG_ASSERT(p_w != 0);
188 _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != 0);
189
190 p_y->m_p_l_child = p_w->m_p_next_sibling;
191 p_w->m_p_next_sibling->m_p_prev_or_parent = p_y;
192
193 p_w->m_p_next_sibling = p_y->m_p_next_sibling;
194 _GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != 0);
195 p_w->m_p_next_sibling->m_p_prev_or_parent = p_w;
196
197 p_y->m_p_next_sibling = p_w;
198 p_w->m_p_prev_or_parent = p_y;
199
200 PB_DS_ASSERT_NODE_CONSISTENT(p_y, false)
201}
202
203PB_DS_CLASS_T_DEC
204inline void
205PB_DS_CLASS_C_DEC::
206fix_sibling_general_marked(node_pointer p_y)
207{
208 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0);
209 --p_y->m_metadata;
210 PB_DS_ASSERT_NODE_CONSISTENT(p_y, false)
211}
212
213PB_DS_CLASS_T_DEC
214inline void
215PB_DS_CLASS_C_DEC::
216fix_child(node_pointer p_y)
217{
218 _GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != 0);
219
220 if (p_y->m_p_next_sibling != 0)
221 p_y->m_p_next_sibling->m_p_prev_or_parent = p_y->m_p_prev_or_parent;
222
223 if (p_y->m_p_prev_or_parent->m_p_l_child == p_y)
224 p_y->m_p_prev_or_parent->m_p_l_child = p_y->m_p_next_sibling;
225 else
226 p_y->m_p_prev_or_parent->m_p_next_sibling = p_y->m_p_next_sibling;
227
228 make_root_and_link(p_y);
229}
230
231PB_DS_CLASS_T_DEC
232void
233PB_DS_CLASS_C_DEC::
234modify(point_iterator it, const_reference r_new_val)
235{
236 PB_DS_ASSERT_VALID((*this))
237 node_pointer p_nd = it.m_p_nd;
238 _GLIBCXX_DEBUG_ASSERT(p_nd != 0);
239
240 const bool smaller = Cmp_Fn::operator()(r_new_val, p_nd->m_value);
241 p_nd->m_value = r_new_val;
242 if (smaller)
243 {
244 remove_node(p_nd);
245 p_nd->m_p_l_child = 0;
246 make_root_and_link(p_nd);
247 PB_DS_ASSERT_VALID((*this))
248 return;
249 }
250
251 if (p_nd->m_p_prev_or_parent == 0)
252 {
253 update_max(p_nd);
254 PB_DS_ASSERT_VALID((*this))
255 return;
256 }
257
258 node_pointer p_y = p_nd->m_p_prev_or_parent;
259 _GLIBCXX_DEBUG_ASSERT(p_y != 0);
260
261 if (p_nd->m_p_next_sibling != 0)
262 p_nd->m_p_next_sibling->m_p_prev_or_parent = p_y;
263
264 if (p_y->m_p_l_child == p_nd)
265 p_y->m_p_l_child = p_nd->m_p_next_sibling;
266 else
267 p_y->m_p_next_sibling = p_nd->m_p_next_sibling;
268
269 fix(p_y);
270 make_root_and_link(p_nd);
271 PB_DS_ASSERT_VALID((*this))
272}
273
274PB_DS_CLASS_T_DEC
275inline void
276PB_DS_CLASS_C_DEC::
277update_max(node_pointer p_nd)
278{
279 if (m_p_max == 0 || Cmp_Fn::operator()(m_p_max->m_value, p_nd->m_value))
280 m_p_max = p_nd;
281}
282
283#endif