1// -*- C++ -*-
2
3// Copyright (C) 2005, 2006 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 2, 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// You should have received a copy of the GNU General Public License
17// along with this library; see the file COPYING.  If not, write to
18// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19// MA 02111-1307, USA.
20
21// As a special exception, you may use this file as part of a free
22// software library without restriction.  Specifically, if other files
23// instantiate templates or use macros or inline functions from this
24// file, or you compile this file and link it with other files to
25// produce an executable, this file does not by itself cause the
26// resulting executable to be covered by the GNU General Public
27// License.  This exception does not however invalidate any other
28// reasons why the executable file might be covered by the GNU General
29// Public License.
30
31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
32
33// Permission to use, copy, modify, sell, and distribute this software
34// is hereby granted without fee, provided that the above copyright
35// notice appears in all copies, and that both that copyright notice
36// and this permission notice appear in supporting documentation. None
37// of the above authors, nor IBM Haifa Research Laboratories, make any
38// representation about the suitability of this software for any
39// purpose. It is provided "as is" without express or implied
40// warranty.
41
42/**
43 * @file splay_fn_imps.hpp
44 * Contains an implementation class for splay_tree_.
45 */
46
47PB_DS_CLASS_T_DEC
48void
49PB_DS_CLASS_C_DEC::
50splay(node_pointer p_nd)
51{
52  while (p_nd->m_p_parent != base_type::m_p_head)
53    {
54#ifdef _GLIBCXX_DEBUG
55      {
56	node_pointer p_head = base_type::m_p_head;
57	assert_special_imp(p_head);
58      }
59#endif
60
61      _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd);)
62
63        if (p_nd->m_p_parent->m_p_parent == base_type::m_p_head)
64	  {
65            base_type::rotate_parent(p_nd);
66            _GLIBCXX_DEBUG_ASSERT(p_nd == this->m_p_head->m_p_parent);
67	  }
68        else
69	  {
70            const node_pointer p_parent = p_nd->m_p_parent;
71            const node_pointer p_grandparent = p_parent->m_p_parent;
72
73#ifdef _GLIBCXX_DEBUG
74            const size_type total =
75	      base_type::recursive_count(p_grandparent);
76            _GLIBCXX_DEBUG_ASSERT(total >= 3);
77#endif
78
79            if (p_parent->m_p_left == p_nd &&
80		p_grandparent->m_p_right == p_parent)
81	      splay_zig_zag_left(p_nd, p_parent, p_grandparent);
82            else if (p_parent->m_p_right == p_nd &&
83		     p_grandparent->m_p_left == p_parent)
84	      splay_zig_zag_right(p_nd, p_parent, p_grandparent);
85            else if (p_parent->m_p_left == p_nd &&
86		     p_grandparent->m_p_left == p_parent)
87	      splay_zig_zig_left(p_nd, p_parent, p_grandparent);
88            else
89	      splay_zig_zig_right(p_nd, p_parent, p_grandparent);
90            _GLIBCXX_DEBUG_ASSERT(total ==this->recursive_count(p_nd));
91	  }
92
93      _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd);)
94  }
95}
96
97PB_DS_CLASS_T_DEC
98inline void
99PB_DS_CLASS_C_DEC::
100splay_zig_zag_left(node_pointer p_nd, node_pointer p_parent,
101		   node_pointer p_grandparent)
102{
103  _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent);
104  _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent);
105
106  _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent);)
107
108  _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_left == p_nd &&
109		        p_grandparent->m_p_right == p_parent);
110
111  splay_zz_start(p_nd, p_parent, p_grandparent);
112
113  node_pointer p_b = p_nd->m_p_right;
114  node_pointer p_c = p_nd->m_p_left;
115
116  p_nd->m_p_right = p_parent;
117  p_parent->m_p_parent = p_nd;
118
119  p_nd->m_p_left = p_grandparent;
120  p_grandparent->m_p_parent = p_nd;
121
122  p_parent->m_p_left = p_b;
123  if (p_b != NULL)
124    p_b->m_p_parent = p_parent;
125
126  p_grandparent->m_p_right = p_c;
127  if (p_c != NULL)
128    p_c->m_p_parent = p_grandparent;
129
130  splay_zz_end(p_nd, p_parent, p_grandparent);
131}
132
133PB_DS_CLASS_T_DEC
134inline void
135PB_DS_CLASS_C_DEC::
136splay_zig_zag_right(node_pointer p_nd, node_pointer p_parent,
137		    node_pointer p_grandparent)
138{
139  _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent);
140  _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent);
141
142  _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent);)
143
144  _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_right == p_nd &&
145	  	        p_grandparent->m_p_left == p_parent);
146
147  splay_zz_start(p_nd, p_parent, p_grandparent);
148
149  node_pointer p_b = p_nd->m_p_left;
150  node_pointer p_c = p_nd->m_p_right;
151
152  p_nd->m_p_left = p_parent;
153  p_parent->m_p_parent = p_nd;
154
155  p_nd->m_p_right = p_grandparent;
156  p_grandparent->m_p_parent = p_nd;
157
158  p_parent->m_p_right = p_b;
159  if (p_b != NULL)
160    p_b->m_p_parent = p_parent;
161
162  p_grandparent->m_p_left = p_c;
163  if (p_c != NULL)
164    p_c->m_p_parent = p_grandparent;
165
166  splay_zz_end(p_nd, p_parent, p_grandparent);
167}
168
169PB_DS_CLASS_T_DEC
170inline void
171PB_DS_CLASS_C_DEC::
172splay_zig_zig_left(node_pointer p_nd, node_pointer p_parent,
173		   node_pointer p_grandparent)
174{
175  _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent);
176  _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent);
177
178  _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent);)
179
180  _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_left == p_nd &&
181		     p_nd->m_p_parent->m_p_parent->m_p_left == p_nd->m_p_parent);
182
183  splay_zz_start(p_nd, p_parent, p_grandparent);
184
185  node_pointer p_b = p_nd->m_p_right;
186  node_pointer p_c = p_parent->m_p_right;
187
188  p_nd->m_p_right = p_parent;
189  p_parent->m_p_parent = p_nd;
190
191  p_parent->m_p_right = p_grandparent;
192  p_grandparent->m_p_parent = p_parent;
193
194  p_parent->m_p_left = p_b;
195  if (p_b != NULL)
196    p_b->m_p_parent = p_parent;
197
198  p_grandparent->m_p_left = p_c;
199  if (p_c != NULL)
200    p_c->m_p_parent = p_grandparent;
201
202  splay_zz_end(p_nd, p_parent, p_grandparent);
203}
204
205PB_DS_CLASS_T_DEC
206inline void
207PB_DS_CLASS_C_DEC::
208splay_zig_zig_right(node_pointer p_nd, node_pointer p_parent,
209		    node_pointer p_grandparent)
210{
211  _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent);
212  _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent);
213  _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent);)
214  _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_right == p_nd &&
215	          p_nd->m_p_parent->m_p_parent->m_p_right == p_nd->m_p_parent);
216
217  splay_zz_start(p_nd, p_parent, p_grandparent);
218
219  node_pointer p_b = p_nd->m_p_left;
220  node_pointer p_c = p_parent->m_p_left;
221
222  p_nd->m_p_left = p_parent;
223  p_parent->m_p_parent = p_nd;
224
225  p_parent->m_p_left = p_grandparent;
226  p_grandparent->m_p_parent = p_parent;
227
228  p_parent->m_p_right = p_b;
229  if (p_b != NULL)
230    p_b->m_p_parent = p_parent;
231
232  p_grandparent->m_p_right = p_c;
233  if (p_c != NULL)
234    p_c->m_p_parent = p_grandparent;
235
236  base_type::update_to_top(p_grandparent, (node_update* )this);
237  splay_zz_end(p_nd, p_parent, p_grandparent);
238}
239
240PB_DS_CLASS_T_DEC
241inline void
242PB_DS_CLASS_C_DEC::
243splay_zz_start(node_pointer p_nd,
244#ifdef _GLIBCXX_DEBUG
245	       node_pointer p_parent,
246#else
247	       node_pointer /*p_parent*/,
248#endif
249	       node_pointer p_grandparent)
250{
251  _GLIBCXX_DEBUG_ASSERT(p_nd != NULL);
252  _GLIBCXX_DEBUG_ASSERT(p_parent != NULL);
253  _GLIBCXX_DEBUG_ASSERT(p_grandparent != NULL);
254
255  const bool grandparent_head = p_grandparent->m_p_parent == base_type::m_p_head;
256
257  if (grandparent_head)
258    {
259      base_type::m_p_head->m_p_parent = base_type::m_p_head->m_p_parent;
260      p_nd->m_p_parent = base_type::m_p_head;
261      return;
262    }
263
264  node_pointer p_greatgrandparent = p_grandparent->m_p_parent;
265
266  p_nd->m_p_parent = p_greatgrandparent;
267
268  if (p_grandparent == p_greatgrandparent->m_p_left)
269    p_greatgrandparent->m_p_left = p_nd;
270  else
271    p_greatgrandparent->m_p_right = p_nd;
272}
273
274PB_DS_CLASS_T_DEC
275inline void
276PB_DS_CLASS_C_DEC::
277splay_zz_end(node_pointer p_nd, node_pointer p_parent,
278	     node_pointer p_grandparent)
279{
280  if (p_nd->m_p_parent == base_type::m_p_head)
281    base_type::m_p_head->m_p_parent = p_nd;
282
283  apply_update(p_grandparent, (node_update* )this);
284  apply_update(p_parent, (node_update* )this);
285  apply_update(p_nd, (node_update* )this);
286
287  _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd);)
288}
289
290