libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009, 2010 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 split_join_fn_imps.hpp
  38  * Contains an implementation for rb_tree_.
  39  */
  40
  41 PB_DS_CLASS_T_DEC
  42 inline void
  43 PB_DS_CLASS_C_DEC::
  44 join(PB_DS_CLASS_C_DEC& other)
  45 {
  46   _GLIBCXX_DEBUG_ONLY(assert_valid();)
  47   _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
  48   _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();)
  49   if (base_type::join_prep(other) == false)
  50     {
  51       _GLIBCXX_DEBUG_ONLY(assert_valid();)
  52       _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
  53       return;
  54     }
  55
  56   const node_pointer p_x = other.split_min();
  57   join_imp(p_x, other.m_p_head->m_p_parent);
  58   base_type::join_finish(other);
  59   _GLIBCXX_DEBUG_ONLY(assert_valid();)
  60   _GLIBCXX_DEBUG_ONLY(base_type::assert_valid();)
  61   _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
  62   _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();)
  63  }
  64
  65 PB_DS_CLASS_T_DEC
  66 void
  67 PB_DS_CLASS_C_DEC::
  68 join_imp(node_pointer p_x, node_pointer p_r)
  69 {
  70   _GLIBCXX_DEBUG_ASSERT(p_x != 0);
  71   if (p_r != 0)
  72     p_r->m_red = false;
  73
  74   const size_type h = black_height(base_type::m_p_head->m_p_parent);
  75   const size_type other_h = black_height(p_r);
  76   node_pointer p_x_l;
  77   node_pointer p_x_r;
  78   std::pair<node_pointer, node_pointer> join_pos;
  79   const bool right_join = h >= other_h;
  80   if (right_join)
  81     {
  82       join_pos = find_join_pos_right(base_type::m_p_head->m_p_parent,
  83                                      h, other_h);
  84       p_x_l = join_pos.first;
  85       p_x_r = p_r;
  86     }
  87   else
  88     {
  89       p_x_l = base_type::m_p_head->m_p_parent;
  90       base_type::m_p_head->m_p_parent = p_r;
  91       if (p_r != 0)
  92         p_r->m_p_parent = base_type::m_p_head;
  93
  94       join_pos = find_join_pos_left(base_type::m_p_head->m_p_parent,
  95                                     h, other_h);
  96       p_x_r = join_pos.first;
  97     }
  98
  99   node_pointer p_parent = join_pos.second;
 100   if (p_parent == base_type::m_p_head)
 101     {
 102       base_type::m_p_head->m_p_parent = p_x;
 103       p_x->m_p_parent = base_type::m_p_head;
 104     }
 105   else
 106     {
 107       p_x->m_p_parent = p_parent;
 108       if (right_join)
 109         p_x->m_p_parent->m_p_right = p_x;
 110       else
 111         p_x->m_p_parent->m_p_left = p_x;
 112     }
 113
 114   p_x->m_p_left = p_x_l;
 115   if (p_x_l != 0)
 116     p_x_l->m_p_parent = p_x;
 117
 118   p_x->m_p_right = p_x_r;
 119   if (p_x_r != 0)
 120     p_x_r->m_p_parent = p_x;
 121
 122   p_x->m_red = true;
 123
 124   base_type::initialize_min_max();
 125   _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();)
 126   base_type::update_to_top(p_x, (node_update* )this);
 127   insert_fixup(p_x);
 128   _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid());
 129 }
 130
 131 PB_DS_CLASS_T_DEC
 132 inline typename PB_DS_CLASS_C_DEC::node_pointer
 133 PB_DS_CLASS_C_DEC::
 134 split_min()
 135 {
 136   node_pointer p_min = base_type::m_p_head->m_p_left;
 137
 138 #ifdef _GLIBCXX_DEBUG
 139   const node_pointer p_head = base_type::m_p_head;
 140   _GLIBCXX_DEBUG_ASSERT(p_min != p_head);
 141 #endif
 142
 143   remove_node(p_min);
 144   return p_min;
 145 }
 146
 147 PB_DS_CLASS_T_DEC
 148 std::pair<
 149   typename PB_DS_CLASS_C_DEC::node_pointer,
 150   typename PB_DS_CLASS_C_DEC::node_pointer>
 151 PB_DS_CLASS_C_DEC::
 152 find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r)
 153 {
 154   _GLIBCXX_DEBUG_ASSERT(h_l >= h_r);
 155
 156   if (base_type::m_p_head->m_p_parent == 0)
 157     return (std::make_pair((node_pointer)0, base_type::m_p_head));
 158
 159   node_pointer p_l_parent = base_type::m_p_head;
 160   while (h_l > h_r)
 161     {
 162       if (p_l->m_red == false)
 163         {
 164           _GLIBCXX_DEBUG_ASSERT(h_l > 0);
 165           --h_l;
 166         }
 167
 168       p_l_parent = p_l;
 169       p_l = p_l->m_p_right;
 170     }
 171
 172   if (!is_effectively_black(p_l))
 173     {
 174       p_l_parent = p_l;
 175       p_l = p_l->m_p_right;
 176     }
 177
 178   _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_l));
 179   _GLIBCXX_DEBUG_ASSERT(black_height(p_l) == h_r);
 180   _GLIBCXX_DEBUG_ASSERT(p_l == 0 || p_l->m_p_parent == p_l_parent);
 181   return std::make_pair(p_l, p_l_parent);
 182 }
 183
 184 PB_DS_CLASS_T_DEC
 185 std::pair<
 186   typename PB_DS_CLASS_C_DEC::node_pointer,
 187   typename PB_DS_CLASS_C_DEC::node_pointer>
 188 PB_DS_CLASS_C_DEC::
 189 find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r)
 190 {
 191   _GLIBCXX_DEBUG_ASSERT(h_r > h_l);
 192   if (base_type::m_p_head->m_p_parent == 0)
 193     return (std::make_pair((node_pointer)0,
 194                            base_type::m_p_head));
 195   node_pointer p_r_parent = base_type::m_p_head;
 196   while (h_r > h_l)
 197     {
 198       if (p_r->m_red == false)
 199         {
 200           _GLIBCXX_DEBUG_ASSERT(h_r > 0);
 201           --h_r;
 202         }
 203
 204       p_r_parent = p_r;
 205       p_r = p_r->m_p_left;
 206     }
 207
 208   if (!is_effectively_black(p_r))
 209     {
 210       p_r_parent = p_r;
 211       p_r = p_r->m_p_left;
 212     }
 213
 214   _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_r));
 215   _GLIBCXX_DEBUG_ASSERT(black_height(p_r) == h_l);
 216   _GLIBCXX_DEBUG_ASSERT(p_r == 0 || p_r->m_p_parent == p_r_parent);
 217   return std::make_pair(p_r, p_r_parent);
 218 }
 219
 220 PB_DS_CLASS_T_DEC
 221 inline typename PB_DS_CLASS_C_DEC::size_type
 222 PB_DS_CLASS_C_DEC::
 223 black_height(node_pointer p_nd)
 224 {
 225   size_type h = 1;
 226   while (p_nd != 0)
 227     {
 228       if (p_nd->m_red == false)
 229         ++h;
 230       p_nd = p_nd->m_p_left;
 231     }
 232   return h;
 233 }
 234
 235 PB_DS_CLASS_T_DEC
 236 void
 237 PB_DS_CLASS_C_DEC::
 238 split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other)
 239 {
 240   _GLIBCXX_DEBUG_ONLY(assert_valid());
 241   _GLIBCXX_DEBUG_ONLY(base_type::assert_valid();)
 242
 243     _GLIBCXX_DEBUG_ONLY(other.assert_valid());
 244   _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();)
 245
 246     if (base_type::split_prep(r_key, other) == false)
 247       {
 248         _GLIBCXX_DEBUG_ONLY(assert_valid());
 249         _GLIBCXX_DEBUG_ONLY(other.assert_valid());
 250         return;
 251       }
 252
 253   _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();)
 254   _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid();)
 255   node_pointer p_nd = upper_bound(r_key).m_p_nd;
 256   do
 257     {
 258       node_pointer p_next_nd = p_nd->m_p_parent;
 259       if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value)))
 260         split_at_node(p_nd, other);
 261
 262       _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();)
 263       _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid();)
 264       p_nd = p_next_nd;
 265     }
 266   while (p_nd != base_type::m_p_head);
 267
 268   base_type::split_finish(other);
 269   _GLIBCXX_DEBUG_ONLY(assert_valid();)
 270   _GLIBCXX_DEBUG_ONLY(assert_valid();)
 271 }
 272
 273 PB_DS_CLASS_T_DEC
 274 void
 275 PB_DS_CLASS_C_DEC::
 276 split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other)
 277 {
 278   _GLIBCXX_DEBUG_ASSERT(p_nd != 0);
 279
 280   node_pointer p_l = p_nd->m_p_left;
 281   node_pointer p_r = p_nd->m_p_right;
 282   node_pointer p_parent = p_nd->m_p_parent;
 283   if (p_parent == base_type::m_p_head)
 284     {
 285       base_type::m_p_head->m_p_parent = p_l;
 286       if (p_l != 0)
 287         {
 288           p_l->m_p_parent = base_type::m_p_head;
 289           p_l->m_red = false;
 290         }
 291     }
 292   else
 293     {
 294       if (p_parent->m_p_left == p_nd)
 295         p_parent->m_p_left = p_l;
 296       else
 297         p_parent->m_p_right = p_l;
 298
 299       if (p_l != 0)
 300         p_l->m_p_parent = p_parent;
 301
 302       update_to_top(p_parent, (node_update* )this);
 303
 304       if (!p_nd->m_red)
 305         remove_fixup(p_l, p_parent);
 306     }
 307
 308   base_type::initialize_min_max();
 309   other.join_imp(p_nd, p_r);
 310   _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid());
 311   _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid());
 312 }
 313