3 // Copyright (C) 2005, 2006, 2007, 2008, 2009 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 2, 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 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
33 // Permission to use, copy, modify, sell, and distribute this software
34 // is hereby granted without fee, provided that the above copyright
35 // notice appears in all copies, and that both that copyright notice
36 // and this permission notice appear in supporting documentation. None
37 // of the above authors, nor IBM Haifa Research Laboratories, make any
38 // representation about the suitability of this software for any
39 // purpose. It is provided "as is" without express or implied
43 * @file hash_load_check_resize_trigger_imp.hpp
44 * Contains a resize trigger implementation.
49 hash_load_check_resize_trigger(float load_min
, float load_max
)
50 : m_load_min(load_min
), m_load_max(load_max
), m_next_shrink_size(0),
51 m_next_grow_size(0), m_resize_needed(false)
52 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
57 notify_find_search_start()
58 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
63 notify_find_search_collision()
64 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
69 notify_find_search_end()
70 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
75 notify_insert_search_start()
76 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
81 notify_insert_search_collision()
82 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
87 notify_insert_search_end()
88 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
93 notify_erase_search_start()
94 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
99 notify_erase_search_collision()
100 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
105 notify_erase_search_end()
106 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
111 notify_inserted(size_type num_entries
)
113 m_resize_needed
= (num_entries
>= m_next_grow_size
);
114 size_base::set_size(num_entries
);
115 _GLIBCXX_DEBUG_ONLY(assert_valid();)
121 notify_erased(size_type num_entries
)
123 size_base::set_size(num_entries
);
124 m_resize_needed
= num_entries
<= m_next_shrink_size
;
125 _GLIBCXX_DEBUG_ONLY(assert_valid();)
131 is_resize_needed() const
133 _GLIBCXX_DEBUG_ONLY(assert_valid();)
134 return m_resize_needed
;
140 is_grow_needed(size_type
/*size*/, size_type num_entries
) const
142 _GLIBCXX_DEBUG_ASSERT(m_resize_needed
);
143 return num_entries
>= m_next_grow_size
;
148 ~hash_load_check_resize_trigger() { }
153 notify_resized(size_type new_size
)
155 m_resize_needed
= false;
156 m_next_grow_size
= size_type(m_load_max
* new_size
- 1);
157 m_next_shrink_size
= size_type(m_load_min
* new_size
);
159 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_
160 std::cerr
<< "hlcrt::notify_resized " <<
161 static_cast<unsigned long>(new_size
) << " " <<
162 static_cast<unsigned long>(m_load_min
) << " " <<
163 static_cast<unsigned long>(m_load_max
) << " " <<
164 static_cast<unsigned long>(m_next_shrink_size
) << " " <<
165 static_cast<unsigned long>(m_next_grow_size
) << " " << std::endl
;
168 _GLIBCXX_DEBUG_ONLY(assert_valid();)
174 notify_externally_resized(size_type new_size
)
176 m_resize_needed
= false;
177 size_type new_grow_size
= size_type(m_load_max
* new_size
- 1);
178 size_type new_shrink_size
= size_type(m_load_min
* new_size
);
179 if (new_grow_size
>= m_next_grow_size
)
181 _GLIBCXX_DEBUG_ASSERT(new_shrink_size
> m_next_shrink_size
);
182 m_next_grow_size
= new_grow_size
;
183 _GLIBCXX_DEBUG_ONLY(assert_valid();)
185 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_
186 std::cerr
<< "hlcrt::notify_externally_resized1 " <<
187 static_cast<unsigned long>(new_size
) << " " <<
188 static_cast<unsigned long>(m_load_min
) << " " <<
189 static_cast<unsigned long>(m_load_max
) << " " <<
190 static_cast<unsigned long>(m_next_shrink_size
) << " " <<
191 static_cast<unsigned long>(m_next_grow_size
) << " " << std::endl
;
196 _GLIBCXX_DEBUG_ASSERT(new_shrink_size
<= m_next_shrink_size
);
197 m_next_shrink_size
= new_shrink_size
;
199 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_
200 std::cerr
<< "hlcrt::notify_externally_resized2 " <<
201 static_cast<unsigned long>(new_size
) << " " <<
202 static_cast<unsigned long>(m_load_min
) << " " <<
203 static_cast<unsigned long>(m_load_max
) << " " <<
204 static_cast<unsigned long>(m_next_shrink_size
) << " " <<
205 static_cast<unsigned long>(m_next_grow_size
) << " " << std::endl
;
208 _GLIBCXX_DEBUG_ONLY(assert_valid();)
216 _GLIBCXX_DEBUG_ONLY(assert_valid();)
217 size_base::set_size(0);
218 m_resize_needed
= (0 < m_next_shrink_size
);
219 _GLIBCXX_DEBUG_ONLY(assert_valid();)
225 swap(PB_DS_CLASS_C_DEC
& other
)
227 _GLIBCXX_DEBUG_ONLY(assert_valid();)
228 _GLIBCXX_DEBUG_ONLY(other
.assert_valid();)
230 size_base::swap(other
);
231 std::swap(m_load_min
, other
.m_load_min
);
232 std::swap(m_load_max
, other
.m_load_max
);
233 std::swap(m_resize_needed
, other
.m_resize_needed
);
234 std::swap(m_next_grow_size
, other
.m_next_grow_size
);
235 std::swap(m_next_shrink_size
, other
.m_next_shrink_size
);
237 _GLIBCXX_DEBUG_ONLY(assert_valid();)
238 _GLIBCXX_DEBUG_ONLY(other
.assert_valid();)
242 inline std::pair
<float, float>
246 PB_DS_STATIC_ASSERT(access
, external_load_access
);
247 return std::make_pair(m_load_min
, m_load_max
);
253 set_loads(std::pair
<float, float> load_pair
)
255 PB_DS_STATIC_ASSERT(access
, external_load_access
);
256 const float old_load_min
= m_load_min
;
257 const float old_load_max
= m_load_max
;
258 const size_type old_next_shrink_size
= m_next_shrink_size
;
259 const size_type old_next_grow_size
= m_next_grow_size
;
260 const bool old_resize_needed
= m_resize_needed
;
264 m_load_min
= load_pair
.first
;
265 m_load_max
= load_pair
.second
;
266 do_resize(static_cast<size_type
>(size_base::get_size() / ((m_load_min
+ m_load_max
) / 2)));
270 m_load_min
= old_load_min
;
271 m_load_max
= old_load_max
;
272 m_next_shrink_size
= old_next_shrink_size
;
273 m_next_grow_size
= old_next_grow_size
;
274 m_resize_needed
= old_resize_needed
;
275 __throw_exception_again
;
285 #ifdef _GLIBCXX_DEBUG
291 _GLIBCXX_DEBUG_ASSERT(m_load_max
> m_load_min
);
292 _GLIBCXX_DEBUG_ASSERT(m_next_grow_size
>= m_next_shrink_size
);