1 // Internal header for TR1 unordered_set and unordered_map -*- C++ -*-
3 // Copyright (C) 2005 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 // ??? Arguably this should be Internal::hashtable, not std::tr1::hashtable.
43 // Class template hashtable attempts to encapsulate all reasonable
44 // variation among hash tables that use chaining. It does not handle
48 // M. Austern, "A Proposal to Add Hash Tables to the Standard
49 // Library (revision 4)," WG21 Document N1456=03-0039, 2003.
50 // D. E. Knuth, The Art of Computer Programming, v. 3, Sorting and Searching.
51 // A. Tavori and V. Dreizin, "Generic Associative Containers", 2004.
54 #ifndef GNU_LIBSTDCXX_TR1_HASHTABLE_
55 #define GNU_LIBSTDCXX_TR1_HASHTABLE_
57 #include <utility> // For std::pair
62 #include <bits/functexcept.h>
63 #include <tr1/type_traits> // For true_type and false_type
65 //----------------------------------------------------------------------
70 template<bool Flag, typename IfTrue, typename IfFalse>
73 template<typename IfTrue, typename IfFalse>
74 struct IF<true, IfTrue, IfFalse>
75 { typedef IfTrue type; };
77 template <typename IfTrue, typename IfFalse>
78 struct IF<false, IfTrue, IfFalse>
79 { typedef IfFalse type; };
81 // Helper function: return distance(first, last) for forward
82 // iterators, or 0 for input iterators.
83 template<class Iterator>
84 inline typename std::iterator_traits<Iterator>::difference_type
85 distance_fw(Iterator first, Iterator last, std::input_iterator_tag)
88 template<class Iterator>
89 inline typename std::iterator_traits<Iterator>::difference_type
90 distance_fw(Iterator first, Iterator last, std::forward_iterator_tag)
91 { return std::distance(first, last); }
93 template<class Iterator>
94 inline typename std::iterator_traits<Iterator>::difference_type
95 distance_fw(Iterator first, Iterator last)
97 typedef typename std::iterator_traits<Iterator>::iterator_category tag;
98 return distance_fw(first, last, tag());
101 } // namespace Internal
103 //----------------------------------------------------------------------
104 // Auxiliary types used for all instantiations of hashtable: nodes
107 // Nodes, used to wrap elements stored in the hash table. A policy
108 // template parameter of class template hashtable controls whether
109 // nodes also store a hash code. In some cases (e.g. strings) this may
110 // be a performance win.
114 template<typename Value, bool cache_hash_code>
117 template<typename Value>
118 struct hash_node<Value, true>
121 std::size_t hash_code;
125 template<typename Value>
126 struct hash_node<Value, false>
132 // Local iterators, used to iterate within a bucket but not between
135 template<typename Value, bool cache>
136 struct node_iterator_base
138 node_iterator_base(hash_node<Value, cache>* p)
143 { m_cur = m_cur->m_next; }
145 hash_node<Value, cache>* m_cur;
148 template<typename Value, bool cache>
150 operator==(const node_iterator_base<Value, cache>& x,
151 const node_iterator_base<Value, cache>& y)
152 { return x.m_cur == y.m_cur; }
154 template<typename Value, bool cache>
156 operator!=(const node_iterator_base<Value, cache>& x,
157 const node_iterator_base<Value, cache>& y)
158 { return x.m_cur != y.m_cur; }
160 template<typename Value, bool constant_iterators, bool cache>
162 : public node_iterator_base<Value, cache>
164 typedef Value value_type;
165 typedef typename IF<constant_iterators, const Value*, Value*>::type
167 typedef typename IF<constant_iterators, const Value&, Value&>::type
169 typedef std::ptrdiff_t difference_type;
170 typedef std::forward_iterator_tag iterator_category;
173 node_iterator(hash_node<Value, cache>* p = 0)
174 : node_iterator_base<Value, cache>(p) { }
178 { return this->m_cur->m_v; }
182 { return &this->m_cur->m_v; }
194 node_iterator tmp(*this);
200 template<typename Value, bool constant_iterators, bool cache>
201 struct node_const_iterator
202 : public node_iterator_base<Value, cache>
204 typedef Value value_type;
205 typedef const Value* pointer;
206 typedef const Value& reference;
207 typedef std::ptrdiff_t difference_type;
208 typedef std::forward_iterator_tag iterator_category;
211 node_const_iterator(hash_node<Value, cache>* p = 0)
212 : node_iterator_base<Value, cache>(p) { }
214 node_const_iterator(const node_iterator<Value, constant_iterators,
216 : node_iterator_base<Value, cache>(x.m_cur) { }
220 { return this->m_cur->m_v; }
224 { return &this->m_cur->m_v; }
236 node_const_iterator tmp(*this);
242 template<typename Value, bool cache>
243 struct hashtable_iterator_base
245 hashtable_iterator_base(hash_node<Value, cache>* node,
246 hash_node<Value, cache>** bucket)
247 : m_cur_node(node), m_cur_bucket(bucket)
253 m_cur_node = m_cur_node->m_next;
261 hash_node<Value, cache>* m_cur_node;
262 hash_node<Value, cache>** m_cur_bucket;
265 // Global iterators, used for arbitrary iteration within a hash
266 // table. Larger and more expensive than local iterators.
267 template<typename Value, bool cache>
269 hashtable_iterator_base<Value, cache>::
274 // This loop requires the bucket array to have a non-null sentinel.
275 while (!*m_cur_bucket)
277 m_cur_node = *m_cur_bucket;
280 template<typename Value, bool cache>
282 operator==(const hashtable_iterator_base<Value, cache>& x,
283 const hashtable_iterator_base<Value, cache>& y)
284 { return x.m_cur_node == y.m_cur_node; }
286 template<typename Value, bool cache>
288 operator!=(const hashtable_iterator_base<Value, cache>& x,
289 const hashtable_iterator_base<Value, cache>& y)
290 { return x.m_cur_node != y.m_cur_node; }
292 template<typename Value, bool constant_iterators, bool cache>
293 struct hashtable_iterator
294 : public hashtable_iterator_base<Value, cache>
296 typedef Value value_type;
297 typedef typename IF<constant_iterators, const Value*, Value*>::type
299 typedef typename IF<constant_iterators, const Value&, Value&>::type
301 typedef std::ptrdiff_t difference_type;
302 typedef std::forward_iterator_tag iterator_category;
304 hashtable_iterator(hash_node<Value, cache>* p,
305 hash_node<Value, cache>** b)
306 : hashtable_iterator_base<Value, cache>(p, b) { }
309 hashtable_iterator(hash_node<Value, cache>** b)
310 : hashtable_iterator_base<Value, cache>(*b, b) { }
314 { return this->m_cur_node->m_v; }
318 { return &this->m_cur_node->m_v; }
330 hashtable_iterator tmp(*this);
336 template<typename Value, bool constant_iterators, bool cache>
337 struct hashtable_const_iterator
338 : public hashtable_iterator_base<Value, cache>
340 typedef Value value_type;
341 typedef const Value* pointer;
342 typedef const Value& reference;
343 typedef std::ptrdiff_t difference_type;
344 typedef std::forward_iterator_tag iterator_category;
346 hashtable_const_iterator(hash_node<Value, cache>* p,
347 hash_node<Value, cache>** b)
348 : hashtable_iterator_base<Value, cache>(p, b) { }
351 hashtable_const_iterator(hash_node<Value, cache>** b)
352 : hashtable_iterator_base<Value, cache>(*b, b) { }
354 hashtable_const_iterator(const hashtable_iterator<Value,
355 constant_iterators, cache>& x)
356 : hashtable_iterator_base<Value, cache>(x.m_cur_node, x.m_cur_bucket) { }
360 { return this->m_cur_node->m_v; }
364 { return &this->m_cur_node->m_v; }
366 hashtable_const_iterator&
373 hashtable_const_iterator
376 hashtable_const_iterator tmp(*this);
381 } // namespace Internal
383 // ----------------------------------------------------------------------
384 // Many of class template hashtable's template parameters are policy
385 // classes. These are defaults for the policies.
389 // The two key extraction policies used by the *set and *map variants.
394 operator()(const T& t) const
398 template<typename Pair>
401 typename Pair::first_type
402 operator()(const Pair& p) const
406 // Default range hashing function: use division to fold a large number
407 // into the range [0, N).
408 struct mod_range_hashing
410 typedef std::size_t first_argument_type;
411 typedef std::size_t second_argument_type;
412 typedef std::size_t result_type;
415 operator() (first_argument_type r, second_argument_type N) const
419 // Default ranged hash function H. In principle it should be a
420 // function object composed from objects of type H1 and H2 such that
421 // h(k, N) = h2(h1(k), N), but that would mean making extra copies of
422 // h1 and h2. So instead we'll just use a tag to tell class template
423 // hashtable to do that composition.
424 struct default_ranged_hash { };
426 // Default value for rehash policy. Bucket size is (usually) the
427 // smallest prime that keeps the load factor small enough.
428 struct prime_rehash_policy
430 prime_rehash_policy(float z = 1.0);
433 max_load_factor() const;
435 // Return a bucket size no smaller than n.
437 next_bkt(std::size_t n) const;
439 // Return a bucket count appropriate for n elements
441 bkt_for_elements(std::size_t n) const;
443 // n_bkt is current bucket count, n_elt is current element count,
444 // and n_ins is number of elements to be inserted. Do we need to
445 // increase bucket count? If so, return make_pair(true, n), where n
446 // is the new bucket count. If not, return make_pair(false, 0).
447 std::pair<bool, std::size_t>
448 need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const;
450 float m_max_load_factor;
451 float m_growth_factor;
452 mutable std::size_t m_next_resize;
455 // XXX This is a hack. prime_rehash_policy's member functions, and
456 // certainly the list of primes, should be defined in a .cc file.
457 // We're temporarily putting them in a header because we don't have a
458 // place to put TR1 .cc files yet. There's no good reason for any of
459 // prime_rehash_policy's member functions to be inline, and there's
460 // certainly no good reason for X<> to exist at all.
464 template<typename X, typename Y>
473 static const int n_primes = 256;
474 static const unsigned long primes[n_primes + 1];
478 const int X<dummy>::n_primes;
481 const unsigned long X<dummy>::primes[n_primes + 1] =
483 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
484 37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul,
485 83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul,
486 157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul,
487 277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul,
488 503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul,
489 953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul,
490 1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul,
491 3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul,
492 5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul,
493 11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul,
494 19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul,
495 33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul,
496 57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul,
497 99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul,
498 159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul,
499 256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul,
500 410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul,
501 658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul,
502 1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul,
503 1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul,
504 2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul,
505 4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul,
506 6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul,
507 11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul,
508 16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul,
509 24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul,
510 36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul,
511 54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul,
512 80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul,
513 118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul,
514 176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul,
515 260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul,
516 386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul,
517 573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul,
518 849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul,
519 1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul,
520 1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul,
521 2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul,
522 3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul,
524 4294967291ul // sentinel so we don't have to test result of lower_bound
528 prime_rehash_policy::
529 prime_rehash_policy(float z)
530 : m_max_load_factor(z), m_growth_factor(2.f), m_next_resize(0)
534 prime_rehash_policy::
535 max_load_factor() const
536 { return m_max_load_factor; }
538 // Return a prime no smaller than n.
540 prime_rehash_policy::
541 next_bkt(std::size_t n) const
543 const unsigned long* const last = X<0>::primes + X<0>::n_primes;
544 const unsigned long* p = std::lower_bound (X<0>::primes, last, n);
545 m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
549 // Return the smallest prime p such that alpha p >= n, where alpha
550 // is the load factor.
552 prime_rehash_policy::
553 bkt_for_elements(std::size_t n) const
555 const unsigned long* const last = X<0>::primes + X<0>::n_primes;
556 const float min_bkts = n / m_max_load_factor;
557 const unsigned long* p = std::lower_bound (X<0>::primes, last,
559 m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
563 // Finds the smallest prime p such that alpha p > n_elt + n_ins.
564 // If p > n_bkt, return make_pair(true, p); otherwise return
565 // make_pair(false, 0). In principle this isn't very different from
568 // The only tricky part is that we're caching the element count at
569 // which we need to rehash, so we don't have to do a floating-point
570 // multiply for every insertion.
572 inline std::pair<bool, std::size_t>
573 prime_rehash_policy::
574 need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const
576 if (n_elt + n_ins > m_next_resize)
578 float min_bkts = (float(n_ins) + float(n_elt)) / m_max_load_factor;
579 if (min_bkts > n_bkt)
581 min_bkts = std::max (min_bkts, m_growth_factor * n_bkt);
582 const unsigned long* const last = X<0>::primes + X<0>::n_primes;
583 const unsigned long* p = std::lower_bound (X<0>::primes, last,
586 static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
587 return std::make_pair(true, *p);
592 static_cast<std::size_t>(std::ceil(n_bkt * m_max_load_factor));
593 return std::make_pair(false, 0);
597 return std::make_pair(false, 0);
600 } // namespace Internal
602 //----------------------------------------------------------------------
603 // Base classes for std::tr1::hashtable. We define these base classes
604 // because in some cases we want to do different things depending on
605 // the value of a policy class. In some cases the policy class affects
606 // which member functions and nested typedefs are defined; we handle that
607 // by specializing base class templates. Several of the base class templates
608 // need to access other members of class template hashtable, so we use
609 // the "curiously recurring template pattern" for them.
613 // class template map_base. If the hashtable has a value type of the
614 // form pair<T1, T2> and a key extraction policy that returns the
615 // first part of the pair, the hashtable gets a mapped_type typedef.
616 // If it satisfies those criteria and also has unique keys, then it
617 // also gets an operator[].
619 template<typename K, typename V, typename Ex, bool unique, typename Hashtable>
622 template<typename K, typename Pair, typename Hashtable>
623 struct map_base<K, Pair, extract1st<Pair>, false, Hashtable>
625 typedef typename Pair::second_type mapped_type;
628 template<typename K, typename Pair, typename Hashtable>
629 struct map_base<K, Pair, extract1st<Pair>, true, Hashtable>
631 typedef typename Pair::second_type mapped_type;
634 operator[](const K& k)
636 Hashtable* h = static_cast<Hashtable*>(this);
637 typename Hashtable::iterator it =
638 h->insert(std::make_pair(k, mapped_type())).first;
643 // class template rehash_base. Give hashtable the max_load_factor
644 // functions iff the rehash policy is prime_rehash_policy.
645 template<typename RehashPolicy, typename Hashtable>
646 struct rehash_base { };
648 template<typename Hashtable>
649 struct rehash_base<prime_rehash_policy, Hashtable>
652 max_load_factor() const
654 const Hashtable* This = static_cast<const Hashtable*>(this);
655 return This->rehash_policy()->max_load_factor();
659 max_load_factor(float z)
661 Hashtable* This = static_cast<Hashtable*>(this);
662 This->rehash_policy(prime_rehash_policy(z));
666 // Class template hash_code_base. Encapsulates two policy issues that
667 // aren't quite orthogonal.
668 // (1) the difference between using a ranged hash function and using
669 // the combination of a hash function and a range-hashing function.
670 // In the former case we don't have such things as hash codes, so
671 // we have a dummy type as placeholder.
672 // (2) Whether or not we cache hash codes. Caching hash codes is
673 // meaningless if we have a ranged hash function.
674 // We also put the key extraction and equality comparison function
675 // objects here, for convenience.
677 // Primary template: unused except as a hook for specializations.
679 template<typename Key, typename Value,
680 typename ExtractKey, typename Equal,
681 typename H1, typename H2, typename H,
682 bool cache_hash_code>
683 struct hash_code_base;
685 // Specialization: ranged hash function, no caching hash codes. H1
686 // and H2 are provided but ignored. We define a dummy hash code type.
687 template<typename Key, typename Value,
688 typename ExtractKey, typename Equal,
689 typename H1, typename H2, typename H>
690 struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, false>
693 hash_code_base(const ExtractKey& ex, const Equal& eq,
694 const H1&, const H2&, const H& h)
695 : m_extract(ex), m_eq(eq), m_ranged_hash(h) { }
697 typedef void* hash_code_t;
700 m_hash_code(const Key& k) const
704 bucket_index(const Key& k, hash_code_t, std::size_t N) const
705 { return m_ranged_hash (k, N); }
708 bucket_index(const hash_node<Value, false>* p, std::size_t N) const
709 { return m_ranged_hash (m_extract (p->m_v), N); }
712 compare(const Key& k, hash_code_t, hash_node<Value, false>* n) const
713 { return m_eq (k, m_extract(n->m_v)); }
716 store_code(hash_node<Value, false>*, hash_code_t) const
720 copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const
724 m_swap(hash_code_base& x)
726 std::swap(m_extract, x.m_extract);
727 std::swap(m_eq, x.m_eq);
728 std::swap(m_ranged_hash, x.m_ranged_hash);
732 ExtractKey m_extract;
738 // No specialization for ranged hash function while caching hash codes.
739 // That combination is meaningless, and trying to do it is an error.
742 // Specialization: ranged hash function, cache hash codes. This
743 // combination is meaningless, so we provide only a declaration
744 // and no definition.
746 template<typename Key, typename Value,
747 typename ExtractKey, typename Equal,
748 typename H1, typename H2, typename H>
749 struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, true>;
752 // Specialization: hash function and range-hashing function, no
753 // caching of hash codes. H is provided but ignored. Provides
754 // typedef and accessor required by TR1.
756 template<typename Key, typename Value,
757 typename ExtractKey, typename Equal,
758 typename H1, typename H2>
759 struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2,
760 default_ranged_hash, false>
765 hash_function() const
769 hash_code_base(const ExtractKey& ex, const Equal& eq,
770 const H1& h1, const H2& h2, const default_ranged_hash&)
771 : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { }
773 typedef std::size_t hash_code_t;
776 m_hash_code(const Key& k) const
780 bucket_index(const Key&, hash_code_t c, std::size_t N) const
781 { return m_h2 (c, N); }
784 bucket_index(const hash_node<Value, false>* p, std::size_t N) const
785 { return m_h2 (m_h1 (m_extract (p->m_v)), N); }
788 compare(const Key& k, hash_code_t, hash_node<Value, false>* n) const
789 { return m_eq (k, m_extract(n->m_v)); }
792 store_code(hash_node<Value, false>*, hash_code_t) const
796 copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const
800 m_swap(hash_code_base& x)
802 std::swap(m_extract, x.m_extract);
803 std::swap(m_eq, x.m_eq);
804 std::swap(m_h1, x.m_h1);
805 std::swap(m_h2, x.m_h2);
809 ExtractKey m_extract;
815 // Specialization: hash function and range-hashing function,
816 // caching hash codes. H is provided but ignored. Provides
817 // typedef and accessor required by TR1.
818 template<typename Key, typename Value,
819 typename ExtractKey, typename Equal,
820 typename H1, typename H2>
821 struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2,
822 default_ranged_hash, true>
827 hash_function() const
831 hash_code_base(const ExtractKey& ex, const Equal& eq,
832 const H1& h1, const H2& h2, const default_ranged_hash&)
833 : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { }
835 typedef std::size_t hash_code_t;
838 m_hash_code (const Key& k) const
842 bucket_index(const Key&, hash_code_t c, std::size_t N) const
843 { return m_h2 (c, N); }
846 bucket_index(const hash_node<Value, true>* p, std::size_t N) const
847 { return m_h2 (p->hash_code, N); }
850 compare(const Key& k, hash_code_t c, hash_node<Value, true>* n) const
851 { return c == n->hash_code && m_eq(k, m_extract(n->m_v)); }
854 store_code(hash_node<Value, true>* n, hash_code_t c) const
855 { n->hash_code = c; }
858 copy_code(hash_node<Value, true>* to,
859 const hash_node<Value, true>* from) const
860 { to->hash_code = from->hash_code; }
863 m_swap(hash_code_base& x)
865 std::swap(m_extract, x.m_extract);
866 std::swap(m_eq, x.m_eq);
867 std::swap(m_h1, x.m_h1);
868 std::swap(m_h2, x.m_h2);
872 ExtractKey m_extract;
878 } // namespace internal
882 _GLIBCXX_BEGIN_NAMESPACE(tr1)
884 //----------------------------------------------------------------------
885 // Class template hashtable, class definition.
887 // Meaning of class template hashtable's template parameters
889 // Key and Value: arbitrary CopyConstructible types.
891 // Allocator: an allocator type ([lib.allocator.requirements]) whose
892 // value type is Value.
894 // ExtractKey: function object that takes a object of type Value
895 // and returns a value of type Key.
897 // Equal: function object that takes two objects of type k and returns
898 // a bool-like value that is true if the two objects are considered equal.
900 // H1: the hash function. A unary function object with argument type
901 // Key and result type size_t. Return values should be distributed
902 // over the entire range [0, numeric_limits<size_t>:::max()].
904 // H2: the range-hashing function (in the terminology of Tavori and
905 // Dreizin). A binary function object whose argument types and result
906 // type are all size_t. Given arguments r and N, the return value is
907 // in the range [0, N).
909 // H: the ranged hash function (Tavori and Dreizin). A binary function
910 // whose argument types are Key and size_t and whose result type is
911 // size_t. Given arguments k and N, the return value is in the range
912 // [0, N). Default: h(k, N) = h2(h1(k), N). If H is anything other
913 // than the default, H1 and H2 are ignored.
915 // RehashPolicy: Policy class with three members, all of which govern
916 // the bucket count. n_bkt(n) returns a bucket count no smaller
917 // than n. bkt_for_elements(n) returns a bucket count appropriate
918 // for an element count of n. need_rehash(n_bkt, n_elt, n_ins)
919 // determines whether, if the current bucket count is n_bkt and the
920 // current element count is n_elt, we need to increase the bucket
921 // count. If so, returns make_pair(true, n), where n is the new
922 // bucket count. If not, returns make_pair(false, <anything>).
924 // ??? Right now it is hard-wired that the number of buckets never
925 // shrinks. Should we allow RehashPolicy to change that?
927 // cache_hash_code: bool. true if we store the value of the hash
928 // function along with the value. This is a time-space tradeoff.
929 // Storing it may improve lookup speed by reducing the number of times
930 // we need to call the Equal function.
932 // constant_iterators: bool. true if iterator and const_iterator are
933 // both constant iterator types. This is true for unordered_set and
934 // unordered_multiset, false for unordered_map and unordered_multimap.
936 // unique_keys: bool. true if the return value of hashtable::count(k)
937 // is always at most one, false if it may be an arbitrary number. This
938 // true for unordered_set and unordered_map, false for unordered_multiset
939 // and unordered_multimap.
941 template<typename Key, typename Value,
943 typename ExtractKey, typename Equal,
944 typename H1, typename H2,
945 typename H, typename RehashPolicy,
946 bool cache_hash_code,
947 bool constant_iterators,
950 : public Internal::rehash_base<RehashPolicy,
951 hashtable<Key, Value, Allocator, ExtractKey,
952 Equal, H1, H2, H, RehashPolicy,
953 cache_hash_code, constant_iterators,
955 public Internal::hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H,
957 public Internal::map_base<Key, Value, ExtractKey, unique_keys,
958 hashtable<Key, Value, Allocator, ExtractKey,
959 Equal, H1, H2, H, RehashPolicy,
960 cache_hash_code, constant_iterators,
964 typedef Allocator allocator_type;
965 typedef Value value_type;
966 typedef Key key_type;
967 typedef Equal key_equal;
968 // mapped_type, if present, comes from map_base.
969 // hasher, if present, comes from hash_code_base.
970 typedef typename Allocator::difference_type difference_type;
971 typedef typename Allocator::size_type size_type;
972 typedef typename Allocator::reference reference;
973 typedef typename Allocator::const_reference const_reference;
975 typedef Internal::node_iterator<value_type, constant_iterators,
978 typedef Internal::node_const_iterator<value_type, constant_iterators,
980 const_local_iterator;
982 typedef Internal::hashtable_iterator<value_type, constant_iterators,
985 typedef Internal::hashtable_const_iterator<value_type, constant_iterators,
990 typedef Internal::hash_node<Value, cache_hash_code> node;
991 typedef typename Allocator::template rebind<node>::other
993 typedef typename Allocator::template rebind<node*>::other
997 node_allocator_t m_node_allocator;
999 size_type m_bucket_count;
1000 size_type m_element_count;
1001 RehashPolicy m_rehash_policy;
1004 m_allocate_node(const value_type& v);
1007 m_deallocate_node(node* n);
1010 m_deallocate_nodes(node**, size_type);
1013 m_allocate_buckets(size_type n);
1016 m_deallocate_buckets(node**, size_type n);
1018 public: // Constructor, destructor, assignment, swap
1019 hashtable(size_type bucket_hint,
1020 const H1&, const H2&, const H&,
1021 const Equal&, const ExtractKey&,
1022 const allocator_type&);
1024 template<typename InIter>
1025 hashtable(InIter first, InIter last,
1026 size_type bucket_hint,
1027 const H1&, const H2&, const H&,
1028 const Equal&, const ExtractKey&,
1029 const allocator_type&);
1031 hashtable(const hashtable&);
1034 operator=(const hashtable&);
1038 void swap(hashtable&);
1040 public: // Basic container operations
1044 iterator i(m_buckets);
1053 const_iterator i(m_buckets);
1061 { return iterator(m_buckets + m_bucket_count); }
1065 { return const_iterator(m_buckets + m_bucket_count); }
1069 { return m_element_count; }
1073 { return size() == 0; }
1076 get_allocator() const
1077 { return m_node_allocator; }
1081 { return m_node_allocator.max_size(); }
1083 public: // Bucket operations
1085 bucket_count() const
1086 { return m_bucket_count; }
1089 max_bucket_count() const
1090 { return max_size(); }
1093 bucket_size(size_type n) const
1094 { return std::distance(begin(n), end(n)); }
1096 size_type bucket(const key_type& k) const
1098 return this->bucket_index(k, this->m_hash_code, this->m_bucket_count);
1103 { return local_iterator(m_buckets[n]); }
1107 { return local_iterator(0); }
1109 const_local_iterator
1110 begin(size_type n) const
1111 { return const_local_iterator(m_buckets[n]); }
1113 const_local_iterator
1114 end(size_type n) const
1115 { return const_local_iterator(0); }
1120 return static_cast<float>(size()) / static_cast<float>(bucket_count());
1122 // max_load_factor, if present, comes from rehash_base.
1124 // Generalization of max_load_factor. Extension, not found in TR1. Only
1125 // useful if RehashPolicy is something other than the default.
1127 rehash_policy() const
1128 { return m_rehash_policy; }
1131 rehash_policy(const RehashPolicy&);
1135 find(const key_type&);
1138 find(const key_type& k) const;
1141 count(const key_type& k) const;
1143 std::pair<iterator, iterator>
1144 equal_range(const key_type& k);
1146 std::pair<const_iterator, const_iterator>
1147 equal_range(const key_type& k) const;
1149 private: // Insert and erase helper functions
1150 // ??? This dispatching is a workaround for the fact that we don't
1151 // have partial specialization of member templates; it would be
1152 // better to just specialize insert on unique_keys. There may be a
1153 // cleaner workaround.
1154 typedef typename Internal::IF<unique_keys,
1155 std::pair<iterator, bool>, iterator>::type
1158 typedef typename Internal::IF<unique_keys,
1159 Internal::extract1st<Insert_Return_Type>,
1160 Internal::identity<Insert_Return_Type>
1165 find_node(node* p, const key_type& k,
1166 typename hashtable::hash_code_t c) const;
1168 std::pair<iterator, bool>
1169 insert(const value_type&, std::tr1::true_type);
1172 insert(const value_type&, std::tr1::false_type);
1175 erase_node(node*, node**);
1177 public: // Insert and erase
1179 insert(const value_type& v)
1181 return this->insert(v, std::tr1::integral_constant<bool,
1186 insert(iterator, const value_type& v)
1187 { return iterator(Insert_Conv_Type()(this->insert(v))); }
1190 insert(const_iterator, const value_type& v)
1191 { return const_iterator(Insert_Conv_Type()(this->insert(v))); }
1193 template<typename InIter>
1195 insert(InIter first, InIter last);
1201 erase(const_iterator);
1204 erase(const key_type&);
1207 erase(iterator, iterator);
1210 erase(const_iterator, const_iterator);
1216 // Set number of buckets to be apropriate for container of n element.
1217 void rehash(size_type n);
1220 // Unconditionally change size of bucket array to n.
1221 void m_rehash(size_type n);
1224 //----------------------------------------------------------------------
1225 // Definitions of class template hashtable's out-of-line member functions.
1227 template<typename K, typename V,
1228 typename A, typename Ex, typename Eq,
1229 typename H1, typename H2, typename H, typename RP,
1230 bool c, bool ci, bool u>
1231 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node*
1232 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1233 m_allocate_node(const value_type& v)
1235 node* n = m_node_allocator.allocate(1);
1238 get_allocator().construct(&n->m_v, v);
1244 m_node_allocator.deallocate(n, 1);
1245 __throw_exception_again;
1249 template<typename K, typename V,
1250 typename A, typename Ex, typename Eq,
1251 typename H1, typename H2, typename H, typename RP,
1252 bool c, bool ci, bool u>
1254 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1255 m_deallocate_node(node* n)
1257 get_allocator().destroy(&n->m_v);
1258 m_node_allocator.deallocate(n, 1);
1261 template<typename K, typename V,
1262 typename A, typename Ex, typename Eq,
1263 typename H1, typename H2, typename H, typename RP,
1264 bool c, bool ci, bool u>
1266 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1267 m_deallocate_nodes(node** array, size_type n)
1269 for (size_type i = 0; i < n; ++i)
1276 m_deallocate_node (tmp);
1282 template<typename K, typename V,
1283 typename A, typename Ex, typename Eq,
1284 typename H1, typename H2, typename H, typename RP,
1285 bool c, bool ci, bool u>
1286 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node**
1287 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1288 m_allocate_buckets(size_type n)
1290 bucket_allocator_t alloc(m_node_allocator);
1292 // We allocate one extra bucket to hold a sentinel, an arbitrary
1293 // non-null pointer. Iterator increment relies on this.
1294 node** p = alloc.allocate(n+1);
1295 std::fill(p, p+n, (node*) 0);
1296 p[n] = reinterpret_cast<node*>(0x1000);
1300 template<typename K, typename V,
1301 typename A, typename Ex, typename Eq,
1302 typename H1, typename H2, typename H, typename RP,
1303 bool c, bool ci, bool u>
1305 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1306 m_deallocate_buckets(node** p, size_type n)
1308 bucket_allocator_t alloc(m_node_allocator);
1309 alloc.deallocate(p, n+1);
1312 template<typename K, typename V,
1313 typename A, typename Ex, typename Eq,
1314 typename H1, typename H2, typename H, typename RP,
1315 bool c, bool ci, bool u>
1316 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1317 hashtable(size_type bucket_hint,
1318 const H1& h1, const H2& h2, const H& h,
1319 const Eq& eq, const Ex& exk,
1320 const allocator_type& a)
1321 : Internal::rehash_base<RP,hashtable>(),
1322 Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq, h1, h2, h),
1323 Internal::map_base<K, V, Ex, u, hashtable>(),
1324 m_node_allocator(a),
1329 m_bucket_count = m_rehash_policy.next_bkt(bucket_hint);
1330 m_buckets = m_allocate_buckets(m_bucket_count);
1333 template<typename K, typename V,
1334 typename A, typename Ex, typename Eq,
1335 typename H1, typename H2, typename H, typename RP,
1336 bool c, bool ci, bool u>
1337 template<typename InIter>
1338 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1339 hashtable(InIter f, InIter l,
1340 size_type bucket_hint,
1341 const H1& h1, const H2& h2, const H& h,
1342 const Eq& eq, const Ex& exk,
1343 const allocator_type& a)
1344 : Internal::rehash_base<RP,hashtable>(),
1345 Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c> (exk, eq,
1347 Internal::map_base<K,V,Ex,u,hashtable>(),
1348 m_node_allocator(a),
1353 m_bucket_count = std::max(m_rehash_policy.next_bkt(bucket_hint),
1355 bkt_for_elements(Internal::
1356 distance_fw(f, l)));
1357 m_buckets = m_allocate_buckets(m_bucket_count);
1366 m_deallocate_buckets(m_buckets, m_bucket_count);
1367 __throw_exception_again;
1371 template<typename K, typename V,
1372 typename A, typename Ex, typename Eq,
1373 typename H1, typename H2, typename H, typename RP,
1374 bool c, bool ci, bool u>
1375 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1376 hashtable(const hashtable& ht)
1377 : Internal::rehash_base<RP, hashtable>(ht),
1378 Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(ht),
1379 Internal::map_base<K, V, Ex, u, hashtable>(ht),
1380 m_node_allocator(ht.get_allocator()),
1381 m_bucket_count(ht.m_bucket_count),
1382 m_element_count(ht.m_element_count),
1383 m_rehash_policy(ht.m_rehash_policy)
1385 m_buckets = m_allocate_buckets (m_bucket_count);
1388 for (size_t i = 0; i < ht.m_bucket_count; ++i)
1390 node* n = ht.m_buckets[i];
1391 node** tail = m_buckets + i;
1394 *tail = m_allocate_node(n->m_v);
1395 this->copy_code(*tail, n);
1396 tail = &((*tail)->m_next);
1404 m_deallocate_buckets (m_buckets, m_bucket_count);
1405 __throw_exception_again;
1409 template<typename K, typename V,
1410 typename A, typename Ex, typename Eq,
1411 typename H1, typename H2, typename H, typename RP,
1412 bool c, bool ci, bool u>
1413 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>&
1414 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1415 operator=(const hashtable& ht)
1422 template<typename K, typename V,
1423 typename A, typename Ex, typename Eq,
1424 typename H1, typename H2, typename H, typename RP,
1425 bool c, bool ci, bool u>
1426 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1430 m_deallocate_buckets(m_buckets, m_bucket_count);
1433 template<typename K, typename V,
1434 typename A, typename Ex, typename Eq,
1435 typename H1, typename H2, typename H, typename RP,
1436 bool c, bool ci, bool u>
1438 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1441 // The only base class with member variables is hash_code_base. We
1442 // define hash_code_base::m_swap because different specializations
1443 // have different members.
1444 Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>::m_swap(x);
1446 // open LWG issue 431
1447 // std::swap(m_node_allocator, x.m_node_allocator);
1448 std::swap(m_rehash_policy, x.m_rehash_policy);
1449 std::swap(m_buckets, x.m_buckets);
1450 std::swap(m_bucket_count, x.m_bucket_count);
1451 std::swap(m_element_count, x.m_element_count);
1454 template<typename K, typename V,
1455 typename A, typename Ex, typename Eq,
1456 typename H1, typename H2, typename H, typename RP,
1457 bool c, bool ci, bool u>
1459 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1460 rehash_policy(const RP& pol)
1462 m_rehash_policy = pol;
1463 size_type n_bkt = pol.bkt_for_elements(m_element_count);
1464 if (n_bkt > m_bucket_count)
1468 template<typename K, typename V,
1469 typename A, typename Ex, typename Eq,
1470 typename H1, typename H2, typename H, typename RP,
1471 bool c, bool ci, bool u>
1472 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
1473 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1474 find(const key_type& k)
1476 typename hashtable::hash_code_t code = this->m_hash_code (k);
1477 std::size_t n = this->bucket_index(k, code, this->bucket_count());
1478 node* p = find_node (m_buckets[n], k, code);
1479 return p ? iterator(p, m_buckets + n) : this->end();
1482 template<typename K, typename V,
1483 typename A, typename Ex, typename Eq,
1484 typename H1, typename H2, typename H, typename RP,
1485 bool c, bool ci, bool u>
1486 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
1487 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1488 find(const key_type& k) const
1490 typename hashtable::hash_code_t code = this->m_hash_code (k);
1491 std::size_t n = this->bucket_index(k, code, this->bucket_count());
1492 node* p = find_node (m_buckets[n], k, code);
1493 return p ? const_iterator(p, m_buckets + n) : this->end();
1496 template<typename K, typename V,
1497 typename A, typename Ex, typename Eq,
1498 typename H1, typename H2, typename H, typename RP,
1499 bool c, bool ci, bool u>
1500 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::size_type
1501 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1502 count(const key_type& k) const
1504 typename hashtable::hash_code_t code = this->m_hash_code (k);
1505 std::size_t n = this->bucket_index (k, code, this->bucket_count());
1507 for (node* p = m_buckets[n]; p ; p = p->m_next)
1508 if (this->compare (k, code, p))
1513 template<typename K, typename V,
1514 typename A, typename Ex, typename Eq,
1515 typename H1, typename H2, typename H, typename RP,
1516 bool c, bool ci, bool u>
1517 std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
1518 H2, H, RP, c, ci, u>::iterator,
1519 typename hashtable<K, V, A, Ex, Eq, H1,
1520 H2, H, RP, c, ci, u>::iterator>
1521 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1522 equal_range(const key_type& k)
1524 typename hashtable::hash_code_t code = this->m_hash_code (k);
1525 std::size_t n = this->bucket_index(k, code, this->bucket_count());
1526 node** head = m_buckets + n;
1527 node* p = find_node (*head, k, code);
1531 node* p1 = p->m_next;
1532 for (; p1 ; p1 = p1->m_next)
1533 if (!this->compare (k, code, p1))
1536 iterator first(p, head);
1537 iterator last(p1, head);
1539 last.m_incr_bucket();
1540 return std::make_pair(first, last);
1543 return std::make_pair(this->end(), this->end());
1546 template<typename K, typename V,
1547 typename A, typename Ex, typename Eq,
1548 typename H1, typename H2, typename H, typename RP,
1549 bool c, bool ci, bool u>
1550 std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
1551 H2, H, RP, c, ci, u>::const_iterator,
1552 typename hashtable<K, V, A, Ex, Eq, H1,
1553 H2, H, RP, c, ci, u>::const_iterator>
1554 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1555 equal_range(const key_type& k) const
1557 typename hashtable::hash_code_t code = this->m_hash_code (k);
1558 std::size_t n = this->bucket_index(k, code, this->bucket_count());
1559 node** head = m_buckets + n;
1560 node* p = find_node (*head, k, code);
1564 node* p1 = p->m_next;
1565 for (; p1 ; p1 = p1->m_next)
1566 if (!this->compare (k, code, p1))
1569 const_iterator first(p, head);
1570 const_iterator last(p1, head);
1572 last.m_incr_bucket();
1573 return std::make_pair(first, last);
1576 return std::make_pair(this->end(), this->end());
1579 // Find the node whose key compares equal to k, beginning the search
1580 // at p (usually the head of a bucket). Return nil if no node is found.
1581 template<typename K, typename V,
1582 typename A, typename Ex, typename Eq,
1583 typename H1, typename H2, typename H, typename RP,
1584 bool c, bool ci, bool u>
1585 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node*
1586 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1587 find_node(node* p, const key_type& k,
1588 typename hashtable::hash_code_t code) const
1590 for ( ; p ; p = p->m_next)
1591 if (this->compare (k, code, p))
1596 // Insert v if no element with its key is already present.
1597 template<typename K, typename V,
1598 typename A, typename Ex, typename Eq,
1599 typename H1, typename H2, typename H, typename RP,
1600 bool c, bool ci, bool u>
1601 std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
1602 H2, H, RP, c, ci, u>::iterator, bool>
1603 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1604 insert(const value_type& v, std::tr1::true_type)
1606 const key_type& k = this->m_extract(v);
1607 typename hashtable::hash_code_t code = this->m_hash_code (k);
1608 size_type n = this->bucket_index(k, code, m_bucket_count);
1610 if (node* p = find_node(m_buckets[n], k, code))
1611 return std::make_pair(iterator(p, m_buckets + n), false);
1613 std::pair<bool, size_t> do_rehash
1614 = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);
1616 // Allocate the new node before doing the rehash so that we don't
1617 // do a rehash if the allocation throws.
1618 node* new_node = m_allocate_node (v);
1622 if (do_rehash.first)
1624 n = this->bucket_index(k, code, do_rehash.second);
1625 m_rehash(do_rehash.second);
1628 new_node->m_next = m_buckets[n];
1629 this->store_code(new_node, code);
1630 m_buckets[n] = new_node;
1632 return std::make_pair(iterator(new_node, m_buckets + n), true);
1636 m_deallocate_node (new_node);
1637 __throw_exception_again;
1641 // Insert v unconditionally.
1642 template<typename K, typename V,
1643 typename A, typename Ex, typename Eq,
1644 typename H1, typename H2, typename H, typename RP,
1645 bool c, bool ci, bool u>
1646 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
1647 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1648 insert(const value_type& v, std::tr1::false_type)
1650 std::pair<bool, std::size_t> do_rehash
1651 = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);
1652 if (do_rehash.first)
1653 m_rehash(do_rehash.second);
1655 const key_type& k = this->m_extract(v);
1656 typename hashtable::hash_code_t code = this->m_hash_code (k);
1657 size_type n = this->bucket_index(k, code, m_bucket_count);
1659 node* new_node = m_allocate_node (v);
1660 node* prev = find_node(m_buckets[n], k, code);
1663 new_node->m_next = prev->m_next;
1664 prev->m_next = new_node;
1668 new_node->m_next = m_buckets[n];
1669 m_buckets[n] = new_node;
1671 this->store_code(new_node, code);
1674 return iterator(new_node, m_buckets + n);
1677 // For erase(iterator) and erase(const_iterator).
1678 template<typename K, typename V,
1679 typename A, typename Ex, typename Eq,
1680 typename H1, typename H2, typename H, typename RP,
1681 bool c, bool ci, bool u>
1683 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1684 erase_node(node* p, node** b)
1691 node* next = cur->m_next;
1697 cur->m_next = next->m_next;
1700 m_deallocate_node (p);
1704 template<typename K, typename V,
1705 typename A, typename Ex, typename Eq,
1706 typename H1, typename H2, typename H, typename RP,
1707 bool c, bool ci, bool u>
1708 template<typename InIter>
1710 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1711 insert(InIter first, InIter last)
1713 size_type n_elt = Internal::distance_fw (first, last);
1714 std::pair<bool, std::size_t> do_rehash
1715 = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, n_elt);
1716 if (do_rehash.first)
1717 m_rehash(do_rehash.second);
1719 for (; first != last; ++first)
1720 this->insert (*first);
1723 template<typename K, typename V,
1724 typename A, typename Ex, typename Eq,
1725 typename H1, typename H2, typename H, typename RP,
1726 bool c, bool ci, bool u>
1727 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
1728 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1731 iterator result = i;
1733 erase_node(i.m_cur_node, i.m_cur_bucket);
1737 template<typename K, typename V,
1738 typename A, typename Ex, typename Eq,
1739 typename H1, typename H2, typename H, typename RP,
1740 bool c, bool ci, bool u>
1741 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
1742 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1743 erase(const_iterator i)
1745 const_iterator result = i;
1747 erase_node(i.m_cur_node, i.m_cur_bucket);
1751 template<typename K, typename V,
1752 typename A, typename Ex, typename Eq,
1753 typename H1, typename H2, typename H, typename RP,
1754 bool c, bool ci, bool u>
1755 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::size_type
1756 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1757 erase(const key_type& k)
1759 typename hashtable::hash_code_t code = this->m_hash_code (k);
1760 size_type n = this->bucket_index(k, code, m_bucket_count);
1761 size_type result = 0;
1763 node** slot = m_buckets + n;
1764 while (*slot && ! this->compare (k, code, *slot))
1765 slot = &((*slot)->m_next);
1767 while (*slot && this->compare (k, code, *slot))
1771 m_deallocate_node (n);
1779 // ??? This could be optimized by taking advantage of the bucket
1780 // structure, but it's not clear that it's worth doing. It probably
1781 // wouldn't even be an optimization unless the load factor is large.
1782 template<typename K, typename V,
1783 typename A, typename Ex, typename Eq,
1784 typename H1, typename H2, typename H, typename RP,
1785 bool c, bool ci, bool u>
1786 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
1787 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1788 erase(iterator first, iterator last)
1790 while (first != last)
1791 first = this->erase(first);
1795 template<typename K, typename V,
1796 typename A, typename Ex, typename Eq,
1797 typename H1, typename H2, typename H, typename RP,
1798 bool c, bool ci, bool u>
1799 typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
1800 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1801 erase(const_iterator first, const_iterator last)
1803 while (first != last)
1804 first = this->erase(first);
1808 template<typename K, typename V,
1809 typename A, typename Ex, typename Eq,
1810 typename H1, typename H2, typename H, typename RP,
1811 bool c, bool ci, bool u>
1813 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1816 m_deallocate_nodes(m_buckets, m_bucket_count);
1817 m_element_count = 0;
1820 template<typename K, typename V,
1821 typename A, typename Ex, typename Eq,
1822 typename H1, typename H2, typename H, typename RP,
1823 bool c, bool ci, bool u>
1825 hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1826 m_rehash(size_type N)
1828 node** new_array = m_allocate_buckets (N);
1831 for (size_type i = 0; i < m_bucket_count; ++i)
1832 while (node* p = m_buckets[i])
1834 size_type new_index = this->bucket_index (p, N);
1835 m_buckets[i] = p->m_next;
1836 p->m_next = new_array[new_index];
1837 new_array[new_index] = p;
1839 m_deallocate_buckets(m_buckets, m_bucket_count);
1841 m_buckets = new_array;
1845 // A failure here means that a hash function threw an exception.
1846 // We can't restore the previous state without calling the hash
1847 // function again, so the only sensible recovery is to delete
1849 m_deallocate_nodes(new_array, N);
1850 m_deallocate_buckets(new_array, N);
1851 m_deallocate_nodes(m_buckets, m_bucket_count);
1852 m_element_count = 0;
1853 __throw_exception_again;
1857 _GLIBCXX_END_NAMESPACE
1858 } // Namespace std::tr1
1860 #endif /* GNU_LIBSTDCXX_TR1_HASHTABLE_ */