libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp

   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 // <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 _Alloc::template rebind<Key>::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<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 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         { }
 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<point_iterator, bool>
 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<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