contrib/gcc-4.1/libstdc++-v3/include/ext/pb_assoc/hash_policy.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 hash_policy.hpp
  42  * Contains hash-related policies.
  43  */
  44
  45 #ifndef HASH_POLICY_HPP
  46 #define HASH_POLICY_HPP
  47
  48 #include <algorithm>
  49 #include <vector>
  50 #include <cmath>
  51 #include <ext/pb_assoc/exception.hpp>
  52 #include <ext/pb_assoc/detail/hash_fn/mask_based_range_hashing.hpp>
  53 #include <ext/pb_assoc/detail/hash_fn/mod_based_range_hashing.hpp>
  54 #include <ext/pb_assoc/detail/resize_policy/size_base.hpp>
  55
  56 namespace pb_assoc
  57 {
  58   struct null_hash_fn
  59   { };
  60
  61   struct null_probe_fn
  62   { };
  63
  64 #define PB_ASSOC_CLASS_T_DEC \
  65         template<typename Const_Key_Ref, typename Size_Type>
  66
  67 #define PB_ASSOC_CLASS_C_DEC \
  68         linear_probe_fn< \
  69                 Const_Key_Ref, \
  70                 Size_Type>
  71
  72   template<typename Const_Key_Ref, typename Size_Type = size_t>
  73     class linear_probe_fn
  74     {
  75     public:
  76       typedef Size_Type size_type;
  77
  78       void
  79       swap(PB_ASSOC_CLASS_C_DEC& r_other);
  80
  81     protected:
  82       inline size_type
  83       operator()(Const_Key_Ref r_key, size_type i) const;
  84     };
  85
  86 #include <ext/pb_assoc/detail/hash_fn/linear_probe_fn_imp.hpp>
  87
  88 #undef PB_ASSOC_CLASS_T_DEC
  89 #undef PB_ASSOC_CLASS_C_DEC
  90
  91 #define PB_ASSOC_CLASS_T_DEC \
  92         template<class Const_Key_Ref, typename Size_Type>
  93
  94 #define PB_ASSOC_CLASS_C_DEC \
  95         quadratic_probe_fn<Const_Key_Ref, Size_Type>
  96
  97   template<typename Const_Key_Ref, typename Size_Type = size_t>
  98     class quadratic_probe_fn
  99     {
 100     public:
 101       typedef Size_Type size_type;
 102
 103       void
 104       swap(PB_ASSOC_CLASS_C_DEC& r_other);
 105
 106     protected:
 107       inline size_type
 108       operator()(Const_Key_Ref r_key, size_type i) const;
 109     };
 110
 111 #include <ext/pb_assoc/detail/hash_fn/quadratic_probe_fn_imp.hpp>
 112
 113 #undef PB_ASSOC_CLASS_T_DEC
 114 #undef PB_ASSOC_CLASS_C_DEC
 115
 116 #define PB_ASSOC_CLASS_T_DEC \
 117         template<typename Size_Type>
 118
 119 #define PB_ASSOC_CLASS_C_DEC \
 120         direct_mask_range_hashing<Size_Type>
 121
 122   template<typename Size_Type = size_t>
 123     class direct_mask_range_hashing
 124     : public pb_assoc::detail::mask_based_range_hashing<Size_Type>
 125     {
 126     public:
 127       typedef Size_Type size_type;
 128
 129       void
 130       swap(PB_ASSOC_CLASS_C_DEC& r_other);
 131
 132     protected:
 133       void
 134       notify_resized(size_type size);
 135
 136       inline size_type
 137       operator()(size_type hash) const;
 138
 139     private:
 140       typedef pb_assoc::detail::mask_based_range_hashing<Size_Type>
 141       my_mask_based_base;
 142     };
 143
 144 #define PB_ASSOC_MASK_BASED_C_DEC \
 145         pb_assoc::detail::mask_based_range_hashing< \
 146                 Size_Type>
 147
 148 #include <ext/pb_assoc/detail/hash_fn/direct_mask_range_hashing_imp.hpp>
 149
 150 #undef PB_ASSOC_CLASS_T_DEC
 151 #undef PB_ASSOC_CLASS_C_DEC
 152
 153 #undef PB_ASSOC_MASK_BASED_C_DEC
 154
 155 #define PB_ASSOC_CLASS_T_DEC \
 156         template<typename Size_Type>
 157
 158 #define PB_ASSOC_CLASS_C_DEC \
 159         direct_mod_range_hashing<Size_Type>
 160
 161 #define PB_ASSOC_MOD_BASED_C_DEC \
 162         pb_assoc::detail::mod_based_range_hashing<Size_Type>
 163
 164   template<typename Size_Type = size_t>
 165     class direct_mod_range_hashing : public PB_ASSOC_MOD_BASED_C_DEC
 166     {
 167     public:
 168       typedef Size_Type size_type;
 169
 170       void
 171       swap(PB_ASSOC_CLASS_C_DEC& r_other);
 172
 173     protected:
 174       /*
 175        *   description = "Notifies the policy object that the container's
 176        *          __size has changed to size.">
 177        **/
 178       void
 179       notify_resized(size_type size);
 180
 181       inline size_type
 182     operator()(size_type hash) const;
 183
 184     private:
 185       typedef PB_ASSOC_MOD_BASED_C_DEC my_mod_based_base;
 186     };
 187
 188 #include <ext/pb_assoc/detail/hash_fn/direct_mod_range_hashing_imp.hpp>
 189
 190 #undef PB_ASSOC_CLASS_T_DEC
 191 #undef PB_ASSOC_CLASS_C_DEC
 192
 193 #undef PB_ASSOC_MOD_BASED_C_DEC
 194
 195 #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG
 196 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
 197 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
 198 #define PB_ASSOC_DBG_ONLY(X) X
 199 #else // #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG
 200 #define PB_ASSOC_DBG_ASSERT(X)
 201 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
 202 #define PB_ASSOC_DBG_ONLY(X) ;
 203 #endif // #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG
 204
 205 #define PB_ASSOC_CLASS_T_DEC \
 206         template<bool External_Load_Access, typename Size_Type>
 207
 208 #define PB_ASSOC_CLASS_C_DEC \
 209         hash_load_check_resize_trigger<External_Load_Access, Size_Type>
 210
 211 #define PB_ASSOC_SIZE_BASE_C_DEC \
 212         pb_assoc::detail::size_base<Size_Type, External_Load_Access>
 213
 214   template<bool External_Load_Access = false, typename Size_Type = size_t>
 215     class hash_load_check_resize_trigger : private PB_ASSOC_SIZE_BASE_C_DEC
 216     {
 217     public:
 218       typedef Size_Type size_type;
 219
 220       enum
 221         {
 222           external_load_access = External_Load_Access
 223         };
 224
 225       hash_load_check_resize_trigger(float load_min = 0.125,
 226                                      float load_max = 0.5);
 227
 228       void
 229       swap(PB_ASSOC_CLASS_C_DEC& r_other);
 230
 231       virtual
 232       ~hash_load_check_resize_trigger();
 233
 234       inline std::pair<float, float>
 235       get_loads() const;
 236
 237       void
 238       set_loads(std::pair<float, float> load_pair);
 239
 240     protected:
 241       inline void
 242       notify_insert_search_start();
 243
 244       inline void
 245       notify_insert_search_collision();
 246
 247       inline void
 248       notify_insert_search_end();
 249
 250       inline void
 251       notify_find_search_start();
 252
 253       inline void
 254       notify_find_search_collision();
 255
 256       inline void
 257       notify_find_search_end();
 258
 259       inline void
 260       notify_erase_search_start();
 261
 262       inline void
 263       notify_erase_search_collision();
 264
 265       inline void
 266       notify_erase_search_end();
 267
 268       inline void
 269       notify_inserted(size_type num_entries);
 270
 271       inline void
 272       notify_erased(size_type num_entries);
 273
 274       void
 275       notify_cleared();
 276
 277       void
 278       notify_resized(size_type new_size);
 279
 280       void
 281       notify_externally_resized(size_type new_size);
 282
 283       inline bool
 284       is_resize_needed() const;
 285
 286       inline bool
 287       is_grow_needed(size_type size, size_type num_entries) const;
 288
 289       inline bool
 290       is_shrink_needed(size_type size, size_type num_entries) const;
 291
 292       typedef PB_ASSOC_SIZE_BASE_C_DEC my_size_base;
 293
 294     private:
 295       inline std::pair<float, float>
 296       get_loads_imp(pb_assoc::detail::int_to_type<true>) const;
 297
 298       void
 299       set_loads_imp(std::pair<float, float>,
 300                     pb_assoc::detail::int_to_type<true>);
 301
 302       virtual void
 303       do_resize(size_type new_size);
 304
 305 #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG
 306       void
 307       assert_valid() const;
 308 #endif // #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG
 309
 310       float m_load_min, m_load_max;
 311
 312       size_type m_next_shrink_size;
 313
 314       size_type m_next_grow_size;
 315
 316       bool m_resize_needed;
 317
 318       static pb_assoc::detail::int_to_type<External_Load_Access>
 319       s_external_load_access_ind;
 320     };
 321
 322 #include <ext/pb_assoc/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp>
 323
 324 #undef PB_ASSOC_CLASS_T_DEC
 325 #undef PB_ASSOC_CLASS_C_DEC
 326
 327 #undef PB_ASSOC_SIZE_BASE_C_DEC
 328
 329 #undef PB_ASSOC_DBG_ASSERT
 330 #undef PB_ASSOC_DBG_VERIFY
 331 #undef PB_ASSOC_DBG_ONLY
 332
 333 #ifdef PB_ASSOC_HT_MAX_COLLISION_CHECK_RESIZE_TRIGGER_POLICY_DEBUG
 334 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
 335 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
 336 #define PB_ASSOC_DBG_ONLY(X) X
 337 #else // #ifdef PB_ASSOC_HT_MAX_COLLISION_CHECK_RESIZE_TRIGGER_POLICY_DEBUG
 338 #define PB_ASSOC_DBG_ASSERT(X)
 339 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
 340 #define PB_ASSOC_DBG_ONLY(X) ;
 341 #endif // #ifdef PB_ASSOC_HT_MAX_COLLISION_CHECK_RESIZE_TRIGGER_POLICY_DEBUG
 342
 343 #define PB_ASSOC_CLASS_T_DEC \
 344         template<bool External_Load_Access, typename Size_Type>
 345
 346 #define PB_ASSOC_CLASS_C_DEC \
 347         cc_hash_max_collision_check_resize_trigger< \
 348                 External_Load_Access, \
 349                 Size_Type>
 350
 351   template<bool External_Load_Access = false, typename Size_Type = size_t>
 352     class cc_hash_max_collision_check_resize_trigger
 353     {
 354     public:
 355       typedef Size_Type size_type;
 356
 357       enum
 358         {
 359           external_load_access = External_Load_Access
 360         };
 361
 362       cc_hash_max_collision_check_resize_trigger(float load = 0.5);
 363
 364       void
 365       swap(PB_ASSOC_CLASS_C_DEC& r_other);
 366
 367       inline float
 368       get_load() const;
 369
 370     protected:
 371       inline void
 372       notify_insert_search_start();
 373
 374       inline void
 375       notify_insert_search_collision();
 376
 377       inline void
 378       notify_insert_search_end();
 379
 380       inline void
 381       notify_find_search_start();
 382
 383       inline void
 384       notify_find_search_collision();
 385
 386       inline void
 387       notify_find_search_end();
 388
 389       inline void
 390       notify_erase_search_start();
 391
 392       inline void
 393       notify_erase_search_collision();
 394
 395       inline void
 396       notify_erase_search_end();
 397
 398       inline void
 399       notify_inserted(size_type num_entries);
 400
 401       inline void
 402       notify_erased(size_type num_entries);
 403
 404       void
 405       notify_cleared();
 406
 407       void
 408       notify_resized(size_type new_size);
 409
 410       void
 411       notify_externally_resized(size_type new_size);
 412
 413       inline bool
 414       is_resize_needed() const;
 415
 416       inline bool
 417       is_grow_needed(size_type size, size_type num_entries) const;
 418
 419       inline bool
 420       is_shrink_needed(size_type size, size_type num_entries) const;
 421
 422     private:
 423       template<typename Key>
 424       class max_col_checker
 425       {
 426       public:
 427         max_col_checker(size_type size, size_type* p_max_col)
 428         : m_p_max_col(p_max_col), m_a_col(size, 0)
 429         { }
 430
 431         void
 432         operator()(const std::pair<const Key, size_type>& r_key_pos_pair)
 433         { ++m_a_col[r_key_pos_pair.second]; }
 434
 435       private:
 436         std::vector<size_type> m_a_col;
 437
 438         size_type* const m_p_max_col;
 439       };
 440
 441     private:
 442       inline float
 443       get_load_imp(pb_assoc::detail::int_to_type<true>) const;
 444
 445       float m_load;
 446
 447       size_type m_size;
 448
 449       size_type m_num_col;
 450
 451       size_type m_max_col;
 452
 453       bool m_resize_needed;
 454
 455       static pb_assoc::detail::int_to_type<External_Load_Access>
 456       s_external_load_access_ind;
 457     };
 458
 459 #include <ext/pb_assoc/detail/resize_policy/cc_hash_max_collision_resize_trigger_imp.hpp>
 460
 461 #undef PB_ASSOC_CLASS_T_DEC
 462 #undef PB_ASSOC_CLASS_C_DEC
 463
 464 #undef PB_ASSOC_DBG_ASSERT
 465 #undef PB_ASSOC_DBG_VERIFY
 466 #undef PB_ASSOC_DBG_ONLY
 467
 468 #define PB_ASSOC_CLASS_T_DEC \
 469         template<typename Size_Type>
 470
 471 #define PB_ASSOC_CLASS_C_DEC \
 472         hash_exponential_size_policy< \
 473                 Size_Type>
 474
 475   template<typename Size_Type = size_t>
 476   class hash_exponential_size_policy
 477   {
 478   public:
 479     typedef Size_Type size_type;
 480
 481     hash_exponential_size_policy(size_type start_size = 8,
 482                                  size_type grow_factor = 2);
 483
 484     void
 485     swap(PB_ASSOC_CLASS_C_DEC& r_other);
 486
 487   protected:
 488     size_type
 489     get_init_size(size_type suggested_size) const;
 490
 491     size_type
 492     get_nearest_larger_size(size_type cur_size) const;
 493
 494     size_type
 495     get_nearest_smaller_size(size_type cur_size) const;
 496
 497 #ifdef PB_ASSOC_HT_EXPONENTIAL_SIZE_POLICY_DEBUG
 498     void
 499     assert_is_one_of_my_sizes(size_type size) const;
 500 #endif // #ifdef PB_ASSOC_HT_EXPONENTIAL_SIZE_POLICY_DEBUG
 501
 502   private:
 503     size_type m_start_size;
 504     size_type m_grow_factor;
 505   };
 506
 507 #include <ext/pb_assoc/detail/resize_policy/hash_exponential_size_policy_imp.hpp>
 508
 509 #undef PB_ASSOC_CLASS_T_DEC
 510 #undef PB_ASSOC_CLASS_C_DEC
 511
 512 #undef PB_ASSOC_DBG_ASSERT
 513 #undef PB_ASSOC_DBG_VERIFY
 514 #undef PB_ASSOC_DBG_ONLY
 515
 516 #define PB_ASSOC_CLASS_T_DEC
 517
 518 #define PB_ASSOC_CLASS_C_DEC \
 519         hash_prime_size_policy
 520
 521 #ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG
 522 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
 523 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
 524 #define PB_ASSOC_DBG_ONLY(X) X
 525 #else // #ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG
 526 #define PB_ASSOC_DBG_ASSERT(X)
 527 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
 528 #define PB_ASSOC_DBG_ONLY(X) ;
 529 #endif // #ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG
 530
 531   struct hash_prime_size_policy
 532   {
 533     typedef size_t size_type;
 534
 535     inline void
 536     swap(PB_ASSOC_CLASS_C_DEC& r_other);
 537
 538   protected:
 539     inline size_type
 540     get_init_size(size_type suggested_size) const;
 541
 542     inline size_type
 543     get_nearest_larger_size(size_type cur_size) const;
 544
 545     inline size_type
 546     get_nearest_smaller_size(size_type cur_size) const;
 547
 548     inline size_type
 549     get_nearest_larger_size_imp(size_type size) const;
 550
 551 #ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG
 552     void
 553     assert_is_one_of_my_sizes(size_type size) const;
 554 #endif // #ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG
 555   };
 556
 557 #include <ext/pb_assoc/detail/resize_policy/hash_prime_size_policy_imp.hpp>
 558
 559 #undef PB_ASSOC_CLASS_T_DEC
 560 #undef PB_ASSOC_CLASS_C_DEC
 561
 562 #undef PB_ASSOC_DBG_ASSERT
 563 #undef PB_ASSOC_DBG_VERIFY
 564 #undef PB_ASSOC_DBG_ONLY
 565
 566 #define PB_ASSOC_CLASS_T_DEC \
 567         template< \
 568                 class Size_Policy, \
 569                 class Trigger_Policy, \
 570                 bool External_Size_Access, \
 571                 typename Size_Type>
 572
 573 #define PB_ASSOC_CLASS_C_DEC \
 574         hash_standard_resize_policy< \
 575                 Size_Policy, \
 576                 Trigger_Policy, \
 577                 External_Size_Access, \
 578                 Size_Type>
 579
 580   template<class Size_Policy =  pb_assoc::hash_exponential_size_policy<>,
 581            class Trigger_Policy = pb_assoc::hash_load_check_resize_trigger<>,
 582            bool External_Size_Access = false,
 583            typename Size_Type = size_t>
 584   class hash_standard_resize_policy : public Size_Policy, public Trigger_Policy
 585   {
 586   public:
 587     typedef Size_Type           size_type;
 588     typedef Trigger_Policy      trigger_policy;
 589     typedef Size_Policy         size_policy;
 590
 591     enum
 592       {
 593         external_size_access = External_Size_Access
 594       };
 595
 596     hash_standard_resize_policy(size_type suggested_size = 8);
 597
 598     hash_standard_resize_policy(const Size_Policy&,
 599                                 size_type suggested_size = 8);
 600
 601     hash_standard_resize_policy(const Size_Policy&, const Trigger_Policy&,
 602                                 size_type suggested_size = 8);
 603
 604     virtual
 605     ~hash_standard_resize_policy();
 606
 607     inline void
 608     swap(PB_ASSOC_CLASS_C_DEC& r_other);
 609
 610     Size_Policy&
 611     get_size_policy();
 612
 613     const Size_Policy&
 614     get_size_policy() const;
 615
 616     Trigger_Policy&
 617     get_trigger_policy();
 618
 619     const Trigger_Policy&
 620     get_trigger_policy() const;
 621
 622     inline size_type
 623     get_actual_size() const;
 624
 625     void
 626     resize(size_type suggested_new_size);
 627
 628   protected:
 629
 630     inline void
 631     notify_insert_search_start();
 632
 633     inline void
 634     notify_insert_search_collision();
 635
 636     inline void
 637     notify_insert_search_end();
 638
 639     inline void
 640     notify_find_search_start();
 641
 642     inline void
 643     notify_find_search_collision();
 644
 645     inline void
 646     notify_find_search_end();
 647
 648     inline void
 649     notify_erase_search_start();
 650
 651     inline void
 652     notify_erase_search_collision();
 653
 654     inline void
 655     notify_erase_search_end();
 656
 657     inline void
 658     notify_inserted(size_type num_e);
 659
 660     inline void
 661     notify_erased(size_type num_e);
 662
 663     void
 664     notify_cleared();
 665
 666     void
 667     notify_resized(size_type new_size);
 668
 669     size_type
 670     get_init_size() const;
 671
 672     inline bool
 673     is_resize_needed() const;
 674
 675     size_type
 676     get_new_size(size_type size, size_type num_used_e) const;
 677
 678   private:
 679     typedef Trigger_Policy my_trigger_policy_base;
 680
 681     typedef Size_Policy my_size_policy_base;
 682
 683     typedef
 684     pb_assoc::detail::int_to_type<false>
 685     external_resize_false_indicator;
 686
 687     typedef
 688     pb_assoc::detail::int_to_type<true>
 689     external_resize_true_indicator;
 690
 691     inline size_type
 692     get_actual_size(external_resize_true_indicator) const;
 693
 694     void
 695     resize(size_type new_size, external_resize_true_indicator);
 696
 697     virtual void
 698     do_resize(size_type new_size);
 699
 700     static pb_assoc::detail::int_to_type<External_Size_Access>
 701     s_external_size_access_indicator;
 702
 703     size_type m_size;
 704   };
 705
 706 #include <ext/pb_assoc/detail/resize_policy/hash_standard_resize_policy_imp.hpp>
 707
 708 #undef PB_ASSOC_CLASS_T_DEC
 709 #undef PB_ASSOC_CLASS_C_DEC
 710
 711 #undef PB_ASSOC_DBG_ASSERT
 712 #undef PB_ASSOC_DBG_VERIFY
 713 #undef PB_ASSOC_DBG_ONLY
 714
 715 } // namespace pb_assoc
 716
 717 #endif // #ifndef HASH_POLICY_HPP