[thirdparty/gcc.git] / libstdc++-v3 / include / ext / pb_ds / hash_policy.hpp

// -*- C++ -*-

// Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file hash_policy.hpp
 * Contains hash-related policies.
 */

#ifndef PB_DS_HASH_POLICY_HPP
#define PB_DS_HASH_POLICY_HPP

#include <bits/c++config.h>
#include <algorithm>
#include <vector>
#include <cmath>
#include <ext/pb_ds/exception.hpp>
#include <ext/pb_ds/detail/type_utils.hpp>
#include <ext/pb_ds/detail/hash_fn/mask_based_range_hashing.hpp>
#include <ext/pb_ds/detail/hash_fn/mod_based_range_hashing.hpp>
#include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_size_base.hpp>

namespace __gnu_pbds
{
#define PB_DS_CLASS_T_DEC template<typename Size_Type>
#define PB_DS_CLASS_C_DEC linear_probe_fn<Size_Type>

  /// A probe sequence policy using fixed increments.
  template<typename Size_Type = std::size_t>
  class linear_probe_fn
  {
  public:
    typedef Size_Type size_type;

    void
    swap(PB_DS_CLASS_C_DEC& other);

  protected:
    // Returns the i-th offset from the hash value.
    inline size_type
    operator()(size_type i) const;
  };

#include <ext/pb_ds/detail/hash_fn/linear_probe_fn_imp.hpp>

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

#define PB_DS_CLASS_T_DEC template<typename Size_Type>
#define PB_DS_CLASS_C_DEC quadratic_probe_fn<Size_Type>

  /// A probe sequence policy using square increments.
  template<typename Size_Type = std::size_t>
  class quadratic_probe_fn
  {
  public:
    typedef Size_Type size_type;

    void
    swap(PB_DS_CLASS_C_DEC& other);

  protected:
    // Returns the i-th offset from the hash value.
    inline size_type
    operator()(size_type i) const;
  };

#include <ext/pb_ds/detail/hash_fn/quadratic_probe_fn_imp.hpp>

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

#define PB_DS_CLASS_T_DEC template<typename Size_Type>
#define PB_DS_CLASS_C_DEC direct_mask_range_hashing<Size_Type>

  /// A mask range-hashing class (uses a bit-mask).
  template<typename Size_Type = std::size_t>
  class direct_mask_range_hashing 
  : public detail::mask_based_range_hashing<Size_Type>
  {
  private:
    typedef detail::mask_based_range_hashing<Size_Type> mask_based_base;

  public:
    typedef Size_Type size_type;

    void
    swap(PB_DS_CLASS_C_DEC& other);

  protected:
    void
    notify_resized(size_type size);

    // Transforms the __hash value hash into a ranged-hash value
    // (using a bit-mask).
    inline size_type
    operator()(size_type hash) const;
  };

#include <ext/pb_ds/detail/hash_fn/direct_mask_range_hashing_imp.hpp>

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

#define PB_DS_CLASS_T_DEC template<typename Size_Type>
#define PB_DS_CLASS_C_DEC direct_mod_range_hashing<Size_Type>

  /// A mod range-hashing class (uses the modulo function).
  template<typename Size_Type = std::size_t>
  class direct_mod_range_hashing 
  : public detail::mod_based_range_hashing<Size_Type>
  {
  public:
    typedef Size_Type size_type;
      
    void
    swap(PB_DS_CLASS_C_DEC& other);

  protected:
    void
    notify_resized(size_type size);
      
    // Transforms the __hash value hash into a ranged-hash value
    // (using a modulo operation).
    inline size_type
    operator()(size_type hash) const;
      
  private:
    typedef detail::mod_based_range_hashing<size_type> mod_based_base;
  };

#include <ext/pb_ds/detail/hash_fn/direct_mod_range_hashing_imp.hpp>

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

#define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type>
#define PB_DS_CLASS_C_DEC hash_load_check_resize_trigger<External_Load_Access, Size_Type>
#define PB_DS_SIZE_BASE_C_DEC detail::hash_load_check_resize_trigger_size_base<Size_Type, External_Load_Access>

