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