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 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
285