contrib/libstdc++/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file lu_map_.hpp
  44  * Contains a list update map.
  45  */
  46
  47 #include <utility>
  48 #include <iterator>
  49 #include <ext/pb_ds/detail/cond_dealtor.hpp>
  50 #include <ext/pb_ds/tag_and_trait.hpp>
  51 #include <ext/pb_ds/detail/types_traits.hpp>
  52 #include <ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp>
  53 #include <ext/pb_ds/exception.hpp>
  54 #ifdef _GLIBCXX_DEBUG
  55 #include <ext/pb_ds/detail/map_debug_base.hpp>
  56 #endif
  57 #ifdef PB_DS_LU_MAP_TRACE_
  58 #include <iostream>
  59 #endif
  60 #include <debug/debug.h>
  61
  62 namespace pb_ds
  63 {
  64   namespace detail
  65   {
  66 #define PB_DS_CLASS_T_DEC \
  67     template<typename Key, typename Mapped, class Eq_Fn, \
  68              class Allocator, class Update_Policy>
  69
  70 #ifdef PB_DS_DATA_TRUE_INDICATOR
  71 #define PB_DS_CLASS_NAME lu_map_data_
  72 #endif
  73
  74 #ifdef PB_DS_DATA_FALSE_INDICATOR
  75 #define PB_DS_CLASS_NAME lu_map_no_data_
  76 #endif
  77
  78 #define PB_DS_CLASS_C_DEC \
  79     PB_DS_CLASS_NAME<Key, Mapped, Eq_Fn, Allocator, Update_Policy>
  80
  81 #define PB_DS_TYPES_TRAITS_C_DEC \
  82     types_traits<Key, Mapped, Allocator, false>
  83
  84 #ifdef _GLIBCXX_DEBUG
  85 #define PB_DS_MAP_DEBUG_BASE_C_DEC \
  86     map_debug_base<Key, Eq_Fn, \
  87               typename Allocator::template rebind<Key>::other::const_reference>
  88 #endif
  89
  90 #ifdef PB_DS_DATA_TRUE_INDICATOR
  91 #define PB_DS_V2F(X) (X).first
  92 #define PB_DS_V2S(X) (X).second
  93 #define PB_DS_EP2VP(X)& ((X)->m_value)
  94 #endif
  95
  96 #ifdef PB_DS_DATA_FALSE_INDICATOR
  97 #define PB_DS_V2F(X) (X)
  98 #define PB_DS_V2S(X) Mapped_Data()
  99 #define PB_DS_EP2VP(X)& ((X)->m_value.first)
 100 #endif
 101
 102     /* Skip to the lu, my darling. */
 103     // list-based (with updates) associative container.
 104     template<typename Key,
 105              typename Mapped,
 106              class Eq_Fn,
 107              class Allocator,
 108              class Update_Policy>
 109     class PB_DS_CLASS_NAME :
 110 #ifdef _GLIBCXX_DEBUG
 111       protected PB_DS_MAP_DEBUG_BASE_C_DEC,
 112 #endif
 113       public PB_DS_TYPES_TRAITS_C_DEC
 114     {
 115     private:
 116       typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
 117
 118       struct entry
 119      : public lu_map_entry_metadata_base<typename Update_Policy::metadata_type>
 120       {
 121         typename traits_base::value_type m_value;
 122         typename Allocator::template rebind<entry>::other::pointer m_p_next;
 123       };
 124
 125       typedef typename Allocator::template rebind<entry>::other entry_allocator;
 126       typedef typename entry_allocator::pointer entry_pointer;
 127       typedef typename entry_allocator::const_pointer const_entry_pointer;
 128       typedef typename entry_allocator::reference entry_reference;
 129       typedef typename entry_allocator::const_reference const_entry_reference;
 130
 131       typedef typename Allocator::template rebind<entry_pointer>::other entry_pointer_allocator;
 132       typedef typename entry_pointer_allocator::pointer entry_pointer_array;
 133
 134       typedef typename traits_base::value_type value_type_;
 135       typedef typename traits_base::pointer pointer_;
 136       typedef typename traits_base::const_pointer const_pointer_;
 137       typedef typename traits_base::reference reference_;
 138       typedef typename traits_base::const_reference const_reference_;
 139
 140 #define PB_DS_GEN_POS entry_pointer
 141
 142 #include <ext/pb_ds/detail/unordered_iterator/const_point_iterator.hpp>
 143 #include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp>
 144 #include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp>
 145 #include <ext/pb_ds/detail/unordered_iterator/iterator.hpp>
 146
 147 #undef PB_DS_GEN_POS
 148
 149
 150 #ifdef _GLIBCXX_DEBUG
 151       typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base;
 152 #endif
 153
 154       typedef cond_dealtor<entry, Allocator> cond_dealtor_t;
 155
 156     public:
 157       typedef Allocator allocator;
 158       typedef typename Allocator::size_type size_type;
 159       typedef typename Allocator::difference_type difference_type;
 160       typedef Eq_Fn eq_fn;
 161       typedef Update_Policy update_policy;
 162       typedef typename Update_Policy::metadata_type update_metadata;
 163       typedef typename traits_base::key_type key_type;
 164       typedef typename traits_base::key_pointer key_pointer;
 165       typedef typename traits_base::const_key_pointer const_key_pointer;
 166       typedef typename traits_base::key_reference key_reference;
 167       typedef typename traits_base::const_key_reference const_key_reference;
 168       typedef typename traits_base::mapped_type mapped_type;
 169       typedef typename traits_base::mapped_pointer mapped_pointer;
 170       typedef typename traits_base::const_mapped_pointer const_mapped_pointer;
 171       typedef typename traits_base::mapped_reference mapped_reference;
 172       typedef typename traits_base::const_mapped_reference const_mapped_reference;
 173       typedef typename traits_base::value_type value_type;
 174       typedef typename traits_base::pointer pointer;
 175       typedef typename traits_base::const_pointer const_pointer;
 176       typedef typename traits_base::reference reference;
 177       typedef typename traits_base::const_reference const_reference;
 178
 179 #ifdef PB_DS_DATA_TRUE_INDICATOR
 180       typedef point_iterator_ point_iterator;
 181 #endif
 182
 183 #ifdef PB_DS_DATA_FALSE_INDICATOR
 184       typedef const_point_iterator_ point_iterator;
 185 #endif
 186
 187       typedef const_point_iterator_ const_point_iterator;
 188
 189 #ifdef PB_DS_DATA_TRUE_INDICATOR
 190       typedef iterator_ iterator;
 191 #endif
 192
 193 #ifdef PB_DS_DATA_FALSE_INDICATOR
 194       typedef const_iterator_ iterator;
 195 #endif
 196
 197       typedef const_iterator_ const_iterator;
 198
 199     public:
 200       PB_DS_CLASS_NAME();
 201
 202       PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&);
 203
 204       virtual
 205       ~PB_DS_CLASS_NAME();
 206
 207       template<typename It>
 208       PB_DS_CLASS_NAME(It first_it, It last_it);
 209
 210       void
 211       swap(PB_DS_CLASS_C_DEC&);
 212
 213       inline size_type
 214       size() const;
 215
 216       inline size_type
 217       max_size() const;
 218
 219       inline bool
 220       empty() const;
 221
 222       inline mapped_reference
 223       operator[](const_key_reference r_key)
 224       {
 225 #ifdef PB_DS_DATA_TRUE_INDICATOR
 226         _GLIBCXX_DEBUG_ONLY(assert_valid();)
 227         return insert(std::make_pair(r_key, mapped_type())).first->second;
 228 #else
 229         insert(r_key);
 230         return traits_base::s_null_mapped;
 231 #endif
 232       }
 233
 234       inline std::pair<point_iterator, bool>
 235       insert(const_reference);
 236
 237       inline point_iterator
 238       find(const_key_reference r_key)
 239       {
 240         _GLIBCXX_DEBUG_ONLY(assert_valid();)
 241         entry_pointer p_e = find_imp(r_key);
 242         return point_iterator(p_e == NULL ? NULL: &p_e->m_value);
 243       }
 244
 245       inline const_point_iterator
 246       find(const_key_reference r_key) const
 247       {
 248         _GLIBCXX_DEBUG_ONLY(assert_valid();)
 249         entry_pointer p_e = find_imp(r_key);
 250         return const_point_iterator(p_e == NULL ? NULL: &p_e->m_value);
 251       }
 252
 253       inline bool
 254       erase(const_key_reference);
 255
 256       template<typename Pred>
 257       inline size_type
 258       erase_if(Pred);
 259
 260       void
 261       clear();
 262
 263       inline iterator
 264       begin();
 265
 266       inline const_iterator
 267       begin() const;
 268
 269       inline iterator
 270       end();
 271
 272       inline const_iterator
 273       end() const;
 274
 275 #ifdef _GLIBCXX_DEBUG
 276       void
 277       assert_valid() const;
 278 #endif
 279
 280 #ifdef PB_DS_LU_MAP_TRACE_
 281       void
 282       trace() const;
 283 #endif
 284
 285     protected:
 286
 287       template<typename It>
 288       void
 289       copy_from_range(It, It);
 290
 291     private:
 292 #ifdef PB_DS_DATA_TRUE_INDICATOR
 293       friend class iterator_;
 294 #endif
 295
 296       friend class const_iterator_;
 297
 298       inline entry_pointer
 299       allocate_new_entry(const_reference, false_type);
 300
 301       inline entry_pointer
 302       allocate_new_entry(const_reference, true_type);
 303
 304       template<typename Metadata>
 305       inline static void
 306       init_entry_metadata(entry_pointer, type_to_type<Metadata>);
 307
 308       inline static void
 309       init_entry_metadata(entry_pointer, type_to_type<null_lu_metadata>);
 310
 311       void
 312       deallocate_all();
 313
 314       void
 315       erase_next(entry_pointer);
 316
 317       void
 318       actual_erase_entry(entry_pointer);
 319
 320       void
 321       inc_it_state(const_pointer& r_p_value, entry_pointer& r_pos) const
 322       {
 323         r_pos = r_pos->m_p_next;
 324         r_p_value = (r_pos == NULL) ? NULL : &r_pos->m_value;
 325       }
 326
 327       template<typename Metadata>
 328       inline static bool
 329       apply_update(entry_pointer, type_to_type<Metadata>);
 330
 331       inline static bool
 332       apply_update(entry_pointer, type_to_type<null_lu_metadata>);
 333
 334       inline entry_pointer
 335       find_imp(const_key_reference) const;
 336
 337       static entry_allocator s_entry_allocator;
 338       static Eq_Fn s_eq_fn;
 339       static Update_Policy s_update_policy;
 340       static type_to_type<update_metadata> s_metadata_type_indicator;
 341       static null_lu_metadata s_null_lu_metadata;
 342
 343       mutable entry_pointer m_p_l;
 344     };
 345
 346 #include <ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp>
 347 #include <ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp>
 348 #include <ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp>
 349 #include <ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp>
 350 #include <ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp>
 351 #include <ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp>
 352 #include <ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp>
 353 #include <ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp>
 354
 355 #undef PB_DS_CLASS_T_DEC
 356 #undef PB_DS_CLASS_C_DEC
 357 #undef  PB_DS_TYPES_TRAITS_C_DEC
 358 #undef PB_DS_MAP_DEBUG_BASE_C_DEC
 359 #undef PB_DS_CLASS_NAME
 360 #undef PB_DS_V2F
 361 #undef PB_DS_EP2VP
 362 #undef PB_DS_V2S
 363
 364   } // namespace detail
 365 } // namespace pb_ds