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