l4/pkg/l4re-core/libstdc++-v3/contrib/libstdc++-v3-4.9/include/ext/pb_ds/hash_policy.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2014 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 hash_policy.hpp
  38  * Contains hash-related policies.
  39  */
  40
  41 #ifndef PB_DS_HASH_POLICY_HPP
  42 #define PB_DS_HASH_POLICY_HPP
  43
  44 #include <bits/c++config.h>
  45 #include <algorithm>
  46 #include <vector>
  47 #include <cmath>
  48 #include <ext/pb_ds/exception.hpp>
  49 #include <ext/pb_ds/detail/type_utils.hpp>
  50 #include <ext/pb_ds/detail/hash_fn/mask_based_range_hashing.hpp>
  51 #include <ext/pb_ds/detail/hash_fn/mod_based_range_hashing.hpp>
  52 #include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_size_base.hpp>
  53
  54 namespace __gnu_pbds
  55 {
  56 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
  57 #define PB_DS_CLASS_C_DEC linear_probe_fn<Size_Type>
  58
  59   /// A probe sequence policy using fixed increments.
  60   template<typename Size_Type = std::size_t>
  61   class linear_probe_fn
  62   {
  63   public:
  64     typedef Size_Type size_type;
  65
  66     void
  67     swap(PB_DS_CLASS_C_DEC& other);
  68
  69   protected:
  70     /// Returns the i-th offset from the hash value.
  71     inline size_type
  72     operator()(size_type i) const;
  73   };
  74
  75 #include <ext/pb_ds/detail/hash_fn/linear_probe_fn_imp.hpp>
  76
  77 #undef PB_DS_CLASS_T_DEC
  78 #undef PB_DS_CLASS_C_DEC
  79
  80 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
  81 #define PB_DS_CLASS_C_DEC quadratic_probe_fn<Size_Type>
  82
  83   /// A probe sequence policy using square increments.
  84   template<typename Size_Type = std::size_t>
  85   class quadratic_probe_fn
  86   {
  87   public:
  88     typedef Size_Type size_type;
  89
  90     void
  91     swap(PB_DS_CLASS_C_DEC& other);
  92
  93   protected:
  94     /// Returns the i-th offset from the hash value.
  95     inline size_type
  96     operator()(size_type i) const;
  97   };
  98
  99 #include <ext/pb_ds/detail/hash_fn/quadratic_probe_fn_imp.hpp>
 100
 101 #undef PB_DS_CLASS_T_DEC
 102 #undef PB_DS_CLASS_C_DEC
 103
 104 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
 105 #define PB_DS_CLASS_C_DEC direct_mask_range_hashing<Size_Type>
 106
 107   /// A mask range-hashing class (uses a bitmask).
 108   template<typename Size_Type = std::size_t>
 109   class direct_mask_range_hashing
 110   : public detail::mask_based_range_hashing<Size_Type>
 111   {
 112   private:
 113     typedef detail::mask_based_range_hashing<Size_Type> mask_based_base;
 114
 115   public:
 116     typedef Size_Type size_type;
 117
 118     void
 119     swap(PB_DS_CLASS_C_DEC& other);
 120
 121   protected:
 122     void
 123     notify_resized(size_type size);
 124
 125     /// Transforms the __hash value hash into a ranged-hash value
 126     /// (using a bit-mask).
 127     inline size_type
 128     operator()(size_type hash) const;
 129   };
 130
 131 #include <ext/pb_ds/detail/hash_fn/direct_mask_range_hashing_imp.hpp>
 132
 133 #undef PB_DS_CLASS_T_DEC
 134 #undef PB_DS_CLASS_C_DEC
 135
 136 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
 137 #define PB_DS_CLASS_C_DEC direct_mod_range_hashing<Size_Type>
 138
 139   /// A mod range-hashing class (uses the modulo function).
 140   template<typename Size_Type = std::size_t>
 141   class direct_mod_range_hashing
 142   : public detail::mod_based_range_hashing<Size_Type>
 143   {
 144   public:
 145     typedef Size_Type size_type;
 146
 147     void
 148     swap(PB_DS_CLASS_C_DEC& other);
 149
 150   protected:
 151     void
 152     notify_resized(size_type size);
 153
 154     /// Transforms the __hash value hash into a ranged-hash value
 155     /// (using a modulo operation).
 156     inline size_type
 157     operator()(size_type hash) const;
 158
 159   private:
 160     typedef detail::mod_based_range_hashing<size_type> mod_based_base;
 161   };
 162
 163 #include <ext/pb_ds/detail/hash_fn/direct_mod_range_hashing_imp.hpp>
 164
 165 #undef PB_DS_CLASS_T_DEC
 166 #undef PB_DS_CLASS_C_DEC
 167
 168 #define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type>
 169 #define PB_DS_CLASS_C_DEC hash_load_check_resize_trigger<External_Load_Access, Size_Type>
 170 #define PB_DS_SIZE_BASE_C_DEC detail::hash_load_check_resize_trigger_size_base<Size_Type, External_Load_Access>
 171
 172   /// A resize trigger policy based on a load check. It keeps the
 173   /// load factor between some load factors load_min and load_max.
 174   template<bool External_Load_Access = false, typename Size_Type = std::size_t>
 175   class hash_load_check_resize_trigger : private PB_DS_SIZE_BASE_C_DEC
 176   {
 177   public:
 178     typedef Size_Type size_type;
 179
 180     enum
 181       {
 182         /// Specifies whether the load factor can be accessed
 183         /// externally. The two options have different trade-offs in
 184         /// terms of flexibility, genericity, and encapsulation.
 185         external_load_access = External_Load_Access
 186       };
 187
 188     /// Default constructor, or constructor taking load_min and
 189     /// load_max load factors between which this policy will keep the
 190     /// actual load.
 191     hash_load_check_resize_trigger(float load_min = 0.125,
 192                                    float load_max = 0.5);
 193
 194     void
 195     swap(hash_load_check_resize_trigger& other);
 196
 197     virtual
 198     ~hash_load_check_resize_trigger();
 199
 200     /// Returns a pair of the minimal and maximal loads, respectively.
 201     inline std::pair<float, float>
 202     get_loads() const;
 203
 204     /// Sets the loads through a pair of the minimal and maximal
 205     /// loads, respectively.
 206     void
 207     set_loads(std::pair<float, float> load_pair);
 208
 209   protected:
 210     inline void
 211     notify_insert_search_start();
 212
 213     inline void
 214     notify_insert_search_collision();
 215
 216     inline void
 217     notify_insert_search_end();
 218
 219     inline void
 220     notify_find_search_start();
 221
 222     inline void
 223     notify_find_search_collision();
 224
 225     inline void
 226     notify_find_search_end();
 227
 228     inline void
 229     notify_erase_search_start();
 230
 231     inline void
 232     notify_erase_search_collision();
 233
 234     inline void
 235     notify_erase_search_end();
 236
 237     /// Notifies an element was inserted. The total number of entries
 238     /// in the table is num_entries.
 239     inline void
 240     notify_inserted(size_type num_entries);
 241
 242     inline void
 243     notify_erased(size_type num_entries);
 244
 245     /// Notifies the table was cleared.
 246     void
 247     notify_cleared();
 248
 249     /// Notifies the table was resized as a result of this object's
 250     /// signifying that a resize is needed.
 251     void
 252     notify_resized(size_type new_size);
 253
 254     void
 255     notify_externally_resized(size_type new_size);
 256
 257     inline bool
 258     is_resize_needed() const;
 259
 260     inline bool
 261     is_grow_needed(size_type size, size_type num_entries) const;
 262
 263   private:
 264     virtual void
 265     do_resize(size_type new_size);
 266
 267     typedef PB_DS_SIZE_BASE_C_DEC size_base;
 268
 269 #ifdef _GLIBCXX_DEBUG
 270     void
 271     assert_valid(const char* file, int line) const;
 272 #endif
 273
 274     float       m_load_min;
 275     float       m_load_max;
 276     size_type   m_next_shrink_size;
 277     size_type   m_next_grow_size;
 278     bool        m_resize_needed;
 279   };
 280
 281 #include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp>
 282
 283 #undef PB_DS_CLASS_T_DEC
 284 #undef PB_DS_CLASS_C_DEC
 285 #undef PB_DS_SIZE_BASE_C_DEC
 286
 287 #define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type>
 288 #define PB_DS_CLASS_C_DEC cc_hash_max_collision_check_resize_trigger<External_Load_Access, Size_Type>
 289
 290   /// A resize trigger policy based on collision checks. It keeps the
 291   /// simulated load factor lower than some given load factor.
 292   template<bool External_Load_Access = false, typename Size_Type = std::size_t>
 293   class cc_hash_max_collision_check_resize_trigger
 294   {
 295   public:
 296     typedef Size_Type   size_type;
 297
 298     enum
 299       {
 300         /// Specifies whether the load factor can be accessed
 301         /// externally. The two options have different trade-offs in
 302         /// terms of flexibility, genericity, and encapsulation.
 303         external_load_access = External_Load_Access
 304       };
 305
 306     /// Default constructor, or constructor taking load, a __load
 307     /// factor which it will attempt to maintain.
 308     cc_hash_max_collision_check_resize_trigger(float load = 0.5);
 309
 310     void
 311     swap(PB_DS_CLASS_C_DEC& other);
 312
 313     /// Returns the current load.
 314     inline float
 315     get_load() const;
 316
 317     /// Sets the load; does not resize the container.
 318     void
 319     set_load(float load);
 320
 321   protected:
 322     /// Notifies an insert search started.
 323     inline void
 324     notify_insert_search_start();
 325
 326     /// Notifies a search encountered a collision.
 327     inline void
 328     notify_insert_search_collision();
 329
 330     /// Notifies a search ended.
 331     inline void
 332     notify_insert_search_end();
 333
 334     /// Notifies a find search started.
 335     inline void
 336     notify_find_search_start();
 337
 338     /// Notifies a search encountered a collision.
 339     inline void
 340     notify_find_search_collision();
 341
 342     /// Notifies a search ended.
 343     inline void
 344     notify_find_search_end();
 345
 346     /// Notifies an erase search started.
 347     inline void
 348     notify_erase_search_start();
 349
 350     /// Notifies a search encountered a collision.
 351     inline void
 352     notify_erase_search_collision();
 353
 354     /// Notifies a search ended.
 355     inline void
 356     notify_erase_search_end();
 357
 358     /// Notifies an element was inserted.
 359     inline void
 360     notify_inserted(size_type num_entries);
 361
 362     /// Notifies an element was erased.
 363     inline void
 364     notify_erased(size_type num_entries);
 365
 366     /// Notifies the table was cleared.
 367     void
 368     notify_cleared();
 369
 370     /// Notifies the table was resized as a result of this object's
 371     /// signifying that a resize is needed.
 372     void
 373     notify_resized(size_type new_size);
 374
 375     /// Notifies the table was resized externally.
 376     void
 377     notify_externally_resized(size_type new_size);
 378
 379     /// Queries whether a resize is needed.
 380     inline bool
 381     is_resize_needed() const;
 382
 383     /// Queries whether a grow is needed. This method is called only
 384     /// if this object indicated is needed.
 385     inline bool
 386     is_grow_needed(size_type size, size_type num_entries) const;
 387
 388   private:
 389     void
 390     calc_max_num_coll();
 391
 392     inline void
 393     calc_resize_needed();
 394
 395     float       m_load;
 396     size_type   m_size;
 397     size_type   m_num_col;
 398     size_type   m_max_col;
 399     bool        m_resize_needed;
 400   };
 401
 402 #include <ext/pb_ds/detail/resize_policy/cc_hash_max_collision_check_resize_trigger_imp.hpp>
 403
 404 #undef PB_DS_CLASS_T_DEC
 405 #undef PB_DS_CLASS_C_DEC
 406
 407 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
 408 #define PB_DS_CLASS_C_DEC hash_exponential_size_policy<Size_Type>
 409
 410   /// A size policy whose sequence of sizes form an exponential
 411   /// sequence (typically powers of 2.
 412   template<typename Size_Type = std::size_t>
 413   class hash_exponential_size_policy
 414   {
 415   public:
 416     typedef Size_Type size_type;
 417
 418     /// Default constructor, or onstructor taking a start_size, or
 419     /// constructor taking a start size and grow_factor. The policy
 420     /// will use the sequence of sizes start_size, start_size*
 421     /// grow_factor, start_size* grow_factor^2, ...
 422     hash_exponential_size_policy(size_type start_size = 8,
 423                                  size_type grow_factor = 2);
 424
 425     void
 426     swap(PB_DS_CLASS_C_DEC& other);
 427
 428   protected:
 429     size_type
 430     get_nearest_larger_size(size_type size) const;
 431
 432     size_type
 433     get_nearest_smaller_size(size_type size) const;
 434
 435   private:
 436     size_type m_start_size;
 437     size_type m_grow_factor;
 438   };
 439
 440 #include <ext/pb_ds/detail/resize_policy/hash_exponential_size_policy_imp.hpp>
 441
 442 #undef PB_DS_CLASS_T_DEC
 443 #undef PB_DS_CLASS_C_DEC
 444
 445 #define PB_DS_CLASS_T_DEC
 446 #define PB_DS_CLASS_C_DEC hash_prime_size_policy
 447
 448   /// A size policy whose sequence of sizes form a nearly-exponential
 449   /// sequence of primes.
 450   class hash_prime_size_policy
 451   {
 452   public:
 453     /// Size type.
 454     typedef std::size_t size_type;
 455
 456     /// Default constructor, or onstructor taking a start_size The
 457     /// policy will use the sequence of sizes approximately
 458     /// start_size, start_size* 2, start_size* 2^2, ...
 459     hash_prime_size_policy(size_type start_size = 8);
 460
 461     inline void
 462     swap(PB_DS_CLASS_C_DEC& other);
 463
 464   protected:
 465     size_type
 466     get_nearest_larger_size(size_type size) const;
 467
 468     size_type
 469     get_nearest_smaller_size(size_type size) const;
 470
 471   private:
 472     size_type m_start_size;
 473   };
 474
 475 #include <ext/pb_ds/detail/resize_policy/hash_prime_size_policy_imp.hpp>
 476
 477 #undef PB_DS_CLASS_T_DEC
 478 #undef PB_DS_CLASS_C_DEC
 479
 480 #define PB_DS_CLASS_T_DEC template<typename Size_Policy, typename Trigger_Policy, bool External_Size_Access, typename Size_Type>
 481
 482 #define PB_DS_CLASS_C_DEC hash_standard_resize_policy<Size_Policy, Trigger_Policy, External_Size_Access, Size_Type>
 483
 484   /// A resize policy which delegates operations to size and trigger policies.
 485   template<typename Size_Policy = hash_exponential_size_policy<>,
 486            typename Trigger_Policy = hash_load_check_resize_trigger<>,
 487            bool External_Size_Access = false,
 488            typename Size_Type = std::size_t>
 489   class hash_standard_resize_policy
 490   : public Size_Policy, public Trigger_Policy
 491   {
 492   public:
 493     typedef Size_Type           size_type;
 494     typedef Trigger_Policy      trigger_policy;
 495     typedef Size_Policy         size_policy;
 496
 497     enum
 498       {
 499         external_size_access = External_Size_Access
 500       };
 501
 502     /// Default constructor.
 503     hash_standard_resize_policy();
 504
 505     /// constructor taking some policies r_size_policy will be copied
 506     /// by the Size_Policy object of this object.
 507     hash_standard_resize_policy(const Size_Policy& r_size_policy);
 508
 509     /// constructor taking some policies. r_size_policy will be
 510     /// copied by the Size_Policy object of this
 511     /// object. r_trigger_policy will be copied by the Trigger_Policy
 512     /// object of this object.
 513     hash_standard_resize_policy(const Size_Policy& r_size_policy,
 514                                 const Trigger_Policy& r_trigger_policy);
 515
 516     virtual
 517     ~hash_standard_resize_policy();
 518
 519     inline void
 520     swap(PB_DS_CLASS_C_DEC& other);
 521
 522     /// Access to the Size_Policy object used.
 523     Size_Policy&
 524     get_size_policy();
 525
 526     /// Const access to the Size_Policy object used.
 527     const Size_Policy&
 528     get_size_policy() const;
 529
 530     /// Access to the Trigger_Policy object used.
 531     Trigger_Policy&
 532     get_trigger_policy();
 533
 534     /// Access to the Trigger_Policy object used.
 535     const Trigger_Policy&
 536     get_trigger_policy() const;
 537
 538     /// Returns the actual size of the container.
 539     inline size_type
 540     get_actual_size() const;
 541
 542     /// Resizes the container to suggested_new_size, a suggested size
 543     /// (the actual size will be determined by the Size_Policy
 544     /// object).
 545     void
 546     resize(size_type suggested_new_size);
 547
 548   protected:
 549     inline void
 550     notify_insert_search_start();
 551
 552     inline void
 553     notify_insert_search_collision();
 554
 555     inline void
 556     notify_insert_search_end();
 557
 558     inline void
 559     notify_find_search_start();
 560
 561     inline void
 562     notify_find_search_collision();
 563
 564     inline void
 565     notify_find_search_end();
 566
 567     inline void
 568     notify_erase_search_start();
 569
 570     inline void
 571     notify_erase_search_collision();
 572
 573     inline void
 574     notify_erase_search_end();
 575
 576     inline void
 577     notify_inserted(size_type num_e);
 578
 579     inline void
 580     notify_erased(size_type num_e);
 581
 582     void
 583     notify_cleared();
 584
 585     void
 586     notify_resized(size_type new_size);
 587
 588     inline bool
 589     is_resize_needed() const;
 590
 591     /// Queries what the new size should be, when the container is
 592     /// resized naturally. The current __size of the container is
 593     /// size, and the number of used entries within the container is
 594     /// num_used_e.
 595     size_type
 596     get_new_size(size_type size, size_type num_used_e) const;
 597
 598   private:
 599     /// Resizes to new_size.
 600     virtual void
 601     do_resize(size_type new_size);
 602
 603     typedef Trigger_Policy trigger_policy_base;
 604
 605     typedef Size_Policy size_policy_base;
 606
 607     size_type m_size;
 608   };
 609
 610 #include <ext/pb_ds/detail/resize_policy/hash_standard_resize_policy_imp.hpp>
 611
 612 #undef PB_DS_CLASS_T_DEC
 613 #undef PB_DS_CLASS_C_DEC
 614
 615 } // namespace __gnu_pbds
 616
 617 #endif