1// -*- C++ -*-
2
3// Copyright (C) 2005 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
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 2, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.
15
16// You should have received a copy of the GNU General Public License along
17// with this library; see the file COPYING.  If not, write to the Free
18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
19// USA.
20
21// As a special exception, you may use this file as part of a free software
22// library without restriction.  Specifically, if other files instantiate
23// templates or use macros or inline functions from this file, or you compile
24// this file and link it with other files to produce an executable, this
25// file does not by itself cause the resulting executable to be covered by
26// the GNU General Public License.  This exception does not however
27// invalidate any other reasons why the executable file might be covered by
28// the GNU General Public License.
29
30// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
31
32// Permission to use, copy, modify, sell, and distribute this software
33// is hereby granted without fee, provided that the above copyright
34// notice appears in all copies, and that both that copyright notice and
35// this permission notice appear in supporting documentation. None of
36// the above authors, nor IBM Haifa Research Laboratories, make any
37// representation about the suitability of this software for any
38// purpose. It is provided "as is" without express or implied warranty.
39
40/**
41 * @file split_join_fn_imps.hpp
42 * Contains an implementation for rb_tree_.
43 */
44
45PB_ASSOC_CLASS_T_DEC
46inline void
47PB_ASSOC_CLASS_C_DEC::
48join(PB_ASSOC_CLASS_C_DEC& r_other)
49{
50  PB_ASSOC_DBG_ONLY(assert_valid();)
51    PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
52
53    PB_ASSOC_DBG_ONLY(r_other.assert_valid();)
54    PB_ASSOC_DBG_ONLY(r_other.PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
55
56    if (PB_ASSOC_BASE_C_DEC::join_prep(r_other) == false)
57      {
58	PB_ASSOC_DBG_ONLY(assert_valid();)
59	  PB_ASSOC_DBG_ONLY(r_other.assert_valid();)
60
61	  return;
62      }
63
64  const node_pointer p_x = r_other.split_min();
65
66  join_imp(p_x, r_other.m_p_head->m_p_parent);
67
68  PB_ASSOC_BASE_C_DEC::join_finish(r_other);
69
70  PB_ASSOC_DBG_ONLY(assert_valid();)
71    PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
72
73    PB_ASSOC_DBG_ONLY(r_other.assert_valid();)
74    PB_ASSOC_DBG_ONLY(r_other.PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
75    }
76
77PB_ASSOC_CLASS_T_DEC
78void
79PB_ASSOC_CLASS_C_DEC::
80join_imp(node_pointer p_x, node_pointer p_r)
81{
82  PB_ASSOC_DBG_ASSERT(p_x != NULL);
83
84  if (p_r != NULL)
85    p_r->m_red = false;
86
87  const size_type h =
88    black_height(PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent);
89  const size_type other_h = black_height(p_r);
90
91  node_pointer p_x_l;
92  node_pointer p_x_r;
93
94  std::pair<node_pointer, node_pointer> join_pos;
95
96  const bool right_join = h >= other_h;
97
98  if (right_join)
99    {
100      join_pos = find_join_pos_right(PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent, h, other_h);
101
102      p_x_l = join_pos.first;
103      p_x_r = p_r;
104    }
105  else
106    {
107      p_x_l = PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent;
108
109      PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent = p_r;
110      if (p_r != NULL)
111	p_r->m_p_parent = PB_ASSOC_BASE_C_DEC::m_p_head;
112
113      join_pos = find_join_pos_left(PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent, h, other_h);
114
115      p_x_r = join_pos.first;
116    }
117
118  node_pointer p_parent = join_pos.second;
119
120  if (p_parent == PB_ASSOC_BASE_C_DEC::m_p_head)
121    {
122      PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent = p_x;
123
124      p_x->m_p_parent = PB_ASSOC_BASE_C_DEC::m_p_head;
125    }
126  else
127    {
128      p_x->m_p_parent = p_parent;
129
130      if (right_join)
131	p_x->m_p_parent->m_p_right = p_x;
132      else
133	p_x->m_p_parent->m_p_left = p_x;
134    }
135
136  p_x->m_p_left = p_x_l;
137  if (p_x_l != NULL)
138    p_x_l->m_p_parent = p_x;
139
140  p_x->m_p_right = p_x_r;
141  if (p_x_r != NULL)
142    p_x_r->m_p_parent = p_x;
143
144  p_x->m_red = true;
145
146  PB_ASSOC_BASE_C_DEC::initialize_min_max();
147
148  PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
149
150    PB_ASSOC_BASE_C_DEC::update_to_top(p_x, (Node_Updator* )this);
151
152  insert_fixup(p_x);
153
154  PB_ASSOC_DBG_ONLY(assert_valid());
155  PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
156    }
157
158PB_ASSOC_CLASS_T_DEC
159inline typename PB_ASSOC_CLASS_C_DEC::node_pointer
160PB_ASSOC_CLASS_C_DEC::
161split_min()
162{
163  PB_ASSOC_DBG_ASSERT(PB_ASSOC_BASE_C_DEC::m_p_head->m_p_left !=
164		      PB_ASSOC_BASE_C_DEC::m_p_head);
165
166  node_pointer p_min = PB_ASSOC_BASE_C_DEC::m_p_head->m_p_left;
167
168  remove_node(p_min);
169
170  return (p_min);
171}
172
173PB_ASSOC_CLASS_T_DEC
174std::pair<
175  typename PB_ASSOC_CLASS_C_DEC::node_pointer,
176  typename PB_ASSOC_CLASS_C_DEC::node_pointer>
177PB_ASSOC_CLASS_C_DEC::
178find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r)
179{
180  PB_ASSOC_DBG_ASSERT(h_l >= h_r);
181
182  if (PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent == NULL)
183    return (std::make_pair((node_pointer)NULL,
184			   PB_ASSOC_BASE_C_DEC::m_p_head));
185
186  node_pointer p_l_parent = PB_ASSOC_BASE_C_DEC::m_p_head;
187
188  while (h_l > h_r)
189    {
190      if (p_l->m_red == false)
191	{
192	  PB_ASSOC_DBG_ASSERT(h_l > 0);
193
194	  --h_l;
195	}
196
197      p_l_parent = p_l;
198
199      p_l = p_l->m_p_right;
200    }
201
202  if (!is_effectively_black(p_l))
203    {
204      p_l_parent = p_l;
205
206      p_l = p_l->m_p_right;
207    }
208
209  PB_ASSOC_DBG_ASSERT(is_effectively_black(p_l));
210  PB_ASSOC_DBG_ASSERT(black_height(p_l) == h_r);
211  PB_ASSOC_DBG_ASSERT(p_l == NULL || p_l->m_p_parent == p_l_parent);
212
213  return (std::make_pair(p_l, p_l_parent));
214}
215
216PB_ASSOC_CLASS_T_DEC
217std::pair<
218  typename PB_ASSOC_CLASS_C_DEC::node_pointer,
219  typename PB_ASSOC_CLASS_C_DEC::node_pointer>
220PB_ASSOC_CLASS_C_DEC::
221find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r)
222{
223  PB_ASSOC_DBG_ASSERT(h_r > h_l);
224
225  if (PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent == NULL)
226    return (std::make_pair((node_pointer)NULL,
227			   PB_ASSOC_BASE_C_DEC::m_p_head));
228
229  node_pointer p_r_parent = PB_ASSOC_BASE_C_DEC::m_p_head;
230
231  while (h_r > h_l)
232    {
233      if (p_r->m_red == false)
234	{
235	  PB_ASSOC_DBG_ASSERT(h_r > 0);
236
237	  --h_r;
238	}
239
240      p_r_parent = p_r;
241
242      p_r = p_r->m_p_left;
243    }
244
245  if (!is_effectively_black(p_r))
246    {
247      p_r_parent = p_r;
248
249      p_r = p_r->m_p_left;
250    }
251
252  PB_ASSOC_DBG_ASSERT(is_effectively_black(p_r));
253  PB_ASSOC_DBG_ASSERT(black_height(p_r) == h_l);
254  PB_ASSOC_DBG_ASSERT(p_r == NULL || p_r->m_p_parent == p_r_parent);
255
256  return (std::make_pair(p_r, p_r_parent));
257}
258
259PB_ASSOC_CLASS_T_DEC
260inline typename PB_ASSOC_CLASS_C_DEC::size_type
261PB_ASSOC_CLASS_C_DEC::
262black_height(node_pointer p_nd)
263{
264  size_type h = 1;
265
266  while (p_nd != NULL)
267    {
268      if (p_nd->m_red == false)
269	++h;
270
271      p_nd = p_nd->m_p_left;
272    }
273
274  return (h);
275}
276
277PB_ASSOC_CLASS_T_DEC
278void
279PB_ASSOC_CLASS_C_DEC::
280split(const_key_reference r_key, PB_ASSOC_CLASS_C_DEC& r_other)
281{
282  PB_ASSOC_DBG_ONLY(assert_valid());
283  PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
284
285    PB_ASSOC_DBG_ONLY(r_other.assert_valid());
286  PB_ASSOC_DBG_ONLY(r_other.PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
287
288    if (PB_ASSOC_BASE_C_DEC::split_prep(r_key, r_other) == false)
289      {
290	PB_ASSOC_DBG_ONLY(assert_valid());
291	PB_ASSOC_DBG_ONLY(r_other.assert_valid());
292
293	return;
294      }
295
296  PB_ASSOC_DBG_ONLY(assert_valid());
297  PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
298
299    PB_ASSOC_DBG_ONLY(r_other.assert_valid());
300  PB_ASSOC_DBG_ONLY(r_other.PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
301
302    node_pointer p_nd = upper_bound(r_key).m_p_nd;
303
304  do
305    {
306      node_pointer p_next_nd = p_nd->m_p_parent;
307
308      if (Cmp_Fn::operator()(
309			     r_key,
310			     PB_ASSOC_V2F(p_nd->m_value)))
311	split_at_node(p_nd, r_other);
312
313      PB_ASSOC_DBG_ONLY(assert_valid());
314      PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
315
316	PB_ASSOC_DBG_ONLY(r_other.assert_valid());
317      PB_ASSOC_DBG_ONLY(r_other.PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
318
319	p_nd = p_next_nd;
320    }
321  while (p_nd != PB_ASSOC_BASE_C_DEC::m_p_head);
322
323  PB_ASSOC_BASE_C_DEC::split_finish(r_other);
324
325  PB_ASSOC_DBG_ONLY(assert_valid());
326  PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
327
328    PB_ASSOC_DBG_ONLY(r_other.assert_valid());
329  PB_ASSOC_DBG_ONLY(r_other.PB_ASSOC_BASE_C_DEC::assert_valid(true, true);)
330    }
331
332PB_ASSOC_CLASS_T_DEC
333void
334PB_ASSOC_CLASS_C_DEC::
335split_at_node(node_pointer p_nd, PB_ASSOC_CLASS_C_DEC& r_other)
336{
337  PB_ASSOC_DBG_ASSERT(p_nd != NULL);
338
339  node_pointer p_l = p_nd->m_p_left;
340  node_pointer p_r = p_nd->m_p_right;
341
342  node_pointer p_parent = p_nd->m_p_parent;
343
344  if (p_parent == PB_ASSOC_BASE_C_DEC::m_p_head)
345    {
346      PB_ASSOC_BASE_C_DEC::m_p_head->m_p_parent = p_l;
347
348      if (p_l != NULL)
349	{
350	  p_l->m_p_parent = PB_ASSOC_BASE_C_DEC::m_p_head;
351
352	  p_l->m_red = false;
353	}
354    }
355  else
356    {
357      if (p_parent->m_p_left == p_nd)
358	p_parent->m_p_left = p_l;
359      else
360	p_parent->m_p_right = p_l;
361
362      if (p_l != NULL)
363	p_l->m_p_parent = p_parent;
364
365      update_to_top(p_parent, (Node_Updator* )this);
366
367      if (!p_nd->m_red)
368	remove_fixup(p_l, p_parent);
369    }
370
371  PB_ASSOC_BASE_C_DEC::initialize_min_max();
372
373  PB_ASSOC_DBG_ONLY(assert_valid());
374  PB_ASSOC_DBG_ONLY(PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
375
376    PB_ASSOC_DBG_ONLY(r_other.assert_valid());
377  PB_ASSOC_DBG_ONLY(r_other.PB_ASSOC_BASE_C_DEC::assert_valid(true, false);)
378
379    r_other.join_imp(p_nd, p_r);
380}
381
382