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 split_join_fn_imps.hpp
44 * Contains an implementation for rb_tree_.
45 */
46
47PB_DS_CLASS_T_DEC
48inline void
49PB_DS_CLASS_C_DEC::
50join(PB_DS_CLASS_C_DEC& other)
51{
52  _GLIBCXX_DEBUG_ONLY(assert_valid();)
53  _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
54  _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();)
55  if (base_type::join_prep(other) == false)
56    {
57      _GLIBCXX_DEBUG_ONLY(assert_valid();)
58      _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
59      return;
60    }
61
62  const node_pointer p_x = other.split_min();
63  join_imp(p_x, other.m_p_head->m_p_parent);
64  base_type::join_finish(other);
65  _GLIBCXX_DEBUG_ONLY(assert_valid();)
66  _GLIBCXX_DEBUG_ONLY(base_type::assert_valid();)
67  _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
68  _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();)
69 }
70
71PB_DS_CLASS_T_DEC
72void
73PB_DS_CLASS_C_DEC::
74join_imp(node_pointer p_x, node_pointer p_r)
75{
76  _GLIBCXX_DEBUG_ASSERT(p_x != NULL);
77  if (p_r != NULL)
78    p_r->m_red = false;
79
80  const size_type h = black_height(base_type::m_p_head->m_p_parent);
81  const size_type other_h = black_height(p_r);
82  node_pointer p_x_l;
83  node_pointer p_x_r;
84  std::pair<node_pointer, node_pointer> join_pos;
85  const bool right_join = h >= other_h;
86  if (right_join)
87    {
88      join_pos = find_join_pos_right(base_type::m_p_head->m_p_parent,
89				     h, other_h);
90      p_x_l = join_pos.first;
91      p_x_r = p_r;
92    }
93  else
94    {
95      p_x_l = base_type::m_p_head->m_p_parent;
96      base_type::m_p_head->m_p_parent = p_r;
97      if (p_r != NULL)
98	p_r->m_p_parent = base_type::m_p_head;
99
100      join_pos = find_join_pos_left(base_type::m_p_head->m_p_parent,
101				    h, other_h);
102      p_x_r = join_pos.first;
103    }
104
105  node_pointer p_parent = join_pos.second;
106  if (p_parent == base_type::m_p_head)
107    {
108      base_type::m_p_head->m_p_parent = p_x;
109      p_x->m_p_parent = base_type::m_p_head;
110    }
111  else
112    {
113      p_x->m_p_parent = p_parent;
114      if (right_join)
115	p_x->m_p_parent->m_p_right = p_x;
116      else
117	p_x->m_p_parent->m_p_left = p_x;
118    }
119
120  p_x->m_p_left = p_x_l;
121  if (p_x_l != NULL)
122    p_x_l->m_p_parent = p_x;
123
124  p_x->m_p_right = p_x_r;
125  if (p_x_r != NULL)
126    p_x_r->m_p_parent = p_x;
127
128  p_x->m_red = true;
129
130  base_type::initialize_min_max();
131  _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();)
132  base_type::update_to_top(p_x, (node_update* )this);
133  insert_fixup(p_x);
134  _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid());
135}
136
137PB_DS_CLASS_T_DEC
138inline typename PB_DS_CLASS_C_DEC::node_pointer
139PB_DS_CLASS_C_DEC::
140split_min()
141{
142  node_pointer p_min = base_type::m_p_head->m_p_left;
143
144#ifdef _GLIBCXX_DEBUG
145  const node_pointer p_head = base_type::m_p_head;
146  _GLIBCXX_DEBUG_ASSERT(p_min != p_head);
147#endif
148
149  remove_node(p_min);
150  return p_min;
151}
152
153PB_DS_CLASS_T_DEC
154std::pair<
155  typename PB_DS_CLASS_C_DEC::node_pointer,
156  typename PB_DS_CLASS_C_DEC::node_pointer>
157PB_DS_CLASS_C_DEC::
158find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r)
159{
160  _GLIBCXX_DEBUG_ASSERT(h_l >= h_r);
161
162  if (base_type::m_p_head->m_p_parent == NULL)
163    return (std::make_pair((node_pointer)NULL, base_type::m_p_head));
164
165  node_pointer p_l_parent = base_type::m_p_head;
166  while (h_l > h_r)
167    {
168      if (p_l->m_red == false)
169        {
170	  _GLIBCXX_DEBUG_ASSERT(h_l > 0);
171	  --h_l;
172        }
173
174      p_l_parent = p_l;
175      p_l = p_l->m_p_right;
176    }
177
178  if (!is_effectively_black(p_l))
179    {
180      p_l_parent = p_l;
181      p_l = p_l->m_p_right;
182    }
183
184  _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_l));
185  _GLIBCXX_DEBUG_ASSERT(black_height(p_l) == h_r);
186  _GLIBCXX_DEBUG_ASSERT(p_l == NULL || p_l->m_p_parent == p_l_parent);
187  return std::make_pair(p_l, p_l_parent);
188}
189
190PB_DS_CLASS_T_DEC
191std::pair<
192  typename PB_DS_CLASS_C_DEC::node_pointer,
193  typename PB_DS_CLASS_C_DEC::node_pointer>
194PB_DS_CLASS_C_DEC::
195find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r)
196{
197  _GLIBCXX_DEBUG_ASSERT(h_r > h_l);
198  if (base_type::m_p_head->m_p_parent == NULL)
199    return (std::make_pair((node_pointer)NULL,
200			   base_type::m_p_head));
201  node_pointer p_r_parent = base_type::m_p_head;
202  while (h_r > h_l)
203    {
204      if (p_r->m_red == false)
205        {
206	  _GLIBCXX_DEBUG_ASSERT(h_r > 0);
207	  --h_r;
208        }
209
210      p_r_parent = p_r;
211      p_r = p_r->m_p_left;
212    }
213
214  if (!is_effectively_black(p_r))
215    {
216      p_r_parent = p_r;
217      p_r = p_r->m_p_left;
218    }
219
220  _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_r));
221  _GLIBCXX_DEBUG_ASSERT(black_height(p_r) == h_l);
222  _GLIBCXX_DEBUG_ASSERT(p_r == NULL || p_r->m_p_parent == p_r_parent);
223  return std::make_pair(p_r, p_r_parent);
224}
225
226PB_DS_CLASS_T_DEC
227inline typename PB_DS_CLASS_C_DEC::size_type
228PB_DS_CLASS_C_DEC::
229black_height(node_pointer p_nd)
230{
231  size_type h = 1;
232  while (p_nd != NULL)
233    {
234      if (p_nd->m_red == false)
235	++h;
236      p_nd = p_nd->m_p_left;
237    }
238  return h;
239}
240
241PB_DS_CLASS_T_DEC
242void
243PB_DS_CLASS_C_DEC::
244split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other)
245{
246  _GLIBCXX_DEBUG_ONLY(assert_valid());
247  _GLIBCXX_DEBUG_ONLY(base_type::assert_valid();)
248
249    _GLIBCXX_DEBUG_ONLY(other.assert_valid());
250  _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();)
251
252    if (base_type::split_prep(r_key, other) == false)
253      {
254        _GLIBCXX_DEBUG_ONLY(assert_valid());
255        _GLIBCXX_DEBUG_ONLY(other.assert_valid());
256        return;
257      }
258
259  _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();)
260  _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid();)
261  node_pointer p_nd = upper_bound(r_key).m_p_nd;
262  do
263    {
264      node_pointer p_next_nd = p_nd->m_p_parent;
265      if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value)))
266	split_at_node(p_nd, other);
267
268      _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();)
269      _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid();)
270      p_nd = p_next_nd;
271    }
272  while (p_nd != base_type::m_p_head);
273
274  base_type::split_finish(other);
275  _GLIBCXX_DEBUG_ONLY(assert_valid();)
276  _GLIBCXX_DEBUG_ONLY(assert_valid();)
277}
278
279PB_DS_CLASS_T_DEC
280void
281PB_DS_CLASS_C_DEC::
282split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other)
283{
284  _GLIBCXX_DEBUG_ASSERT(p_nd != NULL);
285
286  node_pointer p_l = p_nd->m_p_left;
287  node_pointer p_r = p_nd->m_p_right;
288  node_pointer p_parent = p_nd->m_p_parent;
289  if (p_parent == base_type::m_p_head)
290    {
291      base_type::m_p_head->m_p_parent = p_l;
292      if (p_l != NULL)
293        {
294	  p_l->m_p_parent = base_type::m_p_head;
295	  p_l->m_red = false;
296        }
297    }
298  else
299    {
300      if (p_parent->m_p_left == p_nd)
301	p_parent->m_p_left = p_l;
302      else
303	p_parent->m_p_right = p_l;
304
305      if (p_l != NULL)
306	p_l->m_p_parent = p_parent;
307
308      update_to_top(p_parent, (node_update* )this);
309
310      if (!p_nd->m_red)
311	remove_fixup(p_l, p_parent);
312    }
313
314  base_type::initialize_min_max();
315  other.join_imp(p_nd, p_r);
316  _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid());
317  _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid());
318}
319
320