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)
236 ~_Hashtable() noexcept;
238 void swap(_Hashtable&);
240 // Basic container operations
243 { return iterator(_M_buckets + _M_begin_bucket_index); }
246 begin() const noexcept
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); }
258 cbegin() const noexcept
259 { return const_iterator(_M_buckets + _M_begin_bucket_index); }
262 cend() const noexcept
263 { return const_iterator(_M_buckets + _M_bucket_count); }
266 size() const noexcept
267 { return _M_element_count; }
270 empty() const noexcept
271 { return size() == 0; }
274 get_allocator() const noexcept
275 { return allocator_type(_M_node_allocator); }
278 max_size() const noexcept
279 { return _M_node_allocator.max_size(); }
284 { return this->_M_eq; }
286 // hash_function, if present, comes from _Hash_code_base.
290 bucket_count() const noexcept
291 { return _M_bucket_count; }
294 max_bucket_count() const noexcept
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); }
334 load_factor() const noexcept
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 typedef typename std::conditional<__unique_keys,
378 std::pair<iterator, bool>,
382 typedef typename std::conditional<__unique_keys,
383 std::_Select1st<_Insert_Return_Type>,
384 std::_Identity<_Insert_Return_Type>
389 template<typename _Arg>
390 std::pair<iterator, bool>
391 _M_insert(_Arg&&, std::true_type);
393 template<typename _Arg>
395 _M_insert(_Arg&&, std::false_type);
400 insert(const value_type& __v)
401 { return _M_insert(__v, integral_constant<bool, __unique_keys>()); }
404 insert(const_iterator, const value_type& __v)
405 { return _Insert_Conv_Type()(insert(__v)); }
407 template<typename _Pair, typename = typename
408 std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,
409 std::is_convertible<_Pair,
410 value_type>>::value>::type>
413 { return _M_insert(std::forward<_Pair>(__v),
414 integral_constant<bool, __unique_keys>()); }
416 template<typename _Pair, typename = typename
417 std::enable_if<__and_<integral_constant<bool, !__constant_iterators>,
418 std::is_convertible<_Pair,
419 value_type>>::value>::type>
421 insert(const_iterator, _Pair&& __v)
422 { return _Insert_Conv_Type()(insert(std::forward<_Pair>(__v))); }
424 template<typename _InputIterator>
426 insert(_InputIterator __first, _InputIterator __last);
429 insert(initializer_list<value_type> __l)
430 { this->insert(__l.begin(), __l.end()); }
433 erase(const_iterator);
438 { return erase(const_iterator(__it)); }
441 erase(const key_type&);
444 erase(const_iterator, const_iterator);
449 // Set number of buckets to be appropriate for container of n element.
450 void rehash(size_type __n);
453 // reserve, if present, comes from _Rehash_base.
456 // Unconditionally change size of bucket array to n, restore hash policy
457 // resize value to __next_resize on exception.
458 void _M_rehash(size_type __n, size_type __next_resize);
462 // Definitions of class template _Hashtable's out-of-line member functions.
463 template<typename _Key, typename _Value,
464 typename _Allocator, typename _ExtractKey, typename _Equal,
465 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
466 bool __chc, bool __cit, bool __uk>
467 template<typename... _Args>
468 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
469 _H1, _H2, _Hash, _RehashPolicy,
470 __chc, __cit, __uk>::_Node*
471 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
472 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
473 _M_allocate_node(_Args&&... __args)
475 _Node* __n = _M_node_allocator.allocate(1);
478 _M_node_allocator.construct(__n, std::forward<_Args>(__args)...);
484 _M_node_allocator.deallocate(__n, 1);
485 __throw_exception_again;
489 template<typename _Key, typename _Value,
490 typename _Allocator, typename _ExtractKey, typename _Equal,
491 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
492 bool __chc, bool __cit, bool __uk>
494 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
495 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
496 _M_deallocate_node(_Node* __n)
498 _M_node_allocator.destroy(__n);
499 _M_node_allocator.deallocate(__n, 1);
502 template<typename _Key, typename _Value,
503 typename _Allocator, typename _ExtractKey, typename _Equal,
504 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
505 bool __chc, bool __cit, bool __uk>
507 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
508 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
509 _M_deallocate_nodes(_Node** __array, size_type __n)
511 for (size_type __i = 0; __i < __n; ++__i)
513 _Node* __p = __array[__i];
518 _M_deallocate_node(__tmp);
524 template<typename _Key, typename _Value,
525 typename _Allocator, typename _ExtractKey, typename _Equal,
526 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
527 bool __chc, bool __cit, bool __uk>
528 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
529 _H1, _H2, _Hash, _RehashPolicy,
530 __chc, __cit, __uk>::_Node**
531 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
532 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
533 _M_allocate_buckets(size_type __n)
535 _Bucket_allocator_type __alloc(_M_node_allocator);
537 // We allocate one extra bucket to hold a sentinel, an arbitrary
538 // non-null pointer. Iterator increment relies on this.
539 _Node** __p = __alloc.allocate(__n + 1);
540 std::fill(__p, __p + __n, (_Node*) 0);
541 __p[__n] = reinterpret_cast<_Node*>(0x1000);
545 template<typename _Key, typename _Value,
546 typename _Allocator, typename _ExtractKey, typename _Equal,
547 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
548 bool __chc, bool __cit, bool __uk>
550 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
551 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
552 _M_deallocate_buckets(_Node** __p, size_type __n)
554 _Bucket_allocator_type __alloc(_M_node_allocator);
555 __alloc.deallocate(__p, __n + 1);
558 template<typename _Key, typename _Value,
559 typename _Allocator, typename _ExtractKey, typename _Equal,
560 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
561 bool __chc, bool __cit, bool __uk>
562 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
563 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
564 _Hashtable(size_type __bucket_hint,
565 const _H1& __h1, const _H2& __h2, const _Hash& __h,
566 const _Equal& __eq, const _ExtractKey& __exk,
567 const allocator_type& __a)
568 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
569 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
570 _H1, _H2, _Hash, __chc>(__exk, __eq,
572 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
573 _M_node_allocator(__a),
578 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
579 _M_buckets = _M_allocate_buckets(_M_bucket_count);
580 _M_begin_bucket_index = _M_bucket_count;
583 template<typename _Key, typename _Value,
584 typename _Allocator, typename _ExtractKey, typename _Equal,
585 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
586 bool __chc, bool __cit, bool __uk>
587 template<typename _InputIterator>
588 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
589 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
590 _Hashtable(_InputIterator __f, _InputIterator __l,
591 size_type __bucket_hint,
592 const _H1& __h1, const _H2& __h2, const _Hash& __h,
593 const _Equal& __eq, const _ExtractKey& __exk,
594 const allocator_type& __a)
595 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
596 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
597 _H1, _H2, _Hash, __chc>(__exk, __eq,
599 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
600 _M_node_allocator(__a),
605 _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
607 _M_bkt_for_elements(__detail::
610 _M_buckets = _M_allocate_buckets(_M_bucket_count);
611 _M_begin_bucket_index = _M_bucket_count;
614 for (; __f != __l; ++__f)
620 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
621 __throw_exception_again;
625 template<typename _Key, typename _Value,
626 typename _Allocator, typename _ExtractKey, typename _Equal,
627 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
628 bool __chc, bool __cit, bool __uk>
629 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
630 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
631 _Hashtable(const _Hashtable& __ht)
632 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
633 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
634 _H1, _H2, _Hash, __chc>(__ht),
635 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
636 _M_node_allocator(__ht._M_node_allocator),
637 _M_bucket_count(__ht._M_bucket_count),
638 _M_begin_bucket_index(__ht._M_begin_bucket_index),
639 _M_element_count(__ht._M_element_count),
640 _M_rehash_policy(__ht._M_rehash_policy)
642 _M_buckets = _M_allocate_buckets(_M_bucket_count);
645 for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i)
647 _Node* __n = __ht._M_buckets[__i];
648 _Node** __tail = _M_buckets + __i;
651 *__tail = _M_allocate_node(__n->_M_v);
652 this->_M_copy_code(*__tail, __n);
653 __tail = &((*__tail)->_M_next);
661 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
662 __throw_exception_again;
666 template<typename _Key, typename _Value,
667 typename _Allocator, typename _ExtractKey, typename _Equal,
668 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
669 bool __chc, bool __cit, bool __uk>
670 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
671 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
672 _Hashtable(_Hashtable&& __ht)
673 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
674 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
675 _H1, _H2, _Hash, __chc>(__ht),
676 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
677 _M_node_allocator(std::move(__ht._M_node_allocator)),
678 _M_buckets(__ht._M_buckets),
679 _M_bucket_count(__ht._M_bucket_count),
680 _M_begin_bucket_index(__ht._M_begin_bucket_index),
681 _M_element_count(__ht._M_element_count),
682 _M_rehash_policy(__ht._M_rehash_policy)
684 __ht._M_rehash_policy = _RehashPolicy();
685 __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0);
686 __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count);
687 __ht._M_begin_bucket_index = __ht._M_bucket_count;
688 __ht._M_element_count = 0;
691 template<typename _Key, typename _Value,
692 typename _Allocator, typename _ExtractKey, typename _Equal,
693 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
694 bool __chc, bool __cit, bool __uk>
695 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
696 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
697 ~_Hashtable() noexcept
700 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
703 template<typename _Key, typename _Value,
704 typename _Allocator, typename _ExtractKey, typename _Equal,
705 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
706 bool __chc, bool __cit, bool __uk>
708 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
709 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
710 swap(_Hashtable& __x)
712 // The only base class with member variables is hash_code_base. We
713 // define _Hash_code_base::_M_swap because different specializations
714 // have different members.
715 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
716 _H1, _H2, _Hash, __chc>::_M_swap(__x);
718 // _GLIBCXX_RESOLVE_LIB_DEFECTS
719 // 431. Swapping containers with unequal allocators.
720 std::__alloc_swap<_Node_allocator_type>::_S_do_it(_M_node_allocator,
721 __x._M_node_allocator);
723 std::swap(_M_rehash_policy, __x._M_rehash_policy);
724 std::swap(_M_buckets, __x._M_buckets);
725 std::swap(_M_bucket_count, __x._M_bucket_count);
726 std::swap(_M_begin_bucket_index, __x._M_begin_bucket_index);
727 std::swap(_M_element_count, __x._M_element_count);
730 template<typename _Key, typename _Value,
731 typename _Allocator, typename _ExtractKey, typename _Equal,
732 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
733 bool __chc, bool __cit, bool __uk>
735 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
736 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
737 __rehash_policy(const _RehashPolicy& __pol)
739 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
740 if (__n_bkt > _M_bucket_count)
741 _M_rehash(__n_bkt, _M_rehash_policy._M_next_resize);
742 _M_rehash_policy = __pol;
745 template<typename _Key, typename _Value,
746 typename _Allocator, typename _ExtractKey, typename _Equal,
747 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
748 bool __chc, bool __cit, bool __uk>
749 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
750 _H1, _H2, _Hash, _RehashPolicy,
751 __chc, __cit, __uk>::iterator
752 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
753 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
754 find(const key_type& __k)
756 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
757 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
758 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
759 return __p ? iterator(__p, _M_buckets + __n) : this->end();
762 template<typename _Key, typename _Value,
763 typename _Allocator, typename _ExtractKey, typename _Equal,
764 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
765 bool __chc, bool __cit, bool __uk>
766 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
767 _H1, _H2, _Hash, _RehashPolicy,
768 __chc, __cit, __uk>::const_iterator
769 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
770 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
771 find(const key_type& __k) const
773 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
774 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
775 _Node* __p = _M_find_node(_M_buckets[__n], __k, __code);
776 return __p ? const_iterator(__p, _M_buckets + __n) : this->end();
779 template<typename _Key, typename _Value,
780 typename _Allocator, typename _ExtractKey, typename _Equal,
781 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
782 bool __chc, bool __cit, bool __uk>
783 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
784 _H1, _H2, _Hash, _RehashPolicy,
785 __chc, __cit, __uk>::size_type
786 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
787 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
788 count(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 std::size_t __result = 0;
793 for (_Node* __p = _M_buckets[__n]; __p; __p = __p->_M_next)
794 if (this->_M_compare(__k, __code, __p))
799 template<typename _Key, typename _Value,
800 typename _Allocator, typename _ExtractKey, typename _Equal,
801 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
802 bool __chc, bool __cit, bool __uk>
803 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
804 _ExtractKey, _Equal, _H1,
805 _H2, _Hash, _RehashPolicy,
806 __chc, __cit, __uk>::iterator,
807 typename _Hashtable<_Key, _Value, _Allocator,
808 _ExtractKey, _Equal, _H1,
809 _H2, _Hash, _RehashPolicy,
810 __chc, __cit, __uk>::iterator>
811 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
812 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
813 equal_range(const key_type& __k)
815 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
816 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
817 _Node** __head = _M_buckets + __n;
818 _Node* __p = _M_find_node(*__head, __k, __code);
822 _Node* __p1 = __p->_M_next;
823 for (; __p1; __p1 = __p1->_M_next)
824 if (!this->_M_compare(__k, __code, __p1))
827 iterator __first(__p, __head);
828 iterator __last(__p1, __head);
830 __last._M_incr_bucket();
831 return std::make_pair(__first, __last);
834 return std::make_pair(this->end(), this->end());
837 template<typename _Key, typename _Value,
838 typename _Allocator, typename _ExtractKey, typename _Equal,
839 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
840 bool __chc, bool __cit, bool __uk>
841 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
842 _ExtractKey, _Equal, _H1,
843 _H2, _Hash, _RehashPolicy,
844 __chc, __cit, __uk>::const_iterator,
845 typename _Hashtable<_Key, _Value, _Allocator,
846 _ExtractKey, _Equal, _H1,
847 _H2, _Hash, _RehashPolicy,
848 __chc, __cit, __uk>::const_iterator>
849 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
850 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
851 equal_range(const key_type& __k) const
853 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
854 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
855 _Node** __head = _M_buckets + __n;
856 _Node* __p = _M_find_node(*__head, __k, __code);
860 _Node* __p1 = __p->_M_next;
861 for (; __p1; __p1 = __p1->_M_next)
862 if (!this->_M_compare(__k, __code, __p1))
865 const_iterator __first(__p, __head);
866 const_iterator __last(__p1, __head);
868 __last._M_incr_bucket();
869 return std::make_pair(__first, __last);
872 return std::make_pair(this->end(), this->end());
875 // Find the node whose key compares equal to k, beginning the search
876 // at p (usually the head of a bucket). Return nullptr if no node is found.
877 template<typename _Key, typename _Value,
878 typename _Allocator, typename _ExtractKey, typename _Equal,
879 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
880 bool __chc, bool __cit, bool __uk>
881 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey,
882 _Equal, _H1, _H2, _Hash, _RehashPolicy,
883 __chc, __cit, __uk>::_Node*
884 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
885 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
886 _M_find_node(_Node* __p, const key_type& __k,
887 typename _Hashtable::_Hash_code_type __code) const
889 for (; __p; __p = __p->_M_next)
890 if (this->_M_compare(__k, __code, __p))
895 // Insert v in bucket n (assumes no element with its key already present).
896 template<typename _Key, typename _Value,
897 typename _Allocator, typename _ExtractKey, typename _Equal,
898 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
899 bool __chc, bool __cit, bool __uk>
900 template<typename _Arg>
901 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
902 _H1, _H2, _Hash, _RehashPolicy,
903 __chc, __cit, __uk>::iterator
904 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
905 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
906 _M_insert_bucket(_Arg&& __v, size_type __n,
907 typename _Hashtable::_Hash_code_type __code)
909 const size_type __saved_next_resize = _M_rehash_policy._M_next_resize;
910 std::pair<bool, std::size_t> __do_rehash
911 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
912 _M_element_count, 1);
914 if (__do_rehash.first)
916 const key_type& __k = this->_M_extract(__v);
917 __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
920 _Node* __new_node = 0;
923 // Allocate the new node before doing the rehash so that we
924 // don't do a rehash if the allocation throws.
925 __new_node = _M_allocate_node(std::forward<_Arg>(__v));
926 if (__do_rehash.first)
927 _M_rehash(__do_rehash.second, __saved_next_resize);
929 __new_node->_M_next = _M_buckets[__n];
930 this->_M_store_code(__new_node, __code);
931 _M_buckets[__n] = __new_node;
933 if (__n < _M_begin_bucket_index)
934 _M_begin_bucket_index = __n;
935 return iterator(__new_node, _M_buckets + __n);
940 _M_rehash_policy._M_next_resize = __saved_next_resize;
942 _M_deallocate_node(__new_node);
943 __throw_exception_again;
947 // Insert v if no element with its key is already present.
948 template<typename _Key, typename _Value,
949 typename _Allocator, typename _ExtractKey, typename _Equal,
950 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
951 bool __chc, bool __cit, bool __uk>
952 template<typename _Arg>
953 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
954 _ExtractKey, _Equal, _H1,
955 _H2, _Hash, _RehashPolicy,
956 __chc, __cit, __uk>::iterator, bool>
957 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
958 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
959 _M_insert(_Arg&& __v, std::true_type)
961 const key_type& __k = this->_M_extract(__v);
962 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
963 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
965 if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code))
966 return std::make_pair(iterator(__p, _M_buckets + __n), false);
967 return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v),
971 // Insert v unconditionally.
972 template<typename _Key, typename _Value,
973 typename _Allocator, typename _ExtractKey, typename _Equal,
974 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
975 bool __chc, bool __cit, bool __uk>
976 template<typename _Arg>
977 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
978 _H1, _H2, _Hash, _RehashPolicy,
979 __chc, __cit, __uk>::iterator
980 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
981 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
982 _M_insert(_Arg&& __v, std::false_type)
984 const size_type __saved_next_resize = _M_rehash_policy._M_next_resize;
985 std::pair<bool, std::size_t> __do_rehash
986 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
987 _M_element_count, 1);
988 if (__do_rehash.first)
989 _M_rehash(__do_rehash.second, __saved_next_resize);
991 const key_type& __k = this->_M_extract(__v);
992 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
993 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
995 // First find the node, avoid leaking new_node if compare throws.
996 _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code);
997 _Node* __new_node = _M_allocate_node(std::forward<_Arg>(__v));
1001 __new_node->_M_next = __prev->_M_next;
1002 __prev->_M_next = __new_node;
1006 __new_node->_M_next = _M_buckets[__n];
1007 _M_buckets[__n] = __new_node;
1008 if (__n < _M_begin_bucket_index)
1009 _M_begin_bucket_index = __n;
1011 this->_M_store_code(__new_node, __code);
1014 return iterator(__new_node, _M_buckets + __n);
1017 template<typename _Key, typename _Value,
1018 typename _Allocator, typename _ExtractKey, typename _Equal,
1019 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1020 bool __chc, bool __cit, bool __uk>
1021 template<typename _InputIterator>
1023 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1024 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1025 insert(_InputIterator __first, _InputIterator __last)
1027 size_type __n_elt = __detail::__distance_fw(__first, __last);
1028 const size_type __saved_next_resize = _M_rehash_policy._M_next_resize;
1029 std::pair<bool, std::size_t> __do_rehash
1030 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1031 _M_element_count, __n_elt);
1032 if (__do_rehash.first)
1033 _M_rehash(__do_rehash.second, __saved_next_resize);
1035 for (; __first != __last; ++__first)
1036 this->insert(*__first);
1039 template<typename _Key, typename _Value,
1040 typename _Allocator, typename _ExtractKey, typename _Equal,
1041 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1042 bool __chc, bool __cit, bool __uk>
1043 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1044 _H1, _H2, _Hash, _RehashPolicy,
1045 __chc, __cit, __uk>::iterator
1046 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1047 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1048 erase(const_iterator __it)
1050 iterator __result(__it._M_cur_node, __it._M_cur_bucket);
1053 _Node* __cur = *__it._M_cur_bucket;
1054 if (__cur == __it._M_cur_node)
1056 *__it._M_cur_bucket = __cur->_M_next;
1058 // If _M_begin_bucket_index no longer indexes the first non-empty
1059 // bucket - its single node is being erased - update it.
1060 if (!_M_buckets[_M_begin_bucket_index])
1061 _M_begin_bucket_index = __result._M_cur_bucket - _M_buckets;
1065 _Node* __next = __cur->_M_next;
1066 while (__next != __it._M_cur_node)
1069 __next = __cur->_M_next;
1071 __cur->_M_next = __next->_M_next;
1074 _M_deallocate_node(__it._M_cur_node);
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>::size_type
1087 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1088 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1089 erase(const key_type& __k)
1091 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1092 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
1093 size_type __result = 0;
1095 _Node** __slot = _M_buckets + __n;
1096 while (*__slot && !this->_M_compare(__k, __code, *__slot))
1097 __slot = &((*__slot)->_M_next);
1099 _Node** __saved_slot = 0;
1100 while (*__slot && this->_M_compare(__k, __code, *__slot))
1102 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1103 // 526. Is it undefined if a function in the standard changes
1105 if (std::__addressof(this->_M_extract((*__slot)->_M_v))
1106 != std::__addressof(__k))
1108 _Node* __p = *__slot;
1109 *__slot = __p->_M_next;
1110 _M_deallocate_node(__p);
1116 __saved_slot = __slot;
1117 __slot = &((*__slot)->_M_next);
1123 _Node* __p = *__saved_slot;
1124 *__saved_slot = __p->_M_next;
1125 _M_deallocate_node(__p);
1130 // If the entire bucket indexed by _M_begin_bucket_index has been
1131 // erased look forward for the first non-empty bucket.
1132 if (!_M_buckets[_M_begin_bucket_index])
1134 if (!_M_element_count)
1135 _M_begin_bucket_index = _M_bucket_count;
1138 ++_M_begin_bucket_index;
1139 while (!_M_buckets[_M_begin_bucket_index])
1140 ++_M_begin_bucket_index;
1147 // ??? This could be optimized by taking advantage of the bucket
1148 // structure, but it's not clear that it's worth doing. It probably
1149 // wouldn't even be an optimization unless the load factor is large.
1150 template<typename _Key, typename _Value,
1151 typename _Allocator, typename _ExtractKey, typename _Equal,
1152 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1153 bool __chc, bool __cit, bool __uk>
1154 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1155 _H1, _H2, _Hash, _RehashPolicy,
1156 __chc, __cit, __uk>::iterator
1157 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1158 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1159 erase(const_iterator __first, const_iterator __last)
1161 while (__first != __last)
1162 __first = this->erase(__first);
1163 return iterator(__last._M_cur_node, __last._M_cur_bucket);
1166 template<typename _Key, typename _Value,
1167 typename _Allocator, typename _ExtractKey, typename _Equal,
1168 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1169 bool __chc, bool __cit, bool __uk>
1171 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1172 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1175 _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1176 _M_element_count = 0;
1177 _M_begin_bucket_index = _M_bucket_count;
1180 template<typename _Key, typename _Value,
1181 typename _Allocator, typename _ExtractKey, typename _Equal,
1182 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1183 bool __chc, bool __cit, bool __uk>
1185 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1186 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1187 rehash(size_type __n)
1189 const size_type __saved_next_resize = _M_rehash_policy._M_next_resize;
1190 _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
1191 _M_rehash_policy._M_bkt_for_elements(_M_element_count
1193 __saved_next_resize);
1196 template<typename _Key, typename _Value,
1197 typename _Allocator, typename _ExtractKey, typename _Equal,
1198 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1199 bool __chc, bool __cit, bool __uk>
1201 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1202 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1203 _M_rehash(size_type __n, size_type __next_resize)
1205 _Node** __new_array = 0;
1208 __new_array = _M_allocate_buckets(__n);
1209 _M_begin_bucket_index = __n;
1210 for (size_type __i = 0; __i < _M_bucket_count; ++__i)
1211 while (_Node* __p = _M_buckets[__i])
1213 std::size_t __new_index = this->_M_bucket_index(__p, __n);
1214 _M_buckets[__i] = __p->_M_next;
1215 __p->_M_next = __new_array[__new_index];
1216 __new_array[__new_index] = __p;
1217 if (__new_index < _M_begin_bucket_index)
1218 _M_begin_bucket_index = __new_index;
1220 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1221 _M_bucket_count = __n;
1222 _M_buckets = __new_array;
1228 // A failure here means that a hash function threw an exception.
1229 // We can't restore the previous state without calling the hash
1230 // function again, so the only sensible recovery is to delete
1232 _M_deallocate_nodes(__new_array, __n);
1233 _M_deallocate_buckets(__new_array, __n);
1234 _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1235 _M_element_count = 0;
1236 _M_begin_bucket_index = _M_bucket_count;
1237 _M_rehash_policy._M_next_resize = 0;
1240 // A failure here means that buckets allocation failed. We only
1241 // have to restore hash policy previous state.
1242 _M_rehash_policy._M_next_resize = __next_resize;
1243 __throw_exception_again;
1247 _GLIBCXX_END_NAMESPACE_VERSION
1250 #endif // _HASHTABLE_H