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