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