1// -*- C++ -*- 2 3// Copyright (C) 2005-2022 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 <bits/c++config.h> 45#include <algorithm> 46#include <vector> 47#include <cmath> 48#include <ext/pb_ds/exception.hpp> 49#include <ext/pb_ds/detail/type_utils.hpp> 50#include <ext/pb_ds/detail/hash_fn/mask_based_range_hashing.hpp> 51#include <ext/pb_ds/detail/hash_fn/mod_based_range_hashing.hpp> 52#include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_size_base.hpp> 53 54namespace __gnu_pbds 55{ 56#define PB_DS_CLASS_T_DEC template<typename Size_Type> 57#define PB_DS_CLASS_C_DEC linear_probe_fn<Size_Type> 58 59 /// A probe sequence policy using fixed increments. 60 template<typename Size_Type = std::size_t> 61 class linear_probe_fn 62 { 63 public: 64 typedef Size_Type size_type; 65 66 void 67 swap(PB_DS_CLASS_C_DEC& other); 68 69 protected: 70 /// Returns the i-th offset from the hash value. 71 inline size_type 72 operator()(size_type i) const; 73 }; 74 75#include <ext/pb_ds/detail/hash_fn/linear_probe_fn_imp.hpp> 76 77#undef PB_DS_CLASS_T_DEC 78#undef PB_DS_CLASS_C_DEC 79 80#define PB_DS_CLASS_T_DEC template<typename Size_Type> 81#define PB_DS_CLASS_C_DEC quadratic_probe_fn<Size_Type> 82 83 /// A probe sequence policy using square increments. 84 template<typename Size_Type = std::size_t> 85 class quadratic_probe_fn 86 { 87 public: 88 typedef Size_Type size_type; 89 90 void 91 swap(PB_DS_CLASS_C_DEC& other); 92 93 protected: 94 /// Returns the i-th offset from the hash value. 95 inline size_type 96 operator()(size_type i) const; 97 }; 98 99#include <ext/pb_ds/detail/hash_fn/quadratic_probe_fn_imp.hpp> 100 101#undef PB_DS_CLASS_T_DEC 102#undef PB_DS_CLASS_C_DEC 103 104#define PB_DS_CLASS_T_DEC template<typename Size_Type> 105#define PB_DS_CLASS_C_DEC direct_mask_range_hashing<Size_Type> 106 107 /// A mask range-hashing class (uses a bitmask). 108 template<typename Size_Type = std::size_t> 109 class direct_mask_range_hashing 110 : public detail::mask_based_range_hashing<Size_Type> 111 { 112 private: 113 typedef detail::mask_based_range_hashing<Size_Type> mask_based_base; 114 115 public: 116 typedef Size_Type size_type; 117 118 void 119 swap(PB_DS_CLASS_C_DEC& other); 120 121 protected: 122 void 123 notify_resized(size_type size); 124 125 /// Transforms the __hash value hash into a ranged-hash value 126 /// (using a bit-mask). 127 inline size_type 128 operator()(size_type hash) const; 129 }; 130 131#include <ext/pb_ds/detail/hash_fn/direct_mask_range_hashing_imp.hpp> 132 133#undef PB_DS_CLASS_T_DEC 134#undef PB_DS_CLASS_C_DEC 135 136#define PB_DS_CLASS_T_DEC template<typename Size_Type> 137#define PB_DS_CLASS_C_DEC direct_mod_range_hashing<Size_Type> 138 139 /// A mod range-hashing class (uses the modulo function). 140 template<typename Size_Type = std::size_t> 141 class direct_mod_range_hashing 142 : public detail::mod_based_range_hashing<Size_Type> 143 { 144 public: 145 typedef Size_Type size_type; 146 147 void 148 swap(PB_DS_CLASS_C_DEC& other); 149 150 protected: 151 void 152 notify_resized(size_type size); 153 154 /// Transforms the __hash value hash into a ranged-hash value 155 /// (using a modulo operation). 156 inline size_type 157 operator()(size_type hash) const; 158 159 private: 160 typedef detail::mod_based_range_hashing<size_type> mod_based_base; 161 }; 162 163#include <ext/pb_ds/detail/hash_fn/direct_mod_range_hashing_imp.hpp> 164 165#undef PB_DS_CLASS_T_DEC 166#undef PB_DS_CLASS_C_DEC 167 168#define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type> 169#define PB_DS_CLASS_C_DEC hash_load_check_resize_trigger<External_Load_Access, Size_Type> 170#define PB_DS_SIZE_BASE_C_DEC detail::hash_load_check_resize_trigger_size_base<Size_Type, External_Load_Access> 171 172 /// A resize trigger policy based on a load check. It keeps the 173 /// load factor between some load factors load_min and load_max. 174 template<bool External_Load_Access = false, typename Size_Type = std::size_t> 175 class hash_load_check_resize_trigger : private PB_DS_SIZE_BASE_C_DEC 176 { 177 public: 178 typedef Size_Type size_type; 179 180 enum 181 { 182 /// Specifies whether the load factor can be accessed 183 /// externally. The two options have different trade-offs in 184 /// terms of flexibility, genericity, and encapsulation. 185 external_load_access = External_Load_Access 186 }; 187 188 /// Default constructor, or constructor taking load_min and 189 /// load_max load factors between which this policy will keep the 190 /// actual load. 191 hash_load_check_resize_trigger(float load_min = 0.125, 192 float load_max = 0.5); 193 194 void 195 swap(hash_load_check_resize_trigger& other); 196 197 virtual 198 ~hash_load_check_resize_trigger(); 199 200 /// Returns a pair of the minimal and maximal loads, respectively. 201 inline std::pair<float, float> 202 get_loads() const; 203 204 /// Sets the loads through a pair of the minimal and maximal 205 /// loads, respectively. 206 void 207 set_loads(std::pair<float, float> load_pair); 208 209 protected: 210 inline void 211 notify_insert_search_start(); 212 213 inline void 214 notify_insert_search_collision(); 215 216 inline void 217 notify_insert_search_end(); 218 219 inline void 220 notify_find_search_start(); 221 222 inline void 223 notify_find_search_collision(); 224 225 inline void 226 notify_find_search_end(); 227 228 inline void 229 notify_erase_search_start(); 230 231 inline void 232 notify_erase_search_collision(); 233 234 inline void 235 notify_erase_search_end(); 236 237 /// Notifies an element was inserted. The total number of entries 238 /// in the table is num_entries. 239 inline void 240 notify_inserted(size_type num_entries); 241 242 inline void 243 notify_erased(size_type num_entries); 244 245 /// Notifies the table was cleared. 246 void 247 notify_cleared(); 248 249 /// Notifies the table was resized as a result of this object's 250 /// signifying that a resize is needed. 251 void 252 notify_resized(size_type new_size); 253 254 void 255 notify_externally_resized(size_type new_size); 256 257 inline bool 258 is_resize_needed() const; 259 260 inline bool 261 is_grow_needed(size_type size, size_type num_entries) const; 262 263 private: 264 virtual void 265 do_resize(size_type new_size); 266 267 typedef PB_DS_SIZE_BASE_C_DEC size_base; 268 269#ifdef _GLIBCXX_DEBUG 270 void 271 assert_valid(const char* file, int line) const; 272#endif 273 274 float m_load_min; 275 float m_load_max; 276 size_type m_next_shrink_size; 277 size_type m_next_grow_size; 278 bool m_resize_needed; 279 }; 280 281#include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp> 282 283#undef PB_DS_CLASS_T_DEC 284#undef PB_DS_CLASS_C_DEC 285#undef PB_DS_SIZE_BASE_C_DEC 286 287#define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type> 288#define PB_DS_CLASS_C_DEC cc_hash_max_collision_check_resize_trigger<External_Load_Access, Size_Type> 289 290 /// A resize trigger policy based on collision checks. It keeps the 291 /// simulated load factor lower than some given load factor. 292 template<bool External_Load_Access = false, typename Size_Type = std::size_t> 293 class cc_hash_max_collision_check_resize_trigger 294 { 295 public: 296 typedef Size_Type size_type; 297 298 enum 299 { 300 /// Specifies whether the load factor can be accessed 301 /// externally. The two options have different trade-offs in 302 /// terms of flexibility, genericity, and encapsulation. 303 external_load_access = External_Load_Access 304 }; 305 306 /// Default constructor, or constructor taking load, a __load 307 /// factor which it will attempt to maintain. 308 cc_hash_max_collision_check_resize_trigger(float load = 0.5); 309 310 void 311 swap(PB_DS_CLASS_C_DEC& other); 312 313 /// Returns the current load. 314 inline float 315 get_load() const; 316 317 /// Sets the load; does not resize the container. 318 void 319 set_load(float load); 320 321 protected: 322 /// Notifies an insert search started. 323 inline void 324 notify_insert_search_start(); 325 326 /// Notifies a search encountered a collision. 327 inline void 328 notify_insert_search_collision(); 329 330 /// Notifies a search ended. 331 inline void 332 notify_insert_search_end(); 333 334 /// Notifies a find search started. 335 inline void 336 notify_find_search_start(); 337 338 /// Notifies a search encountered a collision. 339 inline void 340 notify_find_search_collision(); 341 342 /// Notifies a search ended. 343 inline void 344 notify_find_search_end(); 345 346 /// Notifies an erase search started. 347 inline void 348 notify_erase_search_start(); 349 350 /// Notifies a search encountered a collision. 351 inline void 352 notify_erase_search_collision(); 353 354 /// Notifies a search ended. 355 inline void 356 notify_erase_search_end(); 357 358 /// Notifies an element was inserted. 359 inline void 360 notify_inserted(size_type num_entries); 361 362 /// Notifies an element was erased. 363 inline void 364 notify_erased(size_type num_entries); 365 366 /// Notifies the table was cleared. 367 void 368 notify_cleared(); 369 370 /// Notifies the table was resized as a result of this object's 371 /// signifying that a resize is needed. 372 void 373 notify_resized(size_type new_size); 374 375 /// Notifies the table was resized externally. 376 void 377 notify_externally_resized(size_type new_size); 378 379 /// Queries whether a resize is needed. 380 inline bool 381 is_resize_needed() const; 382 383 /// Queries whether a grow is needed. This method is called only 384 /// if this object indicated is needed. 385 inline bool 386 is_grow_needed(size_type size, size_type num_entries) const; 387 388 private: 389 void 390 calc_max_num_coll(); 391 392 inline void 393 calc_resize_needed(); 394 395 float m_load; 396 size_type m_size; 397 size_type m_num_col; 398 size_type m_max_col; 399 bool m_resize_needed; 400 }; 401 402#include <ext/pb_ds/detail/resize_policy/cc_hash_max_collision_check_resize_trigger_imp.hpp> 403 404#undef PB_DS_CLASS_T_DEC 405#undef PB_DS_CLASS_C_DEC 406 407#define PB_DS_CLASS_T_DEC template<typename Size_Type> 408#define PB_DS_CLASS_C_DEC hash_exponential_size_policy<Size_Type> 409 410 /// A size policy whose sequence of sizes form an exponential 411 /// sequence (typically powers of 2. 412 template<typename Size_Type = std::size_t> 413 class hash_exponential_size_policy 414 { 415 public: 416 typedef Size_Type size_type; 417 418 /// Default constructor, or onstructor taking a start_size, or 419 /// constructor taking a start size and grow_factor. The policy 420 /// will use the sequence of sizes start_size, start_size* 421 /// grow_factor, start_size* grow_factor^2, ... 422 hash_exponential_size_policy(size_type start_size = 8, 423 size_type grow_factor = 2); 424 425 void 426 swap(PB_DS_CLASS_C_DEC& other); 427 428 protected: 429 size_type 430 get_nearest_larger_size(size_type size) const; 431 432 size_type 433 get_nearest_smaller_size(size_type size) const; 434 435 private: 436 size_type m_start_size; 437 size_type m_grow_factor; 438 }; 439 440#include <ext/pb_ds/detail/resize_policy/hash_exponential_size_policy_imp.hpp> 441 442#undef PB_DS_CLASS_T_DEC 443#undef PB_DS_CLASS_C_DEC 444 445#define PB_DS_CLASS_T_DEC 446#define PB_DS_CLASS_C_DEC hash_prime_size_policy 447 448 /// A size policy whose sequence of sizes form a nearly-exponential 449 /// sequence of primes. 450 class hash_prime_size_policy 451 { 452 public: 453 /// Size type. 454 typedef std::size_t size_type; 455 456 /// Default constructor, or onstructor taking a start_size The 457 /// policy will use the sequence of sizes approximately 458 /// start_size, start_size* 2, start_size* 2^2, ... 459 hash_prime_size_policy(size_type start_size = 8); 460 461 inline void 462 swap(PB_DS_CLASS_C_DEC& other); 463 464 protected: 465 size_type 466 get_nearest_larger_size(size_type size) const; 467 468 size_type 469 get_nearest_smaller_size(size_type size) const; 470 471 private: 472 size_type m_start_size; 473 }; 474 475#include <ext/pb_ds/detail/resize_policy/hash_prime_size_policy_imp.hpp> 476 477#undef PB_DS_CLASS_T_DEC 478#undef PB_DS_CLASS_C_DEC 479 480#define PB_DS_CLASS_T_DEC template<typename Size_Policy, typename Trigger_Policy, bool External_Size_Access, typename Size_Type> 481 482#define PB_DS_CLASS_C_DEC hash_standard_resize_policy<Size_Policy, Trigger_Policy, External_Size_Access, Size_Type> 483 484 /// A resize policy which delegates operations to size and trigger policies. 485 template<typename Size_Policy = hash_exponential_size_policy<>, 486 typename Trigger_Policy = hash_load_check_resize_trigger<>, 487 bool External_Size_Access = false, 488 typename Size_Type = std::size_t> 489 class hash_standard_resize_policy 490 : public Size_Policy, public Trigger_Policy 491 { 492 public: 493 typedef Size_Type size_type; 494 typedef Trigger_Policy trigger_policy; 495 typedef Size_Policy size_policy; 496 497 enum 498 { 499 external_size_access = External_Size_Access 500 }; 501 502 /// Default constructor. 503 hash_standard_resize_policy(); 504 505 /// constructor taking some policies r_size_policy will be copied 506 /// by the Size_Policy object of this object. 507 hash_standard_resize_policy(const Size_Policy& r_size_policy); 508 509 /// constructor taking some policies. r_size_policy will be 510 /// copied by the Size_Policy object of this 511 /// object. r_trigger_policy will be copied by the Trigger_Policy 512 /// object of this object. 513 hash_standard_resize_policy(const Size_Policy& r_size_policy, 514 const Trigger_Policy& r_trigger_policy); 515 516 virtual 517 ~hash_standard_resize_policy(); 518 519 inline void 520 swap(PB_DS_CLASS_C_DEC& other); 521 522 /// Access to the Size_Policy object used. 523 Size_Policy& 524 get_size_policy(); 525 526 /// Const access to the Size_Policy object used. 527 const Size_Policy& 528 get_size_policy() const; 529 530 /// Access to the Trigger_Policy object used. 531 Trigger_Policy& 532 get_trigger_policy(); 533 534 /// Access to the Trigger_Policy object used. 535 const Trigger_Policy& 536 get_trigger_policy() const; 537 538 /// Returns the actual size of the container. 539 inline size_type 540 get_actual_size() const; 541 542 /// Resizes the container to suggested_new_size, a suggested size 543 /// (the actual size will be determined by the Size_Policy 544 /// object). 545 void 546 resize(size_type suggested_new_size); 547 548 protected: 549 inline void 550 notify_insert_search_start(); 551 552 inline void 553 notify_insert_search_collision(); 554 555 inline void 556 notify_insert_search_end(); 557 558 inline void 559 notify_find_search_start(); 560 561 inline void 562 notify_find_search_collision(); 563 564 inline void 565 notify_find_search_end(); 566 567 inline void 568 notify_erase_search_start(); 569 570 inline void 571 notify_erase_search_collision(); 572 573 inline void 574 notify_erase_search_end(); 575 576 inline void 577 notify_inserted(size_type num_e); 578 579 inline void 580 notify_erased(size_type num_e); 581 582 void 583 notify_cleared(); 584 585 void 586 notify_resized(size_type new_size); 587 588 inline bool 589 is_resize_needed() const; 590 591 /// Queries what the new size should be, when the container is 592 /// resized naturally. The current __size of the container is 593 /// size, and the number of used entries within the container is 594 /// num_used_e. 595 size_type 596 get_new_size(size_type size, size_type num_used_e) const; 597 598 private: 599 /// Resizes to new_size. 600 virtual void 601 do_resize(size_type new_size); 602 603 typedef Trigger_Policy trigger_policy_base; 604 605 typedef Size_Policy size_policy_base; 606 607 size_type m_size; 608 }; 609 610#include <ext/pb_ds/detail/resize_policy/hash_standard_resize_policy_imp.hpp> 611 612#undef PB_DS_CLASS_T_DEC 613#undef PB_DS_CLASS_C_DEC 614 615} // namespace __gnu_pbds 616 617#endif 618