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