]>
Commit | Line | Data |
---|---|---|
b82f782b BK |
1 | // Internal policy header for TR1 unordered_set and unordered_map -*- C++ -*- |
2 | ||
7adcbafe | 3 | // Copyright (C) 2010-2022 Free Software Foundation, Inc. |
b82f782b BK |
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 | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
b82f782b BK |
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 | ||
748086b7 JJ |
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/>. | |
b82f782b | 24 | |
ab65a4c7 | 25 | /** @file tr1/hashtable_policy.h |
e133ace8 | 26 | * This is an internal header file, included by other library headers. |
f910786b BK |
27 | * Do not attempt to use it directly. |
28 | * @headername{tr1/unordered_map, tr1/unordered_set} | |
b82f782b BK |
29 | */ |
30 | ||
12ffa228 | 31 | namespace std _GLIBCXX_VISIBILITY(default) |
b82f782b | 32 | { |
4a15d842 FD |
33 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
34 | ||
3b2524b1 PC |
35 | namespace tr1 |
36 | { | |
95cefe5f | 37 | namespace __detail |
b82f782b | 38 | { |
b82f782b BK |
39 | // Helper function: return distance(first, last) for forward |
40 | // iterators, or 0 for input iterators. | |
95cefe5f PC |
41 | template<class _Iterator> |
42 | inline typename std::iterator_traits<_Iterator>::difference_type | |
43 | __distance_fw(_Iterator __first, _Iterator __last, | |
44 | std::input_iterator_tag) | |
b82f782b BK |
45 | { return 0; } |
46 | ||
95cefe5f PC |
47 | template<class _Iterator> |
48 | inline typename std::iterator_traits<_Iterator>::difference_type | |
49 | __distance_fw(_Iterator __first, _Iterator __last, | |
50 | std::forward_iterator_tag) | |
51 | { return std::distance(__first, __last); } | |
b82f782b | 52 | |
95cefe5f PC |
53 | template<class _Iterator> |
54 | inline typename std::iterator_traits<_Iterator>::difference_type | |
55 | __distance_fw(_Iterator __first, _Iterator __last) | |
b82f782b | 56 | { |
95cefe5f PC |
57 | typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag; |
58 | return __distance_fw(__first, __last, _Tag()); | |
b82f782b BK |
59 | } |
60 | ||
95cefe5f | 61 | // Auxiliary types used for all instantiations of _Hashtable: nodes |
b82f782b BK |
62 | // and iterators. |
63 | ||
64 | // Nodes, used to wrap elements stored in the hash table. A policy | |
95cefe5f | 65 | // template parameter of class template _Hashtable controls whether |
b82f782b BK |
66 | // nodes also store a hash code. In some cases (e.g. strings) this |
67 | // may be a performance win. | |
95cefe5f PC |
68 | template<typename _Value, bool __cache_hash_code> |
69 | struct _Hash_node; | |
b82f782b | 70 | |
95cefe5f PC |
71 | template<typename _Value> |
72 | struct _Hash_node<_Value, true> | |
b82f782b | 73 | { |
95cefe5f PC |
74 | _Value _M_v; |
75 | std::size_t _M_hash_code; | |
76 | _Hash_node* _M_next; | |
b82f782b BK |
77 | }; |
78 | ||
95cefe5f PC |
79 | template<typename _Value> |
80 | struct _Hash_node<_Value, false> | |
b82f782b | 81 | { |
95cefe5f PC |
82 | _Value _M_v; |
83 | _Hash_node* _M_next; | |
b82f782b BK |
84 | }; |
85 | ||
86 | // Local iterators, used to iterate within a bucket but not between | |
87 | // buckets. | |
95cefe5f PC |
88 | template<typename _Value, bool __cache> |
89 | struct _Node_iterator_base | |
b82f782b | 90 | { |
95cefe5f PC |
91 | _Node_iterator_base(_Hash_node<_Value, __cache>* __p) |
92 | : _M_cur(__p) { } | |
b82f782b BK |
93 | |
94 | void | |
95cefe5f PC |
95 | _M_incr() |
96 | { _M_cur = _M_cur->_M_next; } | |
b82f782b | 97 | |
95cefe5f | 98 | _Hash_node<_Value, __cache>* _M_cur; |
b82f782b BK |
99 | }; |
100 | ||
95cefe5f | 101 | template<typename _Value, bool __cache> |
b82f782b | 102 | inline bool |
95cefe5f PC |
103 | operator==(const _Node_iterator_base<_Value, __cache>& __x, |
104 | const _Node_iterator_base<_Value, __cache>& __y) | |
105 | { return __x._M_cur == __y._M_cur; } | |
b82f782b | 106 | |
95cefe5f | 107 | template<typename _Value, bool __cache> |
b82f782b | 108 | inline bool |
95cefe5f PC |
109 | operator!=(const _Node_iterator_base<_Value, __cache>& __x, |
110 | const _Node_iterator_base<_Value, __cache>& __y) | |
111 | { return __x._M_cur != __y._M_cur; } | |
b82f782b | 112 | |
95cefe5f PC |
113 | template<typename _Value, bool __constant_iterators, bool __cache> |
114 | struct _Node_iterator | |
115 | : public _Node_iterator_base<_Value, __cache> | |
b82f782b | 116 | { |
95cefe5f PC |
117 | typedef _Value value_type; |
118 | typedef typename | |
119 | __gnu_cxx::__conditional_type<__constant_iterators, | |
120 | const _Value*, _Value*>::__type | |
b82f782b | 121 | pointer; |
95cefe5f PC |
122 | typedef typename |
123 | __gnu_cxx::__conditional_type<__constant_iterators, | |
124 | const _Value&, _Value&>::__type | |
b82f782b BK |
125 | reference; |
126 | typedef std::ptrdiff_t difference_type; | |
127 | typedef std::forward_iterator_tag iterator_category; | |
128 | ||
95cefe5f PC |
129 | _Node_iterator() |
130 | : _Node_iterator_base<_Value, __cache>(0) { } | |
b82f782b BK |
131 | |
132 | explicit | |
95cefe5f PC |
133 | _Node_iterator(_Hash_node<_Value, __cache>* __p) |
134 | : _Node_iterator_base<_Value, __cache>(__p) { } | |
b82f782b BK |
135 | |
136 | reference | |
137 | operator*() const | |
95cefe5f | 138 | { return this->_M_cur->_M_v; } |
b82f782b BK |
139 | |
140 | pointer | |
141 | operator->() const | |
f271b536 | 142 | { return std::__addressof(this->_M_cur->_M_v); } |
b82f782b | 143 | |
95cefe5f | 144 | _Node_iterator& |
b82f782b BK |
145 | operator++() |
146 | { | |
95cefe5f | 147 | this->_M_incr(); |
b82f782b BK |
148 | return *this; |
149 | } | |
150 | ||
95cefe5f | 151 | _Node_iterator |
b82f782b BK |
152 | operator++(int) |
153 | { | |
95cefe5f PC |
154 | _Node_iterator __tmp(*this); |
155 | this->_M_incr(); | |
156 | return __tmp; | |
b82f782b BK |
157 | } |
158 | }; | |
159 | ||
95cefe5f PC |
160 | template<typename _Value, bool __constant_iterators, bool __cache> |
161 | struct _Node_const_iterator | |
162 | : public _Node_iterator_base<_Value, __cache> | |
b82f782b | 163 | { |
95cefe5f PC |
164 | typedef _Value value_type; |
165 | typedef const _Value* pointer; | |
166 | typedef const _Value& reference; | |
b82f782b BK |
167 | typedef std::ptrdiff_t difference_type; |
168 | typedef std::forward_iterator_tag iterator_category; | |
169 | ||
95cefe5f PC |
170 | _Node_const_iterator() |
171 | : _Node_iterator_base<_Value, __cache>(0) { } | |
b82f782b BK |
172 | |
173 | explicit | |
95cefe5f PC |
174 | _Node_const_iterator(_Hash_node<_Value, __cache>* __p) |
175 | : _Node_iterator_base<_Value, __cache>(__p) { } | |
b82f782b | 176 | |
95cefe5f PC |
177 | _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators, |
178 | __cache>& __x) | |
179 | : _Node_iterator_base<_Value, __cache>(__x._M_cur) { } | |
b82f782b BK |
180 | |
181 | reference | |
182 | operator*() const | |
95cefe5f | 183 | { return this->_M_cur->_M_v; } |
b82f782b BK |
184 | |
185 | pointer | |
186 | operator->() const | |
f271b536 | 187 | { return std::__addressof(this->_M_cur->_M_v); } |
b82f782b | 188 | |
95cefe5f | 189 | _Node_const_iterator& |
b82f782b BK |
190 | operator++() |
191 | { | |
95cefe5f | 192 | this->_M_incr(); |
b82f782b BK |
193 | return *this; |
194 | } | |
195 | ||
95cefe5f | 196 | _Node_const_iterator |
b82f782b BK |
197 | operator++(int) |
198 | { | |
95cefe5f PC |
199 | _Node_const_iterator __tmp(*this); |
200 | this->_M_incr(); | |
201 | return __tmp; | |
b82f782b BK |
202 | } |
203 | }; | |
204 | ||
95cefe5f PC |
205 | template<typename _Value, bool __cache> |
206 | struct _Hashtable_iterator_base | |
b82f782b | 207 | { |
95cefe5f PC |
208 | _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node, |
209 | _Hash_node<_Value, __cache>** __bucket) | |
210 | : _M_cur_node(__node), _M_cur_bucket(__bucket) { } | |
b82f782b BK |
211 | |
212 | void | |
95cefe5f | 213 | _M_incr() |
b82f782b | 214 | { |
95cefe5f PC |
215 | _M_cur_node = _M_cur_node->_M_next; |
216 | if (!_M_cur_node) | |
217 | _M_incr_bucket(); | |
b82f782b BK |
218 | } |
219 | ||
220 | void | |
95cefe5f | 221 | _M_incr_bucket(); |
b82f782b | 222 | |
95cefe5f PC |
223 | _Hash_node<_Value, __cache>* _M_cur_node; |
224 | _Hash_node<_Value, __cache>** _M_cur_bucket; | |
b82f782b BK |
225 | }; |
226 | ||
227 | // Global iterators, used for arbitrary iteration within a hash | |
228 | // table. Larger and more expensive than local iterators. | |
95cefe5f | 229 | template<typename _Value, bool __cache> |
b82f782b | 230 | void |
95cefe5f PC |
231 | _Hashtable_iterator_base<_Value, __cache>:: |
232 | _M_incr_bucket() | |
b82f782b | 233 | { |
95cefe5f | 234 | ++_M_cur_bucket; |
b82f782b BK |
235 | |
236 | // This loop requires the bucket array to have a non-null sentinel. | |
95cefe5f PC |
237 | while (!*_M_cur_bucket) |
238 | ++_M_cur_bucket; | |
239 | _M_cur_node = *_M_cur_bucket; | |
b82f782b BK |
240 | } |
241 | ||
95cefe5f | 242 | template<typename _Value, bool __cache> |
b82f782b | 243 | inline bool |
95cefe5f PC |
244 | operator==(const _Hashtable_iterator_base<_Value, __cache>& __x, |
245 | const _Hashtable_iterator_base<_Value, __cache>& __y) | |
246 | { return __x._M_cur_node == __y._M_cur_node; } | |
b82f782b | 247 | |
95cefe5f | 248 | template<typename _Value, bool __cache> |
b82f782b | 249 | inline bool |
95cefe5f PC |
250 | operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x, |
251 | const _Hashtable_iterator_base<_Value, __cache>& __y) | |
252 | { return __x._M_cur_node != __y._M_cur_node; } | |
b82f782b | 253 | |
95cefe5f PC |
254 | template<typename _Value, bool __constant_iterators, bool __cache> |
255 | struct _Hashtable_iterator | |
256 | : public _Hashtable_iterator_base<_Value, __cache> | |
b82f782b | 257 | { |
95cefe5f PC |
258 | typedef _Value value_type; |
259 | typedef typename | |
260 | __gnu_cxx::__conditional_type<__constant_iterators, | |
261 | const _Value*, _Value*>::__type | |
b82f782b | 262 | pointer; |
95cefe5f PC |
263 | typedef typename |
264 | __gnu_cxx::__conditional_type<__constant_iterators, | |
265 | const _Value&, _Value&>::__type | |
b82f782b BK |
266 | reference; |
267 | typedef std::ptrdiff_t difference_type; | |
268 | typedef std::forward_iterator_tag iterator_category; | |
269 | ||
95cefe5f PC |
270 | _Hashtable_iterator() |
271 | : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } | |
b82f782b | 272 | |
95cefe5f PC |
273 | _Hashtable_iterator(_Hash_node<_Value, __cache>* __p, |
274 | _Hash_node<_Value, __cache>** __b) | |
275 | : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } | |
b82f782b BK |
276 | |
277 | explicit | |
95cefe5f PC |
278 | _Hashtable_iterator(_Hash_node<_Value, __cache>** __b) |
279 | : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } | |
b82f782b BK |
280 | |
281 | reference | |
282 | operator*() const | |
95cefe5f | 283 | { return this->_M_cur_node->_M_v; } |
b82f782b BK |
284 | |
285 | pointer | |
286 | operator->() const | |
f271b536 | 287 | { return std::__addressof(this->_M_cur_node->_M_v); } |
b82f782b | 288 | |
95cefe5f | 289 | _Hashtable_iterator& |
b82f782b BK |
290 | operator++() |
291 | { | |
95cefe5f | 292 | this->_M_incr(); |
b82f782b BK |
293 | return *this; |
294 | } | |
295 | ||
95cefe5f | 296 | _Hashtable_iterator |
b82f782b BK |
297 | operator++(int) |
298 | { | |
95cefe5f PC |
299 | _Hashtable_iterator __tmp(*this); |
300 | this->_M_incr(); | |
301 | return __tmp; | |
b82f782b BK |
302 | } |
303 | }; | |
304 | ||
95cefe5f PC |
305 | template<typename _Value, bool __constant_iterators, bool __cache> |
306 | struct _Hashtable_const_iterator | |
307 | : public _Hashtable_iterator_base<_Value, __cache> | |
b82f782b | 308 | { |
95cefe5f PC |
309 | typedef _Value value_type; |
310 | typedef const _Value* pointer; | |
311 | typedef const _Value& reference; | |
b82f782b BK |
312 | typedef std::ptrdiff_t difference_type; |
313 | typedef std::forward_iterator_tag iterator_category; | |
314 | ||
95cefe5f PC |
315 | _Hashtable_const_iterator() |
316 | : _Hashtable_iterator_base<_Value, __cache>(0, 0) { } | |
b82f782b | 317 | |
95cefe5f PC |
318 | _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p, |
319 | _Hash_node<_Value, __cache>** __b) | |
320 | : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { } | |
b82f782b BK |
321 | |
322 | explicit | |
95cefe5f PC |
323 | _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b) |
324 | : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { } | |
b82f782b | 325 | |
95cefe5f PC |
326 | _Hashtable_const_iterator(const _Hashtable_iterator<_Value, |
327 | __constant_iterators, __cache>& __x) | |
328 | : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node, | |
329 | __x._M_cur_bucket) { } | |
b82f782b BK |
330 | |
331 | reference | |
332 | operator*() const | |
95cefe5f | 333 | { return this->_M_cur_node->_M_v; } |
b82f782b BK |
334 | |
335 | pointer | |
336 | operator->() const | |
f271b536 | 337 | { return std::__addressof(this->_M_cur_node->_M_v); } |
b82f782b | 338 | |
95cefe5f | 339 | _Hashtable_const_iterator& |
b82f782b BK |
340 | operator++() |
341 | { | |
95cefe5f | 342 | this->_M_incr(); |
b82f782b BK |
343 | return *this; |
344 | } | |
345 | ||
95cefe5f | 346 | _Hashtable_const_iterator |
b82f782b BK |
347 | operator++(int) |
348 | { | |
95cefe5f PC |
349 | _Hashtable_const_iterator __tmp(*this); |
350 | this->_M_incr(); | |
351 | return __tmp; | |
b82f782b BK |
352 | } |
353 | }; | |
354 | ||
355 | ||
95cefe5f | 356 | // Many of class template _Hashtable's template parameters are policy |
b82f782b BK |
357 | // classes. These are defaults for the policies. |
358 | ||
b82f782b BK |
359 | // Default range hashing function: use division to fold a large number |
360 | // into the range [0, N). | |
95cefe5f | 361 | struct _Mod_range_hashing |
b82f782b BK |
362 | { |
363 | typedef std::size_t first_argument_type; | |
364 | typedef std::size_t second_argument_type; | |
365 | typedef std::size_t result_type; | |
366 | ||
367 | result_type | |
95cefe5f PC |
368 | operator()(first_argument_type __num, second_argument_type __den) const |
369 | { return __num % __den; } | |
b82f782b BK |
370 | }; |
371 | ||
372 | // Default ranged hash function H. In principle it should be a | |
373 | // function object composed from objects of type H1 and H2 such that | |
374 | // h(k, N) = h2(h1(k), N), but that would mean making extra copies of | |
375 | // h1 and h2. So instead we'll just use a tag to tell class template | |
376 | // hashtable to do that composition. | |
95cefe5f | 377 | struct _Default_ranged_hash { }; |
b82f782b BK |
378 | |
379 | // Default value for rehash policy. Bucket size is (usually) the | |
380 | // smallest prime that keeps the load factor small enough. | |
95cefe5f | 381 | struct _Prime_rehash_policy |
b82f782b | 382 | { |
4d007574 PC |
383 | _Prime_rehash_policy(float __z = 1.0) |
384 | : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0) { } | |
95cefe5f | 385 | |
b82f782b | 386 | float |
4d007574 PC |
387 | max_load_factor() const |
388 | { return _M_max_load_factor; } | |
b82f782b BK |
389 | |
390 | // Return a bucket size no smaller than n. | |
391 | std::size_t | |
95cefe5f | 392 | _M_next_bkt(std::size_t __n) const; |
b82f782b BK |
393 | |
394 | // Return a bucket count appropriate for n elements | |
395 | std::size_t | |
95cefe5f | 396 | _M_bkt_for_elements(std::size_t __n) const; |
b82f782b | 397 | |
95cefe5f PC |
398 | // __n_bkt is current bucket count, __n_elt is current element count, |
399 | // and __n_ins is number of elements to be inserted. Do we need to | |
b82f782b BK |
400 | // increase bucket count? If so, return make_pair(true, n), where n |
401 | // is the new bucket count. If not, return make_pair(false, 0). | |
402 | std::pair<bool, std::size_t> | |
95cefe5f PC |
403 | _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, |
404 | std::size_t __n_ins) const; | |
bce62343 PC |
405 | |
406 | enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 }; | |
407 | ||
95cefe5f PC |
408 | float _M_max_load_factor; |
409 | float _M_growth_factor; | |
410 | mutable std::size_t _M_next_resize; | |
b82f782b BK |
411 | }; |
412 | ||
4d007574 | 413 | extern const unsigned long __prime_list[]; |
b82f782b | 414 | |
4d007574 PC |
415 | // XXX This is a hack. There's no good reason for any of |
416 | // _Prime_rehash_policy's member functions to be inline. | |
b82f782b BK |
417 | |
418 | // Return a prime no smaller than n. | |
419 | inline std::size_t | |
95cefe5f PC |
420 | _Prime_rehash_policy:: |
421 | _M_next_bkt(std::size_t __n) const | |
b82f782b | 422 | { |
29dbb034 FD |
423 | // Don't include the last prime in the search, so that anything |
424 | // higher than the second-to-last prime returns a past-the-end | |
425 | // iterator that can be dereferenced to get the last prime. | |
426 | const unsigned long* __p | |
427 | = std::lower_bound(__prime_list, __prime_list + _S_n_primes - 1, __n); | |
861d6c43 PC |
428 | _M_next_resize = |
429 | static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor)); | |
95cefe5f | 430 | return *__p; |
b82f782b BK |
431 | } |
432 | ||
433 | // Return the smallest prime p such that alpha p >= n, where alpha | |
434 | // is the load factor. | |
435 | inline std::size_t | |
95cefe5f PC |
436 | _Prime_rehash_policy:: |
437 | _M_bkt_for_elements(std::size_t __n) const | |
b82f782b | 438 | { |
95cefe5f | 439 | const float __min_bkts = __n / _M_max_load_factor; |
29dbb034 | 440 | return _M_next_bkt(__builtin_ceil(__min_bkts)); |
b82f782b BK |
441 | } |
442 | ||
95cefe5f PC |
443 | // Finds the smallest prime p such that alpha p > __n_elt + __n_ins. |
444 | // If p > __n_bkt, return make_pair(true, p); otherwise return | |
b82f782b | 445 | // make_pair(false, 0). In principle this isn't very different from |
95cefe5f | 446 | // _M_bkt_for_elements. |
4d007574 | 447 | |
b82f782b BK |
448 | // The only tricky part is that we're caching the element count at |
449 | // which we need to rehash, so we don't have to do a floating-point | |
450 | // multiply for every insertion. | |
4d007574 | 451 | |
b82f782b | 452 | inline std::pair<bool, std::size_t> |
95cefe5f PC |
453 | _Prime_rehash_policy:: |
454 | _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt, | |
455 | std::size_t __n_ins) const | |
b82f782b | 456 | { |
95cefe5f | 457 | if (__n_elt + __n_ins > _M_next_resize) |
b82f782b | 458 | { |
95cefe5f PC |
459 | float __min_bkts = ((float(__n_ins) + float(__n_elt)) |
460 | / _M_max_load_factor); | |
461 | if (__min_bkts > __n_bkt) | |
b82f782b | 462 | { |
95cefe5f | 463 | __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt); |
29dbb034 FD |
464 | return std::make_pair(true, |
465 | _M_next_bkt(__builtin_ceil(__min_bkts))); | |
b82f782b BK |
466 | } |
467 | else | |
468 | { | |
861d6c43 PC |
469 | _M_next_resize = static_cast<std::size_t> |
470 | (__builtin_ceil(__n_bkt * _M_max_load_factor)); | |
b82f782b BK |
471 | return std::make_pair(false, 0); |
472 | } | |
473 | } | |
474 | else | |
475 | return std::make_pair(false, 0); | |
476 | } | |
477 | ||
95cefe5f | 478 | // Base classes for std::tr1::_Hashtable. We define these base |
b82f782b BK |
479 | // classes because in some cases we want to do different things |
480 | // depending on the value of a policy class. In some cases the | |
481 | // policy class affects which member functions and nested typedefs | |
482 | // are defined; we handle that by specializing base class templates. | |
483 | // Several of the base class templates need to access other members | |
95cefe5f | 484 | // of class template _Hashtable, so we use the "curiously recurring |
b82f782b BK |
485 | // template pattern" for them. |
486 | ||
95cefe5f | 487 | // class template _Map_base. If the hashtable has a value type of the |
b82f782b BK |
488 | // form pair<T1, T2> and a key extraction policy that returns the |
489 | // first part of the pair, the hashtable gets a mapped_type typedef. | |
490 | // If it satisfies those criteria and also has unique keys, then it | |
491 | // also gets an operator[]. | |
95cefe5f PC |
492 | template<typename _Key, typename _Value, typename _Ex, bool __unique, |
493 | typename _Hashtable> | |
494 | struct _Map_base { }; | |
b82f782b | 495 | |
95cefe5f PC |
496 | template<typename _Key, typename _Pair, typename _Hashtable> |
497 | struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable> | |
b82f782b | 498 | { |
95cefe5f | 499 | typedef typename _Pair::second_type mapped_type; |
b82f782b BK |
500 | }; |
501 | ||
95cefe5f | 502 | template<typename _Key, typename _Pair, typename _Hashtable> |
2aa5c17c | 503 | struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable> |
b82f782b | 504 | { |
95cefe5f | 505 | typedef typename _Pair::second_type mapped_type; |
b82f782b BK |
506 | |
507 | mapped_type& | |
95cefe5f | 508 | operator[](const _Key& __k); |
b82f782b BK |
509 | }; |
510 | ||
95cefe5f PC |
511 | template<typename _Key, typename _Pair, typename _Hashtable> |
512 | typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>, | |
513 | true, _Hashtable>::mapped_type& | |
514 | _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>:: | |
515 | operator[](const _Key& __k) | |
b82f782b | 516 | { |
95cefe5f PC |
517 | _Hashtable* __h = static_cast<_Hashtable*>(this); |
518 | typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k); | |
519 | std::size_t __n = __h->_M_bucket_index(__k, __code, | |
520 | __h->_M_bucket_count); | |
521 | ||
522 | typename _Hashtable::_Node* __p = | |
523 | __h->_M_find_node(__h->_M_buckets[__n], __k, __code); | |
524 | if (!__p) | |
525 | return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()), | |
526 | __n, __code)->second; | |
527 | return (__p->_M_v).second; | |
b82f782b BK |
528 | } |
529 | ||
95cefe5f PC |
530 | // class template _Rehash_base. Give hashtable the max_load_factor |
531 | // functions iff the rehash policy is _Prime_rehash_policy. | |
532 | template<typename _RehashPolicy, typename _Hashtable> | |
533 | struct _Rehash_base { }; | |
b82f782b | 534 | |
95cefe5f PC |
535 | template<typename _Hashtable> |
536 | struct _Rehash_base<_Prime_rehash_policy, _Hashtable> | |
b82f782b BK |
537 | { |
538 | float | |
539 | max_load_factor() const | |
540 | { | |
95cefe5f PC |
541 | const _Hashtable* __this = static_cast<const _Hashtable*>(this); |
542 | return __this->__rehash_policy().max_load_factor(); | |
b82f782b BK |
543 | } |
544 | ||
545 | void | |
95cefe5f | 546 | max_load_factor(float __z) |
b82f782b | 547 | { |
95cefe5f PC |
548 | _Hashtable* __this = static_cast<_Hashtable*>(this); |
549 | __this->__rehash_policy(_Prime_rehash_policy(__z)); | |
b82f782b BK |
550 | } |
551 | }; | |
552 | ||
95cefe5f | 553 | // Class template _Hash_code_base. Encapsulates two policy issues that |
b82f782b BK |
554 | // aren't quite orthogonal. |
555 | // (1) the difference between using a ranged hash function and using | |
556 | // the combination of a hash function and a range-hashing function. | |
557 | // In the former case we don't have such things as hash codes, so | |
558 | // we have a dummy type as placeholder. | |
559 | // (2) Whether or not we cache hash codes. Caching hash codes is | |
560 | // meaningless if we have a ranged hash function. | |
561 | // We also put the key extraction and equality comparison function | |
562 | // objects here, for convenience. | |
563 | ||
564 | // Primary template: unused except as a hook for specializations. | |
95cefe5f PC |
565 | template<typename _Key, typename _Value, |
566 | typename _ExtractKey, typename _Equal, | |
567 | typename _H1, typename _H2, typename _Hash, | |
568 | bool __cache_hash_code> | |
569 | struct _Hash_code_base; | |
b82f782b BK |
570 | |
571 | // Specialization: ranged hash function, no caching hash codes. H1 | |
572 | // and H2 are provided but ignored. We define a dummy hash code type. | |
95cefe5f PC |
573 | template<typename _Key, typename _Value, |
574 | typename _ExtractKey, typename _Equal, | |
575 | typename _H1, typename _H2, typename _Hash> | |
576 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, | |
577 | _Hash, false> | |
b82f782b BK |
578 | { |
579 | protected: | |
95cefe5f PC |
580 | _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, |
581 | const _H1&, const _H2&, const _Hash& __h) | |
582 | : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { } | |
b82f782b | 583 | |
95cefe5f | 584 | typedef void* _Hash_code_type; |
b82f782b | 585 | |
95cefe5f PC |
586 | _Hash_code_type |
587 | _M_hash_code(const _Key& __key) const | |
b82f782b BK |
588 | { return 0; } |
589 | ||
590 | std::size_t | |
95cefe5f PC |
591 | _M_bucket_index(const _Key& __k, _Hash_code_type, |
592 | std::size_t __n) const | |
593 | { return _M_ranged_hash(__k, __n); } | |
b82f782b BK |
594 | |
595 | std::size_t | |
95cefe5f PC |
596 | _M_bucket_index(const _Hash_node<_Value, false>* __p, |
597 | std::size_t __n) const | |
598 | { return _M_ranged_hash(_M_extract(__p->_M_v), __n); } | |
b82f782b BK |
599 | |
600 | bool | |
95cefe5f PC |
601 | _M_compare(const _Key& __k, _Hash_code_type, |
602 | _Hash_node<_Value, false>* __n) const | |
603 | { return _M_eq(__k, _M_extract(__n->_M_v)); } | |
b82f782b BK |
604 | |
605 | void | |
95cefe5f | 606 | _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const |
b82f782b BK |
607 | { } |
608 | ||
609 | void | |
95cefe5f PC |
610 | _M_copy_code(_Hash_node<_Value, false>*, |
611 | const _Hash_node<_Value, false>*) const | |
b82f782b BK |
612 | { } |
613 | ||
614 | void | |
95cefe5f | 615 | _M_swap(_Hash_code_base& __x) |
b82f782b | 616 | { |
95cefe5f PC |
617 | std::swap(_M_extract, __x._M_extract); |
618 | std::swap(_M_eq, __x._M_eq); | |
619 | std::swap(_M_ranged_hash, __x._M_ranged_hash); | |
b82f782b BK |
620 | } |
621 | ||
622 | protected: | |
95cefe5f PC |
623 | _ExtractKey _M_extract; |
624 | _Equal _M_eq; | |
625 | _Hash _M_ranged_hash; | |
b82f782b BK |
626 | }; |
627 | ||
628 | ||
629 | // No specialization for ranged hash function while caching hash codes. | |
630 | // That combination is meaningless, and trying to do it is an error. | |
631 | ||
632 | ||
633 | // Specialization: ranged hash function, cache hash codes. This | |
634 | // combination is meaningless, so we provide only a declaration | |
635 | // and no definition. | |
95cefe5f PC |
636 | template<typename _Key, typename _Value, |
637 | typename _ExtractKey, typename _Equal, | |
638 | typename _H1, typename _H2, typename _Hash> | |
639 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, | |
640 | _Hash, true>; | |
b82f782b BK |
641 | |
642 | // Specialization: hash function and range-hashing function, no | |
643 | // caching of hash codes. H is provided but ignored. Provides | |
644 | // typedef and accessor required by TR1. | |
95cefe5f PC |
645 | template<typename _Key, typename _Value, |
646 | typename _ExtractKey, typename _Equal, | |
647 | typename _H1, typename _H2> | |
648 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, | |
649 | _Default_ranged_hash, false> | |
b82f782b | 650 | { |
95cefe5f PC |
651 | typedef _H1 hasher; |
652 | ||
b82f782b BK |
653 | hasher |
654 | hash_function() const | |
95cefe5f | 655 | { return _M_h1; } |
b82f782b BK |
656 | |
657 | protected: | |
95cefe5f PC |
658 | _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, |
659 | const _H1& __h1, const _H2& __h2, | |
660 | const _Default_ranged_hash&) | |
661 | : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { } | |
b82f782b | 662 | |
95cefe5f PC |
663 | typedef std::size_t _Hash_code_type; |
664 | ||
665 | _Hash_code_type | |
666 | _M_hash_code(const _Key& __k) const | |
667 | { return _M_h1(__k); } | |
b82f782b BK |
668 | |
669 | std::size_t | |
95cefe5f PC |
670 | _M_bucket_index(const _Key&, _Hash_code_type __c, |
671 | std::size_t __n) const | |
672 | { return _M_h2(__c, __n); } | |
b82f782b BK |
673 | |
674 | std::size_t | |
95cefe5f PC |
675 | _M_bucket_index(const _Hash_node<_Value, false>* __p, |
676 | std::size_t __n) const | |
677 | { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); } | |
b82f782b BK |
678 | |
679 | bool | |
95cefe5f PC |
680 | _M_compare(const _Key& __k, _Hash_code_type, |
681 | _Hash_node<_Value, false>* __n) const | |
682 | { return _M_eq(__k, _M_extract(__n->_M_v)); } | |
b82f782b BK |
683 | |
684 | void | |
95cefe5f | 685 | _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const |
b82f782b BK |
686 | { } |
687 | ||
688 | void | |
95cefe5f PC |
689 | _M_copy_code(_Hash_node<_Value, false>*, |
690 | const _Hash_node<_Value, false>*) const | |
b82f782b BK |
691 | { } |
692 | ||
693 | void | |
95cefe5f | 694 | _M_swap(_Hash_code_base& __x) |
b82f782b | 695 | { |
95cefe5f PC |
696 | std::swap(_M_extract, __x._M_extract); |
697 | std::swap(_M_eq, __x._M_eq); | |
698 | std::swap(_M_h1, __x._M_h1); | |
699 | std::swap(_M_h2, __x._M_h2); | |
b82f782b BK |
700 | } |
701 | ||
702 | protected: | |
95cefe5f PC |
703 | _ExtractKey _M_extract; |
704 | _Equal _M_eq; | |
705 | _H1 _M_h1; | |
706 | _H2 _M_h2; | |
b82f782b BK |
707 | }; |
708 | ||
709 | // Specialization: hash function and range-hashing function, | |
710 | // caching hash codes. H is provided but ignored. Provides | |
711 | // typedef and accessor required by TR1. | |
95cefe5f PC |
712 | template<typename _Key, typename _Value, |
713 | typename _ExtractKey, typename _Equal, | |
714 | typename _H1, typename _H2> | |
715 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, | |
716 | _Default_ranged_hash, true> | |
b82f782b | 717 | { |
95cefe5f | 718 | typedef _H1 hasher; |
b82f782b BK |
719 | |
720 | hasher | |
721 | hash_function() const | |
95cefe5f | 722 | { return _M_h1; } |
b82f782b BK |
723 | |
724 | protected: | |
95cefe5f PC |
725 | _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq, |
726 | const _H1& __h1, const _H2& __h2, | |
727 | const _Default_ranged_hash&) | |
728 | : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { } | |
b82f782b | 729 | |
95cefe5f | 730 | typedef std::size_t _Hash_code_type; |
b82f782b | 731 | |
95cefe5f PC |
732 | _Hash_code_type |
733 | _M_hash_code(const _Key& __k) const | |
734 | { return _M_h1(__k); } | |
b82f782b BK |
735 | |
736 | std::size_t | |
95cefe5f PC |
737 | _M_bucket_index(const _Key&, _Hash_code_type __c, |
738 | std::size_t __n) const | |
739 | { return _M_h2(__c, __n); } | |
b82f782b BK |
740 | |
741 | std::size_t | |
95cefe5f PC |
742 | _M_bucket_index(const _Hash_node<_Value, true>* __p, |
743 | std::size_t __n) const | |
744 | { return _M_h2(__p->_M_hash_code, __n); } | |
b82f782b BK |
745 | |
746 | bool | |
95cefe5f PC |
747 | _M_compare(const _Key& __k, _Hash_code_type __c, |
748 | _Hash_node<_Value, true>* __n) const | |
749 | { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); } | |
b82f782b BK |
750 | |
751 | void | |
95cefe5f PC |
752 | _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const |
753 | { __n->_M_hash_code = __c; } | |
b82f782b BK |
754 | |
755 | void | |
95cefe5f PC |
756 | _M_copy_code(_Hash_node<_Value, true>* __to, |
757 | const _Hash_node<_Value, true>* __from) const | |
758 | { __to->_M_hash_code = __from->_M_hash_code; } | |
b82f782b BK |
759 | |
760 | void | |
95cefe5f | 761 | _M_swap(_Hash_code_base& __x) |
b82f782b | 762 | { |
95cefe5f PC |
763 | std::swap(_M_extract, __x._M_extract); |
764 | std::swap(_M_eq, __x._M_eq); | |
765 | std::swap(_M_h1, __x._M_h1); | |
766 | std::swap(_M_h2, __x._M_h2); | |
b82f782b BK |
767 | } |
768 | ||
769 | protected: | |
95cefe5f PC |
770 | _ExtractKey _M_extract; |
771 | _Equal _M_eq; | |
772 | _H1 _M_h1; | |
773 | _H2 _M_h2; | |
b82f782b | 774 | }; |
95cefe5f | 775 | } // namespace __detail |
3b2524b1 | 776 | } |
4a15d842 FD |
777 | |
778 | _GLIBCXX_END_NAMESPACE_VERSION | |
e133ace8 | 779 | } |