1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2018 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 PB_DS_CLASS_T_DEC 42 void 43 PB_DS_CLASS_C_DEC:: 44 splay(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 91 PB_DS_CLASS_T_DEC 92 inline void 93 PB_DS_CLASS_C_DEC:: 94 splay_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 127 PB_DS_CLASS_T_DEC 128 inline void 129 PB_DS_CLASS_C_DEC:: 130 splay_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 163 PB_DS_CLASS_T_DEC 164 inline void 165 PB_DS_CLASS_C_DEC:: 166 splay_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 199 PB_DS_CLASS_T_DEC 200 inline void 201 PB_DS_CLASS_C_DEC:: 202 splay_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 234 PB_DS_CLASS_T_DEC 235 inline void 236 PB_DS_CLASS_C_DEC:: 237 splay_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 268 PB_DS_CLASS_T_DEC 269 inline void 270 PB_DS_CLASS_C_DEC:: 271 splay_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