1 // Internal header for TR1 unordered_set and unordered_map -*- C++ -*-
3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
31 * This is a TR1 C++ Library header.
34 // This header file defines std::tr1::hashtable, which is used to
35 // implement std::tr1::unordered_set, std::tr1::unordered_map,
36 // std::tr1::unordered_multiset, and std::tr1::unordered_multimap.
37 // hashtable has many template parameters, partly to accommodate
38 // the differences between those four classes and partly to
39 // accommodate policy choices that go beyond what TR1 calls for.
41 // Class template hashtable attempts to encapsulate all reasonable
42 // variation among hash tables that use chaining. It does not handle
46 // M. Austern, "A Proposal to Add Hash Tables to the Standard
47 // Library (revision 4)," WG21 Document N1456=03-0039, 2003.
48 // D. E. Knuth, The Art of Computer Programming, v. 3, Sorting and Searching.
49 // A. Tavori and V. Dreizin, "Policy-Based Data Structures", 2004.
50 // http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html
52 #ifndef _TR1_HASHTABLE
53 #define _TR1_HASHTABLE 1
55 #include <utility> // For std::pair
61 #include <bits/functexcept.h>
62 #include <tr1/type_traits> // For true_type and false_type
63 #include <tr1/hashtable_policy.h>
67 _GLIBCXX_BEGIN_NAMESPACE(tr1)
69 // Class template hashtable, class definition.
71 // Meaning of class template hashtable's template parameters
73 // Key and Value: arbitrary CopyConstructible types.
75 // Allocator: an allocator type ([lib.allocator.requirements]) whose
76 // value type is Value.
78 // ExtractKey: function object that takes a object of type Value
79 // and returns a value of type Key.
81 // Equal: function object that takes two objects of type k and returns
82 // a bool-like value that is true if the two objects are considered equal.
84 // H1: the hash function. A unary function object with argument type
85 // Key and result type size_t. Return values should be distributed
86 // over the entire range [0, numeric_limits<size_t>:::max()].
88 // H2: the range-hashing function (in the terminology of Tavori and
89 // Dreizin). A binary function object whose argument types and result
90 // type are all size_t. Given arguments r and N, the return value is
91 // in the range [0, N).
93 // H: the ranged hash function (Tavori and Dreizin). A binary function
94 // whose argument types are Key and size_t and whose result type is
95 // size_t. Given arguments k and N, the return value is in the range
96 // [0, N). Default: h(k, N) = h2(h1(k), N). If H is anything other
97 // than the default, H1 and H2 are ignored.
99 // RehashPolicy: Policy class with three members, all of which govern
100 // the bucket count. n_bkt(n) returns a bucket count no smaller
101 // than n. bkt_for_elements(n) returns a bucket count appropriate
102 // for an element count of n. need_rehash(n_bkt, n_elt, n_ins)
103 // determines whether, if the current bucket count is n_bkt and the
104 // current element count is n_elt, we need to increase the bucket
105 // count. If so, returns make_pair(true, n), where n is the new
106 // bucket count. If not, returns make_pair(false, <anything>).
108 // ??? Right now it is hard-wired that the number of buckets never
109 // shrinks. Should we allow RehashPolicy to change that?
111 // cache_hash_code: bool. true if we store the value of the hash
112 // function along with the value. This is a time-space tradeoff.
113 // Storing it may improve lookup speed by reducing the number of times
114 // we need to call the Equal function.
116 // constant_iterators: bool. true if iterator and const_iterator are
117 // both constant iterator types. This is true for unordered_set and
118 // unordered_multiset, false for unordered_map and unordered_multimap.
120 // unique_keys: bool. true if the return value of hashtable::count(k)
121 // is always at most one, false if it may be an arbitrary number. This
122 // true for unordered_set and unordered_map, false for unordered_multiset
123 // and unordered_multimap.
125 template<typename Key, typename Value, typename Allocator,
126 typename ExtractKey, typename Equal,
127 typename H1, typename H2, typename H,
128 typename RehashPolicy,
129 bool cache_hash_code,
130 bool constant_iterators,
133 : public detail::rehash_base<RehashPolicy,
134 hashtable<Key, Value, Allocator, ExtractKey,
135 Equal, H1, H2, H, RehashPolicy,
136 cache_hash_code, constant_iterators,
138 public detail::hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H,
140 public detail::map_base<Key, Value, ExtractKey, unique_keys,
141 hashtable<Key, Value, Allocator, ExtractKey,
142 Equal, H1, H2, H, RehashPolicy,
143 cache_hash_code, constant_iterators,
147 typedef Allocator allocator_type;
148 typedef Value value_type;
149 typedef Key key_type;
150 typedef Equal key_equal;
151 // mapped_type, if present, comes from map_base.
152 // hasher, if present, comes from hash_code_base.
153 typedef typename Allocator::difference_type difference_type;
154 typedef typename Allocator::size_type size_type;
155 typedef typename Allocator::reference reference;
156 typedef typename Allocator::const_reference const_reference;
158 typedef detail::node_iterator<value_type, constant_iterators,
161 typedef detail::node_const_iterator<value_type, constant_iterators,
163 const_local_iterator;
165 typedef detail::hashtable_iterator<value_type, constant_iterators,
168 typedef detail::hashtable_const_iterator<value_type, constant_iterators,
172 template<typename K, typename Pair, typename Hashtable>
173 friend struct detail::map_base;
176 typedef detail::hash_node<Value, cache_hash_code> node;
177 typedef typename Allocator::template rebind<node>::other
179 typedef typename Allocator::template rebind<node*>::other
182 node_allocator_t m_node_allocator;
184 size_type m_bucket_count;
185 size_type m_element_count;
186 RehashPolicy m_rehash_policy;
189 m_allocate_node(const value_type& v);
192 m_deallocate_node(node* n);
195 m_deallocate_nodes(node**, size_type);
198 m_allocate_buckets(size_type n);
201 m_deallocate_buckets(node**, size_type n);
204 // Constructor, destructor, assignment, swap
205 hashtable(size_type bucket_hint,
206 const H1&, const H2&, const H&,
207 const Equal&, const ExtractKey&,
208 const allocator_type&);
210 template<typename InIter>
211 hashtable(InIter first, InIter last,
212 size_type bucket_hint,
213 const H1&, const H2&, const H&,
214 const Equal&, const ExtractKey&,
215 const allocator_type&);
217 hashtable(const hashtable&);
220 operator=(const hashtable&);
224 void swap(hashtable&);
226 // Basic container operations
230 iterator i(m_buckets);
239 const_iterator i(m_buckets);
247 { return iterator(m_buckets + m_bucket_count); }
251 { return const_iterator(m_buckets + m_bucket_count); }
255 { return m_element_count; }
259 { return size() == 0; }
262 get_allocator() const
263 { return m_node_allocator; }
267 { return m_node_allocator.max_size(); }
272 { return this->m_eq; }
274 // hash_function, if present, comes from hash_code_base.
279 { return m_bucket_count; }
282 max_bucket_count() const
283 { return max_size(); }
286 bucket_size(size_type n) const
287 { return std::distance(begin(n), end(n)); }
290 bucket(const key_type& k) const
292 return this->bucket_index(k, this->m_hash_code(k),
293 this->m_bucket_count);
298 { return local_iterator(m_buckets[n]); }
302 { return local_iterator(0); }
305 begin(size_type n) const
306 { return const_local_iterator(m_buckets[n]); }
310 { return const_local_iterator(0); }
315 return static_cast<float>(size()) / static_cast<float>(bucket_count());
318 // max_load_factor, if present, comes from rehash_base.
320 // Generalization of max_load_factor. Extension, not found in TR1. Only
321 // useful if RehashPolicy is something other than the default.
323 rehash_policy() const
324 { return m_rehash_policy; }
327 rehash_policy(const RehashPolicy&);
331 find(const key_type& k);
334 find(const key_type& k) const;
337 count(const key_type& k) const;
339 std::pair<iterator, iterator>
340 equal_range(const key_type& k);
342 std::pair<const_iterator, const_iterator>
343 equal_range(const key_type& k) const;
345 private: // Find, insert and erase helper functions
346 // ??? This dispatching is a workaround for the fact that we don't
347 // have partial specialization of member templates; it would be
348 // better to just specialize insert on unique_keys. There may be a
349 // cleaner workaround.
350 typedef typename detail::IF<unique_keys,
351 std::pair<iterator, bool>, iterator>::type
354 typedef typename detail::IF<unique_keys,
355 detail::extract1st<Insert_Return_Type>,
356 detail::identity<Insert_Return_Type>
361 m_find_node(node*, const key_type&,
362 typename hashtable::hash_code_t) const;
365 m_insert_bucket(const value_type&, size_type,
366 typename hashtable::hash_code_t);
368 std::pair<iterator, bool>
369 m_insert(const value_type&, std::tr1::true_type);
372 m_insert(const value_type&, std::tr1::false_type);
375 m_erase_node(node*, node**);
380 insert(const value_type& v)
381 { return m_insert(v, std::tr1::integral_constant<bool, unique_keys>()); }
384 insert(iterator, const value_type& v)
385 { return iterator(Insert_Conv_Type()(this->insert(v))); }
388 insert(const_iterator, const value_type& v)
389 { return const_iterator(Insert_Conv_Type()(this->insert(v))); }
391 template<typename InIter>
393 insert(InIter first, InIter last);
399 erase(const_iterator);
402 erase(const key_type&);
405 erase(iterator, iterator);
408 erase(const_iterator, const_iterator);
413 // Set number of buckets to be appropriate for container of n element.
414 void rehash(size_type n);
417 // Unconditionally change size of bucket array to n.
418 void m_rehash(size_type n);
422 // Definitions of class template hashtable's out-of-line member functions.
423 template<typename K, typename V,
424 typename A, typename Ex, typename Eq,
425 typename H1, typename H2, typename H, typename RP,
426 bool c, bool ci, bool u>
427 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node*
428 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
429 m_allocate_node(const value_type& v)
431 node* n = m_node_allocator.allocate(1);
434 get_allocator().construct(&n->m_v, v);
440 m_node_allocator.deallocate(n, 1);
441 __throw_exception_again;
445 template<typename K, typename V,
446 typename A, typename Ex, typename Eq,
447 typename H1, typename H2, typename H, typename RP,
448 bool c, bool ci, bool u>
450 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
451 m_deallocate_node(node* n)
453 get_allocator().destroy(&n->m_v);
454 m_node_allocator.deallocate(n, 1);
457 template<typename K, typename V,
458 typename A, typename Ex, typename Eq,
459 typename H1, typename H2, typename H, typename RP,
460 bool c, bool ci, bool u>
462 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
463 m_deallocate_nodes(node** array, size_type n)
465 for (size_type i = 0; i < n; ++i)
472 m_deallocate_node(tmp);
478 template<typename K, typename V,
479 typename A, typename Ex, typename Eq,
480 typename H1, typename H2, typename H, typename RP,
481 bool c, bool ci, bool u>
482 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node**
483 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
484 m_allocate_buckets(size_type n)
486 bucket_allocator_t alloc(m_node_allocator);
488 // We allocate one extra bucket to hold a sentinel, an arbitrary
489 // non-null pointer. Iterator increment relies on this.
490 node** p = alloc.allocate(n + 1);
491 std::fill(p, p + n, (node*) 0);
492 p[n] = reinterpret_cast<node*>(0x1000);
496 template<typename K, typename V,
497 typename A, typename Ex, typename Eq,
498 typename H1, typename H2, typename H, typename RP,
499 bool c, bool ci, bool u>
501 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
502 m_deallocate_buckets(node** p, size_type n)
504 bucket_allocator_t alloc(m_node_allocator);
505 alloc.deallocate(p, n + 1);
508 template<typename K, typename V,
509 typename A, typename Ex, typename Eq,
510 typename H1, typename H2, typename H, typename RP,
511 bool c, bool ci, bool u>
512 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
513 hashtable(size_type bucket_hint,
514 const H1& h1, const H2& h2, const H& h,
515 const Eq& eq, const Ex& exk,
516 const allocator_type& a)
517 : detail::rehash_base<RP, hashtable>(),
518 detail::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq, h1, h2, h),
519 detail::map_base<K, V, Ex, u, hashtable>(),
525 m_bucket_count = m_rehash_policy.next_bkt(bucket_hint);
526 m_buckets = m_allocate_buckets(m_bucket_count);
529 template<typename K, typename V,
530 typename A, typename Ex, typename Eq,
531 typename H1, typename H2, typename H, typename RP,
532 bool c, bool ci, bool u>
533 template<typename InIter>
534 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
535 hashtable(InIter f, InIter l,
536 size_type bucket_hint,
537 const H1& h1, const H2& h2, const H& h,
538 const Eq& eq, const Ex& exk,
539 const allocator_type& a)
540 : detail::rehash_base<RP, hashtable>(),
541 detail::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq,
543 detail::map_base<K, V, Ex, u, hashtable>(),
549 m_bucket_count = std::max(m_rehash_policy.next_bkt(bucket_hint),
551 bkt_for_elements(detail::
553 m_buckets = m_allocate_buckets(m_bucket_count);
562 m_deallocate_buckets(m_buckets, m_bucket_count);
563 __throw_exception_again;
567 template<typename K, typename V,
568 typename A, typename Ex, typename Eq,
569 typename H1, typename H2, typename H, typename RP,
570 bool c, bool ci, bool u>
571 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
572 hashtable(const hashtable& ht)
573 : detail::rehash_base<RP, hashtable>(ht),
574 detail::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(ht),
575 detail::map_base<K, V, Ex, u, hashtable>(ht),
576 m_node_allocator(ht.get_allocator()),
577 m_bucket_count(ht.m_bucket_count),
578 m_element_count(ht.m_element_count),
579 m_rehash_policy(ht.m_rehash_policy)
581 m_buckets = m_allocate_buckets(m_bucket_count);
584 for (size_type i = 0; i < ht.m_bucket_count; ++i)
586 node* n = ht.m_buckets[i];
587 node** tail = m_buckets + i;
590 *tail = m_allocate_node(n->m_v);
591 this->copy_code(*tail, n);
592 tail = &((*tail)->m_next);
600 m_deallocate_buckets(m_buckets, m_bucket_count);
601 __throw_exception_again;
605 template<typename K, typename V,
606 typename A, typename Ex, typename Eq,
607 typename H1, typename H2, typename H, typename RP,
608 bool c, bool ci, bool u>
609 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>&
610 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
611 operator=(const hashtable& ht)
618 template<typename K, typename V,
619 typename A, typename Ex, typename Eq,
620 typename H1, typename H2, typename H, typename RP,
621 bool c, bool ci, bool u>
622 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
626 m_deallocate_buckets(m_buckets, m_bucket_count);
629 template<typename K, typename V,
630 typename A, typename Ex, typename Eq,
631 typename H1, typename H2, typename H, typename RP,
632 bool c, bool ci, bool u>
634 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
637 // The only base class with member variables is hash_code_base. We
638 // define hash_code_base::m_swap because different specializations
639 // have different members.
640 detail::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>::m_swap(x);
642 // _GLIBCXX_RESOLVE_LIB_DEFECTS
643 // 431. Swapping containers with unequal allocators.
644 std::__alloc_swap<node_allocator_t>::_S_do_it(m_node_allocator,
647 std::swap(m_rehash_policy, x.m_rehash_policy);
648 std::swap(m_buckets, x.m_buckets);
649 std::swap(m_bucket_count, x.m_bucket_count);
650 std::swap(m_element_count, x.m_element_count);
653 template<typename K, typename V,
654 typename A, typename Ex, typename Eq,
655 typename H1, typename H2, typename H, typename RP,
656 bool c, bool ci, bool u>
658 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
659 rehash_policy(const RP& pol)
661 m_rehash_policy = pol;
662 size_type n_bkt = pol.bkt_for_elements(m_element_count);
663 if (n_bkt > m_bucket_count)
667 template<typename K, typename V,
668 typename A, typename Ex, typename Eq,
669 typename H1, typename H2, typename H, typename RP,
670 bool c, bool ci, bool u>
671 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
672 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
673 find(const key_type& k)
675 typename hashtable::hash_code_t code = this->m_hash_code(k);
676 std::size_t n = this->bucket_index(k, code, this->bucket_count());
677 node* p = m_find_node(m_buckets[n], k, code);
678 return p ? iterator(p, m_buckets + n) : this->end();
681 template<typename K, typename V,
682 typename A, typename Ex, typename Eq,
683 typename H1, typename H2, typename H, typename RP,
684 bool c, bool ci, bool u>
685 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
686 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
687 find(const key_type& k) const
689 typename hashtable::hash_code_t code = this->m_hash_code(k);
690 std::size_t n = this->bucket_index(k, code, this->bucket_count());
691 node* p = m_find_node(m_buckets[n], k, code);
692 return p ? const_iterator(p, m_buckets + n) : this->end();
695 template<typename K, typename V,
696 typename A, typename Ex, typename Eq,
697 typename H1, typename H2, typename H, typename RP,
698 bool c, bool ci, bool u>
699 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::size_type
700 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
701 count(const key_type& k) const
703 typename hashtable::hash_code_t code = this->m_hash_code(k);
704 std::size_t n = this->bucket_index(k, code, this->bucket_count());
705 std::size_t result = 0;
706 for (node* p = m_buckets[n]; p; p = p->m_next)
707 if (this->compare(k, code, p))
712 template<typename K, typename V,
713 typename A, typename Ex, typename Eq,
714 typename H1, typename H2, typename H, typename RP,
715 bool c, bool ci, bool u>
716 std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
717 H2, H, RP, c, ci, u>::iterator,
718 typename hashtable<K, V, A, Ex, Eq, H1,
719 H2, H, RP, c, ci, u>::iterator>
720 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
721 equal_range(const key_type& k)
723 typename hashtable::hash_code_t code = this->m_hash_code(k);
724 std::size_t n = this->bucket_index(k, code, this->bucket_count());
725 node** head = m_buckets + n;
726 node* p = m_find_node(*head, k, code);
730 node* p1 = p->m_next;
731 for (; p1; p1 = p1->m_next)
732 if (!this->compare(k, code, p1))
735 iterator first(p, head);
736 iterator last(p1, head);
738 last.m_incr_bucket();
739 return std::make_pair(first, last);
742 return std::make_pair(this->end(), this->end());
745 template<typename K, typename V,
746 typename A, typename Ex, typename Eq,
747 typename H1, typename H2, typename H, typename RP,
748 bool c, bool ci, bool u>
749 std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
750 H2, H, RP, c, ci, u>::const_iterator,
751 typename hashtable<K, V, A, Ex, Eq, H1,
752 H2, H, RP, c, ci, u>::const_iterator>
753 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
754 equal_range(const key_type& k) const
756 typename hashtable::hash_code_t code = this->m_hash_code(k);
757 std::size_t n = this->bucket_index(k, code, this->bucket_count());
758 node** head = m_buckets + n;
759 node* p = m_find_node(*head, k, code);
763 node* p1 = p->m_next;
764 for (; p1; p1 = p1->m_next)
765 if (!this->compare(k, code, p1))
768 const_iterator first(p, head);
769 const_iterator last(p1, head);
771 last.m_incr_bucket();
772 return std::make_pair(first, last);
775 return std::make_pair(this->end(), this->end());
778 // Find the node whose key compares equal to k, beginning the search
779 // at p (usually the head of a bucket). Return nil if no node is found.
780 template<typename K, typename V,
781 typename A, typename Ex, typename Eq,
782 typename H1, typename H2, typename H, typename RP,
783 bool c, bool ci, bool u>
784 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node*
785 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
786 m_find_node(node* p, const key_type& k,
787 typename hashtable::hash_code_t code) const
789 for (; p; p = p->m_next)
790 if (this->compare(k, code, p))
795 // Insert v in bucket n (assumes no element with its key already present).
796 template<typename K, typename V,
797 typename A, typename Ex, typename Eq,
798 typename H1, typename H2, typename H, typename RP,
799 bool c, bool ci, bool u>
800 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
801 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
802 m_insert_bucket(const value_type& v, size_type n,
803 typename hashtable::hash_code_t code)
805 std::pair<bool, std::size_t> do_rehash
806 = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);
808 // Allocate the new node before doing the rehash so that we don't
809 // do a rehash if the allocation throws.
810 node* new_node = m_allocate_node(v);
816 const key_type& k = this->m_extract(v);
817 n = this->bucket_index(k, code, do_rehash.second);
818 m_rehash(do_rehash.second);
821 new_node->m_next = m_buckets[n];
822 this->store_code(new_node, code);
823 m_buckets[n] = new_node;
825 return iterator(new_node, m_buckets + n);
829 m_deallocate_node(new_node);
830 __throw_exception_again;
834 // Insert v if no element with its key is already present.
835 template<typename K, typename V,
836 typename A, typename Ex, typename Eq,
837 typename H1, typename H2, typename H, typename RP,
838 bool c, bool ci, bool u>
839 std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
840 H2, H, RP, c, ci, u>::iterator, bool>
841 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
842 m_insert(const value_type& v, std::tr1::true_type)
844 const key_type& k = this->m_extract(v);
845 typename hashtable::hash_code_t code = this->m_hash_code(k);
846 size_type n = this->bucket_index(k, code, m_bucket_count);
848 if (node* p = m_find_node(m_buckets[n], k, code))
849 return std::make_pair(iterator(p, m_buckets + n), false);
850 return std::make_pair(m_insert_bucket(v, n, code), true);
853 // Insert v unconditionally.
854 template<typename K, typename V,
855 typename A, typename Ex, typename Eq,
856 typename H1, typename H2, typename H, typename RP,
857 bool c, bool ci, bool u>
858 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
859 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
860 m_insert(const value_type& v, std::tr1::false_type)
862 std::pair<bool, std::size_t> do_rehash
863 = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);
865 m_rehash(do_rehash.second);
867 const key_type& k = this->m_extract(v);
868 typename hashtable::hash_code_t code = this->m_hash_code(k);
869 size_type n = this->bucket_index(k, code, m_bucket_count);
871 // First find the node, avoid leaking new_node if compare throws.
872 node* prev = m_find_node(m_buckets[n], k, code);
873 node* new_node = m_allocate_node(v);
877 new_node->m_next = prev->m_next;
878 prev->m_next = new_node;
882 new_node->m_next = m_buckets[n];
883 m_buckets[n] = new_node;
885 this->store_code(new_node, code);
888 return iterator(new_node, m_buckets + n);
891 // For erase(iterator) and erase(const_iterator).
892 template<typename K, typename V,
893 typename A, typename Ex, typename Eq,
894 typename H1, typename H2, typename H, typename RP,
895 bool c, bool ci, bool u>
897 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
898 m_erase_node(node* p, node** b)
905 node* next = cur->m_next;
911 cur->m_next = next->m_next;
914 m_deallocate_node(p);
918 template<typename K, typename V,
919 typename A, typename Ex, typename Eq,
920 typename H1, typename H2, typename H, typename RP,
921 bool c, bool ci, bool u>
922 template<typename InIter>
924 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
925 insert(InIter first, InIter last)
927 size_type n_elt = detail::distance_fw(first, last);
928 std::pair<bool, std::size_t> do_rehash
929 = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, n_elt);
931 m_rehash(do_rehash.second);
933 for (; first != last; ++first)
934 this->insert(*first);
937 template<typename K, typename V,
938 typename A, typename Ex, typename Eq,
939 typename H1, typename H2, typename H, typename RP,
940 bool c, bool ci, bool u>
941 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
942 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
945 iterator result = it;
947 m_erase_node(it.m_cur_node, it.m_cur_bucket);
951 template<typename K, typename V,
952 typename A, typename Ex, typename Eq,
953 typename H1, typename H2, typename H, typename RP,
954 bool c, bool ci, bool u>
955 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
956 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
957 erase(const_iterator it)
959 const_iterator result = it;
961 m_erase_node(it.m_cur_node, it.m_cur_bucket);
965 template<typename K, typename V,
966 typename A, typename Ex, typename Eq,
967 typename H1, typename H2, typename H, typename RP,
968 bool c, bool ci, bool u>
969 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::size_type
970 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
971 erase(const key_type& k)
973 typename hashtable::hash_code_t code = this->m_hash_code(k);
974 std::size_t n = this->bucket_index(k, code, m_bucket_count);
975 size_type result = 0;
977 node** slot = m_buckets + n;
978 while (*slot && !this->compare(k, code, *slot))
979 slot = &((*slot)->m_next);
981 while (*slot && this->compare(k, code, *slot))
985 m_deallocate_node(p);
993 // ??? This could be optimized by taking advantage of the bucket
994 // structure, but it's not clear that it's worth doing. It probably
995 // wouldn't even be an optimization unless the load factor is large.
996 template<typename K, typename V,
997 typename A, typename Ex, typename Eq,
998 typename H1, typename H2, typename H, typename RP,
999 bool c, bool ci, bool u>
1000 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
1001 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1002 erase(iterator first, iterator last)
1004 while (first != last)
1005 first = this->erase(first);
1009 template<typename K, typename V,
1010 typename A, typename Ex, typename Eq,
1011 typename H1, typename H2, typename H, typename RP,
1012 bool c, bool ci, bool u>
1013 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
1014 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1015 erase(const_iterator first, const_iterator last)
1017 while (first != last)
1018 first = this->erase(first);
1022 template<typename K, typename V,
1023 typename A, typename Ex, typename Eq,
1024 typename H1, typename H2, typename H, typename RP,
1025 bool c, bool ci, bool u>
1027 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1030 m_deallocate_nodes(m_buckets, m_bucket_count);
1031 m_element_count = 0;
1034 template<typename K, typename V,
1035 typename A, typename Ex, typename Eq,
1036 typename H1, typename H2, typename H, typename RP,
1037 bool c, bool ci, bool u>
1039 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1042 m_rehash(std::max(m_rehash_policy.next_bkt(n),
1043 m_rehash_policy.bkt_for_elements(m_element_count
1047 template<typename K, typename V,
1048 typename A, typename Ex, typename Eq,
1049 typename H1, typename H2, typename H, typename RP,
1050 bool c, bool ci, bool u>
1052 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1053 m_rehash(size_type n)
1055 node** new_array = m_allocate_buckets(n);
1058 for (size_type i = 0; i < m_bucket_count; ++i)
1059 while (node* p = m_buckets[i])
1061 std::size_t new_index = this->bucket_index(p, n);
1062 m_buckets[i] = p->m_next;
1063 p->m_next = new_array[new_index];
1064 new_array[new_index] = p;
1066 m_deallocate_buckets(m_buckets, m_bucket_count);
1068 m_buckets = new_array;
1072 // A failure here means that a hash function threw an exception.
1073 // We can't restore the previous state without calling the hash
1074 // function again, so the only sensible recovery is to delete
1076 m_deallocate_nodes(new_array, n);
1077 m_deallocate_buckets(new_array, n);
1078 m_deallocate_nodes(m_buckets, m_bucket_count);
1079 m_element_count = 0;
1080 __throw_exception_again;
1084 _GLIBCXX_END_NAMESPACE
1085 } // namespace std::tr1
1087 #endif // _TR1_HASHTABLE