libstdc++
hash_load_check_resize_trigger_imp.hpp
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2005-2019 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 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
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
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.
19
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/>.
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_load_check_resize_trigger_imp.hpp
38 * Contains a resize trigger implementation.
39 */
40
41#define PB_DS_ASSERT_VALID(X) \
42 _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);)
43
44PB_DS_CLASS_T_DEC
45PB_DS_CLASS_C_DEC::
46hash_load_check_resize_trigger(float load_min, float load_max)
47: m_load_min(load_min), m_load_max(load_max), m_next_shrink_size(0),
48 m_next_grow_size(0), m_resize_needed(false)
49{ PB_DS_ASSERT_VALID((*this)) }
50
51PB_DS_CLASS_T_DEC
52inline void
53PB_DS_CLASS_C_DEC::
54notify_find_search_start()
55{ PB_DS_ASSERT_VALID((*this)) }
56
57PB_DS_CLASS_T_DEC
58inline void
59PB_DS_CLASS_C_DEC::
60notify_find_search_collision()
61{ PB_DS_ASSERT_VALID((*this)) }
62
63PB_DS_CLASS_T_DEC
64inline void
65PB_DS_CLASS_C_DEC::
66notify_find_search_end()
67{ PB_DS_ASSERT_VALID((*this)) }
68
69PB_DS_CLASS_T_DEC
70inline void
71PB_DS_CLASS_C_DEC::
72notify_insert_search_start()
73{ PB_DS_ASSERT_VALID((*this)) }
74
75PB_DS_CLASS_T_DEC
76inline void
77PB_DS_CLASS_C_DEC::
78notify_insert_search_collision()
79{ PB_DS_ASSERT_VALID((*this)) }
80
81PB_DS_CLASS_T_DEC
82inline void
83PB_DS_CLASS_C_DEC::
84notify_insert_search_end()
85{ PB_DS_ASSERT_VALID((*this)) }
86
87PB_DS_CLASS_T_DEC
88inline void
89PB_DS_CLASS_C_DEC::
90notify_erase_search_start()
91{ PB_DS_ASSERT_VALID((*this)) }
92
93PB_DS_CLASS_T_DEC
94inline void
95PB_DS_CLASS_C_DEC::
96notify_erase_search_collision()
97{ PB_DS_ASSERT_VALID((*this)) }
98
99PB_DS_CLASS_T_DEC
100inline void
101PB_DS_CLASS_C_DEC::
102notify_erase_search_end()
103{ PB_DS_ASSERT_VALID((*this)) }
104
105PB_DS_CLASS_T_DEC
106inline void
107PB_DS_CLASS_C_DEC::
108notify_inserted(size_type num_entries)
109{
110 m_resize_needed = (num_entries >= m_next_grow_size);
111 size_base::set_size(num_entries);
112 PB_DS_ASSERT_VALID((*this))
113}
114
115PB_DS_CLASS_T_DEC
116inline void
117PB_DS_CLASS_C_DEC::
118notify_erased(size_type num_entries)
119{
120 size_base::set_size(num_entries);
121 m_resize_needed = num_entries <= m_next_shrink_size;
122 PB_DS_ASSERT_VALID((*this))
123}
124
125PB_DS_CLASS_T_DEC
126inline bool
127PB_DS_CLASS_C_DEC::
128is_resize_needed() const
129{
130 PB_DS_ASSERT_VALID((*this))
131 return m_resize_needed;
132}
133
134PB_DS_CLASS_T_DEC
135inline bool
136PB_DS_CLASS_C_DEC::
137is_grow_needed(size_type /*size*/, size_type num_entries) const
138{
139 _GLIBCXX_DEBUG_ASSERT(m_resize_needed);
140 return num_entries >= m_next_grow_size;
141}
142
143PB_DS_CLASS_T_DEC
144PB_DS_CLASS_C_DEC::
145~hash_load_check_resize_trigger() { }
146
147PB_DS_CLASS_T_DEC
148void
149PB_DS_CLASS_C_DEC::
150notify_resized(size_type new_size)
151{
152 m_resize_needed = false;
153 m_next_grow_size = size_type(m_load_max * new_size - 1);
154 m_next_shrink_size = size_type(m_load_min * new_size);
155
156#ifdef PB_DS_HT_MAP_RESIZE_TRACE_
157 std::cerr << "hlcrt::notify_resized " << std::endl
158 << "1 " << new_size << std::endl
159 << "2 " << m_load_min << std::endl
160 << "3 " << m_load_max << std::endl
161 << "4 " << m_next_shrink_size << std::endl
162 << "5 " << m_next_grow_size << std::endl;
163#endif
164
165 PB_DS_ASSERT_VALID((*this))
166}
167
168PB_DS_CLASS_T_DEC
169void
170PB_DS_CLASS_C_DEC::
171notify_externally_resized(size_type new_size)
172{
173 m_resize_needed = false;
174 size_type new_grow_size = size_type(m_load_max * new_size - 1);
175 size_type new_shrink_size = size_type(m_load_min * new_size);
176
177#ifdef PB_DS_HT_MAP_RESIZE_TRACE_
178 std::cerr << "hlcrt::notify_externally_resized " << std::endl
179 << "1 " << new_size << std::endl
180 << "2 " << m_load_min << std::endl
181 << "3 " << m_load_max << std::endl
182 << "4 " << m_next_shrink_size << std::endl
183 << "5 " << m_next_grow_size << std::endl
184 << "6 " << new_shrink_size << std::endl
185 << "7 " << new_grow_size << std::endl;
186#endif
187
188 if (new_grow_size >= m_next_grow_size)
189 {
190 _GLIBCXX_DEBUG_ASSERT(new_shrink_size >= m_next_shrink_size);
191 m_next_grow_size = new_grow_size;
192 }
193 else
194 {
195 _GLIBCXX_DEBUG_ASSERT(new_shrink_size <= m_next_shrink_size);
196 m_next_shrink_size = new_shrink_size;
197 }
198
199 PB_DS_ASSERT_VALID((*this))
200}
201
202PB_DS_CLASS_T_DEC
203void
204PB_DS_CLASS_C_DEC::
205notify_cleared()
206{
207 PB_DS_ASSERT_VALID((*this))
208 size_base::set_size(0);
209 m_resize_needed = (0 < m_next_shrink_size);
210 PB_DS_ASSERT_VALID((*this))
211}
212
213PB_DS_CLASS_T_DEC
214void
215PB_DS_CLASS_C_DEC::
216swap(PB_DS_CLASS_C_DEC& other)
217{
218 PB_DS_ASSERT_VALID((*this))
219 PB_DS_ASSERT_VALID(other)
220
221 size_base::swap(other);
222 std::swap(m_load_min, other.m_load_min);
223 std::swap(m_load_max, other.m_load_max);
224 std::swap(m_resize_needed, other.m_resize_needed);
225 std::swap(m_next_grow_size, other.m_next_grow_size);
226 std::swap(m_next_shrink_size, other.m_next_shrink_size);
227
228 PB_DS_ASSERT_VALID((*this))
229 PB_DS_ASSERT_VALID(other)
230}
231
232PB_DS_CLASS_T_DEC
233inline std::pair<float, float>
234PB_DS_CLASS_C_DEC::
235get_loads() const
236{
237 PB_DS_STATIC_ASSERT(access, external_load_access);
238 return std::make_pair(m_load_min, m_load_max);
239}
240
241PB_DS_CLASS_T_DEC
242void
243PB_DS_CLASS_C_DEC::
244set_loads(std::pair<float, float> load_pair)
245{
246 PB_DS_STATIC_ASSERT(access, external_load_access);
247 const float old_load_min = m_load_min;
248 const float old_load_max = m_load_max;
249 const size_type old_next_shrink_size = m_next_shrink_size;
250 const size_type old_next_grow_size = m_next_grow_size;
251 const bool old_resize_needed = m_resize_needed;
252
253 __try
254 {
255 m_load_min = load_pair.first;
256 m_load_max = load_pair.second;
257 do_resize(static_cast<size_type>(size_base::get_size() / ((m_load_min + m_load_max) / 2)));
258 }
259 __catch(...)
260 {
261 m_load_min = old_load_min;
262 m_load_max = old_load_max;
263 m_next_shrink_size = old_next_shrink_size;
264 m_next_grow_size = old_next_grow_size;
265 m_resize_needed = old_resize_needed;
266 __throw_exception_again;
267 }
268}
269
270PB_DS_CLASS_T_DEC
271void
272PB_DS_CLASS_C_DEC::
273do_resize(size_type)
274{ std::abort(); }
275
276#ifdef _GLIBCXX_DEBUG
277# define PB_DS_DEBUG_VERIFY(_Cond) \
278 _GLIBCXX_DEBUG_VERIFY_AT(_Cond, \
279 _M_message(#_Cond" assertion from %1;:%2;") \
280 ._M_string(__FILE__)._M_integer(__LINE__) \
281 ,__file,__line)
282
283PB_DS_CLASS_T_DEC
284void
285PB_DS_CLASS_C_DEC::
286assert_valid(const char* __file, int __line) const
287{
288 PB_DS_DEBUG_VERIFY(m_load_max > m_load_min);
289 PB_DS_DEBUG_VERIFY(m_next_grow_size >= m_next_shrink_size);
290}
291# undef PB_DS_DEBUG_VERIFY
292#endif
293#undef PB_DS_ASSERT_VALID
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
Definition: stl_pair.h:524
ISO C++ entities toplevel namespace is std.
basic_ostream< _CharT, _Traits > & endl(basic_ostream< _CharT, _Traits > &__os)
Write a newline and flush the stream.
Definition: ostream:599
ostream cerr
Linked to standard output.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:210
_T1 first
second_type is the second bound type
Definition: stl_pair.h:214
_T2 second
first is a copy of the first object
Definition: stl_pair.h:215