detail/pat_trie_/insert_join_fn_imps.hpp

103 rec_join_prep(node_const_pointer p_l, node_const_pointer p_r,
108       if (p_r->m_type == leaf_node)
111 			static_cast<leaf_const_pointer>(p_r), r_bag);
115       _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node);
117 		    static_cast<inode_const_pointer>(p_r), r_bag);
122   if (p_r->m_type == leaf_node)
125 		    static_cast<leaf_const_pointer>(p_r), r_bag);
129   _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node);
132 		static_cast<inode_const_pointer>(p_r), r_bag);
138 rec_join_prep(leaf_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/,
145 rec_join_prep(leaf_const_pointer /*p_l*/, inode_const_pointer /*p_r*/,
152 rec_join_prep(inode_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/,
159 rec_join_prep(inode_const_pointer p_l, inode_const_pointer p_r,
162   if (p_l->get_e_ind() == p_r->get_e_ind() &&
164 					    p_r->pref_b_it(), p_r->pref_e_it()))
166       for (typename inode::const_iterator it = p_r->begin();
167 	   it != p_r->end(); ++ it)
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))
179       node_const_pointer p_r_join_child = p_r->get_join_child(p_l, this);
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))
188       node_const_pointer p_r_join_child = p_r->get_join_child(p_l, this);
199 rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind,
202   _GLIBCXX_DEBUG_ASSERT(p_r != 0);
205       apply_update(p_r, (node_update*)this);
206       return (p_r);
211       if (p_r->m_type == leaf_node)
214 					static_cast<leaf_pointer>(p_r), r_bag);
219       _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node);
221 				    static_cast<inode_pointer>(p_r),
228   if (p_r->m_type == leaf_node)
231 				    static_cast<leaf_pointer>(p_r),
237   _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node);
239 				static_cast<inode_pointer>(p_r),
249 rec_join(leaf_pointer p_l, leaf_pointer p_r, branch_bag& r_bag)
251   _GLIBCXX_DEBUG_ASSERT(p_r != 0);
253     return (p_r);
254   node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
262 rec_join(leaf_pointer p_l, inode_pointer p_r, size_type checked_ind,
267   const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r);
270   _GLIBCXX_DEBUG_ASSERT(p_r != 0);
271   node_pointer p_ret = rec_join(p_r, p_l, checked_ind, r_bag);
279 rec_join(inode_pointer p_l, leaf_pointer p_r, size_type checked_ind, branch_bag& r_bag)
282   _GLIBCXX_DEBUG_ASSERT(p_r != 0);
286   const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r);
289   if (!p_l->should_be_mine(pref_begin(p_r), pref_end(p_r), checked_ind, this))
291       node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
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)
302       node_pointer p_new_child = rec_join(p_pot_child, p_r, p_l->get_e_ind(),
317 rec_join(inode_pointer p_l, inode_pointer p_r,
321   _GLIBCXX_DEBUG_ASSERT(p_r != 0);
325   const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r);
328   if (p_l->get_e_ind() == p_r->get_e_ind() &&
330 					    p_r->pref_b_it(), p_r->pref_e_it()))
332       for (typename inode::iterator it = p_r->begin();
333 	   it != p_r->end(); ++ it)
341       p_r->~inode();
342       s_inode_allocator.deallocate(p_r, 1);
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))
351       node_pointer p_new_child = rec_join(p_l->get_join_child(p_r, this),
352 					  p_r, 0, r_bag);
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))
362       node_pointer p_new_child = rec_join(p_r->get_join_child(p_l, this), p_l,
365       p_r->replace_child(p_new_child, pref_begin(p_new_child),
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;
373   node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
439 insert_branch(node_pointer p_l, node_pointer p_r, branch_bag& r_bag)
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);
452   p_new_nd->add_child(p_r, right_b_it, right_e_it, this);
454   p_r->m_p_parent = p_new_nd;