URL https://opencores.org/ocsvn/scarts/scarts/trunk

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [libstdc++-v3/] [include/] [ext/] [pb_assoc/] [hash_policy.hpp] - Blame information for rev 17

Details | Compare with Previous | View Log


// -*- C++ -*-
 
// Copyright (C) 2005 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 2, 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.
 
// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.
 
// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.
 
// 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 HASH_POLICY_HPP
#define HASH_POLICY_HPP
 
#include <algorithm>
#include <vector>
#include <cmath>
#include <ext/pb_assoc/exception.hpp>
#include <ext/pb_assoc/detail/hash_fn/mask_based_range_hashing.hpp>
#include <ext/pb_assoc/detail/hash_fn/mod_based_range_hashing.hpp>
#include <ext/pb_assoc/detail/resize_policy/size_base.hpp>
 
namespace pb_assoc
{
  struct null_hash_fn
  { };
 
  struct null_probe_fn
  { };
 
#define PB_ASSOC_CLASS_T_DEC \
        template<typename Const_Key_Ref, typename Size_Type>
 
#define PB_ASSOC_CLASS_C_DEC \
        linear_probe_fn< \
                Const_Key_Ref, \
                Size_Type>
 
  template<typename Const_Key_Ref, typename Size_Type = size_t>
    class linear_probe_fn
    {
    public:
      typedef Size_Type size_type;
 
      void
      swap(PB_ASSOC_CLASS_C_DEC& r_other);
 
    protected:
      inline size_type
      operator()(Const_Key_Ref r_key, size_type i) const;
    };
 
#include <ext/pb_assoc/detail/hash_fn/linear_probe_fn_imp.hpp>
 
#undef PB_ASSOC_CLASS_T_DEC
#undef PB_ASSOC_CLASS_C_DEC
 
#define PB_ASSOC_CLASS_T_DEC \
        template<class Const_Key_Ref, typename Size_Type>
 
#define PB_ASSOC_CLASS_C_DEC \
        quadratic_probe_fn<Const_Key_Ref, Size_Type>
 
  template<typename Const_Key_Ref, typename Size_Type = size_t>
    class quadratic_probe_fn
    {
    public:
      typedef Size_Type size_type;
 
      void
      swap(PB_ASSOC_CLASS_C_DEC& r_other);
 
    protected:
      inline size_type
      operator()(Const_Key_Ref r_key, size_type i) const;
    };
 
#include <ext/pb_assoc/detail/hash_fn/quadratic_probe_fn_imp.hpp>
 
#undef PB_ASSOC_CLASS_T_DEC
#undef PB_ASSOC_CLASS_C_DEC
 
#define PB_ASSOC_CLASS_T_DEC \
        template<typename Size_Type>
 
#define PB_ASSOC_CLASS_C_DEC \
        direct_mask_range_hashing<Size_Type>
 
  template<typename Size_Type = size_t>
    class direct_mask_range_hashing
    : public pb_assoc::detail::mask_based_range_hashing<Size_Type>
    {
    public:
      typedef Size_Type size_type;
 
      void
      swap(PB_ASSOC_CLASS_C_DEC& r_other);
 
    protected:
      void
      notify_resized(size_type size);
 
      inline size_type
      operator()(size_type hash) const;
 
    private:
      typedef pb_assoc::detail::mask_based_range_hashing<Size_Type>
      my_mask_based_base;
    };
 
#define PB_ASSOC_MASK_BASED_C_DEC \
        pb_assoc::detail::mask_based_range_hashing< \
                Size_Type>
 
#include <ext/pb_assoc/detail/hash_fn/direct_mask_range_hashing_imp.hpp>
 
#undef PB_ASSOC_CLASS_T_DEC
#undef PB_ASSOC_CLASS_C_DEC
 
#undef PB_ASSOC_MASK_BASED_C_DEC
 
#define PB_ASSOC_CLASS_T_DEC \
        template<typename Size_Type>
 
#define PB_ASSOC_CLASS_C_DEC \
        direct_mod_range_hashing<Size_Type>
 
#define PB_ASSOC_MOD_BASED_C_DEC \
        pb_assoc::detail::mod_based_range_hashing<Size_Type>
 
  template<typename Size_Type = size_t>
    class direct_mod_range_hashing : public PB_ASSOC_MOD_BASED_C_DEC
    {
    public:
      typedef Size_Type size_type;
 
      void
      swap(PB_ASSOC_CLASS_C_DEC& r_other);
 
    protected:
      /*
       *   description = "Notifies the policy object that the container's
       *          __size has changed to size.">
       **/
      void
      notify_resized(size_type size);
 
      inline size_type
    operator()(size_type hash) const;
 
