1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file hash_policy.hpp 44169691Skan * Contains hash-related policies. 45169691Skan */ 46169691Skan 47169691Skan#ifndef PB_DS_HASH_POLICY_HPP 48169691Skan#define PB_DS_HASH_POLICY_HPP 49169691Skan 50169691Skan#include <algorithm> 51169691Skan#include <vector> 52169691Skan#include <cmath> 53169691Skan#include <ext/pb_ds/exception.hpp> 54169691Skan#include <ext/pb_ds/detail/type_utils.hpp> 55169691Skan#include <ext/pb_ds/detail/hash_fn/mask_based_range_hashing.hpp> 56169691Skan#include <ext/pb_ds/detail/hash_fn/mod_based_range_hashing.hpp> 57169691Skan#include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_size_base.hpp> 58169691Skan 59169691Skannamespace pb_ds 60169691Skan{ 61169691Skan // A null hash function, indicating that the combining hash function 62169691Skan // is actually a ranged hash function. 63169691Skan struct null_hash_fn 64169691Skan { }; 65169691Skan 66169691Skan // A null probe function, indicating that the combining probe 67169691Skan // function is actually a ranged probe function. 68169691Skan struct null_probe_fn 69169691Skan { }; 70169691Skan 71169691Skan#define PB_DS_CLASS_T_DEC template<typename Size_Type> 72169691Skan#define PB_DS_CLASS_C_DEC linear_probe_fn<Size_Type> 73169691Skan 74169691Skan // A probe sequence policy using fixed increments. 75169691Skan template<typename Size_Type = size_t> 76169691Skan class linear_probe_fn 77169691Skan { 78169691Skan public: 79169691Skan typedef Size_Type size_type; 80169691Skan 81169691Skan void 82169691Skan swap(PB_DS_CLASS_C_DEC& other); 83169691Skan 84169691Skan protected: 85169691Skan // Returns the i-th offset from the hash value. 86169691Skan inline size_type 87169691Skan operator()(size_type i) const; 88169691Skan }; 89169691Skan 90169691Skan#include <ext/pb_ds/detail/hash_fn/linear_probe_fn_imp.hpp> 91169691Skan 92169691Skan#undef PB_DS_CLASS_T_DEC 93169691Skan#undef PB_DS_CLASS_C_DEC 94169691Skan 95169691Skan#define PB_DS_CLASS_T_DEC template<typename Size_Type> 96169691Skan#define PB_DS_CLASS_C_DEC quadratic_probe_fn<Size_Type> 97169691Skan 98169691Skan // A probe sequence policy using square increments. 99169691Skan template<typename Size_Type = size_t> 100169691Skan class quadratic_probe_fn 101169691Skan { 102169691Skan public: 103169691Skan typedef Size_Type size_type; 104169691Skan 105169691Skan void 106169691Skan swap(PB_DS_CLASS_C_DEC& other); 107169691Skan 108169691Skan protected: 109169691Skan // Returns the i-th offset from the hash value. 110169691Skan inline size_type 111169691Skan operator()(size_type i) const; 112169691Skan }; 113169691Skan 114169691Skan#include <ext/pb_ds/detail/hash_fn/quadratic_probe_fn_imp.hpp> 115169691Skan 116169691Skan#undef PB_DS_CLASS_T_DEC 117169691Skan#undef PB_DS_CLASS_C_DEC 118169691Skan 119169691Skan#define PB_DS_CLASS_T_DEC template<typename Size_Type> 120169691Skan#define PB_DS_CLASS_C_DEC direct_mask_range_hashing<Size_Type> 121169691Skan 122169691Skan // A mask range-hashing class (uses a bit-mask). 123169691Skan template<typename Size_Type = size_t> 124169691Skan class direct_mask_range_hashing 125169691Skan : public detail::mask_based_range_hashing<Size_Type> 126169691Skan { 127169691Skan private: 128169691Skan typedef detail::mask_based_range_hashing<Size_Type> mask_based_base; 129169691Skan 130169691Skan public: 131169691Skan typedef Size_Type size_type; 132169691Skan 133169691Skan void 134169691Skan swap(PB_DS_CLASS_C_DEC& other); 135169691Skan 136169691Skan protected: 137169691Skan void 138169691Skan notify_resized(size_type size); 139169691Skan 140169691Skan // Transforms the __hash value hash into a ranged-hash value 141169691Skan // (using a bit-mask). 142169691Skan inline size_type 143169691Skan operator()(size_type hash) const; 144169691Skan }; 145169691Skan 146169691Skan#include <ext/pb_ds/detail/hash_fn/direct_mask_range_hashing_imp.hpp> 147169691Skan 148169691Skan#undef PB_DS_CLASS_T_DEC 149169691Skan#undef PB_DS_CLASS_C_DEC 150169691Skan 151169691Skan#define PB_DS_CLASS_T_DEC template<typename Size_Type> 152169691Skan#define PB_DS_CLASS_C_DEC direct_mod_range_hashing<Size_Type> 153169691Skan 154169691Skan // A mod range-hashing class (uses the modulo function). 155169691Skan template<typename Size_Type = size_t> 156169691Skan class direct_mod_range_hashing 157169691Skan : public detail::mod_based_range_hashing<Size_Type> 158169691Skan { 159169691Skan public: 160169691Skan typedef Size_Type size_type; 161169691Skan 162169691Skan void 163169691Skan swap(PB_DS_CLASS_C_DEC& other); 164169691Skan 165169691Skan protected: 166169691Skan void 167169691Skan notify_resized(size_type size); 168169691Skan 169169691Skan // Transforms the __hash value hash into a ranged-hash value 170169691Skan // (using a modulo operation). 171169691Skan inline size_type 172169691Skan operator()(size_type hash) const; 173169691Skan 174169691Skan private: 175169691Skan typedef detail::mod_based_range_hashing<size_type> mod_based_base; 176169691Skan }; 177169691Skan 178169691Skan#include <ext/pb_ds/detail/hash_fn/direct_mod_range_hashing_imp.hpp> 179169691Skan 180169691Skan#undef PB_DS_CLASS_T_DEC 181169691Skan#undef PB_DS_CLASS_C_DEC 182169691Skan 183169691Skan#define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type> 184169691Skan#define PB_DS_CLASS_C_DEC hash_load_check_resize_trigger<External_Load_Access, Size_Type> 185169691Skan#define PB_DS_SIZE_BASE_C_DEC detail::hash_load_check_resize_trigger_size_base<Size_Type, External_Load_Access> 186169691Skan 187169691Skan // A resize trigger policy based on a load check. It keeps the 188169691Skan // load factor between some load factors load_min and load_max. 189169691Skan template<bool External_Load_Access = false, typename Size_Type = size_t> 190169691Skan class hash_load_check_resize_trigger : private PB_DS_SIZE_BASE_C_DEC 191169691Skan { 192169691Skan public: 193169691Skan typedef Size_Type size_type; 194169691Skan 195169691Skan enum 196169691Skan { 197169691Skan external_load_access = External_Load_Access 198169691Skan }; 199169691Skan 200169691Skan // Default constructor, or constructor taking load_min and 201169691Skan // load_max load factors between which this policy will keep the 202169691Skan // actual load. 203169691Skan hash_load_check_resize_trigger(float load_min = 0.125, 204169691Skan float load_max = 0.5); 205169691Skan 206169691Skan void 207169691Skan swap(hash_load_check_resize_trigger& other); 208169691Skan 209169691Skan virtual 210169691Skan ~hash_load_check_resize_trigger(); 211169691Skan 212169691Skan // Returns a pair of the minimal and maximal loads, respectively. 213169691Skan inline std::pair<float, float> 214169691Skan get_loads() const; 215169691Skan 216169691Skan // Sets the loads through a pair of the minimal and maximal 217169691Skan // loads, respectively. 218169691Skan void 219169691Skan set_loads(std::pair<float, float> load_pair); 220169691Skan 221169691Skan protected: 222169691Skan inline void 223169691Skan notify_insert_search_start(); 224169691Skan 225169691Skan inline void 226169691Skan notify_insert_search_collision(); 227169691Skan 228169691Skan inline void 229169691Skan notify_insert_search_end(); 230169691Skan 231169691Skan inline void 232169691Skan notify_find_search_start(); 233169691Skan 234169691Skan inline void 235169691Skan notify_find_search_collision(); 236169691Skan 237169691Skan inline void 238169691Skan notify_find_search_end(); 239169691Skan 240169691Skan inline void 241169691Skan notify_erase_search_start(); 242169691Skan 243169691Skan inline void 244169691Skan notify_erase_search_collision(); 245169691Skan 246169691Skan inline void 247169691Skan notify_erase_search_end(); 248169691Skan 249169691Skan // Notifies an element was inserted. The total number of entries 250169691Skan // in the table is num_entries. 251169691Skan inline void 252169691Skan notify_inserted(size_type num_entries); 253169691Skan 254169691Skan inline void 255169691Skan notify_erased(size_type num_entries); 256169691Skan 257169691Skan // Notifies the table was cleared. 258169691Skan void 259169691Skan notify_cleared(); 260169691Skan 261169691Skan // Notifies the table was resized as a result of this object's 262169691Skan // signifying that a resize is needed. 263169691Skan void 264169691Skan notify_resized(size_type new_size); 265169691Skan 266169691Skan void 267169691Skan notify_externally_resized(size_type new_size); 268169691Skan 269169691Skan inline bool 270169691Skan is_resize_needed() const; 271169691Skan 272169691Skan inline bool 273169691Skan is_grow_needed(size_type size, size_type num_entries) const; 274169691Skan 275169691Skan private: 276169691Skan virtual void 277169691Skan do_resize(size_type new_size); 278169691Skan 279169691Skan typedef PB_DS_SIZE_BASE_C_DEC size_base; 280169691Skan 281169691Skan#ifdef _GLIBCXX_DEBUG 282169691Skan void 283169691Skan assert_valid() const; 284169691Skan#endif 285169691Skan 286169691Skan float m_load_min; 287169691Skan float m_load_max; 288169691Skan size_type m_next_shrink_size; 289169691Skan size_type m_next_grow_size; 290169691Skan bool m_resize_needed; 291169691Skan }; 292169691Skan 293169691Skan#include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp> 294169691Skan 295169691Skan#undef PB_DS_CLASS_T_DEC 296169691Skan#undef PB_DS_CLASS_C_DEC 297169691Skan#undef PB_DS_SIZE_BASE_C_DEC 298169691Skan 299169691Skan#define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type> 300169691Skan#define PB_DS_CLASS_C_DEC cc_hash_max_collision_check_resize_trigger<External_Load_Access, Size_Type> 301169691Skan 302169691Skan // A resize trigger policy based on collision checks. It keeps the 303169691Skan // simulated load factor lower than some given load factor. 304169691Skan template<bool External_Load_Access = false, typename Size_Type = size_t> 305169691Skan class cc_hash_max_collision_check_resize_trigger 306169691Skan { 307169691Skan public: 308169691Skan typedef Size_Type size_type; 309169691Skan 310169691Skan enum 311169691Skan { 312169691Skan external_load_access = External_Load_Access 313169691Skan }; 314169691Skan 315169691Skan // Default constructor, or constructor taking load, a __load 316169691Skan // factor which it will attempt to maintain. 317169691Skan cc_hash_max_collision_check_resize_trigger(float load = 0.5); 318169691Skan 319169691Skan void 320169691Skan swap(PB_DS_CLASS_C_DEC& other); 321169691Skan 322169691Skan // Returns the current load. 323169691Skan inline float 324169691Skan get_load() const; 325169691Skan 326169691Skan // Sets the load; does not resize the container. 327169691Skan void 328169691Skan set_load(float load); 329169691Skan 330169691Skan protected: 331169691Skan inline void 332169691Skan notify_insert_search_start(); 333169691Skan 334169691Skan inline void 335169691Skan notify_insert_search_collision(); 336169691Skan 337169691Skan inline void 338169691Skan notify_insert_search_end(); 339169691Skan 340169691Skan inline void 341169691Skan notify_find_search_start(); 342169691Skan 343169691Skan inline void 344169691Skan notify_find_search_collision(); 345169691Skan 346169691Skan inline void 347169691Skan notify_find_search_end(); 348169691Skan 349169691Skan inline void 350169691Skan notify_erase_search_start(); 351169691Skan 352169691Skan inline void 353169691Skan notify_erase_search_collision(); 354169691Skan 355169691Skan inline void 356169691Skan notify_erase_search_end(); 357169691Skan 358169691Skan inline void 359169691Skan notify_inserted(size_type num_entries); 360169691Skan 361169691Skan inline void 362169691Skan notify_erased(size_type num_entries); 363169691Skan 364169691Skan void 365169691Skan notify_cleared(); 366169691Skan 367169691Skan // Notifies the table was resized as a result of this object's 368169691Skan // signifying that a resize is needed. 369169691Skan void 370169691Skan notify_resized(size_type new_size); 371169691Skan 372169691Skan void 373169691Skan notify_externally_resized(size_type new_size); 374169691Skan 375169691Skan inline bool 376169691Skan is_resize_needed() const; 377169691Skan 378169691Skan inline bool 379169691Skan is_grow_needed(size_type size, size_type num_entries) const; 380169691Skan 381169691Skan private: 382169691Skan void 383169691Skan calc_max_num_coll(); 384169691Skan 385169691Skan inline void 386169691Skan calc_resize_needed(); 387169691Skan 388169691Skan float m_load; 389169691Skan size_type m_size; 390169691Skan size_type m_num_col; 391169691Skan size_type m_max_col; 392169691Skan bool m_resize_needed; 393169691Skan }; 394169691Skan 395169691Skan#include <ext/pb_ds/detail/resize_policy/cc_hash_max_collision_check_resize_trigger_imp.hpp> 396169691Skan 397169691Skan#undef PB_DS_CLASS_T_DEC 398169691Skan#undef PB_DS_CLASS_C_DEC 399169691Skan 400169691Skan#define PB_DS_CLASS_T_DEC template<typename Size_Type> 401169691Skan#define PB_DS_CLASS_C_DEC hash_exponential_size_policy<Size_Type> 402169691Skan 403169691Skan // A size policy whose sequence of sizes form an exponential 404169691Skan // sequence (typically powers of 2. 405169691Skan template<typename Size_Type = size_t> 406169691Skan class hash_exponential_size_policy 407169691Skan { 408169691Skan public: 409169691Skan typedef Size_Type size_type; 410169691Skan 411169691Skan // Default constructor, or onstructor taking a start_size, or 412169691Skan // constructor taking a start size and grow_factor. The policy 413169691Skan // will use the sequence of sizes start_size, start_size* 414169691Skan // grow_factor, start_size* grow_factor^2, ... 415169691Skan hash_exponential_size_policy(size_type start_size = 8, 416169691Skan size_type grow_factor = 2); 417169691Skan 418169691Skan void 419169691Skan swap(PB_DS_CLASS_C_DEC& other); 420169691Skan 421169691Skan protected: 422169691Skan size_type 423169691Skan get_nearest_larger_size(size_type size) const; 424169691Skan 425169691Skan size_type 426169691Skan get_nearest_smaller_size(size_type size) const; 427169691Skan 428169691Skan private: 429169691Skan size_type m_start_size; 430169691Skan size_type m_grow_factor; 431169691Skan }; 432169691Skan 433169691Skan#include <ext/pb_ds/detail/resize_policy/hash_exponential_size_policy_imp.hpp> 434169691Skan 435169691Skan#undef PB_DS_CLASS_T_DEC 436169691Skan#undef PB_DS_CLASS_C_DEC 437169691Skan 438169691Skan#define PB_DS_CLASS_T_DEC 439169691Skan#define PB_DS_CLASS_C_DEC hash_prime_size_policy 440169691Skan 441169691Skan // A size policy whose sequence of sizes form a nearly-exponential 442169691Skan // sequence of primes. 443169691Skan class hash_prime_size_policy 444169691Skan { 445169691Skan public: 446169691Skan // Size type. 447169691Skan typedef size_t size_type; 448169691Skan 449169691Skan // Default constructor, or onstructor taking a start_size The 450169691Skan // policy will use the sequence of sizes approximately 451169691Skan // start_size, start_size* 2, start_size* 2^2, ... 452169691Skan hash_prime_size_policy(size_type start_size = 8); 453169691Skan 454169691Skan inline void 455169691Skan swap(PB_DS_CLASS_C_DEC& other); 456169691Skan 457169691Skan protected: 458169691Skan size_type 459169691Skan get_nearest_larger_size(size_type size) const; 460169691Skan 461169691Skan size_type 462169691Skan get_nearest_smaller_size(size_type size) const; 463169691Skan 464169691Skan private: 465169691Skan size_type m_start_size; 466169691Skan }; 467169691Skan 468169691Skan#include <ext/pb_ds/detail/resize_policy/hash_prime_size_policy_imp.hpp> 469169691Skan 470169691Skan#undef PB_DS_CLASS_T_DEC 471169691Skan#undef PB_DS_CLASS_C_DEC 472169691Skan 473169691Skan#define PB_DS_CLASS_T_DEC template<typename Size_Policy, typename Trigger_Policy, bool External_Size_Access, typename Size_Type> 474169691Skan 475169691Skan#define PB_DS_CLASS_C_DEC hash_standard_resize_policy<Size_Policy, Trigger_Policy, External_Size_Access, Size_Type> 476169691Skan 477169691Skan // A resize policy which delegates operations to size and trigger policies. 478169691Skan template<typename Size_Policy = hash_exponential_size_policy<>, 479169691Skan typename Trigger_Policy = hash_load_check_resize_trigger<>, 480169691Skan bool External_Size_Access = false, 481169691Skan typename Size_Type = size_t> 482169691Skan class hash_standard_resize_policy 483169691Skan : public Size_Policy, public Trigger_Policy 484169691Skan { 485169691Skan public: 486169691Skan typedef Size_Type size_type; 487169691Skan typedef Trigger_Policy trigger_policy; 488169691Skan typedef Size_Policy size_policy; 489169691Skan 490169691Skan enum 491169691Skan { 492169691Skan external_size_access = External_Size_Access 493169691Skan }; 494169691Skan 495169691Skan // Default constructor. 496169691Skan hash_standard_resize_policy(); 497169691Skan 498169691Skan // constructor taking some policies r_size_policy will be copied 499169691Skan // by the Size_Policy object of this object. 500169691Skan hash_standard_resize_policy(const Size_Policy& r_size_policy); 501169691Skan 502169691Skan // constructor taking some policies. r_size_policy will be 503169691Skan // copied by the Size_Policy object of this 504169691Skan // object. r_trigger_policy will be copied by the Trigger_Policy 505169691Skan // object of this object. 506169691Skan hash_standard_resize_policy(const Size_Policy& r_size_policy, 507169691Skan const Trigger_Policy& r_trigger_policy); 508169691Skan 509169691Skan virtual 510169691Skan ~hash_standard_resize_policy(); 511169691Skan 512169691Skan inline void 513169691Skan swap(PB_DS_CLASS_C_DEC& other); 514169691Skan 515169691Skan // Access to the Size_Policy object used. 516169691Skan Size_Policy& 517169691Skan get_size_policy(); 518169691Skan 519169691Skan // Const access to the Size_Policy object used. 520169691Skan const Size_Policy& 521169691Skan get_size_policy() const; 522169691Skan 523169691Skan // Access to the Trigger_Policy object used. 524169691Skan Trigger_Policy& 525169691Skan get_trigger_policy(); 526169691Skan 527169691Skan // Access to the Trigger_Policy object used. 528169691Skan const Trigger_Policy& 529169691Skan get_trigger_policy() const; 530169691Skan 531169691Skan // Returns the actual size of the container. 532169691Skan inline size_type 533169691Skan get_actual_size() const; 534169691Skan 535169691Skan // Resizes the container to suggested_new_size, a suggested size 536169691Skan // (the actual size will be determined by the Size_Policy 537169691Skan // object). 538169691Skan void 539169691Skan resize(size_type suggested_new_size); 540169691Skan 541169691Skan protected: 542169691Skan inline void 543169691Skan notify_insert_search_start(); 544169691Skan 545169691Skan inline void 546169691Skan notify_insert_search_collision(); 547169691Skan 548169691Skan inline void 549169691Skan notify_insert_search_end(); 550169691Skan 551169691Skan inline void 552169691Skan notify_find_search_start(); 553169691Skan 554169691Skan inline void 555169691Skan notify_find_search_collision(); 556169691Skan 557169691Skan inline void 558169691Skan notify_find_search_end(); 559169691Skan 560169691Skan inline void 561169691Skan notify_erase_search_start(); 562169691Skan 563169691Skan inline void 564169691Skan notify_erase_search_collision(); 565169691Skan 566169691Skan inline void 567169691Skan notify_erase_search_end(); 568169691Skan 569169691Skan inline void 570169691Skan notify_inserted(size_type num_e); 571169691Skan 572169691Skan inline void 573169691Skan notify_erased(size_type num_e); 574169691Skan 575169691Skan void 576169691Skan notify_cleared(); 577169691Skan 578169691Skan void 579169691Skan notify_resized(size_type new_size); 580169691Skan 581169691Skan inline bool 582169691Skan is_resize_needed() const; 583169691Skan 584169691Skan // Queries what the new size should be, when the container is 585169691Skan // resized naturally. The current __size of the container is 586169691Skan // size, and the number of used entries within the container is 587169691Skan // num_used_e. 588169691Skan size_type 589169691Skan get_new_size(size_type size, size_type num_used_e) const; 590169691Skan 591169691Skan private: 592169691Skan // Resizes to new_size. 593169691Skan virtual void 594169691Skan do_resize(size_type new_size); 595169691Skan 596169691Skan typedef Trigger_Policy trigger_policy_base; 597169691Skan 598169691Skan typedef Size_Policy size_policy_base; 599169691Skan 600169691Skan size_type m_size; 601169691Skan }; 602169691Skan 603169691Skan#include <ext/pb_ds/detail/resize_policy/hash_standard_resize_policy_imp.hpp> 604169691Skan 605169691Skan#undef PB_DS_CLASS_T_DEC 606169691Skan#undef PB_DS_CLASS_C_DEC 607169691Skan 608169691Skan} // namespace pb_ds 609169691Skan 610169691Skan#endif 611