libstdc++
hash_policy.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2009, 2010 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00026 
00027 // Permission to use, copy, modify, sell, and distribute this software
00028 // is hereby granted without fee, provided that the above copyright
00029 // notice appears in all copies, and that both that copyright notice
00030 // and this permission notice appear in supporting documentation. None
00031 // of the above authors, nor IBM Haifa Research Laboratories, make any
00032 // representation about the suitability of this software for any
00033 // purpose. It is provided "as is" without express or implied
00034 // warranty.
00035 
00036 /**
00037  * @file hash_policy.hpp
00038  * Contains hash-related policies.
00039  */
00040 
00041 #ifndef PB_DS_HASH_POLICY_HPP
00042 #define PB_DS_HASH_POLICY_HPP
00043 
00044 #include <bits/c++config.h>
00045 #include <algorithm>
00046 #include <vector>
00047 #include <cmath>
00048 #include <ext/pb_ds/exception.hpp>
00049 #include <ext/pb_ds/detail/type_utils.hpp>
00050 #include <ext/pb_ds/detail/hash_fn/mask_based_range_hashing.hpp>
00051 #include <ext/pb_ds/detail/hash_fn/mod_based_range_hashing.hpp>
00052 #include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_size_base.hpp>
00053 
00054 namespace __gnu_pbds
00055 {
00056   // A null hash function, indicating that the combining hash function
00057   // is actually a ranged hash function.
00058   struct null_hash_fn
00059   { };
00060 
00061   // A null probe function, indicating that the combining probe
00062   // function is actually a ranged probe function.
00063   struct null_probe_fn
00064   { };
00065 
00066 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
00067 #define PB_DS_CLASS_C_DEC linear_probe_fn<Size_Type>
00068 
00069   // A probe sequence policy using fixed increments.
00070   template<typename Size_Type = std::size_t>
00071   class linear_probe_fn
00072   {
00073   public:
00074     typedef Size_Type size_type;
00075 
00076     void
00077     swap(PB_DS_CLASS_C_DEC& other);
00078 
00079   protected:
00080     // Returns the i-th offset from the hash value.
00081     inline size_type
00082     operator()(size_type i) const;
00083   };
00084 
00085 #include <ext/pb_ds/detail/hash_fn/linear_probe_fn_imp.hpp>
00086 
00087 #undef PB_DS_CLASS_T_DEC
00088 #undef PB_DS_CLASS_C_DEC
00089 
00090 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
00091 #define PB_DS_CLASS_C_DEC quadratic_probe_fn<Size_Type>
00092 
00093   // A probe sequence policy using square increments.
00094   template<typename Size_Type = std::size_t>
00095   class quadratic_probe_fn
00096   {
00097   public:
00098     typedef Size_Type size_type;
00099 
00100     void
00101     swap(PB_DS_CLASS_C_DEC& other);
00102 
00103   protected:
00104     // Returns the i-th offset from the hash value.
00105     inline size_type
00106     operator()(size_type i) const;
00107   };
00108 
00109 #include <ext/pb_ds/detail/hash_fn/quadratic_probe_fn_imp.hpp>
00110 
00111 #undef PB_DS_CLASS_T_DEC
00112 #undef PB_DS_CLASS_C_DEC
00113 
00114 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
00115 #define PB_DS_CLASS_C_DEC direct_mask_range_hashing<Size_Type>
00116 
00117   // A mask range-hashing class (uses a bit-mask).
00118   template<typename Size_Type = std::size_t>
00119   class direct_mask_range_hashing 
00120   : public detail::mask_based_range_hashing<Size_Type>
00121   {
00122   private:
00123     typedef detail::mask_based_range_hashing<Size_Type> mask_based_base;
00124 
00125   public:
00126     typedef Size_Type size_type;
00127 
00128     void
00129     swap(PB_DS_CLASS_C_DEC& other);
00130 
00131   protected:
00132     void
00133     notify_resized(size_type size);
00134 
00135     // Transforms the __hash value hash into a ranged-hash value
00136     // (using a bit-mask).
00137     inline size_type
00138     operator()(size_type hash) const;
00139   };
00140 
00141 #include <ext/pb_ds/detail/hash_fn/direct_mask_range_hashing_imp.hpp>
00142 
00143 #undef PB_DS_CLASS_T_DEC
00144 #undef PB_DS_CLASS_C_DEC
00145 
00146 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
00147 #define PB_DS_CLASS_C_DEC direct_mod_range_hashing<Size_Type>
00148 
00149   // A mod range-hashing class (uses the modulo function).
00150   template<typename Size_Type = std::size_t>
00151   class direct_mod_range_hashing 
00152   : public detail::mod_based_range_hashing<Size_Type>
00153   {
00154   public:
00155     typedef Size_Type size_type;
00156       
00157     void
00158     swap(PB_DS_CLASS_C_DEC& other);
00159 
00160   protected:
00161     void
00162     notify_resized(size_type size);
00163       
00164     // Transforms the __hash value hash into a ranged-hash value
00165     // (using a modulo operation).
00166     inline size_type
00167     operator()(size_type hash) const;
00168       
00169   private:
00170     typedef detail::mod_based_range_hashing<size_type> mod_based_base;
00171   };
00172 
00173 #include <ext/pb_ds/detail/hash_fn/direct_mod_range_hashing_imp.hpp>
00174 
00175 #undef PB_DS_CLASS_T_DEC
00176 #undef PB_DS_CLASS_C_DEC
00177 
00178 #define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type>
00179 #define PB_DS_CLASS_C_DEC hash_load_check_resize_trigger<External_Load_Access, Size_Type>
00180 #define PB_DS_SIZE_BASE_C_DEC detail::hash_load_check_resize_trigger_size_base<Size_Type, External_Load_Access>
00181 
00182   // A resize trigger policy based on a load check. It keeps the
00183   // load factor between some load factors load_min and load_max.
00184   template<bool External_Load_Access = false, typename Size_Type = std::size_t>
00185   class hash_load_check_resize_trigger : private PB_DS_SIZE_BASE_C_DEC
00186   {
00187   public:
00188     typedef Size_Type size_type;
00189 
00190     enum
00191       {
00192     external_load_access = External_Load_Access
00193       };
00194 
00195     // Default constructor, or constructor taking load_min and
00196     // load_max load factors between which this policy will keep the
00197     // actual load.
00198     hash_load_check_resize_trigger(float load_min = 0.125,
00199                    float load_max = 0.5);
00200 
00201     void
00202     swap(hash_load_check_resize_trigger& other);
00203 
00204     virtual
00205     ~hash_load_check_resize_trigger();
00206 
00207     // Returns a pair of the minimal and maximal loads, respectively.
00208     inline std::pair<float, float>
00209     get_loads() const;
00210 
00211     // Sets the loads through a pair of the minimal and maximal
00212     // loads, respectively.
00213     void
00214     set_loads(std::pair<float, float> load_pair);
00215 
00216   protected:
00217     inline void
00218     notify_insert_search_start();
00219 
00220     inline void
00221     notify_insert_search_collision();
00222 
00223     inline void
00224     notify_insert_search_end();
00225 
00226     inline void
00227     notify_find_search_start();
00228 
00229     inline void
00230     notify_find_search_collision();
00231 
00232     inline void
00233     notify_find_search_end();
00234 
00235     inline void
00236     notify_erase_search_start();
00237 
00238     inline void
00239     notify_erase_search_collision();
00240 
00241     inline void
00242     notify_erase_search_end();
00243 
00244     // Notifies an element was inserted. The total number of entries
00245     // in the table is num_entries.
00246     inline void
00247     notify_inserted(size_type num_entries);
00248 
00249     inline void
00250     notify_erased(size_type num_entries);
00251 
00252     // Notifies the table was cleared.
00253     void
00254     notify_cleared();
00255 
00256     // Notifies the table was resized as a result of this object's
00257     // signifying that a resize is needed.
00258     void
00259     notify_resized(size_type new_size);
00260 
00261     void
00262     notify_externally_resized(size_type new_size);
00263 
00264     inline bool
00265     is_resize_needed() const;
00266 
00267     inline bool
00268     is_grow_needed(size_type size, size_type num_entries) const;
00269 
00270   private:
00271     virtual void
00272     do_resize(size_type new_size);
00273 
00274     typedef PB_DS_SIZE_BASE_C_DEC size_base;
00275 
00276 #ifdef _GLIBCXX_DEBUG
00277     void
00278     assert_valid() const;
00279 #endif 
00280 
00281     float   m_load_min;
00282     float   m_load_max;
00283     size_type   m_next_shrink_size;
00284     size_type   m_next_grow_size;
00285     bool    m_resize_needed;
00286   };
00287 
00288 #include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp>
00289 
00290 #undef PB_DS_CLASS_T_DEC
00291 #undef PB_DS_CLASS_C_DEC
00292 #undef PB_DS_SIZE_BASE_C_DEC
00293 
00294 #define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type>
00295 #define PB_DS_CLASS_C_DEC cc_hash_max_collision_check_resize_trigger<External_Load_Access, Size_Type>
00296 
00297   // A resize trigger policy based on collision checks. It keeps the
00298   // simulated load factor lower than some given load factor.
00299   template<bool External_Load_Access = false, typename Size_Type = std::size_t>
00300   class cc_hash_max_collision_check_resize_trigger
00301   {
00302   public:
00303     typedef Size_Type size_type;
00304 
00305     enum
00306       {
00307     external_load_access = External_Load_Access
00308       };
00309 
00310     // Default constructor, or constructor taking load, a __load
00311     // factor which it will attempt to maintain.
00312     cc_hash_max_collision_check_resize_trigger(float load = 0.5);
00313 
00314     void
00315     swap(PB_DS_CLASS_C_DEC& other);
00316 
00317     // Returns the current load.
00318     inline float
00319     get_load() const;
00320 
00321     // Sets the load; does not resize the container.
00322     void
00323     set_load(float load);
00324 
00325   protected:
00326     inline void
00327     notify_insert_search_start();
00328 
00329     inline void
00330     notify_insert_search_collision();
00331 
00332     inline void
00333     notify_insert_search_end();
00334 
00335     inline void
00336     notify_find_search_start();
00337 
00338     inline void
00339     notify_find_search_collision();
00340 
00341     inline void
00342     notify_find_search_end();
00343 
00344     inline void
00345     notify_erase_search_start();
00346 
00347     inline void
00348     notify_erase_search_collision();
00349 
00350     inline void
00351     notify_erase_search_end();
00352 
00353     inline void
00354     notify_inserted(size_type num_entries);
00355 
00356     inline void
00357     notify_erased(size_type num_entries);
00358 
00359     void
00360     notify_cleared();
00361 
00362     // Notifies the table was resized as a result of this object's
00363     // signifying that a resize is needed.
00364     void
00365     notify_resized(size_type new_size);
00366 
00367     void
00368     notify_externally_resized(size_type new_size);
00369 
00370     inline bool
00371     is_resize_needed() const;
00372 
00373     inline bool
00374     is_grow_needed(size_type size, size_type num_entries) const;
00375 
00376   private:
00377     void
00378     calc_max_num_coll();
00379 
00380     inline void
00381     calc_resize_needed();
00382 
00383     float   m_load;
00384     size_type   m_size;
00385     size_type   m_num_col;
00386     size_type   m_max_col;
00387     bool    m_resize_needed;
00388   };
00389 
00390 #include <ext/pb_ds/detail/resize_policy/cc_hash_max_collision_check_resize_trigger_imp.hpp>
00391 
00392 #undef PB_DS_CLASS_T_DEC
00393 #undef PB_DS_CLASS_C_DEC
00394 
00395 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
00396 #define PB_DS_CLASS_C_DEC hash_exponential_size_policy<Size_Type>
00397 
00398   // A size policy whose sequence of sizes form an exponential
00399   // sequence (typically powers of 2.
00400   template<typename Size_Type = std::size_t>
00401   class hash_exponential_size_policy
00402   {
00403   public:
00404     typedef Size_Type size_type;
00405 
00406     // Default constructor, or onstructor taking a start_size, or
00407     // constructor taking a start size and grow_factor. The policy
00408     // will use the sequence of sizes start_size, start_size*
00409     // grow_factor, start_size* grow_factor^2, ...
00410     hash_exponential_size_policy(size_type start_size = 8,
00411                  size_type grow_factor = 2);
00412 
00413     void
00414     swap(PB_DS_CLASS_C_DEC& other);
00415 
00416   protected:
00417     size_type
00418     get_nearest_larger_size(size_type size) const;
00419 
00420     size_type
00421     get_nearest_smaller_size(size_type size) const;
00422 
00423   private:
00424     size_type m_start_size;
00425     size_type m_grow_factor;
00426   };
00427 
00428 #include <ext/pb_ds/detail/resize_policy/hash_exponential_size_policy_imp.hpp>
00429 
00430 #undef PB_DS_CLASS_T_DEC
00431 #undef PB_DS_CLASS_C_DEC
00432 
00433 #define PB_DS_CLASS_T_DEC
00434 #define PB_DS_CLASS_C_DEC hash_prime_size_policy
00435 
00436   // A size policy whose sequence of sizes form a nearly-exponential
00437   // sequence of primes.
00438   class hash_prime_size_policy
00439   {
00440   public:
00441     // Size type.
00442     typedef std::size_t size_type;
00443 
00444     // Default constructor, or onstructor taking a start_size The
00445     // policy will use the sequence of sizes approximately
00446     // start_size, start_size* 2, start_size* 2^2, ...
00447     hash_prime_size_policy(size_type start_size = 8);
00448 
00449     inline void
00450     swap(PB_DS_CLASS_C_DEC& other);
00451 
00452   protected:
00453     size_type
00454     get_nearest_larger_size(size_type size) const;
00455 
00456     size_type
00457     get_nearest_smaller_size(size_type size) const;
00458 
00459   private:
00460     size_type m_start_size;
00461   };
00462 
00463 #include <ext/pb_ds/detail/resize_policy/hash_prime_size_policy_imp.hpp>
00464 
00465 #undef PB_DS_CLASS_T_DEC
00466 #undef PB_DS_CLASS_C_DEC
00467 
00468 #define PB_DS_CLASS_T_DEC template<typename Size_Policy, typename Trigger_Policy, bool External_Size_Access, typename Size_Type>
00469 
00470 #define PB_DS_CLASS_C_DEC hash_standard_resize_policy<Size_Policy, Trigger_Policy, External_Size_Access, Size_Type>
00471 
00472   // A resize policy which delegates operations to size and trigger policies.
00473   template<typename Size_Policy = hash_exponential_size_policy<>,
00474        typename Trigger_Policy = hash_load_check_resize_trigger<>,
00475        bool External_Size_Access = false,
00476        typename Size_Type = std::size_t>
00477   class hash_standard_resize_policy 
00478   : public Size_Policy, public Trigger_Policy
00479   {
00480   public:
00481     typedef Size_Type       size_type;
00482     typedef Trigger_Policy  trigger_policy;
00483     typedef Size_Policy     size_policy;
00484 
00485     enum
00486       {
00487     external_size_access = External_Size_Access
00488       };
00489 
00490     // Default constructor.
00491     hash_standard_resize_policy();
00492 
00493     // constructor taking some policies r_size_policy will be copied
00494     // by the Size_Policy object of this object.
00495     hash_standard_resize_policy(const Size_Policy& r_size_policy);
00496 
00497     // constructor taking some policies. r_size_policy will be
00498     // copied by the Size_Policy object of this
00499     // object. r_trigger_policy will be copied by the Trigger_Policy
00500     // object of this object.
00501     hash_standard_resize_policy(const Size_Policy& r_size_policy, 
00502                 const Trigger_Policy& r_trigger_policy);
00503 
00504     virtual
00505     ~hash_standard_resize_policy();
00506 
00507     inline void
00508     swap(PB_DS_CLASS_C_DEC& other);
00509 
00510     // Access to the Size_Policy object used.
00511     Size_Policy& 
00512     get_size_policy();
00513 
00514     // Const access to the Size_Policy object used.
00515     const Size_Policy& 
00516     get_size_policy() const;
00517 
00518     // Access to the Trigger_Policy object used.
00519     Trigger_Policy& 
00520     get_trigger_policy();
00521 
00522     // Access to the Trigger_Policy object used.
00523     const Trigger_Policy& 
00524     get_trigger_policy() const;
00525 
00526     // Returns the actual size of the container.
00527     inline size_type
00528     get_actual_size() const;
00529 
00530     // Resizes the container to suggested_new_size, a suggested size
00531     // (the actual size will be determined by the Size_Policy
00532     // object).
00533     void
00534     resize(size_type suggested_new_size);
00535 
00536   protected:
00537     inline void
00538     notify_insert_search_start();
00539 
00540     inline void
00541     notify_insert_search_collision();
00542 
00543     inline void
00544     notify_insert_search_end();
00545 
00546     inline void
00547     notify_find_search_start();
00548 
00549     inline void
00550     notify_find_search_collision();
00551 
00552     inline void
00553     notify_find_search_end();
00554 
00555     inline void
00556     notify_erase_search_start();
00557 
00558     inline void
00559     notify_erase_search_collision();
00560 
00561     inline void
00562     notify_erase_search_end();
00563 
00564     inline void
00565     notify_inserted(size_type num_e);
00566 
00567     inline void
00568     notify_erased(size_type num_e);
00569 
00570     void
00571     notify_cleared();
00572 
00573     void
00574     notify_resized(size_type new_size);
00575 
00576     inline bool
00577     is_resize_needed() const;
00578 
00579     // Queries what the new size should be, when the container is
00580     // resized naturally. The current __size of the container is
00581     // size, and the number of used entries within the container is
00582     // num_used_e.
00583     size_type
00584     get_new_size(size_type size, size_type num_used_e) const;
00585 
00586   private:
00587     // Resizes to new_size.
00588     virtual void
00589     do_resize(size_type new_size);
00590 
00591     typedef Trigger_Policy trigger_policy_base;
00592 
00593     typedef Size_Policy size_policy_base;
00594 
00595     size_type m_size;
00596   };
00597 
00598 #include <ext/pb_ds/detail/resize_policy/hash_standard_resize_policy_imp.hpp>
00599 
00600 #undef PB_DS_CLASS_T_DEC
00601 #undef PB_DS_CLASS_C_DEC
00602 
00603 } // namespace __gnu_pbds
00604 
00605 #endif