?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Merge from mainline (160224:163495).
[official-gcc/graphite-test-results.git] / libstdc++-v3 / include / bits / hashtable.h
blobe62e156e523eb0f791071491dc7205fe586a67b5
1 // hashtable.h header -*- 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 bits/hashtable.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 #ifndef _HASHTABLE_H
31 #define _HASHTABLE_H 1
32
33 #pragma GCC system_header
34
35 #include <bits/hashtable_policy.h>
36
37 namespace std
38 {
39 // Class template _Hashtable, class definition.
40
41 // Meaning of class template _Hashtable's template parameters
42
43 // _Key and _Value: arbitrary CopyConstructible types.
44
45 // _Allocator: an allocator type ([lib.allocator.requirements]) whose
46 // value type is Value. As a conforming extension, we allow for
47 // value type != Value.
48
49 // _ExtractKey: function object that takes a object of type Value
50 // and returns a value of type _Key.
51
52 // _Equal: function object that takes two objects of type k and returns
53 // a bool-like value that is true if the two objects are considered equal.
54
55 // _H1: the hash function. A unary function object with argument type
56 // Key and result type size_t. Return values should be distributed
57 // over the entire range [0, numeric_limits<size_t>:::max()].
58
59 // _H2: the range-hashing function (in the terminology of Tavori and
60 // Dreizin). A binary function object whose argument types and result
61 // type are all size_t. Given arguments r and N, the return value is
62 // in the range [0, N).
63
64 // _Hash: the ranged hash function (Tavori and Dreizin). A binary function
65 // whose argument types are _Key and size_t and whose result type is
66 // size_t. Given arguments k and N, the return value is in the range
67 // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other
68 // than the default, _H1 and _H2 are ignored.
69
70 // _RehashPolicy: Policy class with three members, all of which govern
71 // the bucket count. _M_next_bkt(n) returns a bucket count no smaller
72 // than n. _M_bkt_for_elements(n) returns a bucket count appropriate
73 // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins)
74 // determines whether, if the current bucket count is n_bkt and the
75 // current element count is n_elt, we need to increase the bucket
76 // count. If so, returns make_pair(true, n), where n is the new
77 // bucket count. If not, returns make_pair(false, <anything>).
78
79 // ??? Right now it is hard-wired that the number of buckets never
80 // shrinks. Should we allow _RehashPolicy to change that?
81
82 // __cache_hash_code: bool. true if we store the value of the hash
83 // function along with the value. This is a time-space tradeoff.
84 // Storing it may improve lookup speed by reducing the number of times
85 // we need to call the Equal function.
86
87 // __constant_iterators: bool. true if iterator and const_iterator are
88 // both constant iterator types. This is true for unordered_set and
89 // unordered_multiset, false for unordered_map and unordered_multimap.
90
91 // __unique_keys: bool. true if the return value of _Hashtable::count(k)
92 // is always at most one, false if it may be an arbitrary number. This
93 // true for unordered_set and unordered_map, false for unordered_multiset
94 // and unordered_multimap.
95
96 template<typename _Key, typename _Value, typename _Allocator,
97 typename _ExtractKey, typename _Equal,
98 typename _H1, typename _H2, typename _Hash,
99 typename _RehashPolicy,
100 bool __cache_hash_code,
101 bool __constant_iterators,
102 bool __unique_keys>
103 class _Hashtable
104 : public __detail::_Rehash_base<_RehashPolicy,
105 _Hashtable<_Key, _Value, _Allocator,
106 _ExtractKey,
107 _Equal, _H1, _H2, _Hash,
108 _RehashPolicy,
109 __cache_hash_code,
110 __constant_iterators,
111 __unique_keys> >,
112 public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
113 _H1, _H2, _Hash, __cache_hash_code>,
114 public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys,
115 _Hashtable<_Key, _Value, _Allocator,
116 _ExtractKey,
117 _Equal, _H1, _H2, _Hash,
118 _RehashPolicy,
119 __cache_hash_code,
120 __constant_iterators,
121 __unique_keys> >,
122 public __detail::_Equality_base<_ExtractKey, __unique_keys,
123 _Hashtable<_Key, _Value, _Allocator,
124 _ExtractKey,
125 _Equal, _H1, _H2, _Hash,
126 _RehashPolicy,
127 __cache_hash_code,
128 __constant_iterators,
129 __unique_keys> >
130 {
131 public:
132 typedef _Allocator allocator_type;
133 typedef _Value value_type;
134 typedef _Key key_type;
135 typedef _Equal key_equal;
136 // mapped_type, if present, comes from _Map_base.
137 // hasher, if present, comes from _Hash_code_base.
138 typedef typename _Allocator::pointer pointer;
139 typedef typename _Allocator::const_pointer const_pointer;
140 typedef typename _Allocator::reference reference;
141 typedef typename _Allocator::const_reference const_reference;
142
143 typedef std::size_t size_type;
144 typedef std::ptrdiff_t difference_type;
145 typedef __detail::_Node_iterator<value_type, __constant_iterators,
146 __cache_hash_code>
147 local_iterator;
148 typedef __detail::_Node_const_iterator<value_type,
149 __constant_iterators,
150 __cache_hash_code>
151 const_local_iterator;
152
153 typedef __detail::_Hashtable_iterator<value_type, __constant_iterators,
154 __cache_hash_code>
155 iterator;
156 typedef __detail::_Hashtable_const_iterator<value_type,
157 __constant_iterators,
158 __cache_hash_code>
159 const_iterator;
160
161 template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
162 typename _Hashtable2>
163 friend struct __detail::_Map_base;
164
165 private:
166 typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
167 typedef typename _Allocator::template rebind<_Node>::other
168 _Node_allocator_type;
169 typedef typename _Allocator::template rebind<_Node*>::other
170 _Bucket_allocator_type;
171
172 typedef typename _Allocator::template rebind<_Value>::other
173 _Value_allocator_type;
174
175 _Node_allocator_type _M_node_allocator;
176 _Node** _M_buckets;
177 size_type _M_bucket_count;
178 size_type _M_element_count;
179 _RehashPolicy _M_rehash_policy;
180
181 _Node*
182 _M_allocate_node(const value_type& __v);
183
184 void
185 _M_deallocate_node(_Node* __n);
186
187 void
188 _M_deallocate_nodes(_Node**, size_type);
189
190 _Node**
191 _M_allocate_buckets(size_type __n);
192
193 void
194 _M_deallocate_buckets(_Node**, size_type __n);
195
196 public:
197 // Constructor, destructor, assignment, swap
198 _Hashtable(size_type __bucket_hint,
199 const _H1&, const _H2&, const _Hash&,
200 const _Equal&, const _ExtractKey&,
201 const allocator_type&);
202
203 template<typename _InputIterator>
204 _Hashtable(_InputIterator __first, _InputIterator __last,
205 size_type __bucket_hint,
206 const _H1&, const _H2&, const _Hash&,
207 const _Equal&, const _ExtractKey&,
208 const allocator_type&);
209
210 _Hashtable(const _Hashtable&);
211
212 _Hashtable(_Hashtable&&);
213
214 _Hashtable&
215 operator=(const _Hashtable& __ht)
216 {
217 _Hashtable __tmp(__ht);
218 this->swap(__tmp);
219 return *this;
220 }
221
222 _Hashtable&
223 operator=(_Hashtable&& __ht)
224 {
225 // NB: DR 1204.
226 // NB: DR 675.
227 this->clear();
228 this->swap(__ht);
229 return *this;
230 }
231
232 ~_Hashtable();
233
234 void swap(_Hashtable&);
235
236 // Basic container operations
237 iterator
238 begin()
239 {
240 iterator __i(_M_buckets);
241 if (!__i._M_cur_node)
242 __i._M_incr_bucket();
243 return __i;
244 }
245
246 const_iterator
247 begin() const
248 {
249 const_iterator __i(_M_buckets);
250 if (!__i._M_cur_node)
251 __i._M_incr_bucket();
252 return __i;
253 }
254
255 iterator
256 end()
257 { return iterator(_M_buckets + _M_bucket_count); }
258
259 const_iterator
260 end() const
261 { return const_iterator(_M_buckets + _M_bucket_count); }
262
263 const_iterator
264 cbegin() const
265 {
266 const_iterator __i(_M_buckets);
267 if (!__i._M_cur_node)
268 __i._M_incr_bucket();
269 return __i;
270 }
271
272 const_iterator
273 cend() const
274 { return const_iterator(_M_buckets + _M_bucket_count); }
275
276 size_type
277 size() const
278 { return _M_element_count; }
279
280 bool
281 empty() const
282 { return size() == 0; }
283
284 allocator_type
285 get_allocator() const
286 { return allocator_type(_M_node_allocator); }
287
288 _Value_allocator_type
289 _M_get_Value_allocator() const
290 { return _Value_allocator_type(_M_node_allocator); }
291
292 size_type
293 max_size() const
294 { return _M_node_allocator.max_size(); }
295
296 // Observers
297 key_equal
298 key_eq() const
299 { return this->_M_eq; }
300
301 // hash_function, if present, comes from _Hash_code_base.
302
303 // Bucket operations
304 size_type
305 bucket_count() const
306 { return _M_bucket_count; }
307
308 size_type
309 max_bucket_count() const
310 { return max_size(); }
311
312 size_type
313 bucket_size(size_type __n) const
314 { return std::distance(begin(__n), end(__n)); }
315
316 size_type
317 bucket(const key_type& __k) const
318 {
319 return this->_M_bucket_index(__k, this->_M_hash_code(__k),
320 bucket_count());
321 }
322
323 local_iterator
324 begin(size_type __n)
325 { return local_iterator(_M_buckets[__n]); }
326
327 local_iterator
328 end(size_type)
329 { return local_iterator(0); }
330
331 const_local_iterator
332 begin(size_type __n) const
333 { return const_local_iterator(_M_buckets[__n]); }
334
335 const_local_iterator
336 end(size_type) const
337 { return const_local_iterator(0); }
338
339 // DR 691.
340 const_local_iterator
341 cbegin(size_type __n) const
342 { return const_local_iterator(_M_buckets[__n]); }
343
344 const_local_iterator
345 cend(size_type) const
346 { return const_local_iterator(0); }
347
348 float
349 load_factor() const
350 {
351 return static_cast<float>(size()) / static_cast<float>(bucket_count());
352 }
353
354 // max_load_factor, if present, comes from _Rehash_base.
355
356 // Generalization of max_load_factor. Extension, not found in TR1. Only
357 // useful if _RehashPolicy is something other than the default.
358 const _RehashPolicy&
359 __rehash_policy() const
360 { return _M_rehash_policy; }
361
362 void
363 __rehash_policy(const _RehashPolicy&);
364
365 // Lookup.
366 iterator
367 find(const key_type& __k);
368
369 const_iterator
370 find(const key_type& __k) const;
371
372 size_type
373 count(const key_type& __k) const;
374
375 std::pair<iterator, iterator>
376 equal_range(const key_type& __k);
377
378 std::pair<const_iterator, const_iterator>
379 equal_range(const key_type& __k) const;
380
381 private: // Find, insert and erase helper functions
382 // ??? This dispatching is a workaround for the fact that we don't
383 // have partial specialization of member templates; it would be
384 // better to just specialize insert on __unique_keys. There may be a
385 // cleaner workaround.
386 typedef typename std::conditional<__unique_keys,
387 std::pair<iterator, bool>,
388 iterator>::type
389 _Insert_Return_Type;
390
391 typedef typename std::conditional<__unique_keys,
392 std::_Select1st<_Insert_Return_Type>,
393 std::_Identity<_Insert_Return_Type>
394 >::type
395 _Insert_Conv_Type;
396
397 _Node*
398 _M_find_node(_Node*, const key_type&,
399 typename _Hashtable::_Hash_code_type) const;
400
401 iterator
402 _M_insert_bucket(const value_type&, size_type,
403 typename _Hashtable::_Hash_code_type);
404
405 std::pair<iterator, bool>
406 _M_insert(const value_type&, std::true_type);
407
408 iterator
409 _M_insert(const value_type&, std::false_type);
410
411 void
412 _M_erase_node(_Node*, _Node**);
413
414 public:
415 // Insert and erase
416 _Insert_Return_Type
417 insert(const value_type& __v)
418 { return _M_insert(__v, std::integral_constant<bool,
419 __unique_keys>()); }
420
421 iterator
422 insert(const_iterator, const value_type& __v)
423 { return iterator(_Insert_Conv_Type()(this->insert(__v))); }
424
425 template<typename _InputIterator>
426 void
427 insert(_InputIterator __first, _InputIterator __last);
428
429 void
430 insert(initializer_list<value_type> __l)
431 { this->insert(__l.begin(), __l.end()); }
432
433 iterator
434 erase(const_iterator);
435
436 size_type
437 erase(const key_type&);
438
439 iterator
440 erase(const_iterator, const_iterator);
441
442 void
443 clear();
444
445 // Set number of buckets to be appropriate for container of n element.
446 void rehash(size_type __n);
447
448 // DR 1189.
449 // reserve, if present, comes from _Rehash_base.
450
451 private:
452 // Unconditionally change size of bucket array to n.
453 void _M_rehash(size_type __n);
454 };
455
456
457 // Definitions of class template _Hashtable's out-of-line member functions.
458 template<typename _Key, typename _Value,
459 typename _Allocator, typename _ExtractKey, typename _Equal,
460 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
461 bool __chc, bool __cit, bool __uk>
462 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
463 _H1, _H2, _Hash, _RehashPolicy,
464 __chc, __cit, __uk>::_Node*
465 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
466 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
467 _M_allocate_node(const value_type& __v)
468 {
469 _Node* __n = _M_node_allocator.allocate(1);
470 __try
471 {
472 _M_node_allocator.construct(__n, __v);
473 __n->_M_next = 0;
474 return __n;
475 }
476 __catch(...)
477 {
478 _M_node_allocator.deallocate(__n, 1);
479 __throw_exception_again;
480 }
481 }
482
483 template<typename _Key, typename _Value,
484 typename _Allocator, typename _ExtractKey, typename _Equal,
485 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
486 bool __chc, bool __cit, bool __uk>
487 void
488 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
489 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
490 _M_deallocate_node(_Node* __n)
491 {
492 _M_node_allocator.destroy(__n);
493 _M_node_allocator.deallocate(__n, 1);
494 }
495
496 template<typename _Key, typename _Value,
497 typename _Allocator, typename _ExtractKey, typename _Equal,
498 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
499 bool __chc, bool __cit, bool __uk>
500 void
501 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
502 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
503 _M_deallocate_nodes(_Node** __array, size_type __n)
504 {
505 for (size_type __i = 0; __i < __n; ++__i)
506 {
507 _Node* __p = __array[__i];
508 while (__p)
509 {
510 _Node* __tmp = __p;
511 __p = __p->_M_next;
512 _M_deallocate_node(__tmp);
513 }
514 __array[__i] = 0;
515 }
516 }
517
518 template<typename _Key, typename _Value,
519 typename _Allocator, typename _ExtractKey, typename _Equal,
520 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
521 bool __chc, bool __cit, bool __uk>
522 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
523 _H1, _H2, _Hash, _RehashPolicy,
524 __chc, __cit, __uk>::_Node**
525 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
526 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
527 _M_allocate_buckets(size_type __n)
528 {
529 _Bucket_allocator_type __alloc(_M_node_allocator);
530
531 // We allocate one extra bucket to hold a sentinel, an arbitrary
532 // non-null pointer. Iterator increment relies on this.
533 _Node** __p = __alloc.allocate(__n + 1);
534 std::fill(__p, __p + __n, (_Node*) 0);
535 __p[__n] = reinterpret_cast<_Node*>(0x1000);
536 return __p;
537 }
538
539 template<typename _Key, typename _Value,
540 typename _Allocator, typename _ExtractKey, typename _Equal,
541 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
542 bool __chc, bool __cit, bool __uk>
543 void
544 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
545 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
546 _M_deallocate_buckets(_Node** __p, size_type __n)
547 {
548 _Bucket_allocator_type __alloc(_M_node_allocator);
549 __alloc.deallocate(__p, __n + 1);
550 }
551
552 template<typename _Key, typename _Value,
553 typename _Allocator, typename _ExtractKey, typename _Equal,
554 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
555 bool __chc, bool __cit, bool __uk>
556 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
557 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
558 _Hashtable(size_type __bucket_hint,
559 const _H1& __h1, const _H2& __h2, const _Hash& __h,
560 const _Equal& __eq, const _ExtractKey& __exk,
561 const allocator_type& __a)
562 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
563 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
564 _H1, _H2, _Hash, __chc>(__exk, __eq,
565 __h1, __h2, __h),
566 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
567 _M_node_allocator(__a),
568 _M_bucket_count(0),
569 _M_element_count(0),
570 _M_rehash_policy()
571 {
572 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
573 _M_buckets = _M_allocate_buckets(_M_bucket_count);
574 }
575
576 template<typename _Key, typename _Value,
577 typename _Allocator, typename _ExtractKey, typename _Equal,
578 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
579 bool __chc, bool __cit, bool __uk>
580 template<typename _InputIterator>
581 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
582 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
583 _Hashtable(_InputIterator __f, _InputIterator __l,
584 size_type __bucket_hint,
585 const _H1& __h1, const _H2& __h2, const _Hash& __h,
586 const _Equal& __eq, const _ExtractKey& __exk,
587 const allocator_type& __a)
588 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
589 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
590 _H1, _H2, _Hash, __chc>(__exk, __eq,
591 __h1, __h2, __h),
592 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
593 _M_node_allocator(__a),
594 _M_bucket_count(0),
595 _M_element_count(0),
596 _M_rehash_policy()
597 {
598 _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
599 _M_rehash_policy.
600 _M_bkt_for_elements(__detail::
601 __distance_fw(__f,
602 __l)));
603 _M_buckets = _M_allocate_buckets(_M_bucket_count);
604 __try
605 {
606 for (; __f != __l; ++__f)
607 this->insert(*__f);
608 }
609 __catch(...)
610 {
611 clear();
612 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
613 __throw_exception_again;
614 }
615 }
616
617 template<typename _Key, typename _Value,
618 typename _Allocator, typename _ExtractKey, typename _Equal,
619 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
620 bool __chc, bool __cit, bool __uk>
621 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
622 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
623 _Hashtable(const _Hashtable& __ht)
624 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
625 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
626 _H1, _H2, _Hash, __chc>(__ht),
627 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
628 _M_node_allocator(__ht._M_node_allocator),
629 _M_bucket_count(__ht._M_bucket_count),
630 _M_element_count(__ht._M_element_count),
631 _M_rehash_policy(__ht._M_rehash_policy)
632 {
633 _M_buckets = _M_allocate_buckets(_M_bucket_count);
634 __try
635 {
636 for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i)
637 {
638 _Node* __n = __ht._M_buckets[__i];
639 _Node** __tail = _M_buckets + __i;
640 while (__n)
641 {
642 *__tail = _M_allocate_node(__n->_M_v);
643 this->_M_copy_code(*__tail, __n);
644 __tail = &((*__tail)->_M_next);
645 __n = __n->_M_next;
646 }
647 }
648 }
649 __catch(...)
650 {
651 clear();
652 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
653 __throw_exception_again;
654 }
655 }
656
657 template<typename _Key, typename _Value,
658 typename _Allocator, typename _ExtractKey, typename _Equal,
659 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
660 bool __chc, bool __cit, bool __uk>
661 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
662 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
663 _Hashtable(_Hashtable&& __ht)
664 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
665 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
666 _H1, _H2, _Hash, __chc>(__ht),
667 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
668 _M_node_allocator(__ht._M_node_allocator),
669 _M_buckets(__ht._M_buckets),
670 _M_bucket_count(__ht._M_bucket_count),
671 _M_element_count(__ht._M_element_count),
672 _M_rehash_policy(__ht._M_rehash_policy)
673 {
674 size_type __n_bkt = __ht._M_rehash_policy._M_next_bkt(0);
675 __ht._M_buckets = __ht._M_allocate_buckets(__n_bkt);
676 __ht._M_bucket_count = __n_bkt;
677 __ht._M_element_count = 0;
678 __ht._M_rehash_policy = _RehashPolicy();
679 }
680
681 template<typename _Key, typename _Value,
682 typename _Allocator, typename _ExtractKey, typename _Equal,
683 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
684 bool __chc, bool __cit, bool __uk>
685 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
686 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
687 ~_Hashtable()
688 {
689 clear();
690 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
691 }
692
693 template<typename _Key, typename _Value,
694 typename _Allocator, typename _ExtractKey, typename _Equal,
695 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
696 bool __chc, bool __cit, bool __uk>
697 void
698 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
699 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
700 swap(_Hashtable& __x)
701 {
702 // The only base class with member variables is hash_code_base. We
703 // define _Hash_code_base::_M_swap because different specializations
704 // have different members.
705 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
706 _H1, _H2, _Hash, __chc>::_M_swap(__x);
707
708 // _GLIBCXX_RESOLVE_LIB_DEFECTS
709 // 431. Swapping containers with unequal allocators.
710 std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
711 __x._M_node_allocator);
712
713 std::swap(_M_rehash_policy, __x._M_rehash_policy);
714 std::swap(_M_buckets, __x._M_buckets);
715 std::swap(_M_bucket_count, __x._M_bucket_count);
716 std::swap(_M_element_count, __x._M_element_count);
717 }
718
719 template<typename _Key, typename _Value,
720 typename _Allocator, typename _ExtractKey, typename _Equal,
721 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
722 bool __chc, bool __cit, bool __uk>
723 void
724 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
725 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
726 __rehash_policy(const _RehashPolicy& __pol)
727 {
728 _M_rehash_policy = __pol;
729 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
730 if (__n_bkt > _M_bucket_count)
731 _M_rehash(__n_bkt);
732 }
733
734 template<typename _Key, typename _Value,
735 typename _Allocator, typename _ExtractKey, typename _Equal,
736 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
737 bool __chc, bool __cit, bool __uk>
738 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
739 _H1, _H2, _Hash, _RehashPolicy,
740 __chc, __cit, __uk>::iterator
741 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
742 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
743 find(const key_type& __k)
744 {
745 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
746 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
747 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
748 return __p ? iterator(__p, _M_buckets + __n) : this->end();
749 }
750
751 template<typename _Key, typename _Value,
752 typename _Allocator, typename _ExtractKey, typename _Equal,
753 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
754 bool __chc, bool __cit, bool __uk>
755 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
756 _H1, _H2, _Hash, _RehashPolicy,
757 __chc, __cit, __uk>::const_iterator
758 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
759 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
760 find(const key_type& __k) const
761 {
762 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
763 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
764 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
765 return __p ? const_iterator(__p, _M_buckets + __n) : this->end();
766 }
767
768 template<typename _Key, typename _Value,
769 typename _Allocator, typename _ExtractKey, typename _Equal,
770 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
771 bool __chc, bool __cit, bool __uk>
772 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
773 _H1, _H2, _Hash, _RehashPolicy,
774 __chc, __cit, __uk>::size_type
775 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
776 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
777 count(const key_type& __k) const
778 {
779 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
780 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
781 std::size_t __result = 0;
782 for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next)
783 if (this->_M_compare(__k, __code, __p))
784 ++__result;
785 return __result;
786 }
787
788 template<typename _Key, typename _Value,
789 typename _Allocator, typename _ExtractKey, typename _Equal,
790 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
791 bool __chc, bool __cit, bool __uk>
792 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
793 _ExtractKey, _Equal, _H1,
794 _H2, _Hash, _RehashPolicy,
795 __chc, __cit, __uk>::iterator,
796 typename _Hashtable<_Key, _Value, _Allocator,
797 _ExtractKey, _Equal, _H1,
798 _H2, _Hash, _RehashPolicy,
799 __chc, __cit, __uk>::iterator>
800 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
801 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
802 equal_range(const key_type& __k)
803 {
804 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
805 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
806 _Node** __head = _M_buckets + __n;
807 _Node* __p = _M_find_node(*__head, __k, __code);
808
809 if (__p)
810 {
811 _Node* __p1 = __p->_M_next;
812 for (; __p1; __p1 = __p1->_M_next)
813 if (!this->_M_compare(__k, __code, __p1))
814 break;
815
816 iterator __first(__p, __head);
817 iterator __last(__p1, __head);
818 if (!__p1)
819 __last._M_incr_bucket();
820 return std::make_pair(__first, __last);
821 }
822 else
823 return std::make_pair(this->end(), this->end());
824 }
825
826 template<typename _Key, typename _Value,
827 typename _Allocator, typename _ExtractKey, typename _Equal,
828 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
829 bool __chc, bool __cit, bool __uk>
830 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
831 _ExtractKey, _Equal, _H1,
832 _H2, _Hash, _RehashPolicy,
833 __chc, __cit, __uk>::const_iterator,
834 typename _Hashtable<_Key, _Value, _Allocator,
835 _ExtractKey, _Equal, _H1,
836 _H2, _Hash, _RehashPolicy,
837 __chc, __cit, __uk>::const_iterator>
838 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
839 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
840 equal_range(const key_type& __k) const
841 {
842 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
843 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
844 _Node** __head = _M_buckets + __n;
845 _Node* __p = _M_find_node(*__head, __k, __code);
846
847 if (__p)
848 {
849 _Node* __p1 = __p->_M_next;
850 for (; __p1; __p1 = __p1->_M_next)
851 if (!this->_M_compare(__k, __code, __p1))
852 break;
853
854 const_iterator __first(__p, __head);
855 const_iterator __last(__p1, __head);
856 if (!__p1)
857 __last._M_incr_bucket();
858 return std::make_pair(__first, __last);
859 }
860 else
861 return std::make_pair(this->end(), this->end());
862 }
863
864 // Find the node whose key compares equal to k, beginning the search
865 // at p (usually the head of a bucket). Return nil if no node is found.
866 template<typename _Key, typename _Value,
867 typename _Allocator, typename _ExtractKey, typename _Equal,
868 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
869 bool __chc, bool __cit, bool __uk>
870 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
871 _Equal, _H1, _H2, _Hash, _RehashPolicy,
872 __chc, __cit, __uk>::_Node*
873 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
874 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
875 _M_find_node(_Node* __p, const key_type& __k,
876 typename _Hashtable::_Hash_code_type __code) const
877 {
878 for (; __p; __p = __p->_M_next)
879 if (this->_M_compare(__k, __code, __p))
880 return __p;
881 return false;
882 }
883
884 // Insert v in bucket n (assumes no element with its key already present).
885 template<typename _Key, typename _Value,
886 typename _Allocator, typename _ExtractKey, typename _Equal,
887 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
888 bool __chc, bool __cit, bool __uk>
889 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
890 _H1, _H2, _Hash, _RehashPolicy,
891 __chc, __cit, __uk>::iterator
892 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
893 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
894 _M_insert_bucket(const value_type& __v, size_type __n,
895 typename _Hashtable::_Hash_code_type __code)
896 {
897 std::pair<bool, std::size_t> __do_rehash
898 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
899 _M_element_count, 1);
900
901 // Allocate the new node before doing the rehash so that we don't
902 // do a rehash if the allocation throws.
903 _Node* __new_node = _M_allocate_node(__v);
904
905 __try
906 {
907 if (__do_rehash.first)
908 {
909 const key_type& __k = this->_M_extract(__v);
910 __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
911 _M_rehash(__do_rehash.second);
912 }
913
914 __new_node->_M_next = _M_buckets[__n];
915 this->_M_store_code(__new_node, __code);
916 _M_buckets[__n] = __new_node;
917 ++_M_element_count;
918 return iterator(__new_node, _M_buckets + __n);
919 }
920 __catch(...)
921 {
922 _M_deallocate_node(__new_node);
923 __throw_exception_again;
924 }
925 }
926
927 // Insert v if no element with its key is already present.
928 template<typename _Key, typename _Value,
929 typename _Allocator, typename _ExtractKey, typename _Equal,
930 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
931 bool __chc, bool __cit, bool __uk>
932 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
933 _ExtractKey, _Equal, _H1,
934 _H2, _Hash, _RehashPolicy,
935 __chc, __cit, __uk>::iterator, bool>
936 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
937 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
938 _M_insert(const value_type& __v, std::true_type)
939 {
940 const key_type& __k = this->_M_extract(__v);
941 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
942 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
943
944 if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code))
945 return std::make_pair(iterator(__p, _M_buckets + __n), false);
946 return std::make_pair(_M_insert_bucket(__v, __n, __code), true);
947 }
948
949 // Insert v unconditionally.
950 template<typename _Key, typename _Value,
951 typename _Allocator, typename _ExtractKey, typename _Equal,
952 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
953 bool __chc, bool __cit, bool __uk>
954 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
955 _H1, _H2, _Hash, _RehashPolicy,
956 __chc, __cit, __uk>::iterator
957 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
958 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
959 _M_insert(const value_type& __v, std::false_type)
960 {
961 std::pair<bool, std::size_t> __do_rehash
962 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
963 _M_element_count, 1);
964 if (__do_rehash.first)
965 _M_rehash(__do_rehash.second);
966
967 const key_type& __k = this->_M_extract(__v);
968 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
969 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
970
971 // First find the node, avoid leaking new_node if compare throws.
972 _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code);
973 _Node* __new_node = _M_allocate_node(__v);
974
975 if (__prev)
976 {
977 __new_node->_M_next = __prev->_M_next;
978 __prev->_M_next = __new_node;
979 }
980 else
981 {
982 __new_node->_M_next = _M_buckets[__n];
983 _M_buckets[__n] = __new_node;
984 }
985 this->_M_store_code(__new_node, __code);
986
987 ++_M_element_count;
988 return iterator(__new_node, _M_buckets + __n);
989 }
990
991 // For erase(iterator) and erase(const_iterator).
992 template<typename _Key, typename _Value,
993 typename _Allocator, typename _ExtractKey, typename _Equal,
994 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
995 bool __chc, bool __cit, bool __uk>
996 void
997 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
998 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
999 _M_erase_node(_Node* __p, _Node** __b)
1000 {
1001 _Node* __cur = *__b;
1002 if (__cur == __p)
1003 *__b = __cur->_M_next;
1004 else
1005 {
1006 _Node* __next = __cur->_M_next;
1007 while (__next != __p)
1008 {
1009 __cur = __next;
1010 __next = __cur->_M_next;
1011 }
1012 __cur->_M_next = __next->_M_next;
1013 }
1014
1015 _M_deallocate_node(__p);
1016 --_M_element_count;
1017 }
1018
1019 template<typename _Key, typename _Value,
1020 typename _Allocator, typename _ExtractKey, typename _Equal,
1021 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1022 bool __chc, bool __cit, bool __uk>
1023 template<typename _InputIterator>
1024 void
1025 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1026 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1027 insert(_InputIterator __first, _InputIterator __last)
1028 {
1029 size_type __n_elt = __detail::__distance_fw(__first, __last);
1030 std::pair<bool, std::size_t> __do_rehash
1031 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1032 _M_element_count, __n_elt);
1033 if (__do_rehash.first)
1034 _M_rehash(__do_rehash.second);
1035
1036 for (; __first != __last; ++__first)
1037 this->insert(*__first);
1038 }
1039
1040 template<typename _Key, typename _Value,
1041 typename _Allocator, typename _ExtractKey, typename _Equal,
1042 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1043 bool __chc, bool __cit, bool __uk>
1044 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1045 _H1, _H2, _Hash, _RehashPolicy,
1046 __chc, __cit, __uk>::iterator
1047 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1048 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1049 erase(const_iterator __it)
1050 {
1051 iterator __result(__it._M_cur_node, __it._M_cur_bucket);
1052 ++__result;
1053 _M_erase_node(__it._M_cur_node, __it._M_cur_bucket);
1054 return __result;
1055 }
1056
1057 template<typename _Key, typename _Value,
1058 typename _Allocator, typename _ExtractKey, typename _Equal,
1059 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1060 bool __chc, bool __cit, bool __uk>
1061 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1062 _H1, _H2, _Hash, _RehashPolicy,
1063 __chc, __cit, __uk>::size_type
1064 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1065 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1066 erase(const key_type& __k)
1067 {
1068 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1069 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
1070 size_type __result = 0;
1071
1072 _Node** __slot = _M_buckets + __n;
1073 while (*__slot && !this->_M_compare(__k, __code, *__slot))
1074 __slot = &((*__slot)->_M_next);
1075
1076 _Node** __saved_slot = 0;
1077 while (*__slot && this->_M_compare(__k, __code, *__slot))
1078 {
1079 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1080 // 526. Is it undefined if a function in the standard changes
1081 // in parameters?
1082 if (std::__addressof(this->_M_extract((*__slot)->_M_v))
1083 != std::__addressof(__k))
1084 {
1085 _Node* __p = *__slot;
1086 *__slot = __p->_M_next;
1087 _M_deallocate_node(__p);
1088 --_M_element_count;
1089 ++__result;
1090 }
1091 else
1092 {
1093 __saved_slot = __slot;
1094 __slot = &((*__slot)->_M_next);
1095 }
1096 }
1097
1098 if (__saved_slot)
1099 {
1100 _Node* __p = *__saved_slot;
1101 *__saved_slot = __p->_M_next;
1102 _M_deallocate_node(__p);
1103 --_M_element_count;
1104 ++__result;
1105 }
1106
1107 return __result;
1108 }
1109
1110 // ??? This could be optimized by taking advantage of the bucket
1111 // structure, but it's not clear that it's worth doing. It probably
1112 // wouldn't even be an optimization unless the load factor is large.
1113 template<typename _Key, typename _Value,
1114 typename _Allocator, typename _ExtractKey, typename _Equal,
1115 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1116 bool __chc, bool __cit, bool __uk>
1117 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1118 _H1, _H2, _Hash, _RehashPolicy,
1119 __chc, __cit, __uk>::iterator
1120 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1121 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1122 erase(const_iterator __first, const_iterator __last)
1123 {
1124 while (__first != __last)
1125 __first = this->erase(__first);
1126 return iterator(__last._M_cur_node, __last._M_cur_bucket);
1127 }
1128
1129 template<typename _Key, typename _Value,
1130 typename _Allocator, typename _ExtractKey, typename _Equal,
1131 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1132 bool __chc, bool __cit, bool __uk>
1133 void
1134 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1135 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1136 clear()
1137 {
1138 _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1139 _M_element_count = 0;
1140 }
1141
1142 template<typename _Key, typename _Value,
1143 typename _Allocator, typename _ExtractKey, typename _Equal,
1144 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1145 bool __chc, bool __cit, bool __uk>
1146 void
1147 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1148 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1149 rehash(size_type __n)
1150 {
1151 _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
1152 _M_rehash_policy._M_bkt_for_elements(_M_element_count
1153 + 1)));
1154 }
1155
1156 template<typename _Key, typename _Value,
1157 typename _Allocator, typename _ExtractKey, typename _Equal,
1158 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1159 bool __chc, bool __cit, bool __uk>
1160 void
1161 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1162 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1163 _M_rehash(size_type __n)
1164 {
1165 _Node** __new_array = _M_allocate_buckets(__n);
1166 __try
1167 {
1168 for (size_type __i = 0; __i < _M_bucket_count; ++__i)
1169 while (_Node* __p = _M_buckets[__i])
1170 {
1171 std::size_t __new_index = this->_M_bucket_index(__p, __n);
1172 _M_buckets[__i] = __p->_M_next;
1173 __p->_M_next = __new_array[__new_index];
1174 __new_array[__new_index] = __p;
1175 }
1176 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1177 _M_bucket_count = __n;
1178 _M_buckets = __new_array;
1179 }
1180 __catch(...)
1181 {
1182 // A failure here means that a hash function threw an exception.
1183 // We can't restore the previous state without calling the hash
1184 // function again, so the only sensible recovery is to delete
1185 // everything.
1186 _M_deallocate_nodes(__new_array, __n);
1187 _M_deallocate_buckets(__new_array, __n);
1188 _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1189 _M_element_count = 0;
1190 __throw_exception_again;
1191 }
1192 }
1193 }
1194
1195 #endif // _HASHTABLE_H
GCC graphite test results