1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2022 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_/split_fn_imps.hpp
38  * Contains an implementation class for pat_trie.
39  */
40 
41 #ifdef PB_DS_CLASS_C_DEC
42 
43 PB_DS_CLASS_T_DEC
44 void
45 PB_DS_CLASS_C_DEC::
split(key_const_reference r_key,PB_DS_CLASS_C_DEC & other)46 split(key_const_reference r_key, PB_DS_CLASS_C_DEC& other)
47 {
48   PB_DS_ASSERT_VALID((*this))
49   PB_DS_ASSERT_VALID(other)
50   branch_bag bag;
51   leaf_pointer p_split_lf = split_prep(r_key, other, bag);
52   if (p_split_lf == 0)
53     {
54       _GLIBCXX_DEBUG_ASSERT(bag.empty());
55       PB_DS_ASSERT_VALID((*this))
56       PB_DS_ASSERT_VALID(other)
57       return;
58     }
59 
60   _GLIBCXX_DEBUG_ASSERT(!bag.empty());
61   other.clear();
62 
63   m_p_head->m_p_parent = rec_split(m_p_head->m_p_parent, pref_begin(p_split_lf),
64                                            pref_end(p_split_lf), other, bag);
65 
66   m_p_head->m_p_parent->m_p_parent = m_p_head;
67 
68   head_pointer __ohead = other.m_p_head;
69   __ohead->m_p_max = m_p_head->m_p_max;
70   m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent);
71   __ohead->m_p_min = other.leftmost_descendant(__ohead->m_p_parent);
72 
73   other.m_size = std::distance(other.PB_DS_CLASS_C_DEC::begin(),
74                                      other.PB_DS_CLASS_C_DEC::end());
75   m_size -= other.m_size;
76   PB_DS_ASSERT_VALID((*this))
77   PB_DS_ASSERT_VALID(other)
78 }
79 
80 PB_DS_CLASS_T_DEC
81 typename PB_DS_CLASS_C_DEC::leaf_pointer
82 PB_DS_CLASS_C_DEC::
split_prep(key_const_reference r_key,PB_DS_CLASS_C_DEC & other,branch_bag & r_bag)83 split_prep(key_const_reference r_key, PB_DS_CLASS_C_DEC& other,
84              branch_bag& r_bag)
85 {
86   _GLIBCXX_DEBUG_ASSERT(r_bag.empty());
87   if (m_size == 0)
88     {
89       other.clear();
90       PB_DS_ASSERT_VALID((*this))
91       PB_DS_ASSERT_VALID(other)
92       return 0;
93     }
94 
95   if (synth_access_traits::cmp_keys(r_key,
96                                             PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_min)->value())))
97     {
98       other.clear();
99       value_swap(other);
100       PB_DS_ASSERT_VALID((*this))
101       PB_DS_ASSERT_VALID(other)
102       return 0;
103     }
104 
105   if (!synth_access_traits::cmp_keys(r_key,
106                                                PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_max)->value())))
107     {
108       PB_DS_ASSERT_VALID((*this))
109       PB_DS_ASSERT_VALID(other)
110       return 0;
111     }
112 
113   iterator it = lower_bound(r_key);
114 
115   if (!synth_access_traits::equal_keys(PB_DS_V2F(*it), r_key))
116     --it;
117 
118   node_pointer p_nd = it.m_p_nd;
119   _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == leaf_node);
120   leaf_pointer p_ret_l = static_cast<leaf_pointer>(p_nd);
121   while (p_nd->m_type != head_node)
122     {
123       r_bag.add_branch();
124       p_nd = p_nd->m_p_parent;
125     }
126   _GLIBCXX_DEBUG_ONLY(debug_base::split(r_key,(synth_access_traits&)(*this), other);)
127 
128   return p_ret_l;
129 }
130 
131 PB_DS_CLASS_T_DEC
132 typename PB_DS_CLASS_C_DEC::node_pointer
133 PB_DS_CLASS_C_DEC::
rec_split(node_pointer p_nd,a_const_iterator b_it,a_const_iterator e_it,PB_DS_CLASS_C_DEC & other,branch_bag & r_bag)134 rec_split(node_pointer p_nd, a_const_iterator b_it, a_const_iterator e_it,
135             PB_DS_CLASS_C_DEC& other, branch_bag& r_bag)
136 {
137   if (p_nd->m_type == leaf_node)
138     {
139       _GLIBCXX_DEBUG_ASSERT(other.m_p_head->m_p_parent == 0);
140       return p_nd;
141     }
142 
143   _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == i_node);
144   inode_pointer p_ind = static_cast<inode_pointer>(p_nd);
145 
146   node_pointer pfirst = p_ind->get_child_node(b_it, e_it, this);
147   node_pointer p_child_ret = rec_split(pfirst, b_it, e_it, other, r_bag);
148   PB_DS_ASSERT_NODE_VALID(p_child_ret)
149   p_ind->replace_child(p_child_ret, b_it, e_it, this);
150   apply_update(p_ind, (node_update*)this);
151 
152   inode_iterator child_it = p_ind->get_child_it(b_it, e_it, this);
153   const size_type lhs_dist = std::distance(p_ind->begin(), child_it);
154   const size_type lhs_num_children = lhs_dist + 1;
155   _GLIBCXX_DEBUG_ASSERT(lhs_num_children > 0);
156 
157   const size_type rhs_dist =  std::distance(p_ind->begin(), p_ind->end());
158   size_type rhs_num_children = rhs_dist - lhs_num_children;
159   if (rhs_num_children == 0)
160     {
161       apply_update(p_ind, (node_update*)this);
162       return p_ind;
163     }
164 
165   other.split_insert_branch(p_ind->get_e_ind(), b_it, child_it,
166                                   rhs_num_children, r_bag);
167 
168   child_it = p_ind->get_child_it(b_it, e_it, this);
169   while (rhs_num_children != 0)
170     {
171       ++child_it;
172       p_ind->remove_child(child_it);
173       --rhs_num_children;
174     }
175   apply_update(p_ind, (node_update*)this);
176 
177   const size_type int_dist = std::distance(p_ind->begin(), p_ind->end());
178   _GLIBCXX_DEBUG_ASSERT(int_dist >= 1);
179   if (int_dist > 1)
180     {
181       p_ind->update_prefixes(this);
182       PB_DS_ASSERT_NODE_VALID(p_ind)
183       apply_update(p_ind, (node_update*)this);
184       return p_ind;
185     }
186 
187   node_pointer p_ret = *p_ind->begin();
188   p_ind->~inode();
189   s_inode_allocator.deallocate(p_ind, 1);
190   apply_update(p_ret, (node_update*)this);
191   return p_ret;
192 }
193 
194 PB_DS_CLASS_T_DEC
195 void
196 PB_DS_CLASS_C_DEC::
split_insert_branch(size_type e_ind,a_const_iterator b_it,inode_iterator child_b_it,size_type num_children,branch_bag & r_bag)197 split_insert_branch(size_type e_ind, a_const_iterator b_it,
198                         inode_iterator child_b_it,
199                         size_type num_children, branch_bag& r_bag)
200 {
201 #ifdef _GLIBCXX_DEBUG
202   if (m_p_head->m_p_parent != 0)
203     PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent)
204 #endif
205 
206   const size_type start = m_p_head->m_p_parent == 0 ? 0 : 1;
207   const size_type total_num_children = start + num_children;
208   if (total_num_children == 0)
209     {
210       _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent == 0);
211       return;
212     }
213 
214   if (total_num_children == 1)
215     {
216       if (m_p_head->m_p_parent != 0)
217           {
218             PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent)
219             return;
220           }
221 
222       _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent == 0);
223       ++child_b_it;
224       m_p_head->m_p_parent = *child_b_it;
225       m_p_head->m_p_parent->m_p_parent = m_p_head;
226       apply_update(m_p_head->m_p_parent, (node_update*)this);
227       PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent)
228       return;
229     }
230 
231   _GLIBCXX_DEBUG_ASSERT(total_num_children > 1);
232   inode_pointer p_new_root = r_bag.get_branch();
233   new (p_new_root) inode(e_ind, b_it);
234   size_type num_inserted = 0;
235   while (num_inserted++ < num_children)
236     {
237       ++child_b_it;
238       PB_DS_ASSERT_NODE_VALID((*child_b_it))
239       p_new_root->add_child(*child_b_it, pref_begin(*child_b_it),
240                                   pref_end(*child_b_it), this);
241     }
242 
243   if (m_p_head->m_p_parent != 0)
244     p_new_root->add_child(m_p_head->m_p_parent,
245                                 pref_begin(m_p_head->m_p_parent),
246                                 pref_end(m_p_head->m_p_parent), this);
247 
248   m_p_head->m_p_parent = p_new_root;
249   p_new_root->m_p_parent = m_p_head;
250   apply_update(m_p_head->m_p_parent, (node_update*)this);
251   PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent)
252 }
253 #endif
254