libstdc++
hash_policy.hpp
Go to the documentation of this file.
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>
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 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_find_search_end()
Notifies a search ended.
Definition: hash_policy.hpp:67
void notify_erase_search_start()
Notifies an erase search started.
Definition: hash_policy.hpp:91
Trigger_Policy & get_trigger_policy()
Access to the Trigger_Policy object used.
void notify_insert_search_end()
Notifies a search ended.
Definition: hash_policy.hpp:85
A mask range-hashing class (uses a bitmask).
Specifies whether the load factor can be accessed externally. The two options have different trade-of...
A resize trigger policy based on a load check. It keeps the load factor between some load factors loa...
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...
void notify_cleared()
Notifies the table was cleared.
void notify_erase_search_collision()
Notifies a search encountered a collision.
Definition: hash_policy.hpp:97
std::size_t size_type
Size type.
GNU extensions for policy-based data structures for public use.
void notify_erase_search_end()
Notifies a search ended.
Specifies whether the load factor can be accessed externally. The two options have different trade-of...
void notify_find_search_start()
Notifies a find search started.
Definition: hash_policy.hpp:55
void notify_resized(size_type new_size)
Notifies the table was resized as a result of this object'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...
void notify_inserted(size_type num_entries)
Notifies an element was inserted.
void notify_cleared()
Notifies the table was cleared.
void notify_insert_search_collision()
Notifies a search encountered a collision.
Definition: hash_policy.hpp:79
A size policy whose sequence of sizes form an exponential sequence (typically powers of 2...
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
std::pair< float, float > get_loads() const
Returns a pair of the minimal and maximal loads, respectively.
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
A resize policy which delegates operations to size and trigger policies.
A probe sequence policy using fixed increments.
Definition: hash_policy.hpp:61
void set_load(float load)
Sets the load; does not resize the container.
float get_load() const
Returns the current load.
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
A resize trigger policy based on collision checks. It keeps the simulated load factor lower than some...
A mod range-hashing class (uses the modulo function).
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
void notify_externally_resized(size_type new_size)
Notifies the table was resized externally.
void notify_erased(size_type num_entries)
Notifies an element was erased.
void notify_find_search_collision()
Notifies a search encountered a collision.
Definition: hash_policy.hpp:61
A probe sequence policy using square increments.
Definition: hash_policy.hpp:85
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
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...
void notify_resized(size_type new_size)
Notifies the table was resized as a result of this object's signifying that a resize is needed...
size_type operator()(size_type i) const
Returns the i-th offset from the hash value.
Definition: hash_policy.hpp:51
size_type get_actual_size() const
Returns the actual size of the container.
hash_standard_resize_policy()
Default constructor.
Definition: hash_policy.hpp:44
void notify_insert_search_start()
Notifies an insert search started.
Definition: hash_policy.hpp:73
void resize(size_type suggested_new_size)
Resizes the container to suggested_new_size, a suggested size (the actual size will be determined by ...
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
A size policy whose sequence of sizes form a nearly-exponential sequence of primes.
bool is_resize_needed() const
Queries whether a resize is needed.