libstdc++
splay_fn_imps.hpp
Go to the documentation of this file.
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
43PB_DS_CLASS_T_DEC
44void
45PB_DS_CLASS_C_DEC::
46splay(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
93PB_DS_CLASS_T_DEC
94inline void
95PB_DS_CLASS_C_DEC::
96splay_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
129PB_DS_CLASS_T_DEC
130inline void
131PB_DS_CLASS_C_DEC::
132splay_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
165PB_DS_CLASS_T_DEC
166inline void
167PB_DS_CLASS_C_DEC::
168splay_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
201PB_DS_CLASS_T_DEC
202inline void
203PB_DS_CLASS_C_DEC::
204splay_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
236PB_DS_CLASS_T_DEC
237inline void
238PB_DS_CLASS_C_DEC::
239splay_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
270PB_DS_CLASS_T_DEC
271inline void
272PB_DS_CLASS_C_DEC::
273splay_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