1 // TR1 hashtable.h header -*- C++ -*-
3 // Copyright (C) 2007, 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 tr1/hashtable.h
26 * This is an internal header file, included by other library headers.
27 * You should not attempt to use it directly.
30 #ifndef _GLIBCXX_TR1_HASHTABLE_H
31 #define _GLIBCXX_TR1_HASHTABLE_H 1
33 #pragma GCC system_header
35 #include <tr1/hashtable_policy.h>
41 // Class template _Hashtable, class definition.
43 // Meaning of class template _Hashtable's template parameters
45 // _Key and _Value: arbitrary CopyConstructible types.
47 // _Allocator: an allocator type ([lib.allocator.requirements]) whose
48 // value type is Value. As a conforming extension, we allow for
49 // value type != Value.
51 // _ExtractKey: function object that takes a object of type Value
52 // and returns a value of type _Key.
54 // _Equal: function object that takes two objects of type k and returns
55 // a bool-like value that is true if the two objects are considered equal.
57 // _H1: the hash function. A unary function object with argument type
58 // Key and result type size_t. Return values should be distributed
59 // over the entire range [0, numeric_limits<size_t>:::max()].
61 // _H2: the range-hashing function (in the terminology of Tavori and
62 // Dreizin). A binary function object whose argument types and result
63 // type are all size_t. Given arguments r and N, the return value is
64 // in the range [0, N).
66 // _Hash: the ranged hash function (Tavori and Dreizin). A binary function
67 // whose argument types are _Key and size_t and whose result type is
68 // size_t. Given arguments k and N, the return value is in the range
69 // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other
70 // than the default, _H1 and _H2 are ignored.
72 // _RehashPolicy: Policy class with three members, all of which govern
73 // the bucket count. _M_next_bkt(n) returns a bucket count no smaller
74 // than n. _M_bkt_for_elements(n) returns a bucket count appropriate
75 // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins)
76 // determines whether, if the current bucket count is n_bkt and the
77 // current element count is n_elt, we need to increase the bucket
78 // count. If so, returns make_pair(true, n), where n is the new
79 // bucket count. If not, returns make_pair(false, <anything>).
81 // ??? Right now it is hard-wired that the number of buckets never
82 // shrinks. Should we allow _RehashPolicy to change that?
84 // __cache_hash_code: bool. true if we store the value of the hash
85 // function along with the value. This is a time-space tradeoff.
86 // Storing it may improve lookup speed by reducing the number of times
87 // we need to call the Equal function.
89 // __constant_iterators: bool. true if iterator and const_iterator are
90 // both constant iterator types. This is true for unordered_set and
91 // unordered_multiset, false for unordered_map and unordered_multimap.
93 // __unique_keys: bool. true if the return value of _Hashtable::count(k)
94 // is always at most one, false if it may be an arbitrary number. This
95 // true for unordered_set and unordered_map, false for unordered_multiset
96 // and unordered_multimap.
98 template<typename _Key
, typename _Value
, typename _Allocator
,
99 typename _ExtractKey
, typename _Equal
,
100 typename _H1
, typename _H2
, typename _Hash
,
101 typename _RehashPolicy
,
102 bool __cache_hash_code
,
103 bool __constant_iterators
,
106 : public __detail::_Rehash_base
<_RehashPolicy
,
107 _Hashtable
<_Key
, _Value
, _Allocator
,
109 _Equal
, _H1
, _H2
, _Hash
,
112 __constant_iterators
,
114 public __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
115 _H1
, _H2
, _Hash
, __cache_hash_code
>,
116 public __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __unique_keys
,
117 _Hashtable
<_Key
, _Value
, _Allocator
,
119 _Equal
, _H1
, _H2
, _Hash
,
122 __constant_iterators
,
126 typedef _Allocator allocator_type
;
127 typedef _Value value_type
;
128 typedef _Key key_type
;
129 typedef _Equal key_equal
;
130 // mapped_type, if present, comes from _Map_base.
131 // hasher, if present, comes from _Hash_code_base.
132 typedef typename
_Allocator::difference_type difference_type
;
133 typedef typename
_Allocator::size_type size_type
;
134 typedef typename
_Allocator::pointer pointer
;
135 typedef typename
_Allocator::const_pointer const_pointer
;
136 typedef typename
_Allocator::reference reference
;
137 typedef typename
_Allocator::const_reference const_reference
;
139 typedef __detail::_Node_iterator
<value_type
, __constant_iterators
,
142 typedef __detail::_Node_const_iterator
<value_type
,
143 __constant_iterators
,
145 const_local_iterator
;
147 typedef __detail::_Hashtable_iterator
<value_type
, __constant_iterators
,
150 typedef __detail::_Hashtable_const_iterator
<value_type
,
151 __constant_iterators
,
155 template<typename _Key2
, typename _Value2
, typename _Ex2
, bool __unique2
,
156 typename _Hashtable2
>
157 friend struct __detail::_Map_base
;
160 typedef __detail::_Hash_node
<_Value
, __cache_hash_code
> _Node
;
161 typedef typename
_Allocator::template rebind
<_Node
>::other
162 _Node_allocator_type
;
163 typedef typename
_Allocator::template rebind
<_Node
*>::other
164 _Bucket_allocator_type
;
166 typedef typename
_Allocator::template rebind
<_Value
>::other
167 _Value_allocator_type
;
169 _Node_allocator_type _M_node_allocator
;
171 size_type _M_bucket_count
;
172 size_type _M_element_count
;
173 _RehashPolicy _M_rehash_policy
;
176 _M_allocate_node(const value_type
& __v
);
179 _M_deallocate_node(_Node
* __n
);
182 _M_deallocate_nodes(_Node
**, size_type
);
185 _M_allocate_buckets(size_type __n
);
188 _M_deallocate_buckets(_Node
**, size_type __n
);
191 // Constructor, destructor, assignment, swap
192 _Hashtable(size_type __bucket_hint
,
193 const _H1
&, const _H2
&, const _Hash
&,
194 const _Equal
&, const _ExtractKey
&,
195 const allocator_type
&);
197 template<typename _InputIterator
>
198 _Hashtable(_InputIterator __first
, _InputIterator __last
,
199 size_type __bucket_hint
,
200 const _H1
&, const _H2
&, const _Hash
&,
201 const _Equal
&, const _ExtractKey
&,
202 const allocator_type
&);
204 _Hashtable(const _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
); }
242 { return _M_element_count
; }
246 { return size() == 0; }
249 get_allocator() const
250 { return allocator_type(_M_node_allocator
); }
252 _Value_allocator_type
253 _M_get_Value_allocator() const
254 { return _Value_allocator_type(_M_node_allocator
); }
258 { return _M_node_allocator
.max_size(); }
263 { return this->_M_eq
; }
265 // hash_function, if present, comes from _Hash_code_base.
270 { return _M_bucket_count
; }
273 max_bucket_count() const
274 { return max_size(); }
277 bucket_size(size_type __n
) const
278 { return std::distance(begin(__n
), end(__n
)); }
281 bucket(const key_type
& __k
) const
283 return this->_M_bucket_index(__k
, this->_M_hash_code(__k
),
289 { return local_iterator(_M_buckets
[__n
]); }
293 { return local_iterator(0); }
296 begin(size_type __n
) const
297 { return const_local_iterator(_M_buckets
[__n
]); }
301 { return const_local_iterator(0); }
306 return static_cast<float>(size()) / static_cast<float>(bucket_count());
309 // max_load_factor, if present, comes from _Rehash_base.
311 // Generalization of max_load_factor. Extension, not found in TR1. Only
312 // useful if _RehashPolicy is something other than the default.
314 __rehash_policy() const
315 { return _M_rehash_policy
; }
318 __rehash_policy(const _RehashPolicy
&);
322 find(const key_type
& __k
);
325 find(const key_type
& __k
) const;
328 count(const key_type
& __k
) const;
330 std::pair
<iterator
, iterator
>
331 equal_range(const key_type
& __k
);
333 std::pair
<const_iterator
, const_iterator
>
334 equal_range(const key_type
& __k
) const;
336 private: // Find, insert and erase helper functions
337 // ??? This dispatching is a workaround for the fact that we don't
338 // have partial specialization of member templates; it would be
339 // better to just specialize insert on __unique_keys. There may be a
340 // cleaner workaround.
341 typedef typename
__gnu_cxx::__conditional_type
<__unique_keys
,
342 std::pair
<iterator
, bool>, iterator
>::__type
345 typedef typename
__gnu_cxx::__conditional_type
<__unique_keys
,
346 std::_Select1st
<_Insert_Return_Type
>,
347 std::_Identity
<_Insert_Return_Type
>
352 _M_find_node(_Node
*, const key_type
&,
353 typename
_Hashtable::_Hash_code_type
) const;
356 _M_insert_bucket(const value_type
&, size_type
,
357 typename
_Hashtable::_Hash_code_type
);
359 std::pair
<iterator
, bool>
360 _M_insert(const value_type
&, std::tr1::true_type
);
363 _M_insert(const value_type
&, std::tr1::false_type
);
366 _M_erase_node(_Node
*, _Node
**);
371 insert(const value_type
& __v
)
372 { return _M_insert(__v
, std::tr1::integral_constant
<bool,
376 insert(iterator
, const value_type
& __v
)
377 { return iterator(_Insert_Conv_Type()(this->insert(__v
))); }
380 insert(const_iterator
, const value_type
& __v
)
381 { return const_iterator(_Insert_Conv_Type()(this->insert(__v
))); }
383 template<typename _InputIterator
>
385 insert(_InputIterator __first
, _InputIterator __last
);
391 erase(const_iterator
);
394 erase(const key_type
&);
397 erase(iterator
, iterator
);
400 erase(const_iterator
, const_iterator
);
405 // Set number of buckets to be appropriate for container of n element.
406 void rehash(size_type __n
);
409 // Unconditionally change size of bucket array to n.
410 void _M_rehash(size_type __n
);
414 // Definitions of class template _Hashtable's out-of-line member functions.
415 template<typename _Key
, typename _Value
,
416 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
417 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
418 bool __chc
, bool __cit
, bool __uk
>
419 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
420 _H1
, _H2
, _Hash
, _RehashPolicy
,
421 __chc
, __cit
, __uk
>::_Node
*
422 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
423 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
424 _M_allocate_node(const value_type
& __v
)
426 _Node
* __n
= _M_node_allocator
.allocate(1);
429 _M_get_Value_allocator().construct(&__n
->_M_v
, __v
);
435 _M_node_allocator
.deallocate(__n
, 1);
436 __throw_exception_again
;
440 template<typename _Key
, typename _Value
,
441 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
442 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
443 bool __chc
, bool __cit
, bool __uk
>
445 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
446 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
447 _M_deallocate_node(_Node
* __n
)
449 _M_get_Value_allocator().destroy(&__n
->_M_v
);
450 _M_node_allocator
.deallocate(__n
, 1);
453 template<typename _Key
, typename _Value
,
454 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
455 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
456 bool __chc
, bool __cit
, bool __uk
>
458 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
459 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
460 _M_deallocate_nodes(_Node
** __array
, size_type __n
)
462 for (size_type __i
= 0; __i
< __n
; ++__i
)
464 _Node
* __p
= __array
[__i
];
469 _M_deallocate_node(__tmp
);
475 template<typename _Key
, typename _Value
,
476 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
477 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
478 bool __chc
, bool __cit
, bool __uk
>
479 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
480 _H1
, _H2
, _Hash
, _RehashPolicy
,
481 __chc
, __cit
, __uk
>::_Node
**
482 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
483 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
484 _M_allocate_buckets(size_type __n
)
486 _Bucket_allocator_type
__alloc(_M_node_allocator
);
488 // We allocate one extra bucket to hold a sentinel, an arbitrary
489 // non-null pointer. Iterator increment relies on this.
490 _Node
** __p
= __alloc
.allocate(__n
+ 1);
491 std::fill(__p
, __p
+ __n
, (_Node
*) 0);
492 __p
[__n
] = reinterpret_cast<_Node
*>(0x1000);
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
>
501 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
502 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
503 _M_deallocate_buckets(_Node
** __p
, size_type __n
)
505 _Bucket_allocator_type
__alloc(_M_node_allocator
);
506 __alloc
.deallocate(__p
, __n
+ 1);
509 template<typename _Key
, typename _Value
,
510 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
511 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
512 bool __chc
, bool __cit
, bool __uk
>
513 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
514 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
515 _Hashtable(size_type __bucket_hint
,
516 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
517 const _Equal
& __eq
, const _ExtractKey
& __exk
,
518 const allocator_type
& __a
)
519 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(),
520 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
521 _H1
, _H2
, _Hash
, __chc
>(__exk
, __eq
,
523 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(),
524 _M_node_allocator(__a
),
529 _M_bucket_count
= _M_rehash_policy
._M_next_bkt(__bucket_hint
);
530 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
533 template<typename _Key
, typename _Value
,
534 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
535 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
536 bool __chc
, bool __cit
, bool __uk
>
537 template<typename _InputIterator
>
538 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
539 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
540 _Hashtable(_InputIterator __f
, _InputIterator __l
,
541 size_type __bucket_hint
,
542 const _H1
& __h1
, const _H2
& __h2
, const _Hash
& __h
,
543 const _Equal
& __eq
, const _ExtractKey
& __exk
,
544 const allocator_type
& __a
)
545 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(),
546 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
547 _H1
, _H2
, _Hash
, __chc
>(__exk
, __eq
,
549 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(),
550 _M_node_allocator(__a
),
555 _M_bucket_count
= std::max(_M_rehash_policy
._M_next_bkt(__bucket_hint
),
557 _M_bkt_for_elements(__detail::
560 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
563 for (; __f
!= __l
; ++__f
)
569 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
570 __throw_exception_again
;
574 template<typename _Key
, typename _Value
,
575 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
576 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
577 bool __chc
, bool __cit
, bool __uk
>
578 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
579 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
580 _Hashtable(const _Hashtable
& __ht
)
581 : __detail::_Rehash_base
<_RehashPolicy
, _Hashtable
>(__ht
),
582 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
583 _H1
, _H2
, _Hash
, __chc
>(__ht
),
584 __detail::_Map_base
<_Key
, _Value
, _ExtractKey
, __uk
, _Hashtable
>(__ht
),
585 _M_node_allocator(__ht
._M_node_allocator
),
586 _M_bucket_count(__ht
._M_bucket_count
),
587 _M_element_count(__ht
._M_element_count
),
588 _M_rehash_policy(__ht
._M_rehash_policy
)
590 _M_buckets
= _M_allocate_buckets(_M_bucket_count
);
593 for (size_type __i
= 0; __i
< __ht
._M_bucket_count
; ++__i
)
595 _Node
* __n
= __ht
._M_buckets
[__i
];
596 _Node
** __tail
= _M_buckets
+ __i
;
599 *__tail
= _M_allocate_node(__n
->_M_v
);
600 this->_M_copy_code(*__tail
, __n
);
601 __tail
= &((*__tail
)->_M_next
);
609 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
610 __throw_exception_again
;
614 template<typename _Key
, typename _Value
,
615 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
616 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
617 bool __chc
, bool __cit
, bool __uk
>
618 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
619 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>&
620 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
621 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
622 operator=(const _Hashtable
& __ht
)
624 _Hashtable
__tmp(__ht
);
629 template<typename _Key
, typename _Value
,
630 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
631 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
632 bool __chc
, bool __cit
, bool __uk
>
633 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
634 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
638 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
641 template<typename _Key
, typename _Value
,
642 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
643 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
644 bool __chc
, bool __cit
, bool __uk
>
646 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
647 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
648 swap(_Hashtable
& __x
)
650 // The only base class with member variables is hash_code_base. We
651 // define _Hash_code_base::_M_swap because different specializations
652 // have different members.
653 __detail::_Hash_code_base
<_Key
, _Value
, _ExtractKey
, _Equal
,
654 _H1
, _H2
, _Hash
, __chc
>::_M_swap(__x
);
656 // _GLIBCXX_RESOLVE_LIB_DEFECTS
657 // 431. Swapping containers with unequal allocators.
658 std::__alloc_swap
<_Node_allocator_type
>::_S_do_it(_M_node_allocator
,
659 __x
._M_node_allocator
);
661 std::swap(_M_rehash_policy
, __x
._M_rehash_policy
);
662 std::swap(_M_buckets
, __x
._M_buckets
);
663 std::swap(_M_bucket_count
, __x
._M_bucket_count
);
664 std::swap(_M_element_count
, __x
._M_element_count
);
667 template<typename _Key
, typename _Value
,
668 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
669 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
670 bool __chc
, bool __cit
, bool __uk
>
672 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
673 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
674 __rehash_policy(const _RehashPolicy
& __pol
)
676 _M_rehash_policy
= __pol
;
677 size_type __n_bkt
= __pol
._M_bkt_for_elements(_M_element_count
);
678 if (__n_bkt
> _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
>
686 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
687 _H1
, _H2
, _Hash
, _RehashPolicy
,
688 __chc
, __cit
, __uk
>::iterator
689 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
690 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
691 find(const key_type
& __k
)
693 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
694 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
695 _Node
* __p
= _M_find_node(_M_buckets
[__n
], __k
, __code
);
696 return __p
? iterator(__p
, _M_buckets
+ __n
) : this->end();
699 template<typename _Key
, typename _Value
,
700 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
701 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
702 bool __chc
, bool __cit
, bool __uk
>
703 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
704 _H1
, _H2
, _Hash
, _RehashPolicy
,
705 __chc
, __cit
, __uk
>::const_iterator
706 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
707 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
708 find(const key_type
& __k
) const
710 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
711 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
712 _Node
* __p
= _M_find_node(_M_buckets
[__n
], __k
, __code
);
713 return __p
? const_iterator(__p
, _M_buckets
+ __n
) : this->end();
716 template<typename _Key
, typename _Value
,
717 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
718 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
719 bool __chc
, bool __cit
, bool __uk
>
720 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
721 _H1
, _H2
, _Hash
, _RehashPolicy
,
722 __chc
, __cit
, __uk
>::size_type
723 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
724 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
725 count(const key_type
& __k
) const
727 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
728 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
729 std::size_t __result
= 0;
730 for (_Node
* __p
= _M_buckets
[__n
]; __p
; __p
= __p
->_M_next
)
731 if (this->_M_compare(__k
, __code
, __p
))
736 template<typename _Key
, typename _Value
,
737 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
738 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
739 bool __chc
, bool __cit
, bool __uk
>
740 std::pair
<typename _Hashtable
<_Key
, _Value
, _Allocator
,
741 _ExtractKey
, _Equal
, _H1
,
742 _H2
, _Hash
, _RehashPolicy
,
743 __chc
, __cit
, __uk
>::iterator
,
744 typename _Hashtable
<_Key
, _Value
, _Allocator
,
745 _ExtractKey
, _Equal
, _H1
,
746 _H2
, _Hash
, _RehashPolicy
,
747 __chc
, __cit
, __uk
>::iterator
>
748 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
749 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
750 equal_range(const key_type
& __k
)
752 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
753 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
754 _Node
** __head
= _M_buckets
+ __n
;
755 _Node
* __p
= _M_find_node(*__head
, __k
, __code
);
759 _Node
* __p1
= __p
->_M_next
;
760 for (; __p1
; __p1
= __p1
->_M_next
)
761 if (!this->_M_compare(__k
, __code
, __p1
))
764 iterator
__first(__p
, __head
);
765 iterator
__last(__p1
, __head
);
767 __last
._M_incr_bucket();
768 return std::make_pair(__first
, __last
);
771 return std::make_pair(this->end(), this->end());
774 template<typename _Key
, typename _Value
,
775 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
776 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
777 bool __chc
, bool __cit
, bool __uk
>
778 std::pair
<typename _Hashtable
<_Key
, _Value
, _Allocator
,
779 _ExtractKey
, _Equal
, _H1
,
780 _H2
, _Hash
, _RehashPolicy
,
781 __chc
, __cit
, __uk
>::const_iterator
,
782 typename _Hashtable
<_Key
, _Value
, _Allocator
,
783 _ExtractKey
, _Equal
, _H1
,
784 _H2
, _Hash
, _RehashPolicy
,
785 __chc
, __cit
, __uk
>::const_iterator
>
786 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
787 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
788 equal_range(const key_type
& __k
) const
790 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
791 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
792 _Node
** __head
= _M_buckets
+ __n
;
793 _Node
* __p
= _M_find_node(*__head
, __k
, __code
);
797 _Node
* __p1
= __p
->_M_next
;
798 for (; __p1
; __p1
= __p1
->_M_next
)
799 if (!this->_M_compare(__k
, __code
, __p1
))
802 const_iterator
__first(__p
, __head
);
803 const_iterator
__last(__p1
, __head
);
805 __last
._M_incr_bucket();
806 return std::make_pair(__first
, __last
);
809 return std::make_pair(this->end(), this->end());
812 // Find the node whose key compares equal to k, beginning the search
813 // at p (usually the head of a bucket). Return nil if no node is found.
814 template<typename _Key
, typename _Value
,
815 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
816 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
817 bool __chc
, bool __cit
, bool __uk
>
818 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
,
819 _Equal
, _H1
, _H2
, _Hash
, _RehashPolicy
,
820 __chc
, __cit
, __uk
>::_Node
*
821 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
822 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
823 _M_find_node(_Node
* __p
, const key_type
& __k
,
824 typename
_Hashtable::_Hash_code_type __code
) const
826 for (; __p
; __p
= __p
->_M_next
)
827 if (this->_M_compare(__k
, __code
, __p
))
832 // Insert v in bucket n (assumes no element with its key already present).
833 template<typename _Key
, typename _Value
,
834 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
835 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
836 bool __chc
, bool __cit
, bool __uk
>
837 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
838 _H1
, _H2
, _Hash
, _RehashPolicy
,
839 __chc
, __cit
, __uk
>::iterator
840 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
841 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
842 _M_insert_bucket(const value_type
& __v
, size_type __n
,
843 typename
_Hashtable::_Hash_code_type __code
)
845 std::pair
<bool, std::size_t> __do_rehash
846 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
847 _M_element_count
, 1);
849 // Allocate the new node before doing the rehash so that we don't
850 // do a rehash if the allocation throws.
851 _Node
* __new_node
= _M_allocate_node(__v
);
855 if (__do_rehash
.first
)
857 const key_type
& __k
= this->_M_extract(__v
);
858 __n
= this->_M_bucket_index(__k
, __code
, __do_rehash
.second
);
859 _M_rehash(__do_rehash
.second
);
862 __new_node
->_M_next
= _M_buckets
[__n
];
863 this->_M_store_code(__new_node
, __code
);
864 _M_buckets
[__n
] = __new_node
;
866 return iterator(__new_node
, _M_buckets
+ __n
);
870 _M_deallocate_node(__new_node
);
871 __throw_exception_again
;
875 // Insert v if no element with its key is already present.
876 template<typename _Key
, typename _Value
,
877 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
878 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
879 bool __chc
, bool __cit
, bool __uk
>
880 std::pair
<typename _Hashtable
<_Key
, _Value
, _Allocator
,
881 _ExtractKey
, _Equal
, _H1
,
882 _H2
, _Hash
, _RehashPolicy
,
883 __chc
, __cit
, __uk
>::iterator
, bool>
884 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
885 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
886 _M_insert(const value_type
& __v
, std::tr1::true_type
)
888 const key_type
& __k
= this->_M_extract(__v
);
889 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
890 size_type __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
892 if (_Node
* __p
= _M_find_node(_M_buckets
[__n
], __k
, __code
))
893 return std::make_pair(iterator(__p
, _M_buckets
+ __n
), false);
894 return std::make_pair(_M_insert_bucket(__v
, __n
, __code
), true);
897 // Insert v unconditionally.
898 template<typename _Key
, typename _Value
,
899 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
900 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
901 bool __chc
, bool __cit
, bool __uk
>
902 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
903 _H1
, _H2
, _Hash
, _RehashPolicy
,
904 __chc
, __cit
, __uk
>::iterator
905 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
906 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
907 _M_insert(const value_type
& __v
, std::tr1::false_type
)
909 std::pair
<bool, std::size_t> __do_rehash
910 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
911 _M_element_count
, 1);
912 if (__do_rehash
.first
)
913 _M_rehash(__do_rehash
.second
);
915 const key_type
& __k
= this->_M_extract(__v
);
916 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
917 size_type __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
919 // First find the node, avoid leaking new_node if compare throws.
920 _Node
* __prev
= _M_find_node(_M_buckets
[__n
], __k
, __code
);
921 _Node
* __new_node
= _M_allocate_node(__v
);
925 __new_node
->_M_next
= __prev
->_M_next
;
926 __prev
->_M_next
= __new_node
;
930 __new_node
->_M_next
= _M_buckets
[__n
];
931 _M_buckets
[__n
] = __new_node
;
933 this->_M_store_code(__new_node
, __code
);
936 return iterator(__new_node
, _M_buckets
+ __n
);
939 // For erase(iterator) and erase(const_iterator).
940 template<typename _Key
, typename _Value
,
941 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
942 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
943 bool __chc
, bool __cit
, bool __uk
>
945 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
946 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
947 _M_erase_node(_Node
* __p
, _Node
** __b
)
951 *__b
= __cur
->_M_next
;
954 _Node
* __next
= __cur
->_M_next
;
955 while (__next
!= __p
)
958 __next
= __cur
->_M_next
;
960 __cur
->_M_next
= __next
->_M_next
;
963 _M_deallocate_node(__p
);
967 template<typename _Key
, typename _Value
,
968 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
969 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
970 bool __chc
, bool __cit
, bool __uk
>
971 template<typename _InputIterator
>
973 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
974 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
975 insert(_InputIterator __first
, _InputIterator __last
)
977 size_type __n_elt
= __detail::__distance_fw(__first
, __last
);
978 std::pair
<bool, std::size_t> __do_rehash
979 = _M_rehash_policy
._M_need_rehash(_M_bucket_count
,
980 _M_element_count
, __n_elt
);
981 if (__do_rehash
.first
)
982 _M_rehash(__do_rehash
.second
);
984 for (; __first
!= __last
; ++__first
)
985 this->insert(*__first
);
988 template<typename _Key
, typename _Value
,
989 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
990 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
991 bool __chc
, bool __cit
, bool __uk
>
992 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
993 _H1
, _H2
, _Hash
, _RehashPolicy
,
994 __chc
, __cit
, __uk
>::iterator
995 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
996 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
999 iterator __result
= __it
;
1001 _M_erase_node(__it
._M_cur_node
, __it
._M_cur_bucket
);
1005 template<typename _Key
, typename _Value
,
1006 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1007 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1008 bool __chc
, bool __cit
, bool __uk
>
1009 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1010 _H1
, _H2
, _Hash
, _RehashPolicy
,
1011 __chc
, __cit
, __uk
>::const_iterator
1012 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1013 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1014 erase(const_iterator __it
)
1016 const_iterator __result
= __it
;
1018 _M_erase_node(__it
._M_cur_node
, __it
._M_cur_bucket
);
1022 template<typename _Key
, typename _Value
,
1023 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1024 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1025 bool __chc
, bool __cit
, bool __uk
>
1026 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1027 _H1
, _H2
, _Hash
, _RehashPolicy
,
1028 __chc
, __cit
, __uk
>::size_type
1029 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1030 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1031 erase(const key_type
& __k
)
1033 typename
_Hashtable::_Hash_code_type __code
= this->_M_hash_code(__k
);
1034 std::size_t __n
= this->_M_bucket_index(__k
, __code
, _M_bucket_count
);
1035 size_type __result
= 0;
1037 _Node
** __slot
= _M_buckets
+ __n
;
1038 while (*__slot
&& !this->_M_compare(__k
, __code
, *__slot
))
1039 __slot
= &((*__slot
)->_M_next
);
1041 _Node
** __saved_slot
= 0;
1042 while (*__slot
&& this->_M_compare(__k
, __code
, *__slot
))
1044 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1045 // 526. Is it undefined if a function in the standard changes
1047 if (&this->_M_extract((*__slot
)->_M_v
) != &__k
)
1049 _Node
* __p
= *__slot
;
1050 *__slot
= __p
->_M_next
;
1051 _M_deallocate_node(__p
);
1057 __saved_slot
= __slot
;
1058 __slot
= &((*__slot
)->_M_next
);
1064 _Node
* __p
= *__saved_slot
;
1065 *__saved_slot
= __p
->_M_next
;
1066 _M_deallocate_node(__p
);
1074 // ??? This could be optimized by taking advantage of the bucket
1075 // structure, but it's not clear that it's worth doing. It probably
1076 // wouldn't even be an optimization unless the load factor is large.
1077 template<typename _Key
, typename _Value
,
1078 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1079 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1080 bool __chc
, bool __cit
, bool __uk
>
1081 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1082 _H1
, _H2
, _Hash
, _RehashPolicy
,
1083 __chc
, __cit
, __uk
>::iterator
1084 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1085 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1086 erase(iterator __first
, iterator __last
)
1088 while (__first
!= __last
)
1089 __first
= this->erase(__first
);
1093 template<typename _Key
, typename _Value
,
1094 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1095 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1096 bool __chc
, bool __cit
, bool __uk
>
1097 typename _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1098 _H1
, _H2
, _Hash
, _RehashPolicy
,
1099 __chc
, __cit
, __uk
>::const_iterator
1100 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1101 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1102 erase(const_iterator __first
, const_iterator __last
)
1104 while (__first
!= __last
)
1105 __first
= this->erase(__first
);
1109 template<typename _Key
, typename _Value
,
1110 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1111 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1112 bool __chc
, bool __cit
, bool __uk
>
1114 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1115 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1118 _M_deallocate_nodes(_M_buckets
, _M_bucket_count
);
1119 _M_element_count
= 0;
1122 template<typename _Key
, typename _Value
,
1123 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1124 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1125 bool __chc
, bool __cit
, bool __uk
>
1127 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1128 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1129 rehash(size_type __n
)
1131 _M_rehash(std::max(_M_rehash_policy
._M_next_bkt(__n
),
1132 _M_rehash_policy
._M_bkt_for_elements(_M_element_count
1136 template<typename _Key
, typename _Value
,
1137 typename _Allocator
, typename _ExtractKey
, typename _Equal
,
1138 typename _H1
, typename _H2
, typename _Hash
, typename _RehashPolicy
,
1139 bool __chc
, bool __cit
, bool __uk
>
1141 _Hashtable
<_Key
, _Value
, _Allocator
, _ExtractKey
, _Equal
,
1142 _H1
, _H2
, _Hash
, _RehashPolicy
, __chc
, __cit
, __uk
>::
1143 _M_rehash(size_type __n
)
1145 _Node
** __new_array
= _M_allocate_buckets(__n
);
1148 for (size_type __i
= 0; __i
< _M_bucket_count
; ++__i
)
1149 while (_Node
* __p
= _M_buckets
[__i
])
1151 std::size_t __new_index
= this->_M_bucket_index(__p
, __n
);
1152 _M_buckets
[__i
] = __p
->_M_next
;
1153 __p
->_M_next
= __new_array
[__new_index
];
1154 __new_array
[__new_index
] = __p
;
1156 _M_deallocate_buckets(_M_buckets
, _M_bucket_count
);
1157 _M_bucket_count
= __n
;
1158 _M_buckets
= __new_array
;
1162 // A failure here means that a hash function threw an exception.
1163 // We can't restore the previous state without calling the hash
1164 // function again, so the only sensible recovery is to delete
1166 _M_deallocate_nodes(__new_array
, __n
);
1167 _M_deallocate_buckets(__new_array
, __n
);
1168 _M_deallocate_nodes(_M_buckets
, _M_bucket_count
);
1169 _M_element_count
= 0;
1170 __throw_exception_again
;
1176 #endif // _GLIBCXX_TR1_HASHTABLE_H