| /contrib/sdk/sources/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/cc_hash_max_collision_check_resize_trigger_imp.hpp |
|---|
| 0,0 → 1,211 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2013 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 cc_hash_max_collision_check_resize_trigger_imp.hpp |
| * Contains a resize trigger implementation. |
| */ |
| PB_DS_CLASS_T_DEC |
| PB_DS_CLASS_C_DEC:: |
| cc_hash_max_collision_check_resize_trigger(float load) : |
| m_load(load), |
| m_size(0), |
| m_num_col(0), |
| m_max_col(0), |
| m_resize_needed(false) |
| { } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_find_search_start() |
| { } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_find_search_collision() |
| { } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_find_search_end() |
| { } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_insert_search_start() |
| { m_num_col = 0; } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_insert_search_collision() |
| { ++m_num_col; } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_insert_search_end() |
| { calc_resize_needed(); } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_erase_search_start() |
| { } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_erase_search_collision() |
| { } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_erase_search_end() |
| { } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_inserted(size_type) |
| { } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_erased(size_type) |
| { m_resize_needed = true; } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| notify_cleared() |
| { m_resize_needed = false; } |
| PB_DS_CLASS_T_DEC |
| inline bool |
| PB_DS_CLASS_C_DEC:: |
| is_resize_needed() const |
| { return m_resize_needed; } |
| PB_DS_CLASS_T_DEC |
| inline bool |
| PB_DS_CLASS_C_DEC:: |
| is_grow_needed(size_type /*size*/, size_type /*num_used_e*/) const |
| { return m_num_col >= m_max_col; } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| notify_resized(size_type new_size) |
| { |
| m_size = new_size; |
| #ifdef PB_DS_HT_MAP_RESIZE_TRACE_ |
| std::cerr << "chmccrt::notify_resized " |
| << static_cast<unsigned long>(new_size) << std::endl; |
| #endif |
| calc_max_num_coll(); |
| calc_resize_needed(); |
| m_num_col = 0; |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| calc_max_num_coll() |
| { |
| // max_col <-- \sqrt{2 load \ln( 2 m \ln( m ) ) } |
| const double ln_arg = 2 * m_size * std::log(double(m_size)); |
| m_max_col = size_type(std::ceil(std::sqrt(2 * m_load * std::log(ln_arg)))); |
| #ifdef PB_DS_HT_MAP_RESIZE_TRACE_ |
| std::cerr << "chmccrt::calc_max_num_coll " |
| << static_cast<unsigned long>(m_size) << " " |
| << static_cast<unsigned long>(m_max_col) << std::endl; |
| #endif |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| notify_externally_resized(size_type new_size) |
| { notify_resized(new_size); } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| swap(PB_DS_CLASS_C_DEC& other) |
| { |
| std::swap(m_load, other.m_load); |
| std::swap(m_size, other.m_size); |
| std::swap(m_num_col, other.m_num_col); |
| std::swap(m_max_col, other.m_max_col); |
| std::swap(m_resize_needed, other.m_resize_needed); |
| } |
| PB_DS_CLASS_T_DEC |
| inline float |
| PB_DS_CLASS_C_DEC:: |
| get_load() const |
| { |
| PB_DS_STATIC_ASSERT(access, external_load_access); |
| return m_load; |
| } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| calc_resize_needed() |
| { m_resize_needed = m_resize_needed || m_num_col >= m_max_col; } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| set_load(float load) |
| { |
| PB_DS_STATIC_ASSERT(access, external_load_access); |
| m_load = load; |
| calc_max_num_coll(); |
| calc_resize_needed(); |
| } |
| /contrib/sdk/sources/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/hash_exponential_size_policy_imp.hpp |
|---|
| 0,0 → 1,90 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2013 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_exponential_size_policy_imp.hpp |
| * Contains a resize size policy implementation. |
| */ |
| PB_DS_CLASS_T_DEC |
| PB_DS_CLASS_C_DEC:: |
| hash_exponential_size_policy(size_type start_size, size_type grow_factor) : |
| m_start_size(start_size), |
| m_grow_factor(grow_factor) |
| { } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| swap(PB_DS_CLASS_C_DEC& other) |
| { |
| std::swap(m_start_size, other.m_start_size); |
| std::swap(m_grow_factor, other.m_grow_factor); |
| } |
| PB_DS_CLASS_T_DEC |
| typename PB_DS_CLASS_C_DEC::size_type |
| PB_DS_CLASS_C_DEC:: |
| get_nearest_larger_size(size_type size) const |
| { |
| size_type ret = m_start_size; |
| while (ret <= size) |
| { |
| const size_type next_ret = ret* m_grow_factor; |
| if (next_ret < ret) |
| __throw_insert_error(); |
| ret = next_ret; |
| } |
| return ret; |
| } |
| PB_DS_CLASS_T_DEC |
| typename PB_DS_CLASS_C_DEC::size_type |
| PB_DS_CLASS_C_DEC:: |
| get_nearest_smaller_size(size_type size) const |
| { |
| size_type ret = m_start_size; |
| while (true) |
| { |
| const size_type next_ret = ret* m_grow_factor; |
| if (next_ret < ret) |
| __throw_resize_error(); |
| if (next_ret >= size) |
| return (ret); |
| ret = next_ret; |
| } |
| return ret; |
| } |
| /contrib/sdk/sources/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp |
|---|
| 0,0 → 1,293 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2013 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_load_check_resize_trigger_imp.hpp |
| * Contains a resize trigger implementation. |
| */ |
| #define PB_DS_ASSERT_VALID(X) \ |
| _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);) |
| PB_DS_CLASS_T_DEC |
| PB_DS_CLASS_C_DEC:: |
| hash_load_check_resize_trigger(float load_min, float load_max) |
| : m_load_min(load_min), m_load_max(load_max), m_next_shrink_size(0), |
| m_next_grow_size(0), m_resize_needed(false) |
| { PB_DS_ASSERT_VALID((*this)) } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_find_search_start() |
| { PB_DS_ASSERT_VALID((*this)) } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_find_search_collision() |
| { PB_DS_ASSERT_VALID((*this)) } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_find_search_end() |
| { PB_DS_ASSERT_VALID((*this)) } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_insert_search_start() |
| { PB_DS_ASSERT_VALID((*this)) } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_insert_search_collision() |
| { PB_DS_ASSERT_VALID((*this)) } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_insert_search_end() |
| { PB_DS_ASSERT_VALID((*this)) } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_erase_search_start() |
| { PB_DS_ASSERT_VALID((*this)) } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_erase_search_collision() |
| { PB_DS_ASSERT_VALID((*this)) } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_erase_search_end() |
| { PB_DS_ASSERT_VALID((*this)) } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_inserted(size_type num_entries) |
| { |
| m_resize_needed = (num_entries >= m_next_grow_size); |
| size_base::set_size(num_entries); |
| PB_DS_ASSERT_VALID((*this)) |
| } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_erased(size_type num_entries) |
| { |
| size_base::set_size(num_entries); |
| m_resize_needed = num_entries <= m_next_shrink_size; |
| PB_DS_ASSERT_VALID((*this)) |
| } |
| PB_DS_CLASS_T_DEC |
| inline bool |
| PB_DS_CLASS_C_DEC:: |
| is_resize_needed() const |
| { |
| PB_DS_ASSERT_VALID((*this)) |
| return m_resize_needed; |
| } |
| PB_DS_CLASS_T_DEC |
| inline bool |
| PB_DS_CLASS_C_DEC:: |
| is_grow_needed(size_type /*size*/, size_type num_entries) const |
| { |
| _GLIBCXX_DEBUG_ASSERT(m_resize_needed); |
| return num_entries >= m_next_grow_size; |
| } |
| PB_DS_CLASS_T_DEC |
| PB_DS_CLASS_C_DEC:: |
| ~hash_load_check_resize_trigger() { } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| notify_resized(size_type new_size) |
| { |
| m_resize_needed = false; |
| m_next_grow_size = size_type(m_load_max * new_size - 1); |
| m_next_shrink_size = size_type(m_load_min * new_size); |
| #ifdef PB_DS_HT_MAP_RESIZE_TRACE_ |
| std::cerr << "hlcrt::notify_resized " << std::endl |
| << "1 " << new_size << std::endl |
| << "2 " << m_load_min << std::endl |
| << "3 " << m_load_max << std::endl |
| << "4 " << m_next_shrink_size << std::endl |
| << "5 " << m_next_grow_size << std::endl; |
| #endif |
| PB_DS_ASSERT_VALID((*this)) |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| notify_externally_resized(size_type new_size) |
| { |
| m_resize_needed = false; |
| size_type new_grow_size = size_type(m_load_max * new_size - 1); |
| size_type new_shrink_size = size_type(m_load_min * new_size); |
| #ifdef PB_DS_HT_MAP_RESIZE_TRACE_ |
| std::cerr << "hlcrt::notify_externally_resized " << std::endl |
| << "1 " << new_size << std::endl |
| << "2 " << m_load_min << std::endl |
| << "3 " << m_load_max << std::endl |
| << "4 " << m_next_shrink_size << std::endl |
| << "5 " << m_next_grow_size << std::endl |
| << "6 " << new_shrink_size << std::endl |
| << "7 " << new_grow_size << std::endl; |
| #endif |
| if (new_grow_size >= m_next_grow_size) |
| { |
| _GLIBCXX_DEBUG_ASSERT(new_shrink_size >= m_next_shrink_size); |
| m_next_grow_size = new_grow_size; |
| } |
| else |
| { |
| _GLIBCXX_DEBUG_ASSERT(new_shrink_size <= m_next_shrink_size); |
| m_next_shrink_size = new_shrink_size; |
| } |
| PB_DS_ASSERT_VALID((*this)) |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| notify_cleared() |
| { |
| PB_DS_ASSERT_VALID((*this)) |
| size_base::set_size(0); |
| m_resize_needed = (0 < m_next_shrink_size); |
| PB_DS_ASSERT_VALID((*this)) |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| swap(PB_DS_CLASS_C_DEC& other) |
| { |
| PB_DS_ASSERT_VALID((*this)) |
| PB_DS_ASSERT_VALID(other) |
| size_base::swap(other); |
| std::swap(m_load_min, other.m_load_min); |
| std::swap(m_load_max, other.m_load_max); |
| std::swap(m_resize_needed, other.m_resize_needed); |
| std::swap(m_next_grow_size, other.m_next_grow_size); |
| std::swap(m_next_shrink_size, other.m_next_shrink_size); |
| PB_DS_ASSERT_VALID((*this)) |
| PB_DS_ASSERT_VALID(other) |
| } |
| PB_DS_CLASS_T_DEC |
| inline std::pair<float, float> |
| PB_DS_CLASS_C_DEC:: |
| get_loads() const |
| { |
| PB_DS_STATIC_ASSERT(access, external_load_access); |
| return std::make_pair(m_load_min, m_load_max); |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| set_loads(std::pair<float, float> load_pair) |
| { |
| PB_DS_STATIC_ASSERT(access, external_load_access); |
| const float old_load_min = m_load_min; |
| const float old_load_max = m_load_max; |
| const size_type old_next_shrink_size = m_next_shrink_size; |
| const size_type old_next_grow_size = m_next_grow_size; |
| const bool old_resize_needed = m_resize_needed; |
| __try |
| { |
| m_load_min = load_pair.first; |
| m_load_max = load_pair.second; |
| do_resize(static_cast<size_type>(size_base::get_size() / ((m_load_min + m_load_max) / 2))); |
| } |
| __catch(...) |
| { |
| m_load_min = old_load_min; |
| m_load_max = old_load_max; |
| m_next_shrink_size = old_next_shrink_size; |
| m_next_grow_size = old_next_grow_size; |
| m_resize_needed = old_resize_needed; |
| __throw_exception_again; |
| } |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| do_resize(size_type) |
| { std::abort(); } |
| #ifdef _GLIBCXX_DEBUG |
| # define PB_DS_DEBUG_VERIFY(_Cond) \ |
| _GLIBCXX_DEBUG_VERIFY_AT(_Cond, \ |
| _M_message(#_Cond" assertion from %1;:%2;") \ |
| ._M_string(__FILE__)._M_integer(__LINE__) \ |
| ,__file,__line) |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| assert_valid(const char* __file, int __line) const |
| { |
| PB_DS_DEBUG_VERIFY(m_load_max > m_load_min); |
| PB_DS_DEBUG_VERIFY(m_next_grow_size >= m_next_shrink_size); |
| } |
| # undef PB_DS_DEBUG_VERIFY |
| #endif |
| #undef PB_DS_ASSERT_VALID |
| /contrib/sdk/sources/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_size_base.hpp |
|---|
| 0,0 → 1,94 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2013 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_load_check_resize_trigger_size_base.hpp |
| * Contains an base holding size for some resize policies. |
| */ |
| #ifndef PB_DS_HASH_LOAD_CHECK_RESIZE_TRIGGER_SIZE_BASE_HPP |
| #define PB_DS_HASH_LOAD_CHECK_RESIZE_TRIGGER_SIZE_BASE_HPP |
| namespace __gnu_pbds |
| { |
| namespace detail |
| { |
| /// Primary template. |
| template<typename Size_Type, bool Hold_Size> |
| class hash_load_check_resize_trigger_size_base; |
| /// Specializations. |
| template<typename Size_Type> |
| class hash_load_check_resize_trigger_size_base<Size_Type, true> |
| { |
| protected: |
| typedef Size_Type size_type; |
| hash_load_check_resize_trigger_size_base(): m_size(0) |
| { } |
| inline void |
| swap(hash_load_check_resize_trigger_size_base& other) |
| { std::swap(m_size, other.m_size); } |
| inline void |
| set_size(size_type size) |
| { m_size = size; } |
| inline size_type |
| get_size() const |
| { return m_size; } |
| private: |
| size_type m_size; |
| }; |
| template<typename Size_Type> |
| class hash_load_check_resize_trigger_size_base<Size_Type, false> |
| { |
| protected: |
| typedef Size_Type size_type; |
| protected: |
| inline void |
| swap(hash_load_check_resize_trigger_size_base& other) { } |
| inline void |
| set_size(size_type size) { } |
| }; |
| } // namespace detail |
| } // namespace __gnu_pbds |
| #endif |
| /contrib/sdk/sources/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/hash_prime_size_policy_imp.hpp |
|---|
| 0,0 → 1,161 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2013 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_prime_size_policy_imp.hpp |
| * Contains a resize size policy implementation. |
| */ |
| #pragma GCC system_header |
| namespace detail |
| { |
| enum |
| { |
| num_distinct_sizes_32_bit = 30, |
| num_distinct_sizes_64_bit = 62, |
| num_distinct_sizes = sizeof(std::size_t) != 8 ? |
| num_distinct_sizes_32_bit : num_distinct_sizes_64_bit, |
| }; |
| // Originally taken from the SGI implementation; acknowledged in the docs. |
| // Further modified (for 64 bits) from tr1's hashtable. |
| static const std::size_t g_a_sizes[num_distinct_sizes_64_bit] = |
| { |
| /* 0 */ 5ul, |
| /* 1 */ 11ul, |
| /* 2 */ 23ul, |
| /* 3 */ 47ul, |
| /* 4 */ 97ul, |
| /* 5 */ 199ul, |
| /* 6 */ 409ul, |
| /* 7 */ 823ul, |
| /* 8 */ 1741ul, |
| /* 9 */ 3469ul, |
| /* 10 */ 6949ul, |
| /* 11 */ 14033ul, |
| /* 12 */ 28411ul, |
| /* 13 */ 57557ul, |
| /* 14 */ 116731ul, |
| /* 15 */ 236897ul, |
| /* 16 */ 480881ul, |
| /* 17 */ 976369ul, |
| /* 18 */ 1982627ul, |
| /* 19 */ 4026031ul, |
| /* 20 */ 8175383ul, |
| /* 21 */ 16601593ul, |
| /* 22 */ 33712729ul, |
| /* 23 */ 68460391ul, |
| /* 24 */ 139022417ul, |
| /* 25 */ 282312799ul, |
| /* 26 */ 573292817ul, |
| /* 27 */ 1164186217ul, |
| /* 28 */ 2364114217ul, |
| /* 29 */ 4294967291ul, |
| /* 30 */ (std::size_t)8589934583ull, |
| /* 31 */ (std::size_t)17179869143ull, |
| /* 32 */ (std::size_t)34359738337ull, |
| /* 33 */ (std::size_t)68719476731ull, |
| /* 34 */ (std::size_t)137438953447ull, |
| /* 35 */ (std::size_t)274877906899ull, |
| /* 36 */ (std::size_t)549755813881ull, |
| /* 37 */ (std::size_t)1099511627689ull, |
| /* 38 */ (std::size_t)2199023255531ull, |
| /* 39 */ (std::size_t)4398046511093ull, |
| /* 40 */ (std::size_t)8796093022151ull, |
| /* 41 */ (std::size_t)17592186044399ull, |
| /* 42 */ (std::size_t)35184372088777ull, |
| /* 43 */ (std::size_t)70368744177643ull, |
| /* 44 */ (std::size_t)140737488355213ull, |
| /* 45 */ (std::size_t)281474976710597ull, |
| /* 46 */ (std::size_t)562949953421231ull, |
| /* 47 */ (std::size_t)1125899906842597ull, |
| /* 48 */ (std::size_t)2251799813685119ull, |
| /* 49 */ (std::size_t)4503599627370449ull, |
| /* 50 */ (std::size_t)9007199254740881ull, |
| /* 51 */ (std::size_t)18014398509481951ull, |
| /* 52 */ (std::size_t)36028797018963913ull, |
| /* 53 */ (std::size_t)72057594037927931ull, |
| /* 54 */ (std::size_t)144115188075855859ull, |
| /* 55 */ (std::size_t)288230376151711717ull, |
| /* 56 */ (std::size_t)576460752303423433ull, |
| /* 57 */ (std::size_t)1152921504606846883ull, |
| /* 58 */ (std::size_t)2305843009213693951ull, |
| /* 59 */ (std::size_t)4611686018427387847ull, |
| /* 60 */ (std::size_t)9223372036854775783ull, |
| /* 61 */ (std::size_t)18446744073709551557ull, |
| }; |
| } // namespace detail |
| PB_DS_CLASS_T_DEC |
| inline |
| PB_DS_CLASS_C_DEC:: |
| hash_prime_size_policy(size_type n) : m_start_size(n) |
| { m_start_size = get_nearest_larger_size(n); } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| swap(PB_DS_CLASS_C_DEC& other) |
| { std::swap(m_start_size, other.m_start_size); } |
| PB_DS_CLASS_T_DEC |
| inline PB_DS_CLASS_C_DEC::size_type |
| PB_DS_CLASS_C_DEC:: |
| get_nearest_larger_size(size_type n) const |
| { |
| const std::size_t* const p_upper = std::upper_bound(detail::g_a_sizes, |
| detail::g_a_sizes + detail::num_distinct_sizes, n); |
| if (p_upper == detail::g_a_sizes + detail::num_distinct_sizes) |
| __throw_resize_error(); |
| return *p_upper; |
| } |
| PB_DS_CLASS_T_DEC |
| inline PB_DS_CLASS_C_DEC::size_type |
| PB_DS_CLASS_C_DEC:: |
| get_nearest_smaller_size(size_type n) const |
| { |
| const std::size_t* p_lower = std::lower_bound(detail::g_a_sizes, |
| detail::g_a_sizes + detail::num_distinct_sizes, n); |
| if (*p_lower >= n && p_lower != detail::g_a_sizes) |
| --p_lower; |
| if (*p_lower < m_start_size) |
| return m_start_size; |
| return *p_lower; |
| } |
| /contrib/sdk/sources/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/hash_standard_resize_policy_imp.hpp |
|---|
| 0,0 → 1,249 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2013 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_standard_resize_policy_imp.hpp |
| * Contains a resize policy implementation. |
| */ |
| PB_DS_CLASS_T_DEC |
| PB_DS_CLASS_C_DEC:: |
| hash_standard_resize_policy() |
| : m_size(Size_Policy::get_nearest_larger_size(1)) |
| { trigger_policy_base::notify_externally_resized(m_size); } |
| PB_DS_CLASS_T_DEC |
| PB_DS_CLASS_C_DEC:: |
| hash_standard_resize_policy(const Size_Policy& r_size_policy) |
| : Size_Policy(r_size_policy), m_size(Size_Policy::get_nearest_larger_size(1)) |
| { trigger_policy_base::notify_externally_resized(m_size); } |
| PB_DS_CLASS_T_DEC |
| PB_DS_CLASS_C_DEC:: |
| hash_standard_resize_policy(const Size_Policy& r_size_policy, |
| const Trigger_Policy& r_trigger_policy) |
| : Size_Policy(r_size_policy), Trigger_Policy(r_trigger_policy), |
| m_size(Size_Policy::get_nearest_larger_size(1)) |
| { trigger_policy_base::notify_externally_resized(m_size); } |
| PB_DS_CLASS_T_DEC |
| PB_DS_CLASS_C_DEC:: |
| ~hash_standard_resize_policy() |
| { } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| swap(PB_DS_CLASS_C_DEC& other) |
| { |
| trigger_policy_base::swap(other); |
| size_policy_base::swap(other); |
| std::swap(m_size, other.m_size); |
| } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_find_search_start() |
| { trigger_policy_base::notify_find_search_start(); } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_find_search_collision() |
| { trigger_policy_base::notify_find_search_collision(); } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_find_search_end() |
| { trigger_policy_base::notify_find_search_end(); } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_insert_search_start() |
| { trigger_policy_base::notify_insert_search_start(); } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_insert_search_collision() |
| { trigger_policy_base::notify_insert_search_collision(); } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_insert_search_end() |
| { trigger_policy_base::notify_insert_search_end(); } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_erase_search_start() |
| { trigger_policy_base::notify_erase_search_start(); } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_erase_search_collision() |
| { trigger_policy_base::notify_erase_search_collision(); } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_erase_search_end() |
| { trigger_policy_base::notify_erase_search_end(); } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_inserted(size_type num_e) |
| { trigger_policy_base::notify_inserted(num_e); } |
| PB_DS_CLASS_T_DEC |
| inline void |
| PB_DS_CLASS_C_DEC:: |
| notify_erased(size_type num_e) |
| { trigger_policy_base::notify_erased(num_e); } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| notify_cleared() |
| { trigger_policy_base::notify_cleared(); } |
| PB_DS_CLASS_T_DEC |
| inline bool |
| PB_DS_CLASS_C_DEC:: |
| is_resize_needed() const |
| { return trigger_policy_base::is_resize_needed(); } |
| PB_DS_CLASS_T_DEC |
| typename PB_DS_CLASS_C_DEC::size_type |
| PB_DS_CLASS_C_DEC:: |
| get_new_size(size_type size, size_type num_used_e) const |
| { |
| if (trigger_policy_base::is_grow_needed(size, num_used_e)) |
| return size_policy_base::get_nearest_larger_size(size); |
| return size_policy_base::get_nearest_smaller_size(size); |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| notify_resized(size_type new_size) |
| { |
| trigger_policy_base::notify_resized(new_size); |
| m_size = new_size; |
| } |
| PB_DS_CLASS_T_DEC |
| inline typename PB_DS_CLASS_C_DEC::size_type |
| PB_DS_CLASS_C_DEC:: |
| get_actual_size() const |
| { |
| PB_DS_STATIC_ASSERT(access, external_size_access); |
| return m_size; |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| resize(size_type new_size) |
| { |
| PB_DS_STATIC_ASSERT(access, external_size_access); |
| size_type actual_size = size_policy_base::get_nearest_larger_size(1); |
| while (actual_size < new_size) |
| { |
| const size_type pot = size_policy_base::get_nearest_larger_size(actual_size); |
| if (pot == actual_size && pot < new_size) |
| __throw_resize_error(); |
| actual_size = pot; |
| } |
| if (actual_size > 0) |
| --actual_size; |
| const size_type old_size = m_size; |
| __try |
| { |
| do_resize(actual_size - 1); |
| } |
| __catch(insert_error& ) |
| { |
| m_size = old_size; |
| __throw_resize_error(); |
| } |
| __catch(...) |
| { |
| m_size = old_size; |
| __throw_exception_again; |
| } |
| } |
| PB_DS_CLASS_T_DEC |
| void |
| PB_DS_CLASS_C_DEC:: |
| do_resize(size_type) |
| { |
| // Do nothing |
| } |
| PB_DS_CLASS_T_DEC |
| Trigger_Policy& |
| PB_DS_CLASS_C_DEC:: |
| get_trigger_policy() |
| { return *this; } |
| PB_DS_CLASS_T_DEC |
| const Trigger_Policy& |
| PB_DS_CLASS_C_DEC:: |
| get_trigger_policy() const |
| { return *this; } |
| PB_DS_CLASS_T_DEC |
| Size_Policy& |
| PB_DS_CLASS_C_DEC:: |
| get_size_policy() |
| { return *this; } |
| PB_DS_CLASS_T_DEC |
| const Size_Policy& |
| PB_DS_CLASS_C_DEC:: |
| get_size_policy() const |
| { return *this; } |
| /contrib/sdk/sources/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_resize_policy.hpp |
|---|
| 0,0 → 1,125 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2013 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 sample_resize_policy.hpp |
| * Contains a sample resize policy for hash tables. |
| */ |
| #ifndef PB_DS_SAMPLE_RESIZE_POLICY_HPP |
| #define PB_DS_SAMPLE_RESIZE_POLICY_HPP |
| namespace __gnu_pbds |
| { |
| /// A sample resize policy. |
| class sample_resize_policy |
| { |
| public: |
| /// Size type. |
| typedef std::size_t size_type; |
| /// Default constructor. |
| sample_resize_policy(); |
| /// Copy constructor. |
| sample_range_hashing(const sample_resize_policy& other); |
| /// Swaps content. |
| inline void |
| swap(sample_resize_policy& other); |
| protected: |
| /// Notifies a search started. |
| inline void |
| notify_insert_search_start(); |
| /// Notifies a search encountered a collision. |
| inline void |
| notify_insert_search_collision(); |
| /// Notifies a search ended. |
| inline void |
| notify_insert_search_end(); |
| /// Notifies a search started. |
| inline void |
| notify_find_search_start(); |
| /// Notifies a search encountered a collision. |
| inline void |
| notify_find_search_collision(); |
| /// Notifies a search ended. |
| inline void |
| notify_find_search_end(); |
| /// Notifies a search started. |
| inline void |
| notify_erase_search_start(); |
| /// Notifies a search encountered a collision. |
| inline void |
| notify_erase_search_collision(); |
| /// Notifies a search ended. |
| inline void |
| notify_erase_search_end(); |
| /// Notifies an element was inserted. |
| inline void |
| notify_inserted(size_type num_e); |
| /// Notifies an element was erased. |
| inline void |
| notify_erased(size_type num_e); |
| /// Notifies the table was cleared. |
| void |
| notify_cleared(); |
| /// Notifies the table was resized to new_size. |
| void |
| notify_resized(size_type new_size); |
| /// Queries whether a resize is needed. |
| inline bool |
| is_resize_needed() const; |
| /// Queries what the new size should be. |
| size_type |
| get_new_size(size_type size, size_type num_used_e) const; |
| }; |
| } |
| #endif |
| /contrib/sdk/sources/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_resize_trigger.hpp |
|---|
| 0,0 → 1,136 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2013 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 sample_resize_trigger.hpp |
| * Contains a sample resize trigger policy class. |
| */ |
| #ifndef PB_DS_SAMPLE_RESIZE_TRIGGER_HPP |
| #define PB_DS_SAMPLE_RESIZE_TRIGGER_HPP |
| namespace __gnu_pbds |
| { |
| /// A sample resize trigger policy. |
| class sample_resize_trigger |
| { |
| public: |
| /// Size type. |
| typedef std::size_t size_type; |
| /// Default constructor. |
| sample_resize_trigger(); |
| /// Copy constructor. |
| sample_range_hashing(const sample_resize_trigger&); |
| /// Swaps content. |
| inline void |
| swap(sample_resize_trigger&); |
| protected: |
| /// Notifies a search started. |
| inline void |
| notify_insert_search_start(); |
| /// Notifies a search encountered a collision. |
| inline void |
| notify_insert_search_collision(); |
| /// Notifies a search ended. |
| inline void |
| notify_insert_search_end(); |
| /// Notifies a search started. |
| inline void |
| notify_find_search_start(); |
| /// Notifies a search encountered a collision. |
| inline void |
| notify_find_search_collision(); |
| /// Notifies a search ended. |
| inline void |
| notify_find_search_end(); |
| /// Notifies a search started. |
| inline void |
| notify_erase_search_start(); |
| /// Notifies a search encountered a collision. |
| inline void |
| notify_erase_search_collision(); |
| /// Notifies a search ended. |
| 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); |
| /// Notifies an element was erased. |
| 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); |
| /// Notifies the table was resized externally. |
| void |
| notify_externally_resized(size_type new_size); |
| /// Queries whether a resize is needed. |
| inline bool |
| is_resize_needed() const; |
| /// Queries whether a grow is needed. |
| inline bool |
| is_grow_needed(size_type size, size_type num_entries) const; |
| private: |
| /// Resizes to new_size. |
| virtual void |
| do_resize(size_type); |
| }; |
| } |
| #endif |
| /contrib/sdk/sources/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/sample_size_policy.hpp |
|---|
| 0,0 → 1,73 |
| // -*- C++ -*- |
| // Copyright (C) 2005-2013 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 sample_size_policy.hpp |
| * Contains a sample size resize-policy. |
| */ |
| #ifndef PB_DS_SAMPLE_SIZE_POLICY_HPP |
| #define PB_DS_SAMPLE_SIZE_POLICY_HPP |
| namespace __gnu_pbds |
| { |
| /// A sample size policy. |
| class sample_size_policy |
| { |
| public: |
| /// Size type. |
| typedef std::size_t size_type; |
| /// Default constructor. |
| sample_size_policy(); |
| /// Copy constructor. |
| sample_range_hashing(const sample_size_policy&); |
| /// Swaps content. |
| inline void |
| swap(sample_size_policy& other); |
| protected: |
| /// Given a __size size, returns a __size that is larger. |
| inline size_type |
| get_nearest_larger_size(size_type size) const; |
| /// Given a __size size, returns a __size that is smaller. |
| inline size_type |
| get_nearest_smaller_size(size_type size) const; |
| }; |
| } |
| #endif |