  /// A resize trigger policy based on a load check. It keeps the
  /// load factor between some load factors load_min and load_max.
  template<bool External_Load_Access = false, typename Size_Type = std::size_t>
  class hash_load_check_resize_trigger : private PB_DS_SIZE_BASE_C_DEC
  {
  public:
    typedef Size_Type size_type;

    enum
      {
	external_load_access = External_Load_Access
      };

    // Default constructor, or constructor taking load_min and
    // load_max load factors between which this policy will keep the
    // actual load.
    hash_load_check_resize_trigger(float load_min = 0.125,
				   float load_max = 0.5);

    void
    swap(hash_load_check_resize_trigger& other);

    virtual
    ~hash_load_check_resize_trigger();

    // Returns a pair of the minimal and maximal loads, respectively.
    inline std::pair<float, float>
    get_loads() const;

    // Sets the loads through a pair of the minimal and maximal
    // loads, respectively.
    void
    set_loads(std::pair<float, float> load_pair);

  protected:
    inline void
    notify_insert_search_start();

    inline void
    notify_insert_search_collision();

    inline void
    notify_insert_search_end();

    inline void
    notify_find_search_start();

    inline void
    notify_find_search_collision();

    inline void
    notify_find_search_end();

    inline void
    notify_erase_search_start();

    inline void
    notify_erase_search_collision();

    inline void
    notify_erase_search_end();

    // Notifies an element was inserted. The total number of entries
    // in the table is num_entries.
    inline void
    notify_inserted(size_type num_entries);

    inline void
    notify_erased(size_type num_entries);

    // Notifies the table was cleared.
    void
    notify_cleared();

    // Notifies the table was resized as a result of this object's
    // signifying that a resize is needed.
    void
    notify_resized(size_type new_size);

    void
    notify_externally_resized(size_type new_size);

    inline bool
    is_resize_needed() const;

    inline bool
    is_grow_needed(size_type size, size_type num_entries) const;

  private:
    virtual void
    do_resize(size_type new_size);

    typedef PB_DS_SIZE_BASE_C_DEC size_base;

#ifdef _GLIBCXX_DEBUG
    void
    assert_valid(const char* file, int line) const;
#endif 

    float 	m_load_min;
    float 	m_load_max;
    size_type 	m_next_shrink_size;
    size_type 	m_next_grow_size;
    bool 	m_resize_needed;
  };

#include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp>

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#undef PB_DS_SIZE_BASE_C_DEC

#define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type>
#define PB_DS_CLASS_C_DEC cc_hash_max_collision_check_resize_trigger<External_Load_Access, Size_Type>

  /// A resize trigger policy based on collision checks. It keeps the
  /// simulated load factor lower than some given load factor.
  template<bool External_Load_Access = false, typename Size_Type = std::size_t>
  class cc_hash_max_collision_check_resize_trigger
  {
  public:
    typedef Size_Type size_type;

    enum
      {
	external_load_access = External_Load_Access
      };

    // Default constructor, or constructor taking load, a __load
    // factor which it will attempt to maintain.
    cc_hash_max_collision_check_resize_trigger(float load = 0.5);

    void
    swap(PB_DS_CLASS_C_DEC& other);

    // Returns the current load.
    inline float
    get_load() const;

    // Sets the load; does not resize the container.
    void
    set_load(float load);

  protected:
    inline void
    notify_insert_search_start();

    inline void
    notify_insert_search_collision();

    inline void
    notify_insert_search_end();

    inline void
    notify_find_search_start();

    inline void
    notify_find_search_collision();

    inline void
    notify_find_search_end();

    inline void
    notify_erase_search_start();

    inline void
    notify_erase_search_collision();

    inline void
    notify_erase_search_end();

    inline void
    notify_inserted(size_type num_entries);

    inline void
    notify_erased(size_type num_entries);

    void
    notify_cleared();

    // Notifies the table was resized as a result of this object's
    // signifying that a resize is needed.
    void
    notify_resized(size_type new_size);

    void
    notify_externally_resized(size_type new_size);

