1// -*- C++ -*- 2 3// Copyright (C) 2005-2013 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 41PB_DS_CLASS_T_DEC 42void 43PB_DS_CLASS_C_DEC:: 44splay(node_pointer p_nd) 45{ 46 while (p_nd->m_p_parent != base_type::m_p_head) 47 { 48#ifdef _GLIBCXX_DEBUG 49 { 50 node_pointer p_head = base_type::m_p_head; 51 assert_special_imp(p_head, __FILE__, __LINE__); 52 } 53#endif 54 55 PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_nd) 56 57 if (p_nd->m_p_parent->m_p_parent == base_type::m_p_head) 58 { 59 base_type::rotate_parent(p_nd); 60 _GLIBCXX_DEBUG_ASSERT(p_nd == this->m_p_head->m_p_parent); 61 } 62 else 63 { 64 const node_pointer p_parent = p_nd->m_p_parent; 65 const node_pointer p_grandparent = p_parent->m_p_parent; 66 67#ifdef _GLIBCXX_DEBUG 68 const size_type total = 69 base_type::recursive_count(p_grandparent); 70 _GLIBCXX_DEBUG_ASSERT(total >= 3); 71#endif 72 73 if (p_parent->m_p_left == p_nd && 74 p_grandparent->m_p_right == p_parent) 75 splay_zig_zag_left(p_nd, p_parent, p_grandparent); 76 else if (p_parent->m_p_right == p_nd && 77 p_grandparent->m_p_left == p_parent) 78 splay_zig_zag_right(p_nd, p_parent, p_grandparent); 79 else if (p_parent->m_p_left == p_nd && 80 p_grandparent->m_p_left == p_parent) 81 splay_zig_zig_left(p_nd, p_parent, p_grandparent); 82 else 83 splay_zig_zig_right(p_nd, p_parent, p_grandparent); 84 _GLIBCXX_DEBUG_ASSERT(total ==this->recursive_count(p_nd)); 85 } 86 87 PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_nd) 88 } 89} 90 91PB_DS_CLASS_T_DEC 92inline void 93PB_DS_CLASS_C_DEC:: 94splay_zig_zag_left(node_pointer p_nd, node_pointer p_parent, 95 node_pointer p_grandparent) 96{ 97 _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent); 98 _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent); 99 100 PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_grandparent) 101 102 _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_left == p_nd && 103 p_grandparent->m_p_right == p_parent); 104 105 splay_zz_start(p_nd, p_parent, p_grandparent); 106 107 node_pointer p_b = p_nd->m_p_right; 108 node_pointer p_c = p_nd->m_p_left; 109 110 p_nd->m_p_right = p_parent; 111 p_parent->m_p_parent = p_nd; 112 113 p_nd->m_p_left = p_grandparent; 114 p_grandparent->m_p_parent = p_nd; 115 116 p_parent->m_p_left = p_b; 117 if (p_b != 0) 118 p_b->m_p_parent = p_parent; 119 120 p_grandparent->m_p_right = p_c; 121 if (p_c != 0) 122 p_c->m_p_parent = p_grandparent; 123 124 splay_zz_end(p_nd, p_parent, p_grandparent); 125} 126 127PB_DS_CLASS_T_DEC 128inline void 129PB_DS_CLASS_C_DEC:: 130splay_zig_zag_right(node_pointer p_nd, node_pointer p_parent, 131 node_pointer p_grandparent) 132{ 133 _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent); 134 _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent); 135 136 PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_grandparent) 137 138 _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_right == p_nd && 139 p_grandparent->m_p_left == p_parent); 140 141 splay_zz_start(p_nd, p_parent, p_grandparent); 142 143 node_pointer p_b = p_nd->m_p_left; 144 node_pointer p_c = p_nd->m_p_right; 145 146 p_nd->m_p_left = p_parent; 147 p_parent->m_p_parent = p_nd; 148 149 p_nd->m_p_right = p_grandparent; 150 p_grandparent->m_p_parent = p_nd; 151 152 p_parent->m_p_right = p_b; 153 if (p_b != 0) 154 p_b->m_p_parent = p_parent; 155 156 p_grandparent->m_p_left = p_c; 157 if (p_c != 0) 158 p_c->m_p_parent = p_grandparent; 159 160 splay_zz_end(p_nd, p_parent, p_grandparent); 161} 162 163PB_DS_CLASS_T_DEC 164inline void 165PB_DS_CLASS_C_DEC:: 166splay_zig_zig_left(node_pointer p_nd, node_pointer p_parent, 167 node_pointer p_grandparent) 168{ 169 _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent); 170 _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent); 171 172 PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_grandparent) 173 174 _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_left == p_nd && 175 p_nd->m_p_parent->m_p_parent->m_p_left == p_nd->m_p_parent); 176 177 splay_zz_start(p_nd, p_parent, p_grandparent); 178 179 node_pointer p_b = p_nd->m_p_right; 180 node_pointer p_c = p_parent->m_p_right; 181 182 p_nd->m_p_right = p_parent; 183 p_parent->m_p_parent = p_nd; 184 185 p_parent->m_p_right = p_grandparent; 186 p_grandparent->m_p_parent = p_parent; 187 188 p_parent->m_p_left = p_b; 189 if (p_b != 0) 190 p_b->m_p_parent = p_parent; 191 192 p_grandparent->m_p_left = p_c; 193 if (p_c != 0) 194 p_c->m_p_parent = p_grandparent; 195 196 splay_zz_end(p_nd, p_parent, p_grandparent); 197} 198 199PB_DS_CLASS_T_DEC 200inline void 201PB_DS_CLASS_C_DEC:: 202splay_zig_zig_right(node_pointer p_nd, node_pointer p_parent, 203 node_pointer p_grandparent) 204{ 205 _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent); 206 _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent); 207 PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_grandparent) 208 _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_right == p_nd && 209 p_nd->m_p_parent->m_p_parent->m_p_right == p_nd->m_p_parent); 210 211 splay_zz_start(p_nd, p_parent, p_grandparent); 212 213 node_pointer p_b = p_nd->m_p_left; 214 node_pointer p_c = p_parent->m_p_left; 215 216 p_nd->m_p_left = p_parent; 217 p_parent->m_p_parent = p_nd; 218 219 p_parent->m_p_left = p_grandparent; 220 p_grandparent->m_p_parent = p_parent; 221 222 p_parent->m_p_right = p_b; 223 if (p_b != 0) 224 p_b->m_p_parent = p_parent; 225 226 p_grandparent->m_p_right = p_c; 227 if (p_c != 0) 228 p_c->m_p_parent = p_grandparent; 229 230 base_type::update_to_top(p_grandparent, (node_update*)this); 231 splay_zz_end(p_nd, p_parent, p_grandparent); 232} 233 234PB_DS_CLASS_T_DEC 235inline void 236PB_DS_CLASS_C_DEC:: 237splay_zz_start(node_pointer p_nd, 238#ifdef _GLIBCXX_DEBUG 239 node_pointer p_parent, 240#else 241 node_pointer /*p_parent*/, 242#endif 243 node_pointer p_grandparent) 244{ 245 _GLIBCXX_DEBUG_ASSERT(p_nd != 0); 246 _GLIBCXX_DEBUG_ASSERT(p_parent != 0); 247 _GLIBCXX_DEBUG_ASSERT(p_grandparent != 0); 248 249 const bool grandparent_head = p_grandparent->m_p_parent == base_type::m_p_head; 250 251 if (grandparent_head) 252 { 253 base_type::m_p_head->m_p_parent = base_type::m_p_head->m_p_parent; 254 p_nd->m_p_parent = base_type::m_p_head; 255 return; 256 } 257 258 node_pointer p_greatgrandparent = p_grandparent->m_p_parent; 259 260 p_nd->m_p_parent = p_greatgrandparent; 261 262 if (p_grandparent == p_greatgrandparent->m_p_left) 263 p_greatgrandparent->m_p_left = p_nd; 264 else 265 p_greatgrandparent->m_p_right = p_nd; 266} 267 268PB_DS_CLASS_T_DEC 269inline void 270PB_DS_CLASS_C_DEC:: 271splay_zz_end(node_pointer p_nd, node_pointer p_parent, 272 node_pointer p_grandparent) 273{ 274 if (p_nd->m_p_parent == base_type::m_p_head) 275 base_type::m_p_head->m_p_parent = p_nd; 276 277 this->apply_update(p_grandparent, (node_update*)this); 278 this->apply_update(p_parent, (node_update*)this); 279 this->apply_update(p_nd, (node_update*)this); 280 PB_DS_ASSERT_BASE_NODE_CONSISTENT(p_nd) 281} 282