]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
a5544970 | 3 | // Copyright (C) 2005-2019 Free Software Foundation, Inc. |
4569a895 AT |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
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 | ||
748086b7 JJ |
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. | |
4569a895 | 19 | |
748086b7 JJ |
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/>. | |
4569a895 AT |
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 | /** | |
a345e45d BK |
37 | * @file pat_trie_/insert_join_fn_imps.hpp |
38 | * Contains an implementation class for pat_trie. | |
4569a895 AT |
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 | { | |
f5886803 FD |
46 | PB_DS_ASSERT_VALID((*this)) |
47 | PB_DS_ASSERT_VALID(other) | |
a345e45d | 48 | branch_bag bag; |
4569a895 AT |
49 | if (!join_prep(other, bag)) |
50 | { | |
f5886803 FD |
51 | PB_DS_ASSERT_VALID((*this)) |
52 | PB_DS_ASSERT_VALID(other) | |
4569a895 AT |
53 | return; |
54 | } | |
55 | ||
a345e45d | 56 | m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, |
47bea7b8 | 57 | other.m_p_head->m_p_parent, 0, bag); |
4569a895 AT |
58 | |
59 | m_p_head->m_p_parent->m_p_parent = m_p_head; | |
4569a895 | 60 | m_size += other.m_size; |
4569a895 | 61 | other.initialize(); |
f5886803 | 62 | PB_DS_ASSERT_VALID(other) |
4569a895 AT |
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); | |
f5886803 | 65 | PB_DS_ASSERT_VALID((*this)) |
4569a895 AT |
66 | } |
67 | ||
68 | PB_DS_CLASS_T_DEC | |
69 | bool | |
70 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 71 | join_prep(PB_DS_CLASS_C_DEC& other, branch_bag& r_bag) |
4569a895 | 72 | { |
f5886803 FD |
73 | PB_DS_ASSERT_VALID((*this)) |
74 | PB_DS_ASSERT_VALID(other) | |
47bea7b8 BK |
75 | if (other.m_size == 0) |
76 | return false; | |
4569a895 AT |
77 | |
78 | if (m_size == 0) | |
79 | { | |
80 | value_swap(other); | |
47bea7b8 | 81 | return false; |
4569a895 AT |
82 | } |
83 | ||
f5886803 | 84 | const bool greater = |
a345e45d BK |
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())); | |
4569a895 | 87 | |
f5886803 | 88 | const bool lesser = |
a345e45d BK |
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())); | |
4569a895 | 91 | |
47bea7b8 | 92 | if (!greater && !lesser) |
8fafc2d3 | 93 | __throw_join_error(); |
4569a895 AT |
94 | |
95 | rec_join_prep(m_p_head->m_p_parent, other.m_p_head->m_p_parent, r_bag); | |
f5886803 | 96 | _GLIBCXX_DEBUG_ONLY(debug_base::join(other, false);) |
47bea7b8 | 97 | return true; |
4569a895 AT |
98 | } |
99 | ||
100 | PB_DS_CLASS_T_DEC | |
101 | void | |
102 | PB_DS_CLASS_C_DEC:: | |
a345e45d BK |
103 | rec_join_prep(node_const_pointer p_l, node_const_pointer p_r, |
104 | branch_bag& r_bag) | |
4569a895 | 105 | { |
a345e45d | 106 | if (p_l->m_type == leaf_node) |
4569a895 | 107 | { |
a345e45d BK |
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); | |
4569a895 | 112 | return; |
a345e45d | 113 | } |
4569a895 | 114 | |
a345e45d BK |
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); | |
4569a895 AT |
118 | return; |
119 | } | |
120 | ||
a345e45d BK |
121 | _GLIBCXX_DEBUG_ASSERT(p_l->m_type == i_node); |
122 | if (p_r->m_type == leaf_node) | |
4569a895 | 123 | { |
a345e45d BK |
124 | rec_join_prep(static_cast<inode_const_pointer>(p_l), |
125 | static_cast<leaf_const_pointer>(p_r), r_bag); | |
4569a895 AT |
126 | return; |
127 | } | |
128 | ||
a345e45d | 129 | _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node); |
4569a895 | 130 | |
a345e45d BK |
131 | rec_join_prep(static_cast<inode_const_pointer>(p_l), |
132 | static_cast<inode_const_pointer>(p_r), r_bag); | |
4569a895 AT |
133 | } |
134 | ||
135 | PB_DS_CLASS_T_DEC | |
136 | void | |
137 | PB_DS_CLASS_C_DEC:: | |
a345e45d BK |
138 | rec_join_prep(leaf_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/, |
139 | branch_bag& r_bag) | |
47bea7b8 | 140 | { r_bag.add_branch(); } |
4569a895 AT |
141 | |
142 | PB_DS_CLASS_T_DEC | |
143 | void | |
144 | PB_DS_CLASS_C_DEC:: | |
a345e45d BK |
145 | rec_join_prep(leaf_const_pointer /*p_l*/, inode_const_pointer /*p_r*/, |
146 | branch_bag& r_bag) | |
47bea7b8 | 147 | { r_bag.add_branch(); } |
4569a895 AT |
148 | |
149 | PB_DS_CLASS_T_DEC | |
150 | void | |
151 | PB_DS_CLASS_C_DEC:: | |
a345e45d BK |
152 | rec_join_prep(inode_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/, |
153 | branch_bag& r_bag) | |
47bea7b8 | 154 | { r_bag.add_branch(); } |
4569a895 AT |
155 | |
156 | PB_DS_CLASS_T_DEC | |
157 | void | |
158 | PB_DS_CLASS_C_DEC:: | |
a345e45d BK |
159 | rec_join_prep(inode_const_pointer p_l, inode_const_pointer p_r, |
160 | branch_bag& r_bag) | |
4569a895 | 161 | { |
a345e45d BK |
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(), | |
47bea7b8 | 164 | p_r->pref_b_it(), p_r->pref_e_it())) |
4569a895 | 165 | { |
a345e45d | 166 | for (typename inode::const_iterator it = p_r->begin(); |
4569a895 | 167 | it != p_r->end(); ++ it) |
a345e45d BK |
168 | { |
169 | node_const_pointer p_l_join_child = p_l->get_join_child(*it, this); | |
8fc81078 | 170 | if (p_l_join_child != 0) |
4569a895 | 171 | rec_join_prep(p_l_join_child, * it, r_bag); |
a345e45d | 172 | } |
4569a895 AT |
173 | return; |
174 | } | |
175 | ||
a345e45d | 176 | if (p_r->get_e_ind() < p_l->get_e_ind() && |
47bea7b8 | 177 | p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) |
4569a895 | 178 | { |
a345e45d | 179 | node_const_pointer p_r_join_child = p_r->get_join_child(p_l, this); |
8fc81078 | 180 | if (p_r_join_child != 0) |
4569a895 | 181 | rec_join_prep(p_r_join_child, p_l, r_bag); |
4569a895 AT |
182 | return; |
183 | } | |
184 | ||
a345e45d | 185 | if (p_r->get_e_ind() < p_l->get_e_ind() && |
47bea7b8 | 186 | p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) |
4569a895 | 187 | { |
a345e45d | 188 | node_const_pointer p_r_join_child = p_r->get_join_child(p_l, this); |
8fc81078 | 189 | if (p_r_join_child != 0) |
4569a895 | 190 | rec_join_prep(p_r_join_child, p_l, r_bag); |
4569a895 AT |
191 | return; |
192 | } | |
4569a895 AT |
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:: | |
a345e45d BK |
199 | rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, |
200 | branch_bag& r_bag) | |
4569a895 | 201 | { |
8fc81078 PC |
202 | _GLIBCXX_DEBUG_ASSERT(p_r != 0); |
203 | if (p_l == 0) | |
4569a895 | 204 | { |
a345e45d | 205 | apply_update(p_r, (node_update*)this); |
4569a895 AT |
206 | return (p_r); |
207 | } | |
208 | ||
a345e45d | 209 | if (p_l->m_type == leaf_node) |
4569a895 | 210 | { |
a345e45d BK |
211 | if (p_r->m_type == leaf_node) |
212 | { | |
47bea7b8 BK |
213 | node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l), |
214 | static_cast<leaf_pointer>(p_r), r_bag); | |
a345e45d | 215 | apply_update(p_ret, (node_update*)this); |
47bea7b8 | 216 | return p_ret; |
a345e45d | 217 | } |
4569a895 | 218 | |
a345e45d | 219 | _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node); |
47bea7b8 | 220 | node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l), |
a345e45d | 221 | static_cast<inode_pointer>(p_r), |
47bea7b8 | 222 | checked_ind, r_bag); |
a345e45d | 223 | apply_update(p_ret, (node_update*)this); |
47bea7b8 | 224 | return p_ret; |
4569a895 AT |
225 | } |
226 | ||
a345e45d BK |
227 | _GLIBCXX_DEBUG_ASSERT(p_l->m_type == i_node); |
228 | if (p_r->m_type == leaf_node) | |
4569a895 | 229 | { |
a345e45d | 230 | node_pointer p_ret = rec_join(static_cast<inode_pointer>(p_l), |
4569a895 | 231 | static_cast<leaf_pointer>(p_r), |
47bea7b8 | 232 | checked_ind, r_bag); |
a345e45d | 233 | apply_update(p_ret, (node_update*)this); |
47bea7b8 | 234 | return p_ret; |
4569a895 AT |
235 | } |
236 | ||
a345e45d BK |
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), | |
4569a895 AT |
240 | r_bag); |
241 | ||
a345e45d | 242 | apply_update(p_ret, (node_update*)this); |
47bea7b8 | 243 | return p_ret; |
4569a895 AT |
244 | } |
245 | ||
246 | PB_DS_CLASS_T_DEC | |
247 | typename PB_DS_CLASS_C_DEC::node_pointer | |
248 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 249 | rec_join(leaf_pointer p_l, leaf_pointer p_r, branch_bag& r_bag) |
4569a895 | 250 | { |
8fc81078 PC |
251 | _GLIBCXX_DEBUG_ASSERT(p_r != 0); |
252 | if (p_l == 0) | |
4569a895 | 253 | return (p_r); |
4569a895 | 254 | node_pointer p_ret = insert_branch(p_l, p_r, r_bag); |
f5886803 | 255 | _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == 2); |
47bea7b8 | 256 | return p_ret; |
4569a895 AT |
257 | } |
258 | ||
259 | PB_DS_CLASS_T_DEC | |
260 | typename PB_DS_CLASS_C_DEC::node_pointer | |
261 | PB_DS_CLASS_C_DEC:: | |
a345e45d BK |
262 | rec_join(leaf_pointer p_l, inode_pointer p_r, size_type checked_ind, |
263 | branch_bag& r_bag) | |
4569a895 | 264 | { |
47bea7b8 | 265 | #ifdef _GLIBCXX_DEBUG |
f5886803 FD |
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); | |
a345e45d | 268 | #endif |
4569a895 | 269 | |
8fc81078 | 270 | _GLIBCXX_DEBUG_ASSERT(p_r != 0); |
4569a895 | 271 | node_pointer p_ret = rec_join(p_r, p_l, checked_ind, r_bag); |
f5886803 | 272 | _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == lhs_leafs + rhs_leafs); |
47bea7b8 | 273 | return p_ret; |
4569a895 AT |
274 | } |
275 | ||
276 | PB_DS_CLASS_T_DEC | |
277 | typename PB_DS_CLASS_C_DEC::node_pointer | |
278 | PB_DS_CLASS_C_DEC:: | |
a345e45d | 279 | rec_join(inode_pointer p_l, leaf_pointer p_r, size_type checked_ind, branch_bag& r_bag) |
4569a895 | 280 | { |
8fc81078 PC |
281 | _GLIBCXX_DEBUG_ASSERT(p_l != 0); |
282 | _GLIBCXX_DEBUG_ASSERT(p_r != 0); | |
4569a895 | 283 | |
47bea7b8 | 284 | #ifdef _GLIBCXX_DEBUG |
f5886803 FD |
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); | |
a345e45d | 287 | #endif |
4569a895 | 288 | |
47bea7b8 | 289 | if (!p_l->should_be_mine(pref_begin(p_r), pref_end(p_r), checked_ind, this)) |
4569a895 AT |
290 | { |
291 | node_pointer p_ret = insert_branch(p_l, p_r, r_bag); | |
f5886803 FD |
292 | PB_DS_ASSERT_NODE_VALID(p_ret) |
293 | _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == | |
a345e45d | 294 | lhs_leafs + rhs_leafs); |
47bea7b8 | 295 | return p_ret; |
4569a895 AT |
296 | } |
297 | ||
47bea7b8 BK |
298 | node_pointer p_pot_child = p_l->add_child(p_r, pref_begin(p_r), |
299 | pref_end(p_r), this); | |
4569a895 AT |
300 | if (p_pot_child != p_r) |
301 | { | |
47bea7b8 | 302 | node_pointer p_new_child = rec_join(p_pot_child, p_r, p_l->get_e_ind(), |
4569a895 AT |
303 | r_bag); |
304 | ||
47bea7b8 BK |
305 | p_l->replace_child(p_new_child, pref_begin(p_new_child), |
306 | pref_end(p_new_child), this); | |
4569a895 AT |
307 | } |
308 | ||
f5886803 FD |
309 | PB_DS_ASSERT_NODE_VALID(p_l) |
310 | _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_l) == lhs_leafs + rhs_leafs); | |
47bea7b8 | 311 | return p_l; |
4569a895 AT |
312 | } |
313 | ||
314 | PB_DS_CLASS_T_DEC | |
315 | typename PB_DS_CLASS_C_DEC::node_pointer | |
316 | PB_DS_CLASS_C_DEC:: | |
a345e45d BK |
317 | rec_join(inode_pointer p_l, inode_pointer p_r, |
318 | branch_bag& r_bag) | |
4569a895 | 319 | { |
8fc81078 PC |
320 | _GLIBCXX_DEBUG_ASSERT(p_l != 0); |
321 | _GLIBCXX_DEBUG_ASSERT(p_r != 0); | |
4569a895 | 322 | |
47bea7b8 | 323 | #ifdef _GLIBCXX_DEBUG |
f5886803 FD |
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); | |
a345e45d | 326 | #endif |
47bea7b8 | 327 | |
a345e45d BK |
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(), | |
47bea7b8 | 330 | p_r->pref_b_it(), p_r->pref_e_it())) |
4569a895 | 331 | { |
a345e45d | 332 | for (typename inode::iterator it = p_r->begin(); |
4569a895 | 333 | it != p_r->end(); ++ it) |
a345e45d | 334 | { |
47bea7b8 BK |
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); | |
a345e45d | 339 | } |
4569a895 | 340 | |
a345e45d BK |
341 | p_r->~inode(); |
342 | s_inode_allocator.deallocate(p_r, 1); | |
f5886803 FD |
343 | PB_DS_ASSERT_NODE_VALID(p_l) |
344 | _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_l) == lhs_leafs + rhs_leafs); | |
47bea7b8 | 345 | return p_l; |
4569a895 AT |
346 | } |
347 | ||
a345e45d | 348 | if (p_l->get_e_ind() < p_r->get_e_ind() && |
47bea7b8 | 349 | p_l->should_be_mine(p_r->pref_b_it(), p_r->pref_e_it(), 0, this)) |
4569a895 | 350 | { |
47bea7b8 BK |
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); | |
f5886803 | 355 | PB_DS_ASSERT_NODE_VALID(p_l) |
47bea7b8 | 356 | return p_l; |
4569a895 AT |
357 | } |
358 | ||
a345e45d | 359 | if (p_r->get_e_ind() < p_l->get_e_ind() && |
47bea7b8 | 360 | p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) |
4569a895 | 361 | { |
47bea7b8 BK |
362 | node_pointer p_new_child = rec_join(p_r->get_join_child(p_l, this), p_l, |
363 | 0, r_bag); | |
4569a895 | 364 | |
a345e45d | 365 | p_r->replace_child(p_new_child, pref_begin(p_new_child), |
47bea7b8 | 366 | pref_end(p_new_child), this); |
4569a895 | 367 | |
f5886803 FD |
368 | PB_DS_ASSERT_NODE_VALID(p_r) |
369 | _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_r) == lhs_leafs + rhs_leafs); | |
47bea7b8 | 370 | return p_r; |
4569a895 AT |
371 | } |
372 | ||
373 | node_pointer p_ret = insert_branch(p_l, p_r, r_bag); | |
f5886803 FD |
374 | PB_DS_ASSERT_NODE_VALID(p_ret) |
375 | _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == lhs_leafs + rhs_leafs); | |
47bea7b8 | 376 | return p_ret; |
4569a895 AT |
377 | } |
378 | ||
379 | PB_DS_CLASS_T_DEC | |
47bea7b8 | 380 | inline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool> |
4569a895 AT |
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)); | |
a345e45d BK |
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))) | |
4569a895 | 387 | { |
f5886803 FD |
388 | PB_DS_CHECK_KEY_EXISTS(PB_DS_V2F(r_val)) |
389 | PB_DS_ASSERT_VALID((*this)) | |
47bea7b8 | 390 | return std::make_pair(iterator(p_lf), false); |
4569a895 AT |
391 | } |
392 | ||
f5886803 | 393 | PB_DS_CHECK_KEY_DOES_NOT_EXIST(PB_DS_V2F(r_val)) |
4569a895 AT |
394 | |
395 | leaf_pointer p_new_lf = s_leaf_allocator.allocate(1); | |
4569a895 AT |
396 | cond_dealtor cond(p_new_lf); |
397 | ||
398 | new (p_new_lf) leaf(r_val); | |
a345e45d | 399 | apply_update(p_new_lf, (node_update*)this); |
4569a895 | 400 | cond.set_call_destructor(); |
a345e45d | 401 | branch_bag bag; |
4569a895 | 402 | bag.add_branch(); |
47bea7b8 | 403 | m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, p_new_lf, 0, bag); |
4569a895 | 404 | m_p_head->m_p_parent->m_p_parent = m_p_head; |
4569a895 | 405 | cond.set_no_action_dtor(); |
4569a895 | 406 | ++m_size; |
4569a895 | 407 | update_min_max_for_inserted_leaf(p_new_lf); |
a345e45d | 408 | _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) |
f5886803 | 409 | PB_DS_ASSERT_VALID((*this)) |
47bea7b8 | 410 | return std::make_pair(point_iterator(p_new_lf), true); |
4569a895 AT |
411 | } |
412 | ||
413 | PB_DS_CLASS_T_DEC | |
414 | typename PB_DS_CLASS_C_DEC::size_type | |
415 | PB_DS_CLASS_C_DEC:: | |
a345e45d BK |
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) | |
4569a895 AT |
420 | { |
421 | size_type diff_pos = 0; | |
4569a895 AT |
422 | while (b_l != e_l) |
423 | { | |
424 | if (b_r == e_r) | |
425 | return (diff_pos); | |
a345e45d | 426 | if (access_traits::e_pos(*b_l) != access_traits::e_pos(*b_r)) |
4569a895 | 427 | return (diff_pos); |
4569a895 AT |
428 | ++b_l; |
429 | ++b_r; | |
4569a895 AT |
430 | ++diff_pos; |
431 | } | |
47bea7b8 BK |
432 | _GLIBCXX_DEBUG_ASSERT(b_r != e_r); |
433 | return diff_pos; | |
4569a895 AT |
434 | } |
435 | ||
436 | PB_DS_CLASS_T_DEC | |
a345e45d | 437 | typename PB_DS_CLASS_C_DEC::inode_pointer |
4569a895 | 438 | PB_DS_CLASS_C_DEC:: |
a345e45d | 439 | insert_branch(node_pointer p_l, node_pointer p_r, branch_bag& r_bag) |
4569a895 | 440 | { |
a345e45d BK |
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); | |
4569a895 | 445 | |
a345e45d | 446 | const size_type diff_ind = keys_diff_ind(left_b_it, left_e_it, |
47bea7b8 | 447 | right_b_it, right_e_it); |
4569a895 | 448 | |
a345e45d BK |
449 | inode_pointer p_new_nd = r_bag.get_branch(); |
450 | new (p_new_nd) inode(diff_ind, left_b_it); | |
47bea7b8 BK |
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); | |
4569a895 AT |
453 | p_l->m_p_parent = p_new_nd; |
454 | p_r->m_p_parent = p_new_nd; | |
f5886803 | 455 | PB_DS_ASSERT_NODE_VALID(p_new_nd) |
47bea7b8 | 456 | return (p_new_nd); |
4569a895 AT |
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 || | |
a345e45d BK |
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()))) | |
4569a895 AT |
467 | m_p_head->m_p_min = p_new_lf; |
468 | ||
469 | if (m_p_head->m_p_max == m_p_head || | |
a345e45d | 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()))) |
4569a895 AT |
471 | m_p_head->m_p_max = p_new_lf; |
472 | } |