1// -*- C++ -*-
2
3// Copyright (C) 2005-2014 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
41PB_DS_CLASS_T_DEC
42void
43PB_DS_CLASS_C_DEC::
44join(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
68PB_DS_CLASS_T_DEC
69bool
70PB_DS_CLASS_C_DEC::
71join_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
100PB_DS_CLASS_T_DEC
101void
102PB_DS_CLASS_C_DEC::
103rec_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
135PB_DS_CLASS_T_DEC
136void
137PB_DS_CLASS_C_DEC::
138rec_join_prep(leaf_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/,
139	      branch_bag& r_bag)
140{ r_bag.add_branch(); }
141
142PB_DS_CLASS_T_DEC
143void
144PB_DS_CLASS_C_DEC::
145rec_join_prep(leaf_const_pointer /*p_l*/, inode_const_pointer /*p_r*/,
146	      branch_bag& r_bag)
147{ r_bag.add_branch(); }
148
149PB_DS_CLASS_T_DEC
150void
151PB_DS_CLASS_C_DEC::
152rec_join_prep(inode_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/,
153	      branch_bag& r_bag)
154{ r_bag.add_branch(); }
155
156PB_DS_CLASS_T_DEC
157void
158PB_DS_CLASS_C_DEC::
159rec_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
196PB_DS_CLASS_T_DEC
197typename PB_DS_CLASS_C_DEC::node_pointer
198PB_DS_CLASS_C_DEC::
199rec_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
246PB_DS_CLASS_T_DEC
247typename PB_DS_CLASS_C_DEC::node_pointer
248PB_DS_CLASS_C_DEC::
249rec_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
259PB_DS_CLASS_T_DEC
260typename PB_DS_CLASS_C_DEC::node_pointer
261PB_DS_CLASS_C_DEC::
262rec_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
276PB_DS_CLASS_T_DEC
277typename PB_DS_CLASS_C_DEC::node_pointer
278PB_DS_CLASS_C_DEC::
279rec_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
314PB_DS_CLASS_T_DEC
315typename PB_DS_CLASS_C_DEC::node_pointer
316PB_DS_CLASS_C_DEC::
317rec_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
379PB_DS_CLASS_T_DEC
380inline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool>
381PB_DS_CLASS_C_DEC::
382insert(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
413PB_DS_CLASS_T_DEC
414typename PB_DS_CLASS_C_DEC::size_type
415PB_DS_CLASS_C_DEC::
416keys_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
436PB_DS_CLASS_T_DEC
437typename PB_DS_CLASS_C_DEC::inode_pointer
438PB_DS_CLASS_C_DEC::
439insert_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
459PB_DS_CLASS_T_DEC
460void
461PB_DS_CLASS_C_DEC::
462update_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