1// -*- C++ -*-
2
3// Copyright (C) 2005, 2006 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 2, 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// 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.
20
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
29// Public License.
30
31// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
32
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
40// warranty.
41
42/**
43 * @file hash_standard_resize_policy_imp.hpp
44 * Contains a resize policy implementation.
45 */
46
47#define PB_DS_STATIC_ASSERT(UNIQUE, E) \
48  typedef detail::static_assert_dumclass<sizeof(detail::static_assert<(bool)(E)>)> UNIQUE##static_assert_type
49
50PB_DS_CLASS_T_DEC
51PB_DS_CLASS_C_DEC::
52hash_standard_resize_policy()
53: m_size(Size_Policy::get_nearest_larger_size(1))
54{ trigger_policy_base::notify_externally_resized(m_size); }
55
56PB_DS_CLASS_T_DEC
57PB_DS_CLASS_C_DEC::
58hash_standard_resize_policy(const Size_Policy& r_size_policy)
59: Size_Policy(r_size_policy), m_size(Size_Policy::get_nearest_larger_size(1))
60{ trigger_policy_base::notify_externally_resized(m_size); }
61
62PB_DS_CLASS_T_DEC
63PB_DS_CLASS_C_DEC::
64hash_standard_resize_policy(const Size_Policy& r_size_policy,
65			    const Trigger_Policy& r_trigger_policy)
66: Size_Policy(r_size_policy), Trigger_Policy(r_trigger_policy),
67  m_size(Size_Policy::get_nearest_larger_size(1))
68{ trigger_policy_base::notify_externally_resized(m_size); }
69
70PB_DS_CLASS_T_DEC
71PB_DS_CLASS_C_DEC::
72~hash_standard_resize_policy()
73{ }
74
75PB_DS_CLASS_T_DEC
76void
77PB_DS_CLASS_C_DEC::
78swap(PB_DS_CLASS_C_DEC& other)
79{
80  trigger_policy_base::swap(other);
81  size_policy_base::swap(other);
82  std::swap(m_size, other.m_size);
83}
84
85PB_DS_CLASS_T_DEC
86inline void
87PB_DS_CLASS_C_DEC::
88notify_find_search_start()
89{ trigger_policy_base::notify_find_search_start(); }
90
91PB_DS_CLASS_T_DEC
92inline void
93PB_DS_CLASS_C_DEC::
94notify_find_search_collision()
95{ trigger_policy_base::notify_find_search_collision(); }
96
97PB_DS_CLASS_T_DEC
98inline void
99PB_DS_CLASS_C_DEC::
100notify_find_search_end()
101{ trigger_policy_base::notify_find_search_end(); }
102
103PB_DS_CLASS_T_DEC
104inline void
105PB_DS_CLASS_C_DEC::
106notify_insert_search_start()
107{ trigger_policy_base::notify_insert_search_start(); }
108
109PB_DS_CLASS_T_DEC
110inline void
111PB_DS_CLASS_C_DEC::
112notify_insert_search_collision()
113{ trigger_policy_base::notify_insert_search_collision(); }
114
115PB_DS_CLASS_T_DEC
116inline void
117PB_DS_CLASS_C_DEC::
118notify_insert_search_end()
119{ trigger_policy_base::notify_insert_search_end(); }
120
121PB_DS_CLASS_T_DEC
122inline void
123PB_DS_CLASS_C_DEC::
124notify_erase_search_start()
125{ trigger_policy_base::notify_erase_search_start(); }
126
127PB_DS_CLASS_T_DEC
128inline void
129PB_DS_CLASS_C_DEC::
130notify_erase_search_collision()
131{ trigger_policy_base::notify_erase_search_collision(); }
132
133PB_DS_CLASS_T_DEC
134inline void
135PB_DS_CLASS_C_DEC::
136notify_erase_search_end()
137{ trigger_policy_base::notify_erase_search_end(); }
138
139PB_DS_CLASS_T_DEC
140inline void
141PB_DS_CLASS_C_DEC::
142notify_inserted(size_type num_e)
143{ trigger_policy_base::notify_inserted(num_e); }
144
145PB_DS_CLASS_T_DEC
146inline void
147PB_DS_CLASS_C_DEC::
148notify_erased(size_type num_e)
149{ trigger_policy_base::notify_erased(num_e); }
150
151PB_DS_CLASS_T_DEC
152void
153PB_DS_CLASS_C_DEC::
154notify_cleared()
155{ trigger_policy_base::notify_cleared(); }
156
157PB_DS_CLASS_T_DEC
158inline bool
159PB_DS_CLASS_C_DEC::
160is_resize_needed() const
161{ return trigger_policy_base::is_resize_needed(); }
162
163PB_DS_CLASS_T_DEC
164typename PB_DS_CLASS_C_DEC::size_type
165PB_DS_CLASS_C_DEC::
166get_new_size(size_type size, size_type num_used_e) const
167{
168  if (trigger_policy_base::is_grow_needed(size, num_used_e))
169    return size_policy_base::get_nearest_larger_size(size);
170  return size_policy_base::get_nearest_smaller_size(size);
171}
172
173PB_DS_CLASS_T_DEC
174void
175PB_DS_CLASS_C_DEC::
176notify_resized(size_type new_size)
177{
178  trigger_policy_base::notify_resized(new_size);
179  m_size = new_size;
180}
181
182PB_DS_CLASS_T_DEC
183inline typename PB_DS_CLASS_C_DEC::size_type
184PB_DS_CLASS_C_DEC::
185get_actual_size() const
186{
187  PB_DS_STATIC_ASSERT(access, external_size_access);
188  return m_size;
189}
190
191PB_DS_CLASS_T_DEC
192void
193PB_DS_CLASS_C_DEC::
194resize(size_type new_size)
195{
196  PB_DS_STATIC_ASSERT(access, external_size_access);
197  size_type actual_size = size_policy_base::get_nearest_larger_size(1);
198  while (actual_size < new_size)
199    {
200      const size_type pot = size_policy_base::get_nearest_larger_size(actual_size);
201
202      if (pot == actual_size && pot < new_size)
203	__throw_resize_error();
204      actual_size = pot;
205    }
206
207  if (actual_size > 0)
208    --actual_size;
209
210  const size_type old_size = m_size;
211  try
212    {
213      do_resize(actual_size - 1);
214    }
215  catch(insert_error& )
216    {
217      m_size = old_size;
218      __throw_resize_error();
219    }
220  catch(...)
221    {
222      m_size = old_size;
223      __throw_exception_again;
224    }
225}
226
227PB_DS_CLASS_T_DEC
228void
229PB_DS_CLASS_C_DEC::
230do_resize(size_type)
231{
232  // Do nothing
233}
234
235PB_DS_CLASS_T_DEC
236Trigger_Policy&
237PB_DS_CLASS_C_DEC::
238get_trigger_policy()
239{ return *this; }
240
241PB_DS_CLASS_T_DEC
242const Trigger_Policy&
243PB_DS_CLASS_C_DEC::
244get_trigger_policy() const
245{ return *this; }
246
247PB_DS_CLASS_T_DEC
248Size_Policy&
249PB_DS_CLASS_C_DEC::
250get_size_policy()
251{ return *this; }
252
253PB_DS_CLASS_T_DEC
254const Size_Policy&
255PB_DS_CLASS_C_DEC::
256get_size_policy() const
257{ return *this; }
258
259#undef PB_DS_STATIC_ASSERT
260
261