libstdc++-v3/include/ext/pb_assoc/detail/cc_ht_map_/cc_ht_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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  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 cc_ht_map_.hpp
  42  * Contains an implementation class for cc_ht_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/hash_fn/ranged_hash_fn.hpp>
  50 #include <ext/pb_assoc/detail/hash_types_traits.hpp>
  51 #include <ext/pb_assoc/detail/types_traits.hpp>
  52 #include <ext/pb_assoc/exception.hpp>
  53 #include <ext/pb_assoc/detail/map_debug_base.hpp>
  54 #include <ext/pb_assoc/detail/eq_fn/hash_eq_fn.hpp>
  55
  56 namespace pb_assoc
  57 {
  58
  59   namespace detail
  60   {
  61
  62 #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
  63 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
  64 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
  65 #define PB_ASSOC_DBG_ONLY(X) X
  66 #else // #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
  67 #define PB_ASSOC_DBG_ASSERT(X)
  68 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
  69 #define PB_ASSOC_DBG_ONLY(X) ;
  70 #endif // #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
  71
  72 #define PB_ASSOC_CLASS_T_DEC \
  73         template< \
  74                 typename Key, \
  75                 typename Data, \
  76                 class Hash_Fn, \
  77                 class Eq_Fn, \
  78                 class Allocator, \
  79                 bool Store_Hash, \
  80                 class Comb_Hash_Fn, \
  81                 class Resize_Policy>
  82
  83 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
  84 #define PB_ASSOC_CLASS_NAME \
  85         cc_ht_map_data_
  86 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
  87
  88 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
  89 #define PB_ASSOC_CLASS_NAME \
  90         cc_ht_map_no_data_
  91 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
  92
  93 #define PB_ASSOC_CLASS_C_DEC \
  94         PB_ASSOC_CLASS_NAME< \
  95                 Key, \
  96                 Data, \
  97                 Hash_Fn, \
  98                 Eq_Fn, \
  99                 Allocator, \
 100                 Store_Hash, \
 101                 Comb_Hash_Fn, \
 102                 Resize_Policy >
 103
 104 #define PB_ASSOC_HASH_EQ_FN_C_DEC \
 105         pb_assoc::detail::hash_eq_fn< \
 106                 Key, \
 107                 Eq_Fn, \
 108                 Allocator, \
 109                 Store_Hash>
 110
 111 #define PB_ASSOC_RANGED_HASH_FN_C_DEC \
 112         pb_assoc::detail::ranged_hash_fn< \
 113                 Key, \
 114                 Hash_Fn, \
 115                 Allocator, \
 116                 Comb_Hash_Fn, \
 117                 Store_Hash>
 118
 119 #define PB_ASSOC_TYPES_TRAITS_C_DEC \
 120         types_traits< \
 121                 Key, \
 122                 Data, \
 123                 Allocator>
 124
 125 #define PB_ASSOC_HASH_TYPES_TRAITS_C_DEC \
 126         hash_types_traits< \
 127                 typename Allocator::size_type, \
 128                 Store_Hash>
 129
 130 #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
 131 #define PB_ASSOC_MAP_DEBUG_BASE_C_DEC \
 132         pb_assoc::detail::map_debug_base< \
 133                 Key, \
 134                 Eq_Fn>
 135 #endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
 136
 137 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 138 #define PB_ASSOC_V2F(X) (X).first
 139 #define PB_ASSOC_V2S(X) (X).second
 140 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 141
 142 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
 143 #define PB_ASSOC_V2F(X) (X)
 144 #define PB_ASSOC_V2S(X) Mapped_Data()
 145 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
 146
 147 #define PB_ASSOC_STATIC_ASSERT(UNIQUE, E) \
 148         typedef \
 149                 pb_assoc::detail::static_assert_dummy_class< \
 150                         sizeof(pb_assoc::detail::static_assert<(bool)(E)>)> \
 151                         UNIQUE##static_assert_type
 152
 153     template<typename Key,
 154              typename Data,
 155              class Hash_Fn,
 156              class Eq_Fn,
 157              class Allocator,
 158              bool Store_Hash,
 159              class Comb_Hash_Fn,
 160              class Resize_Policy >
 161     class PB_ASSOC_CLASS_NAME:
 162 #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
 163       protected PB_ASSOC_MAP_DEBUG_BASE_C_DEC,
 164 #endif // #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
 165       public PB_ASSOC_HASH_EQ_FN_C_DEC,
 166       public Resize_Policy,
 167       public PB_ASSOC_RANGED_HASH_FN_C_DEC,
 168       public PB_ASSOC_TYPES_TRAITS_C_DEC,
 169       public PB_ASSOC_HASH_TYPES_TRAITS_C_DEC
 170     {
 171
 172     public:
 173
 174       typedef typename Allocator::size_type size_type;
 175
 176       typedef
 177       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_key_reference
 178       const_key_reference;
 179
 180       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_type data_type;
 181
 182       typedef
 183       typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_reference
 184       data_reference;
 185
 186       typedef
 187       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_data_reference
 188       const_data_reference;
 189
 190       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type value_type;
 191
 192       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::pointer pointer;
 193
 194       typedef
 195       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_pointer
 196       const_pointer;
 197
 198       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::reference reference;
 199
 200       typedef
 201       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_reference
 202       const_reference;
 203
 204     protected:
 205
 206       typedef typename PB_ASSOC_HASH_TYPES_TRAITS_C_DEC::comp_hash comp_hash;
 207
 208       struct no_store_hash_entry
 209       {
 210         value_type m_value;
 211
 212         typename Allocator::template rebind<
 213           no_store_hash_entry>::other::pointer m_p_next;
 214       };
 215
 216       struct store_hash_entry
 217       {
 218         value_type m_value;
 219
 220         size_type m_hash;
 221
 222         typename Allocator::template rebind<
 223           store_hash_entry>::other::pointer m_p_next;
 224       };
 225
 226       typedef
 227       typename cond_type<
 228         Store_Hash,
 229         store_hash_entry,
 230         no_store_hash_entry>::type
 231       entry;
 232
 233       typedef
 234       typename Allocator::template rebind<entry>::other
 235       entry_allocator;
 236
 237       typedef typename entry_allocator::pointer entry_pointer;
 238
 239       typedef typename entry_allocator::const_pointer const_entry_pointer;
 240
 241       typedef typename entry_allocator::reference entry_reference;
 242
 243       typedef
 244       typename entry_allocator::const_reference
 245       const_entry_reference;
 246
 247       typedef
 248       typename Allocator::template rebind<entry_pointer>::other
 249       entry_pointer_allocator;
 250
 251       typedef typename entry_pointer_allocator::pointer entry_pointer_array;
 252
 253       typedef value_type mapped_value_type;
 254
 255       typedef pointer mapped_pointer;
 256
 257       typedef const_pointer const_mapped_pointer;
 258
 259       typedef reference mapped_reference;
 260
 261       typedef const_reference const_mapped_reference;
 262
 263 #define PB_ASSOC_GEN_POS std::pair<entry_pointer, size_type>
 264
 265 #include <ext/pb_assoc/detail/unordered_iterator/const_find_iterator.hpp>
 266 #include <ext/pb_assoc/detail/unordered_iterator/find_iterator.hpp>
 267 #include <ext/pb_assoc/detail/unordered_iterator/const_iterator.hpp>
 268 #include <ext/pb_assoc/detail/unordered_iterator/iterator.hpp>
 269
 270 #undef PB_ASSOC_GEN_POS
 271
 272       typedef find_iterator_ find_iterator;
 273
 274       typedef const_find_iterator_ const_find_iterator;
 275
 276       typedef iterator_ iterator;
 277
 278       typedef const_iterator_ const_iterator;
 279
 280       typedef Hash_Fn hash_fn;
 281
 282       typedef Eq_Fn eq_fn;
 283
 284       typedef Allocator allocator;
 285
 286       typedef Resize_Policy resize_policy;
 287
 288     protected:
 289
 290       PB_ASSOC_CLASS_NAME();
 291
 292       PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn);
 293
 294       PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn);
 295
 296       PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Hash_Fn& r_comb_hash_fn);
 297
 298       PB_ASSOC_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Hash_Fn& r_comb_hash_fn, const Resize_Policy& r_resize_policy);
 299
 300       PB_ASSOC_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other);
 301
 302       virtual
 303       ~PB_ASSOC_CLASS_NAME();
 304
 305       void
 306       swap(PB_ASSOC_CLASS_C_DEC& r_other);
 307
 308       template<class It>
 309       void
 310       copy_from_range(It first_it, It last_it);
 311
 312       inline size_type
 313       size() const;
 314
 315       inline size_type
 316       max_size() const;
 317
 318       inline bool
 319       empty() const;
 320
 321       Hash_Fn&
 322       get_hash_fn();
 323
 324       const Hash_Fn&
 325       get_hash_fn() const;
 326
 327       Eq_Fn&
 328       get_eq_fn();
 329
 330       const Eq_Fn&
 331       get_eq_fn() const;
 332
 333       Comb_Hash_Fn&
 334       get_comb_hash_fn();
 335
 336       const Comb_Hash_Fn&
 337       get_comb_hash_fn() const;
 338
 339       Resize_Policy&
 340       get_resize_policy();
 341
 342       const Resize_Policy&
 343       get_resize_policy() const;
 344
 345       inline std::pair<find_iterator, bool>
 346       insert(const_reference r_val);
 347
 348       inline data_reference
 349       subscript_imp(const_key_reference r_key);
 350
 351       inline find_iterator
 352       find(const_key_reference r_key);
 353
 354       inline const_find_iterator
 355       find(const_key_reference r_key) const;
 356
 357       inline find_iterator
 358       find_end();
 359
 360       inline const_find_iterator
 361       find_end() const;
 362
 363       template<class T>
 364       inline size_type
 365       erase(T r_t, bool erase_entry_if_last, pb_assoc::detail::int_to_type<false>);
 366
 367       template<class T>
 368       inline size_type
 369       erase(T r_t, bool erase_entry_if_last, pb_assoc::detail::int_to_type<true>);
 370
 371       template<class Pred>
 372       inline size_type
 373       erase_if(Pred& r_pred);
 374
 375       void
 376       clear();
 377
 378       inline iterator
 379       begin();
 380
 381       inline const_iterator
 382       begin() const;
 383
 384       inline iterator
 385       end();
 386
 387       inline const_iterator
 388       end() const;
 389
 390 #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
 391
 392       virtual void
 393       assert_valid() const;
 394
 395 #endif // #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
 396
 397       virtual void
 398       do_resize(size_type new_size);
 399
 400     private:
 401
 402       typedef PB_ASSOC_TYPES_TRAITS_C_DEC my_traits_base;
 403
 404       typedef PB_ASSOC_HASH_TYPES_TRAITS_C_DEC my_hash_traits_base;
 405
 406       typedef PB_ASSOC_RANGED_HASH_FN_C_DEC my_ranged_hash_fn_base;
 407
 408       typedef PB_ASSOC_HASH_EQ_FN_C_DEC my_hash_eq_fn_base;
 409
 410       typedef Resize_Policy my_resize_base;
 411
 412 #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
 413       typedef PB_ASSOC_MAP_DEBUG_BASE_C_DEC my_map_debug_base;
 414 #endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
 415
 416     private:
 417
 418       inline bool
 419       do_resize_if_needed();
 420
 421       inline void
 422       do_resize_if_needed_no_throw();
 423
 424       void
 425       resize_imp_no_exceptions(size_type new_size, entry_pointer_array a_p_entries_resized, size_type old_size);
 426
 427       inline entry_pointer
 428       resize_imp_no_exceptions_reassign_pointer(entry_pointer p_e, entry_pointer_array a_p_entries_resized, int_to_type<false>);
 429
 430       inline entry_pointer
 431       resize_imp_no_exceptions_reassign_pointer(entry_pointer p_e, entry_pointer_array a_p_entries_resized, int_to_type<true>);
 432
 433       template<class For_Each_Fn>
 434       void
 435       do_for_each(For_Each_Fn fn);
 436
 437       void
 438       deallocate_links_in_list(entry_pointer p_e);
 439
 440       inline entry_pointer
 441       get_entry(const_reference r_val, int_to_type<false>);
 442
 443       inline entry_pointer
 444       get_entry(const_reference r_val, int_to_type<true>);
 445
 446       inline void
 447       rels_entry(entry_pointer p_e);
 448
 449       void
 450       constructor_insert_new_imp(const_reference r_val, size_type pos, int_to_type<false>);
 451
 452       void
 453       constructor_insert_new_imp(const_reference r_val, size_type pos, int_to_type<true>);
 454
 455       void
 456       deallocate_all();
 457
 458       inline data_reference
 459       subscript_imp(const_key_reference r_key, int_to_type<false>);
 460
 461       inline data_reference
 462       subscript_imp(const_key_reference r_key, int_to_type<true>);
 463
 464       inline std::pair<find_iterator, bool>
 465       insert_imp(const_reference r_val, int_to_type<false>);
 466
 467       inline std::pair<find_iterator, bool>
 468       insert_imp(const_reference r_val, int_to_type<true>);
 469
 470       inline pointer
 471       insert_new_imp(const_reference r_val, size_type pos);
 472
 473       inline pointer
 474       insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair);
 475
 476       inline const_data_reference
 477       const_subscript_imp(const_key_reference r_key, int_to_type<false>) const;
 478
 479       inline const_data_reference
 480       const_subscript_imp(const_key_reference r_key, int_to_type<true>) const;
 481
 482       inline pointer
 483       find_key_pointer(const_key_reference r_key, int_to_type<false>);
 484
 485       inline pointer
 486       find_key_pointer(const_key_reference r_key, int_to_type<true>);
 487
 488       template<class T>
 489       inline size_type
 490       erase_in_pos_imp(T r_t, bool erase_entry_if_last, size_type pos);
 491
 492       template<class T>
 493       inline size_type
 494       erase_in_pos_imp(T r_t, bool erase_entry_if_last, const comp_hash& r_pos_hash_pair);
 495
 496       inline void
 497       erase_entry_pointer(entry_pointer& r_p_e);
 498
 499 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 500       void
 501       inc_it_state(pointer& r_p_value, std::pair<entry_pointer, size_type>& r_pos) const;
 502 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 503
 504       void
 505       inc_it_state(const_pointer& r_p_value, std::pair<entry_pointer, size_type>& r_pos) const;
 506
 507       void
 508       get_start_it_state(pointer& r_p_value, std::pair<entry_pointer, size_type>& r_pos) const;
 509
 510 #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
 511
 512       void
 513       assert_entry_pointer_array_valid(const entry_pointer_array a_p_entries) const;
 514
 515       void
 516       assert_entry_pointer_valid(const entry_pointer p_e, store_hash_true_indicator) const;
 517
 518       void
 519       assert_entry_pointer_valid(const entry_pointer p_e, store_hash_false_indicator) const;
 520
 521 #endif // #ifdef PB_ASSOC_CC_HT_MAP_DEBUG
 522
 523     private:
 524       static entry_allocator s_entry_allocator;
 525
 526       static entry_pointer_allocator s_entry_pointer_allocator;
 527
 528       typedef
 529       pb_assoc::detail::cond_dealtor<
 530         entry,
 531         Allocator>
 532       cond_dealtor_t;
 533
 534       entry_pointer_array m_a_p_entries;
 535
 536       size_type m_num_e_p;
 537
 538       size_type m_num_used_e;
 539
 540       friend class iterator_;
 541
 542       friend class const_iterator_;
 543
 544       static iterator s_end_it;
 545
 546       static const_iterator s_const_end_it;
 547
 548       static find_iterator s_find_end_it;
 549
 550       static const_find_iterator s_const_find_end_it;
 551
 552       enum
 553         {
 554           store_hash_ok =
 555           !Store_Hash ||
 556           !pb_assoc::detail::is_same_type<
 557           Hash_Fn,
 558           pb_assoc::null_hash_fn>::value
 559         };
 560
 561       PB_ASSOC_STATIC_ASSERT(sth, store_hash_ok);
 562     };
 563
 564 #include <ext/pb_assoc/detail/cc_ht_map_/constructor_destructor_fn_imps.hpp>
 565 #include <ext/pb_assoc/detail/cc_ht_map_/entry_list_fn_imps.hpp>
 566 #include <ext/pb_assoc/detail/cc_ht_map_/find_fn_imps.hpp>
 567 #include <ext/pb_assoc/detail/cc_ht_map_/resize_fn_imps.hpp>
 568 #include <ext/pb_assoc/detail/cc_ht_map_/debug_fn_imps.hpp>
 569 #include <ext/pb_assoc/detail/cc_ht_map_/size_fn_imps.hpp>
 570 #include <ext/pb_assoc/detail/cc_ht_map_/policy_access_fn_imps.hpp>
 571 #include <ext/pb_assoc/detail/cc_ht_map_/erase_fn_imps.hpp>
 572 #include <ext/pb_assoc/detail/cc_ht_map_/iterators_fn_imps.hpp>
 573 #include <ext/pb_assoc/detail/cc_ht_map_/insert_fn_imps.hpp>
 574
 575 #undef PB_ASSOC_CLASS_T_DEC
 576
 577 #undef PB_ASSOC_CLASS_C_DEC
 578
 579 #undef PB_ASSOC_HASH_EQ_FN_C_DEC
 580
 581 #undef PB_ASSOC_RANGED_HASH_FN_C_DEC
 582
 583 #undef PB_ASSOC_TYPES_TRAITS_C_DEC
 584
 585 #undef PB_ASSOC_HASH_TYPES_TRAITS_C_DEC
 586
 587 #undef PB_ASSOC_MAP_DEBUG_BASE_C_DEC
 588
 589 #undef PB_ASSOC_CLASS_NAME
 590
 591 #undef PB_ASSOC_V2F
 592 #undef PB_ASSOC_V2S
 593
 594 #undef PB_ASSOC_DBG_ASSERT
 595 #undef PB_ASSOC_DBG_VERIFY
 596 #undef PB_ASSOC_DBG_ONLY
 597
 598 #undef PB_ASSOC_STATIC_ASSERT
 599
 600   } // namespace detail
 601
 602 } // namespace pb_assoc