libstdc++
hash_load_check_resize_trigger_imp.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2022 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 #ifdef PB_DS_CLASS_C_DEC
42 
43 #define PB_DS_ASSERT_VALID(X) \
44  _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);)
45 
46 PB_DS_CLASS_T_DEC
47 PB_DS_CLASS_C_DEC::
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)) }
52 
53 PB_DS_CLASS_T_DEC
54 inline void
55 PB_DS_CLASS_C_DEC::
56 notify_find_search_start()
57 { PB_DS_ASSERT_VALID((*this)) }
58 
59 PB_DS_CLASS_T_DEC
60 inline void
61 PB_DS_CLASS_C_DEC::
62 notify_find_search_collision()
63 { PB_DS_ASSERT_VALID((*this)) }
64 
65 PB_DS_CLASS_T_DEC
66 inline void
67 PB_DS_CLASS_C_DEC::
68 notify_find_search_end()
69 { PB_DS_ASSERT_VALID((*this)) }
70 
71 PB_DS_CLASS_T_DEC
72 inline void
73 PB_DS_CLASS_C_DEC::
74 notify_insert_search_start()
75 { PB_DS_ASSERT_VALID((*this)) }
76 
77 PB_DS_CLASS_T_DEC
78 inline void
79 PB_DS_CLASS_C_DEC::
80 notify_insert_search_collision()
81 { PB_DS_ASSERT_VALID((*this)) }
82 
83 PB_DS_CLASS_T_DEC
84 inline void
85 PB_DS_CLASS_C_DEC::
86 notify_insert_search_end()
87 { PB_DS_ASSERT_VALID((*this)) }
88 
89 PB_DS_CLASS_T_DEC
90 inline void
91 PB_DS_CLASS_C_DEC::
92 notify_erase_search_start()
93 { PB_DS_ASSERT_VALID((*this)) }
94 
95 PB_DS_CLASS_T_DEC
96 inline void
97 PB_DS_CLASS_C_DEC::
98 notify_erase_search_collision()
99 { PB_DS_ASSERT_VALID((*this)) }
100 
101 PB_DS_CLASS_T_DEC
102 inline void
103 PB_DS_CLASS_C_DEC::
104 notify_erase_search_end()
105 { PB_DS_ASSERT_VALID((*this)) }
106 
107 PB_DS_CLASS_T_DEC
108 inline void
109 PB_DS_CLASS_C_DEC::
110 notify_inserted(size_type num_entries)
111 {
112  m_resize_needed = (num_entries >= m_next_grow_size);
113  size_base::set_size(num_entries);
114  PB_DS_ASSERT_VALID((*this))
115 }
116 
117 PB_DS_CLASS_T_DEC
118 inline void
119 PB_DS_CLASS_C_DEC::
120 notify_erased(size_type num_entries)
121 {
122  size_base::set_size(num_entries);
123  m_resize_needed = num_entries <= m_next_shrink_size;
124  PB_DS_ASSERT_VALID((*this))
125 }
126 
127 PB_DS_CLASS_T_DEC
128 inline bool
129 PB_DS_CLASS_C_DEC::
130 is_resize_needed() const
131 {
132  PB_DS_ASSERT_VALID((*this))
133  return m_resize_needed;
134 }
135 
136 PB_DS_CLASS_T_DEC
137 inline bool
138 PB_DS_CLASS_C_DEC::
139 is_grow_needed(size_type /*size*/, size_type num_entries) const
140 {
141  _GLIBCXX_DEBUG_ASSERT(m_resize_needed);
142  return num_entries >= m_next_grow_size;
143 }
144 
145 PB_DS_CLASS_T_DEC
146 PB_DS_CLASS_C_DEC::
147 ~hash_load_check_resize_trigger() { }
148 
149 PB_DS_CLASS_T_DEC
150 void
151 PB_DS_CLASS_C_DEC::
152 notify_resized(size_type new_size)
153 {
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);
157 
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;
165 #endif
166 
167  PB_DS_ASSERT_VALID((*this))
168 }
169 
170 PB_DS_CLASS_T_DEC
171 void
172 PB_DS_CLASS_C_DEC::
173 notify_externally_resized(size_type new_size)
174 {
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);
178 
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;
188 #endif
189 
190  if (new_grow_size >= m_next_grow_size)
191  {
192  _GLIBCXX_DEBUG_ASSERT(new_shrink_size >= m_next_shrink_size);
193  m_next_grow_size = new_grow_size;
194  }
195  else
196  {
197  _GLIBCXX_DEBUG_ASSERT(new_shrink_size <= m_next_shrink_size);
198  m_next_shrink_size = new_shrink_size;
199  }
200 
201  PB_DS_ASSERT_VALID((*this))
202 }
203 
204 PB_DS_CLASS_T_DEC
205 void
206 PB_DS_CLASS_C_DEC::
207 notify_cleared()
208 {
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))
213 }
214 
215 PB_DS_CLASS_T_DEC
216 void
217 PB_DS_CLASS_C_DEC::
218 swap(PB_DS_CLASS_C_DEC& other)
219 {
220  PB_DS_ASSERT_VALID((*this))
221  PB_DS_ASSERT_VALID(other)
222 
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);
229 
230  PB_DS_ASSERT_VALID((*this))
231  PB_DS_ASSERT_VALID(other)
232 }
233 
234 PB_DS_CLASS_T_DEC
235 inline std::pair<float, float>
236 PB_DS_CLASS_C_DEC::
237 get_loads() const
238 {
239  PB_DS_STATIC_ASSERT(access, external_load_access);
240  return std::make_pair(m_load_min, m_load_max);
241 }
242 
243 PB_DS_CLASS_T_DEC
244 void
245 PB_DS_CLASS_C_DEC::
246 set_loads(std::pair<float, float> load_pair)
247 {
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;
254 
255  __try
256  {
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)));
260  }
261  __catch(...)
262  {
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;
269  }
270 }
271 
272 PB_DS_CLASS_T_DEC
273 void
274 PB_DS_CLASS_C_DEC::
275 do_resize(size_type)
276 { std::abort(); }
277 
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__) \
283  ,__file,__line)
284 
285 PB_DS_CLASS_T_DEC
286 void
287 PB_DS_CLASS_C_DEC::
288 assert_valid(const char* __file, int __line) const
289 {
290  PB_DS_DEBUG_VERIFY(m_load_max > m_load_min);
291  PB_DS_DEBUG_VERIFY(m_next_grow_size >= m_next_shrink_size);
292 }
293 # undef PB_DS_DEBUG_VERIFY
294 #endif
295 #undef PB_DS_ASSERT_VALID
296 #endif
std::pair::pair
pair(_T1, _T2) -> pair< _T1, _T2 >
Two pairs of the same type are equal iff their members are equal.
std::shared_mutex::swap
void swap(shared_lock< _Mutex > &__x, shared_lock< _Mutex > &__y) noexcept
Swap specialization for shared_lock.
Definition: shared_mutex:851
std
ISO C++ entities toplevel namespace is std.
std::cerr
ostream cerr
Linked to standard output.
std::endl
basic_ostream< _CharT, _Traits > & endl(basic_ostream< _CharT, _Traits > &__os)
Write a newline and flush the stream.
Definition: ostream:688
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:187
std::pair::first
_T1 first
The first member.
Definition: stl_pair.h:191
std::pair::second
_T2 second
The second member.
Definition: stl_pair.h:192