    private:
      typedef PB_ASSOC_MOD_BASED_C_DEC my_mod_based_base;
    };
 
#include <ext/pb_assoc/detail/hash_fn/direct_mod_range_hashing_imp.hpp>
 
#undef PB_ASSOC_CLASS_T_DEC
#undef PB_ASSOC_CLASS_C_DEC
 
#undef PB_ASSOC_MOD_BASED_C_DEC
 
#ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG
#define PB_ASSOC_DBG_ASSERT(X) assert(X)
#define PB_ASSOC_DBG_VERIFY(X) assert(X)
#define PB_ASSOC_DBG_ONLY(X) X
#else // #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG
#define PB_ASSOC_DBG_ASSERT(X)
#define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
#define PB_ASSOC_DBG_ONLY(X) ;
#endif // #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG
 
#define PB_ASSOC_CLASS_T_DEC \
        template<bool External_Load_Access, typename Size_Type>
 
#define PB_ASSOC_CLASS_C_DEC \
        hash_load_check_resize_trigger<External_Load_Access, Size_Type>
 
#define PB_ASSOC_SIZE_BASE_C_DEC \
        pb_assoc::detail::size_base<Size_Type, External_Load_Access>
 
  template<bool External_Load_Access = false, typename Size_Type = size_t>
    class hash_load_check_resize_trigger : private PB_ASSOC_SIZE_BASE_C_DEC
    {
    public:
      typedef Size_Type size_type;
 
      enum
        {
          external_load_access = External_Load_Access
        };
 
      hash_load_check_resize_trigger(float load_min = 0.125,
                                     float load_max = 0.5);
 
      void
      swap(PB_ASSOC_CLASS_C_DEC& r_other);
 
      virtual
      ~hash_load_check_resize_trigger();
 
      inline std::pair<float, float>
      get_loads() const;
 
      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();
 
      inline void
      notify_inserted(size_type num_entries);
 
      inline void
      notify_erased(size_type num_entries);
 
      void
      notify_cleared();
 
      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;
 
      inline bool
      is_shrink_needed(size_type size, size_type num_entries) const;
 
      typedef PB_ASSOC_SIZE_BASE_C_DEC my_size_base;
 
    private:
      inline std::pair<float, float>
      get_loads_imp(pb_assoc::detail::int_to_type<true>) const;
 
      void
      set_loads_imp(std::pair<float, float>,
                    pb_assoc::detail::int_to_type<true>);
 
      virtual void
      do_resize(size_type new_size);
 
#ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG
      void
      assert_valid() const;
#endif // #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG
 
      float m_load_min, m_load_max;
 
      size_type m_next_shrink_size;
 
      size_type m_next_grow_size;
 
      bool m_resize_needed;
 
      static pb_assoc::detail::int_to_type<External_Load_Access>
      s_external_load_access_ind;
    };
 
#include <ext/pb_assoc/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp>
 
#undef PB_ASSOC_CLASS_T_DEC
#undef PB_ASSOC_CLASS_C_DEC
 
#undef PB_ASSOC_SIZE_BASE_C_DEC
 
#undef PB_ASSOC_DBG_ASSERT
#undef PB_ASSOC_DBG_VERIFY
#undef PB_ASSOC_DBG_ONLY
 
#ifdef PB_ASSOC_HT_MAX_COLLISION_CHECK_RESIZE_TRIGGER_POLICY_DEBUG
#define PB_ASSOC_DBG_ASSERT(X) assert(X)
#define PB_ASSOC_DBG_VERIFY(X) assert(X)
#define PB_ASSOC_DBG_ONLY(X) X
#else // #ifdef PB_ASSOC_HT_MAX_COLLISION_CHECK_RESIZE_TRIGGER_POLICY_DEBUG
#define PB_ASSOC_DBG_ASSERT(X)
#define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
#define PB_ASSOC_DBG_ONLY(X) ;
#endif // #ifdef PB_ASSOC_HT_MAX_COLLISION_CHECK_RESIZE_TRIGGER_POLICY_DEBUG
 
#define PB_ASSOC_CLASS_T_DEC \
        template<bool External_Load_Access, typename Size_Type>
 
#define PB_ASSOC_CLASS_C_DEC \
        cc_hash_max_collision_check_resize_trigger< \
                External_Load_Access, \
                Size_Type>
 
  template<bool External_Load_Access = false, typename Size_Type = size_t>
    class cc_hash_max_collision_check_resize_trigger
    {
    public:
      typedef Size_Type size_type;
 
      enum
        {
          external_load_access = External_Load_Access
        };
 
      cc_hash_max_collision_check_resize_trigger(float load = 0.5);
 
      void
      swap(PB_ASSOC_CLASS_C_DEC& r_other);
 
      inline float
      get_load() const;
 
    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();
 
      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;
 
      inline bool
      is_shrink_needed(size_type size, size_type num_entries) const;
 
    private:
      template<typename Key>
      class max_col_checker
      {
      public:
        max_col_checker(size_type size, size_type* p_max_col)
        : m_p_max_col(p_max_col), m_a_col(size, 0)
        { }
 
        void
        operator()(const std::pair<const Key, size_type>& r_key_pos_pair)
        { ++m_a_col[r_key_pos_pair.second]; }
 
      private:
        std::vector<size_type> m_a_col;
 
        size_type* const m_p_max_col;
      };
 
    private:
      inline float
      get_load_imp(pb_assoc::detail::int_to_type<true>) const;
 
      float m_load;
 
      size_type m_size;
 
      size_type m_num_col;
 
      size_type m_max_col;
 
      bool m_resize_needed;
 
