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> 48#include <ext/pb_ds/detail/type_utils.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 53namespace __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. 207 inline std::pair<float, float> 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 605