libstdc++
split_fn_imps.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00026 
00027 // Permission to use, copy, modify, sell, and distribute this software
00028 // is hereby granted without fee, provided that the above copyright
00029 // notice appears in all copies, and that both that copyright notice
00030 // and this permission notice appear in supporting documentation. None
00031 // of the above authors, nor IBM Haifa Research Laboratories, make any
00032 // representation about the suitability of this software for any
00033 // purpose. It is provided "as is" without express or implied
00034 // warranty.
00035 
00036 /**
00037  * @file pat_trie_/split_fn_imps.hpp
00038  * Contains an implementation class for pat_trie.
00039  */
00040 
00041 PB_DS_CLASS_T_DEC
00042 void
00043 PB_DS_CLASS_C_DEC::
00044 split(key_const_reference r_key, PB_DS_CLASS_C_DEC& other)
00045 {
00046   PB_DS_ASSERT_VALID((*this))
00047   PB_DS_ASSERT_VALID(other)
00048   branch_bag bag;
00049   leaf_pointer p_split_lf = split_prep(r_key, other, bag);
00050   if (p_split_lf == 0)
00051     {
00052       _GLIBCXX_DEBUG_ASSERT(bag.empty());
00053       PB_DS_ASSERT_VALID((*this))
00054       PB_DS_ASSERT_VALID(other)
00055       return;
00056     }
00057 
00058   _GLIBCXX_DEBUG_ASSERT(!bag.empty());
00059   other.clear();
00060 
00061   m_p_head->m_p_parent = rec_split(m_p_head->m_p_parent, pref_begin(p_split_lf),
00062                    pref_end(p_split_lf), other, bag);
00063 
00064   m_p_head->m_p_parent->m_p_parent = m_p_head;
00065 
00066   head_pointer __ohead = other.m_p_head;
00067   __ohead->m_p_max = m_p_head->m_p_max;
00068   m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent);
00069   __ohead->m_p_min = other.leftmost_descendant(__ohead->m_p_parent);
00070 
00071   other.m_size = std::distance(other.PB_DS_CLASS_C_DEC::begin(),
00072                    other.PB_DS_CLASS_C_DEC::end());
00073   m_size -= other.m_size;
00074   PB_DS_ASSERT_VALID((*this))
00075   PB_DS_ASSERT_VALID(other)
00076 }
00077 
00078 PB_DS_CLASS_T_DEC
00079 typename PB_DS_CLASS_C_DEC::leaf_pointer
00080 PB_DS_CLASS_C_DEC::
00081 split_prep(key_const_reference r_key, PB_DS_CLASS_C_DEC& other,
00082        branch_bag& r_bag)
00083 {
00084   _GLIBCXX_DEBUG_ASSERT(r_bag.empty());
00085   if (m_size == 0)
00086     {
00087       other.clear();
00088       PB_DS_ASSERT_VALID((*this))
00089       PB_DS_ASSERT_VALID(other)
00090       return 0;
00091     }
00092 
00093   if (synth_access_traits::cmp_keys(r_key,
00094                     PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_min)->value())))
00095     {
00096       other.clear();
00097       value_swap(other);
00098       PB_DS_ASSERT_VALID((*this))
00099       PB_DS_ASSERT_VALID(other)
00100       return 0;
00101     }
00102 
00103   if (!synth_access_traits::cmp_keys(r_key,
00104                        PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_max)->value())))
00105     {
00106       PB_DS_ASSERT_VALID((*this))
00107       PB_DS_ASSERT_VALID(other)
00108       return 0;
00109     }
00110 
00111   iterator it = lower_bound(r_key);
00112 
00113   if (!synth_access_traits::equal_keys(PB_DS_V2F(*it), r_key))
00114     --it;
00115 
00116   node_pointer p_nd = it.m_p_nd;
00117   _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == leaf_node);
00118   leaf_pointer p_ret_l = static_cast<leaf_pointer>(p_nd);
00119   while (p_nd->m_type != head_node)
00120     {
00121       r_bag.add_branch();
00122       p_nd = p_nd->m_p_parent;
00123     }
00124   _GLIBCXX_DEBUG_ONLY(debug_base::split(r_key,(synth_access_traits&)(*this), other);)
00125 
00126   return p_ret_l;
00127 }
00128 
00129 PB_DS_CLASS_T_DEC
00130 typename PB_DS_CLASS_C_DEC::node_pointer
00131 PB_DS_CLASS_C_DEC::
00132 rec_split(node_pointer p_nd, a_const_iterator b_it, a_const_iterator e_it,
00133       PB_DS_CLASS_C_DEC& other, branch_bag& r_bag)
00134 {
00135   if (p_nd->m_type == leaf_node)
00136     {
00137       _GLIBCXX_DEBUG_ASSERT(other.m_p_head->m_p_parent == 0);
00138       return p_nd;
00139     }
00140 
00141   _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == i_node);
00142   inode_pointer p_ind = static_cast<inode_pointer>(p_nd);
00143 
00144   node_pointer pfirst = p_ind->get_child_node(b_it, e_it, this);
00145   node_pointer p_child_ret = rec_split(pfirst, b_it, e_it, other, r_bag);
00146   PB_DS_ASSERT_NODE_VALID(p_child_ret)
00147   p_ind->replace_child(p_child_ret, b_it, e_it, this);
00148   apply_update(p_ind, (node_update*)this);
00149 
00150   inode_iterator child_it = p_ind->get_child_it(b_it, e_it, this);
00151   const size_type lhs_dist = std::distance(p_ind->begin(), child_it);
00152   const size_type lhs_num_children = lhs_dist + 1;
00153   _GLIBCXX_DEBUG_ASSERT(lhs_num_children > 0);
00154 
00155   const size_type rhs_dist =  std::distance(p_ind->begin(), p_ind->end());
00156   size_type rhs_num_children = rhs_dist - lhs_num_children;
00157   if (rhs_num_children == 0)
00158     {
00159       apply_update(p_ind, (node_update*)this);
00160       return p_ind;
00161     }
00162 
00163   other.split_insert_branch(p_ind->get_e_ind(), b_it, child_it,
00164                 rhs_num_children, r_bag);
00165 
00166   child_it = p_ind->get_child_it(b_it, e_it, this);
00167   while (rhs_num_children != 0)
00168     {
00169       ++child_it;
00170       p_ind->remove_child(child_it);
00171       --rhs_num_children;
00172     }
00173   apply_update(p_ind, (node_update*)this);
00174 
00175   const size_type int_dist = std::distance(p_ind->begin(), p_ind->end());
00176   _GLIBCXX_DEBUG_ASSERT(int_dist >= 1);
00177   if (int_dist > 1)
00178     {
00179       p_ind->update_prefixes(this);
00180       PB_DS_ASSERT_NODE_VALID(p_ind)
00181       apply_update(p_ind, (node_update*)this);
00182       return p_ind;
00183     }
00184 
00185   node_pointer p_ret = *p_ind->begin();
00186   p_ind->~inode();
00187   s_inode_allocator.deallocate(p_ind, 1);
00188   apply_update(p_ret, (node_update*)this);
00189   return p_ret;
00190 }
00191 
00192 PB_DS_CLASS_T_DEC
00193 void
00194 PB_DS_CLASS_C_DEC::
00195 split_insert_branch(size_type e_ind, a_const_iterator b_it,
00196             inode_iterator child_b_it,
00197             size_type num_children, branch_bag& r_bag)
00198 {
00199 #ifdef _GLIBCXX_DEBUG
00200   if (m_p_head->m_p_parent != 0)
00201     PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent)
00202 #endif
00203 
00204   const size_type start = m_p_head->m_p_parent == 0 ? 0 : 1;
00205   const size_type total_num_children = start + num_children;
00206   if (total_num_children == 0)
00207     {
00208       _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent == 0);
00209       return;
00210     }
00211 
00212   if (total_num_children == 1)
00213     {
00214       if (m_p_head->m_p_parent != 0)
00215     {
00216       PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent)
00217       return;
00218     }
00219 
00220       _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent == 0);
00221       ++child_b_it;
00222       m_p_head->m_p_parent = *child_b_it;
00223       m_p_head->m_p_parent->m_p_parent = m_p_head;
00224       apply_update(m_p_head->m_p_parent, (node_update*)this);
00225       PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent)
00226       return;
00227     }
00228 
00229   _GLIBCXX_DEBUG_ASSERT(total_num_children > 1);
00230   inode_pointer p_new_root = r_bag.get_branch();
00231   new (p_new_root) inode(e_ind, b_it);
00232   size_type num_inserted = 0;
00233   while (num_inserted++ < num_children)
00234     {
00235       ++child_b_it;
00236       PB_DS_ASSERT_NODE_VALID((*child_b_it))
00237       p_new_root->add_child(*child_b_it, pref_begin(*child_b_it),
00238                 pref_end(*child_b_it), this);
00239     }
00240 
00241   if (m_p_head->m_p_parent != 0)
00242     p_new_root->add_child(m_p_head->m_p_parent,
00243               pref_begin(m_p_head->m_p_parent),
00244               pref_end(m_p_head->m_p_parent), this);
00245 
00246   m_p_head->m_p_parent = p_new_root;
00247   p_new_root->m_p_parent = m_p_head;
00248   apply_update(m_p_head->m_p_parent, (node_update*)this);
00249   PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent)
00250 }