      static pb_assoc::detail::int_to_type<External_Load_Access>
      s_external_load_access_ind;
    };
 
#include <ext/pb_assoc/detail/resize_policy/cc_hash_max_collision_resize_trigger_imp.hpp>
 
#undef PB_ASSOC_CLASS_T_DEC
#undef PB_ASSOC_CLASS_C_DEC
 
#undef PB_ASSOC_DBG_ASSERT
#undef PB_ASSOC_DBG_VERIFY
#undef PB_ASSOC_DBG_ONLY
 
#define PB_ASSOC_CLASS_T_DEC \
        template<typename Size_Type>
 
#define PB_ASSOC_CLASS_C_DEC \
        hash_exponential_size_policy< \
                Size_Type>
 
  template<typename Size_Type = size_t>
  class hash_exponential_size_policy
  {
  public:
    typedef Size_Type size_type;
 
    hash_exponential_size_policy(size_type start_size = 8,
                                 size_type grow_factor = 2);
 
    void
    swap(PB_ASSOC_CLASS_C_DEC& r_other);
 
  protected:
    size_type
    get_init_size(size_type suggested_size) const;
 
    size_type
    get_nearest_larger_size(size_type cur_size) const;
 
    size_type
    get_nearest_smaller_size(size_type cur_size) const;
 
#ifdef PB_ASSOC_HT_EXPONENTIAL_SIZE_POLICY_DEBUG
    void
    assert_is_one_of_my_sizes(size_type size) const;
#endif // #ifdef PB_ASSOC_HT_EXPONENTIAL_SIZE_POLICY_DEBUG
 
  private:
    size_type m_start_size;
    size_type m_grow_factor;
  };
 
#include <ext/pb_assoc/detail/resize_policy/hash_exponential_size_policy_imp.hpp>
 
#undef PB_ASSOC_CLASS_T_DEC
#undef PB_ASSOC_CLASS_C_DEC
 
#undef PB_ASSOC_DBG_ASSERT
#undef PB_ASSOC_DBG_VERIFY
#undef PB_ASSOC_DBG_ONLY
 
#define PB_ASSOC_CLASS_T_DEC
 
#define PB_ASSOC_CLASS_C_DEC \
        hash_prime_size_policy
 
#ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG
#define PB_ASSOC_DBG_ASSERT(X) assert(X)
#define PB_ASSOC_DBG_VERIFY(X) assert(X)
#define PB_ASSOC_DBG_ONLY(X) X
#else // #ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG
#define PB_ASSOC_DBG_ASSERT(X)
#define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
#define PB_ASSOC_DBG_ONLY(X) ;
#endif // #ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG
 
  struct hash_prime_size_policy
  {
    typedef size_t size_type;
 
    inline void
    swap(PB_ASSOC_CLASS_C_DEC& r_other);
 
  protected:
    inline size_type
    get_init_size(size_type suggested_size) const;
 
    inline size_type
    get_nearest_larger_size(size_type cur_size) const;
 
    inline size_type
    get_nearest_smaller_size(size_type cur_size) const;
 
    inline size_type
    get_nearest_larger_size_imp(size_type size) const;
 
#ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG
    void
    assert_is_one_of_my_sizes(size_type size) const;
#endif // #ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG
  };
 
#include <ext/pb_assoc/detail/resize_policy/hash_prime_size_policy_imp.hpp>
 
#undef PB_ASSOC_CLASS_T_DEC
#undef PB_ASSOC_CLASS_C_DEC
 
#undef PB_ASSOC_DBG_ASSERT
#undef PB_ASSOC_DBG_VERIFY
#undef PB_ASSOC_DBG_ONLY
 
#define PB_ASSOC_CLASS_T_DEC \
        template< \
                class Size_Policy, \
                class Trigger_Policy, \
                bool External_Size_Access, \
                typename Size_Type>
 
#define PB_ASSOC_CLASS_C_DEC \
        hash_standard_resize_policy< \
                Size_Policy, \
                Trigger_Policy, \
                External_Size_Access, \
                Size_Type>
 
  template<class Size_Policy =  pb_assoc::hash_exponential_size_policy<>,
           class Trigger_Policy = pb_assoc::hash_load_check_resize_trigger<>,
           bool External_Size_Access = false,
           typename Size_Type = 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
      };
 
    hash_standard_resize_policy(size_type suggested_size = 8);
 
    hash_standard_resize_policy(const Size_Policy&,
                                size_type suggested_size = 8);
 
    hash_standard_resize_policy(const Size_Policy&, const Trigger_Policy&,
                                size_type suggested_size = 8);
 
    virtual
    ~hash_standard_resize_policy();
 
    inline void
    swap(PB_ASSOC_CLASS_C_DEC& r_other);
 
    Size_Policy&
    get_size_policy();
 
    const Size_Policy&
    get_size_policy() const;
 
    Trigger_Policy&
    get_trigger_policy();
 
    const Trigger_Policy&
    get_trigger_policy() const;
 
    inline size_type
    get_actual_size() const;
 
    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);
 
    size_type
    get_init_size() const;
 
    inline bool
    is_resize_needed() const;
 
    size_type
    get_new_size(size_type size, size_type num_used_e) const;
 
  private:
    typedef Trigger_Policy my_trigger_policy_base;
 
    typedef Size_Policy my_size_policy_base;
 
    typedef
    pb_assoc::detail::int_to_type<false>
    external_resize_false_indicator;
 
    typedef
    pb_assoc::detail::int_to_type<true>
    external_resize_true_indicator;
 
    inline size_type
    get_actual_size(external_resize_true_indicator) const;
 
    void
    resize(size_type new_size, external_resize_true_indicator);
 
    virtual void
    do_resize(size_type new_size);
 
    static pb_assoc::detail::int_to_type<External_Size_Access>
    s_external_size_access_indicator;
 
    size_type m_size;
  };
 
