libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2019 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 pat_trie_/insert_join_fn_imps.hpp
  38  * Contains an implementation class for pat_trie.
  39  */
  40
  41 PB_DS_CLASS_T_DEC
  42 void
  43 PB_DS_CLASS_C_DEC::
  44 join(PB_DS_CLASS_C_DEC& other)
  45 {
  46   PB_DS_ASSERT_VALID((*this))
  47   PB_DS_ASSERT_VALID(other)
  48   branch_bag bag;
  49   if (!join_prep(other, bag))
  50     {
  51       PB_DS_ASSERT_VALID((*this))
  52       PB_DS_ASSERT_VALID(other)
  53       return;
  54     }
  55
  56   m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent,
  57                                   other.m_p_head->m_p_parent, 0, bag);
  58
  59   m_p_head->m_p_parent->m_p_parent = m_p_head;
  60   m_size += other.m_size;
  61   other.initialize();
  62   PB_DS_ASSERT_VALID(other)
  63   m_p_head->m_p_min = leftmost_descendant(m_p_head->m_p_parent);
  64   m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent);
  65   PB_DS_ASSERT_VALID((*this))
  66 }
  67
  68 PB_DS_CLASS_T_DEC
  69 bool
  70 PB_DS_CLASS_C_DEC::
  71 join_prep(PB_DS_CLASS_C_DEC& other, branch_bag& r_bag)
  72 {
  73   PB_DS_ASSERT_VALID((*this))
  74   PB_DS_ASSERT_VALID(other)
  75   if (other.m_size == 0)
  76     return false;
  77
  78   if (m_size == 0)
  79     {
  80       value_swap(other);
  81       return false;
  82     }
  83
  84   const bool greater =
  85     synth_access_traits::cmp_keys(PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_max)->value()),
  86                                     PB_DS_V2F(static_cast<leaf_const_pointer>(other.m_p_head->m_p_min)->value()));
  87
  88   const bool lesser =
  89     synth_access_traits::cmp_keys(PB_DS_V2F(static_cast<leaf_const_pointer>(other.m_p_head->m_p_max)->value()),
  90                                     PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_min)->value()));
  91
  92   if (!greater && !lesser)
  93     __throw_join_error();
  94
  95   rec_join_prep(m_p_head->m_p_parent, other.m_p_head->m_p_parent, r_bag);
  96   _GLIBCXX_DEBUG_ONLY(debug_base::join(other, false);)
  97   return true;
  98 }
  99
 100 PB_DS_CLASS_T_DEC
 101 void
 102 PB_DS_CLASS_C_DEC::
 103 rec_join_prep(node_const_pointer p_l, node_const_pointer p_r,
 104               branch_bag& r_bag)
 105 {
 106   if (p_l->m_type == leaf_node)
 107     {
 108       if (p_r->m_type == leaf_node)
 109         {
 110           rec_join_prep(static_cast<leaf_const_pointer>(p_l),
 111                         static_cast<leaf_const_pointer>(p_r), r_bag);
 112           return;
 113         }
 114
 115       _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node);
 116       rec_join_prep(static_cast<leaf_const_pointer>(p_l),
 117                     static_cast<inode_const_pointer>(p_r), r_bag);
 118       return;
 119     }
 120
 121   _GLIBCXX_DEBUG_ASSERT(p_l->m_type == i_node);
 122   if (p_r->m_type == leaf_node)
 123     {
 124       rec_join_prep(static_cast<inode_const_pointer>(p_l),
 125                     static_cast<leaf_const_pointer>(p_r), r_bag);
 126       return;
 127     }
 128
 129   _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node);
 130
 131   rec_join_prep(static_cast<inode_const_pointer>(p_l),
 132                 static_cast<inode_const_pointer>(p_r), r_bag);
 133 }
 134
 135 PB_DS_CLASS_T_DEC
 136 void
 137 PB_DS_CLASS_C_DEC::
 138 rec_join_prep(leaf_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/,
 139               branch_bag& r_bag)
 140 { r_bag.add_branch(); }
 141
 142 PB_DS_CLASS_T_DEC
 143 void
 144 PB_DS_CLASS_C_DEC::
 145 rec_join_prep(leaf_const_pointer /*p_l*/, inode_const_pointer /*p_r*/,
 146               branch_bag& r_bag)
 147 { r_bag.add_branch(); }
 148
 149 PB_DS_CLASS_T_DEC
 150 void
 151 PB_DS_CLASS_C_DEC::
 152 rec_join_prep(inode_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/,
 153               branch_bag& r_bag)
 154 { r_bag.add_branch(); }
 155
 156 PB_DS_CLASS_T_DEC
 157 void
 158 PB_DS_CLASS_C_DEC::
 159 rec_join_prep(inode_const_pointer p_l, inode_const_pointer p_r,
 160               branch_bag& r_bag)
 161 {
 162   if (p_l->get_e_ind() == p_r->get_e_ind() &&
 163       synth_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(),
 164                                             p_r->pref_b_it(), p_r->pref_e_it()))
 165     {
 166       for (typename inode::const_iterator it = p_r->begin();
 167            it != p_r->end(); ++ it)
 168         {
 169           node_const_pointer p_l_join_child = p_l->get_join_child(*it, this);
 170           if (p_l_join_child != 0)
 171             rec_join_prep(p_l_join_child, * it, r_bag);
 172         }
 173       return;
 174     }
 175
 176   if (p_r->get_e_ind() < p_l->get_e_ind() &&
 177       p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this))
 178     {
 179       node_const_pointer p_r_join_child = p_r->get_join_child(p_l, this);
 180       if (p_r_join_child != 0)
 181         rec_join_prep(p_r_join_child, p_l, r_bag);
 182       return;
 183     }
 184
 185   if (p_r->get_e_ind() < p_l->get_e_ind() &&
 186       p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this))
 187     {
 188       node_const_pointer p_r_join_child = p_r->get_join_child(p_l, this);
 189       if (p_r_join_child != 0)
 190         rec_join_prep(p_r_join_child, p_l, r_bag);
 191       return;
 192     }
 193   r_bag.add_branch();
 194 }
 195
 196 PB_DS_CLASS_T_DEC
 197 typename PB_DS_CLASS_C_DEC::node_pointer
 198 PB_DS_CLASS_C_DEC::
 199 rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind,
 200          branch_bag& r_bag)
 201 {
 202   _GLIBCXX_DEBUG_ASSERT(p_r != 0);
 203   if (p_l == 0)
 204     {
 205       apply_update(p_r, (node_update*)this);
 206       return (p_r);
 207     }
 208
 209   if (p_l->m_type == leaf_node)
 210     {
 211       if (p_r->m_type == leaf_node)
 212         {
 213           node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l),
 214                                         static_cast<leaf_pointer>(p_r), r_bag);
 215           apply_update(p_ret, (node_update*)this);
 216           return p_ret;
 217         }
 218
 219       _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node);
 220       node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l),
 221                                     static_cast<inode_pointer>(p_r),
 222                                     checked_ind, r_bag);
 223       apply_update(p_ret, (node_update*)this);
 224       return p_ret;
 225     }
 226
 227   _GLIBCXX_DEBUG_ASSERT(p_l->m_type == i_node);
 228   if (p_r->m_type == leaf_node)
 229     {
 230       node_pointer p_ret = rec_join(static_cast<inode_pointer>(p_l),
 231                                     static_cast<leaf_pointer>(p_r),
 232                                     checked_ind, r_bag);
 233       apply_update(p_ret, (node_update*)this);
 234       return p_ret;
 235     }
 236
 237   _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node);
 238   node_pointer p_ret = rec_join(static_cast<inode_pointer>(p_l),
 239                                 static_cast<inode_pointer>(p_r),
 240                                 r_bag);
 241
 242   apply_update(p_ret, (node_update*)this);
 243   return p_ret;
 244 }
 245
 246 PB_DS_CLASS_T_DEC
 247 typename PB_DS_CLASS_C_DEC::node_pointer
 248 PB_DS_CLASS_C_DEC::
 249 rec_join(leaf_pointer p_l, leaf_pointer p_r, branch_bag& r_bag)
 250 {
 251   _GLIBCXX_DEBUG_ASSERT(p_r != 0);
 252   if (p_l == 0)
 253     return (p_r);
 254   node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
 255   _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == 2);
 256   return p_ret;
 257 }
 258
 259 PB_DS_CLASS_T_DEC
 260 typename PB_DS_CLASS_C_DEC::node_pointer
 261 PB_DS_CLASS_C_DEC::
 262 rec_join(leaf_pointer p_l, inode_pointer p_r, size_type checked_ind,
 263          branch_bag& r_bag)
 264 {
 265 #ifdef _GLIBCXX_DEBUG
 266   const size_type lhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_l);
 267   const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r);
 268 #endif
 269
 270   _GLIBCXX_DEBUG_ASSERT(p_r != 0);
 271   node_pointer p_ret = rec_join(p_r, p_l, checked_ind, r_bag);
 272   _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == lhs_leafs + rhs_leafs);
 273   return p_ret;
 274 }
 275
 276 PB_DS_CLASS_T_DEC
 277 typename PB_DS_CLASS_C_DEC::node_pointer
 278 PB_DS_CLASS_C_DEC::
 279 rec_join(inode_pointer p_l, leaf_pointer p_r, size_type checked_ind, branch_bag& r_bag)
 280 {
 281   _GLIBCXX_DEBUG_ASSERT(p_l != 0);
 282   _GLIBCXX_DEBUG_ASSERT(p_r != 0);
 283
 284 #ifdef _GLIBCXX_DEBUG
 285   const size_type lhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_l);
 286   const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r);
 287 #endif
 288
 289   if (!p_l->should_be_mine(pref_begin(p_r), pref_end(p_r), checked_ind, this))
 290     {
 291       node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
 292       PB_DS_ASSERT_NODE_VALID(p_ret)
 293       _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) ==
 294                             lhs_leafs + rhs_leafs);
 295       return p_ret;
 296     }
 297
 298   node_pointer p_pot_child = p_l->add_child(p_r, pref_begin(p_r),
 299                                             pref_end(p_r), this);
 300   if (p_pot_child != p_r)
 301     {
 302       node_pointer p_new_child = rec_join(p_pot_child, p_r, p_l->get_e_ind(),
 303                                           r_bag);
 304
 305       p_l->replace_child(p_new_child, pref_begin(p_new_child),
 306                          pref_end(p_new_child), this);
 307     }
 308
 309   PB_DS_ASSERT_NODE_VALID(p_l)
 310   _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_l) == lhs_leafs + rhs_leafs);
 311   return p_l;
 312 }
 313
 314 PB_DS_CLASS_T_DEC
 315 typename PB_DS_CLASS_C_DEC::node_pointer
 316 PB_DS_CLASS_C_DEC::
 317 rec_join(inode_pointer p_l, inode_pointer p_r,
 318          branch_bag& r_bag)
 319 {
 320   _GLIBCXX_DEBUG_ASSERT(p_l != 0);
 321   _GLIBCXX_DEBUG_ASSERT(p_r != 0);
 322
 323 #ifdef _GLIBCXX_DEBUG
 324   const size_type lhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_l);
 325   const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r);
 326 #endif
 327
 328   if (p_l->get_e_ind() == p_r->get_e_ind() &&
 329       synth_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(),
 330                                             p_r->pref_b_it(), p_r->pref_e_it()))
 331     {
 332       for (typename inode::iterator it = p_r->begin();
 333            it != p_r->end(); ++ it)
 334         {
 335           node_pointer p_new_child = rec_join(p_l->get_join_child(*it, this),
 336                                               * it, 0, r_bag);
 337           p_l->replace_child(p_new_child, pref_begin(p_new_child),
 338                              pref_end(p_new_child), this);
 339         }
 340
 341       p_r->~inode();
 342       s_inode_allocator.deallocate(p_r, 1);
 343       PB_DS_ASSERT_NODE_VALID(p_l)
 344       _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_l) == lhs_leafs + rhs_leafs);
 345       return p_l;
 346     }
 347
 348   if (p_l->get_e_ind() < p_r->get_e_ind() &&
 349       p_l->should_be_mine(p_r->pref_b_it(), p_r->pref_e_it(), 0, this))
 350     {
 351       node_pointer p_new_child = rec_join(p_l->get_join_child(p_r, this),
 352                                           p_r, 0, r_bag);
 353       p_l->replace_child(p_new_child, pref_begin(p_new_child),
 354                          pref_end(p_new_child), this);
 355       PB_DS_ASSERT_NODE_VALID(p_l)
 356       return p_l;
 357     }
 358
 359   if (p_r->get_e_ind() < p_l->get_e_ind() &&
 360       p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this))
 361     {
 362       node_pointer p_new_child = rec_join(p_r->get_join_child(p_l, this), p_l,
 363                                           0, r_bag);
 364
 365       p_r->replace_child(p_new_child, pref_begin(p_new_child),
 366                          pref_end(p_new_child), this);
 367
 368       PB_DS_ASSERT_NODE_VALID(p_r)
 369       _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_r) == lhs_leafs + rhs_leafs);
 370       return p_r;
 371     }
 372
 373   node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
 374   PB_DS_ASSERT_NODE_VALID(p_ret)
 375   _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == lhs_leafs + rhs_leafs);
 376   return p_ret;
 377 }
 378
 379 PB_DS_CLASS_T_DEC
 380 inline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool>
 381 PB_DS_CLASS_C_DEC::
 382 insert(const_reference r_val)
 383 {
 384   node_pointer p_lf = find_imp(PB_DS_V2F(r_val));
 385   if (p_lf != 0 && p_lf->m_type == leaf_node &&
 386       synth_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_lf)->value()), PB_DS_V2F(r_val)))
 387     {
 388       PB_DS_CHECK_KEY_EXISTS(PB_DS_V2F(r_val))
 389       PB_DS_ASSERT_VALID((*this))
 390       return std::make_pair(iterator(p_lf), false);
 391     }
 392
 393   PB_DS_CHECK_KEY_DOES_NOT_EXIST(PB_DS_V2F(r_val))
 394
 395   leaf_pointer p_new_lf = s_leaf_allocator.allocate(1);
 396   cond_dealtor cond(p_new_lf);
 397
 398   new (p_new_lf) leaf(r_val);
 399   apply_update(p_new_lf, (node_update*)this);
 400   cond.set_call_destructor();
 401   branch_bag bag;
 402   bag.add_branch();
 403   m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, p_new_lf, 0, bag);
 404   m_p_head->m_p_parent->m_p_parent = m_p_head;
 405   cond.set_no_action_dtor();
 406   ++m_size;
 407   update_min_max_for_inserted_leaf(p_new_lf);
 408   _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));)
 409   PB_DS_ASSERT_VALID((*this))
 410   return std::make_pair(point_iterator(p_new_lf), true);
 411 }
 412
 413 PB_DS_CLASS_T_DEC
 414 typename PB_DS_CLASS_C_DEC::size_type
 415 PB_DS_CLASS_C_DEC::
 416 keys_diff_ind(typename access_traits::const_iterator b_l,
 417               typename access_traits::const_iterator e_l,
 418               typename access_traits::const_iterator b_r,
 419               typename access_traits::const_iterator e_r)
 420 {
 421   size_type diff_pos = 0;
 422   while (b_l != e_l)
 423     {
 424       if (b_r == e_r)
 425         return (diff_pos);
 426       if (access_traits::e_pos(*b_l) != access_traits::e_pos(*b_r))
 427         return (diff_pos);
 428       ++b_l;
 429       ++b_r;
 430       ++diff_pos;
 431     }
 432   _GLIBCXX_DEBUG_ASSERT(b_r != e_r);
 433   return diff_pos;
 434 }
 435
 436 PB_DS_CLASS_T_DEC
 437 typename PB_DS_CLASS_C_DEC::inode_pointer
 438 PB_DS_CLASS_C_DEC::
 439 insert_branch(node_pointer p_l, node_pointer p_r, branch_bag& r_bag)
 440 {
 441   typename synth_access_traits::const_iterator left_b_it = pref_begin(p_l);
 442   typename synth_access_traits::const_iterator left_e_it = pref_end(p_l);
 443   typename synth_access_traits::const_iterator right_b_it = pref_begin(p_r);
 444   typename synth_access_traits::const_iterator right_e_it = pref_end(p_r);
 445
 446   const size_type diff_ind = keys_diff_ind(left_b_it, left_e_it,
 447                                            right_b_it, right_e_it);
 448
 449   inode_pointer p_new_nd = r_bag.get_branch();
 450   new (p_new_nd) inode(diff_ind, left_b_it);
 451   p_new_nd->add_child(p_l, left_b_it, left_e_it, this);
 452   p_new_nd->add_child(p_r, right_b_it, right_e_it, this);
 453   p_l->m_p_parent = p_new_nd;
 454   p_r->m_p_parent = p_new_nd;
 455   PB_DS_ASSERT_NODE_VALID(p_new_nd)
 456   return (p_new_nd);
 457 }
 458
 459 PB_DS_CLASS_T_DEC
 460 void
 461 PB_DS_CLASS_C_DEC::
 462 update_min_max_for_inserted_leaf(leaf_pointer p_new_lf)
 463 {
 464   if (m_p_head->m_p_min == m_p_head ||
 465       synth_access_traits::cmp_keys(PB_DS_V2F(p_new_lf->value()),
 466                                       PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_min)->value())))
 467     m_p_head->m_p_min = p_new_lf;
 468
 469   if (m_p_head->m_p_max == m_p_head ||
 470       synth_access_traits::cmp_keys(PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_max)->value()), PB_DS_V2F(p_new_lf->value())))
 471     m_p_head->m_p_max = p_new_lf;
 472 }