1 // TR1 hashtable.h header -*- C++ -*-
3 // Copyright (C) 2007-2014 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 tr1/hashtable.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly.
28 * @headername{tr1/unordered_set, tr1/unordered_map}
31 #ifndef _GLIBCXX_TR1_HASHTABLE_H
32 #define _GLIBCXX_TR1_HASHTABLE_H 1
34 #pragma GCC system_header
36 #include <tr1/hashtable_policy.h>
38 namespace std
_GLIBCXX_VISIBILITY(default)
42 _GLIBCXX_BEGIN_NAMESPACE_VERSION
44 // Class template _Hashtable, class definition.
46 // Meaning of class template _Hashtable's template parameters
48 // _Key and _Value: arbitrary CopyConstructible types.
50 // _Allocator: an allocator type ([lib.allocator.requirements]) whose
51 // value type is Value. As a conforming extension, we allow for
52 // value type != Value.
54 // _ExtractKey: function object that takes a object of type Value
55 // and returns a value of type _Key.
57 // _Equal: function object that takes two objects of type k and returns
58 // a bool-like value that is true if the two objects are considered equal.
60 // _H1: the hash function. A unary function object with argument type
61 // Key and result type size_t. Return values should be distributed
62 // over the entire range [0, numeric_limits<size_t>:::max()].
64 // _H2: the range-hashing function (in the terminology of Tavori and
65 // Dreizin). A binary function object whose argument types and result
66 // type are all size_t. Given arguments r and N, the return value is
67 // in the range [0, N).
69 // _Hash: the ranged hash function (Tavori and Dreizin). A binary function
70 // whose argument types are _Key and size_t and whose result type is
71 // size_t. Given arguments k and N, the return value is in the range
72 // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other
73 // than the default, _H1 and _H2 are ignored.
75 // _RehashPolicy: Policy class with three members, all of which govern
76 // the bucket count. _M_next_bkt(n) returns a bucket count no smaller
77 // than n. _M_bkt_for_elements(n) returns a bucket count appropriate
78 // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins)
79 // determines whether, if the current bucket count is n_bkt and the
80 // current element count is n_elt, we need to increase the bucket
81 // count. If so, returns make_pair(true, n), where n is the new
82 // bucket count. If not, returns make_pair(false, <anything>).
84 // ??? Right now it is hard-wired that the number of buckets never
85 // shrinks. Should we allow _RehashPolicy to change that?
87 // __cache_hash_code: bool. true if we store the value of the hash
88 // function along with the value. This is a time-space tradeoff.
89 // Storing it may improve lookup speed by reducing the number of times
90 // we need to call the Equal function.
92 // __constant_iterators: bool. true if iterator and const_iterator are
93 // both constant iterator types. This is true for unordered_set and
94 // unordered_multiset, false for unordered_map and unordered_multimap.
96 // __unique_keys: bool. true if the return value of _Hashtable::count(k)
97 // is always at most one, false if it may be an arbitrary number. This
98 // true for unordered_set and unordered_map, false for unordered_multiset
99 // and unordered_multimap.
101 template<typename _Key
, typename _Value
, typename _Allocator
,
102 typename _ExtractKey
, typename _Equal
,
103 typename _H1
, typename _H2
, typename _Hash
,
104 typename _RehashPolicy
,
105 bool __cache_hash_code
,
106 bool __constant_iterators
,
109 : public __detail::_Rehash_base
<_RehashPolicy
,
110 _Hashtable
<_Key
, _Value
, _Allocator
,
112 _Equal
, _H1
, _H2
, _Hash
,
115 __constant_iterators
,
117 public __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
118 _H1
, _H2
, _Hash
, __cache_hash_code
>,
119 public __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __unique_keys
,
120 _Hashtable
<_Key
, _Value
, _Allocator
,
122 _Equal
, _H1
, _H2
, _Hash
,
125 __constant_iterators
,
129 typedef _Allocator allocator_type
;
130 typedef _Value value_type
;
131 typedef _Key key_type
;
132 typedef _Equal key_equal
;
133 // mapped_type, if present, comes from _Map_base.
134 // hasher, if present, comes from _Hash_code_base.
135 typedef typename
_Allocator::difference_type difference_type
;
136 typedef typename
_Allocator::size_type size_type
;
137 typedef typename
_Allocator::pointer pointer
;
138 typedef typename
_Allocator::const_pointer const_pointer
;
139 typedef typename
_Allocator::reference reference
;
140 typedef typename
_Allocator::const_reference const_reference
;
142 typedef __detail::_Node_iterator
<value_type
, __constant_iterators
,
145 typedef __detail::_Node_const_iterator
<value_type
,
146 __constant_iterators
,
148 const_local_iterator
;
150 typedef __detail::_Hashtable_iterator
<value_type
, __constant_iterators
,
153 typedef __detail::_Hashtable_const_iterator
<value_type
,
154 __constant_iterators
,
158 template<typename _Key2
, typename _Value2
, typename _Ex2
, bool __unique2
,
159 typename _Hashtable2
>
160 friend struct __detail::_Map_base
;
163 typedef __detail::_Hash_node
<_Value
, __cache_hash_code
> _Node
;
164 typedef typename
_Allocator::template rebind
<_Node
>::other
165 _Node_allocator_type
;
166 typedef typename
_Allocator::template rebind
<_Node
*>::other
167 _Bucket_allocator_type
;
169 typedef typename
_Allocator::template rebind
<_Value
>::other
170 _Value_allocator_type
;
172 _Node_allocator_type _M_node_allocator
;
174 size_type _M_bucket_count
;
175 size_type _M_element_count
;
176 _RehashPolicy _M_rehash_policy
;
179 _M_allocate_node(const value_type
& __v
);
182 _M_deallocate_node(_Node
* __n
);
185 _M_deallocate_nodes(_Node
**, size_type
);
188 _M_allocate_buckets(size_type __n
);
191 _M_deallocate_buckets(_Node
**, size_type __n
);
194 // Constructor, destructor, assignment, swap
195 _Hashtable(size_type __bucket_hint
,
196 const _H1
&, const _H2
&, const _Hash
&,
197 const _Equal
&, const _ExtractKey
&,
198 const allocator_type
&);
200 template<typename _InputIterator
>
201 _Hashtable(_InputIterator __first
, _InputIterator __last
,
202 size_type __bucket_hint
,
203 const _H1
&, const _H2
&, const _Hash
&,
204 const _Equal
&, const _ExtractKey
&,
205 const allocator_type
&);
207 _Hashtable(const _Hashtable
&);
210 operator=(const _Hashtable
&);
214 void swap(_Hashtable
&);
216 // Basic container operations
220 iterator
__i(_M_buckets
);
221 if (!__i
._M_cur_node
)
222 __i
._M_incr_bucket();
229 const_iterator
__i(_M_buckets
);
230 if (!__i
._M_cur_node
)
231 __i
._M_incr_bucket();
237 { return iterator(_M_buckets
+ _M_bucket_count
); }
241 { return const_iterator(_M_buckets
+ _M_bucket_count
); }
245 { return _M_element_count
; }
249 { return size() == 0; }
252 get_allocator() const
253 { return allocator_type(_M_node_allocator
); }
255 _Value_allocator_type
256 _M_get_Value_allocator() const
257 { return _Value_allocator_type(_M_node_allocator
); }
261 { return _M_node_allocator
.max_size(); }
266 { return this->_M_eq
; }
268 // hash_function, if present, comes from _Hash_code_base.
273 { return _M_bucket_count
; }
276 max_bucket_count() const
277 { return max_size(); }
280 bucket_size(size_type __n
) const
281 { return std::distance(begin(__n
), end(__n
)); }
284 bucket(const key_type
& __k
) const
286 return this->_M_bucket_index(__k
, this->_M_hash_code(__k
),
292 { return local_iterator(_M_buckets
[__n
]); }
296 { return local_iterator(0); }
299 begin(size_type __n
) const
300 { return const_local_iterator(_M_buckets
[__n
]); }
304 { return const_local_iterator(0); }
309 return static_cast<float>(size()) / static_cast<float>(bucket_count());
312 // max_load_factor, if present, comes from _Rehash_base.
314 // Generalization of max_load_factor. Extension, not found in TR1. Only
315 // useful if _RehashPolicy is something other than the default.
317 __rehash_policy() const
318 { return _M_rehash_policy
; }
321 __rehash_policy(const _RehashPolicy
&);
325 find(const key_type
& __k
);
328 find(const key_type
& __k
) const;
331 count(const key_type
& __k
) const;
333 std::pair
<iterator
, iterator
>
334 equal_range(const key_type
& __k
);
336 std::pair
<const_iterator
, const_iterator
>
337 equal_range(const key_type
& __k
) const;
339 private: // Find, insert and erase helper functions
340 // ??? This dispatching is a workaround for the fact that we don't
341 // have partial specialization of member templates; it would be
342 // better to just specialize insert on __unique_keys. There may be a
343 // cleaner workaround.
344 typedef typename
__gnu_cxx::__conditional_type
<__unique_keys
,
345 std::pair
<iterator
, bool>, iterator
>::__type
348 typedef typename
__gnu_cxx::__conditional_type
<__unique_keys
,
349 std::_Select1st
<_Insert_Return_Type
>,
350 std::_Identity
<_Insert_Return_Type
>
355 _M_find_node(_Node
*, const key_type
&,
356 typename
_Hashtable::_Hash_code_type
) const;
359 _M_insert_bucket(const value_type
&, size_type
,
360 typename
_Hashtable::_Hash_code_type
);
362 std::pair
<iterator
, bool>
363 _M_insert(const value_type
&, std::tr1::true_type
);
366 _M_insert(const value_type
&, std::tr1::false_type
);
369 _M_erase_node(_Node
*, _Node
**);
374 insert(const value_type
& __v
)
375 { return _M_insert(__v
, std::tr1::integral_constant
<bool,
379 insert(iterator
, const value_type
& __v
)
380 { return iterator(_Insert_Conv_Type()(this->insert(__v
))); }
383 insert(const_iterator
, const value_type
& __v
)
384 { return const_iterator(_Insert_Conv_Type()(this->insert(__v
))); }
386 template<typename _InputIterator
>
388 insert(_InputIterator __first
, _InputIterator __last
);
394 erase(const_iterator
);
397 erase(const key_type
&);
400 erase(iterator
, iterator
);
403 erase(const_iterator
, const_iterator
);
408 // Set number of buckets to be appropriate for container of n element.
409 void rehash(size_type __n
);
412 // Unconditionally change size of bucket array to n.
413 void _M_rehash(size_type __n
);
417 // Definitions of class template _Hashtable's out-of-line member functions.
418 template<typename _Key
, typename _Value
,
419 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
420 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
421 bool __chc
, bool __cit
, bool __uk
>
422 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
423 _H1
, _H2
, _Hash
, _RehashPolicy
,
424 __chc
, __cit
, __uk
>::_Node
*
425 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
426 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
427 _M_allocate_node(const value_type
& __v
)
429 _Node
* __n
= _M_node_allocator
.allocate(1);
432 _M_get_Value_allocator().construct(&__n
->_M_v
, __v
);
438 _M_node_allocator
.deallocate(__n
, 1);
439 __throw_exception_again
;
443 template<typename _Key
, typename _Value
,
444 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
445 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
446 bool __chc
, bool __cit
, bool __uk
>
448 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
449 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
450 _M_deallocate_node(_Node
* __n
)
452 _M_get_Value_allocator().destroy(&__n
->_M_v
);
453 _M_node_allocator
.deallocate(__n
, 1);
456 template<typename _Key
, typename _Value
,
457 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
458 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
459 bool __chc
, bool __cit
, bool __uk
>
461 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
462 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
463 _M_deallocate_nodes(_Node
** __array
, size_type __n
)
465 for (size_type __i
= 0; __i
< __n
; ++__i
)
467 _Node
* __p
= __array
[__i
];
472 _M_deallocate_node(__tmp
);
478 template<typename _Key
, typename _Value
,
479 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
480 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
481 bool __chc
, bool __cit
, bool __uk
>
482 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
483 _H1
, _H2
, _Hash
, _RehashPolicy
,
484 __chc
, __cit
, __uk
>::_Node
**
485 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
486 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
487 _M_allocate_buckets(size_type __n
)
489 _Bucket_allocator_type
__alloc(_M_node_allocator
);
491 // We allocate one extra bucket to hold a sentinel, an arbitrary
492 // non-null pointer. Iterator increment relies on this.
493 _Node
** __p
= __alloc
.allocate(__n
+ 1);
494 std::fill(__p
, __p
+ __n
, (_Node
*) 0);
495 __p
[__n
] = reinterpret_cast<_Node
*>(0x1000);
499 template<typename _Key
, typename _Value
,
500 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
501 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
502 bool __chc
, bool __cit
, bool __uk
>
504 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
505 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
506 _M_deallocate_buckets(_Node
** __p
, size_type __n
)
508 _Bucket_allocator_type
__alloc(_M_node_allocator
);
509 __alloc
.deallocate(__p
, __n
+ 1);
512 template<typename _Key
, typename _Value
,
513 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
514 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
515 bool __chc
, bool __cit
, bool __uk
>
516 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
517 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
518 _Hashtable(size_type __bucket_hint
,
519 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
520 const _Equal
& __eq
, const _ExtractKey
& __exk
,
521 const allocator_type
& __a
)
522 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(),
523 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
524 _H1
, _H2
, _Hash
, __chc
>(__exk
, __eq
,
526 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(),
527 _M_node_allocator(__a
),
532 _M_bucket_count
= _M_rehash_policy
._M_next_bkt(__bucket_hint
);
533 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
536 template<typename _Key
, typename _Value
,
537 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
538 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
539 bool __chc
, bool __cit
, bool __uk
>
540 template<typename _InputIterator
>
541 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
542 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
543 _Hashtable(_InputIterator __f
, _InputIterator __l
,
544 size_type __bucket_hint
,
545 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
546 const _Equal
& __eq
, const _ExtractKey
& __exk
,
547 const allocator_type
& __a
)
548 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(),
549 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
550 _H1
, _H2
, _Hash
, __chc
>(__exk
, __eq
,
552 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(),
553 _M_node_allocator(__a
),
558 _M_bucket_count
= std::max(_M_rehash_policy
._M_next_bkt(__bucket_hint
),
560 _M_bkt_for_elements(__detail::
563 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
566 for (; __f
!= __l
; ++__f
)
572 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
573 __throw_exception_again
;
577 template<typename _Key
, typename _Value
,
578 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
579 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
580 bool __chc
, bool __cit
, bool __uk
>
581 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
582 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
583 _Hashtable(const _Hashtable
& __ht
)
584 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(__ht
),
585 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
586 _H1
, _H2
, _Hash
, __chc
>(__ht
),
587 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(__ht
),
588 _M_node_allocator(__ht
._M_node_allocator
),
589 _M_bucket_count(__ht
._M_bucket_count
),
590 _M_element_count(__ht
._M_element_count
),
591 _M_rehash_policy(__ht
._M_rehash_policy
)
593 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
596 for (size_type __i
= 0; __i
< __ht
._M_bucket_count
; ++__i
)
598 _Node
* __n
= __ht
._M_buckets
[__i
];
599 _Node
** __tail
= _M_buckets
+ __i
;
602 *__tail
= _M_allocate_node(__n
->_M_v
);
603 this->_M_copy_code(*__tail
, __n
);
604 __tail
= &((*__tail
)->_M_next
);
612 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
613 __throw_exception_again
;
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
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
624 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
625 operator=(const _Hashtable
& __ht
)
627 _Hashtable
__tmp(__ht
);
632 template<typename _Key
, typename _Value
,
633 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
634 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
635 bool __chc
, bool __cit
, bool __uk
>
636 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
637 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
641 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
644 template<typename _Key
, typename _Value
,
645 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
646 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
647 bool __chc
, bool __cit
, bool __uk
>
649 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
650 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
651 swap(_Hashtable
& __x
)
653 // The only base class with member variables is hash_code_base. We
654 // define _Hash_code_base::_M_swap because different specializations
655 // have different members.
656 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
657 _H1
, _H2
, _Hash
, __chc
>::_M_swap(__x
);
659 // _GLIBCXX_RESOLVE_LIB_DEFECTS
660 // 431. Swapping containers with unequal allocators.
661 std::__alloc_swap
<_Node_allocator_type
>::_S_do_it(_M_node_allocator
,
662 __x
._M_node_allocator
);
664 std::swap(_M_rehash_policy
, __x
._M_rehash_policy
);
665 std::swap(_M_buckets
, __x
._M_buckets
);
666 std::swap(_M_bucket_count
, __x
._M_bucket_count
);
667 std::swap(_M_element_count
, __x
._M_element_count
);
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
>
675 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
676 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
677 __rehash_policy(const _RehashPolicy
& __pol
)
679 _M_rehash_policy
= __pol
;
680 size_type __n_bkt
= __pol
._M_bkt_for_elements(_M_element_count
);
681 if (__n_bkt
> _M_bucket_count
)
685 template<typename _Key
, typename _Value
,
686 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
687 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
688 bool __chc
, bool __cit
, bool __uk
>
689 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
690 _H1
, _H2
, _Hash
, _RehashPolicy
,
691 __chc
, __cit
, __uk
>::iterator
692 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
693 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
694 find(const key_type
& __k
)
696 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
697 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
698 _Node
* __p
= _M_find_node(_M_buckets
[__n
], __k
, __code
);
699 return __p
? iterator(__p
, _M_buckets
+ __n
) : this->end();
702 template<typename _Key
, typename _Value
,
703 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
704 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
705 bool __chc
, bool __cit
, bool __uk
>
706 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
707 _H1
, _H2
, _Hash
, _RehashPolicy
,
708 __chc
, __cit
, __uk
>::const_iterator
709 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
710 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
711 find(const key_type
& __k
) const
713 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
714 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
715 _Node
* __p
= _M_find_node(_M_buckets
[__n
], __k
, __code
);
716 return __p
? const_iterator(__p
, _M_buckets
+ __n
) : this->end();
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 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
724 _H1
, _H2
, _Hash
, _RehashPolicy
,
725 __chc
, __cit
, __uk
>::size_type
726 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
727 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
728 count(const key_type
& __k
) const
730 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
731 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
732 std::size_t __result
= 0;
733 for (_Node
* __p
= _M_buckets
[__n
]; __p
; __p
= __p
->_M_next
)
734 if (this->_M_compare(__k
, __code
, __p
))
739 template<typename _Key
, typename _Value
,
740 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
741 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
742 bool __chc
, bool __cit
, bool __uk
>
743 std::pair
<typename _Hashtable
<_Key
, _Value
, _Allocator
,
744 _ExtractKey
, _Equal
, _H1
,
745 _H2
, _Hash
, _RehashPolicy
,
746 __chc
, __cit
, __uk
>::iterator
,
747 typename _Hashtable
<_Key
, _Value
, _Allocator
,
748 _ExtractKey
, _Equal
, _H1
,
749 _H2
, _Hash
, _RehashPolicy
,
750 __chc
, __cit
, __uk
>::iterator
>
751 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
752 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
753 equal_range(const key_type
& __k
)
755 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
756 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
757 _Node
** __head
= _M_buckets
+ __n
;
758 _Node
* __p
= _M_find_node(*__head
, __k
, __code
);
762 _Node
* __p1
= __p
->_M_next
;
763 for (; __p1
; __p1
= __p1
->_M_next
)
764 if (!this->_M_compare(__k
, __code
, __p1
))
767 iterator
__first(__p
, __head
);
768 iterator
__last(__p1
, __head
);
770 __last
._M_incr_bucket();
771 return std::make_pair(__first
, __last
);
774 return std::make_pair(this->end(), this->end());
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
>::const_iterator
,
785 typename _Hashtable
<_Key
, _Value
, _Allocator
,
786 _ExtractKey
, _Equal
, _H1
,
787 _H2
, _Hash
, _RehashPolicy
,
788 __chc
, __cit
, __uk
>::const_iterator
>
789 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
790 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
791 equal_range(const key_type
& __k
) const
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 const_iterator
__first(__p
, __head
);
806 const_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 // Find the node whose key compares equal to k, beginning the search
816 // at p (usually the head of a bucket). Return zero if no node is found.
817 template<typename _Key
, typename _Value
,
818 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
819 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
820 bool __chc
, bool __cit
, bool __uk
>
821 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
,
822 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
823 __chc
, __cit
, __uk
>::_Node
*
824 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
825 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
826 _M_find_node(_Node
* __p
, const key_type
& __k
,
827 typename
_Hashtable::_Hash_code_type __code
) const
829 for (; __p
; __p
= __p
->_M_next
)
830 if (this->_M_compare(__k
, __code
, __p
))
835 // Insert v in bucket n (assumes no element with its key already present).
836 template<typename _Key
, typename _Value
,
837 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
838 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
839 bool __chc
, bool __cit
, bool __uk
>
840 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
841 _H1
, _H2
, _Hash
, _RehashPolicy
,
842 __chc
, __cit
, __uk
>::iterator
843 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
844 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
845 _M_insert_bucket(const value_type
& __v
, size_type __n
,
846 typename
_Hashtable::_Hash_code_type __code
)
848 std::pair
<bool, std::size_t> __do_rehash
849 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
850 _M_element_count
, 1);
852 // Allocate the new node before doing the rehash so that we don't
853 // do a rehash if the allocation throws.
854 _Node
* __new_node
= _M_allocate_node(__v
);
858 if (__do_rehash
.first
)
860 const key_type
& __k
= this->_M_extract(__v
);
861 __n
= this->_M_bucket_index(__k
, __code
, __do_rehash
.second
);
862 _M_rehash(__do_rehash
.second
);
865 __new_node
->_M_next
= _M_buckets
[__n
];
866 this->_M_store_code(__new_node
, __code
);
867 _M_buckets
[__n
] = __new_node
;
869 return iterator(__new_node
, _M_buckets
+ __n
);
873 _M_deallocate_node(__new_node
);
874 __throw_exception_again
;
878 // Insert v if no element with its key is already present.
879 template<typename _Key
, typename _Value
,
880 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
881 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
882 bool __chc
, bool __cit
, bool __uk
>
883 std::pair
<typename _Hashtable
<_Key
, _Value
, _Allocator
,
884 _ExtractKey
, _Equal
, _H1
,
885 _H2
, _Hash
, _RehashPolicy
,
886 __chc
, __cit
, __uk
>::iterator
, bool>
887 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
888 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
889 _M_insert(const value_type
& __v
, std::tr1::true_type
)
891 const key_type
& __k
= this->_M_extract(__v
);
892 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
893 size_type __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
895 if (_Node
* __p
= _M_find_node(_M_buckets
[__n
], __k
, __code
))
896 return std::make_pair(iterator(__p
, _M_buckets
+ __n
), false);
897 return std::make_pair(_M_insert_bucket(__v
, __n
, __code
), true);
900 // Insert v unconditionally.
901 template<typename _Key
, typename _Value
,
902 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
903 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
904 bool __chc
, bool __cit
, bool __uk
>
905 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
906 _H1
, _H2
, _Hash
, _RehashPolicy
,
907 __chc
, __cit
, __uk
>::iterator
908 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
909 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
910 _M_insert(const value_type
& __v
, std::tr1::false_type
)
912 std::pair
<bool, std::size_t> __do_rehash
913 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
914 _M_element_count
, 1);
915 if (__do_rehash
.first
)
916 _M_rehash(__do_rehash
.second
);
918 const key_type
& __k
= this->_M_extract(__v
);
919 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
920 size_type __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
922 // First find the node, avoid leaking new_node if compare throws.
923 _Node
* __prev
= _M_find_node(_M_buckets
[__n
], __k
, __code
);
924 _Node
* __new_node
= _M_allocate_node(__v
);
928 __new_node
->_M_next
= __prev
->_M_next
;
929 __prev
->_M_next
= __new_node
;
933 __new_node
->_M_next
= _M_buckets
[__n
];
934 _M_buckets
[__n
] = __new_node
;
936 this->_M_store_code(__new_node
, __code
);
939 return iterator(__new_node
, _M_buckets
+ __n
);
942 // For erase(iterator) and erase(const_iterator).
943 template<typename _Key
, typename _Value
,
944 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
945 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
946 bool __chc
, bool __cit
, bool __uk
>
948 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
949 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
950 _M_erase_node(_Node
* __p
, _Node
** __b
)
954 *__b
= __cur
->_M_next
;
957 _Node
* __next
= __cur
->_M_next
;
958 while (__next
!= __p
)
961 __next
= __cur
->_M_next
;
963 __cur
->_M_next
= __next
->_M_next
;
966 _M_deallocate_node(__p
);
970 template<typename _Key
, typename _Value
,
971 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
972 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
973 bool __chc
, bool __cit
, bool __uk
>
974 template<typename _InputIterator
>
976 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
977 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
978 insert(_InputIterator __first
, _InputIterator __last
)
980 size_type __n_elt
= __detail::__distance_fw(__first
, __last
);
981 std::pair
<bool, std::size_t> __do_rehash
982 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
983 _M_element_count
, __n_elt
);
984 if (__do_rehash
.first
)
985 _M_rehash(__do_rehash
.second
);
987 for (; __first
!= __last
; ++__first
)
988 this->insert(*__first
);
991 template<typename _Key
, typename _Value
,
992 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
993 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
994 bool __chc
, bool __cit
, bool __uk
>
995 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
996 _H1
, _H2
, _Hash
, _RehashPolicy
,
997 __chc
, __cit
, __uk
>::iterator
998 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
999 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1000 erase(iterator __it
)
1002 iterator __result
= __it
;
1004 _M_erase_node(__it
._M_cur_node
, __it
._M_cur_bucket
);
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 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1013 _H1
, _H2
, _Hash
, _RehashPolicy
,
1014 __chc
, __cit
, __uk
>::const_iterator
1015 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1016 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1017 erase(const_iterator __it
)
1019 const_iterator __result
= __it
;
1021 _M_erase_node(__it
._M_cur_node
, __it
._M_cur_bucket
);
1025 template<typename _Key
, typename _Value
,
1026 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1027 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1028 bool __chc
, bool __cit
, bool __uk
>
1029 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1030 _H1
, _H2
, _Hash
, _RehashPolicy
,
1031 __chc
, __cit
, __uk
>::size_type
1032 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1033 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1034 erase(const key_type
& __k
)
1036 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
1037 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
1038 size_type __result
= 0;
1040 _Node
** __slot
= _M_buckets
+ __n
;
1041 while (*__slot
&& !this->_M_compare(__k
, __code
, *__slot
))
1042 __slot
= &((*__slot
)->_M_next
);
1044 _Node
** __saved_slot
= 0;
1045 while (*__slot
&& this->_M_compare(__k
, __code
, *__slot
))
1047 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1048 // 526. Is it undefined if a function in the standard changes
1050 if (&this->_M_extract((*__slot
)->_M_v
) != &__k
)
1052 _Node
* __p
= *__slot
;
1053 *__slot
= __p
->_M_next
;
1054 _M_deallocate_node(__p
);
1060 __saved_slot
= __slot
;
1061 __slot
= &((*__slot
)->_M_next
);
1067 _Node
* __p
= *__saved_slot
;
1068 *__saved_slot
= __p
->_M_next
;
1069 _M_deallocate_node(__p
);
1077 // ??? This could be optimized by taking advantage of the bucket
1078 // structure, but it's not clear that it's worth doing. It probably
1079 // wouldn't even be an optimization unless the load factor is large.
1080 template<typename _Key
, typename _Value
,
1081 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1082 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1083 bool __chc
, bool __cit
, bool __uk
>
1084 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1085 _H1
, _H2
, _Hash
, _RehashPolicy
,
1086 __chc
, __cit
, __uk
>::iterator
1087 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1088 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1089 erase(iterator __first
, iterator __last
)
1091 while (__first
!= __last
)
1092 __first
= this->erase(__first
);
1096 template<typename _Key
, typename _Value
,
1097 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1098 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1099 bool __chc
, bool __cit
, bool __uk
>
1100 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1101 _H1
, _H2
, _Hash
, _RehashPolicy
,
1102 __chc
, __cit
, __uk
>::const_iterator
1103 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1104 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1105 erase(const_iterator __first
, const_iterator __last
)
1107 while (__first
!= __last
)
1108 __first
= this->erase(__first
);
1112 template<typename _Key
, typename _Value
,
1113 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1114 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1115 bool __chc
, bool __cit
, bool __uk
>
1117 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1118 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1121 _M_deallocate_nodes(_M_buckets
, _M_bucket_count
);
1122 _M_element_count
= 0;
1125 template<typename _Key
, typename _Value
,
1126 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1127 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1128 bool __chc
, bool __cit
, bool __uk
>
1130 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1131 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1132 rehash(size_type __n
)
1134 _M_rehash(std::max(_M_rehash_policy
._M_next_bkt(__n
),
1135 _M_rehash_policy
._M_bkt_for_elements(_M_element_count
1139 template<typename _Key
, typename _Value
,
1140 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1141 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1142 bool __chc
, bool __cit
, bool __uk
>
1144 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1145 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1146 _M_rehash(size_type __n
)
1148 _Node
** __new_array
= _M_allocate_buckets(__n
);
1151 for (size_type __i
= 0; __i
< _M_bucket_count
; ++__i
)
1152 while (_Node
* __p
= _M_buckets
[__i
])
1154 std::size_t __new_index
= this->_M_bucket_index(__p
, __n
);
1155 _M_buckets
[__i
] = __p
->_M_next
;
1156 __p
->_M_next
= __new_array
[__new_index
];
1157 __new_array
[__new_index
] = __p
;
1159 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
1160 _M_bucket_count
= __n
;
1161 _M_buckets
= __new_array
;
1165 // A failure here means that a hash function threw an exception.
1166 // We can't restore the previous state without calling the hash
1167 // function again, so the only sensible recovery is to delete
1169 _M_deallocate_nodes(__new_array
, __n
);
1170 _M_deallocate_buckets(__new_array
, __n
);
1171 _M_deallocate_nodes(_M_buckets
, _M_bucket_count
);
1172 _M_element_count
= 0;
1173 __throw_exception_again
;
1177 _GLIBCXX_END_NAMESPACE_VERSION
1181 #endif // _GLIBCXX_TR1_HASHTABLE_H