libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp

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