#include <ext/pb_assoc/detail/resize_policy/hash_standard_resize_policy_imp.hpp>
 
#undef PB_ASSOC_CLASS_T_DEC
#undef PB_ASSOC_CLASS_C_DEC
 
#undef PB_ASSOC_DBG_ASSERT
#undef PB_ASSOC_DBG_VERIFY
#undef PB_ASSOC_DBG_ONLY
 
} // namespace pb_assoc
 
#endif // #ifndef HASH_POLICY_HPP

Browse

Tools

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [libstdc++-v3/] [include/] [ext/] [pb_assoc/] [hash_policy.hpp] - Blame information for rev 17

Line No.	Rev	Author	Line
1	17	jlechner	`// -- C++ --`
2
3			`// Copyright (C) 2005 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`
7			`// terms of the GNU General Public License as published by the`
8			`// Free Software Foundation; either version 2, or (at your option)`
9			`// any later version.`
10
11			`// This library is distributed in the hope that it will be useful,`
12			`// but WITHOUT ANY WARRANTY; without even the implied warranty of`
13			`// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the`
14			`// GNU General Public License for more details.`
15
16			`// You should have received a copy of the GNU General Public License along`
17			`// with this library; see the file COPYING. If not, write to the Free`
18			`// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,`
19			`// USA.`
20
21			`// As a special exception, you may use this file as part of a free software`
22			`// library without restriction. Specifically, if other files instantiate`
23			`// templates or use macros or inline functions from this file, or you compile`
24			`// this file and link it with other files to produce an executable, this`
25			`// file does not by itself cause the resulting executable to be covered by`
26			`// the GNU General Public License. This exception does not however`
27			`// invalidate any other reasons why the executable file might be covered by`
28			`// the GNU General Public License.`
29
30			`// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.`
31
32			`// Permission to use, copy, modify, sell, and distribute this software`
33			`// is hereby granted without fee, provided that the above copyright`
34			`// notice appears in all copies, and that both that copyright notice and`
35			`// this permission notice appear in supporting documentation. None of`
36			`// the above authors, nor IBM Haifa Research Laboratories, make any`
37			`// representation about the suitability of this software for any`
38			`// purpose. It is provided "as is" without express or implied warranty.`
39
40			`/*`
41			`* @file hash_policy.hpp`
42			`* Contains hash-related policies.`
43			`*/`
44
45			`#ifndef HASH_POLICY_HPP`
46			`#define HASH_POLICY_HPP`
47
48			`#include <algorithm>`
49			`#include <vector>`
50			`#include <cmath>`
51			`#include <ext/pb_assoc/exception.hpp>`
52			`#include <ext/pb_assoc/detail/hash_fn/mask_based_range_hashing.hpp>`
53			`#include <ext/pb_assoc/detail/hash_fn/mod_based_range_hashing.hpp>`
54			`#include <ext/pb_assoc/detail/resize_policy/size_base.hpp>`
55
56			`namespace pb_assoc`
57			`{`
58			`struct null_hash_fn`
59			`{ };`
60
61			`struct null_probe_fn`
62			`{ };`
63
64			`#define PB_ASSOC_CLASS_T_DEC \`
65			`template<typename Const_Key_Ref, typename Size_Type>`
66
67			`#define PB_ASSOC_CLASS_C_DEC \`
68			`linear_probe_fn< \`
69			`Const_Key_Ref, \`
70			`Size_Type>`
71
72			`template<typename Const_Key_Ref, typename Size_Type = size_t>`
73			`class linear_probe_fn`
74			`{`
75			`public:`
76			`typedef Size_Type size_type;`
77
78			`void`
79			`swap(PB_ASSOC_CLASS_C_DEC& r_other);`
80
81			`protected:`
82			`inline size_type`
83			`operator()(Const_Key_Ref r_key, size_type i) const;`
84			`};`
85
86			`#include <ext/pb_assoc/detail/hash_fn/linear_probe_fn_imp.hpp>`
87
88			`#undef PB_ASSOC_CLASS_T_DEC`
89			`#undef PB_ASSOC_CLASS_C_DEC`
90
91			`#define PB_ASSOC_CLASS_T_DEC \`
92			`template<class Const_Key_Ref, typename Size_Type>`
93
94			`#define PB_ASSOC_CLASS_C_DEC \`
95			`quadratic_probe_fn<Const_Key_Ref, Size_Type>`
96
97			`template<typename Const_Key_Ref, typename Size_Type = size_t>`
98			`class quadratic_probe_fn`
99			`{`
100			`public:`
101			`typedef Size_Type size_type;`
102
103			`void`
104			`swap(PB_ASSOC_CLASS_C_DEC& r_other);`
105
106			`protected:`
107			`inline size_type`
108			`operator()(Const_Key_Ref r_key, size_type i) const;`
109			`};`
110
111			`#include <ext/pb_assoc/detail/hash_fn/quadratic_probe_fn_imp.hpp>`
112
113			`#undef PB_ASSOC_CLASS_T_DEC`
114			`#undef PB_ASSOC_CLASS_C_DEC`
115
116			`#define PB_ASSOC_CLASS_T_DEC \`
117			`template<typename Size_Type>`
118
119			`#define PB_ASSOC_CLASS_C_DEC \`
120			`direct_mask_range_hashing<Size_Type>`
121
122			`template<typename Size_Type = size_t>`
123			`class direct_mask_range_hashing`
124			`: public pb_assoc::detail::mask_based_range_hashing<Size_Type>`
125			`{`
126			`public:`
127			`typedef Size_Type size_type;`
128
129			`void`
130			`swap(PB_ASSOC_CLASS_C_DEC& r_other);`
131
132			`protected:`
133			`void`
134			`notify_resized(size_type size);`
135
136			`inline size_type`
137			`operator()(size_type hash) const;`
138
139			`private:`
140			`typedef pb_assoc::detail::mask_based_range_hashing<Size_Type>`
141			`my_mask_based_base;`
142			`};`
143
144			`#define PB_ASSOC_MASK_BASED_C_DEC \`
145			`pb_assoc::detail::mask_based_range_hashing< \`
146			`Size_Type>`
147
148			`#include <ext/pb_assoc/detail/hash_fn/direct_mask_range_hashing_imp.hpp>`
149
150			`#undef PB_ASSOC_CLASS_T_DEC`
151			`#undef PB_ASSOC_CLASS_C_DEC`
152
153			`#undef PB_ASSOC_MASK_BASED_C_DEC`
154
155			`#define PB_ASSOC_CLASS_T_DEC \`
156			`template<typename Size_Type>`
157
158			`#define PB_ASSOC_CLASS_C_DEC \`
159			`direct_mod_range_hashing<Size_Type>`
160
161			`#define PB_ASSOC_MOD_BASED_C_DEC \`
162			`pb_assoc::detail::mod_based_range_hashing<Size_Type>`
163
164			`template<typename Size_Type = size_t>`
165			`class direct_mod_range_hashing : public PB_ASSOC_MOD_BASED_C_DEC`
166			`{`
167			`public:`
168			`typedef Size_Type size_type;`
169
170			`void`
171			`swap(PB_ASSOC_CLASS_C_DEC& r_other);`
172
173			`protected:`
174			`/*`
175			`* description = "Notifies the policy object that the container's`
176			`* __size has changed to size.">`
177			`**/`
178			`void`
179			`notify_resized(size_type size);`
180
181			`inline size_type`
182			`operator()(size_type hash) const;`
183
184			`private:`
185			`typedef PB_ASSOC_MOD_BASED_C_DEC my_mod_based_base;`
186			`};`
187
188			`#include <ext/pb_assoc/detail/hash_fn/direct_mod_range_hashing_imp.hpp>`
189
190			`#undef PB_ASSOC_CLASS_T_DEC`
191			`#undef PB_ASSOC_CLASS_C_DEC`
192
193			`#undef PB_ASSOC_MOD_BASED_C_DEC`
194
195			`#ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG`
196			`#define PB_ASSOC_DBG_ASSERT(X) assert(X)`
197			`#define PB_ASSOC_DBG_VERIFY(X) assert(X)`
198			`#define PB_ASSOC_DBG_ONLY(X) X`
199			`#else // #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG`
200			`#define PB_ASSOC_DBG_ASSERT(X)`
201			`#define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}`
202			`#define PB_ASSOC_DBG_ONLY(X) ;`
203			`#endif // #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG`
204
205			`#define PB_ASSOC_CLASS_T_DEC \`
206			`template<bool External_Load_Access, typename Size_Type>`
207
208			`#define PB_ASSOC_CLASS_C_DEC \`
209			`hash_load_check_resize_trigger<External_Load_Access, Size_Type>`
210
211			`#define PB_ASSOC_SIZE_BASE_C_DEC \`
212			`pb_assoc::detail::size_base<Size_Type, External_Load_Access>`
213
214			`template<bool External_Load_Access = false, typename Size_Type = size_t>`
215			`class hash_load_check_resize_trigger : private PB_ASSOC_SIZE_BASE_C_DEC`
216			`{`
217			`public:`
218			`typedef Size_Type size_type;`
219
220			`enum`
221			`{`
222			`external_load_access = External_Load_Access`
223			`};`
224
225			`hash_load_check_resize_trigger(float load_min = 0.125,`
226			`float load_max = 0.5);`
227
228			`void`
229			`swap(PB_ASSOC_CLASS_C_DEC& r_other);`
230
231			`virtual`
232			`~hash_load_check_resize_trigger();`
233
234			`inline std::pair<float, float>`
235			`get_loads() const;`
236
237			`void`
238			`set_loads(std::pair<float, float> load_pair);`
239
240			`protected:`
241			`inline void`
242			`notify_insert_search_start();`
243
244			`inline void`
245			`notify_insert_search_collision();`
246
247			`inline void`
248			`notify_insert_search_end();`
249
250			`inline void`
251			`notify_find_search_start();`
252
253			`inline void`
254			`notify_find_search_collision();`
255
256			`inline void`
257			`notify_find_search_end();`
258
259			`inline void`
260			`notify_erase_search_start();`
261
262			`inline void`
263			`notify_erase_search_collision();`
264
265			`inline void`
266			`notify_erase_search_end();`
267
268			`inline void`
269			`notify_inserted(size_type num_entries);`
270
271			`inline void`
272			`notify_erased(size_type num_entries);`
273
274			`void`
275			`notify_cleared();`
276
277			`void`
278			`notify_resized(size_type new_size);`
279
280			`void`
281			`notify_externally_resized(size_type new_size);`
282
283			`inline bool`
284			`is_resize_needed() const;`
285
286			`inline bool`
287			`is_grow_needed(size_type size, size_type num_entries) const;`
288
289			`inline bool`
290			`is_shrink_needed(size_type size, size_type num_entries) const;`
291
292			`typedef PB_ASSOC_SIZE_BASE_C_DEC my_size_base;`
293
294			`private:`
295			`inline std::pair<float, float>`
296			`get_loads_imp(pb_assoc::detail::int_to_type<true>) const;`
297
298			`void`
299			`set_loads_imp(std::pair<float, float>,`
300			`pb_assoc::detail::int_to_type<true>);`
301
302			`virtual void`
303			`do_resize(size_type new_size);`
304
305			`#ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG`
306			`void`
307			`assert_valid() const;`
308			`#endif // #ifdef PB_ASSOC_HT_LOAD_CHECK_RESIZE_TRIGGER_DEBUG`
309
310			`float m_load_min, m_load_max;`
311
312			`size_type m_next_shrink_size;`
313
314			`size_type m_next_grow_size;`
315
316			`bool m_resize_needed;`
317
318			`static pb_assoc::detail::int_to_type<External_Load_Access>`
319			`s_external_load_access_ind;`
320			`};`
321
322			`#include <ext/pb_assoc/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp>`
323
324			`#undef PB_ASSOC_CLASS_T_DEC`
325			`#undef PB_ASSOC_CLASS_C_DEC`
326
327			`#undef PB_ASSOC_SIZE_BASE_C_DEC`
328
329			`#undef PB_ASSOC_DBG_ASSERT`
330			`#undef PB_ASSOC_DBG_VERIFY`
331			`#undef PB_ASSOC_DBG_ONLY`
332
333			`#ifdef PB_ASSOC_HT_MAX_COLLISION_CHECK_RESIZE_TRIGGER_POLICY_DEBUG`
334			`#define PB_ASSOC_DBG_ASSERT(X) assert(X)`
335			`#define PB_ASSOC_DBG_VERIFY(X) assert(X)`
336			`#define PB_ASSOC_DBG_ONLY(X) X`
337			`#else // #ifdef PB_ASSOC_HT_MAX_COLLISION_CHECK_RESIZE_TRIGGER_POLICY_DEBUG`
338			`#define PB_ASSOC_DBG_ASSERT(X)`
339			`#define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}`
340			`#define PB_ASSOC_DBG_ONLY(X) ;`
341			`#endif // #ifdef PB_ASSOC_HT_MAX_COLLISION_CHECK_RESIZE_TRIGGER_POLICY_DEBUG`
342
343			`#define PB_ASSOC_CLASS_T_DEC \`
344			`template<bool External_Load_Access, typename Size_Type>`
345
346			`#define PB_ASSOC_CLASS_C_DEC \`
347			`cc_hash_max_collision_check_resize_trigger< \`
348			`External_Load_Access, \`
349			`Size_Type>`
350
351			`template<bool External_Load_Access = false, typename Size_Type = size_t>`
352			`class cc_hash_max_collision_check_resize_trigger`
353			`{`
354			`public:`
355			`typedef Size_Type size_type;`
356
357			`enum`
358			`{`
359			`external_load_access = External_Load_Access`
360			`};`
361
362			`cc_hash_max_collision_check_resize_trigger(float load = 0.5);`
363
364			`void`
365			`swap(PB_ASSOC_CLASS_C_DEC& r_other);`
366
367			`inline float`
368			`get_load() const;`
369
370			`protected:`
371			`inline void`
372			`notify_insert_search_start();`
373
374			`inline void`
375			`notify_insert_search_collision();`
376
377			`inline void`
378			`notify_insert_search_end();`
379
380			`inline void`
381			`notify_find_search_start();`
382
383			`inline void`
384			`notify_find_search_collision();`
385
386			`inline void`
387			`notify_find_search_end();`
388
389			`inline void`
390			`notify_erase_search_start();`
391
392			`inline void`
393			`notify_erase_search_collision();`
394
395			`inline void`
396			`notify_erase_search_end();`
397
398			`inline void`
399			`notify_inserted(size_type num_entries);`
400
401			`inline void`
402			`notify_erased(size_type num_entries);`
403
404			`void`
405			`notify_cleared();`
406
407			`void`
408			`notify_resized(size_type new_size);`
409
410			`void`
411			`notify_externally_resized(size_type new_size);`
412
413			`inline bool`
414			`is_resize_needed() const;`
415
416			`inline bool`
417			`is_grow_needed(size_type size, size_type num_entries) const;`
418
419			`inline bool`
420			`is_shrink_needed(size_type size, size_type num_entries) const;`
421
422			`private:`
423			`template<typename Key>`
424			`class max_col_checker`
425			`{`
426			`public:`
427			`max_col_checker(size_type size, size_type* p_max_col)`
428			`: m_p_max_col(p_max_col), m_a_col(size, 0)`
429			`{ }`
430
431			`void`
432			`operator()(const std::pair<const Key, size_type>& r_key_pos_pair)`
433			`{ ++m_a_col[r_key_pos_pair.second]; }`
434
435			`private:`
436			`std::vector<size_type> m_a_col;`
437
438			`size_type* const m_p_max_col;`
439			`};`
440
441			`private:`
442			`inline float`
443			`get_load_imp(pb_assoc::detail::int_to_type<true>) const;`
444
445			`float m_load;`
446
447			`size_type m_size;`
448
449			`size_type m_num_col;`
450
451			`size_type m_max_col;`
452
453			`bool m_resize_needed;`
454
455			`static pb_assoc::detail::int_to_type<External_Load_Access>`
456			`s_external_load_access_ind;`
457			`};`
458
459			`#include <ext/pb_assoc/detail/resize_policy/cc_hash_max_collision_resize_trigger_imp.hpp>`
460
461			`#undef PB_ASSOC_CLASS_T_DEC`
462			`#undef PB_ASSOC_CLASS_C_DEC`
463
464			`#undef PB_ASSOC_DBG_ASSERT`
465			`#undef PB_ASSOC_DBG_VERIFY`
466			`#undef PB_ASSOC_DBG_ONLY`
467
468			`#define PB_ASSOC_CLASS_T_DEC \`
469			`template<typename Size_Type>`
470
471			`#define PB_ASSOC_CLASS_C_DEC \`
472			`hash_exponential_size_policy< \`
473			`Size_Type>`
474
475			`template<typename Size_Type = size_t>`
476			`class hash_exponential_size_policy`
477			`{`
478			`public:`
479			`typedef Size_Type size_type;`
480
481			`hash_exponential_size_policy(size_type start_size = 8,`
482			`size_type grow_factor = 2);`
483
484			`void`
485			`swap(PB_ASSOC_CLASS_C_DEC& r_other);`
486
487			`protected:`
488			`size_type`
489			`get_init_size(size_type suggested_size) const;`
490
491			`size_type`
492			`get_nearest_larger_size(size_type cur_size) const;`
493
494			`size_type`
495			`get_nearest_smaller_size(size_type cur_size) const;`
496
497			`#ifdef PB_ASSOC_HT_EXPONENTIAL_SIZE_POLICY_DEBUG`
498			`void`
499			`assert_is_one_of_my_sizes(size_type size) const;`
500			`#endif // #ifdef PB_ASSOC_HT_EXPONENTIAL_SIZE_POLICY_DEBUG`
501
502			`private:`
503			`size_type m_start_size;`
504			`size_type m_grow_factor;`
505			`};`
506
507			`#include <ext/pb_assoc/detail/resize_policy/hash_exponential_size_policy_imp.hpp>`
508
509			`#undef PB_ASSOC_CLASS_T_DEC`
510			`#undef PB_ASSOC_CLASS_C_DEC`
511
512			`#undef PB_ASSOC_DBG_ASSERT`
513			`#undef PB_ASSOC_DBG_VERIFY`
514			`#undef PB_ASSOC_DBG_ONLY`
515
516			`#define PB_ASSOC_CLASS_T_DEC`
517
518			`#define PB_ASSOC_CLASS_C_DEC \`
519			`hash_prime_size_policy`
520
521			`#ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG`
522			`#define PB_ASSOC_DBG_ASSERT(X) assert(X)`
523			`#define PB_ASSOC_DBG_VERIFY(X) assert(X)`
524			`#define PB_ASSOC_DBG_ONLY(X) X`
525			`#else // #ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG`
526			`#define PB_ASSOC_DBG_ASSERT(X)`
527			`#define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}`
528			`#define PB_ASSOC_DBG_ONLY(X) ;`
529			`#endif // #ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG`
530
531			`struct hash_prime_size_policy`
532			`{`
533			`typedef size_t size_type;`
534
535			`inline void`
536			`swap(PB_ASSOC_CLASS_C_DEC& r_other);`
537
538			`protected:`
539			`inline size_type`
540			`get_init_size(size_type suggested_size) const;`
541
542			`inline size_type`
543			`get_nearest_larger_size(size_type cur_size) const;`
544
545			`inline size_type`
546			`get_nearest_smaller_size(size_type cur_size) const;`
547
548			`inline size_type`
549			`get_nearest_larger_size_imp(size_type size) const;`
550
551			`#ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG`
552			`void`
553			`assert_is_one_of_my_sizes(size_type size) const;`
554			`#endif // #ifdef PB_ASSOC_HT_PRIME_SIZE_POLICY_DEBUG`
555			`};`
556
557			`#include <ext/pb_assoc/detail/resize_policy/hash_prime_size_policy_imp.hpp>`
558
559			`#undef PB_ASSOC_CLASS_T_DEC`
560			`#undef PB_ASSOC_CLASS_C_DEC`
561
562			`#undef PB_ASSOC_DBG_ASSERT`
563			`#undef PB_ASSOC_DBG_VERIFY`
564			`#undef PB_ASSOC_DBG_ONLY`
565
566			`#define PB_ASSOC_CLASS_T_DEC \`
567			`template< \`
568			`class Size_Policy, \`
569			`class Trigger_Policy, \`
570			`bool External_Size_Access, \`
571			`typename Size_Type>`
572
573			`#define PB_ASSOC_CLASS_C_DEC \`
574			`hash_standard_resize_policy< \`
575			`Size_Policy, \`
576			`Trigger_Policy, \`
577			`External_Size_Access, \`
578			`Size_Type>`
579
580			`template<class Size_Policy = pb_assoc::hash_exponential_size_policy<>,`
581			`class Trigger_Policy = pb_assoc::hash_load_check_resize_trigger<>,`
582			`bool External_Size_Access = false,`
583			`typename Size_Type = size_t>`
584			`class hash_standard_resize_policy : public Size_Policy, public Trigger_Policy`
585			`{`
586			`public:`
587			`typedef Size_Type size_type;`
588			`typedef Trigger_Policy trigger_policy;`
589			`typedef Size_Policy size_policy;`
590
591			`enum`
592			`{`
593			`external_size_access = External_Size_Access`
594			`};`
595
596			`hash_standard_resize_policy(size_type suggested_size = 8);`
597
598			`hash_standard_resize_policy(const Size_Policy&,`
599			`size_type suggested_size = 8);`
600
601			`hash_standard_resize_policy(const Size_Policy&, const Trigger_Policy&,`
602			`size_type suggested_size = 8);`
603
604			`virtual`
605			`~hash_standard_resize_policy();`
606
607			`inline void`
608			`swap(PB_ASSOC_CLASS_C_DEC& r_other);`
609
610			`Size_Policy&`
611			`get_size_policy();`
612
613			`const Size_Policy&`
614			`get_size_policy() const;`
615
616			`Trigger_Policy&`
617			`get_trigger_policy();`
618
619			`const Trigger_Policy&`
620			`get_trigger_policy() const;`
621
622			`inline size_type`
623			`get_actual_size() const;`
624
625			`void`
626			`resize(size_type suggested_new_size);`
627
628			`protected:`
629
630			`inline void`
631			`notify_insert_search_start();`
632
633			`inline void`
634			`notify_insert_search_collision();`
635
636			`inline void`
637			`notify_insert_search_end();`
638
639			`inline void`
640			`notify_find_search_start();`
641
642			`inline void`
643			`notify_find_search_collision();`
644
645			`inline void`
646			`notify_find_search_end();`
647
648			`inline void`
649			`notify_erase_search_start();`
650
651			`inline void`
652			`notify_erase_search_collision();`
653
654			`inline void`
655			`notify_erase_search_end();`
656
657			`inline void`
658			`notify_inserted(size_type num_e);`
659
660			`inline void`
661			`notify_erased(size_type num_e);`
662
663			`void`
664			`notify_cleared();`
665
666			`void`
667			`notify_resized(size_type new_size);`
668
669			`size_type`
670			`get_init_size() const;`
671
672			`inline bool`
673			`is_resize_needed() const;`
674
675			`size_type`
676			`get_new_size(size_type size, size_type num_used_e) const;`
677
678			`private:`
679			`typedef Trigger_Policy my_trigger_policy_base;`
680
681			`typedef Size_Policy my_size_policy_base;`
682
683			`typedef`
684			`pb_assoc::detail::int_to_type<false>`
685			`external_resize_false_indicator;`
686
687			`typedef`
688			`pb_assoc::detail::int_to_type<true>`
689			`external_resize_true_indicator;`
690
691			`inline size_type`
692			`get_actual_size(external_resize_true_indicator) const;`
693
694			`void`
695			`resize(size_type new_size, external_resize_true_indicator);`
696
697			`virtual void`
698			`do_resize(size_type new_size);`
699
700			`static pb_assoc::detail::int_to_type<External_Size_Access>`
701			`s_external_size_access_indicator;`
702
703			`size_type m_size;`
704			`};`
705
706			`#include <ext/pb_assoc/detail/resize_policy/hash_standard_resize_policy_imp.hpp>`
707
708			`#undef PB_ASSOC_CLASS_T_DEC`
709			`#undef PB_ASSOC_CLASS_C_DEC`
710
711			`#undef PB_ASSOC_DBG_ASSERT`
712			`#undef PB_ASSOC_DBG_VERIFY`
713			`#undef PB_ASSOC_DBG_ONLY`
714
715			`} // namespace pb_assoc`
716
717			`#endif // #ifndef HASH_POLICY_HPP`