    inline bool
    is_resize_needed() const;

    inline bool
    is_grow_needed(size_type size, size_type num_entries) const;

  private:
    void
    calc_max_num_coll();

    inline void
    calc_resize_needed();

    float 	m_load;
    size_type 	m_size;
    size_type 	m_num_col;
    size_type 	m_max_col;
    bool 	m_resize_needed;
  };

#include <ext/pb_ds/detail/resize_policy/cc_hash_max_collision_check_resize_trigger_imp.hpp>

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

#define PB_DS_CLASS_T_DEC template<typename Size_Type>
#define PB_DS_CLASS_C_DEC hash_exponential_size_policy<Size_Type>

  /// A size policy whose sequence of sizes form an exponential
  /// sequence (typically powers of 2.
  template<typename Size_Type = std::size_t>
  class hash_exponential_size_policy
  {
  public:
    typedef Size_Type size_type;

    // Default constructor, or onstructor taking a start_size, or
    // constructor taking a start size and grow_factor. The policy
    // will use the sequence of sizes start_size, start_size*
    // grow_factor, start_size* grow_factor^2, ...
    hash_exponential_size_policy(size_type start_size = 8,
				 size_type grow_factor = 2);

    void
    swap(PB_DS_CLASS_C_DEC& other);

  protected:
    size_type
    get_nearest_larger_size(size_type size) const;

    size_type
    get_nearest_smaller_size(size_type size) const;

  private:
    size_type m_start_size;
    size_type m_grow_factor;
  };

#include <ext/pb_ds/detail/resize_policy/hash_exponential_size_policy_imp.hpp>

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

#define PB_DS_CLASS_T_DEC
#define PB_DS_CLASS_C_DEC hash_prime_size_policy

  /// A size policy whose sequence of sizes form a nearly-exponential
  /// sequence of primes.
  class hash_prime_size_policy
  {
  public:
    // Size type.
    typedef std::size_t size_type;

    // Default constructor, or onstructor taking a start_size The
    // policy will use the sequence of sizes approximately
    // start_size, start_size* 2, start_size* 2^2, ...
    hash_prime_size_policy(size_type start_size = 8);

    inline void
    swap(PB_DS_CLASS_C_DEC& other);

  protected:
    size_type
    get_nearest_larger_size(size_type size) const;

    size_type
    get_nearest_smaller_size(size_type size) const;

  private:
    size_type m_start_size;
  };

#include <ext/pb_ds/detail/resize_policy/hash_prime_size_policy_imp.hpp>

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

#define PB_DS_CLASS_T_DEC template<typename Size_Policy, typename Trigger_Policy, bool External_Size_Access, typename Size_Type>

#define PB_DS_CLASS_C_DEC hash_standard_resize_policy<Size_Policy, Trigger_Policy, External_Size_Access, Size_Type>

