Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  1. // -*- C++ -*-
  2.  
  3. // Copyright (C) 2005-2013 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
  597.