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

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