  /// A resize policy which delegates operations to size and trigger policies.
  template<typename Size_Policy = hash_exponential_size_policy<>,
	   typename Trigger_Policy = hash_load_check_resize_trigger<>,
	   bool External_Size_Access = false,
	   typename Size_Type = std::size_t>
  class hash_standard_resize_policy 
  : public Size_Policy, public Trigger_Policy
  {
  public:
    typedef Size_Type 		size_type;
    typedef Trigger_Policy 	trigger_policy;
    typedef Size_Policy 	size_policy;

    enum
      {
	external_size_access = External_Size_Access
      };

    // Default constructor.
    hash_standard_resize_policy();

    // constructor taking some policies r_size_policy will be copied
    // by the Size_Policy object of this object.
    hash_standard_resize_policy(const Size_Policy& r_size_policy);

    // constructor taking some policies. r_size_policy will be
    // copied by the Size_Policy object of this
    // object. r_trigger_policy will be copied by the Trigger_Policy
    // object of this object.
    hash_standard_resize_policy(const Size_Policy& r_size_policy, 
				const Trigger_Policy& r_trigger_policy);

    virtual
    ~hash_standard_resize_policy();

    inline void
    swap(PB_DS_CLASS_C_DEC& other);

    // Access to the Size_Policy object used.
    Size_Policy& 
    get_size_policy();

    // Const access to the Size_Policy object used.
    const Size_Policy& 
    get_size_policy() const;

    // Access to the Trigger_Policy object used.
    Trigger_Policy& 
    get_trigger_policy();

    // Access to the Trigger_Policy object used.
    const Trigger_Policy& 
    get_trigger_policy() const;

    // Returns the actual size of the container.
    inline size_type
    get_actual_size() const;

    // Resizes the container to suggested_new_size, a suggested size
    // (the actual size will be determined by the Size_Policy
    // object).
    void
    resize(size_type suggested_new_size);

  protected:
    inline void
    notify_insert_search_start();

    inline void
    notify_insert_search_collision();

    inline void
    notify_insert_search_end();

    inline void
    notify_find_search_start();

    inline void
    notify_find_search_collision();

    inline void
    notify_find_search_end();

    inline void
    notify_erase_search_start();

    inline void
    notify_erase_search_collision();

    inline void
    notify_erase_search_end();

    inline void
    notify_inserted(size_type num_e);

    inline void
    notify_erased(size_type num_e);

    void
    notify_cleared();

    void
    notify_resized(size_type new_size);

    inline bool
    is_resize_needed() const;

    // Queries what the new size should be, when the container is
    // resized naturally. The current __size of the container is
    // size, and the number of used entries within the container is
    // num_used_e.
    size_type
    get_new_size(size_type size, size_type num_used_e) const;

  private:
    // Resizes to new_size.
    virtual void
    do_resize(size_type new_size);

    typedef Trigger_Policy trigger_policy_base;

    typedef Size_Policy size_policy_base;

    size_type m_size;
  };

#include <ext/pb_ds/detail/resize_policy/hash_standard_resize_policy_imp.hpp>

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

} // namespace __gnu_pbds

#endif
Commit	Line	Data
4569a895 AT	1	// -- C++ --
4569a895 AT	2
f5886803	3	// Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc.
4569a895 AT	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
748086b7	8	// Foundation; either version 3, or (at your option) any later
4569a895 AT	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
748086b7 JJ	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.
4569a895	19
748086b7 JJ	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/>.
4569a895 AT	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
8fc81078	44	#include <bits/c++config.h>
4569a895 AT	45	#include <algorithm>
	46	#include <vector>
	47	#include <cmath>
	48	#include <ext/pb_ds/exception.hpp>
d7f245b1	49	#include <ext/pb_ds/detail/type_utils.hpp>
4569a895 AT	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
5e11f978	54	namespace __gnu_pbds
4569a895	55	{
4569a895 AT	56	#define PB_DS_CLASS_T_DEC template<typename Size_Type>
	57	#define PB_DS_CLASS_C_DEC linear_probe_fn<Size_Type>
	58
a345e45d	59	/// A probe sequence policy using fixed increments.
8fc81078	60	template<typename Size_Type = std::size_t>
4569a895 AT	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
a345e45d	83	/// A probe sequence policy using square increments.
8fc81078	84	template<typename Size_Type = std::size_t>
4569a895 AT	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
a345e45d	107	/// A mask range-hashing class (uses a bit-mask).
8fc81078	108	template<typename Size_Type = std::size_t>
4569a895 AT	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
a345e45d	139	/// A mod range-hashing class (uses the modulo function).
8fc81078	140	template<typename Size_Type = std::size_t>
4569a895 AT	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
a345e45d BK	172	/// A resize trigger policy based on a load check. It keeps the
a345e45d BK	173	/// load factor between some load factors load_min and load_max.
8fc81078	174	template<bool External_Load_Access = false, typename Size_Type = std::size_t>
4569a895 AT	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	external_load_access = External_Load_Access
	183	};
	184
	185	// Default constructor, or constructor taking load_min and
	186	// load_max load factors between which this policy will keep the
	187	// actual load.
	188	hash_load_check_resize_trigger(float load_min = 0.125,
	189	float load_max = 0.5);
	190
	191	void
	192	swap(hash_load_check_resize_trigger& other);
	193
	194	virtual
	195	~hash_load_check_resize_trigger();
	196
	197	// Returns a pair of the minimal and maximal loads, respectively.
	198	inline std::pair<float, float>
	199	get_loads() const;
	200
	201	// Sets the loads through a pair of the minimal and maximal
	202	// loads, respectively.
	203	void
	204	set_loads(std::pair<float, float> load_pair);
	205
	206	protected:
	207	inline void
	208	notify_insert_search_start();
	209
	210	inline void
	211	notify_insert_search_collision();
	212
	213	inline void
	214	notify_insert_search_end();
	215
	216	inline void
	217	notify_find_search_start();
	218
	219	inline void
	220	notify_find_search_collision();
	221
	222	inline void
	223	notify_find_search_end();
	224
	225	inline void
	226	notify_erase_search_start();
	227
	228	inline void
	229	notify_erase_search_collision();
	230
	231	inline void
	232	notify_erase_search_end();
	233
	234	// Notifies an element was inserted. The total number of entries
	235	// in the table is num_entries.
	236	inline void
	237	notify_inserted(size_type num_entries);
	238
