libstdc++
|
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