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 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, restore hash policy
460 // resize value to __next_resize on exception.
461 void _M_rehash(size_type __n, size_type __next_resize);
465 // Definitions of class template _Hashtable's out-of-line member functions.
466 template<typename _Key, typename _Value,
467 typename _Allocator, typename _ExtractKey, typename _Equal,
468 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
469 bool __chc, bool __cit, bool __uk>
470 template<typename... _Args>
471 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
472 _H1, _H2, _Hash, _RehashPolicy,
473 __chc, __cit, __uk>::_Node*
474 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
475 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
476 _M_allocate_node(_Args&&... __args)
478 _Node* __n = _M_node_allocator.allocate(1);
481 _M_node_allocator.construct(__n, std::forward<_Args>(__args)...);
487 _M_node_allocator.deallocate(__n, 1);
488 __throw_exception_again;
492 template<typename _Key, typename _Value,
493 typename _Allocator, typename _ExtractKey, typename _Equal,
494 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
495 bool __chc, bool __cit, bool __uk>
497 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
498 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
499 _M_deallocate_node(_Node* __n)
501 _M_node_allocator.destroy(__n);
502 _M_node_allocator.deallocate(__n, 1);
505 template<typename _Key, typename _Value,
506 typename _Allocator, typename _ExtractKey, typename _Equal,
507 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
508 bool __chc, bool __cit, bool __uk>
510 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
511 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
512 _M_deallocate_nodes(_Node** __array, size_type __n)
514 for (size_type __i = 0; __i < __n; ++__i)
516 _Node* __p = __array[__i];
521 _M_deallocate_node(__tmp);
527 template<typename _Key, typename _Value,
528 typename _Allocator, typename _ExtractKey, typename _Equal,
529 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
530 bool __chc, bool __cit, bool __uk>
531 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
532 _H1, _H2, _Hash, _RehashPolicy,
533 __chc, __cit, __uk>::_Node**
534 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
535 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
536 _M_allocate_buckets(size_type __n)
538 _Bucket_allocator_type __alloc(_M_node_allocator);
540 // We allocate one extra bucket to hold a sentinel, an arbitrary
541 // non-null pointer. Iterator increment relies on this.
542 _Node** __p = __alloc.allocate(__n + 1);
543 std::fill(__p, __p + __n, (_Node*) 0);
544 __p[__n] = reinterpret_cast<_Node*>(0x1000);
548 template<typename _Key, typename _Value,
549 typename _Allocator, typename _ExtractKey, typename _Equal,
550 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
551 bool __chc, bool __cit, bool __uk>
553 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
554 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
555 _M_deallocate_buckets(_Node** __p, size_type __n)
557 _Bucket_allocator_type __alloc(_M_node_allocator);
558 __alloc.deallocate(__p, __n + 1);
561 template<typename _Key, typename _Value,
562 typename _Allocator, typename _ExtractKey, typename _Equal,
563 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
564 bool __chc, bool __cit, bool __uk>
565 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
566 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
567 _Hashtable(size_type __bucket_hint,
568 const _H1& __h1, const _H2& __h2, const _Hash& __h,
569 const _Equal& __eq, const _ExtractKey& __exk,
570 const allocator_type& __a)
571 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
572 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
573 _H1, _H2, _Hash, __chc>(__exk, __eq,
575 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
576 _M_node_allocator(__a),
581 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
582 _M_buckets = _M_allocate_buckets(_M_bucket_count);
583 _M_begin_bucket_index = _M_bucket_count;
586 template<typename _Key, typename _Value,
587 typename _Allocator, typename _ExtractKey, typename _Equal,
588 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
589 bool __chc, bool __cit, bool __uk>
590 template<typename _InputIterator>
591 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
592 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
593 _Hashtable(_InputIterator __f, _InputIterator __l,
594 size_type __bucket_hint,
595 const _H1& __h1, const _H2& __h2, const _Hash& __h,
596 const _Equal& __eq, const _ExtractKey& __exk,
597 const allocator_type& __a)
598 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(),
599 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
600 _H1, _H2, _Hash, __chc>(__exk, __eq,
602 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(),
603 _M_node_allocator(__a),
608 _M_bucket_count = std::max(_M_rehash_policy._M_next_bkt(__bucket_hint),
610 _M_bkt_for_elements(__detail::
613 _M_buckets = _M_allocate_buckets(_M_bucket_count);
614 _M_begin_bucket_index = _M_bucket_count;
617 for (; __f != __l; ++__f)
623 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
624 __throw_exception_again;
628 template<typename _Key, typename _Value,
629 typename _Allocator, typename _ExtractKey, typename _Equal,
630 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
631 bool __chc, bool __cit, bool __uk>
632 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
633 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
634 _Hashtable(const _Hashtable& __ht)
635 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
636 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
637 _H1, _H2, _Hash, __chc>(__ht),
638 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
639 _M_node_allocator(__ht._M_node_allocator),
640 _M_bucket_count(__ht._M_bucket_count),
641 _M_begin_bucket_index(__ht._M_begin_bucket_index),
642 _M_element_count(__ht._M_element_count),
643 _M_rehash_policy(__ht._M_rehash_policy)
645 _M_buckets = _M_allocate_buckets(_M_bucket_count);
648 for (size_type __i = 0; __i < __ht._M_bucket_count; ++__i)
650 _Node* __n = __ht._M_buckets[__i];
651 _Node** __tail = _M_buckets + __i;
654 *__tail = _M_allocate_node(__n->_M_v);
655 this->_M_copy_code(*__tail, __n);
656 __tail = &((*__tail)->_M_next);
664 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
665 __throw_exception_again;
669 template<typename _Key, typename _Value,
670 typename _Allocator, typename _ExtractKey, typename _Equal,
671 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
672 bool __chc, bool __cit, bool __uk>
673 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
674 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
675 _Hashtable(_Hashtable&& __ht)
676 : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(__ht),
677 __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal,
678 _H1, _H2, _Hash, __chc>(__ht),
679 __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(__ht),
680 _M_node_allocator(std::move(__ht._M_node_allocator)),
681 _M_buckets(__ht._M_buckets),
682 _M_bucket_count(__ht._M_bucket_count),
683 _M_begin_bucket_index(__ht._M_begin_bucket_index),
684 _M_element_count(__ht._M_element_count),
685 _M_rehash_policy(__ht._M_rehash_policy)
687 __ht._M_rehash_policy = _RehashPolicy();
688 __ht._M_bucket_count = __ht._M_rehash_policy._M_next_bkt(0);
689 __ht._M_buckets = __ht._M_allocate_buckets(__ht._M_bucket_count);
690 __ht._M_begin_bucket_index = __ht._M_bucket_count;
691 __ht._M_element_count = 0;
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>::
700 ~_Hashtable() noexcept
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 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
743 if (__n_bkt > _M_bucket_count)
744 _M_rehash(__n_bkt, _M_rehash_policy._M_next_resize);
745 _M_rehash_policy = __pol;
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 const size_type __saved_next_resize = _M_rehash_policy._M_next_resize;
913 std::pair<bool, std::size_t> __do_rehash
914 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
915 _M_element_count, 1);
917 if (__do_rehash.first)
919 const key_type& __k = this->_M_extract(__v);
920 __n = this->_M_bucket_index(__k, __code, __do_rehash.second);
923 _Node* __new_node = 0;
926 // Allocate the new node before doing the rehash so that we
927 // don't do a rehash if the allocation throws.
928 __new_node = _M_allocate_node(std::forward<_Arg>(__v));
929 if (__do_rehash.first)
930 _M_rehash(__do_rehash.second, __saved_next_resize);
932 __new_node->_M_next = _M_buckets[__n];
933 this->_M_store_code(__new_node, __code);
934 _M_buckets[__n] = __new_node;
936 if (__n < _M_begin_bucket_index)
937 _M_begin_bucket_index = __n;
938 return iterator(__new_node, _M_buckets + __n);
943 _M_rehash_policy._M_next_resize = __saved_next_resize;
945 _M_deallocate_node(__new_node);
946 __throw_exception_again;
950 // Insert v if no element with its key is already present.
951 template<typename _Key, typename _Value,
952 typename _Allocator, typename _ExtractKey, typename _Equal,
953 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
954 bool __chc, bool __cit, bool __uk>
955 template<typename _Arg>
956 std::pair<typename _Hashtable<_Key, _Value, _Allocator,
957 _ExtractKey, _Equal, _H1,
958 _H2, _Hash, _RehashPolicy,
959 __chc, __cit, __uk>::iterator, bool>
960 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
961 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
962 _M_insert(_Arg&& __v, std::true_type)
964 const key_type& __k = this->_M_extract(__v);
965 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
966 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
968 if (_Node* __p = _M_find_node(_M_buckets[__n], __k, __code))
969 return std::make_pair(iterator(__p, _M_buckets + __n), false);
970 return std::make_pair(_M_insert_bucket(std::forward<_Arg>(__v),
974 // Insert v unconditionally.
975 template<typename _Key, typename _Value,
976 typename _Allocator, typename _ExtractKey, typename _Equal,
977 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
978 bool __chc, bool __cit, bool __uk>
979 template<typename _Arg>
980 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
981 _H1, _H2, _Hash, _RehashPolicy,
982 __chc, __cit, __uk>::iterator
983 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
984 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
985 _M_insert(_Arg&& __v, std::false_type)
987 const size_type __saved_next_resize = _M_rehash_policy._M_next_resize;
988 std::pair<bool, std::size_t> __do_rehash
989 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
990 _M_element_count, 1);
991 if (__do_rehash.first)
992 _M_rehash(__do_rehash.second, __saved_next_resize);
994 const key_type& __k = this->_M_extract(__v);
995 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
996 size_type __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
998 // First find the node, avoid leaking new_node if compare throws.
999 _Node* __prev = _M_find_node(_M_buckets[__n], __k, __code);
1000 _Node* __new_node = _M_allocate_node(std::forward<_Arg>(__v));
1004 __new_node->_M_next = __prev->_M_next;
1005 __prev->_M_next = __new_node;
1009 __new_node->_M_next = _M_buckets[__n];
1010 _M_buckets[__n] = __new_node;
1011 if (__n < _M_begin_bucket_index)
1012 _M_begin_bucket_index = __n;
1014 this->_M_store_code(__new_node, __code);
1017 return iterator(__new_node, _M_buckets + __n);
1020 template<typename _Key, typename _Value,
1021 typename _Allocator, typename _ExtractKey, typename _Equal,
1022 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1023 bool __chc, bool __cit, bool __uk>
1024 template<typename _InputIterator>
1026 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1027 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1028 insert(_InputIterator __first, _InputIterator __last)
1030 size_type __n_elt = __detail::__distance_fw(__first, __last);
1031 const size_type __saved_next_resize = _M_rehash_policy._M_next_resize;
1032 std::pair<bool, std::size_t> __do_rehash
1033 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
1034 _M_element_count, __n_elt);
1035 if (__do_rehash.first)
1036 _M_rehash(__do_rehash.second, __saved_next_resize);
1038 for (; __first != __last; ++__first)
1039 this->insert(*__first);
1042 template<typename _Key, typename _Value,
1043 typename _Allocator, typename _ExtractKey, typename _Equal,
1044 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1045 bool __chc, bool __cit, bool __uk>
1046 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1047 _H1, _H2, _Hash, _RehashPolicy,
1048 __chc, __cit, __uk>::iterator
1049 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1050 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1051 erase(const_iterator __it)
1053 iterator __result(__it._M_cur_node, __it._M_cur_bucket);
1056 _Node* __cur = *__it._M_cur_bucket;
1057 if (__cur == __it._M_cur_node)
1059 *__it._M_cur_bucket = __cur->_M_next;
1061 // If _M_begin_bucket_index no longer indexes the first non-empty
1062 // bucket - its single node is being erased - update it.
1063 if (!_M_buckets[_M_begin_bucket_index])
1064 _M_begin_bucket_index = __result._M_cur_bucket - _M_buckets;
1068 _Node* __next = __cur->_M_next;
1069 while (__next != __it._M_cur_node)
1072 __next = __cur->_M_next;
1074 __cur->_M_next = __next->_M_next;
1077 _M_deallocate_node(__it._M_cur_node);
1083 template<typename _Key, typename _Value,
1084 typename _Allocator, typename _ExtractKey, typename _Equal,
1085 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1086 bool __chc, bool __cit, bool __uk>
1087 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1088 _H1, _H2, _Hash, _RehashPolicy,
1089 __chc, __cit, __uk>::size_type
1090 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1091 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1092 erase(const key_type& __k)
1094 typename _Hashtable::_Hash_code_type __code = this->_M_hash_code(__k);
1095 std::size_t __n = this->_M_bucket_index(__k, __code, _M_bucket_count);
1096 size_type __result = 0;
1098 _Node** __slot = _M_buckets + __n;
1099 while (*__slot && !this->_M_compare(__k, __code, *__slot))
1100 __slot = &((*__slot)->_M_next);
1102 _Node** __saved_slot = 0;
1103 while (*__slot && this->_M_compare(__k, __code, *__slot))
1105 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1106 // 526. Is it undefined if a function in the standard changes
1108 if (std::__addressof(this->_M_extract((*__slot)->_M_v))
1109 != std::__addressof(__k))
1111 _Node* __p = *__slot;
1112 *__slot = __p->_M_next;
1113 _M_deallocate_node(__p);
1119 __saved_slot = __slot;
1120 __slot = &((*__slot)->_M_next);
1126 _Node* __p = *__saved_slot;
1127 *__saved_slot = __p->_M_next;
1128 _M_deallocate_node(__p);
1133 // If the entire bucket indexed by _M_begin_bucket_index has been
1134 // erased look forward for the first non-empty bucket.
1135 if (!_M_buckets[_M_begin_bucket_index])
1137 if (!_M_element_count)
1138 _M_begin_bucket_index = _M_bucket_count;
1141 ++_M_begin_bucket_index;
1142 while (!_M_buckets[_M_begin_bucket_index])
1143 ++_M_begin_bucket_index;
1150 // ??? This could be optimized by taking advantage of the bucket
1151 // structure, but it's not clear that it's worth doing. It probably
1152 // wouldn't even be an optimization unless the load factor is large.
1153 template<typename _Key, typename _Value,
1154 typename _Allocator, typename _ExtractKey, typename _Equal,
1155 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1156 bool __chc, bool __cit, bool __uk>
1157 typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1158 _H1, _H2, _Hash, _RehashPolicy,
1159 __chc, __cit, __uk>::iterator
1160 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1161 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1162 erase(const_iterator __first, const_iterator __last)
1164 while (__first != __last)
1165 __first = this->erase(__first);
1166 return iterator(__last._M_cur_node, __last._M_cur_bucket);
1169 template<typename _Key, typename _Value,
1170 typename _Allocator, typename _ExtractKey, typename _Equal,
1171 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1172 bool __chc, bool __cit, bool __uk>
1174 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1175 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1178 _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1179 _M_element_count = 0;
1180 _M_begin_bucket_index = _M_bucket_count;
1183 template<typename _Key, typename _Value,
1184 typename _Allocator, typename _ExtractKey, typename _Equal,
1185 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1186 bool __chc, bool __cit, bool __uk>
1188 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1189 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1190 rehash(size_type __n)
1192 const size_type __saved_next_resize = _M_rehash_policy._M_next_resize;
1193 _M_rehash(std::max(_M_rehash_policy._M_next_bkt(__n),
1194 _M_rehash_policy._M_bkt_for_elements(_M_element_count
1196 __saved_next_resize);
1199 template<typename _Key, typename _Value,
1200 typename _Allocator, typename _ExtractKey, typename _Equal,
1201 typename _H1, typename _H2, typename _Hash, typename _RehashPolicy,
1202 bool __chc, bool __cit, bool __uk>
1204 _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal,
1205 _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::
1206 _M_rehash(size_type __n, size_type __next_resize)
1208 _Node** __new_array = 0;
1211 __new_array = _M_allocate_buckets(__n);
1212 _M_begin_bucket_index = __n;
1213 for (size_type __i = 0; __i < _M_bucket_count; ++__i)
1214 while (_Node* __p = _M_buckets[__i])
1216 std::size_t __new_index = this->_M_bucket_index(__p, __n);
1217 _M_buckets[__i] = __p->_M_next;
1218 __p->_M_next = __new_array[__new_index];
1219 __new_array[__new_index] = __p;
1220 if (__new_index < _M_begin_bucket_index)
1221 _M_begin_bucket_index = __new_index;
1223 _M_deallocate_buckets(_M_buckets, _M_bucket_count);
1224 _M_bucket_count = __n;
1225 _M_buckets = __new_array;
1231 // A failure here means that a hash function threw an exception.
1232 // We can't restore the previous state without calling the hash
1233 // function again, so the only sensible recovery is to delete
1235 _M_deallocate_nodes(__new_array, __n);
1236 _M_deallocate_buckets(__new_array, __n);
1237 _M_deallocate_nodes(_M_buckets, _M_bucket_count);
1238 _M_element_count = 0;
1239 _M_begin_bucket_index = _M_bucket_count;
1240 _M_rehash_policy._M_next_resize = 0;
1243 // A failure here means that buckets allocation failed. We only
1244 // have to restore hash policy previous state.
1245 _M_rehash_policy._M_next_resize = __next_resize;
1246 __throw_exception_again;
1250 _GLIBCXX_END_NAMESPACE_VERSION
1253 #endif // _HASHTABLE_H