]>
Commit | Line | Data |
---|---|---|
36fed23c | 1 | // -*- C++ -*- |
2 | ||
fbd26352 | 3 | // Copyright (C) 2005-2019 Free Software Foundation, Inc. |
36fed23c | 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 | |
6bc9506f | 8 | // Foundation; either version 3, or (at your option) any later |
36fed23c | 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 | ||
6bc9506f | 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/>. | |
36fed23c | 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 | /** | |
4f4a327e | 37 | * @file pat_trie_/pat_trie_.hpp |
36fed23c | 38 | * Contains an implementation class for a patricia tree. |
39 | */ | |
40 | ||
36fed23c | 41 | #include <iterator> |
42 | #include <utility> | |
43 | #include <algorithm> | |
44 | #include <functional> | |
45 | #include <assert.h> | |
46 | #include <list> | |
4f4a327e | 47 | #include <ext/pb_ds/exception.hpp> |
48 | #include <ext/pb_ds/tag_and_trait.hpp> | |
49 | #include <ext/pb_ds/tree_policy.hpp> | |
50 | #include <ext/pb_ds/detail/cond_dealtor.hpp> | |
51 | #include <ext/pb_ds/detail/type_utils.hpp> | |
52 | #include <ext/pb_ds/detail/types_traits.hpp> | |
53 | #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> | |
54 | #include <ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp> | |
55 | #include <ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp> | |
2b31bec4 | 56 | #ifdef _GLIBCXX_DEBUG |
6c9bd031 | 57 | #include <ext/pb_ds/detail/debug_map_base.hpp> |
4f4a327e | 58 | #endif |
2b31bec4 | 59 | #include <debug/debug.h> |
36fed23c | 60 | |
b34535d7 | 61 | namespace __gnu_pbds |
36fed23c | 62 | { |
63 | namespace detail | |
64 | { | |
36fed23c | 65 | #ifdef PB_DS_DATA_TRUE_INDICATOR |
4f4a327e | 66 | #define PB_DS_PAT_TRIE_NAME pat_trie_map |
67 | #endif | |
36fed23c | 68 | |
69 | #ifdef PB_DS_DATA_FALSE_INDICATOR | |
4f4a327e | 70 | #define PB_DS_PAT_TRIE_NAME pat_trie_set |
71 | #endif | |
72 | ||
73 | #define PB_DS_CLASS_T_DEC \ | |
74 | template<typename Key, typename Mapped, typename Node_And_It_Traits, \ | |
75 | typename _Alloc> | |
36fed23c | 76 | |
ea18d4a3 | 77 | #define PB_DS_CLASS_C_DEC \ |
4f4a327e | 78 | PB_DS_PAT_TRIE_NAME<Key, Mapped, Node_And_It_Traits, _Alloc> |
36fed23c | 79 | |
4f4a327e | 80 | #define PB_DS_PAT_TRIE_TRAITS_BASE \ |
81 | types_traits<Key, Mapped, _Alloc, false> | |
36fed23c | 82 | |
2b31bec4 | 83 | #ifdef _GLIBCXX_DEBUG |
6c9bd031 | 84 | #define PB_DS_DEBUG_MAP_BASE_C_DEC \ |
4f4a327e | 85 | debug_map_base<Key, eq_by_less<Key, std::less<Key> >, \ |
86 | typename _Alloc::template rebind<Key>::other::const_reference> | |
87 | #endif | |
36fed23c | 88 | |
36fed23c | 89 | |
36fed23c | 90 | /** |
4f4a327e | 91 | * @brief PATRICIA trie. |
3f2eba6f | 92 | * @ingroup branch-detail |
4f4a327e | 93 | * |
3f2eba6f | 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 | |
4f4a327e | 98 | */ |
99 | template<typename Key, typename Mapped, typename Node_And_It_Traits, | |
100 | typename _Alloc> | |
101 | class PB_DS_PAT_TRIE_NAME : | |
2b31bec4 | 102 | #ifdef _GLIBCXX_DEBUG |
6c9bd031 | 103 | public PB_DS_DEBUG_MAP_BASE_C_DEC, |
4f4a327e | 104 | #endif |
105 | public Node_And_It_Traits::synth_access_traits, | |
36fed23c | 106 | public Node_And_It_Traits::node_update, |
4f4a327e | 107 | public PB_DS_PAT_TRIE_TRAITS_BASE, |
108 | public pat_trie_base | |
36fed23c | 109 | { |
36fed23c | 110 | private: |
4f4a327e | 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<node> __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<head> __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<leaf> __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<inode> __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 | { } | |
36fed23c | 155 | |
4f4a327e | 156 | void |
157 | set_no_action_dtor() | |
158 | { m_no_action_dtor = true; } | |
36fed23c | 159 | |
4f4a327e | 160 | void |
161 | set_call_destructor() | |
162 | { m_call_destructor = true; } | |
36fed23c | 163 | |
4f4a327e | 164 | ~cond_dealtor() |
165 | { | |
166 | if (m_no_action_dtor) | |
167 | return; | |
36fed23c | 168 | |
4f4a327e | 169 | if (m_call_destructor) |
170 | m_p_nd->~leaf(); | |
36fed23c | 171 | |
4f4a327e | 172 | s_leaf_allocator.deallocate(m_p_nd, 1); |
173 | } | |
174 | }; | |
36fed23c | 175 | |
36fed23c | 176 | |
4f4a327e | 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; | |
36fed23c | 183 | |
2b31bec4 | 184 | #ifdef _GLIBCXX_DEBUG |
4f4a327e | 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 | }; | |
36fed23c | 230 | |
4f4a327e | 231 | #ifdef _GLIBCXX_DEBUG |
232 | typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; | |
233 | #endif | |
36fed23c | 234 | |
4f4a327e | 235 | typedef typename traits_type::null_node_update_pointer null_node_update_pointer; |
36fed23c | 236 | |
237 | public: | |
4f4a327e | 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&); | |
36fed23c | 276 | |
277 | void | |
ea18d4a3 | 278 | swap(PB_DS_CLASS_C_DEC&); |
36fed23c | 279 | |
4f4a327e | 280 | ~PB_DS_PAT_TRIE_NAME(); |
36fed23c | 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 | ||
4f4a327e | 291 | access_traits& |
292 | get_access_traits(); | |
36fed23c | 293 | |
4f4a327e | 294 | const access_traits& |
295 | get_access_traits() const; | |
36fed23c | 296 | |
4f4a327e | 297 | node_update& |
36fed23c | 298 | get_node_update(); |
299 | ||
4f4a327e | 300 | const node_update& |
36fed23c | 301 | get_node_update() const; |
302 | ||
ea18d4a3 | 303 | inline std::pair<point_iterator, bool> |
304 | insert(const_reference); | |
36fed23c | 305 | |
306 | inline mapped_reference | |
4f4a327e | 307 | operator[](key_const_reference r_key) |
36fed23c | 308 | { |
309 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
ea18d4a3 | 310 | return insert(std::make_pair(r_key, mapped_type())).first->second; |
4f4a327e | 311 | #else |
36fed23c | 312 | insert(r_key); |
4f4a327e | 313 | return traits_base::s_null_type; |
314 | #endif | |
36fed23c | 315 | } |
316 | ||
317 | inline point_iterator | |
4f4a327e | 318 | find(key_const_reference); |
36fed23c | 319 | |
4f4a327e | 320 | inline point_const_iterator |
321 | find(key_const_reference) const; | |
36fed23c | 322 | |
323 | inline point_iterator | |
4f4a327e | 324 | lower_bound(key_const_reference); |
36fed23c | 325 | |
4f4a327e | 326 | inline point_const_iterator |
327 | lower_bound(key_const_reference) const; | |
36fed23c | 328 | |
329 | inline point_iterator | |
4f4a327e | 330 | upper_bound(key_const_reference); |
36fed23c | 331 | |
4f4a327e | 332 | inline point_const_iterator |
333 | upper_bound(key_const_reference) const; | |
36fed23c | 334 | |
335 | void | |
336 | clear(); | |
337 | ||
338 | inline bool | |
4f4a327e | 339 | erase(key_const_reference); |
36fed23c | 340 | |
341 | inline const_iterator | |
ea18d4a3 | 342 | erase(const_iterator); |
36fed23c | 343 | |
344 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
345 | inline iterator | |
ea18d4a3 | 346 | erase(iterator); |
4f4a327e | 347 | #endif |
36fed23c | 348 | |
349 | inline const_reverse_iterator | |
ea18d4a3 | 350 | erase(const_reverse_iterator); |
36fed23c | 351 | |
352 | #ifdef PB_DS_DATA_TRUE_INDICATOR | |
353 | inline reverse_iterator | |
ea18d4a3 | 354 | erase(reverse_iterator); |
4f4a327e | 355 | #endif |
36fed23c | 356 | |
357 | template<typename Pred> | |
358 | inline size_type | |
ea18d4a3 | 359 | erase_if(Pred); |
36fed23c | 360 | |
361 | void | |
ea18d4a3 | 362 | join(PB_DS_CLASS_C_DEC&); |
36fed23c | 363 | |
364 | void | |
4f4a327e | 365 | split(key_const_reference, PB_DS_CLASS_C_DEC&); |
36fed23c | 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 | ||
3f2eba6f | 391 | /// Returns a const node_iterator corresponding to the node at the |
392 | /// root of the tree. | |
4f4a327e | 393 | inline node_const_iterator |
36fed23c | 394 | node_begin() const; |
395 | ||
3f2eba6f | 396 | /// Returns a node_iterator corresponding to the node at the |
397 | /// root of the tree. | |
36fed23c | 398 | inline node_iterator |
399 | node_begin(); | |
400 | ||
3f2eba6f | 401 | /// Returns a const node_iterator corresponding to a node just |
402 | /// after a leaf of the tree. | |
4f4a327e | 403 | inline node_const_iterator |
36fed23c | 404 | node_end() const; |
405 | ||
3f2eba6f | 406 | /// Returns a node_iterator corresponding to a node just |
407 | /// after a leaf of the tree. | |
36fed23c | 408 | inline node_iterator |
409 | node_end(); | |
410 | ||
411 | #ifdef PB_DS_PAT_TRIE_TRACE_ | |
36fed23c | 412 | void |
413 | trace() const; | |
4f4a327e | 414 | #endif |
36fed23c | 415 | |
416 | protected: | |
36fed23c | 417 | template<typename It> |
418 | void | |
ea18d4a3 | 419 | copy_from_range(It, It); |
36fed23c | 420 | |
421 | void | |
ea18d4a3 | 422 | value_swap(PB_DS_CLASS_C_DEC&); |
36fed23c | 423 | |
424 | node_pointer | |
4f4a327e | 425 | recursive_copy_node(node_const_pointer); |
36fed23c | 426 | |
427 | private: | |
36fed23c | 428 | void |
429 | initialize(); | |
430 | ||
431 | inline void | |
ea18d4a3 | 432 | apply_update(node_pointer, null_node_update_pointer); |
36fed23c | 433 | |
434 | template<typename Node_Update_> | |
435 | inline void | |
ea18d4a3 | 436 | apply_update(node_pointer, Node_Update_*); |
36fed23c | 437 | |
438 | bool | |
4f4a327e | 439 | join_prep(PB_DS_CLASS_C_DEC&, branch_bag&); |
36fed23c | 440 | |
441 | void | |
4f4a327e | 442 | rec_join_prep(node_const_pointer, node_const_pointer, branch_bag&); |
36fed23c | 443 | |
444 | void | |
4f4a327e | 445 | rec_join_prep(leaf_const_pointer, leaf_const_pointer, branch_bag&); |
36fed23c | 446 | |
447 | void | |
4f4a327e | 448 | rec_join_prep(leaf_const_pointer, inode_const_pointer, branch_bag&); |
36fed23c | 449 | |
450 | void | |
4f4a327e | 451 | rec_join_prep(inode_const_pointer, leaf_const_pointer, branch_bag&); |
36fed23c | 452 | |
453 | void | |
4f4a327e | 454 | rec_join_prep(inode_const_pointer, inode_const_pointer, branch_bag&); |
36fed23c | 455 | |
456 | node_pointer | |
4f4a327e | 457 | rec_join(node_pointer, node_pointer, size_type, branch_bag&); |
36fed23c | 458 | |
459 | node_pointer | |
4f4a327e | 460 | rec_join(leaf_pointer, leaf_pointer, branch_bag&); |
36fed23c | 461 | |
462 | node_pointer | |
4f4a327e | 463 | rec_join(leaf_pointer, inode_pointer, size_type, branch_bag&); |
36fed23c | 464 | |
465 | node_pointer | |
4f4a327e | 466 | rec_join(inode_pointer, leaf_pointer, size_type, branch_bag&); |
36fed23c | 467 | |
468 | node_pointer | |
4f4a327e | 469 | rec_join(inode_pointer, inode_pointer, branch_bag&); |
36fed23c | 470 | |
471 | size_type | |
4f4a327e | 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); | |
36fed23c | 476 | |
4f4a327e | 477 | inode_pointer |
478 | insert_branch(node_pointer, node_pointer, branch_bag&); | |
36fed23c | 479 | |
480 | void | |
ea18d4a3 | 481 | update_min_max_for_inserted_leaf(leaf_pointer); |
36fed23c | 482 | |
483 | void | |
ea18d4a3 | 484 | erase_leaf(leaf_pointer); |
36fed23c | 485 | |
486 | inline void | |
ea18d4a3 | 487 | actual_erase_leaf(leaf_pointer); |
36fed23c | 488 | |
489 | void | |
ea18d4a3 | 490 | clear_imp(node_pointer); |
36fed23c | 491 | |
492 | void | |
4f4a327e | 493 | erase_fixup(inode_pointer); |
36fed23c | 494 | |
495 | void | |
ea18d4a3 | 496 | update_min_max_for_erased_leaf(leaf_pointer); |
36fed23c | 497 | |
4f4a327e | 498 | static inline a_const_iterator |
499 | pref_begin(node_const_pointer); | |
36fed23c | 500 | |
4f4a327e | 501 | static inline a_const_iterator |
502 | pref_end(node_const_pointer); | |
36fed23c | 503 | |
504 | inline node_pointer | |
4f4a327e | 505 | find_imp(key_const_reference); |
36fed23c | 506 | |
507 | inline node_pointer | |
4f4a327e | 508 | lower_bound_imp(key_const_reference); |
36fed23c | 509 | |
510 | inline node_pointer | |
4f4a327e | 511 | upper_bound_imp(key_const_reference); |
36fed23c | 512 | |
4f4a327e | 513 | inline static leaf_const_pointer |
514 | leftmost_descendant(node_const_pointer); | |
36fed23c | 515 | |
516 | inline static leaf_pointer | |
ea18d4a3 | 517 | leftmost_descendant(node_pointer); |
36fed23c | 518 | |
4f4a327e | 519 | inline static leaf_const_pointer |
520 | rightmost_descendant(node_const_pointer); | |
36fed23c | 521 | |
522 | inline static leaf_pointer | |
ea18d4a3 | 523 | rightmost_descendant(node_pointer); |
36fed23c | 524 | |
2b31bec4 | 525 | #ifdef _GLIBCXX_DEBUG |
36fed23c | 526 | void |
4f4a327e | 527 | assert_valid(const char*, int) const; |
36fed23c | 528 | |
529 | void | |
4f4a327e | 530 | assert_iterators(const char*, int) const; |
36fed23c | 531 | |
532 | void | |
4f4a327e | 533 | assert_reverse_iterators(const char*, int) const; |
36fed23c | 534 | |
535 | static size_type | |
4f4a327e | 536 | recursive_count_leafs(node_const_pointer, const char*, int); |
537 | #endif | |
36fed23c | 538 | |
539 | #ifdef PB_DS_PAT_TRIE_TRACE_ | |
36fed23c | 540 | static void |
4f4a327e | 541 | trace_node(node_const_pointer, size_type); |
36fed23c | 542 | |
543 | template<typename Metadata_> | |
544 | static void | |
4f4a327e | 545 | trace_node_metadata(node_const_pointer, type_to_type<Metadata_>); |
36fed23c | 546 | |
547 | static void | |
4f4a327e | 548 | trace_node_metadata(node_const_pointer, type_to_type<null_type>); |
549 | #endif | |
36fed23c | 550 | |
551 | leaf_pointer | |
4f4a327e | 552 | split_prep(key_const_reference, PB_DS_CLASS_C_DEC&, branch_bag&); |
36fed23c | 553 | |
554 | node_pointer | |
4f4a327e | 555 | rec_split(node_pointer, a_const_iterator, a_const_iterator, |
556 | PB_DS_CLASS_C_DEC&, branch_bag&); | |
36fed23c | 557 | |
558 | void | |
4f4a327e | 559 | split_insert_branch(size_type, a_const_iterator, inode_iterator, |
560 | size_type, branch_bag&); | |
36fed23c | 561 | |
4f4a327e | 562 | static head_allocator s_head_allocator; |
563 | static inode_allocator s_inode_allocator; | |
564 | static leaf_allocator s_leaf_allocator; | |
36fed23c | 565 | |
4f4a327e | 566 | head_pointer m_p_head; |
567 | size_type m_size; | |
36fed23c | 568 | }; |
569 | ||
4f4a327e | 570 | #define PB_DS_ASSERT_NODE_VALID(X) \ |
2548203e | 571 | _GLIBCXX_DEBUG_ONLY(X->assert_valid(this, __FILE__, __LINE__);) |
572 | ||
4f4a327e | 573 | #define PB_DS_RECURSIVE_COUNT_LEAFS(X) \ |
2548203e | 574 | recursive_count_leafs(X, __FILE__, __LINE__) |
575 | ||
36fed23c | 576 | #include <ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp> |
577 | #include <ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp> | |
578 | #include <ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp> | |
579 | #include <ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp> | |
580 | #include <ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp> | |
581 | #include <ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp> | |
582 | #include <ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp> | |
583 | #include <ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp> | |
584 | #include <ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp> | |
585 | #include <ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp> | |
586 | #include <ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp> | |
587 | ||
2548203e | 588 | #undef PB_DS_RECURSIVE_COUNT_LEAFS |
589 | #undef PB_DS_ASSERT_NODE_VALID | |
36fed23c | 590 | #undef PB_DS_CLASS_C_DEC |
36fed23c | 591 | #undef PB_DS_CLASS_T_DEC |
4f4a327e | 592 | #undef PB_DS_PAT_TRIE_NAME |
593 | #undef PB_DS_PAT_TRIE_TRAITS_BASE | |
6c9bd031 | 594 | #undef PB_DS_DEBUG_MAP_BASE_C_DEC |
36fed23c | 595 | } // namespace detail |
b34535d7 | 596 | } // namespace __gnu_pbds |