3 // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
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
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.
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.
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
31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
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
43 * @file splay_fn_imps.hpp
44 * Contains an implementation class for splay_tree_.
50 splay(node_pointer p_nd
)
52 while (p_nd
->m_p_parent
!= base_type::m_p_head
)
56 node_pointer p_head
= base_type::m_p_head
;
57 assert_special_imp(p_head
);
61 _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd
);)
63 if (p_nd
->m_p_parent
->m_p_parent
== base_type::m_p_head
)
65 base_type::rotate_parent(p_nd
);
66 _GLIBCXX_DEBUG_ASSERT(p_nd
== this->m_p_head
->m_p_parent
);
70 const node_pointer p_parent
= p_nd
->m_p_parent
;
71 const node_pointer p_grandparent
= p_parent
->m_p_parent
;
74 const size_type total
=
75 base_type::recursive_count(p_grandparent
);
76 _GLIBCXX_DEBUG_ASSERT(total
>= 3);
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
);
89 splay_zig_zig_right(p_nd
, p_parent
, p_grandparent
);
90 _GLIBCXX_DEBUG_ASSERT(total
==this->recursive_count(p_nd
));
93 _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd
);)
100 splay_zig_zag_left(node_pointer p_nd
, node_pointer p_parent
,
101 node_pointer p_grandparent
)
103 _GLIBCXX_DEBUG_ASSERT(p_parent
== p_nd
->m_p_parent
);
104 _GLIBCXX_DEBUG_ASSERT(p_grandparent
== p_parent
->m_p_parent
);
106 _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent
);)
108 _GLIBCXX_DEBUG_ASSERT(p_parent
->m_p_left
== p_nd
&&
109 p_grandparent
->m_p_right
== p_parent
);
111 splay_zz_start(p_nd
, p_parent
, p_grandparent
);
113 node_pointer p_b
= p_nd
->m_p_right
;
114 node_pointer p_c
= p_nd
->m_p_left
;
116 p_nd
->m_p_right
= p_parent
;
117 p_parent
->m_p_parent
= p_nd
;
119 p_nd
->m_p_left
= p_grandparent
;
120 p_grandparent
->m_p_parent
= p_nd
;
122 p_parent
->m_p_left
= p_b
;
124 p_b
->m_p_parent
= p_parent
;
126 p_grandparent
->m_p_right
= p_c
;
128 p_c
->m_p_parent
= p_grandparent
;
130 splay_zz_end(p_nd
, p_parent
, p_grandparent
);
136 splay_zig_zag_right(node_pointer p_nd
, node_pointer p_parent
,
137 node_pointer p_grandparent
)
139 _GLIBCXX_DEBUG_ASSERT(p_parent
== p_nd
->m_p_parent
);
140 _GLIBCXX_DEBUG_ASSERT(p_grandparent
== p_parent
->m_p_parent
);
142 _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent
);)
144 _GLIBCXX_DEBUG_ASSERT(p_parent
->m_p_right
== p_nd
&&
145 p_grandparent
->m_p_left
== p_parent
);
147 splay_zz_start(p_nd
, p_parent
, p_grandparent
);
149 node_pointer p_b
= p_nd
->m_p_left
;
150 node_pointer p_c
= p_nd
->m_p_right
;
152 p_nd
->m_p_left
= p_parent
;
153 p_parent
->m_p_parent
= p_nd
;
155 p_nd
->m_p_right
= p_grandparent
;
156 p_grandparent
->m_p_parent
= p_nd
;
158 p_parent
->m_p_right
= p_b
;
160 p_b
->m_p_parent
= p_parent
;
162 p_grandparent
->m_p_left
= p_c
;
164 p_c
->m_p_parent
= p_grandparent
;
166 splay_zz_end(p_nd
, p_parent
, p_grandparent
);
172 splay_zig_zig_left(node_pointer p_nd
, node_pointer p_parent
,
173 node_pointer p_grandparent
)
175 _GLIBCXX_DEBUG_ASSERT(p_parent
== p_nd
->m_p_parent
);
176 _GLIBCXX_DEBUG_ASSERT(p_grandparent
== p_parent
->m_p_parent
);
178 _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent
);)
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
);
183 splay_zz_start(p_nd
, p_parent
, p_grandparent
);
185 node_pointer p_b
= p_nd
->m_p_right
;
186 node_pointer p_c
= p_parent
->m_p_right
;
188 p_nd
->m_p_right
= p_parent
;
189 p_parent
->m_p_parent
= p_nd
;
191 p_parent
->m_p_right
= p_grandparent
;
192 p_grandparent
->m_p_parent
= p_parent
;
194 p_parent
->m_p_left
= p_b
;
196 p_b
->m_p_parent
= p_parent
;
198 p_grandparent
->m_p_left
= p_c
;
200 p_c
->m_p_parent
= p_grandparent
;
202 splay_zz_end(p_nd
, p_parent
, p_grandparent
);
208 splay_zig_zig_right(node_pointer p_nd
, node_pointer p_parent
,
209 node_pointer p_grandparent
)
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
);
217 splay_zz_start(p_nd
, p_parent
, p_grandparent
);
219 node_pointer p_b
= p_nd
->m_p_left
;
220 node_pointer p_c
= p_parent
->m_p_left
;
222 p_nd
->m_p_left
= p_parent
;
223 p_parent
->m_p_parent
= p_nd
;
225 p_parent
->m_p_left
= p_grandparent
;
226 p_grandparent
->m_p_parent
= p_parent
;
228 p_parent
->m_p_right
= p_b
;
230 p_b
->m_p_parent
= p_parent
;
232 p_grandparent
->m_p_right
= p_c
;
234 p_c
->m_p_parent
= p_grandparent
;
236 base_type::update_to_top(p_grandparent
, (node_update
* )this);
237 splay_zz_end(p_nd
, p_parent
, p_grandparent
);
243 splay_zz_start(node_pointer p_nd
,
244 #ifdef _GLIBCXX_DEBUG
245 node_pointer p_parent
,
247 node_pointer
/*p_parent*/,
249 node_pointer p_grandparent
)
251 _GLIBCXX_DEBUG_ASSERT(p_nd
!= NULL
);
252 _GLIBCXX_DEBUG_ASSERT(p_parent
!= NULL
);
253 _GLIBCXX_DEBUG_ASSERT(p_grandparent
!= NULL
);
255 const bool grandparent_head
= p_grandparent
->m_p_parent
== base_type::m_p_head
;
257 if (grandparent_head
)
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
;
264 node_pointer p_greatgrandparent
= p_grandparent
->m_p_parent
;
266 p_nd
->m_p_parent
= p_greatgrandparent
;
268 if (p_grandparent
== p_greatgrandparent
->m_p_left
)
269 p_greatgrandparent
->m_p_left
= p_nd
;
271 p_greatgrandparent
->m_p_right
= p_nd
;
277 splay_zz_end(node_pointer p_nd
, node_pointer p_parent
,
278 node_pointer p_grandparent
)
280 if (p_nd
->m_p_parent
== base_type::m_p_head
)
281 base_type::m_p_head
->m_p_parent
= p_nd
;
283 apply_update(p_grandparent
, (node_update
* )this);
284 apply_update(p_parent
, (node_update
* )this);
285 apply_update(p_nd
, (node_update
* )this);
287 _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd
);)