1264790Sbapt// -*- C++ -*- 2264790Sbapt 3272955Srodrigc// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4264790Sbapt// 5264790Sbapt// This file is part of the GNU ISO C++ Library. This library is free 6264790Sbapt// software; you can redistribute it and/or modify it under the terms 7264790Sbapt// of the GNU General Public License as published by the Free Software 8264790Sbapt// Foundation; either version 2, or (at your option) any later 9264790Sbapt// version. 10264790Sbapt 11264790Sbapt// This library is distributed in the hope that it will be useful, but 12264790Sbapt// WITHOUT ANY WARRANTY; without even the implied warranty of 13264790Sbapt// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14264790Sbapt// General Public License for more details. 15264790Sbapt 16264790Sbapt// You should have received a copy of the GNU General Public License 17264790Sbapt// along with this library; see the file COPYING. If not, write to 18264790Sbapt// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19264790Sbapt// MA 02111-1307, USA. 20264790Sbapt 21264790Sbapt// As a special exception, you may use this file as part of a free 22264790Sbapt// software library without restriction. Specifically, if other files 23264790Sbapt// instantiate templates or use macros or inline functions from this 24264790Sbapt// file, or you compile this file and link it with other files to 25264790Sbapt// produce an executable, this file does not by itself cause the 26264790Sbapt// resulting executable to be covered by the GNU General Public 27264790Sbapt// License. This exception does not however invalidate any other 28264790Sbapt// reasons why the executable file might be covered by the GNU General 29264790Sbapt// Public License. 30264790Sbapt 31264790Sbapt// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32264790Sbapt 33264790Sbapt// Permission to use, copy, modify, sell, and distribute this software 34264790Sbapt// is hereby granted without fee, provided that the above copyright 35264790Sbapt// notice appears in all copies, and that both that copyright notice 36264790Sbapt// and this permission notice appear in supporting documentation. None 37264790Sbapt// of the above authors, nor IBM Haifa Research Laboratories, make any 38264790Sbapt// representation about the suitability of this software for any 39264790Sbapt// purpose. It is provided "as is" without express or implied 40264790Sbapt// warranty. 41264790Sbapt 42264790Sbapt/** 43264790Sbapt * @file hash_policy.hpp 44264790Sbapt * Contains hash-related policies. 45264790Sbapt */ 46264790Sbapt 47264790Sbapt#ifndef PB_DS_HASH_POLICY_HPP 48264790Sbapt#define PB_DS_HASH_POLICY_HPP 49264790Sbapt 50264790Sbapt#include <algorithm> 51264790Sbapt#include <vector> 52264790Sbapt#include <cmath> 53264790Sbapt#include <ext/pb_ds/exception.hpp> 54264790Sbapt#include <ext/pb_ds/detail/type_utils.hpp> 55264790Sbapt#include <ext/pb_ds/detail/hash_fn/mask_based_range_hashing.hpp> 56264790Sbapt#include <ext/pb_ds/detail/hash_fn/mod_based_range_hashing.hpp> 57264790Sbapt#include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_size_base.hpp> 58264790Sbapt 59264790Sbaptnamespace pb_ds 60264790Sbapt{ 61264790Sbapt // A null hash function, indicating that the combining hash function 62264790Sbapt // is actually a ranged hash function. 63264790Sbapt struct null_hash_fn 64264790Sbapt { }; 65264790Sbapt 66264790Sbapt // A null probe function, indicating that the combining probe 67264790Sbapt // function is actually a ranged probe function. 68264790Sbapt struct null_probe_fn 69264790Sbapt { }; 70264790Sbapt 71264790Sbapt#define PB_DS_CLASS_T_DEC template<typename Size_Type> 72264790Sbapt#define PB_DS_CLASS_C_DEC linear_probe_fn<Size_Type> 73264790Sbapt 74264790Sbapt // A probe sequence policy using fixed increments. 75264790Sbapt template<typename Size_Type = size_t> 76264790Sbapt class linear_probe_fn 77264790Sbapt { 78264790Sbapt public: 79264790Sbapt typedef Size_Type size_type; 80264790Sbapt 81264790Sbapt void 82264790Sbapt swap(PB_DS_CLASS_C_DEC& other); 83264790Sbapt 84264790Sbapt protected: 85264790Sbapt // Returns the i-th offset from the hash value. 86264790Sbapt inline size_type 87264790Sbapt operator()(size_type i) const; 88264790Sbapt }; 89264790Sbapt 90264790Sbapt#include <ext/pb_ds/detail/hash_fn/linear_probe_fn_imp.hpp> 91264790Sbapt 92264790Sbapt#undef PB_DS_CLASS_T_DEC 93264790Sbapt#undef PB_DS_CLASS_C_DEC 94264790Sbapt 95264790Sbapt#define PB_DS_CLASS_T_DEC template<typename Size_Type> 96264790Sbapt#define PB_DS_CLASS_C_DEC quadratic_probe_fn<Size_Type> 97264790Sbapt 98264790Sbapt // A probe sequence policy using square increments. 99264790Sbapt template<typename Size_Type = size_t> 100264790Sbapt class quadratic_probe_fn 101264790Sbapt { 102264790Sbapt public: 103264790Sbapt typedef Size_Type size_type; 104264790Sbapt 105264790Sbapt void 106264790Sbapt swap(PB_DS_CLASS_C_DEC& other); 107264790Sbapt 108264790Sbapt protected: 109264790Sbapt // Returns the i-th offset from the hash value. 110264790Sbapt inline size_type 111264790Sbapt operator()(size_type i) const; 112264790Sbapt }; 113264790Sbapt 114264790Sbapt#include <ext/pb_ds/detail/hash_fn/quadratic_probe_fn_imp.hpp> 115264790Sbapt 116264790Sbapt#undef PB_DS_CLASS_T_DEC 117264790Sbapt#undef PB_DS_CLASS_C_DEC 118264790Sbapt 119264790Sbapt#define PB_DS_CLASS_T_DEC template<typename Size_Type> 120264790Sbapt#define PB_DS_CLASS_C_DEC direct_mask_range_hashing<Size_Type> 121264790Sbapt 122264790Sbapt // A mask range-hashing class (uses a bit-mask). 123264790Sbapt template<typename Size_Type = size_t> 124264790Sbapt class direct_mask_range_hashing 125264790Sbapt : public detail::mask_based_range_hashing<Size_Type> 126264790Sbapt { 127264790Sbapt private: 128264790Sbapt typedef detail::mask_based_range_hashing<Size_Type> mask_based_base; 129264790Sbapt 130264790Sbapt public: 131264790Sbapt typedef Size_Type size_type; 132264790Sbapt 133264790Sbapt void 134264790Sbapt swap(PB_DS_CLASS_C_DEC& other); 135264790Sbapt 136264790Sbapt protected: 137264790Sbapt void 138264790Sbapt notify_resized(size_type size); 139264790Sbapt 140264790Sbapt // Transforms the __hash value hash into a ranged-hash value 141264790Sbapt // (using a bit-mask). 142264790Sbapt inline size_type 143264790Sbapt operator()(size_type hash) const; 144264790Sbapt }; 145264790Sbapt 146264790Sbapt#include <ext/pb_ds/detail/hash_fn/direct_mask_range_hashing_imp.hpp> 147264790Sbapt 148264790Sbapt#undef PB_DS_CLASS_T_DEC 149264790Sbapt#undef PB_DS_CLASS_C_DEC 150264790Sbapt 151264790Sbapt#define PB_DS_CLASS_T_DEC template<typename Size_Type> 152264790Sbapt#define PB_DS_CLASS_C_DEC direct_mod_range_hashing<Size_Type> 153264790Sbapt 154264790Sbapt // A mod range-hashing class (uses the modulo function). 155264790Sbapt template<typename Size_Type = size_t> 156264790Sbapt class direct_mod_range_hashing 157264790Sbapt : public detail::mod_based_range_hashing<Size_Type> 158264790Sbapt { 159264790Sbapt public: 160264790Sbapt typedef Size_Type size_type; 161264790Sbapt 162264790Sbapt void 163264790Sbapt swap(PB_DS_CLASS_C_DEC& other); 164264790Sbapt 165264790Sbapt protected: 166264790Sbapt void 167264790Sbapt notify_resized(size_type size); 168264790Sbapt 169264790Sbapt // Transforms the __hash value hash into a ranged-hash value 170264790Sbapt // (using a modulo operation). 171264790Sbapt inline size_type 172264790Sbapt operator()(size_type hash) const; 173264790Sbapt 174264790Sbapt private: 175264790Sbapt typedef detail::mod_based_range_hashing<size_type> mod_based_base; 176264790Sbapt }; 177264790Sbapt 178264790Sbapt#include <ext/pb_ds/detail/hash_fn/direct_mod_range_hashing_imp.hpp> 179264790Sbapt 180264790Sbapt#undef PB_DS_CLASS_T_DEC 181264790Sbapt#undef PB_DS_CLASS_C_DEC 182264790Sbapt 183264790Sbapt#define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type> 184264790Sbapt#define PB_DS_CLASS_C_DEC hash_load_check_resize_trigger<External_Load_Access, Size_Type> 185264790Sbapt#define PB_DS_SIZE_BASE_C_DEC detail::hash_load_check_resize_trigger_size_base<Size_Type, External_Load_Access> 186264790Sbapt 187264790Sbapt // A resize trigger policy based on a load check. It keeps the 188264790Sbapt // load factor between some load factors load_min and load_max. 189264790Sbapt template<bool External_Load_Access = false, typename Size_Type = size_t> 190264790Sbapt class hash_load_check_resize_trigger : private PB_DS_SIZE_BASE_C_DEC 191264790Sbapt { 192264790Sbapt public: 193264790Sbapt typedef Size_Type size_type; 194264790Sbapt 195264790Sbapt enum 196264790Sbapt { 197264790Sbapt external_load_access = External_Load_Access 198264790Sbapt }; 199264790Sbapt 200264790Sbapt // Default constructor, or constructor taking load_min and 201264790Sbapt // load_max load factors between which this policy will keep the 202264790Sbapt // actual load. 203264790Sbapt hash_load_check_resize_trigger(float load_min = 0.125, 204264790Sbapt float load_max = 0.5); 205264790Sbapt 206264790Sbapt void 207264790Sbapt swap(hash_load_check_resize_trigger& other); 208264790Sbapt 209264790Sbapt virtual 210264790Sbapt ~hash_load_check_resize_trigger(); 211264790Sbapt 212264790Sbapt // Returns a pair of the minimal and maximal loads, respectively. 213264790Sbapt inline std::pair<float, float> 214264790Sbapt get_loads() const; 215264790Sbapt 216264790Sbapt // Sets the loads through a pair of the minimal and maximal 217264790Sbapt // loads, respectively. 218264790Sbapt void 219264790Sbapt set_loads(std::pair<float, float> load_pair); 220264790Sbapt 221264790Sbapt protected: 222264790Sbapt inline void 223264790Sbapt notify_insert_search_start(); 224264790Sbapt 225264790Sbapt inline void 226264790Sbapt notify_insert_search_collision(); 227264790Sbapt 228264790Sbapt inline void 229264790Sbapt notify_insert_search_end(); 230264790Sbapt 231264790Sbapt inline void 232264790Sbapt notify_find_search_start(); 233264790Sbapt 234264790Sbapt inline void 235264790Sbapt notify_find_search_collision(); 236264790Sbapt 237264790Sbapt inline void 238264790Sbapt notify_find_search_end(); 239264790Sbapt 240264790Sbapt inline void 241264790Sbapt notify_erase_search_start(); 242264790Sbapt 243264790Sbapt inline void 244264790Sbapt notify_erase_search_collision(); 245264790Sbapt 246264790Sbapt inline void 247264790Sbapt notify_erase_search_end(); 248264790Sbapt 249264790Sbapt // Notifies an element was inserted. The total number of entries 250264790Sbapt // in the table is num_entries. 251264790Sbapt inline void 252264790Sbapt notify_inserted(size_type num_entries); 253264790Sbapt 254264790Sbapt inline void 255264790Sbapt notify_erased(size_type num_entries); 256264790Sbapt 257264790Sbapt // Notifies the table was cleared. 258264790Sbapt void 259264790Sbapt notify_cleared(); 260264790Sbapt 261264790Sbapt // Notifies the table was resized as a result of this object's 262264790Sbapt // signifying that a resize is needed. 263264790Sbapt void 264264790Sbapt notify_resized(size_type new_size); 265264790Sbapt 266264790Sbapt void 267264790Sbapt notify_externally_resized(size_type new_size); 268264790Sbapt 269264790Sbapt inline bool 270264790Sbapt is_resize_needed() const; 271264790Sbapt 272264790Sbapt inline bool 273264790Sbapt is_grow_needed(size_type size, size_type num_entries) const; 274264790Sbapt 275264790Sbapt private: 276264790Sbapt virtual void 277264790Sbapt do_resize(size_type new_size); 278264790Sbapt 279264790Sbapt typedef PB_DS_SIZE_BASE_C_DEC size_base; 280264790Sbapt 281264790Sbapt#ifdef _GLIBCXX_DEBUG 282264790Sbapt void 283264790Sbapt assert_valid() const; 284264790Sbapt#endif 285264790Sbapt 286264790Sbapt float m_load_min; 287264790Sbapt float m_load_max; 288264790Sbapt size_type m_next_shrink_size; 289272955Srodrigc size_type m_next_grow_size; 290272955Srodrigc bool m_resize_needed; 291272955Srodrigc }; 292272955Srodrigc 293272955Srodrigc#include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp> 294272955Srodrigc 295272955Srodrigc#undef PB_DS_CLASS_T_DEC 296272955Srodrigc#undef PB_DS_CLASS_C_DEC 297272955Srodrigc#undef PB_DS_SIZE_BASE_C_DEC 298272955Srodrigc 299272955Srodrigc#define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type> 300272955Srodrigc#define PB_DS_CLASS_C_DEC cc_hash_max_collision_check_resize_trigger<External_Load_Access, Size_Type> 301272955Srodrigc 302272955Srodrigc // A resize trigger policy based on collision checks. It keeps the 303272955Srodrigc // simulated load factor lower than some given load factor. 304272955Srodrigc template<bool External_Load_Access = false, typename Size_Type = size_t> 305272955Srodrigc class cc_hash_max_collision_check_resize_trigger 306272955Srodrigc { 307272955Srodrigc public: 308272955Srodrigc typedef Size_Type size_type; 309272955Srodrigc 310272955Srodrigc enum 311272955Srodrigc { 312272955Srodrigc external_load_access = External_Load_Access 313272955Srodrigc }; 314272955Srodrigc 315272955Srodrigc // Default constructor, or constructor taking load, a __load 316272955Srodrigc // factor which it will attempt to maintain. 317272955Srodrigc cc_hash_max_collision_check_resize_trigger(float load = 0.5); 318272955Srodrigc 319264790Sbapt void 320264790Sbapt swap(PB_DS_CLASS_C_DEC& other); 321264790Sbapt 322264790Sbapt // Returns the current load. 323264790Sbapt inline float 324264790Sbapt get_load() const; 325264790Sbapt 326264790Sbapt // Sets the load; does not resize the container. 327264790Sbapt void 328264790Sbapt set_load(float load); 329264790Sbapt 330264790Sbapt protected: 331264790Sbapt inline void 332264790Sbapt notify_insert_search_start(); 333264790Sbapt 334264790Sbapt inline void 335264790Sbapt notify_insert_search_collision(); 336264790Sbapt 337264790Sbapt inline void 338264790Sbapt notify_insert_search_end(); 339264790Sbapt 340264790Sbapt inline void 341264790Sbapt notify_find_search_start(); 342264790Sbapt 343264790Sbapt inline void 344264790Sbapt notify_find_search_collision(); 345264790Sbapt 346264790Sbapt inline void 347264790Sbapt notify_find_search_end(); 348264790Sbapt 349264790Sbapt inline void 350264790Sbapt notify_erase_search_start(); 351264790Sbapt 352264790Sbapt inline void 353264790Sbapt notify_erase_search_collision(); 354264790Sbapt 355264790Sbapt inline void 356264790Sbapt notify_erase_search_end(); 357264790Sbapt 358264790Sbapt inline void 359264790Sbapt notify_inserted(size_type num_entries); 360264790Sbapt 361264790Sbapt inline void 362264790Sbapt notify_erased(size_type num_entries); 363264790Sbapt 364264790Sbapt void 365264790Sbapt notify_cleared(); 366264790Sbapt 367264790Sbapt // Notifies the table was resized as a result of this object's 368264790Sbapt // signifying that a resize is needed. 369264790Sbapt void 370264790Sbapt notify_resized(size_type new_size); 371264790Sbapt 372264790Sbapt void 373264790Sbapt notify_externally_resized(size_type new_size); 374264790Sbapt 375264790Sbapt inline bool 376264790Sbapt is_resize_needed() const; 377264790Sbapt 378264790Sbapt inline bool 379264790Sbapt is_grow_needed(size_type size, size_type num_entries) const; 380264790Sbapt 381264790Sbapt private: 382264790Sbapt void 383264790Sbapt calc_max_num_coll(); 384264790Sbapt 385264790Sbapt inline void 386264790Sbapt calc_resize_needed(); 387264790Sbapt 388264790Sbapt float m_load; 389264790Sbapt size_type m_size; 390264790Sbapt size_type m_num_col; 391264790Sbapt size_type m_max_col; 392264790Sbapt bool m_resize_needed; 393264790Sbapt }; 394264790Sbapt 395264790Sbapt#include <ext/pb_ds/detail/resize_policy/cc_hash_max_collision_check_resize_trigger_imp.hpp> 396264790Sbapt 397264790Sbapt#undef PB_DS_CLASS_T_DEC 398264790Sbapt#undef PB_DS_CLASS_C_DEC 399264790Sbapt 400264790Sbapt#define PB_DS_CLASS_T_DEC template<typename Size_Type> 401264790Sbapt#define PB_DS_CLASS_C_DEC hash_exponential_size_policy<Size_Type> 402264790Sbapt 403264790Sbapt // A size policy whose sequence of sizes form an exponential 404264790Sbapt // sequence (typically powers of 2. 405264790Sbapt template<typename Size_Type = size_t> 406264790Sbapt class hash_exponential_size_policy 407264790Sbapt { 408264790Sbapt public: 409264790Sbapt typedef Size_Type size_type; 410264790Sbapt 411264790Sbapt // Default constructor, or onstructor taking a start_size, or 412264790Sbapt // constructor taking a start size and grow_factor. The policy 413264790Sbapt // will use the sequence of sizes start_size, start_size* 414264790Sbapt // grow_factor, start_size* grow_factor^2, ... 415264790Sbapt hash_exponential_size_policy(size_type start_size = 8, 416264790Sbapt size_type grow_factor = 2); 417264790Sbapt 418264790Sbapt void 419264790Sbapt swap(PB_DS_CLASS_C_DEC& other); 420264790Sbapt 421264790Sbapt protected: 422264790Sbapt size_type 423264790Sbapt get_nearest_larger_size(size_type size) const; 424264790Sbapt 425264790Sbapt size_type 426264790Sbapt get_nearest_smaller_size(size_type size) const; 427264790Sbapt 428264790Sbapt private: 429264790Sbapt size_type m_start_size; 430264790Sbapt size_type m_grow_factor; 431264790Sbapt }; 432264790Sbapt 433264790Sbapt#include <ext/pb_ds/detail/resize_policy/hash_exponential_size_policy_imp.hpp> 434264790Sbapt 435264790Sbapt#undef PB_DS_CLASS_T_DEC 436264790Sbapt#undef PB_DS_CLASS_C_DEC 437264790Sbapt 438264790Sbapt#define PB_DS_CLASS_T_DEC 439264790Sbapt#define PB_DS_CLASS_C_DEC hash_prime_size_policy 440264790Sbapt 441264790Sbapt // A size policy whose sequence of sizes form a nearly-exponential 442264790Sbapt // sequence of primes. 443264790Sbapt class hash_prime_size_policy 444264790Sbapt { 445264790Sbapt public: 446264790Sbapt // Size type. 447264790Sbapt typedef size_t size_type; 448264790Sbapt 449264790Sbapt // Default constructor, or onstructor taking a start_size The 450264790Sbapt // policy will use the sequence of sizes approximately 451264790Sbapt // start_size, start_size* 2, start_size* 2^2, ... 452264790Sbapt hash_prime_size_policy(size_type start_size = 8); 453264790Sbapt 454264790Sbapt inline void 455264790Sbapt swap(PB_DS_CLASS_C_DEC& other); 456264790Sbapt 457264790Sbapt protected: 458264790Sbapt size_type 459264790Sbapt get_nearest_larger_size(size_type size) const; 460264790Sbapt 461264790Sbapt size_type 462264790Sbapt get_nearest_smaller_size(size_type size) const; 463264790Sbapt 464264790Sbapt private: 465264790Sbapt size_type m_start_size; 466264790Sbapt }; 467264790Sbapt 468264790Sbapt#include <ext/pb_ds/detail/resize_policy/hash_prime_size_policy_imp.hpp> 469264790Sbapt 470264790Sbapt#undef PB_DS_CLASS_T_DEC 471264790Sbapt#undef PB_DS_CLASS_C_DEC 472264790Sbapt 473264790Sbapt#define PB_DS_CLASS_T_DEC template<typename Size_Policy, typename Trigger_Policy, bool External_Size_Access, typename Size_Type> 474264790Sbapt 475264790Sbapt#define PB_DS_CLASS_C_DEC hash_standard_resize_policy<Size_Policy, Trigger_Policy, External_Size_Access, Size_Type> 476264790Sbapt 477264790Sbapt // A resize policy which delegates operations to size and trigger policies. 478264790Sbapt template<typename Size_Policy = hash_exponential_size_policy<>, 479264790Sbapt typename Trigger_Policy = hash_load_check_resize_trigger<>, 480264790Sbapt bool External_Size_Access = false, 481264790Sbapt typename Size_Type = size_t> 482264790Sbapt class hash_standard_resize_policy 483264790Sbapt : public Size_Policy, public Trigger_Policy 484264790Sbapt { 485264790Sbapt public: 486264790Sbapt typedef Size_Type size_type; 487264790Sbapt typedef Trigger_Policy trigger_policy; 488264790Sbapt typedef Size_Policy size_policy; 489264790Sbapt 490264790Sbapt enum 491264790Sbapt { 492264790Sbapt external_size_access = External_Size_Access 493264790Sbapt }; 494264790Sbapt 495264790Sbapt // Default constructor. 496264790Sbapt hash_standard_resize_policy(); 497264790Sbapt 498264790Sbapt // constructor taking some policies r_size_policy will be copied 499264790Sbapt // by the Size_Policy object of this object. 500264790Sbapt hash_standard_resize_policy(const Size_Policy& r_size_policy); 501264790Sbapt 502264790Sbapt // constructor taking some policies. r_size_policy will be 503264790Sbapt // copied by the Size_Policy object of this 504264790Sbapt // object. r_trigger_policy will be copied by the Trigger_Policy 505264790Sbapt // object of this object. 506264790Sbapt hash_standard_resize_policy(const Size_Policy& r_size_policy, 507264790Sbapt const Trigger_Policy& r_trigger_policy); 508264790Sbapt 509264790Sbapt virtual 510264790Sbapt ~hash_standard_resize_policy(); 511264790Sbapt 512264790Sbapt inline void 513264790Sbapt swap(PB_DS_CLASS_C_DEC& other); 514264790Sbapt 515264790Sbapt // Access to the Size_Policy object used. 516264790Sbapt Size_Policy& 517264790Sbapt get_size_policy(); 518264790Sbapt 519264790Sbapt // Const access to the Size_Policy object used. 520264790Sbapt const Size_Policy& 521264790Sbapt get_size_policy() const; 522264790Sbapt 523264790Sbapt // Access to the Trigger_Policy object used. 524264790Sbapt Trigger_Policy& 525264790Sbapt get_trigger_policy(); 526264790Sbapt 527264790Sbapt // Access to the Trigger_Policy object used. 528264790Sbapt const Trigger_Policy& 529272955Srodrigc get_trigger_policy() const; 530264790Sbapt 531264790Sbapt // Returns the actual size of the container. 532264790Sbapt inline size_type 533264790Sbapt get_actual_size() const; 534264790Sbapt 535264790Sbapt // Resizes the container to suggested_new_size, a suggested size 536264790Sbapt // (the actual size will be determined by the Size_Policy 537264790Sbapt // object). 538272955Srodrigc void 539264790Sbapt resize(size_type suggested_new_size); 540264790Sbapt 541272955Srodrigc protected: 542272955Srodrigc inline void 543264790Sbapt notify_insert_search_start(); 544264790Sbapt 545264790Sbapt inline void 546264790Sbapt notify_insert_search_collision(); 547264790Sbapt 548264790Sbapt inline void 549264790Sbapt notify_insert_search_end(); 550264790Sbapt 551264790Sbapt inline void 552264790Sbapt notify_find_search_start(); 553264790Sbapt 554264790Sbapt inline void 555264790Sbapt notify_find_search_collision(); 556264790Sbapt 557264790Sbapt inline void 558264790Sbapt notify_find_search_end(); 559264790Sbapt 560264790Sbapt inline void 561264790Sbapt notify_erase_search_start(); 562264790Sbapt 563264790Sbapt inline void 564264790Sbapt notify_erase_search_collision(); 565264790Sbapt 566264790Sbapt inline void 567264790Sbapt notify_erase_search_end(); 568264790Sbapt 569264790Sbapt inline void 570264790Sbapt notify_inserted(size_type num_e); 571264790Sbapt 572264790Sbapt inline void 573264790Sbapt notify_erased(size_type num_e); 574264790Sbapt 575264790Sbapt void 576264790Sbapt notify_cleared(); 577264790Sbapt 578264790Sbapt void 579264790Sbapt notify_resized(size_type new_size); 580264790Sbapt 581264790Sbapt inline bool 582264790Sbapt is_resize_needed() const; 583264790Sbapt 584264790Sbapt // Queries what the new size should be, when the container is 585264790Sbapt // resized naturally. The current __size of the container is 586264790Sbapt // size, and the number of used entries within the container is 587264790Sbapt // num_used_e. 588264790Sbapt size_type 589264790Sbapt get_new_size(size_type size, size_type num_used_e) const; 590264790Sbapt 591264790Sbapt private: 592264790Sbapt // Resizes to new_size. 593264790Sbapt virtual void 594264790Sbapt do_resize(size_type new_size); 595264790Sbapt 596264790Sbapt typedef Trigger_Policy trigger_policy_base; 597264790Sbapt 598264790Sbapt typedef Size_Policy size_policy_base; 599264790Sbapt 600264790Sbapt size_type m_size; 601264790Sbapt }; 602264790Sbapt 603264790Sbapt#include <ext/pb_ds/detail/resize_policy/hash_standard_resize_policy_imp.hpp> 604264790Sbapt 605264790Sbapt#undef PB_DS_CLASS_T_DEC 606264790Sbapt#undef PB_DS_CLASS_C_DEC 607264790Sbapt 608264790Sbapt} // namespace pb_ds 609264790Sbapt 610264790Sbapt#endif 611264790Sbapt