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