239	inline void
240	notify_erased(size_type num_entries);
241
242	// Notifies the table was cleared.
243	void
244	notify_cleared();
245
246	// Notifies the table was resized as a result of this object's
247	// signifying that a resize is needed.
248	void
249	notify_resized(size_type new_size);
250
251	void
252	notify_externally_resized(size_type new_size);
253
254	inline bool
255	is_resize_needed() const;
256
257	inline bool
258	is_grow_needed(size_type size, size_type num_entries) const;
259
260	private:
261	virtual void
262	do_resize(size_type new_size);
263
264	typedef PB_DS_SIZE_BASE_C_DEC size_base;
265
47bea7b8	266	#ifdef _GLIBCXX_DEBUG
4569a895	267	void
f5886803	268	assert_valid(const char* file, int line) const;
4569a895 AT	269	#endif
	270
	271	float m_load_min;
	272	float m_load_max;
	273	size_type m_next_shrink_size;
	274	size_type m_next_grow_size;
	275	bool m_resize_needed;
	276	};
	277
	278	#include <ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp>
	279
	280	#undef PB_DS_CLASS_T_DEC
	281	#undef PB_DS_CLASS_C_DEC
	282	#undef PB_DS_SIZE_BASE_C_DEC
	283
	284	#define PB_DS_CLASS_T_DEC template<bool External_Load_Access, typename Size_Type>
	285	#define PB_DS_CLASS_C_DEC cc_hash_max_collision_check_resize_trigger<External_Load_Access, Size_Type>
	286
