1 // -*- C++ -*-
2
3 // Copyright (C) 2005-2021 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 splay_tree_/splay_fn_imps.hpp
38 * Contains an implementation class for splay_tree_.
39 */
40
41 #ifdef PB_DS_CLASS_C_DEC
42
43 PB_DS_CLASS_T_DEC
44 void
45 PB_DS_CLASS_C_DEC::
splay(node_pointer p_nd)46 splay(node_pointer p_nd)
47 {
48 while (p_nd->m_p_parent != base_type::m_p_head)
49 {
50 #ifdef _GLIBCXX_DEBUG
51 {
52 node_pointer p_head = base_type::m_p_head;
53 assert_special_imp(p_head, __FILE__, __LINE__);
54 }
55 #endif
56
57 PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_nd)
58
59 if (p_nd->m_p_parent->m_p_parent == base_type::m_p_head)
60 {
61 base_type::rotate_parent(p_nd);
62 _GLIBCXX_DEBUG_ASSERT(p_nd == this->m_p_head->m_p_parent);
63 }
64 else
65 {
66 const node_pointer p_parent = p_nd->m_p_parent;
67 const node_pointer p_grandparent = p_parent->m_p_parent;
68
69 #ifdef _GLIBCXX_DEBUG
70 const size_type total =
71 base_type::recursive_count(p_grandparent);
72 _GLIBCXX_DEBUG_ASSERT(total >= 3);
73 #endif
74
75 if (p_parent->m_p_left == p_nd &&
76 p_grandparent->m_p_right == p_parent)
77 splay_zig_zag_left(p_nd, p_parent, p_grandparent);
78 else if (p_parent->m_p_right == p_nd &&
79 p_grandparent->m_p_left == p_parent)
80 splay_zig_zag_right(p_nd, p_parent, p_grandparent);
81 else if (p_parent->m_p_left == p_nd &&
82 p_grandparent->m_p_left == p_parent)
83 splay_zig_zig_left(p_nd, p_parent, p_grandparent);
84 else
85 splay_zig_zig_right(p_nd, p_parent, p_grandparent);
86 _GLIBCXX_DEBUG_ASSERT(total ==this->recursive_count(p_nd));
87 }
88
89 PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_nd)
90 }
91 }
92
93 PB_DS_CLASS_T_DEC
94 inline void
95 PB_DS_CLASS_C_DEC::
splay_zig_zag_left(node_pointer p_nd,node_pointer p_parent,node_pointer p_grandparent)96 splay_zig_zag_left(node_pointer p_nd, node_pointer p_parent,
97 node_pointer p_grandparent)
98 {
99 _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent);
100 _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent);
101
102 PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_grandparent)
103
104 _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_left == p_nd &&
105 p_grandparent->m_p_right == p_parent);
106
107 splay_zz_start(p_nd, p_parent, p_grandparent);
108
109 node_pointer p_b = p_nd->m_p_right;
110 node_pointer p_c = p_nd->m_p_left;
111
112 p_nd->m_p_right = p_parent;
113 p_parent->m_p_parent = p_nd;
114
115 p_nd->m_p_left = p_grandparent;
116 p_grandparent->m_p_parent = p_nd;
117
118 p_parent->m_p_left = p_b;
119 if (p_b != 0)
120 p_b->m_p_parent = p_parent;
121
122 p_grandparent->m_p_right = p_c;
123 if (p_c != 0)
124 p_c->m_p_parent = p_grandparent;
125
126 splay_zz_end(p_nd, p_parent, p_grandparent);
127 }
128
129 PB_DS_CLASS_T_DEC
130 inline void
131 PB_DS_CLASS_C_DEC::
splay_zig_zag_right(node_pointer p_nd,node_pointer p_parent,node_pointer p_grandparent)132 splay_zig_zag_right(node_pointer p_nd, node_pointer p_parent,
133 node_pointer p_grandparent)
134 {
135 _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent);
136 _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent);
137
138 PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_grandparent)
139
140 _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_right == p_nd &&
141 p_grandparent->m_p_left == p_parent);
142
143 splay_zz_start(p_nd, p_parent, p_grandparent);
144
145 node_pointer p_b = p_nd->m_p_left;
146 node_pointer p_c = p_nd->m_p_right;
147
148 p_nd->m_p_left = p_parent;
149 p_parent->m_p_parent = p_nd;
150
151 p_nd->m_p_right = p_grandparent;
152 p_grandparent->m_p_parent = p_nd;
153
154 p_parent->m_p_right = p_b;
155 if (p_b != 0)
156 p_b->m_p_parent = p_parent;
157
158 p_grandparent->m_p_left = p_c;
159 if (p_c != 0)
160 p_c->m_p_parent = p_grandparent;
161
162 splay_zz_end(p_nd, p_parent, p_grandparent);
163 }
164
165 PB_DS_CLASS_T_DEC
166 inline void
167 PB_DS_CLASS_C_DEC::
splay_zig_zig_left(node_pointer p_nd,node_pointer p_parent,node_pointer p_grandparent)168 splay_zig_zig_left(node_pointer p_nd, node_pointer p_parent,
169 node_pointer p_grandparent)
170 {
171 _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent);
172 _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent);
173
174 PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_grandparent)
175
176 _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_left == p_nd &&
177 p_nd->m_p_parent->m_p_parent->m_p_left == p_nd->m_p_parent);
178
179 splay_zz_start(p_nd, p_parent, p_grandparent);
180
181 node_pointer p_b = p_nd->m_p_right;
182 node_pointer p_c = p_parent->m_p_right;
183
184 p_nd->m_p_right = p_parent;
185 p_parent->m_p_parent = p_nd;
186
187 p_parent->m_p_right = p_grandparent;
188 p_grandparent->m_p_parent = p_parent;
189
190 p_parent->m_p_left = p_b;
191 if (p_b != 0)
192 p_b->m_p_parent = p_parent;
193
194 p_grandparent->m_p_left = p_c;
195 if (p_c != 0)
196 p_c->m_p_parent = p_grandparent;
197
198 splay_zz_end(p_nd, p_parent, p_grandparent);
199 }
200
201 PB_DS_CLASS_T_DEC
202 inline void
203 PB_DS_CLASS_C_DEC::
splay_zig_zig_right(node_pointer p_nd,node_pointer p_parent,node_pointer p_grandparent)204 splay_zig_zig_right(node_pointer p_nd, node_pointer p_parent,
205 node_pointer p_grandparent)
206 {
207 _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent);
208 _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent);
209 PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_grandparent)
210 _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_right == p_nd &&
211 p_nd->m_p_parent->m_p_parent->m_p_right == p_nd->m_p_parent);
212
213 splay_zz_start(p_nd, p_parent, p_grandparent);
214
215 node_pointer p_b = p_nd->m_p_left;
216 node_pointer p_c = p_parent->m_p_left;
217
218 p_nd->m_p_left = p_parent;
219 p_parent->m_p_parent = p_nd;
220
221 p_parent->m_p_left = p_grandparent;
222 p_grandparent->m_p_parent = p_parent;
223
224 p_parent->m_p_right = p_b;
225 if (p_b != 0)
226 p_b->m_p_parent = p_parent;
227
228 p_grandparent->m_p_right = p_c;
229 if (p_c != 0)
230 p_c->m_p_parent = p_grandparent;
231
232 base_type::update_to_top(p_grandparent, (node_update*)this);
233 splay_zz_end(p_nd, p_parent, p_grandparent);
234 }
235
236 PB_DS_CLASS_T_DEC
237 inline void
238 PB_DS_CLASS_C_DEC::
splay_zz_start(node_pointer p_nd,node_pointer p_parent,node_pointer p_grandparent)239 splay_zz_start(node_pointer p_nd,
240 #ifdef _GLIBCXX_DEBUG
241 node_pointer p_parent,
242 #else
243 node_pointer /*p_parent*/,
244 #endif
245 node_pointer p_grandparent)
246 {
247 _GLIBCXX_DEBUG_ASSERT(p_nd != 0);
248 _GLIBCXX_DEBUG_ASSERT(p_parent != 0);
249 _GLIBCXX_DEBUG_ASSERT(p_grandparent != 0);
250
251 const bool grandparent_head = p_grandparent->m_p_parent == base_type::m_p_head;
252
253 if (grandparent_head)
254 {
255 base_type::m_p_head->m_p_parent = base_type::m_p_head->m_p_parent;
256 p_nd->m_p_parent = base_type::m_p_head;
257 return;
258 }
259
260 node_pointer p_greatgrandparent = p_grandparent->m_p_parent;
261
262 p_nd->m_p_parent = p_greatgrandparent;
263
264 if (p_grandparent == p_greatgrandparent->m_p_left)
265 p_greatgrandparent->m_p_left = p_nd;
266 else
267 p_greatgrandparent->m_p_right = p_nd;
268 }
269
270 PB_DS_CLASS_T_DEC
271 inline void
272 PB_DS_CLASS_C_DEC::
splay_zz_end(node_pointer p_nd,node_pointer p_parent,node_pointer p_grandparent)273 splay_zz_end(node_pointer p_nd, node_pointer p_parent,
274 node_pointer p_grandparent)
275 {
276 if (p_nd->m_p_parent == base_type::m_p_head)
277 base_type::m_p_head->m_p_parent = p_nd;
278
279 this->apply_update(p_grandparent, (node_update*)this);
280 this->apply_update(p_parent, (node_update*)this);
281 this->apply_update(p_nd, (node_update*)this);
282 PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_nd)
283 }
284 #endif
285