libstdc++
rb_tree_map_/split_join_fn_imps.hpp
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2005-2019 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
41PB_DS_CLASS_T_DEC
42inline void
43PB_DS_CLASS_C_DEC::
44join(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
62PB_DS_CLASS_T_DEC
63void
64PB_DS_CLASS_C_DEC::
65join_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
128PB_DS_CLASS_T_DEC
129inline typename PB_DS_CLASS_C_DEC::node_pointer
130PB_DS_CLASS_C_DEC::
131split_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
144PB_DS_CLASS_T_DEC
146 typename PB_DS_CLASS_C_DEC::node_pointer,
147 typename PB_DS_CLASS_C_DEC::node_pointer>
148PB_DS_CLASS_C_DEC::
149find_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
181PB_DS_CLASS_T_DEC
183 typename PB_DS_CLASS_C_DEC::node_pointer,
184 typename PB_DS_CLASS_C_DEC::node_pointer>
185PB_DS_CLASS_C_DEC::
186find_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
217PB_DS_CLASS_T_DEC
218inline typename PB_DS_CLASS_C_DEC::size_type
219PB_DS_CLASS_C_DEC::
220black_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
232PB_DS_CLASS_T_DEC
233void
234PB_DS_CLASS_C_DEC::
235split(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
266PB_DS_CLASS_T_DEC
267void
268PB_DS_CLASS_C_DEC::
269split_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
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:524
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:210
_T1 first
second_type is the second bound type
Definition: stl_pair.h:214
_T2 second
first is a copy of the first object
Definition: stl_pair.h:215