41#define PB_DS_ASSERT_VALID(X) \
42 _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);)
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)) }
54notify_find_search_start()
55{ PB_DS_ASSERT_VALID((*
this)) }
60notify_find_search_collision()
61{ PB_DS_ASSERT_VALID((*
this)) }
66notify_find_search_end()
67{ PB_DS_ASSERT_VALID((*
this)) }
72notify_insert_search_start()
73{ PB_DS_ASSERT_VALID((*
this)) }
78notify_insert_search_collision()
79{ PB_DS_ASSERT_VALID((*
this)) }
84notify_insert_search_end()
85{ PB_DS_ASSERT_VALID((*
this)) }
90notify_erase_search_start()
91{ PB_DS_ASSERT_VALID((*
this)) }
96notify_erase_search_collision()
97{ PB_DS_ASSERT_VALID((*
this)) }
102notify_erase_search_end()
103{ PB_DS_ASSERT_VALID((*
this)) }
108notify_inserted(size_type num_entries)
110 m_resize_needed = (num_entries >= m_next_grow_size);
111 size_base::set_size(num_entries);
112 PB_DS_ASSERT_VALID((*
this))
118notify_erased(size_type num_entries)
120 size_base::set_size(num_entries);
121 m_resize_needed = num_entries <= m_next_shrink_size;
122 PB_DS_ASSERT_VALID((*
this))
128is_resize_needed()
const
130 PB_DS_ASSERT_VALID((*
this))
131 return m_resize_needed;
137is_grow_needed(size_type , size_type num_entries)
const
139 _GLIBCXX_DEBUG_ASSERT(m_resize_needed);
140 return num_entries >= m_next_grow_size;
145~hash_load_check_resize_trigger() { }
150notify_resized(size_type new_size)
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);
156#ifdef PB_DS_HT_MAP_RESIZE_TRACE_
161 <<
"4 " << m_next_shrink_size <<
std::endl
162 <<
"5 " << m_next_grow_size <<
std::endl;
165 PB_DS_ASSERT_VALID((*
this))
171notify_externally_resized(size_type new_size)
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);
177#ifdef PB_DS_HT_MAP_RESIZE_TRACE_
182 <<
"4 " << m_next_shrink_size <<
std::endl
188 if (new_grow_size >= m_next_grow_size)
190 _GLIBCXX_DEBUG_ASSERT(new_shrink_size >= m_next_shrink_size);
191 m_next_grow_size = new_grow_size;
195 _GLIBCXX_DEBUG_ASSERT(new_shrink_size <= m_next_shrink_size);
196 m_next_shrink_size = new_shrink_size;
199 PB_DS_ASSERT_VALID((*
this))
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))
216swap(PB_DS_CLASS_C_DEC& other)
218 PB_DS_ASSERT_VALID((*
this))
219 PB_DS_ASSERT_VALID(other)
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);
228 PB_DS_ASSERT_VALID((*this))
229 PB_DS_ASSERT_VALID(other)
233inline
std::pair<
float,
float>
237 PB_DS_STATIC_ASSERT(access, external_load_access);
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;
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)));
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;
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__) \
286assert_valid(
const char* __file,
int __line)
const
288 PB_DS_DEBUG_VERIFY(m_load_max > m_load_min);
289 PB_DS_DEBUG_VERIFY(m_next_grow_size >= m_next_shrink_size);
291# undef PB_DS_DEBUG_VERIFY
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.
ISO C++ entities toplevel namespace is std.
basic_ostream< _CharT, _Traits > & endl(basic_ostream< _CharT, _Traits > &__os)
Write a newline and flush the stream.
ostream cerr
Linked to standard output.
Struct holding two objects of arbitrary type.
_T1 first
second_type is the second bound type
_T2 second
first is a copy of the first object