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