libstdc++-v3/include/ext/pb_assoc/detail/lu_map_/lu_map_.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005 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
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  31
  32 // Permission to use, copy, modify, sell, and distribute this software
  33 // is hereby granted without fee, provided that the above copyright
  34 // notice appears in all copies, and that both that copyright notice and
  35 // this permission notice appear in supporting documentation. None of
  36 // the above authors, nor IBM Haifa Research Laboratories, make any
  37 // representation about the suitability of this software for any
  38 // purpose. It is provided "as is" without express or implied warranty.
  39
  40 /**
  41  * @file lu_map_.hpp
  42  * Contains a list update map.
  43  */
  44
  45 #include <utility>
  46 #include <iterator>
  47 #include <ext/pb_assoc/detail/cond_dealtor.hpp>
  48 #include <ext/pb_assoc/trivial_iterator_def.hpp>
  49 #include <ext/pb_assoc/detail/types_traits.hpp>
  50 #include <ext/pb_assoc/exception.hpp>
  51 #include <ext/pb_assoc/detail/map_debug_base.hpp>
  52
  53 namespace pb_assoc
  54 {
  55
  56   namespace detail
  57   {
  58
  59 #ifdef PB_ASSOC_LU_MAP_DEBUG_
  60 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
  61 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
  62 #define PB_ASSOC_DBG_ONLY(X) X
  63 #else // #ifdef PB_ASSOC_LU_MAP_DEBUG_
  64 #define PB_ASSOC_DBG_ASSERT(X)
  65 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
  66 #define PB_ASSOC_DBG_ONLY(X) ;
  67 #endif // #ifdef PB_ASSOC_LU_MAP_DEBUG_
  68
  69 #define PB_ASSOC_CLASS_T_DEC \
  70         template< \
  71                 typename Key, \
  72                 typename Data, \
  73                 class Eq_Fn, \
  74                 class Allocator, \
  75                 class Update_Policy>
  76
  77 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
  78 #define PB_ASSOC_CLASS_NAME \
  79         lu_map_data_
  80 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
  81
  82 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
  83 #define PB_ASSOC_CLASS_NAME \
  84         lu_map_no_data_
  85 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
  86
  87 #define PB_ASSOC_CLASS_C_DEC \
  88         PB_ASSOC_CLASS_NAME< \
  89                 Key, \
  90                 Data, \
  91                 Eq_Fn, \
  92                 Allocator, \
  93                 Update_Policy>
  94
  95 #define PB_ASSOC_TYPES_TRAITS_C_DEC \
  96         pb_assoc::detail::types_traits< \
  97                 Key, \
  98                 Data, \
  99                 Allocator>
 100
 101 #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
 102 #define PB_ASSOC_MAP_DEBUG_BASE_C_DEC \
 103         pb_assoc::detail::map_debug_base< \
 104                 Key, \
 105                 Eq_Fn>
 106 #endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
 107
 108 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 109 #define PB_ASSOC_V2F(X) (X).first
 110 #define PB_ASSOC_V2S(X) (X).second
 111 #define PB_ASSOC_EP2VP(X)& ((X)->m_value)
 112 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 113
 114 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
 115 #define PB_ASSOC_V2F(X) (X)
 116 #define PB_ASSOC_V2S(X) Data()
 117 #define PB_ASSOC_EP2VP(X)& ((X)->m_value.first)
 118 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
 119
 120 #ifdef PB_ASSOC_LU_MAP_DEBUG_
 121 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
 122 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
 123 #define PB_ASSOC_DBG_ONLY(X) X
 124 #else // #ifdef PB_ASSOC_LU_MAP_DEBUG_
 125 #define PB_ASSOC_DBG_ASSERT(X)
 126 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
 127 #define PB_ASSOC_DBG_ONLY(X) ;
 128 #endif // #ifdef PB_ASSOC_LU_MAP_DEBUG_
 129
 130     /* Skip to the lu, my darling. */
 131
 132     template<typename Key,
 133              typename Data,
 134              class Eq_Fn,
 135              class Allocator,
 136              class Update_Policy>
 137     class PB_ASSOC_CLASS_NAME :
 138 #ifdef PB_ASSOC_LU_MAP_DEBUG_
 139       protected PB_ASSOC_MAP_DEBUG_BASE_C_DEC,
 140 #endif // #ifdef PB_ASSOC_LU_MAP_DEBUG_
 141       public Eq_Fn,
 142       public Update_Policy,
 143       public PB_ASSOC_TYPES_TRAITS_C_DEC
 144     {
 145
 146     protected:
 147
 148       typedef typename Allocator::size_type size_type;
 149
 150       typedef
 151       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_key_reference
 152       const_key_reference;
 153
 154 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 155
 156       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_type data_type;
 157
 158       typedef
 159       typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_reference
 160       data_reference;
 161
 162       typedef
 163       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_data_reference
 164       const_data_reference;
 165
 166 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 167
 168       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type value_type;
 169
 170       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::pointer pointer;
 171
 172       typedef
 173       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_pointer
 174       const_pointer;
 175
 176       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::reference reference;
 177
 178       typedef
 179       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_reference
 180       const_reference;
 181
 182       typedef Update_Policy update_policy;
 183
 184       typedef typename Update_Policy::metadata_type update_metadata;
 185
 186       struct entry
 187       {
 188         typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type m_value;
 189
 190         update_metadata m_update_metadata;
 191
 192         typename Allocator::template rebind<entry>::other::pointer m_p_next;
 193       };
 194
 195       typedef
 196       typename Allocator::template rebind<entry>::other
 197       entry_allocator;
 198
 199       typedef typename entry_allocator::pointer entry_pointer;
 200
 201       typedef typename entry_allocator::const_pointer const_entry_pointer;
 202
 203       typedef typename entry_allocator::reference entry_reference;
 204
 205       typedef
 206       typename entry_allocator::const_reference
 207       const_entry_reference;
 208
 209       typedef
 210       typename Allocator::template rebind<entry_pointer>::other
 211       entry_pointer_allocator;
 212
 213       typedef typename entry_pointer_allocator::pointer entry_pointer_array;
 214
 215 #define PB_ASSOC_GEN_POS entry_pointer
 216
 217       typedef value_type mapped_value_type;
 218
 219       typedef pointer mapped_pointer;
 220
 221       typedef const_pointer const_mapped_pointer;
 222
 223       typedef reference mapped_reference;
 224
 225       typedef const_reference const_mapped_reference;
 226
 227 #include <ext/pb_assoc/detail/unordered_iterator/const_find_iterator.hpp>
 228 #include <ext/pb_assoc/detail/unordered_iterator/find_iterator.hpp>
 229 #include <ext/pb_assoc/detail/unordered_iterator/const_iterator.hpp>
 230 #include <ext/pb_assoc/detail/unordered_iterator/iterator.hpp>
 231
 232 #undef PB_ASSOC_GEN_POS
 233
 234       typedef find_iterator_ find_iterator;
 235
 236       typedef const_find_iterator_ const_find_iterator;
 237
 238       typedef iterator_ iterator;
 239
 240       typedef const_iterator_ const_iterator;
 241
 242       typedef Eq_Fn eq_fn;
 243
 244       typedef Allocator allocator;
 245
 246     protected:
 247
 248       PB_ASSOC_CLASS_NAME();
 249
 250       PB_ASSOC_CLASS_NAME(const Eq_Fn& r_eq_fn);
 251
 252       PB_ASSOC_CLASS_NAME(const Eq_Fn& r_eq_fn, const Update_Policy& r_update_policy);
 253
 254       PB_ASSOC_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other);
 255
 256       virtual
 257       ~PB_ASSOC_CLASS_NAME();
 258
 259       void
 260       swap(PB_ASSOC_CLASS_C_DEC& r_other);
 261
 262       template<class It>
 263       void
 264       copy_from_range(It first_it, It last_it);
 265
 266       inline size_type
 267       size() const;
 268
 269       inline size_type
 270       max_size() const;
 271
 272       inline bool
 273       empty() const;
 274
 275       Eq_Fn&
 276       get_eq_fn();
 277
 278       const Eq_Fn&
 279       get_eq_fn() const;
 280
 281       inline std::pair<find_iterator, bool>
 282       insert(const_reference r_val);
 283
 284 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 285       inline data_reference
 286       subscript_imp(const_key_reference r_key);
 287 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 288
 289       inline find_iterator
 290       find(const_key_reference r_key);
 291
 292       inline const_find_iterator
 293       find(const_key_reference r_key) const;
 294
 295 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 296       inline const_data_reference
 297       const_subscript_imp(const_key_reference r_key) const;
 298 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 299
 300       inline size_type
 301       erase(const_key_reference r_key);
 302
 303       template<class Pred>
 304       inline size_type
 305       erase_if(Pred& r_pred);
 306
 307       void
 308       clear();
 309
 310       inline iterator
 311       begin();
 312
 313       inline const_iterator
 314       begin() const;
 315
 316       inline iterator
 317       end();
 318
 319       inline const_iterator
 320       end() const;
 321
 322 #ifdef PB_ASSOC_LU_MAP_DEBUG_
 323
 324       virtual void
 325       assert_valid() const;
 326
 327 #endif // #ifdef PB_ASSOC_LU_MAP_DEBUG_
 328
 329     private:
 330
 331       typedef PB_ASSOC_TYPES_TRAITS_C_DEC my_traits_base;
 332
 333 #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
 334       typedef PB_ASSOC_MAP_DEBUG_BASE_C_DEC my_map_debug_base;
 335 #endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
 336
 337       typedef
 338       pb_assoc::detail::cond_dealtor<
 339         entry,
 340         Allocator>
 341       cond_dealtor_t;
 342
 343     private:
 344
 345       void
 346       deallocate_all(bool deallocate_root);
 347
 348       inline void
 349       move_next_to_front(entry_pointer p_l) const;
 350
 351       void
 352       initialize();
 353
 354       inline void
 355       insert_new_after(entry_pointer p_l, const_reference r_val);
 356
 357       inline entry_pointer
 358       find_imp(const_key_reference r_key) const
 359       {
 360         entry_pointer p_l = m_p_l;
 361
 362         while (p_l->m_p_next != NULL)
 363           if (Eq_Fn::operator()(
 364                                 r_key,
 365                                 PB_ASSOC_V2F(p_l->m_p_next->m_value)))
 366             {
 367               if (Update_Policy::operator()(p_l->m_update_metadata))
 368                 {
 369                   move_next_to_front(p_l);
 370
 371                   return (m_p_l);
 372                 }
 373               else
 374                 return (p_l);
 375             }
 376           else
 377             p_l = p_l->m_p_next;
 378
 379         return (p_l);
 380       }
 381
 382       inline void
 383       erase_imp(entry_pointer p_l);
 384
 385       inline find_iterator
 386       find_end();
 387
 388       inline const_find_iterator
 389       find_end() const;
 390
 391       void
 392       inc_it_state(pointer& r_p_value, std::pair<entry_pointer, size_type>& r_pos) const;
 393
 394       void
 395       inc_it_state(const_pointer& r_p_value, entry_pointer& r_pos) const;
 396
 397       void
 398       get_start_it_state(pointer& r_p_value, std::pair<entry_pointer, size_type>& r_pos) const;
 399
 400 #ifdef PB_ASSOC_LU_MAP_DEBUG_
 401
 402       void
 403       assert_entry_pointer_array_valid(const entry_pointer_array a_p_lntries) const;
 404
 405       void
 406       assert_entry_pointer_valid(const entry_pointer p_l, store_hash_true_indicator) const;
 407
 408       void
 409       assert_entry_pointer_valid(const entry_pointer p_l, store_hash_false_indicator) const;
 410
 411 #endif // #ifdef PB_ASSOC_LU_MAP_DEBUG_
 412
 413     private:
 414
 415       static entry_allocator s_entry_allocator;
 416
 417       mutable entry_pointer m_p_l;
 418
 419       size_type m_size;
 420
 421       friend class iterator_;
 422
 423       friend class const_iterator_;
 424
 425       static iterator s_end_it;
 426
 427       static const_iterator s_const_end_it;
 428
 429       static find_iterator s_find_end_it;
 430
 431       static const_find_iterator s_const_find_end_it;
 432
 433     };
 434
 435 #include <ext/pb_assoc/detail/lu_map_/constructor_destructor_fn_imps.hpp>
 436 #include <ext/pb_assoc/detail/lu_map_/info_fn_imps.hpp>
 437 #include <ext/pb_assoc/detail/lu_map_/debug_fn_imps.hpp>
 438 #include <ext/pb_assoc/detail/lu_map_/policy_access_fn_imps.hpp>
 439 #include <ext/pb_assoc/detail/lu_map_/iterators_fn_imps.hpp>
 440 #include <ext/pb_assoc/detail/lu_map_/erase_fn_imps.hpp>
 441 #include <ext/pb_assoc/detail/lu_map_/find_fn_imps.hpp>
 442 #include <ext/pb_assoc/detail/lu_map_/insert_fn_imps.hpp>
 443
 444 #undef PB_ASSOC_CLASS_T_DEC
 445
 446 #undef PB_ASSOC_CLASS_C_DEC
 447
 448 #undef PB_ASSOC_TYPES_TRAITS_C_DEC
 449
 450 #undef PB_ASSOC_MAP_DEBUG_BASE_C_DEC
 451
 452 #undef PB_ASSOC_CLASS_NAME
 453
 454 #undef PB_ASSOC_V2F
 455 #undef PB_ASSOC_EP2VP
 456 #undef PB_ASSOC_V2S
 457
 458 #undef PB_ASSOC_DBG_ASSERT
 459 #undef PB_ASSOC_DBG_VERIFY
 460 #undef PB_ASSOC_DBG_ONLY
 461
 462   } // namespace detail
 463
 464 } // namespace pb_assoc