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