libstdc++
hash_load_check_resize_trigger_imp.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2014 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 
44 PB_DS_CLASS_T_DEC
45 PB_DS_CLASS_C_DEC::
46 hash_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 
51 PB_DS_CLASS_T_DEC
52 inline void
53 PB_DS_CLASS_C_DEC::
54 notify_find_search_start()
55 { PB_DS_ASSERT_VALID((*this)) }
56 
57 PB_DS_CLASS_T_DEC
58 inline void
59 PB_DS_CLASS_C_DEC::
60 notify_find_search_collision()
61 { PB_DS_ASSERT_VALID((*this)) }
62 
63 PB_DS_CLASS_T_DEC
64 inline void
65 PB_DS_CLASS_C_DEC::
66 notify_find_search_end()
67 { PB_DS_ASSERT_VALID((*this)) }
68 
69 PB_DS_CLASS_T_DEC
70 inline void
71 PB_DS_CLASS_C_DEC::
72 notify_insert_search_start()
73 { PB_DS_ASSERT_VALID((*this)) }
74 
75 PB_DS_CLASS_T_DEC
76 inline void
77 PB_DS_CLASS_C_DEC::
78 notify_insert_search_collision()
79 { PB_DS_ASSERT_VALID((*this)) }
80 
81 PB_DS_CLASS_T_DEC
82 inline void
83 PB_DS_CLASS_C_DEC::
84 notify_insert_search_end()
85 { PB_DS_ASSERT_VALID((*this)) }
86 
87 PB_DS_CLASS_T_DEC
88 inline void
89 PB_DS_CLASS_C_DEC::
90 notify_erase_search_start()
91 { PB_DS_ASSERT_VALID((*this)) }
92 
93 PB_DS_CLASS_T_DEC
94 inline void
95 PB_DS_CLASS_C_DEC::
96 notify_erase_search_collision()
97 { PB_DS_ASSERT_VALID((*this)) }
98 
99 PB_DS_CLASS_T_DEC
100 inline void
101 PB_DS_CLASS_C_DEC::
102 notify_erase_search_end()
103 { PB_DS_ASSERT_VALID((*this)) }
104 
105 PB_DS_CLASS_T_DEC
106 inline void
107 PB_DS_CLASS_C_DEC::
108 notify_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 
115 PB_DS_CLASS_T_DEC
116 inline void
117 PB_DS_CLASS_C_DEC::
118 notify_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 
125 PB_DS_CLASS_T_DEC
126 inline bool
127 PB_DS_CLASS_C_DEC::
128 is_resize_needed() const
129 {
130  PB_DS_ASSERT_VALID((*this))
131  return m_resize_needed;
132 }
133 
134 PB_DS_CLASS_T_DEC
135 inline bool
136 PB_DS_CLASS_C_DEC::
137 is_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 
143 PB_DS_CLASS_T_DEC
144 PB_DS_CLASS_C_DEC::
145 ~hash_load_check_resize_trigger() { }
146 
147 PB_DS_CLASS_T_DEC
148 void
149 PB_DS_CLASS_C_DEC::
150 notify_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 
168 PB_DS_CLASS_T_DEC
169 void
170 PB_DS_CLASS_C_DEC::
171 notify_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 
202 PB_DS_CLASS_T_DEC
203 void
204 PB_DS_CLASS_C_DEC::
205 notify_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 
213 PB_DS_CLASS_T_DEC
214 void
215 PB_DS_CLASS_C_DEC::
216 swap(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 
232 PB_DS_CLASS_T_DEC
233 inline std::pair<float, float>
234 PB_DS_CLASS_C_DEC::
235 get_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 
241 PB_DS_CLASS_T_DEC
242 void
243 PB_DS_CLASS_C_DEC::
244 set_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 
270 PB_DS_CLASS_T_DEC
271 void
272 PB_DS_CLASS_C_DEC::
273 do_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 
283 PB_DS_CLASS_T_DEC
284 void
285 PB_DS_CLASS_C_DEC::
286 assert_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
std::make_pair
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:276
std::pair::first
_T1 first
second_type is the second bound type
Definition: stl_pair.h:101
std
ISO C++ entities toplevel namespace is std.
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
std::swap
void swap(_Tp &, _Tp &) noexcept(__and_< is_nothrow_move_constructible< _Tp >, is_nothrow_move_assignable< _Tp >>::value)
Swaps two values.
Definition: move.h:166
std::pair::second
_T2 second
first is a copy of the first object
Definition: stl_pair.h:102