1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file splay_fn_imps.hpp 44169691Skan * Contains an implementation class for splay_tree_. 45169691Skan */ 46169691Skan 47169691SkanPB_DS_CLASS_T_DEC 48169691Skanvoid 49169691SkanPB_DS_CLASS_C_DEC:: 50169691Skansplay(node_pointer p_nd) 51169691Skan{ 52169691Skan while (p_nd->m_p_parent != base_type::m_p_head) 53169691Skan { 54169691Skan#ifdef _GLIBCXX_DEBUG 55169691Skan { 56169691Skan node_pointer p_head = base_type::m_p_head; 57169691Skan assert_special_imp(p_head); 58169691Skan } 59169691Skan#endif 60169691Skan 61169691Skan _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd);) 62169691Skan 63169691Skan if (p_nd->m_p_parent->m_p_parent == base_type::m_p_head) 64169691Skan { 65169691Skan base_type::rotate_parent(p_nd); 66169691Skan _GLIBCXX_DEBUG_ASSERT(p_nd == this->m_p_head->m_p_parent); 67169691Skan } 68169691Skan else 69169691Skan { 70169691Skan const node_pointer p_parent = p_nd->m_p_parent; 71169691Skan const node_pointer p_grandparent = p_parent->m_p_parent; 72169691Skan 73169691Skan#ifdef _GLIBCXX_DEBUG 74169691Skan const size_type total = 75169691Skan base_type::recursive_count(p_grandparent); 76169691Skan _GLIBCXX_DEBUG_ASSERT(total >= 3); 77169691Skan#endif 78169691Skan 79169691Skan if (p_parent->m_p_left == p_nd && 80169691Skan p_grandparent->m_p_right == p_parent) 81169691Skan splay_zig_zag_left(p_nd, p_parent, p_grandparent); 82169691Skan else if (p_parent->m_p_right == p_nd && 83169691Skan p_grandparent->m_p_left == p_parent) 84169691Skan splay_zig_zag_right(p_nd, p_parent, p_grandparent); 85169691Skan else if (p_parent->m_p_left == p_nd && 86169691Skan p_grandparent->m_p_left == p_parent) 87169691Skan splay_zig_zig_left(p_nd, p_parent, p_grandparent); 88169691Skan else 89169691Skan splay_zig_zig_right(p_nd, p_parent, p_grandparent); 90169691Skan _GLIBCXX_DEBUG_ASSERT(total ==this->recursive_count(p_nd)); 91169691Skan } 92169691Skan 93169691Skan _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd);) 94169691Skan } 95169691Skan} 96169691Skan 97169691SkanPB_DS_CLASS_T_DEC 98169691Skaninline void 99169691SkanPB_DS_CLASS_C_DEC:: 100169691Skansplay_zig_zag_left(node_pointer p_nd, node_pointer p_parent, 101169691Skan node_pointer p_grandparent) 102169691Skan{ 103169691Skan _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent); 104169691Skan _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent); 105169691Skan 106169691Skan _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent);) 107169691Skan 108169691Skan _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_left == p_nd && 109169691Skan p_grandparent->m_p_right == p_parent); 110169691Skan 111169691Skan splay_zz_start(p_nd, p_parent, p_grandparent); 112169691Skan 113169691Skan node_pointer p_b = p_nd->m_p_right; 114169691Skan node_pointer p_c = p_nd->m_p_left; 115169691Skan 116169691Skan p_nd->m_p_right = p_parent; 117169691Skan p_parent->m_p_parent = p_nd; 118169691Skan 119169691Skan p_nd->m_p_left = p_grandparent; 120169691Skan p_grandparent->m_p_parent = p_nd; 121169691Skan 122169691Skan p_parent->m_p_left = p_b; 123169691Skan if (p_b != NULL) 124169691Skan p_b->m_p_parent = p_parent; 125169691Skan 126169691Skan p_grandparent->m_p_right = p_c; 127169691Skan if (p_c != NULL) 128169691Skan p_c->m_p_parent = p_grandparent; 129169691Skan 130169691Skan splay_zz_end(p_nd, p_parent, p_grandparent); 131169691Skan} 132169691Skan 133169691SkanPB_DS_CLASS_T_DEC 134169691Skaninline void 135169691SkanPB_DS_CLASS_C_DEC:: 136169691Skansplay_zig_zag_right(node_pointer p_nd, node_pointer p_parent, 137169691Skan node_pointer p_grandparent) 138169691Skan{ 139169691Skan _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent); 140169691Skan _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent); 141169691Skan 142169691Skan _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent);) 143169691Skan 144169691Skan _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_right == p_nd && 145169691Skan p_grandparent->m_p_left == p_parent); 146169691Skan 147169691Skan splay_zz_start(p_nd, p_parent, p_grandparent); 148169691Skan 149169691Skan node_pointer p_b = p_nd->m_p_left; 150169691Skan node_pointer p_c = p_nd->m_p_right; 151169691Skan 152169691Skan p_nd->m_p_left = p_parent; 153169691Skan p_parent->m_p_parent = p_nd; 154169691Skan 155169691Skan p_nd->m_p_right = p_grandparent; 156169691Skan p_grandparent->m_p_parent = p_nd; 157169691Skan 158169691Skan p_parent->m_p_right = p_b; 159169691Skan if (p_b != NULL) 160169691Skan p_b->m_p_parent = p_parent; 161169691Skan 162169691Skan p_grandparent->m_p_left = p_c; 163169691Skan if (p_c != NULL) 164169691Skan p_c->m_p_parent = p_grandparent; 165169691Skan 166169691Skan splay_zz_end(p_nd, p_parent, p_grandparent); 167169691Skan} 168169691Skan 169169691SkanPB_DS_CLASS_T_DEC 170169691Skaninline void 171169691SkanPB_DS_CLASS_C_DEC:: 172169691Skansplay_zig_zig_left(node_pointer p_nd, node_pointer p_parent, 173169691Skan node_pointer p_grandparent) 174169691Skan{ 175169691Skan _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent); 176169691Skan _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent); 177169691Skan 178169691Skan _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent);) 179169691Skan 180169691Skan _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_left == p_nd && 181169691Skan p_nd->m_p_parent->m_p_parent->m_p_left == p_nd->m_p_parent); 182169691Skan 183169691Skan splay_zz_start(p_nd, p_parent, p_grandparent); 184169691Skan 185169691Skan node_pointer p_b = p_nd->m_p_right; 186169691Skan node_pointer p_c = p_parent->m_p_right; 187169691Skan 188169691Skan p_nd->m_p_right = p_parent; 189169691Skan p_parent->m_p_parent = p_nd; 190169691Skan 191169691Skan p_parent->m_p_right = p_grandparent; 192169691Skan p_grandparent->m_p_parent = p_parent; 193169691Skan 194169691Skan p_parent->m_p_left = p_b; 195169691Skan if (p_b != NULL) 196169691Skan p_b->m_p_parent = p_parent; 197169691Skan 198169691Skan p_grandparent->m_p_left = p_c; 199169691Skan if (p_c != NULL) 200169691Skan p_c->m_p_parent = p_grandparent; 201169691Skan 202169691Skan splay_zz_end(p_nd, p_parent, p_grandparent); 203169691Skan} 204169691Skan 205169691SkanPB_DS_CLASS_T_DEC 206169691Skaninline void 207169691SkanPB_DS_CLASS_C_DEC:: 208169691Skansplay_zig_zig_right(node_pointer p_nd, node_pointer p_parent, 209169691Skan node_pointer p_grandparent) 210169691Skan{ 211169691Skan _GLIBCXX_DEBUG_ASSERT(p_parent == p_nd->m_p_parent); 212169691Skan _GLIBCXX_DEBUG_ASSERT(p_grandparent == p_parent->m_p_parent); 213169691Skan _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_grandparent);) 214169691Skan _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_right == p_nd && 215169691Skan p_nd->m_p_parent->m_p_parent->m_p_right == p_nd->m_p_parent); 216169691Skan 217169691Skan splay_zz_start(p_nd, p_parent, p_grandparent); 218169691Skan 219169691Skan node_pointer p_b = p_nd->m_p_left; 220169691Skan node_pointer p_c = p_parent->m_p_left; 221169691Skan 222169691Skan p_nd->m_p_left = p_parent; 223169691Skan p_parent->m_p_parent = p_nd; 224169691Skan 225169691Skan p_parent->m_p_left = p_grandparent; 226169691Skan p_grandparent->m_p_parent = p_parent; 227169691Skan 228169691Skan p_parent->m_p_right = p_b; 229169691Skan if (p_b != NULL) 230169691Skan p_b->m_p_parent = p_parent; 231169691Skan 232169691Skan p_grandparent->m_p_right = p_c; 233169691Skan if (p_c != NULL) 234169691Skan p_c->m_p_parent = p_grandparent; 235169691Skan 236169691Skan base_type::update_to_top(p_grandparent, (node_update* )this); 237169691Skan splay_zz_end(p_nd, p_parent, p_grandparent); 238169691Skan} 239169691Skan 240169691SkanPB_DS_CLASS_T_DEC 241169691Skaninline void 242169691SkanPB_DS_CLASS_C_DEC:: 243169691Skansplay_zz_start(node_pointer p_nd, 244169691Skan#ifdef _GLIBCXX_DEBUG 245169691Skan node_pointer p_parent, 246169691Skan#else 247169691Skan node_pointer /*p_parent*/, 248169691Skan#endif 249169691Skan node_pointer p_grandparent) 250169691Skan{ 251169691Skan _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); 252169691Skan _GLIBCXX_DEBUG_ASSERT(p_parent != NULL); 253169691Skan _GLIBCXX_DEBUG_ASSERT(p_grandparent != NULL); 254169691Skan 255169691Skan const bool grandparent_head = p_grandparent->m_p_parent == base_type::m_p_head; 256169691Skan 257169691Skan if (grandparent_head) 258169691Skan { 259169691Skan base_type::m_p_head->m_p_parent = base_type::m_p_head->m_p_parent; 260169691Skan p_nd->m_p_parent = base_type::m_p_head; 261169691Skan return; 262169691Skan } 263169691Skan 264169691Skan node_pointer p_greatgrandparent = p_grandparent->m_p_parent; 265169691Skan 266169691Skan p_nd->m_p_parent = p_greatgrandparent; 267169691Skan 268169691Skan if (p_grandparent == p_greatgrandparent->m_p_left) 269169691Skan p_greatgrandparent->m_p_left = p_nd; 270169691Skan else 271169691Skan p_greatgrandparent->m_p_right = p_nd; 272169691Skan} 273169691Skan 274169691SkanPB_DS_CLASS_T_DEC 275169691Skaninline void 276169691SkanPB_DS_CLASS_C_DEC:: 277169691Skansplay_zz_end(node_pointer p_nd, node_pointer p_parent, 278169691Skan node_pointer p_grandparent) 279169691Skan{ 280169691Skan if (p_nd->m_p_parent == base_type::m_p_head) 281169691Skan base_type::m_p_head->m_p_parent = p_nd; 282169691Skan 283169691Skan apply_update(p_grandparent, (node_update* )this); 284169691Skan apply_update(p_parent, (node_update* )this); 285169691Skan apply_update(p_nd, (node_update* )this); 286169691Skan 287169691Skan _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd);) 288169691Skan} 289169691Skan 290