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