libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_fn_imps.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2016 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 }