| 6554 |
serge |
1 |
// -*- C++ -*- |
|
|
2 |
|
|
|
3 |
// Copyright (C) 2005-2015 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 |
// . |
|
|
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_/pat_trie_.hpp |
|
|
38 |
* Contains an implementation class for a patricia tree. |
|
|
39 |
*/ |
|
|
40 |
|
|
|
41 |
#include |
|
|
42 |
#include |
|
|
43 |
#include |
|
|
44 |
#include |
|
|
45 |
#include |
|
|
46 |
#include
|
|
|
47 |
#include |
|
|
48 |
#include |
|
|
49 |
#include |
|
|
50 |
#include |
|
|
51 |
#include |
|
|
52 |
#include |
|
|
53 |
#include |
|
|
54 |
#include |
|
|
55 |
#include |
|
|
56 |
#ifdef _GLIBCXX_DEBUG |
|
|
57 |
#include |
|
|
58 |
#endif |
|
|
59 |
#include |
|
|
60 |
|
|
|
61 |
namespace __gnu_pbds |
|
|
62 |
{ |
|
|
63 |
namespace detail |
|
|
64 |
{ |
|
|
65 |
#ifdef PB_DS_DATA_TRUE_INDICATOR |
|
|
66 |
#define PB_DS_PAT_TRIE_NAME pat_trie_map |
|
|
67 |
#endif |
|
|
68 |
|
|
|
69 |
#ifdef PB_DS_DATA_FALSE_INDICATOR |
|
|
70 |
#define PB_DS_PAT_TRIE_NAME pat_trie_set |
|
|
71 |
#endif |
|
|
72 |
|
|
|
73 |
#define PB_DS_CLASS_T_DEC \ |
|
|
74 |
template |
|
|
75 |
typename _Alloc> |
|
|
76 |
|
|
|
77 |
#define PB_DS_CLASS_C_DEC \ |
|
|
78 |
PB_DS_PAT_TRIE_NAME |
|
|
79 |
|
|
|
80 |
#define PB_DS_PAT_TRIE_TRAITS_BASE \ |
|
|
81 |
types_traits |
|
|
82 |
|
|
|
83 |
#ifdef _GLIBCXX_DEBUG |
|
|
84 |
#define PB_DS_DEBUG_MAP_BASE_C_DEC \ |
|
|
85 |
debug_map_base >, \ |
|
|
86 |
typename _Alloc::template rebind::other::const_reference> |
|
|
87 |
#endif |
|
|
88 |
|
|
|
89 |
|
|
|
90 |
/** |
|
|
91 |
* @brief PATRICIA trie. |
|
|
92 |
* @ingroup branch-detail |
|
|
93 |
* |
|
|
94 |
* This implementation loosely borrows ideas from: |
|
|
95 |
* 1) Fast Mergeable Integer Maps, Okasaki, Gill 1998 |
|
|
96 |
* 2) Ptset: Sets of integers implemented as Patricia trees, |
|
|
97 |
* Jean-Christophe Filliatr, 2000 |
|
|
98 |
*/ |
|
|
99 |
template |
|
|
100 |
typename _Alloc> |
|
|
101 |
class PB_DS_PAT_TRIE_NAME : |
|
|
102 |
#ifdef _GLIBCXX_DEBUG |
|
|
103 |
public PB_DS_DEBUG_MAP_BASE_C_DEC, |
|
|
104 |
#endif |
|
|
105 |
public Node_And_It_Traits::synth_access_traits, |
|
|
106 |
public Node_And_It_Traits::node_update, |
|
|
107 |
public PB_DS_PAT_TRIE_TRAITS_BASE, |
|
|
108 |
public pat_trie_base |
|
|
109 |
{ |
|
|
110 |
private: |
|
|
111 |
typedef pat_trie_base base_type; |
|
|
112 |
typedef PB_DS_PAT_TRIE_TRAITS_BASE traits_base; |
|
|
113 |
typedef Node_And_It_Traits traits_type; |
|
|
114 |
|
|
|
115 |
typedef typename traits_type::synth_access_traits synth_access_traits; |
|
|
116 |
typedef typename synth_access_traits::const_iterator a_const_iterator; |
|
|
117 |
|
|
|
118 |
typedef typename traits_type::node node; |
|
|
119 |
typedef typename _Alloc::template rebind __rebind_n; |
|
|
120 |
typedef typename __rebind_n::other::const_pointer node_const_pointer; |
|
|
121 |
typedef typename __rebind_n::other::pointer node_pointer; |
|
|
122 |
|
|
|
123 |
typedef typename traits_type::head head; |
|
|
124 |
typedef typename _Alloc::template rebind __rebind_h; |
|
|
125 |
typedef typename __rebind_h::other head_allocator; |
|
|
126 |
typedef typename head_allocator::pointer head_pointer; |
|
|
127 |
|
|
|
128 |
typedef typename traits_type::leaf leaf; |
|
|
129 |
typedef typename _Alloc::template rebind __rebind_l; |
|
|
130 |
typedef typename __rebind_l::other leaf_allocator; |
|
|
131 |
typedef typename leaf_allocator::pointer leaf_pointer; |
|
|
132 |
typedef typename leaf_allocator::const_pointer leaf_const_pointer; |
|
|
133 |
|
|
|
134 |
typedef typename traits_type::inode inode; |
|
|
135 |
typedef typename inode::iterator inode_iterator; |
|
|
136 |
typedef typename _Alloc::template rebind __rebind_in; |
|
|
137 |
typedef typename __rebind_in::other __rebind_ina; |
|
|
138 |
typedef typename __rebind_in::other inode_allocator; |
|
|
139 |
typedef typename __rebind_ina::pointer inode_pointer; |
|
|
140 |
typedef typename __rebind_ina::const_pointer inode_const_pointer; |
|
|
141 |
|
|
|
142 |
|
|
|
143 |
/// Conditional deallocator. |
|
|
144 |
class cond_dealtor |
|
|
145 |
{ |
|
|
146 |
protected: |
|
|
147 |
leaf_pointer m_p_nd; |
|
|
148 |
bool m_no_action_dtor; |
|
|
149 |
bool m_call_destructor; |
|
|
150 |
|
|
|
151 |
public: |
|
|
152 |
cond_dealtor(leaf_pointer p_nd) |
|
|
153 |
: m_p_nd(p_nd), m_no_action_dtor(false), m_call_destructor(false) |
|
|
154 |
{ } |
|
|
155 |
|
|
|
156 |
void |
|
|
157 |
set_no_action_dtor() |
|
|
158 |
{ m_no_action_dtor = true; } |
|
|
159 |
|
|
|
160 |
void |
|
|
161 |
set_call_destructor() |
|
|
162 |
{ m_call_destructor = true; } |
|
|
163 |
|
|
|
164 |
~cond_dealtor() |
|
|
165 |
{ |
|
|
166 |
if (m_no_action_dtor) |
|
|
167 |
return; |
|
|
168 |
|
|
|
169 |
if (m_call_destructor) |
|
|
170 |
m_p_nd->~leaf(); |
|
|
171 |
|
|
|
172 |
s_leaf_allocator.deallocate(m_p_nd, 1); |
|
|
173 |
} |
|
|
174 |
}; |
|
|
175 |
|
|
|
176 |
|
|
|
177 |
/// Branch bag, for split-join. |
|
|
178 |
class branch_bag |
|
|
179 |
{ |
|
|
180 |
private: |
|
|
181 |
typedef inode_pointer __inp; |
|
|
182 |
typedef typename _Alloc::template rebind<__inp>::other __rebind_inp; |
|
|
183 |
|
|
|
184 |
#ifdef _GLIBCXX_DEBUG |
|
|
185 |
typedef std::_GLIBCXX_STD_C::list<__inp, __rebind_inp> bag_type; |
|
|
186 |
#else |
|
|
187 |
typedef std::list<__inp, __rebind_inp> bag_type; |
|
|
188 |
#endif |
|
|
189 |
|
|
|
190 |
bag_type m_bag; |
|
|
191 |
public: |
|
|
192 |
void |
|
|
193 |
add_branch() |
|
|
194 |
{ |
|
|
195 |
inode_pointer p_nd = s_inode_allocator.allocate(1); |
|
|
196 |
__try |
|
|
197 |
{ |
|
|
198 |
m_bag.push_back(p_nd); |
|
|
199 |
} |
|
|
200 |
__catch(...) |
|
|
201 |
{ |
|
|
202 |
s_inode_allocator.deallocate(p_nd, 1); |
|
|
203 |
__throw_exception_again; |
|
|
204 |
} |
|
|
205 |
} |
|
|
206 |
|
|
|
207 |
inode_pointer |
|
|
208 |
get_branch() |
|
|
209 |
{ |
|
|
210 |
_GLIBCXX_DEBUG_ASSERT(!m_bag.empty()); |
|
|
211 |
inode_pointer p_nd = *m_bag.begin(); |
|
|
212 |
m_bag.pop_front(); |
|
|
213 |
return p_nd; |
|
|
214 |
} |
|
|
215 |
|
|
|
216 |
~branch_bag() |
|
|
217 |
{ |
|
|
218 |
while (!m_bag.empty()) |
|
|
219 |
{ |
|
|
220 |
inode_pointer p_nd = *m_bag.begin(); |
|
|
221 |
s_inode_allocator.deallocate(p_nd, 1); |
|
|
222 |
m_bag.pop_front(); |
|
|
223 |
} |
|
|
224 |
} |
|
|
225 |
|
|
|
226 |
inline bool |
|
|
227 |
empty() const |
|
|
228 |
{ return m_bag.empty(); } |
|
|
229 |
}; |
|
|
230 |
|
|
|
231 |
#ifdef _GLIBCXX_DEBUG |
|
|
232 |
typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; |
|
|
233 |
#endif |
|
|
234 |
|
|
|
235 |
typedef typename traits_type::null_node_update_pointer null_node_update_pointer; |
|
|
236 |
|
|
|
237 |
public: |
|
|
238 |
typedef pat_trie_tag container_category; |
|
|
239 |
typedef _Alloc allocator_type; |
|
|
240 |
typedef typename _Alloc::size_type size_type; |
|
|
241 |
typedef typename _Alloc::difference_type difference_type; |
|
|
242 |
|
|
|
243 |
typedef typename traits_base::key_type key_type; |
|
|
244 |
typedef typename traits_base::key_pointer key_pointer; |
|
|
245 |
typedef typename traits_base::key_const_pointer key_const_pointer; |
|
|
246 |
typedef typename traits_base::key_reference key_reference; |
|
|
247 |
typedef typename traits_base::key_const_reference key_const_reference; |
|
|
248 |
typedef typename traits_base::mapped_type mapped_type; |
|
|
249 |
typedef typename traits_base::mapped_pointer mapped_pointer; |
|
|
250 |
typedef typename traits_base::mapped_const_pointer mapped_const_pointer; |
|
|
251 |
typedef typename traits_base::mapped_reference mapped_reference; |
|
|
252 |
typedef typename traits_base::mapped_const_reference mapped_const_reference; |
|
|
253 |
typedef typename traits_base::value_type value_type; |
|
|
254 |
typedef typename traits_base::pointer pointer; |
|
|
255 |
typedef typename traits_base::const_pointer const_pointer; |
|
|
256 |
typedef typename traits_base::reference reference; |
|
|
257 |
typedef typename traits_base::const_reference const_reference; |
|
|
258 |
|
|
|
259 |
typedef typename traits_type::access_traits access_traits; |
|
|
260 |
typedef typename traits_type::const_iterator point_const_iterator; |
|
|
261 |
typedef typename traits_type::iterator point_iterator; |
|
|
262 |
typedef point_const_iterator const_iterator; |
|
|
263 |
typedef point_iterator iterator; |
|
|
264 |
|
|
|
265 |
typedef typename traits_type::reverse_iterator reverse_iterator; |
|
|
266 |
typedef typename traits_type::const_reverse_iterator const_reverse_iterator; |
|
|
267 |
typedef typename traits_type::node_const_iterator node_const_iterator; |
|
|
268 |
typedef typename traits_type::node_iterator node_iterator; |
|
|
269 |
typedef typename traits_type::node_update node_update; |
|
|
270 |
|
|
|
271 |
PB_DS_PAT_TRIE_NAME(); |
|
|
272 |
|
|
|
273 |
PB_DS_PAT_TRIE_NAME(const access_traits&); |
|
|
274 |
|
|
|
275 |
PB_DS_PAT_TRIE_NAME(const PB_DS_CLASS_C_DEC&); |
|
|
276 |
|
|
|
277 |
void |
|
|
278 |
swap(PB_DS_CLASS_C_DEC&); |
|
|
279 |
|
|
|
280 |
~PB_DS_PAT_TRIE_NAME(); |
|
|
281 |
|
|
|
282 |
inline bool |
|
|
283 |
empty() const; |
|
|
284 |
|
|
|
285 |
inline size_type |
|
|
286 |
size() const; |
|
|
287 |
|
|
|
288 |
inline size_type |
|
|
289 |
max_size() const; |
|
|
290 |
|
|
|
291 |
access_traits& |
|
|
292 |
get_access_traits(); |
|
|
293 |
|
|
|
294 |
const access_traits& |
|
|
295 |
get_access_traits() const; |
|
|
296 |
|
|
|
297 |
node_update& |
|
|
298 |
get_node_update(); |
|
|
299 |
|
|
|
300 |
const node_update& |
|
|
301 |
get_node_update() const; |
|
|
302 |
|
|
|
303 |
inline std::pair |
|
|
304 |
insert(const_reference); |
|
|
305 |
|
|
|
306 |
inline mapped_reference |
|
|
307 |
operator[](key_const_reference r_key) |
|
|
308 |
{ |
|
|
309 |
#ifdef PB_DS_DATA_TRUE_INDICATOR |
|
|
310 |
return insert(std::make_pair(r_key, mapped_type())).first->second; |
|
|
311 |
#else |
|
|
312 |
insert(r_key); |
|
|
313 |
return traits_base::s_null_type; |
|
|
314 |
#endif |
|
|
315 |
} |
|
|
316 |
|
|
|
317 |
inline point_iterator |
|
|
318 |
find(key_const_reference); |
|
|
319 |
|
|
|
320 |
inline point_const_iterator |
|
|
321 |
find(key_const_reference) const; |
|
|
322 |
|
|
|
323 |
inline point_iterator |
|
|
324 |
lower_bound(key_const_reference); |
|
|
325 |
|
|
|
326 |
inline point_const_iterator |
|
|
327 |
lower_bound(key_const_reference) const; |
|
|
328 |
|
|
|
329 |
inline point_iterator |
|
|
330 |
upper_bound(key_const_reference); |
|
|
331 |
|
|
|
332 |
inline point_const_iterator |
|
|
333 |
upper_bound(key_const_reference) const; |
|
|
334 |
|
|
|
335 |
void |
|
|
336 |
clear(); |
|
|
337 |
|
|
|
338 |
inline bool |
|
|
339 |
erase(key_const_reference); |
|
|
340 |
|
|
|
341 |
inline const_iterator |
|
|
342 |
erase(const_iterator); |
|
|
343 |
|
|
|
344 |
#ifdef PB_DS_DATA_TRUE_INDICATOR |
|
|
345 |
inline iterator |
|
|
346 |
erase(iterator); |
|
|
347 |
#endif |
|
|
348 |
|
|
|
349 |
inline const_reverse_iterator |
|
|
350 |
erase(const_reverse_iterator); |
|
|
351 |
|
|
|
352 |
#ifdef PB_DS_DATA_TRUE_INDICATOR |
|
|
353 |
inline reverse_iterator |
|
|
354 |
erase(reverse_iterator); |
|
|
355 |
#endif |
|
|
356 |
|
|
|
357 |
template |
|
|
358 |
inline size_type |
|
|
359 |
erase_if(Pred); |
|
|
360 |
|
|
|
361 |
void |
|
|
362 |
join(PB_DS_CLASS_C_DEC&); |
|
|
363 |
|
|
|
364 |
void |
|
|
365 |
split(key_const_reference, PB_DS_CLASS_C_DEC&); |
|
|
366 |
|
|
|
367 |
inline iterator |
|
|
368 |
begin(); |
|
|
369 |
|
|
|
370 |
inline const_iterator |
|
|
371 |
begin() const; |
|
|
372 |
|
|
|
373 |
inline iterator |
|
|
374 |
end(); |
|
|
375 |
|
|
|
376 |
inline const_iterator |
|
|
377 |
end() const; |
|
|
378 |
|
|
|
379 |
inline reverse_iterator |
|
|
380 |
rbegin(); |
|
|
381 |
|
|
|
382 |
inline const_reverse_iterator |
|
|
383 |
rbegin() const; |
|
|
384 |
|
|
|
385 |
inline reverse_iterator |
|
|
386 |
rend(); |
|
|
387 |
|
|
|
388 |
inline const_reverse_iterator |
|
|
389 |
rend() const; |
|
|
390 |
|
|
|
391 |
/// Returns a const node_iterator corresponding to the node at the |
|
|
392 |
/// root of the tree. |
|
|
393 |
inline node_const_iterator |
|
|
394 |
node_begin() const; |
|
|
395 |
|
|
|
396 |
/// Returns a node_iterator corresponding to the node at the |
|
|
397 |
/// root of the tree. |
|
|
398 |
inline node_iterator |
|
|
399 |
node_begin(); |
|
|
400 |
|
|
|
401 |
/// Returns a const node_iterator corresponding to a node just |
|
|
402 |
/// after a leaf of the tree. |
|
|
403 |
inline node_const_iterator |
|
|
404 |
node_end() const; |
|
|
405 |
|
|
|
406 |
/// Returns a node_iterator corresponding to a node just |
|
|
407 |
/// after a leaf of the tree. |
|
|
408 |
inline node_iterator |
|
|
409 |
node_end(); |
|
|
410 |
|
|
|
411 |
#ifdef PB_DS_PAT_TRIE_TRACE_ |
|
|
412 |
void |
|
|
413 |
trace() const; |
|
|
414 |
#endif |
|
|
415 |
|
|
|
416 |
protected: |
|
|
417 |
template |
|
|
418 |
void |
|
|
419 |
copy_from_range(It, It); |
|
|
420 |
|
|
|
421 |
void |
|
|
422 |
value_swap(PB_DS_CLASS_C_DEC&); |
|
|
423 |
|
|
|
424 |
node_pointer |
|
|
425 |
recursive_copy_node(node_const_pointer); |
|
|
426 |
|
|
|
427 |
private: |
|
|
428 |
void |
|
|
429 |
initialize(); |
|
|
430 |
|
|
|
431 |
inline void |
|
|
432 |
apply_update(node_pointer, null_node_update_pointer); |
|
|
433 |
|
|
|
434 |
template |
|
|
435 |
inline void |
|
|
436 |
apply_update(node_pointer, Node_Update_*); |
|
|
437 |
|
|
|
438 |
bool |
|
|
439 |
join_prep(PB_DS_CLASS_C_DEC&, branch_bag&); |
|
|
440 |
|
|
|
441 |
void |
|
|
442 |
rec_join_prep(node_const_pointer, node_const_pointer, branch_bag&); |
|
|
443 |
|
|
|
444 |
void |
|
|
445 |
rec_join_prep(leaf_const_pointer, leaf_const_pointer, branch_bag&); |
|
|
446 |
|
|
|
447 |
void |
|
|
448 |
rec_join_prep(leaf_const_pointer, inode_const_pointer, branch_bag&); |
|
|
449 |
|
|
|
450 |
void |
|
|
451 |
rec_join_prep(inode_const_pointer, leaf_const_pointer, branch_bag&); |
|
|
452 |
|
|
|
453 |
void |
|
|
454 |
rec_join_prep(inode_const_pointer, inode_const_pointer, branch_bag&); |
|
|
455 |
|
|
|
456 |
node_pointer |
|
|
457 |
rec_join(node_pointer, node_pointer, size_type, branch_bag&); |
|
|
458 |
|
|
|
459 |
node_pointer |
|
|
460 |
rec_join(leaf_pointer, leaf_pointer, branch_bag&); |
|
|
461 |
|
|
|
462 |
node_pointer |
|
|
463 |
rec_join(leaf_pointer, inode_pointer, size_type, branch_bag&); |
|
|
464 |
|
|
|
465 |
node_pointer |
|
|
466 |
rec_join(inode_pointer, leaf_pointer, size_type, branch_bag&); |
|
|
467 |
|
|
|
468 |
node_pointer |
|
|
469 |
rec_join(inode_pointer, inode_pointer, branch_bag&); |
|
|
470 |
|
|
|
471 |
size_type |
|
|
472 |
keys_diff_ind(typename access_traits::const_iterator, |
|
|
473 |
typename access_traits::const_iterator, |
|
|
474 |
typename access_traits::const_iterator, |
|
|
475 |
typename access_traits::const_iterator); |
|
|
476 |
|
|
|
477 |
inode_pointer |
|
|
478 |
insert_branch(node_pointer, node_pointer, branch_bag&); |
|
|
479 |
|
|
|
480 |
void |
|
|
481 |
update_min_max_for_inserted_leaf(leaf_pointer); |
|
|
482 |
|
|
|
483 |
void |
|
|
484 |
erase_leaf(leaf_pointer); |
|
|
485 |
|
|
|
486 |
inline void |
|
|
487 |
actual_erase_leaf(leaf_pointer); |
|
|
488 |
|
|
|
489 |
void |
|
|
490 |
clear_imp(node_pointer); |
|
|
491 |
|
|
|
492 |
void |
|
|
493 |
erase_fixup(inode_pointer); |
|
|
494 |
|
|
|
495 |
void |
|
|
496 |
update_min_max_for_erased_leaf(leaf_pointer); |
|
|
497 |
|
|
|
498 |
static inline a_const_iterator |
|
|
499 |
pref_begin(node_const_pointer); |
|
|
500 |
|
|
|
501 |
static inline a_const_iterator |
|
|
502 |
pref_end(node_const_pointer); |
|
|
503 |
|
|
|
504 |
inline node_pointer |
|
|
505 |
find_imp(key_const_reference); |
|
|
506 |
|
|
|
507 |
inline node_pointer |
|
|
508 |
lower_bound_imp(key_const_reference); |
|
|
509 |
|
|
|
510 |
inline node_pointer |
|
|
511 |
upper_bound_imp(key_const_reference); |
|
|
512 |
|
|
|
513 |
inline static leaf_const_pointer |
|
|
514 |
leftmost_descendant(node_const_pointer); |
|
|
515 |
|
|
|
516 |
inline static leaf_pointer |
|
|
517 |
leftmost_descendant(node_pointer); |
|
|
518 |
|
|
|
519 |
inline static leaf_const_pointer |
|
|
520 |
rightmost_descendant(node_const_pointer); |
|
|
521 |
|
|
|
522 |
inline static leaf_pointer |
|
|
523 |
rightmost_descendant(node_pointer); |
|
|
524 |
|
|
|
525 |
#ifdef _GLIBCXX_DEBUG |
|
|
526 |
void |
|
|
527 |
assert_valid(const char*, int) const; |
|
|
528 |
|
|
|
529 |
void |
|
|
530 |
assert_iterators(const char*, int) const; |
|
|
531 |
|
|
|
532 |
void |
|
|
533 |
assert_reverse_iterators(const char*, int) const; |
|
|
534 |
|
|
|
535 |
static size_type |
|
|
536 |
recursive_count_leafs(node_const_pointer, const char*, int); |
|
|
537 |
#endif |
|
|
538 |
|
|
|
539 |
#ifdef PB_DS_PAT_TRIE_TRACE_ |
|
|
540 |
static void |
|
|
541 |
trace_node(node_const_pointer, size_type); |
|
|
542 |
|
|
|
543 |
template |
|
|
544 |
static void |
|
|
545 |
trace_node_metadata(node_const_pointer, type_to_type); |
|
|
546 |
|
|
|
547 |
static void |
|
|
548 |
trace_node_metadata(node_const_pointer, type_to_type); |
|
|
549 |
#endif |
|
|
550 |
|
|
|
551 |
leaf_pointer |
|
|
552 |
split_prep(key_const_reference, PB_DS_CLASS_C_DEC&, branch_bag&); |
|
|
553 |
|
|
|
554 |
node_pointer |
|
|
555 |
rec_split(node_pointer, a_const_iterator, a_const_iterator, |
|
|
556 |
PB_DS_CLASS_C_DEC&, branch_bag&); |
|
|
557 |
|
|
|
558 |
void |
|
|
559 |
split_insert_branch(size_type, a_const_iterator, inode_iterator, |
|
|
560 |
size_type, branch_bag&); |
|
|
561 |
|
|
|
562 |
static head_allocator s_head_allocator; |
|
|
563 |
static inode_allocator s_inode_allocator; |
|
|
564 |
static leaf_allocator s_leaf_allocator; |
|
|
565 |
|
|
|
566 |
head_pointer m_p_head; |
|
|
567 |
size_type m_size; |
|
|
568 |
}; |
|
|
569 |
|
|
|
570 |
#define PB_DS_ASSERT_NODE_VALID(X) \ |
|
|
571 |
_GLIBCXX_DEBUG_ONLY(X->assert_valid(this, __FILE__, __LINE__);) |
|
|
572 |
|
|
|
573 |
#define PB_DS_RECURSIVE_COUNT_LEAFS(X) \ |
|
|
574 |
recursive_count_leafs(X, __FILE__, __LINE__) |
|
|
575 |
|
|
|
576 |
#include |
|
|
577 |
#include |
|
|
578 |
#include |
|
|
579 |
#include |
|
|
580 |
#include |
|
|
581 |
#include |
|
|
582 |
#include |
|
|
583 |
#include |
|
|
584 |
#include |
|
|
585 |
#include |
|
|
586 |
#include |
|
|
587 |
|
|
|
588 |
#undef PB_DS_RECURSIVE_COUNT_LEAFS |
|
|
589 |
#undef PB_DS_ASSERT_NODE_VALID |
|
|
590 |
#undef PB_DS_CLASS_C_DEC |
|
|
591 |
#undef PB_DS_CLASS_T_DEC |
|
|
592 |
#undef PB_DS_PAT_TRIE_NAME |
|
|
593 |
#undef PB_DS_PAT_TRIE_TRAITS_BASE |
|
|
594 |
#undef PB_DS_DEBUG_MAP_BASE_C_DEC |
|
|
595 |
} // namespace detail |
|
|
596 |
} // namespace __gnu_pbds |