1// -*- C++ -*-
2
3// Copyright (C) 2005 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
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 2, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.
15
16// You should have received a copy of the GNU General Public License along
17// with this library; see the file COPYING.  If not, write to the Free
18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
19// USA.
20
21// As a special exception, you may use this file as part of a free software
22// library without restriction.  Specifically, if other files instantiate
23// templates or use macros or inline functions from this file, or you compile
24// this file and link it with other files to produce an executable, this
25// file does not by itself cause the resulting executable to be covered by
26// the GNU General Public License.  This exception does not however
27// invalidate any other reasons why the executable file might be covered by
28// the GNU General Public License.
29
30// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
31
32// Permission to use, copy, modify, sell, and distribute this software
33// is hereby granted without fee, provided that the above copyright
34// notice appears in all copies, and that both that copyright notice and
35// this permission notice appear in supporting documentation. None of
36// the above authors, nor IBM Haifa Research Laboratories, make any
37// representation about the suitability of this software for any
38// purpose. It is provided "as is" without express or implied warranty.
39
40/*
41 * @file cc_hash_max_collision_check_resize_trigger_imp.hpp
42 * Contains an implementation of cc_hash_max_collision_check_resize_trigger.
43 */
44
45PB_ASSOC_CLASS_T_DEC
46pb_assoc::detail::int_to_type<External_Load_Access>
47PB_ASSOC_CLASS_C_DEC::s_external_load_access_ind;
48
49PB_ASSOC_CLASS_T_DEC
50PB_ASSOC_CLASS_C_DEC::
51cc_hash_max_collision_check_resize_trigger(float load) :
52  m_load(load),
53  m_size(0),
54  m_num_col(0),
55  m_max_col(0),
56  m_resize_needed(false)
57{ }
58
59PB_ASSOC_CLASS_T_DEC
60inline void
61PB_ASSOC_CLASS_C_DEC::
62notify_find_search_start()
63{ }
64
65PB_ASSOC_CLASS_T_DEC
66inline void
67PB_ASSOC_CLASS_C_DEC::
68notify_find_search_collision()
69{ }
70
71PB_ASSOC_CLASS_T_DEC
72inline void
73PB_ASSOC_CLASS_C_DEC::
74notify_find_search_end()
75{ }
76
77PB_ASSOC_CLASS_T_DEC
78inline void
79PB_ASSOC_CLASS_C_DEC::
80notify_insert_search_start()
81{
82  m_num_col = 0;
83}
84
85PB_ASSOC_CLASS_T_DEC
86inline void
87PB_ASSOC_CLASS_C_DEC::
88notify_insert_search_collision()
89{
90  ++m_num_col;
91}
92
93PB_ASSOC_CLASS_T_DEC
94inline void
95PB_ASSOC_CLASS_C_DEC::
96notify_insert_search_end()
97{
98  PB_ASSOC_DBG_ASSERT(NOTHING_HT_RESIZE_ACTION == 0);
99
100  m_resize_needed =
101    m_resize_needed || (m_num_col >= m_max_col);
102}
103
104PB_ASSOC_CLASS_T_DEC
105inline void
106PB_ASSOC_CLASS_C_DEC::
107notify_erase_search_start()
108{ }
109
110PB_ASSOC_CLASS_T_DEC
111inline void
112PB_ASSOC_CLASS_C_DEC::
113notify_erase_search_collision()
114{ }
115
116PB_ASSOC_CLASS_T_DEC
117inline void
118PB_ASSOC_CLASS_C_DEC::
119notify_erase_search_end()
120{ }
121
122PB_ASSOC_CLASS_T_DEC
123inline void
124PB_ASSOC_CLASS_C_DEC::
125notify_inserted(size_type num_e)
126{
127  PB_ASSOC_DBG_ASSERT(num_e <= m_size);
128
129  if (num_e == m_size)
130    m_resize_needed = true;
131}
132
133PB_ASSOC_CLASS_T_DEC
134inline void
135PB_ASSOC_CLASS_C_DEC::
136notify_erased(size_type num_e)
137{
138  PB_ASSOC_DBG_ASSERT(num_e <= m_size);
139
140  m_resize_needed = false;
141}
142
143PB_ASSOC_CLASS_T_DEC
144void
145PB_ASSOC_CLASS_C_DEC::
146notify_cleared()
147{
148  m_resize_needed = false;
149}
150
151PB_ASSOC_CLASS_T_DEC
152inline bool
153PB_ASSOC_CLASS_C_DEC::
154is_resize_needed() const
155{
156  return (m_resize_needed);
157}
158
159PB_ASSOC_CLASS_T_DEC
160inline bool
161PB_ASSOC_CLASS_C_DEC::
162is_grow_needed(size_type /*size*/, size_type /*num_used_e*/) const
163{
164  PB_ASSOC_DBG_ASSERT(m_resize_needed);
165
166  return (true);
167}
168
169PB_ASSOC_CLASS_T_DEC
170inline bool
171PB_ASSOC_CLASS_C_DEC::
172is_shrink_needed(size_type size, size_type num_used_e) const
173{
174  PB_ASSOC_DBG_ASSERT(m_resize_needed);
175
176  return (false);
177}
178
179PB_ASSOC_CLASS_T_DEC
180void
181PB_ASSOC_CLASS_C_DEC::
182notify_resized(size_type new_size)
183{
184  m_size = new_size;
185
186  // max_col <-- \sqrt{2 load \ln( 2 m \ln( m ) ) }
187
188  const double ln_arg = 2*  m_size*  ::log( (double)m_size);
189
190  m_max_col = (size_type)::ceil(  ::sqrt(2*   m_load*  ::log(ln_arg) ) );
191
192  m_num_col = 0;
193
194  m_resize_needed = false;
195}
196
197PB_ASSOC_CLASS_T_DEC
198void
199PB_ASSOC_CLASS_C_DEC::
200notify_externally_resized(size_type new_size)
201{
202  notify_resized(new_size);
203}
204
205PB_ASSOC_CLASS_T_DEC
206void
207PB_ASSOC_CLASS_C_DEC::
208swap(PB_ASSOC_CLASS_C_DEC& r_other)
209{
210  std::swap(m_load, r_other.m_load);
211
212  std::swap(m_size, r_other.m_size);
213
214  std::swap(m_num_col, r_other.m_num_col);
215
216  std::swap(m_max_col, r_other.m_max_col);
217
218  std::swap(m_resize_needed, r_other.m_resize_needed);
219}
220
221PB_ASSOC_CLASS_T_DEC
222inline float
223PB_ASSOC_CLASS_C_DEC::
224get_load_imp(pb_assoc::detail::int_to_type<true>) const
225{
226  return (m_load);
227}
228