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