1 // hashtable.h header -*- C++ -*-
3 // Copyright (C) 2007, 2008, 2009, 2010, 2011 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 * Do not attempt to use it directly. @headername{unordered_map, unordered_set}
31 #define _HASHTABLE_H 1
33 #pragma GCC system_header
35 #include <bits/hashtable_policy.h>
37 namespace std _GLIBCXX_VISIBILITY(default)
39 _GLIBCXX_BEGIN_NAMESPACE_VERSION
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,
124 public __detail::_Equality_base<_ExtractKey, __unique_keys,
125 _Hashtable<_Key, _Value, _Allocator,
127 _Equal, _H1, _H2, _Hash,
130 __constant_iterators,
134 typedef _Allocator allocator_type;
135 typedef _Value value_type;
136 typedef _Key key_type;
137 typedef _Equal key_equal;
138 // mapped_type, if present, comes from _Map_base.
139 // hasher, if present, comes from _Hash_code_base.
140 typedef typename _Allocator::pointer pointer;
141 typedef typename _Allocator::const_pointer const_pointer;
142 typedef typename _Allocator::reference reference;
143 typedef typename _Allocator::const_reference const_reference;
145 typedef std::size_t size_type;
146 typedef std::ptrdiff_t difference_type;
147 typedef __detail::_Node_iterator<value_type, __constant_iterators,
150 typedef __detail::_Node_const_iterator<value_type,
151 __constant_iterators,
153 const_local_iterator;
155 typedef __detail::_Hashtable_iterator<value_type, __constant_iterators,
158 typedef __detail::_Hashtable_const_iterator<value_type,
159 __constant_iterators,
163 template<typename _Key2, typename _Value2, typename _Ex2, bool __unique2,
164 typename _Hashtable2>
165 friend struct __detail::_Map_base;
168 typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node;
169 typedef typename _Allocator::template rebind<_Node>::other
170 _Node_allocator_type;
171 typedef typename _Allocator::template rebind<_Node*>::other
172 _Bucket_allocator_type;
174 typedef typename _Allocator::template rebind<_Value>::other
175 _Value_allocator_type;
177 _Node_allocator_type _M_node_allocator;
179 size_type _M_bucket_count;
180 size_type _M_begin_bucket_index; // First non-empty bucket.
181 size_type _M_element_count;
182 _RehashPolicy _M_rehash_policy;
184 template<typename... _Args>
186 _M_allocate_node(_Args&&... __args);
189 _M_deallocate_node(_Node* __n);
192 _M_deallocate_nodes(_Node**, size_type);
195 _M_allocate_buckets(size_type __n);
198 _M_deallocate_buckets(_Node**, size_type __n);
201 // Constructor, destructor, assignment, swap
202 _Hashtable(size_type __bucket_hint,
203 const _H1&, const _H2&, const _Hash&,
204 const _Equal&, const _ExtractKey&,
205 const allocator_type&);
207 template<typename _InputIterator>
208 _Hashtable(_InputIterator __first, _InputIterator __last,
209 size_type __bucket_hint,
210 const _H1&, const _H2&, const _Hash&,
211 const _Equal&, const _ExtractKey&,
212 const allocator_type&);
214 _Hashtable(const _Hashtable&);
216 _Hashtable(_Hashtable&&);
219 operator=(const _Hashtable& __ht)
221 _Hashtable __tmp(__ht);
227 operator=(_Hashtable&& __ht)
238 void swap(_Hashtable&);
240 // Basic container operations
243 { return iterator(_M_buckets + _M_begin_bucket_index); }
247 { return const_iterator(_M_buckets + _M_begin_bucket_index); }
251 { return iterator(_M_buckets + _M_bucket_count); }
255 { return const_iterator(_M_buckets + _M_bucket_count); }
259 { return const_iterator(_M_buckets + _M_begin_bucket_index); }
263 { return const_iterator(_M_buckets + _M_bucket_count); }
267 { return _M_element_count; }
271 { return size() == 0; }
274 get_allocator() const
275 { return allocator_type(_M_node_allocator); }
279 { return _M_node_allocator.max_size(); }
284 { return this->_M_eq; }
286 // hash_function, if present, comes from _Hash_code_base.
291 { return _M_bucket_count; }
294 max_bucket_count() const
295 { return max_size(); }
298 bucket_size(size_type __n) const
299 { return std::distance(begin(__n), end(__n)); }
302 bucket(const key_type& __k) const
304 return this->_M_bucket_index(__k, this->_M_hash_code(__k),
310 { return local_iterator(_M_buckets[__n]); }
314 { return local_iterator(0); }
317 begin(size_type __n) const
318 { return const_local_iterator(_M_buckets[__n]); }
322 { return const_local_iterator(0); }
326 cbegin(size_type __n) const
327 { return const_local_iterator(_M_buckets[__n]); }
330 cend(size_type) const
331 { return const_local_iterator(0); }
336 return static_cast<float>(size()) / static_cast<float>(bucket_count());
339 // max_load_factor, if present, comes from _Rehash_base.
341 // Generalization of max_load_factor. Extension, not found in TR1. Only
342 // useful if _RehashPolicy is something other than the default.
344 __rehash_policy() const
345 { return _M_rehash_policy; }
348 __rehash_policy(const _RehashPolicy&);
352 find(const key_type& __k);
355 find(const key_type& __k) const;
358 count(const key_type& __k) const;
360 std::pair<iterator, iterator>
361 equal_range(const key_type& __k);
363 std::pair<const_iterator, const_iterator>
364 equal_range(const key_type& __k) const;
367 // Find and insert helper functions and types
369 _M_find_node(_Node*, const key_type&,
370 typename _Hashtable::_Hash_code_type) const;
372 template<typename _Arg>
374 _M_insert_bucket(_Arg&&, size_type,
375 typename _Hashtable::_Hash_code_type);
377 template<typename _Arg>
378 std::pair<iterator, bool>
379 _M_insert(_Arg&&, std::true_type);
381 template<typename _Arg>
383 _M_insert(_Arg&&, std::false_type);
385 typedef typename std::conditional<__unique_keys,
386 std::pair<iterator, bool>,
390 typedef typename std::conditional<__unique_keys,
391 std::_Select1st<_Insert_Return_Type>,
392 std::_Identity<_Insert_Return_Type>
399 insert(const value_type& __v)
400 { return _M_insert(__v, std::integral_constant<bool, __unique_keys>()); }
403 insert(const_iterator, const value_type& __v)
404 { return _Insert_Conv_Type()(insert(__v)); }
407 insert(value_type&& __v)
408 { return _M_insert(std::move(__v),
409 std::integral_constant<bool, __unique_keys>()); }
412 insert(const_iterator, value_type&& __v)
413 { return _Insert_Conv_Type()(insert(std::move(__v))); }
415 template<typename _Pair, typename = typename
416 std::enable_if<!__constant_iterators
417 && std::is_convertible<_Pair,
418 value_type>::value>::type>
421 { return _M_insert(std::forward<_Pair>(__v),
422 std::integral_constant<bool, __unique_keys>()); }
424 template<typename _Pair, typename = typename
425 std::enable_if<!__constant_iterators
426 && std::is_convertible<_Pair,
427 value_type>::value>::type>
429 insert(const_iterator, _Pair&& __v)
430 { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); }
432 template<typename _InputIterator>
434 insert(_InputIterator __first, _InputIterator __last);
437 insert(initializer_list<value_type> __l)
438 { this->insert(__l.begin(), __l.end()); }
441 erase(const_iterator);
444 erase(const key_type&);
447 erase(const_iterator, const_iterator);
452 // Set number of buckets to be appropriate for container of n element.
453 void rehash(size_type __n);
456 // reserve, if present, comes from _Rehash_base.
459 // Unconditionally change size of bucket array to n.
460 void _M_rehash(size_type __n);
464 // Definitions of class template _Hashtable's out-of-line member functions.
465 template<typename _Key, typename _Value,
466 typename _Allocator, typename _ExtractKey, typename _Equal,
467 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
468 bool __chc, bool __cit, bool __uk>
469 template<typename... _Args>
470 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
471 _H1, _H2, _Hash, _RehashPolicy,
472 __chc, __cit, __uk>::_Node*
473 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
474 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
475 _M_allocate_node(_Args&&... __args)
477 _Node* __n = _M_node_allocator.allocate(1);
480 _M_node_allocator.construct(__n, std::forward<_Args>(__args)...);
486 _M_node_allocator.deallocate(__n, 1);
487 __throw_exception_again;
491 template<typename _Key, typename _Value,
492 typename _Allocator, typename _ExtractKey, typename _Equal,
493 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
494 bool __chc, bool __cit, bool __uk>
496 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
497 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
498 _M_deallocate_node(_Node* __n)
500 _M_node_allocator.destroy(__n);
501 _M_node_allocator.deallocate(__n, 1);
504 template<typename _Key, typename _Value,
505 typename _Allocator, typename _ExtractKey, typename _Equal,
506 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
507 bool __chc, bool __cit, bool __uk>
509 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
510 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
511 _M_deallocate_nodes(_Node** __array, size_type __n)
513 for (size_type __i = 0; __i < __n; ++__i)
515 _Node* __p = __array[__i];
520 _M_deallocate_node(__tmp);
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 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
531 _H1, _H2, _Hash, _RehashPolicy,
532 __chc, __cit, __uk>::_Node**
533 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
534 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
535 _M_allocate_buckets(size_type __n)
537 _Bucket_allocator_type __alloc(_M_node_allocator);
539 // We allocate one extra bucket to hold a sentinel, an arbitrary
540 // non-null pointer. Iterator increment relies on this.
541 _Node** __p = __alloc.allocate(__n + 1);
542 std::fill(__p, __p + __n, (_Node*) 0);
543 __p[__n] = reinterpret_cast<_Node*>(0x1000);
547 template<typename _Key, typename _Value,
548 typename _Allocator, typename _ExtractKey, typename _Equal,
549 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
550 bool __chc, bool __cit, bool __uk>
552 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
553 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
554 _M_deallocate_buckets(_Node** __p, size_type __n)
556 _Bucket_allocator_type __alloc(_M_node_allocator);
557 __alloc.deallocate(__p, __n + 1);
560 template<typename _Key, typename _Value,
561 typename _Allocator, typename _ExtractKey, typename _Equal,
562 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
563 bool __chc, bool __cit, bool __uk>
564 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
565 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
566 _Hashtable(size_type __bucket_hint,
567 const _H1& __h1, const _H2& __h2, const _Hash& __h,
568 const _Equal& __eq, const _ExtractKey& __exk,
569 const allocator_type& __a)
570 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
571 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
572 _H1, _H2, _Hash, __chc>(__exk, __eq,
574 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
575 _M_node_allocator(__a),
580 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
581 _M_buckets = _M_allocate_buckets(_M_bucket_count);
582 _M_begin_bucket_index = _M_bucket_count;
585 template<typename _Key, typename _Value,
586 typename _Allocator, typename _ExtractKey, typename _Equal,
587 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
588 bool __chc, bool __cit, bool __uk>
589 template<typename _InputIterator>
590 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
591 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
592 _Hashtable(_InputIterator __f, _InputIterator __l,
593 size_type __bucket_hint,
594 const _H1& __h1, const _H2& __h2, const _Hash& __h,
595 const _Equal& __eq, const _ExtractKey& __exk,
596 const allocator_type& __a)
597 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
598 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
599 _H1, _H2, _Hash, __chc>(__exk, __eq,
601 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
602 _M_node_allocator(__a),
607 _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
609 _M_bkt_for_elements(__detail::
612 _M_buckets = _M_allocate_buckets(_M_bucket_count);
613 _M_begin_bucket_index = _M_bucket_count;
616 for (; __f != __l; ++__f)
622 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
623 __throw_exception_again;
627 template<typename _Key, typename _Value,
628 typename _Allocator, typename _ExtractKey, typename _Equal,
629 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
630 bool __chc, bool __cit, bool __uk>
631 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
632 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
633 _Hashtable(const _Hashtable& __ht)
634 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
635 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
636 _H1, _H2, _Hash, __chc>(__ht),
637 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
638 _M_node_allocator(__ht._M_node_allocator),
639 _M_bucket_count(__ht._M_bucket_count),
640 _M_begin_bucket_index(__ht._M_begin_bucket_index),
641 _M_element_count(__ht._M_element_count),
642 _M_rehash_policy(__ht._M_rehash_policy)
644 _M_buckets = _M_allocate_buckets(_M_bucket_count);
647 for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i)
649 _Node* __n = __ht._M_buckets[__i];
650 _Node** __tail = _M_buckets + __i;
653 *__tail = _M_allocate_node(__n->_M_v);
654 this->_M_copy_code(*__tail, __n);
655 __tail = &((*__tail)->_M_next);
663 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
664 __throw_exception_again;
668 template<typename _Key, typename _Value,
669 typename _Allocator, typename _ExtractKey, typename _Equal,
670 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
671 bool __chc, bool __cit, bool __uk>
672 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
673 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
674 _Hashtable(_Hashtable&& __ht)
675 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
676 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
677 _H1, _H2, _Hash, __chc>(__ht),
678 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
679 _M_node_allocator(__ht._M_node_allocator),
680 _M_buckets(__ht._M_buckets),
681 _M_bucket_count(__ht._M_bucket_count),
682 _M_begin_bucket_index(__ht._M_begin_bucket_index),
683 _M_element_count(__ht._M_element_count),
684 _M_rehash_policy(__ht._M_rehash_policy)
686 size_type __n_bkt = __ht._M_rehash_policy._M_next_bkt(0);
687 __ht._M_buckets = __ht._M_allocate_buckets(__n_bkt);
688 __ht._M_bucket_count = __n_bkt;
689 __ht._M_begin_bucket_index = __ht._M_bucket_count;
690 __ht._M_element_count = 0;
691 __ht._M_rehash_policy = _RehashPolicy();
694 template<typename _Key, typename _Value,
695 typename _Allocator, typename _ExtractKey, typename _Equal,
696 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
697 bool __chc, bool __cit, bool __uk>
698 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
699 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
703 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
706 template<typename _Key, typename _Value,
707 typename _Allocator, typename _ExtractKey, typename _Equal,
708 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
709 bool __chc, bool __cit, bool __uk>
711 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
712 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
713 swap(_Hashtable& __x)
715 // The only base class with member variables is hash_code_base. We
716 // define _Hash_code_base::_M_swap because different specializations
717 // have different members.
718 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
719 _H1, _H2, _Hash, __chc>::_M_swap(__x);
721 // _GLIBCXX_RESOLVE_LIB_DEFECTS
722 // 431. Swapping containers with unequal allocators.
723 std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
724 __x._M_node_allocator);
726 std::swap(_M_rehash_policy, __x._M_rehash_policy);
727 std::swap(_M_buckets, __x._M_buckets);
728 std::swap(_M_bucket_count, __x._M_bucket_count);
729 std::swap(_M_begin_bucket_index, __x._M_begin_bucket_index);
730 std::swap(_M_element_count, __x._M_element_count);
733 template<typename _Key, typename _Value,
734 typename _Allocator, typename _ExtractKey, typename _Equal,
735 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
736 bool __chc, bool __cit, bool __uk>
738 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
739 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
740 __rehash_policy(const _RehashPolicy& __pol)
742 _M_rehash_policy = __pol;
743 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
744 if (__n_bkt > _M_bucket_count)
748 template<typename _Key, typename _Value,
749 typename _Allocator, typename _ExtractKey, typename _Equal,
750 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
751 bool __chc, bool __cit, bool __uk>
752 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
753 _H1, _H2, _Hash, _RehashPolicy,
754 __chc, __cit, __uk>::iterator
755 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
756 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
757 find(const key_type& __k)
759 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
760 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
761 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
762 return __p ? iterator(__p, _M_buckets + __n) : this->end();
765 template<typename _Key, typename _Value,
766 typename _Allocator, typename _ExtractKey, typename _Equal,
767 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
768 bool __chc, bool __cit, bool __uk>
769 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
770 _H1, _H2, _Hash, _RehashPolicy,
771 __chc, __cit, __uk>::const_iterator
772 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
773 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
774 find(const key_type& __k) const
776 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
777 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
778 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
779 return __p ? const_iterator(__p, _M_buckets + __n) : this->end();
782 template<typename _Key, typename _Value,
783 typename _Allocator, typename _ExtractKey, typename _Equal,
784 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
785 bool __chc, bool __cit, bool __uk>
786 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
787 _H1, _H2, _Hash, _RehashPolicy,
788 __chc, __cit, __uk>::size_type
789 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
790 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
791 count(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 std::size_t __result = 0;
796 for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next)
797 if (this->_M_compare(__k, __code, __p))
802 template<typename _Key, typename _Value,
803 typename _Allocator, typename _ExtractKey, typename _Equal,
804 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
805 bool __chc, bool __cit, bool __uk>
806 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
807 _ExtractKey, _Equal, _H1,
808 _H2, _Hash, _RehashPolicy,
809 __chc, __cit, __uk>::iterator,
810 typename _Hashtable<_Key, _Value, _Allocator,
811 _ExtractKey, _Equal, _H1,
812 _H2, _Hash, _RehashPolicy,
813 __chc, __cit, __uk>::iterator>
814 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
815 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
816 equal_range(const key_type& __k)
818 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
819 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
820 _Node** __head = _M_buckets + __n;
821 _Node* __p = _M_find_node(*__head, __k, __code);
825 _Node* __p1 = __p->_M_next;
826 for (; __p1; __p1 = __p1->_M_next)
827 if (!this->_M_compare(__k, __code, __p1))
830 iterator __first(__p, __head);
831 iterator __last(__p1, __head);
833 __last._M_incr_bucket();
834 return std::make_pair(__first, __last);
837 return std::make_pair(this->end(), this->end());
840 template<typename _Key, typename _Value,
841 typename _Allocator, typename _ExtractKey, typename _Equal,
842 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
843 bool __chc, bool __cit, bool __uk>
844 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
845 _ExtractKey, _Equal, _H1,
846 _H2, _Hash, _RehashPolicy,
847 __chc, __cit, __uk>::const_iterator,
848 typename _Hashtable<_Key, _Value, _Allocator,
849 _ExtractKey, _Equal, _H1,
850 _H2, _Hash, _RehashPolicy,
851 __chc, __cit, __uk>::const_iterator>
852 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
853 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
854 equal_range(const key_type& __k) const
856 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
857 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
858 _Node** __head = _M_buckets + __n;
859 _Node* __p = _M_find_node(*__head, __k, __code);
863 _Node* __p1 = __p->_M_next;
864 for (; __p1; __p1 = __p1->_M_next)
865 if (!this->_M_compare(__k, __code, __p1))
868 const_iterator __first(__p, __head);
869 const_iterator __last(__p1, __head);
871 __last._M_incr_bucket();
872 return std::make_pair(__first, __last);
875 return std::make_pair(this->end(), this->end());
878 // Find the node whose key compares equal to k, beginning the search
879 // at p (usually the head of a bucket). Return nil if no node is found.
880 template<typename _Key, typename _Value,
881 typename _Allocator, typename _ExtractKey, typename _Equal,
882 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
883 bool __chc, bool __cit, bool __uk>
884 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
885 _Equal, _H1, _H2, _Hash, _RehashPolicy,
886 __chc, __cit, __uk>::_Node*
887 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
888 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
889 _M_find_node(_Node* __p, const key_type& __k,
890 typename _Hashtable::_Hash_code_type __code) const
892 for (; __p; __p = __p->_M_next)
893 if (this->_M_compare(__k, __code, __p))
898 // Insert v in bucket n (assumes no element with its key already present).
899 template<typename _Key, typename _Value,
900 typename _Allocator, typename _ExtractKey, typename _Equal,
901 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
902 bool __chc, bool __cit, bool __uk>
903 template<typename _Arg>
904 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
905 _H1, _H2, _Hash, _RehashPolicy,
906 __chc, __cit, __uk>::iterator
907 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
908 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
909 _M_insert_bucket(_Arg&& __v, size_type __n,
910 typename _Hashtable::_Hash_code_type __code)
912 std::pair<bool, std::size_t> __do_rehash
913 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
914 _M_element_count, 1);
916 if (__do_rehash.first)
918 const key_type& __k = this->_M_extract(__v);
919 __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
922 // Allocate the new node before doing the rehash so that we don't
923 // do a rehash if the allocation throws.
924 _Node* __new_node = _M_allocate_node(std::forward<_Arg>(__v));
928 if (__do_rehash.first)
929 _M_rehash(__do_rehash.second);
931 __new_node->_M_next = _M_buckets[__n];
932 this->_M_store_code(__new_node, __code);
933 _M_buckets[__n] = __new_node;
935 if (__n < _M_begin_bucket_index)
936 _M_begin_bucket_index = __n;
937 return iterator(__new_node, _M_buckets + __n);
941 _M_deallocate_node(__new_node);
942 __throw_exception_again;
946 // Insert v if no element with its key is already present.
947 template<typename _Key, typename _Value,
948 typename _Allocator, typename _ExtractKey, typename _Equal,
949 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
950 bool __chc, bool __cit, bool __uk>
951 template<typename _Arg>
952 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
953 _ExtractKey, _Equal, _H1,
954 _H2, _Hash, _RehashPolicy,
955 __chc, __cit, __uk>::iterator, bool>
956 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
957 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
958 _M_insert(_Arg&& __v, std::true_type)
960 const key_type& __k = this->_M_extract(__v);
961 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
962 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
964 if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code))
965 return std::make_pair(iterator(__p, _M_buckets + __n), false);
966 return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v),
970 // Insert v unconditionally.
971 template<typename _Key, typename _Value,
972 typename _Allocator, typename _ExtractKey, typename _Equal,
973 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
974 bool __chc, bool __cit, bool __uk>
975 template<typename _Arg>
976 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
977 _H1, _H2, _Hash, _RehashPolicy,
978 __chc, __cit, __uk>::iterator
979 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
980 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
981 _M_insert(_Arg&& __v, std::false_type)
983 std::pair<bool, std::size_t> __do_rehash
984 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
985 _M_element_count, 1);
986 if (__do_rehash.first)
987 _M_rehash(__do_rehash.second);
989 const key_type& __k = this->_M_extract(__v);
990 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
991 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
993 // First find the node, avoid leaking new_node if compare throws.
994 _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code);
995 _Node* __new_node = _M_allocate_node(std::forward<_Arg>(__v));
999 __new_node->_M_next = __prev->_M_next;
1000 __prev->_M_next = __new_node;
1004 __new_node->_M_next = _M_buckets[__n];
1005 _M_buckets[__n] = __new_node;
1006 if (__n < _M_begin_bucket_index)
1007 _M_begin_bucket_index = __n;
1009 this->_M_store_code(__new_node, __code);
1012 return iterator(__new_node, _M_buckets + __n);
1015 template<typename _Key, typename _Value,
1016 typename _Allocator, typename _ExtractKey, typename _Equal,
1017 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1018 bool __chc, bool __cit, bool __uk>
1019 template<typename _InputIterator>
1021 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1022 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1023 insert(_InputIterator __first, _InputIterator __last)
1025 size_type __n_elt = __detail::__distance_fw(__first, __last);
1026 std::pair<bool, std::size_t> __do_rehash
1027 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1028 _M_element_count, __n_elt);
1029 if (__do_rehash.first)
1030 _M_rehash(__do_rehash.second);
1032 for (; __first != __last; ++__first)
1033 this->insert(*__first);
1036 template<typename _Key, typename _Value,
1037 typename _Allocator, typename _ExtractKey, typename _Equal,
1038 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1039 bool __chc, bool __cit, bool __uk>
1040 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1041 _H1, _H2, _Hash, _RehashPolicy,
1042 __chc, __cit, __uk>::iterator
1043 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1044 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1045 erase(const_iterator __it)
1047 iterator __result(__it._M_cur_node, __it._M_cur_bucket);
1050 _Node* __cur = *__it._M_cur_bucket;
1051 if (__cur == __it._M_cur_node)
1053 *__it._M_cur_bucket = __cur->_M_next;
1055 // If _M_begin_bucket_index no longer indexes the first non-empty
1056 // bucket - its single node is being erased - update it.
1057 if (!_M_buckets[_M_begin_bucket_index])
1058 _M_begin_bucket_index = __result._M_cur_bucket - _M_buckets;
1062 _Node* __next = __cur->_M_next;
1063 while (__next != __it._M_cur_node)
1066 __next = __cur->_M_next;
1068 __cur->_M_next = __next->_M_next;
1071 _M_deallocate_node(__it._M_cur_node);
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>::size_type
1084 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1085 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1086 erase(const key_type& __k)
1088 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1089 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
1090 size_type __result = 0;
1092 _Node** __slot = _M_buckets + __n;
1093 while (*__slot && !this->_M_compare(__k, __code, *__slot))
1094 __slot = &((*__slot)->_M_next);
1096 _Node** __saved_slot = 0;
1097 while (*__slot && this->_M_compare(__k, __code, *__slot))
1099 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1100 // 526. Is it undefined if a function in the standard changes
1102 if (std::__addressof(this->_M_extract((*__slot)->_M_v))
1103 != std::__addressof(__k))
1105 _Node* __p = *__slot;
1106 *__slot = __p->_M_next;
1107 _M_deallocate_node(__p);
1113 __saved_slot = __slot;
1114 __slot = &((*__slot)->_M_next);
1120 _Node* __p = *__saved_slot;
1121 *__saved_slot = __p->_M_next;
1122 _M_deallocate_node(__p);
1127 // If the entire bucket indexed by _M_begin_bucket_index has been
1128 // erased look forward for the first non-empty bucket.
1129 if (!_M_buckets[_M_begin_bucket_index])
1131 if (!_M_element_count)
1132 _M_begin_bucket_index = _M_bucket_count;
1135 ++_M_begin_bucket_index;
1136 while (!_M_buckets[_M_begin_bucket_index])
1137 ++_M_begin_bucket_index;
1144 // ??? This could be optimized by taking advantage of the bucket
1145 // structure, but it's not clear that it's worth doing. It probably
1146 // wouldn't even be an optimization unless the load factor is large.
1147 template<typename _Key, typename _Value,
1148 typename _Allocator, typename _ExtractKey, typename _Equal,
1149 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1150 bool __chc, bool __cit, bool __uk>
1151 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1152 _H1, _H2, _Hash, _RehashPolicy,
1153 __chc, __cit, __uk>::iterator
1154 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1155 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1156 erase(const_iterator __first, const_iterator __last)
1158 while (__first != __last)
1159 __first = this->erase(__first);
1160 return iterator(__last._M_cur_node, __last._M_cur_bucket);
1163 template<typename _Key, typename _Value,
1164 typename _Allocator, typename _ExtractKey, typename _Equal,
1165 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1166 bool __chc, bool __cit, bool __uk>
1168 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1169 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1172 _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1173 _M_element_count = 0;
1174 _M_begin_bucket_index = _M_bucket_count;
1177 template<typename _Key, typename _Value,
1178 typename _Allocator, typename _ExtractKey, typename _Equal,
1179 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1180 bool __chc, bool __cit, bool __uk>
1182 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1183 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1184 rehash(size_type __n)
1186 _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
1187 _M_rehash_policy._M_bkt_for_elements(_M_element_count
1191 template<typename _Key, typename _Value,
1192 typename _Allocator, typename _ExtractKey, typename _Equal,
1193 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1194 bool __chc, bool __cit, bool __uk>
1196 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1197 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1198 _M_rehash(size_type __n)
1200 _Node** __new_array = _M_allocate_buckets(__n);
1203 _M_begin_bucket_index = __n;
1204 for (size_type __i = 0; __i < _M_bucket_count; ++__i)
1205 while (_Node* __p = _M_buckets[__i])
1207 std::size_t __new_index = this->_M_bucket_index(__p, __n);
1208 _M_buckets[__i] = __p->_M_next;
1209 __p->_M_next = __new_array[__new_index];
1210 __new_array[__new_index] = __p;
1211 if (__new_index < _M_begin_bucket_index)
1212 _M_begin_bucket_index = __new_index;
1214 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1215 _M_bucket_count = __n;
1216 _M_buckets = __new_array;
1220 // A failure here means that a hash function threw an exception.
1221 // We can't restore the previous state without calling the hash
1222 // function again, so the only sensible recovery is to delete
1224 _M_deallocate_nodes(__new_array, __n);
1225 _M_deallocate_buckets(__new_array, __n);
1226 _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1227 _M_element_count = 0;
1228 _M_begin_bucket_index = _M_bucket_count;
1229 __throw_exception_again;
1233 _GLIBCXX_END_NAMESPACE_VERSION
1236 #endif // _HASHTABLE_H