3 // Copyright (C) 2005-2020 Free Software Foundation, Inc.
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
8 // Foundation; either version 3, or (at your option) any later
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.
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.
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/>.
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
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
37 * @file hash_load_check_resize_trigger_imp.hpp
38 * Contains a resize trigger implementation.
41 #ifdef PB_DS_CLASS_C_DEC
43 #define PB_DS_ASSERT_VALID(X) \
44 _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);)
48 hash_load_check_resize_trigger(float load_min, float load_max)
49 : m_load_min(load_min), m_load_max(load_max), m_next_shrink_size(0),
50 m_next_grow_size(0), m_resize_needed(false)
51 { PB_DS_ASSERT_VALID((*this)) }
56 notify_find_search_start()
57 { PB_DS_ASSERT_VALID((*this)) }
62 notify_find_search_collision()
63 { PB_DS_ASSERT_VALID((*this)) }
68 notify_find_search_end()
69 { PB_DS_ASSERT_VALID((*this)) }
74 notify_insert_search_start()
75 { PB_DS_ASSERT_VALID((*this)) }
80 notify_insert_search_collision()
81 { PB_DS_ASSERT_VALID((*this)) }
86 notify_insert_search_end()
87 { PB_DS_ASSERT_VALID((*this)) }
92 notify_erase_search_start()
93 { PB_DS_ASSERT_VALID((*this)) }
98 notify_erase_search_collision()
99 { PB_DS_ASSERT_VALID((*this)) }
104 notify_erase_search_end()
105 { PB_DS_ASSERT_VALID((*this)) }
110 notify_inserted(size_type num_entries)
112 m_resize_needed = (num_entries >= m_next_grow_size);
113 size_base::set_size(num_entries);
114 PB_DS_ASSERT_VALID((*this))
120 notify_erased(size_type num_entries)
122 size_base::set_size(num_entries);
123 m_resize_needed = num_entries <= m_next_shrink_size;
124 PB_DS_ASSERT_VALID((*this))
130 is_resize_needed() const
132 PB_DS_ASSERT_VALID((*this))
133 return m_resize_needed;
139 is_grow_needed(size_type /*size*/, size_type num_entries) const
141 _GLIBCXX_DEBUG_ASSERT(m_resize_needed);
142 return num_entries >= m_next_grow_size;
147 ~hash_load_check_resize_trigger() { }
152 notify_resized(size_type new_size)
154 m_resize_needed = false;
155 m_next_grow_size = size_type(m_load_max * new_size - 1);
156 m_next_shrink_size = size_type(m_load_min * new_size);
158 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_
159 std::cerr << "hlcrt::notify_resized " << std::endl
160 << "1 " << new_size << std::endl
161 << "2 " << m_load_min << std::endl
162 << "3 " << m_load_max << std::endl
163 << "4 " << m_next_shrink_size << std::endl
164 << "5 " << m_next_grow_size << std::endl;
167 PB_DS_ASSERT_VALID((*this))
173 notify_externally_resized(size_type new_size)
175 m_resize_needed = false;
176 size_type new_grow_size = size_type(m_load_max * new_size - 1);
177 size_type new_shrink_size = size_type(m_load_min * new_size);
179 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_
180 std::cerr << "hlcrt::notify_externally_resized " << std::endl
181 << "1 " << new_size << std::endl
182 << "2 " << m_load_min << std::endl
183 << "3 " << m_load_max << std::endl
184 << "4 " << m_next_shrink_size << std::endl
185 << "5 " << m_next_grow_size << std::endl
186 << "6 " << new_shrink_size << std::endl
187 << "7 " << new_grow_size << std::endl;
190 if (new_grow_size >= m_next_grow_size)
192 _GLIBCXX_DEBUG_ASSERT(new_shrink_size >= m_next_shrink_size);
193 m_next_grow_size = new_grow_size;
197 _GLIBCXX_DEBUG_ASSERT(new_shrink_size <= m_next_shrink_size);
198 m_next_shrink_size = new_shrink_size;
201 PB_DS_ASSERT_VALID((*this))
209 PB_DS_ASSERT_VALID((*this))
210 size_base::set_size(0);
211 m_resize_needed = (0 < m_next_shrink_size);
212 PB_DS_ASSERT_VALID((*this))
218 swap(PB_DS_CLASS_C_DEC& other)
220 PB_DS_ASSERT_VALID((*this))
221 PB_DS_ASSERT_VALID(other)
223 size_base::swap(other);
224 std::swap(m_load_min, other.m_load_min);
225 std::swap(m_load_max, other.m_load_max);
226 std::swap(m_resize_needed, other.m_resize_needed);
227 std::swap(m_next_grow_size, other.m_next_grow_size);
228 std::swap(m_next_shrink_size, other.m_next_shrink_size);
230 PB_DS_ASSERT_VALID((*this))
231 PB_DS_ASSERT_VALID(other)
235 inline std::pair<float, float>
239 PB_DS_STATIC_ASSERT(access, external_load_access);
240 return std::make_pair(m_load_min, m_load_max);
246 set_loads(std::pair<float, float> load_pair)
248 PB_DS_STATIC_ASSERT(access, external_load_access);
249 const float old_load_min = m_load_min;
250 const float old_load_max = m_load_max;
251 const size_type old_next_shrink_size = m_next_shrink_size;
252 const size_type old_next_grow_size = m_next_grow_size;
253 const bool old_resize_needed = m_resize_needed;
257 m_load_min = load_pair.first;
258 m_load_max = load_pair.second;
259 do_resize(static_cast<size_type>(size_base::get_size() / ((m_load_min + m_load_max) / 2)));
263 m_load_min = old_load_min;
264 m_load_max = old_load_max;
265 m_next_shrink_size = old_next_shrink_size;
266 m_next_grow_size = old_next_grow_size;
267 m_resize_needed = old_resize_needed;
268 __throw_exception_again;
278 #ifdef _GLIBCXX_DEBUG
279 # define PB_DS_DEBUG_VERIFY(_Cond) \
280 _GLIBCXX_DEBUG_VERIFY_AT(_Cond, \
281 _M_message(#_Cond" assertion from %1;:%2;") \
282 ._M_string(__FILE__)._M_integer(__LINE__) \
288 assert_valid(const char* __file, int __line) const
290 PB_DS_DEBUG_VERIFY(m_load_max > m_load_min);
291 PB_DS_DEBUG_VERIFY(m_next_grow_size >= m_next_shrink_size);
293 # undef PB_DS_DEBUG_VERIFY
295 #undef PB_DS_ASSERT_VALID