contrib/libstdc++/include/ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file insert_join_fn_imps.hpp
  44  * Contains an implementation class for bin_search_tree_.
  45  */
  46
  47 PB_DS_CLASS_T_DEC
  48 void
  49 PB_DS_CLASS_C_DEC::
  50 join(PB_DS_CLASS_C_DEC& other)
  51 {
  52   _GLIBCXX_DEBUG_ONLY(assert_valid(););
  53   _GLIBCXX_DEBUG_ONLY(other.assert_valid(););
  54   split_join_branch_bag bag;
  55   if (!join_prep(other, bag))
  56     {
  57       _GLIBCXX_DEBUG_ONLY(assert_valid(););
  58       _GLIBCXX_DEBUG_ONLY(other.assert_valid(););
  59       return;
  60     }
  61
  62   m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent,
  63                                   other.m_p_head->m_p_parent, 0, bag);
  64
  65   m_p_head->m_p_parent->m_p_parent = m_p_head;
  66   m_size += other.m_size;
  67   other.initialize();
  68   _GLIBCXX_DEBUG_ONLY(other.assert_valid(););
  69   m_p_head->m_p_min = leftmost_descendant(m_p_head->m_p_parent);
  70   m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent);
  71   _GLIBCXX_DEBUG_ONLY(assert_valid(););
  72 }
  73
  74 PB_DS_CLASS_T_DEC
  75 bool
  76 PB_DS_CLASS_C_DEC::
  77 join_prep(PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag)
  78 {
  79   _GLIBCXX_DEBUG_ONLY(assert_valid();)
  80   _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
  81   if (other.m_size == 0)
  82     return false;
  83
  84   if (m_size == 0)
  85     {
  86       value_swap(other);
  87       return false;
  88     }
  89
  90   const bool greater = synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(
  91                                                                                                  m_p_head->m_p_max)->value()),PB_DS_V2F(static_cast<const_leaf_pointer>(
  92                                                                                                  other.m_p_head->m_p_min)->value()));
  93
  94   const bool lesser = synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(
  95                                                                                                 other.m_p_head->m_p_max)->value()),PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_min)->value()));
  96
  97   if (!greater && !lesser)
  98     __throw_join_error();
  99
 100   rec_join_prep(m_p_head->m_p_parent, other.m_p_head->m_p_parent, r_bag);
 101   _GLIBCXX_DEBUG_ONLY(map_debug_base::join(other);)
 102   return true;
 103 }
 104
 105 PB_DS_CLASS_T_DEC
 106 void
 107 PB_DS_CLASS_C_DEC::
 108 rec_join_prep(const_node_pointer p_l, const_node_pointer p_r, split_join_branch_bag& r_bag)
 109 {
 110   if (p_l->m_type == pat_trie_leaf_node_type)
 111     {
 112       if (p_r->m_type == pat_trie_leaf_node_type)
 113         {
 114           rec_join_prep(static_cast<const_leaf_pointer>(p_l),
 115                         static_cast<const_leaf_pointer>(p_r), r_bag);
 116           return;
 117         }
 118
 119       _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type);
 120       rec_join_prep(static_cast<const_leaf_pointer>(p_l),
 121                     static_cast<const_internal_node_pointer>(p_r), r_bag);
 122       return;
 123     }
 124
 125   _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type);
 126   if (p_r->m_type == pat_trie_leaf_node_type)
 127     {
 128       rec_join_prep(static_cast<const_internal_node_pointer>(p_l),
 129                     static_cast<const_leaf_pointer>(p_r), r_bag);
 130       return;
 131     }
 132
 133   _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type);
 134
 135   rec_join_prep(static_cast<const_internal_node_pointer>(p_l),
 136                 static_cast<const_internal_node_pointer>(p_r), r_bag);
 137 }
 138
 139 PB_DS_CLASS_T_DEC
 140 void
 141 PB_DS_CLASS_C_DEC::
 142 rec_join_prep(const_leaf_pointer /*p_l*/, const_leaf_pointer /*p_r*/,
 143               split_join_branch_bag& r_bag)
 144 { r_bag.add_branch(); }
 145
 146 PB_DS_CLASS_T_DEC
 147 void
 148 PB_DS_CLASS_C_DEC::
 149 rec_join_prep(const_leaf_pointer /*p_l*/, const_internal_node_pointer /*p_r*/,
 150               split_join_branch_bag& r_bag)
 151 { r_bag.add_branch(); }
 152
 153 PB_DS_CLASS_T_DEC
 154 void
 155 PB_DS_CLASS_C_DEC::
 156 rec_join_prep(const_internal_node_pointer /*p_l*/, const_leaf_pointer /*p_r*/,
 157               split_join_branch_bag& r_bag)
 158 { r_bag.add_branch(); }
 159
 160 PB_DS_CLASS_T_DEC
 161 void
 162 PB_DS_CLASS_C_DEC::
 163 rec_join_prep(const_internal_node_pointer p_l, const_internal_node_pointer p_r,
 164               split_join_branch_bag& r_bag)
 165 {
 166   if (p_l->get_e_ind() == p_r->get_e_ind() &&
 167       synth_e_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(),
 168                                             p_r->pref_b_it(), p_r->pref_e_it()))
 169     {
 170       for (typename internal_node::const_iterator it = p_r->begin();
 171            it != p_r->end(); ++ it)
 172         {
 173           const_node_pointer p_l_join_child = p_l->get_join_child(*it, this);
 174           if (p_l_join_child != NULL)
 175             rec_join_prep(p_l_join_child, * it, r_bag);
 176         }
 177       return;
 178     }
 179
 180   if (p_r->get_e_ind() < p_l->get_e_ind() &&
 181       p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this))
 182     {
 183       const_node_pointer p_r_join_child = p_r->get_join_child(p_l, this);
 184       if (p_r_join_child != NULL)
 185         rec_join_prep(p_r_join_child, p_l, r_bag);
 186       return;
 187     }
 188
 189   if (p_r->get_e_ind() < p_l->get_e_ind() &&
 190       p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this))
 191     {
 192       const_node_pointer p_r_join_child = p_r->get_join_child(p_l, this);
 193       if (p_r_join_child != NULL)
 194         rec_join_prep(p_r_join_child, p_l, r_bag);
 195       return;
 196     }
 197   r_bag.add_branch();
 198 }
 199
 200 PB_DS_CLASS_T_DEC
 201 typename PB_DS_CLASS_C_DEC::node_pointer
 202 PB_DS_CLASS_C_DEC::
 203 rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag)
 204 {
 205   _GLIBCXX_DEBUG_ASSERT(p_r != NULL);
 206   if (p_l == NULL)
 207     {
 208       apply_update(p_r, (node_update* )this);
 209       return (p_r);
 210     }
 211
 212   if (p_l->m_type == pat_trie_leaf_node_type)
 213     {
 214       if (p_r->m_type == pat_trie_leaf_node_type)
 215         {
 216           node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l),
 217                                         static_cast<leaf_pointer>(p_r), r_bag);
 218           apply_update(p_ret, (node_update* )this);
 219           return p_ret;
 220         }
 221
 222       _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type);
 223       node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l),
 224                                     static_cast<internal_node_pointer>(p_r),
 225                                     checked_ind, r_bag);
 226       apply_update(p_ret, (node_update* )this);
 227       return p_ret;
 228     }
 229
 230   _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type);
 231   if (p_r->m_type == pat_trie_leaf_node_type)
 232     {
 233       node_pointer p_ret = rec_join(static_cast<internal_node_pointer>(p_l),
 234                                     static_cast<leaf_pointer>(p_r),
 235                                     checked_ind, r_bag);
 236       apply_update(p_ret, (node_update* )this);
 237       return p_ret;
 238     }
 239
 240   _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type);
 241   node_pointer p_ret = rec_join(static_cast<internal_node_pointer>(p_l),
 242                                 static_cast<internal_node_pointer>(p_r),
 243                                 r_bag);
 244
 245   apply_update(p_ret, (node_update* )this);
 246   return p_ret;
 247 }
 248
 249 PB_DS_CLASS_T_DEC
 250 typename PB_DS_CLASS_C_DEC::node_pointer
 251 PB_DS_CLASS_C_DEC::
 252 rec_join(leaf_pointer p_l, leaf_pointer p_r, split_join_branch_bag& r_bag)
 253 {
 254   _GLIBCXX_DEBUG_ASSERT(p_r != NULL);
 255   if (p_l == NULL)
 256     return (p_r);
 257   node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
 258   _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == 2);
 259   return p_ret;
 260 }
 261
 262 PB_DS_CLASS_T_DEC
 263 typename PB_DS_CLASS_C_DEC::node_pointer
 264 PB_DS_CLASS_C_DEC::
 265 rec_join(leaf_pointer p_l, internal_node_pointer p_r, size_type checked_ind,
 266          split_join_branch_bag& r_bag)
 267 {
 268 #ifdef _GLIBCXX_DEBUG
 269   const size_type lhs_leafs = recursive_count_leafs(p_l);
 270   const size_type rhs_leafs = recursive_count_leafs(p_r);
 271 #endif
 272
 273   _GLIBCXX_DEBUG_ASSERT(p_r != NULL);
 274   node_pointer p_ret = rec_join(p_r, p_l, checked_ind, r_bag);
 275   _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == lhs_leafs + rhs_leafs);
 276   return p_ret;
 277 }
 278
 279 PB_DS_CLASS_T_DEC
 280 typename PB_DS_CLASS_C_DEC::node_pointer
 281 PB_DS_CLASS_C_DEC::
 282 rec_join(internal_node_pointer p_l, leaf_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag)
 283 {
 284   _GLIBCXX_DEBUG_ASSERT(p_l != NULL);
 285   _GLIBCXX_DEBUG_ASSERT(p_r != NULL);
 286
 287 #ifdef _GLIBCXX_DEBUG
 288   const size_type lhs_leafs = recursive_count_leafs(p_l);
 289   const size_type rhs_leafs = recursive_count_leafs(p_r);
 290 #endif
 291
 292   if (!p_l->should_be_mine(pref_begin(p_r), pref_end(p_r), checked_ind, this))
 293     {
 294       node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
 295       _GLIBCXX_DEBUG_ONLY(p_ret->assert_valid(this);)
 296       _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) ==
 297                             lhs_leafs + rhs_leafs);
 298       return p_ret;
 299     }
 300
 301   node_pointer p_pot_child = p_l->add_child(p_r, pref_begin(p_r),
 302                                             pref_end(p_r), this);
 303   if (p_pot_child != p_r)
 304     {
 305       node_pointer p_new_child = rec_join(p_pot_child, p_r, p_l->get_e_ind(),
 306                                           r_bag);
 307
 308       p_l->replace_child(p_new_child, pref_begin(p_new_child),
 309                          pref_end(p_new_child), this);
 310     }
 311
 312   _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this));
 313   _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l) == lhs_leafs + rhs_leafs);
 314   return p_l;
 315 }
 316
 317 PB_DS_CLASS_T_DEC
 318 typename PB_DS_CLASS_C_DEC::node_pointer
 319 PB_DS_CLASS_C_DEC::
 320 rec_join(internal_node_pointer p_l, internal_node_pointer p_r, split_join_branch_bag& r_bag)
 321 {
 322   _GLIBCXX_DEBUG_ASSERT(p_l != NULL);
 323   _GLIBCXX_DEBUG_ASSERT(p_r != NULL);
 324
 325 #ifdef _GLIBCXX_DEBUG
 326   const size_type lhs_leafs = recursive_count_leafs(p_l);
 327   const size_type rhs_leafs = recursive_count_leafs(p_r);
 328 #endif
 329
 330   if (p_l->get_e_ind() == p_r->get_e_ind() &&
 331       synth_e_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(),
 332                                             p_r->pref_b_it(), p_r->pref_e_it()))
 333     {
 334       for (typename internal_node::iterator it = p_r->begin();
 335            it != p_r->end(); ++ it)
 336         {
 337           node_pointer p_new_child = rec_join(p_l->get_join_child(*it, this),
 338                                               * it, 0, r_bag);
 339           p_l->replace_child(p_new_child, pref_begin(p_new_child),
 340                              pref_end(p_new_child), this);
 341         }
 342
 343       p_r->~internal_node();
 344       s_internal_node_allocator.deallocate(p_r, 1);
 345       _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this);)
 346       _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l) == lhs_leafs + rhs_leafs);
 347       return p_l;
 348     }
 349
 350   if (p_l->get_e_ind() < p_r->get_e_ind() &&
 351       p_l->should_be_mine(p_r->pref_b_it(), p_r->pref_e_it(), 0, this))
 352     {
 353       node_pointer p_new_child = rec_join(p_l->get_join_child(p_r, this),
 354                                           p_r, 0, r_bag);
 355       p_l->replace_child(p_new_child, pref_begin(p_new_child),
 356                          pref_end(p_new_child), this);
 357       _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this);)
 358       return p_l;
 359     }
 360
 361   if (p_r->get_e_ind() < p_l->get_e_ind() &&
 362       p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this))
 363     {
 364       node_pointer p_new_child = rec_join(p_r->get_join_child(p_l, this), p_l,
 365                                           0, r_bag);
 366
 367       p_r->replace_child(p_new_child, pref_begin(p_new_child),
 368                          pref_end(p_new_child), this);
 369
 370       _GLIBCXX_DEBUG_ONLY(p_r->assert_valid(this);)
 371       _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_r) == lhs_leafs + rhs_leafs);
 372       return p_r;
 373     }
 374
 375   node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
 376   _GLIBCXX_DEBUG_ONLY(p_ret->assert_valid(this);)
 377   _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == lhs_leafs + rhs_leafs);
 378   return p_ret;
 379 }
 380
 381 PB_DS_CLASS_T_DEC
 382 inline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool>
 383 PB_DS_CLASS_C_DEC::
 384 insert(const_reference r_val)
 385 {
 386   node_pointer p_lf = find_imp(PB_DS_V2F(r_val));
 387   if (p_lf != NULL && p_lf->m_type == pat_trie_leaf_node_type &&
 388       synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_lf)->value()), PB_DS_V2F(r_val)))
 389     {
 390       _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(PB_DS_V2F(r_val)));
 391       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 392       return std::make_pair(iterator(p_lf), false);
 393     }
 394
 395   _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(PB_DS_V2F(r_val)));
 396
 397   leaf_pointer p_new_lf = s_leaf_allocator.allocate(1);
 398   cond_dealtor cond(p_new_lf);
 399
 400   new (p_new_lf) leaf(r_val);
 401   apply_update(p_new_lf, (node_update* )this);
 402   cond.set_call_destructor();
 403   split_join_branch_bag bag;
 404   bag.add_branch();
 405   m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, p_new_lf, 0, bag);
 406   m_p_head->m_p_parent->m_p_parent = m_p_head;
 407   cond.set_no_action_dtor();
 408   ++m_size;
 409   update_min_max_for_inserted_leaf(p_new_lf);
 410   _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(r_val));)
 411   _GLIBCXX_DEBUG_ONLY(assert_valid();)
 412   return std::make_pair(point_iterator(p_new_lf), true);
 413 }
 414
 415 PB_DS_CLASS_T_DEC
 416 typename PB_DS_CLASS_C_DEC::size_type
 417 PB_DS_CLASS_C_DEC::
 418 keys_diff_ind(typename e_access_traits::const_iterator b_l, typename e_access_traits::const_iterator e_l, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r)
 419 {
 420   size_type diff_pos = 0;
 421   while (b_l != e_l)
 422     {
 423       if (b_r == e_r)
 424         return (diff_pos);
 425       if (e_access_traits::e_pos(*b_l) != e_access_traits::e_pos(*b_r))
 426         return (diff_pos);
 427       ++b_l;
 428       ++b_r;
 429       ++diff_pos;
 430     }
 431   _GLIBCXX_DEBUG_ASSERT(b_r != e_r);
 432   return diff_pos;
 433 }
 434
 435 PB_DS_CLASS_T_DEC
 436 typename PB_DS_CLASS_C_DEC::internal_node_pointer
 437 PB_DS_CLASS_C_DEC::
 438 insert_branch(node_pointer p_l, node_pointer p_r, split_join_branch_bag& r_bag)
 439 {
 440   typename synth_e_access_traits::const_iterator left_b_it = pref_begin(p_l);
 441   typename synth_e_access_traits::const_iterator left_e_it = pref_end(p_l);
 442   typename synth_e_access_traits::const_iterator right_b_it = pref_begin(p_r);
 443   typename synth_e_access_traits::const_iterator right_e_it = pref_end(p_r);
 444
 445   const size_type diff_ind = keys_diff_ind(left_b_it, left_e_it,
 446                                            right_b_it, right_e_it);
 447
 448   internal_node_pointer p_new_nd = r_bag.get_branch();
 449   new (p_new_nd) internal_node(diff_ind, left_b_it);
 450   p_new_nd->add_child(p_l, left_b_it, left_e_it, this);
 451   p_new_nd->add_child(p_r, right_b_it, right_e_it, this);
 452   p_l->m_p_parent = p_new_nd;
 453   p_r->m_p_parent = p_new_nd;
 454   _GLIBCXX_DEBUG_ONLY(p_new_nd->assert_valid(this);)
 455   return (p_new_nd);
 456 }
 457
 458 PB_DS_CLASS_T_DEC
 459 void
 460 PB_DS_CLASS_C_DEC::
 461 update_min_max_for_inserted_leaf(leaf_pointer p_new_lf)
 462 {
 463   if (m_p_head->m_p_min == m_p_head ||
 464       synth_e_access_traits::cmp_keys(PB_DS_V2F(p_new_lf->value()),
 465                                       PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_min)->value())))
 466     m_p_head->m_p_min = p_new_lf;
 467
 468   if (m_p_head->m_p_max == m_p_head ||
 469       synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_max)->value()), PB_DS_V2F(p_new_lf->value())))
 470     m_p_head->m_p_max = p_new_lf;
 471 }