libstdc++
insert_join_fn_imps.hpp
Go to the documentation of this file.
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 
41 PB_DS_CLASS_T_DEC
42 void
43 PB_DS_CLASS_C_DEC::
44 join(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 
68 PB_DS_CLASS_T_DEC
69 bool
70 PB_DS_CLASS_C_DEC::
71 join_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 
100 PB_DS_CLASS_T_DEC
101 void
102 PB_DS_CLASS_C_DEC::
103 rec_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 
135 PB_DS_CLASS_T_DEC
136 void
137 PB_DS_CLASS_C_DEC::
138 rec_join_prep(leaf_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/,
139  branch_bag& r_bag)
140 { r_bag.add_branch(); }
141 
142 PB_DS_CLASS_T_DEC
143 void
144 PB_DS_CLASS_C_DEC::
145 rec_join_prep(leaf_const_pointer /*p_l*/, inode_const_pointer /*p_r*/,
146  branch_bag& r_bag)
147 { r_bag.add_branch(); }
148 
149 PB_DS_CLASS_T_DEC
150 void
151 PB_DS_CLASS_C_DEC::
152 rec_join_prep(inode_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/,
153  branch_bag& r_bag)
154 { r_bag.add_branch(); }
155 
156 PB_DS_CLASS_T_DEC
157 void
158 PB_DS_CLASS_C_DEC::
159 rec_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 
196 PB_DS_CLASS_T_DEC
197 typename PB_DS_CLASS_C_DEC::node_pointer
198 PB_DS_CLASS_C_DEC::
199 rec_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 
246 PB_DS_CLASS_T_DEC
247 typename PB_DS_CLASS_C_DEC::node_pointer
248 PB_DS_CLASS_C_DEC::
249 rec_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 
259 PB_DS_CLASS_T_DEC
260 typename PB_DS_CLASS_C_DEC::node_pointer
261 PB_DS_CLASS_C_DEC::
262 rec_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 
276 PB_DS_CLASS_T_DEC
277 typename PB_DS_CLASS_C_DEC::node_pointer
278 PB_DS_CLASS_C_DEC::
279 rec_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 
314 PB_DS_CLASS_T_DEC
315 typename PB_DS_CLASS_C_DEC::node_pointer
316 PB_DS_CLASS_C_DEC::
317 rec_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 
379 PB_DS_CLASS_T_DEC
380 inline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool>
381 PB_DS_CLASS_C_DEC::
382 insert(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 
413 PB_DS_CLASS_T_DEC
414 typename PB_DS_CLASS_C_DEC::size_type
415 PB_DS_CLASS_C_DEC::
416 keys_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 
436 PB_DS_CLASS_T_DEC
437 typename PB_DS_CLASS_C_DEC::inode_pointer
438 PB_DS_CLASS_C_DEC::
439 insert_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 
459 PB_DS_CLASS_T_DEC
460 void
461 PB_DS_CLASS_C_DEC::
462 update_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 }
std::make_pair
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:276