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 list_update_map_/lu_map_.hpp
  38.  * Contains a list update map.
  39.  */
  40.  
  41. #include <utility>
  42. #include <iterator>
  43. #include <ext/pb_ds/detail/cond_dealtor.hpp>
  44. #include <ext/pb_ds/tag_and_trait.hpp>
  45. #include <ext/pb_ds/detail/types_traits.hpp>
  46. #include <ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp>
  47. #include <ext/pb_ds/exception.hpp>
  48. #ifdef _GLIBCXX_DEBUG
  49. #include <ext/pb_ds/detail/debug_map_base.hpp>
  50. #endif
  51. #ifdef PB_DS_LU_MAP_TRACE_
  52. #include <iostream>
  53. #endif
  54. #include <debug/debug.h>
  55.  
  56. namespace __gnu_pbds
  57. {
  58.   namespace detail
  59.   {
  60. #ifdef PB_DS_DATA_TRUE_INDICATOR
  61. #define PB_DS_LU_NAME lu_map
  62. #endif
  63.  
  64. #ifdef PB_DS_DATA_FALSE_INDICATOR
  65. #define PB_DS_LU_NAME lu_set
  66. #endif
  67.  
  68. #define PB_DS_CLASS_T_DEC \
  69.     template<typename Key, typename Mapped, typename Eq_Fn, \
  70.              typename _Alloc, typename Update_Policy>
  71.  
  72. #define PB_DS_CLASS_C_DEC \
  73.     PB_DS_LU_NAME<Key, Mapped, Eq_Fn, _Alloc, Update_Policy>
  74.  
  75. #define PB_DS_LU_TRAITS_BASE \
  76.     types_traits<Key, Mapped, _Alloc, false>
  77.  
  78. #ifdef _GLIBCXX_DEBUG
  79. #define PB_DS_DEBUG_MAP_BASE_C_DEC \
  80.     debug_map_base<Key, Eq_Fn, \
  81.               typename _Alloc::template rebind<Key>::other::const_reference>
  82. #endif
  83.  
  84.     /// list-based (with updates) associative container.
  85.     /// Skip to the lu, my darling.
  86.     template<typename Key,
  87.              typename Mapped,
  88.              typename Eq_Fn,
  89.              typename _Alloc,
  90.              typename Update_Policy>
  91.     class PB_DS_LU_NAME :
  92. #ifdef _GLIBCXX_DEBUG
  93.       protected PB_DS_DEBUG_MAP_BASE_C_DEC,
  94. #endif
  95.       public PB_DS_LU_TRAITS_BASE
  96.     {
  97.     private:
  98.       typedef PB_DS_LU_TRAITS_BASE              traits_base;
  99.  
  100.       struct entry
  101.      : public lu_map_entry_metadata_base<typename Update_Policy::metadata_type>
  102.       {
  103.         typename traits_base::value_type m_value;
  104.         typename _Alloc::template rebind<entry>::other::pointer m_p_next;
  105.       };
  106.  
  107.       typedef typename _Alloc::template rebind<entry>::other entry_allocator;
  108.       typedef typename entry_allocator::pointer entry_pointer;
  109.       typedef typename entry_allocator::const_pointer const_entry_pointer;
  110.       typedef typename entry_allocator::reference entry_reference;
  111.       typedef typename entry_allocator::const_reference const_entry_reference;
  112.  
  113.       typedef typename _Alloc::template rebind<entry_pointer>::other entry_pointer_allocator;
  114.       typedef typename entry_pointer_allocator::pointer entry_pointer_array;
  115.  
  116.       typedef typename traits_base::value_type value_type_;
  117.       typedef typename traits_base::pointer pointer_;
  118.       typedef typename traits_base::const_pointer const_pointer_;
  119.       typedef typename traits_base::reference reference_;
  120.       typedef typename traits_base::const_reference const_reference_;
  121.  
  122. #define PB_DS_GEN_POS entry_pointer
  123.  
  124. #include <ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp>
  125. #include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp>
  126. #include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp>
  127. #include <ext/pb_ds/detail/unordered_iterator/iterator.hpp>
  128.  
  129. #undef PB_DS_GEN_POS
  130.  
  131.  
  132. #ifdef _GLIBCXX_DEBUG
  133.       typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
  134. #endif
  135.  
  136.       typedef cond_dealtor<entry, _Alloc> cond_dealtor_t;
  137.  
  138.     public:
  139.       typedef _Alloc allocator_type;
  140.       typedef typename _Alloc::size_type size_type;
  141.       typedef typename _Alloc::difference_type difference_type;
  142.       typedef Eq_Fn eq_fn;
  143.       typedef Update_Policy update_policy;
  144.       typedef typename Update_Policy::metadata_type update_metadata;
  145.       typedef typename traits_base::key_type key_type;
  146.       typedef typename traits_base::key_pointer key_pointer;
  147.       typedef typename traits_base::key_const_pointer key_const_pointer;
  148.       typedef typename traits_base::key_reference key_reference;
  149.       typedef typename traits_base::key_const_reference key_const_reference;
  150.       typedef typename traits_base::mapped_type mapped_type;
  151.       typedef typename traits_base::mapped_pointer mapped_pointer;
  152.       typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
  153.       typedef typename traits_base::mapped_reference mapped_reference;
  154.       typedef typename traits_base::mapped_const_reference mapped_const_reference;
  155.       typedef typename traits_base::value_type value_type;
  156.       typedef typename traits_base::pointer pointer;
  157.       typedef typename traits_base::const_pointer const_pointer;
  158.       typedef typename traits_base::reference reference;
  159.       typedef typename traits_base::const_reference const_reference;
  160.  
  161. #ifdef PB_DS_DATA_TRUE_INDICATOR
  162.       typedef point_iterator_                   point_iterator;
  163. #endif
  164.  
  165. #ifdef PB_DS_DATA_FALSE_INDICATOR
  166.       typedef point_const_iterator_             point_iterator;
  167. #endif
  168.  
  169.       typedef point_const_iterator_             point_const_iterator;
  170.  
  171. #ifdef PB_DS_DATA_TRUE_INDICATOR
  172.       typedef iterator_                         iterator;
  173. #endif
  174.  
  175. #ifdef PB_DS_DATA_FALSE_INDICATOR
  176.       typedef const_iterator_                   iterator;
  177. #endif
  178.  
  179.       typedef const_iterator_                   const_iterator;
  180.  
  181.     public:
  182.       PB_DS_LU_NAME();
  183.  
  184.       PB_DS_LU_NAME(const PB_DS_CLASS_C_DEC&);
  185.  
  186.       virtual
  187.       ~PB_DS_LU_NAME();
  188.  
  189.       template<typename It>
  190.       PB_DS_LU_NAME(It, It);
  191.  
  192.       void
  193.       swap(PB_DS_CLASS_C_DEC&);
  194.  
  195.       inline size_type
  196.       size() const;
  197.  
  198.       inline size_type
  199.       max_size() const;
  200.  
  201.       inline bool
  202.       empty() const;
  203.  
  204.       inline mapped_reference
  205.       operator[](key_const_reference r_key)
  206.       {
  207. #ifdef PB_DS_DATA_TRUE_INDICATOR
  208.         _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
  209.         return insert(std::make_pair(r_key, mapped_type())).first->second;
  210. #else
  211.         insert(r_key);
  212.         return traits_base::s_null_type;
  213. #endif
  214.       }
  215.  
  216.       inline std::pair<point_iterator, bool>
  217.       insert(const_reference);
  218.  
  219.       inline point_iterator
  220.       find(key_const_reference r_key)
  221.       {
  222.         _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
  223.         entry_pointer p_e = find_imp(r_key);
  224.         return point_iterator(p_e == 0 ? 0: &p_e->m_value);
  225.       }
  226.  
  227.       inline point_const_iterator
  228.       find(key_const_reference r_key) const
  229.       {
  230.         _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
  231.         entry_pointer p_e = find_imp(r_key);
  232.         return point_const_iterator(p_e == 0 ? 0: &p_e->m_value);
  233.       }
  234.  
  235.       inline bool
  236.       erase(key_const_reference);
  237.  
  238.       template<typename Pred>
  239.       inline size_type
  240.       erase_if(Pred);
  241.  
  242.       void
  243.       clear();
  244.  
  245.       inline iterator
  246.       begin();
  247.  
  248.       inline const_iterator
  249.       begin() const;
  250.  
  251.       inline iterator
  252.       end();
  253.  
  254.       inline const_iterator
  255.       end() const;
  256.  
  257. #ifdef _GLIBCXX_DEBUG
  258.       void
  259.       assert_valid(const char* file, int line) const;
  260. #endif
  261.  
  262. #ifdef PB_DS_LU_MAP_TRACE_
  263.       void
  264.       trace() const;
  265. #endif
  266.  
  267.     protected:
  268.  
  269.       template<typename It>
  270.       void
  271.       copy_from_range(It, It);
  272.  
  273.     private:
  274. #ifdef PB_DS_DATA_TRUE_INDICATOR
  275.       friend class iterator_;
  276. #endif
  277.  
  278.       friend class const_iterator_;
  279.  
  280.       inline entry_pointer
  281.       allocate_new_entry(const_reference, false_type);
  282.  
  283.       inline entry_pointer
  284.       allocate_new_entry(const_reference, true_type);
  285.  
  286.       template<typename Metadata>
  287.       inline static void
  288.       init_entry_metadata(entry_pointer, type_to_type<Metadata>);
  289.  
  290.       inline static void
  291.       init_entry_metadata(entry_pointer, type_to_type<null_type>);
  292.  
  293.       void
  294.       deallocate_all();
  295.  
  296.       void
  297.       erase_next(entry_pointer);
  298.  
  299.       void
  300.       actual_erase_entry(entry_pointer);
  301.  
  302.       void
  303.       inc_it_state(const_pointer& r_p_value, entry_pointer& r_pos) const
  304.       {
  305.         r_pos = r_pos->m_p_next;
  306.         r_p_value = (r_pos == 0) ? 0 : &r_pos->m_value;
  307.       }
  308.  
  309.       template<typename Metadata>
  310.       inline static bool
  311.       apply_update(entry_pointer, type_to_type<Metadata>);
  312.  
  313.       inline static bool
  314.       apply_update(entry_pointer, type_to_type<null_type>);
  315.  
  316.       inline entry_pointer
  317.       find_imp(key_const_reference) const;
  318.  
  319.       static entry_allocator                    s_entry_allocator;
  320.       static Eq_Fn                              s_eq_fn;
  321.       static Update_Policy                      s_update_policy;
  322.       static type_to_type<update_metadata>      s_metadata_type_indicator;
  323.       static null_type                          s_null_type;
  324.  
  325.       mutable entry_pointer                     m_p_l;
  326.     };
  327.  
  328. #include <ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp>
  329. #include <ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp>
  330. #include <ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp>
  331. #include <ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp>
  332. #include <ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp>
  333. #include <ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp>
  334. #include <ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp>
  335. #include <ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp>
  336.  
  337. #undef PB_DS_CLASS_T_DEC
  338. #undef PB_DS_CLASS_C_DEC
  339. #undef PB_DS_LU_TRAITS_BASE
  340. #undef PB_DS_DEBUG_MAP_BASE_C_DEC
  341. #undef PB_DS_LU_NAME
  342.   } // namespace detail
  343. } // namespace __gnu_pbds
  344.