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