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