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