a345e45d BK	287	/// A resize trigger policy based on collision checks. It keeps the
a345e45d BK	288	/// simulated load factor lower than some given load factor.
8fc81078	289	template<bool External_Load_Access = false, typename Size_Type = std::size_t>
4569a895 AT	290	class cc_hash_max_collision_check_resize_trigger
	291	{
	292	public:
	293	typedef Size_Type size_type;
	294
	295	enum
	296	{
	297	external_load_access = External_Load_Access
	298	};
	299
	300	// Default constructor, or constructor taking load, a __load
	301	// factor which it will attempt to maintain.
	302	cc_hash_max_collision_check_resize_trigger(float load = 0.5);
	303
	304	void
	305	swap(PB_DS_CLASS_C_DEC& other);
	306
	307	// Returns the current load.
	308	inline float
	309	get_load() const;
	310
	311	// Sets the load; does not resize the container.
	312	void
	313	set_load(float load);
	314
	315	protected:
	316	inline void
	317	notify_insert_search_start();
	318
	319	inline void
	320	notify_insert_search_collision();
	321
	322	inline void
	323	notify_insert_search_end();
	324
	325	inline void
	326	notify_find_search_start();
	327
	328	inline void
	329	notify_find_search_collision();
	330
	331	inline void
	332	notify_find_search_end();
	333
	334	inline void
	335	notify_erase_search_start();
	336
	337	inline void
	338	notify_erase_search_collision();
	339
	340	inline void
	341	notify_erase_search_end();
	342
	343	inline void
	344	notify_inserted(size_type num_entries);
	345
	346	inline void
	347	notify_erased(size_type num_entries);
	348
	349	void
	350	notify_cleared();
	351
	352	// Notifies the table was resized as a result of this object's
	353	// signifying that a resize is needed.
354	void
355	notify_resized(size_type new_size);
356
357	void
358	notify_externally_resized(size_type new_size);
359
360	inline bool
361	is_resize_needed() const;
362
363	inline bool
364	is_grow_needed(size_type size, size_type num_entries) const;
365
366	private:
367	void
368	calc_max_num_coll();
369
370	inline void
371	calc_resize_needed();
372
373	float m_load;
374	size_type m_size;
375	size_type m_num_col;
376	size_type m_max_col;
377	bool m_resize_needed;
378	};
379
380	#include <ext/pb_ds/detail/resize_policy/cc_hash_max_collision_check_resize_trigger_imp.hpp>
381
382	#undef PB_DS_CLASS_T_DEC
383	#undef PB_DS_CLASS_C_DEC
384
385	#define PB_DS_CLASS_T_DEC template<typename Size_Type>
386	#define PB_DS_CLASS_C_DEC hash_exponential_size_policy<Size_Type>
387
a345e45d BK	388	/// A size policy whose sequence of sizes form an exponential
a345e45d BK	389	/// sequence (typically powers of 2.
8fc81078	390	template<typename Size_Type = std::size_t>
4569a895 AT	391	class hash_exponential_size_policy
	392	{
	393	public:
	394	typedef Size_Type size_type;
	395
	396	// Default constructor, or onstructor taking a start_size, or
	397	// constructor taking a start size and grow_factor. The policy
	398	// will use the sequence of sizes start_size, start_size*
	399	// grow_factor, start_size* grow_factor^2, ...
	400	hash_exponential_size_policy(size_type start_size = 8,
	401	size_type grow_factor = 2);
	402
	403	void
	404	swap(PB_DS_CLASS_C_DEC& other);
	405
	406	protected:
	407	size_type
	408	get_nearest_larger_size(size_type size) const;
	409
	410	size_type
	411	get_nearest_smaller_size(size_type size) const;
	412
	413	private:
	414	size_type m_start_size;
	415	size_type m_grow_factor;
	416	};
	417
	418	#include <ext/pb_ds/detail/resize_policy/hash_exponential_size_policy_imp.hpp>
	419
	420	#undef PB_DS_CLASS_T_DEC
	421	#undef PB_DS_CLASS_C_DEC
	422
	423	#define PB_DS_CLASS_T_DEC
	424	#define PB_DS_CLASS_C_DEC hash_prime_size_policy
	425
a345e45d BK	426	/// A size policy whose sequence of sizes form a nearly-exponential
a345e45d BK	427	/// sequence of primes.
4569a895 AT	428	class hash_prime_size_policy
	429	{
	430	public:
	431	// Size type.
8fc81078	432	typedef std::size_t size_type;
4569a895 AT	433
	434	// Default constructor, or onstructor taking a start_size The
	435	// policy will use the sequence of sizes approximately
	436	// start_size, start_size* 2, start_size* 2^2, ...
	437	hash_prime_size_policy(size_type start_size = 8);
	438
	439	inline void
	440	swap(PB_DS_CLASS_C_DEC& other);
	441
	442	protected:
	443	size_type
	444	get_nearest_larger_size(size_type size) const;
	445
	446	size_type
	447	get_nearest_smaller_size(size_type size) const;
	448
	449	private:
	450	size_type m_start_size;
	451	};
	452
	453	#include <ext/pb_ds/detail/resize_policy/hash_prime_size_policy_imp.hpp>
	454
	455	#undef PB_DS_CLASS_T_DEC
	456	#undef PB_DS_CLASS_C_DEC
	457
	458	#define PB_DS_CLASS_T_DEC template<typename Size_Policy, typename Trigger_Policy, bool External_Size_Access, typename Size_Type>
	459
	460	#define PB_DS_CLASS_C_DEC hash_standard_resize_policy<Size_Policy, Trigger_Policy, External_Size_Access, Size_Type>
	461
