1 // -*- C++ -*- 2 3 // Copyright (C) 2005-2022 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_/pat_trie_.hpp 38 * Contains an implementation class for a patricia tree. 39 */ 40 41 #include <iterator> 42 #include <utility> 43 #include <algorithm> 44 #include <functional> 45 #include <assert.h> 46 #include <list> 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> 56 #ifdef _GLIBCXX_DEBUG 57 #include <ext/pb_ds/detail/debug_map_base.hpp> 58 #endif 59 #include <debug/debug.h> 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<typename Key, typename Mapped, typename Node_And_It_Traits, \ 75 typename _Alloc> 76 77 #define PB_DS_CLASS_C_DEC \ 78 PB_DS_PAT_TRIE_NAME<Key, Mapped, Node_And_It_Traits, _Alloc> 79 80 #define PB_DS_PAT_TRIE_TRAITS_BASE \ 81 types_traits<Key, Mapped, _Alloc, false> 82 83 #ifdef _GLIBCXX_DEBUG 84 #define PB_DS_DEBUG_MAP_BASE_C_DEC \ 85 debug_map_base<Key, eq_by_less<Key, std::less<Key> >, \ 86 typename rebind_traits<_Alloc, Key>::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<typename Key, typename Mapped, typename Node_And_It_Traits, 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 rebind_traits<_Alloc, node> __rebind_n; 120 typedef typename __rebind_n::const_pointer node_const_pointer; 121 typedef typename __rebind_n::pointer node_pointer; 122 123 typedef typename traits_type::head head; 124 typedef rebind_traits<_Alloc, head> __rebind_h; 125 typedef typename __rebind_h::allocator_type head_allocator; 126 typedef typename __rebind_h::pointer head_pointer; 127 128 typedef typename traits_type::leaf leaf; 129 typedef rebind_traits<_Alloc, leaf> __rebind_l; 130 typedef typename __rebind_l::allocator_type leaf_allocator; 131 typedef typename __rebind_l::pointer leaf_pointer; 132 typedef typename __rebind_l::const_pointer leaf_const_pointer; 133 134 typedef typename traits_type::inode inode; 135 typedef typename inode::iterator inode_iterator; 136 typedef rebind_traits<_Alloc, inode> __rebind_in; 137 typedef typename __rebind_in::allocator_type inode_allocator; 138 typedef typename __rebind_in::pointer inode_pointer; 139 typedef typename __rebind_in::const_pointer inode_const_pointer; 140 141 142 /// Conditional deallocator. 143 class cond_dealtor 144 { 145 protected: 146 leaf_pointer m_p_nd; 147 bool m_no_action_dtor; 148 bool m_call_destructor; 149 150 public: cond_dealtor(leaf_pointer p_nd)151 cond_dealtor(leaf_pointer p_nd) 152 : m_p_nd(p_nd), m_no_action_dtor(false), m_call_destructor(false) 153 { } 154 155 void set_no_action_dtor()156 set_no_action_dtor() 157 { m_no_action_dtor = true; } 158 159 void set_call_destructor()160 set_call_destructor() 161 { m_call_destructor = true; } 162 ~cond_dealtor()163 ~cond_dealtor() 164 { 165 if (m_no_action_dtor) 166 return; 167 168 if (m_call_destructor) 169 m_p_nd->~leaf(); 170 171 s_leaf_allocator.deallocate(m_p_nd, 1); 172 } 173 }; 174 175 176 /// Branch bag, for split-join. 177 class branch_bag 178 { 179 private: 180 typedef inode_pointer __inp; 181 typedef typename rebind_traits<_Alloc, __inp>::allocator_type 182 __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 add_branch()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 get_branch()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 ~branch_bag()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 _GLIBCXX_NODISCARD inline bool empty() const227 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 _GLIBCXX_NODISCARD 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<point_iterator, bool> 304 insert(const_reference); 305 306 inline mapped_reference operator [](key_const_reference r_key)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<typename Pred> 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<typename It> 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<typename Node_Update_> 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<typename Metadata_> 544 static void 545 trace_node_metadata(node_const_pointer, type_to_type<Metadata_>); 546 547 static void 548 trace_node_metadata(node_const_pointer, type_to_type<null_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 <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 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 597