libstdc++
hash_policy.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2019 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>
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>
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 
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>
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 
100 
101 #undef PB_DS_CLASS_T_DEC
102 #undef PB_DS_CLASS_C_DEC
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>
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 
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>
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;
159  private:
160  typedef detail::mod_based_range_hashing<size_type> mod_based_base;
161  };
162 
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
199 
200  /// Returns a pair of the minimal and maximal loads, respectively.
202  get_loads() const;
203 
204  /// Sets the loads through a pair of the minimal and maximal
205  /// loads, respectively.
206  void
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();
231  inline void
232  notify_erase_search_collision();
233 
234  inline void
235  notify_erase_search_end();
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();
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 
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>
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.
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
325 
326  /// Notifies a search encountered a collision.
327  inline void
329 
330  /// Notifies a search ended.
331  inline void
333 
334  /// Notifies a find search started.
335  inline void
337 
338  /// Notifies a search encountered a collision.
339  inline void
341 
342  /// Notifies a search ended.
343  inline void
345 
346  /// Notifies an erase search started.
347  inline void
349 
350  /// Notifies a search encountered a collision.
351  inline void
353 
354  /// Notifies a search ended.
355  inline void
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 
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>
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 
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.
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 
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>
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.
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
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&
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 
611 
612 #undef PB_DS_CLASS_T_DEC
613 #undef PB_DS_CLASS_C_DEC
614 
615 } // namespace __gnu_pbds
616 
617 #endif
void notify_erase_search_start()
Notifies an erase search started.
Definition: hash_policy.hpp:91
A probe sequence policy using fixed increments.
Definition: hash_policy.hpp:61
void notify_insert_search_end()
Notifies a search ended.
Definition: hash_policy.hpp:85
void set_load(float load)
Sets the load; does not resize the container.
hash_exponential_size_policy(size_type start_size=8, size_type grow_factor=2)
Default constructor, or onstructor taking a start_size, or constructor taking a start size and grow_f...
Definition: hash_policy.hpp:44
void notify_insert_search_collision()
Notifies a search encountered a collision.
Definition: hash_policy.hpp:79
A mod range-hashing class (uses the modulo function).
void notify_resized(size_type new_size)
Notifies the table was resized as a result of this object&#39;s signifying that a resize is needed...
size_type get_actual_size() const
Returns the actual size of the container.
size_type operator()(size_type hash) const
Transforms the __hash value hash into a ranged-hash value (using a modulo operation).
Definition: hash_policy.hpp:57
A size policy whose sequence of sizes form a nearly-exponential sequence of primes.
Trigger_Policy & get_trigger_policy()
Access to the Trigger_Policy object used.
A size policy whose sequence of sizes form an exponential sequence (typically powers of 2...
void resize(size_type suggested_new_size)
Resizes the container to suggested_new_size, a suggested size (the actual size will be determined by ...
void notify_find_search_collision()
Notifies a search encountered a collision.
Definition: hash_policy.hpp:61
bool is_grow_needed(size_type size, size_type num_entries) const
Queries whether a grow is needed. This method is called only if this object indicated is needed...
size_type operator()(size_type hash) const
Transforms the __hash value hash into a ranged-hash value (using a bit-mask).
Definition: hash_policy.hpp:57
size_type operator()(size_type i) const
Returns the i-th offset from the hash value.
Definition: hash_policy.hpp:51
void notify_cleared()
Notifies the table was cleared.
void notify_inserted(size_type num_entries)
Notifies an element was inserted.
void notify_find_search_end()
Notifies a search ended.
Definition: hash_policy.hpp:67
A resize trigger policy based on a load check. It keeps the load factor between some load factors loa...
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:208
void notify_insert_search_start()
Notifies an insert search started.
Definition: hash_policy.hpp:73
A mask range-hashing class (uses a bitmask).
A probe sequence policy using square increments.
Definition: hash_policy.hpp:85
Size_Policy & get_size_policy()
Access to the Size_Policy object used.
cc_hash_max_collision_check_resize_trigger(float load=0.5)
Default constructor, or constructor taking load, a __load factor which it will attempt to maintain...
Definition: hash_policy.hpp:44
void notify_erased(size_type num_entries)
Notifies an element was erased.
hash_load_check_resize_trigger(float load_min=0.125, float load_max=0.5)
Default constructor, or constructor taking load_min and load_max load factors between which this poli...
Definition: hash_policy.hpp:47
void notify_find_search_start()
Notifies a find search started.
Definition: hash_policy.hpp:55
void set_loads(std::pair< float, float > load_pair)
Sets the loads through a pair of the minimal and maximal loads, respectively.
size_type operator()(size_type i) const
Returns the i-th offset from the hash value.
Definition: hash_policy.hpp:51
void notify_erase_search_collision()
Notifies a search encountered a collision.
Definition: hash_policy.hpp:97
bool is_resize_needed() const
Queries whether a resize is needed.
void notify_resized(size_type new_size)
Notifies the table was resized as a result of this object&#39;s signifying that a resize is needed...
size_type get_new_size(size_type size, size_type num_used_e) const
Queries what the new size should be, when the container is resized naturally. The current __size of t...
std::size_t size_type
Size type.
Specifies whether the load factor can be accessed externally. The two options have different trade-of...
void notify_erase_search_end()
Notifies a search ended.
float get_load() const
Returns the current load.
A resize policy which delegates operations to size and trigger policies.
hash_standard_resize_policy()
Default constructor.
Definition: hash_policy.hpp:44
void notify_inserted(size_type num_entries)
Notifies an element was inserted. The total number of entries in the table is num_entries.
hash_prime_size_policy(size_type start_size=8)
Default constructor, or onstructor taking a start_size The policy will use the sequence of sizes appr...
std::pair< float, float > get_loads() const
Returns a pair of the minimal and maximal loads, respectively.
void notify_cleared()
Notifies the table was cleared.
void notify_externally_resized(size_type new_size)
Notifies the table was resized externally.
A resize trigger policy based on collision checks. It keeps the simulated load factor lower than some...
Specifies whether the load factor can be accessed externally. The two options have different trade-of...