1 // hashtable.h header -*- C++ -*-
3 // Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
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)
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.
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.
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/>.
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.
31 #define _HASHTABLE_H 1
33 #pragma GCC system_header
35 #include <bits/hashtable_policy.h>
39 // Class template _Hashtable, class definition.
41 // Meaning of class template _Hashtable's template parameters
43 // _Key and _Value: arbitrary CopyConstructible types.
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.
49 // _ExtractKey: function object that takes a object of type Value
50 // and returns a value of type _Key.
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.
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()].
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).
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.
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>).
79 // ??? Right now it is hard-wired that the number of buckets never
80 // shrinks. Should we allow _RehashPolicy to change that?
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.
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.
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.
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
,
104 : public __detail::_Rehash_base
<_RehashPolicy
,
105 _Hashtable
<_Key
, _Value
, _Allocator
,
107 _Equal
, _H1
, _H2
, _Hash
,
110 __constant_iterators
,
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
,
117 _Equal
, _H1
, _H2
, _Hash
,
120 __constant_iterators
,
124 typedef _Allocator allocator_type
;
125 typedef _Value value_type
;
126 typedef _Key key_type
;
127 typedef _Equal key_equal
;
128 // mapped_type, if present, comes from _Map_base.
129 // hasher, if present, comes from _Hash_code_base.
130 typedef typename
_Allocator::difference_type difference_type
;
131 typedef typename
_Allocator::size_type size_type
;
132 typedef typename
_Allocator::pointer pointer
;
133 typedef typename
_Allocator::const_pointer const_pointer
;
134 typedef typename
_Allocator::reference reference
;
135 typedef typename
_Allocator::const_reference const_reference
;
137 typedef __detail::_Node_iterator
<value_type
, __constant_iterators
,
140 typedef __detail::_Node_const_iterator
<value_type
,
141 __constant_iterators
,
143 const_local_iterator
;
145 typedef __detail::_Hashtable_iterator
<value_type
, __constant_iterators
,
148 typedef __detail::_Hashtable_const_iterator
<value_type
,
149 __constant_iterators
,
153 template<typename _Key2
, typename _Value2
, typename _Ex2
, bool __unique2
,
154 typename _Hashtable2
>
155 friend struct __detail::_Map_base
;
158 typedef __detail::_Hash_node
<_Value
, __cache_hash_code
> _Node
;
159 typedef typename
_Allocator::template rebind
<_Node
>::other
160 _Node_allocator_type
;
161 typedef typename
_Allocator::template rebind
<_Node
*>::other
162 _Bucket_allocator_type
;
164 typedef typename
_Allocator::template rebind
<_Value
>::other
165 _Value_allocator_type
;
167 _Node_allocator_type _M_node_allocator
;
169 size_type _M_bucket_count
;
170 size_type _M_element_count
;
171 _RehashPolicy _M_rehash_policy
;
174 _M_allocate_node(const value_type
& __v
);
177 _M_deallocate_node(_Node
* __n
);
180 _M_deallocate_nodes(_Node
**, size_type
);
183 _M_allocate_buckets(size_type __n
);
186 _M_deallocate_buckets(_Node
**, size_type __n
);
189 // Constructor, destructor, assignment, swap
190 _Hashtable(size_type __bucket_hint
,
191 const _H1
&, const _H2
&, const _Hash
&,
192 const _Equal
&, const _ExtractKey
&,
193 const allocator_type
&);
195 template<typename _InputIterator
>
196 _Hashtable(_InputIterator __first
, _InputIterator __last
,
197 size_type __bucket_hint
,
198 const _H1
&, const _H2
&, const _Hash
&,
199 const _Equal
&, const _ExtractKey
&,
200 const allocator_type
&);
202 _Hashtable(const _Hashtable
&);
204 _Hashtable(_Hashtable
&&);
207 operator=(const _Hashtable
&);
211 void swap(_Hashtable
&);
213 // Basic container operations
217 iterator
__i(_M_buckets
);
218 if (!__i
._M_cur_node
)
219 __i
._M_incr_bucket();
226 const_iterator
__i(_M_buckets
);
227 if (!__i
._M_cur_node
)
228 __i
._M_incr_bucket();
234 { return iterator(_M_buckets
+ _M_bucket_count
); }
238 { return const_iterator(_M_buckets
+ _M_bucket_count
); }
243 const_iterator
__i(_M_buckets
);
244 if (!__i
._M_cur_node
)
245 __i
._M_incr_bucket();
251 { return const_iterator(_M_buckets
+ _M_bucket_count
); }
255 { return _M_element_count
; }
259 { return size() == 0; }
262 get_allocator() const
263 { return allocator_type(_M_node_allocator
); }
265 _Value_allocator_type
266 _M_get_Value_allocator() const
267 { return _Value_allocator_type(_M_node_allocator
); }
271 { return _M_node_allocator
.max_size(); }
276 { return this->_M_eq
; }
278 // hash_function, if present, comes from _Hash_code_base.
283 { return _M_bucket_count
; }
286 max_bucket_count() const
287 { return max_size(); }
290 bucket_size(size_type __n
) const
291 { return std::distance(begin(__n
), end(__n
)); }
294 bucket(const key_type
& __k
) const
296 return this->_M_bucket_index(__k
, this->_M_hash_code(__k
),
302 { return local_iterator(_M_buckets
[__n
]); }
306 { return local_iterator(0); }
309 begin(size_type __n
) const
310 { return const_local_iterator(_M_buckets
[__n
]); }
314 { return const_local_iterator(0); }
318 cbegin(size_type __n
) const
319 { return const_local_iterator(_M_buckets
[__n
]); }
322 cend(size_type
) const
323 { return const_local_iterator(0); }
328 return static_cast<float>(size()) / static_cast<float>(bucket_count());
331 // max_load_factor, if present, comes from _Rehash_base.
333 // Generalization of max_load_factor. Extension, not found in TR1. Only
334 // useful if _RehashPolicy is something other than the default.
336 __rehash_policy() const
337 { return _M_rehash_policy
; }
340 __rehash_policy(const _RehashPolicy
&);
344 find(const key_type
& __k
);
347 find(const key_type
& __k
) const;
350 count(const key_type
& __k
) const;
352 std::pair
<iterator
, iterator
>
353 equal_range(const key_type
& __k
);
355 std::pair
<const_iterator
, const_iterator
>
356 equal_range(const key_type
& __k
) const;
358 private: // Find, insert and erase helper functions
359 // ??? This dispatching is a workaround for the fact that we don't
360 // have partial specialization of member templates; it would be
361 // better to just specialize insert on __unique_keys. There may be a
362 // cleaner workaround.
363 typedef typename
std::conditional
<__unique_keys
,
364 std::pair
<iterator
, bool>,
368 typedef typename
std::conditional
<__unique_keys
,
369 std::_Select1st
<_Insert_Return_Type
>,
370 std::_Identity
<_Insert_Return_Type
>
375 _M_find_node(_Node
*, const key_type
&,
376 typename
_Hashtable::_Hash_code_type
) const;
379 _M_insert_bucket(const value_type
&, size_type
,
380 typename
_Hashtable::_Hash_code_type
);
382 std::pair
<iterator
, bool>
383 _M_insert(const value_type
&, std::true_type
);
386 _M_insert(const value_type
&, std::false_type
);
389 _M_erase_node(_Node
*, _Node
**);
394 insert(const value_type
& __v
)
395 { return _M_insert(__v
, std::integral_constant
<bool,
399 insert(const_iterator
, const value_type
& __v
)
400 { return iterator(_Insert_Conv_Type()(this->insert(__v
))); }
402 template<typename _InputIterator
>
404 insert(_InputIterator __first
, _InputIterator __last
);
407 insert(initializer_list
<value_type
> __l
)
408 { this->insert(__l
.begin(), __l
.end()); }
411 erase(const_iterator
);
414 erase(const key_type
&);
417 erase(const_iterator
, const_iterator
);
422 // Set number of buckets to be appropriate for container of n element.
423 void rehash(size_type __n
);
426 // Unconditionally change size of bucket array to n.
427 void _M_rehash(size_type __n
);
431 // Definitions of class template _Hashtable's out-of-line member functions.
432 template<typename _Key
, typename _Value
,
433 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
434 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
435 bool __chc
, bool __cit
, bool __uk
>
436 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
437 _H1
, _H2
, _Hash
, _RehashPolicy
,
438 __chc
, __cit
, __uk
>::_Node
*
439 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
440 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
441 _M_allocate_node(const value_type
& __v
)
443 _Node
* __n
= _M_node_allocator
.allocate(1);
446 _M_node_allocator
.construct(__n
, __v
);
452 _M_node_allocator
.deallocate(__n
, 1);
453 __throw_exception_again
;
457 template<typename _Key
, typename _Value
,
458 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
459 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
460 bool __chc
, bool __cit
, bool __uk
>
462 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
463 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
464 _M_deallocate_node(_Node
* __n
)
466 _M_node_allocator
.destroy(__n
);
467 _M_node_allocator
.deallocate(__n
, 1);
470 template<typename _Key
, typename _Value
,
471 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
472 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
473 bool __chc
, bool __cit
, bool __uk
>
475 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
476 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
477 _M_deallocate_nodes(_Node
** __array
, size_type __n
)
479 for (size_type __i
= 0; __i
< __n
; ++__i
)
481 _Node
* __p
= __array
[__i
];
486 _M_deallocate_node(__tmp
);
492 template<typename _Key
, typename _Value
,
493 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
494 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
495 bool __chc
, bool __cit
, bool __uk
>
496 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
497 _H1
, _H2
, _Hash
, _RehashPolicy
,
498 __chc
, __cit
, __uk
>::_Node
**
499 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
500 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
501 _M_allocate_buckets(size_type __n
)
503 _Bucket_allocator_type
__alloc(_M_node_allocator
);
505 // We allocate one extra bucket to hold a sentinel, an arbitrary
506 // non-null pointer. Iterator increment relies on this.
507 _Node
** __p
= __alloc
.allocate(__n
+ 1);
508 std::fill(__p
, __p
+ __n
, (_Node
*) 0);
509 __p
[__n
] = reinterpret_cast<_Node
*>(0x1000);
513 template<typename _Key
, typename _Value
,
514 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
515 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
516 bool __chc
, bool __cit
, bool __uk
>
518 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
519 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
520 _M_deallocate_buckets(_Node
** __p
, size_type __n
)
522 _Bucket_allocator_type
__alloc(_M_node_allocator
);
523 __alloc
.deallocate(__p
, __n
+ 1);
526 template<typename _Key
, typename _Value
,
527 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
528 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
529 bool __chc
, bool __cit
, bool __uk
>
530 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
531 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
532 _Hashtable(size_type __bucket_hint
,
533 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
534 const _Equal
& __eq
, const _ExtractKey
& __exk
,
535 const allocator_type
& __a
)
536 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(),
537 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
538 _H1
, _H2
, _Hash
, __chc
>(__exk
, __eq
,
540 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(),
541 _M_node_allocator(__a
),
546 _M_bucket_count
= _M_rehash_policy
._M_next_bkt(__bucket_hint
);
547 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
550 template<typename _Key
, typename _Value
,
551 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
552 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
553 bool __chc
, bool __cit
, bool __uk
>
554 template<typename _InputIterator
>
555 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
556 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
557 _Hashtable(_InputIterator __f
, _InputIterator __l
,
558 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
,
566 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(),
567 _M_node_allocator(__a
),
572 _M_bucket_count
= std::max(_M_rehash_policy
._M_next_bkt(__bucket_hint
),
574 _M_bkt_for_elements(__detail::
577 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
580 for (; __f
!= __l
; ++__f
)
586 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
587 __throw_exception_again
;
591 template<typename _Key
, typename _Value
,
592 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
593 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
594 bool __chc
, bool __cit
, bool __uk
>
595 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
596 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
597 _Hashtable(const _Hashtable
& __ht
)
598 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(__ht
),
599 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
600 _H1
, _H2
, _Hash
, __chc
>(__ht
),
601 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(__ht
),
602 _M_node_allocator(__ht
._M_node_allocator
),
603 _M_bucket_count(__ht
._M_bucket_count
),
604 _M_element_count(__ht
._M_element_count
),
605 _M_rehash_policy(__ht
._M_rehash_policy
)
607 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
610 for (size_type __i
= 0; __i
< __ht
._M_bucket_count
; ++__i
)
612 _Node
* __n
= __ht
._M_buckets
[__i
];
613 _Node
** __tail
= _M_buckets
+ __i
;
616 *__tail
= _M_allocate_node(__n
->_M_v
);
617 this->_M_copy_code(*__tail
, __n
);
618 __tail
= &((*__tail
)->_M_next
);
626 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
627 __throw_exception_again
;
631 template<typename _Key
, typename _Value
,
632 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
633 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
634 bool __chc
, bool __cit
, bool __uk
>
635 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
636 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
637 _Hashtable(_Hashtable
&& __ht
)
638 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(__ht
),
639 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
640 _H1
, _H2
, _Hash
, __chc
>(__ht
),
641 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(__ht
),
642 _M_node_allocator(__ht
._M_node_allocator
),
643 _M_bucket_count(__ht
._M_bucket_count
),
644 _M_element_count(__ht
._M_element_count
),
645 _M_rehash_policy(__ht
._M_rehash_policy
),
646 _M_buckets(__ht
._M_buckets
)
648 size_type __n_bkt
= __ht
._M_rehash_policy
._M_next_bkt(0);
649 __ht
._M_buckets
= __ht
._M_allocate_buckets(__n_bkt
);
650 __ht
._M_bucket_count
= __n_bkt
;
651 __ht
._M_element_count
= 0;
652 __ht
._M_rehash_policy
= _RehashPolicy();
655 template<typename _Key
, typename _Value
,
656 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
657 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
658 bool __chc
, bool __cit
, bool __uk
>
659 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
660 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>&
661 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
662 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
663 operator=(const _Hashtable
& __ht
)
665 _Hashtable
__tmp(__ht
);
670 template<typename _Key
, typename _Value
,
671 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
672 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
673 bool __chc
, bool __cit
, bool __uk
>
674 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
675 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
679 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
682 template<typename _Key
, typename _Value
,
683 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
684 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
685 bool __chc
, bool __cit
, bool __uk
>
687 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
688 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
689 swap(_Hashtable
& __x
)
691 // The only base class with member variables is hash_code_base. We
692 // define _Hash_code_base::_M_swap because different specializations
693 // have different members.
694 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
695 _H1
, _H2
, _Hash
, __chc
>::_M_swap(__x
);
697 // _GLIBCXX_RESOLVE_LIB_DEFECTS
698 // 431. Swapping containers with unequal allocators.
699 std::__alloc_swap
<_Node_allocator_type
>::_S_do_it(_M_node_allocator
,
700 __x
._M_node_allocator
);
702 std::swap(_M_rehash_policy
, __x
._M_rehash_policy
);
703 std::swap(_M_buckets
, __x
._M_buckets
);
704 std::swap(_M_bucket_count
, __x
._M_bucket_count
);
705 std::swap(_M_element_count
, __x
._M_element_count
);
708 template<typename _Key
, typename _Value
,
709 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
710 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
711 bool __chc
, bool __cit
, bool __uk
>
713 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
714 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
715 __rehash_policy(const _RehashPolicy
& __pol
)
717 _M_rehash_policy
= __pol
;
718 size_type __n_bkt
= __pol
._M_bkt_for_elements(_M_element_count
);
719 if (__n_bkt
> _M_bucket_count
)
723 template<typename _Key
, typename _Value
,
724 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
725 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
726 bool __chc
, bool __cit
, bool __uk
>
727 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
728 _H1
, _H2
, _Hash
, _RehashPolicy
,
729 __chc
, __cit
, __uk
>::iterator
730 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
731 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
732 find(const key_type
& __k
)
734 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
735 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
736 _Node
* __p
= _M_find_node(_M_buckets
[__n
], __k
, __code
);
737 return __p
? iterator(__p
, _M_buckets
+ __n
) : this->end();
740 template<typename _Key
, typename _Value
,
741 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
742 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
743 bool __chc
, bool __cit
, bool __uk
>
744 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
745 _H1
, _H2
, _Hash
, _RehashPolicy
,
746 __chc
, __cit
, __uk
>::const_iterator
747 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
748 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
749 find(const key_type
& __k
) const
751 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
752 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
753 _Node
* __p
= _M_find_node(_M_buckets
[__n
], __k
, __code
);
754 return __p
? const_iterator(__p
, _M_buckets
+ __n
) : this->end();
757 template<typename _Key
, typename _Value
,
758 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
759 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
760 bool __chc
, bool __cit
, bool __uk
>
761 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
762 _H1
, _H2
, _Hash
, _RehashPolicy
,
763 __chc
, __cit
, __uk
>::size_type
764 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
765 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
766 count(const key_type
& __k
) const
768 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
769 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
770 std::size_t __result
= 0;
771 for (_Node
* __p
= _M_buckets
[__n
]; __p
; __p
= __p
->_M_next
)
772 if (this->_M_compare(__k
, __code
, __p
))
777 template<typename _Key
, typename _Value
,
778 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
779 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
780 bool __chc
, bool __cit
, bool __uk
>
781 std::pair
<typename _Hashtable
<_Key
, _Value
, _Allocator
,
782 _ExtractKey
, _Equal
, _H1
,
783 _H2
, _Hash
, _RehashPolicy
,
784 __chc
, __cit
, __uk
>::iterator
,
785 typename _Hashtable
<_Key
, _Value
, _Allocator
,
786 _ExtractKey
, _Equal
, _H1
,
787 _H2
, _Hash
, _RehashPolicy
,
788 __chc
, __cit
, __uk
>::iterator
>
789 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
790 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
791 equal_range(const key_type
& __k
)
793 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
794 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
795 _Node
** __head
= _M_buckets
+ __n
;
796 _Node
* __p
= _M_find_node(*__head
, __k
, __code
);
800 _Node
* __p1
= __p
->_M_next
;
801 for (; __p1
; __p1
= __p1
->_M_next
)
802 if (!this->_M_compare(__k
, __code
, __p1
))
805 iterator
__first(__p
, __head
);
806 iterator
__last(__p1
, __head
);
808 __last
._M_incr_bucket();
809 return std::make_pair(__first
, __last
);
812 return std::make_pair(this->end(), this->end());
815 template<typename _Key
, typename _Value
,
816 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
817 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
818 bool __chc
, bool __cit
, bool __uk
>
819 std::pair
<typename _Hashtable
<_Key
, _Value
, _Allocator
,
820 _ExtractKey
, _Equal
, _H1
,
821 _H2
, _Hash
, _RehashPolicy
,
822 __chc
, __cit
, __uk
>::const_iterator
,
823 typename _Hashtable
<_Key
, _Value
, _Allocator
,
824 _ExtractKey
, _Equal
, _H1
,
825 _H2
, _Hash
, _RehashPolicy
,
826 __chc
, __cit
, __uk
>::const_iterator
>
827 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
828 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
829 equal_range(const key_type
& __k
) const
831 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
832 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
833 _Node
** __head
= _M_buckets
+ __n
;
834 _Node
* __p
= _M_find_node(*__head
, __k
, __code
);
838 _Node
* __p1
= __p
->_M_next
;
839 for (; __p1
; __p1
= __p1
->_M_next
)
840 if (!this->_M_compare(__k
, __code
, __p1
))
843 const_iterator
__first(__p
, __head
);
844 const_iterator
__last(__p1
, __head
);
846 __last
._M_incr_bucket();
847 return std::make_pair(__first
, __last
);
850 return std::make_pair(this->end(), this->end());
853 // Find the node whose key compares equal to k, beginning the search
854 // at p (usually the head of a bucket). Return nil if no node is found.
855 template<typename _Key
, typename _Value
,
856 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
857 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
858 bool __chc
, bool __cit
, bool __uk
>
859 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
,
860 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
861 __chc
, __cit
, __uk
>::_Node
*
862 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
863 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
864 _M_find_node(_Node
* __p
, const key_type
& __k
,
865 typename
_Hashtable::_Hash_code_type __code
) const
867 for (; __p
; __p
= __p
->_M_next
)
868 if (this->_M_compare(__k
, __code
, __p
))
873 // Insert v in bucket n (assumes no element with its key already present).
874 template<typename _Key
, typename _Value
,
875 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
876 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
877 bool __chc
, bool __cit
, bool __uk
>
878 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
879 _H1
, _H2
, _Hash
, _RehashPolicy
,
880 __chc
, __cit
, __uk
>::iterator
881 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
882 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
883 _M_insert_bucket(const value_type
& __v
, size_type __n
,
884 typename
_Hashtable::_Hash_code_type __code
)
886 std::pair
<bool, std::size_t> __do_rehash
887 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
888 _M_element_count
, 1);
890 // Allocate the new node before doing the rehash so that we don't
891 // do a rehash if the allocation throws.
892 _Node
* __new_node
= _M_allocate_node(__v
);
896 if (__do_rehash
.first
)
898 const key_type
& __k
= this->_M_extract(__v
);
899 __n
= this->_M_bucket_index(__k
, __code
, __do_rehash
.second
);
900 _M_rehash(__do_rehash
.second
);
903 __new_node
->_M_next
= _M_buckets
[__n
];
904 this->_M_store_code(__new_node
, __code
);
905 _M_buckets
[__n
] = __new_node
;
907 return iterator(__new_node
, _M_buckets
+ __n
);
911 _M_deallocate_node(__new_node
);
912 __throw_exception_again
;
916 // Insert v if no element with its key is already present.
917 template<typename _Key
, typename _Value
,
918 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
919 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
920 bool __chc
, bool __cit
, bool __uk
>
921 std::pair
<typename _Hashtable
<_Key
, _Value
, _Allocator
,
922 _ExtractKey
, _Equal
, _H1
,
923 _H2
, _Hash
, _RehashPolicy
,
924 __chc
, __cit
, __uk
>::iterator
, bool>
925 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
926 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
927 _M_insert(const value_type
& __v
, std::true_type
)
929 const key_type
& __k
= this->_M_extract(__v
);
930 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
931 size_type __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
933 if (_Node
* __p
= _M_find_node(_M_buckets
[__n
], __k
, __code
))
934 return std::make_pair(iterator(__p
, _M_buckets
+ __n
), false);
935 return std::make_pair(_M_insert_bucket(__v
, __n
, __code
), true);
938 // Insert v unconditionally.
939 template<typename _Key
, typename _Value
,
940 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
941 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
942 bool __chc
, bool __cit
, bool __uk
>
943 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
944 _H1
, _H2
, _Hash
, _RehashPolicy
,
945 __chc
, __cit
, __uk
>::iterator
946 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
947 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
948 _M_insert(const value_type
& __v
, std::false_type
)
950 std::pair
<bool, std::size_t> __do_rehash
951 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
952 _M_element_count
, 1);
953 if (__do_rehash
.first
)
954 _M_rehash(__do_rehash
.second
);
956 const key_type
& __k
= this->_M_extract(__v
);
957 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
958 size_type __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
960 // First find the node, avoid leaking new_node if compare throws.
961 _Node
* __prev
= _M_find_node(_M_buckets
[__n
], __k
, __code
);
962 _Node
* __new_node
= _M_allocate_node(__v
);
966 __new_node
->_M_next
= __prev
->_M_next
;
967 __prev
->_M_next
= __new_node
;
971 __new_node
->_M_next
= _M_buckets
[__n
];
972 _M_buckets
[__n
] = __new_node
;
974 this->_M_store_code(__new_node
, __code
);
977 return iterator(__new_node
, _M_buckets
+ __n
);
980 // For erase(iterator) and erase(const_iterator).
981 template<typename _Key
, typename _Value
,
982 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
983 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
984 bool __chc
, bool __cit
, bool __uk
>
986 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
987 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
988 _M_erase_node(_Node
* __p
, _Node
** __b
)
992 *__b
= __cur
->_M_next
;
995 _Node
* __next
= __cur
->_M_next
;
996 while (__next
!= __p
)
999 __next
= __cur
->_M_next
;
1001 __cur
->_M_next
= __next
->_M_next
;
1004 _M_deallocate_node(__p
);
1008 template<typename _Key
, typename _Value
,
1009 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1010 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1011 bool __chc
, bool __cit
, bool __uk
>
1012 template<typename _InputIterator
>
1014 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1015 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1016 insert(_InputIterator __first
, _InputIterator __last
)
1018 size_type __n_elt
= __detail::__distance_fw(__first
, __last
);
1019 std::pair
<bool, std::size_t> __do_rehash
1020 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
1021 _M_element_count
, __n_elt
);
1022 if (__do_rehash
.first
)
1023 _M_rehash(__do_rehash
.second
);
1025 for (; __first
!= __last
; ++__first
)
1026 this->insert(*__first
);
1029 template<typename _Key
, typename _Value
,
1030 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1031 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1032 bool __chc
, bool __cit
, bool __uk
>
1033 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1034 _H1
, _H2
, _Hash
, _RehashPolicy
,
1035 __chc
, __cit
, __uk
>::iterator
1036 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1037 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1038 erase(const_iterator __it
)
1040 iterator
__result(__it
._M_cur_node
, __it
._M_cur_bucket
);
1042 _M_erase_node(__it
._M_cur_node
, __it
._M_cur_bucket
);
1046 template<typename _Key
, typename _Value
,
1047 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1048 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1049 bool __chc
, bool __cit
, bool __uk
>
1050 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1051 _H1
, _H2
, _Hash
, _RehashPolicy
,
1052 __chc
, __cit
, __uk
>::size_type
1053 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1054 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1055 erase(const key_type
& __k
)
1057 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
1058 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
1059 size_type __result
= 0;
1061 _Node
** __slot
= _M_buckets
+ __n
;
1062 while (*__slot
&& !this->_M_compare(__k
, __code
, *__slot
))
1063 __slot
= &((*__slot
)->_M_next
);
1065 _Node
** __saved_slot
= 0;
1066 while (*__slot
&& this->_M_compare(__k
, __code
, *__slot
))
1068 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1069 // 526. Is it undefined if a function in the standard changes
1071 if (&this->_M_extract((*__slot
)->_M_v
) != &__k
)
1073 _Node
* __p
= *__slot
;
1074 *__slot
= __p
->_M_next
;
1075 _M_deallocate_node(__p
);
1081 __saved_slot
= __slot
;
1082 __slot
= &((*__slot
)->_M_next
);
1088 _Node
* __p
= *__saved_slot
;
1089 *__saved_slot
= __p
->_M_next
;
1090 _M_deallocate_node(__p
);
1098 // ??? This could be optimized by taking advantage of the bucket
1099 // structure, but it's not clear that it's worth doing. It probably
1100 // wouldn't even be an optimization unless the load factor is large.
1101 template<typename _Key
, typename _Value
,
1102 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1103 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1104 bool __chc
, bool __cit
, bool __uk
>
1105 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1106 _H1
, _H2
, _Hash
, _RehashPolicy
,
1107 __chc
, __cit
, __uk
>::iterator
1108 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1109 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1110 erase(const_iterator __first
, const_iterator __last
)
1112 while (__first
!= __last
)
1113 __first
= this->erase(__first
);
1114 return iterator(__last
._M_cur_node
, __last
._M_cur_bucket
);
1117 template<typename _Key
, typename _Value
,
1118 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1119 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1120 bool __chc
, bool __cit
, bool __uk
>
1122 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1123 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1126 _M_deallocate_nodes(_M_buckets
, _M_bucket_count
);
1127 _M_element_count
= 0;
1130 template<typename _Key
, typename _Value
,
1131 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1132 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1133 bool __chc
, bool __cit
, bool __uk
>
1135 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1136 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1137 rehash(size_type __n
)
1139 _M_rehash(std::max(_M_rehash_policy
._M_next_bkt(__n
),
1140 _M_rehash_policy
._M_bkt_for_elements(_M_element_count
1144 template<typename _Key
, typename _Value
,
1145 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1146 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1147 bool __chc
, bool __cit
, bool __uk
>
1149 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1150 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1151 _M_rehash(size_type __n
)
1153 _Node
** __new_array
= _M_allocate_buckets(__n
);
1156 for (size_type __i
= 0; __i
< _M_bucket_count
; ++__i
)
1157 while (_Node
* __p
= _M_buckets
[__i
])
1159 std::size_t __new_index
= this->_M_bucket_index(__p
, __n
);
1160 _M_buckets
[__i
] = __p
->_M_next
;
1161 __p
->_M_next
= __new_array
[__new_index
];
1162 __new_array
[__new_index
] = __p
;
1164 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
1165 _M_bucket_count
= __n
;
1166 _M_buckets
= __new_array
;
1170 // A failure here means that a hash function threw an exception.
1171 // We can't restore the previous state without calling the hash
1172 // function again, so the only sensible recovery is to delete
1174 _M_deallocate_nodes(__new_array
, __n
);
1175 _M_deallocate_buckets(__new_array
, __n
);
1176 _M_deallocate_nodes(_M_buckets
, _M_bucket_count
);
1177 _M_element_count
= 0;
1178 __throw_exception_again
;
1183 #endif // _HASHTABLE_H