a345e45d	462	/// A resize policy which delegates operations to size and trigger policies.
4569a895 AT	463	template<typename Size_Policy = hash_exponential_size_policy<>,
	464	typename Trigger_Policy = hash_load_check_resize_trigger<>,
	465	bool External_Size_Access = false,
8fc81078	466	typename Size_Type = std::size_t>
4569a895 AT	467	class hash_standard_resize_policy
	468	: public Size_Policy, public Trigger_Policy
	469	{
	470	public:
	471	typedef Size_Type size_type;
	472	typedef Trigger_Policy trigger_policy;
	473	typedef Size_Policy size_policy;
	474
	475	enum
	476	{
	477	external_size_access = External_Size_Access
	478	};
	479
	480	// Default constructor.
	481	hash_standard_resize_policy();
	482
	483	// constructor taking some policies r_size_policy will be copied
	484	// by the Size_Policy object of this object.
	485	hash_standard_resize_policy(const Size_Policy& r_size_policy);
	486
	487	// constructor taking some policies. r_size_policy will be
	488	// copied by the Size_Policy object of this
	489	// object. r_trigger_policy will be copied by the Trigger_Policy
	490	// object of this object.
	491	hash_standard_resize_policy(const Size_Policy& r_size_policy,
	492	const Trigger_Policy& r_trigger_policy);
	493
	494	virtual
	495	~hash_standard_resize_policy();
	496
	497	inline void
	498	swap(PB_DS_CLASS_C_DEC& other);
	499
	500	// Access to the Size_Policy object used.
	501	Size_Policy&
	502	get_size_policy();
	503
	504	// Const access to the Size_Policy object used.
	505	const Size_Policy&
	506	get_size_policy() const;
	507
	508	// Access to the Trigger_Policy object used.
	509	Trigger_Policy&
	510	get_trigger_policy();
	511
	512	// Access to the Trigger_Policy object used.
	513	const Trigger_Policy&
	514	get_trigger_policy() const;
	515
	516	// Returns the actual size of the container.
	517	inline size_type
	518	get_actual_size() const;
	519
	520	// Resizes the container to suggested_new_size, a suggested size
	521	// (the actual size will be determined by the Size_Policy
	522	// object).
	523	void
	524	resize(size_type suggested_new_size);
	525
	526	protected:
	527	inline void
	528	notify_insert_search_start();
	529
	530	inline void
531	notify_insert_search_collision();
532
533	inline void
534	notify_insert_search_end();
535
536	inline void
537	notify_find_search_start();
538
539	inline void
540	notify_find_search_collision();
541
542	inline void
543	notify_find_search_end();
544
545	inline void
546	notify_erase_search_start();
547
548	inline void
549	notify_erase_search_collision();
550
551	inline void
552	notify_erase_search_end();
553
554	inline void
555	notify_inserted(size_type num_e);
556
557	inline void
558	notify_erased(size_type num_e);
559
560	void
561	notify_cleared();
562
563	void
564	notify_resized(size_type new_size);
565
566	inline bool
567	is_resize_needed() const;
568
569	// Queries what the new size should be, when the container is
570	// resized naturally. The current __size of the container is
571	// size, and the number of used entries within the container is
572	// num_used_e.
573	size_type
574	get_new_size(size_type size, size_type num_used_e) const;
575
576	private:
577	// Resizes to new_size.
578	virtual void
579	do_resize(size_type new_size);
580
581	typedef Trigger_Policy trigger_policy_base;
582
583	typedef Size_Policy size_policy_base;
584
585	size_type m_size;
586	};
587
588	#include <ext/pb_ds/detail/resize_policy/hash_standard_resize_policy_imp.hpp>
589
590	#undef PB_DS_CLASS_T_DEC
591	#undef PB_DS_CLASS_C_DEC
592
5e11f978	593	} // namespace __gnu_pbds
4569a895 AT	594
4569a895 AT	595	#endif