Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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