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