OSDN Git Service

2006-02-22 Paolo Carlini <pcarlini@suse.de>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / tr1 / hashtable
1 // Internal header for TR1 unordered_set and unordered_map -*- C++ -*-
2
3 // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
4 //
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)
9 // any later version.
10
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.
15
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,
19 // USA.
20
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.
29
30 /** @file 
31  *  This is a TR1 C++ Library header. 
32  */
33
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.
40
41 // ??? Arguably this should be Internal::hashtable, not std::tr1::hashtable.
42
43 // Class template hashtable attempts to encapsulate all reasonable
44 // variation among hash tables that use chaining.  It does not handle
45 // open addressing.
46
47 // References: 
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.
52 //    ??? Full citation?
53
54 #ifndef GNU_LIBSTDCXX_TR1_HASHTABLE_
55 #define GNU_LIBSTDCXX_TR1_HASHTABLE_
56
57 #include <utility>              // For std::pair
58 #include <memory>
59 #include <iterator>
60 #include <cstddef>
61 #include <cstdlib>
62 #include <cmath>
63 #include <bits/functexcept.h>
64 #include <tr1/type_traits>      // For true_type and false_type
65
66 //----------------------------------------------------------------------
67 // General utilities
68
69 namespace Internal
70 {
71   template<bool Flag, typename IfTrue, typename IfFalse>
72     struct IF;
73
74   template<typename IfTrue, typename IfFalse>
75     struct IF<true, IfTrue, IfFalse>
76     { typedef IfTrue type; };
77  
78   template <typename IfTrue, typename IfFalse>
79     struct IF<false, IfTrue, IfFalse>
80     { typedef IfFalse type; };
81
82   // Helper function: return distance(first, last) for forward
83   // iterators, or 0 for input iterators.
84   template<class Iterator>
85     inline typename std::iterator_traits<Iterator>::difference_type
86     distance_fw(Iterator first, Iterator last, std::input_iterator_tag)
87     { return 0; }
88
89   template<class Iterator>
90     inline typename std::iterator_traits<Iterator>::difference_type
91     distance_fw(Iterator first, Iterator last, std::forward_iterator_tag)
92     { return std::distance(first, last); }
93
94   template<class Iterator>
95     inline typename std::iterator_traits<Iterator>::difference_type
96     distance_fw(Iterator first, Iterator last)
97     {
98       typedef typename std::iterator_traits<Iterator>::iterator_category tag;
99       return distance_fw(first, last, tag());
100     }
101   
102 } // namespace Internal
103
104
105 //----------------------------------------------------------------------
106 // Auxiliary types used for all instantiations of hashtable: nodes
107 // and iterators.
108
109 // Nodes, used to wrap elements stored in the hash table.  A policy
110 // template parameter of class template hashtable controls whether
111 // nodes also store a hash code. In some cases (e.g. strings) this may
112 // be a performance win.
113
114 namespace Internal
115 {
116   template<typename Value, bool cache_hash_code>
117     struct hash_node;
118
119   template<typename Value>
120     struct hash_node<Value, true>
121     {
122       Value       m_v;
123       std::size_t hash_code;
124       hash_node*  m_next;
125     };
126
127   template<typename Value>
128     struct hash_node<Value, false>
129     {
130       Value       m_v;
131       hash_node*  m_next;
132     };
133
134   // Local iterators, used to iterate within a bucket but not between
135   // buckets.
136
137   template<typename Value, bool cache>
138     struct node_iterator_base
139     {
140       node_iterator_base(hash_node<Value, cache>* p)
141       : m_cur(p) { }
142       
143       void
144       incr()
145       { m_cur = m_cur->m_next; }
146
147       hash_node<Value, cache>* m_cur;
148     };
149
150   template<typename Value, bool cache>
151     inline bool
152     operator==(const node_iterator_base<Value, cache>& x,
153                const node_iterator_base<Value, cache>& y)
154     { return x.m_cur == y.m_cur; }
155
156   template<typename Value, bool cache>
157     inline bool
158     operator!=(const node_iterator_base<Value, cache>& x,
159                const node_iterator_base<Value, cache>& y)
160     { return x.m_cur != y.m_cur; }
161
162   template<typename Value, bool constant_iterators, bool cache>
163     struct node_iterator
164     : public node_iterator_base<Value, cache>
165     {
166       typedef Value                                    value_type;
167       typedef typename IF<constant_iterators, const Value*, Value*>::type
168                                                        pointer;
169       typedef typename IF<constant_iterators, const Value&, Value&>::type
170                                                        reference;
171       typedef std::ptrdiff_t                           difference_type;
172       typedef std::forward_iterator_tag                iterator_category;
173
174       explicit
175       node_iterator(hash_node<Value, cache>* p = 0)
176       : node_iterator_base<Value, cache>(p) { }
177
178       reference
179       operator*() const
180       { return this->m_cur->m_v; }
181   
182       pointer
183       operator->() const
184       { return &this->m_cur->m_v; }
185
186       node_iterator&
187       operator++()
188       { 
189         this->incr(); 
190         return *this; 
191       }
192   
193       node_iterator
194       operator++(int)
195       { 
196         node_iterator tmp(*this);
197         this->incr();
198         return tmp;
199       }
200     };
201
202   template<typename Value, bool constant_iterators, bool cache>
203     struct node_const_iterator
204     : public node_iterator_base<Value, cache>
205     {
206       typedef Value                                    value_type;
207       typedef const Value*                             pointer;
208       typedef const Value&                             reference;
209       typedef std::ptrdiff_t                           difference_type;
210       typedef std::forward_iterator_tag                iterator_category;
211
212       explicit
213       node_const_iterator(hash_node<Value, cache>* p = 0)
214       : node_iterator_base<Value, cache>(p) { }
215
216       node_const_iterator(const node_iterator<Value, constant_iterators,
217                           cache>& x)
218       : node_iterator_base<Value, cache>(x.m_cur) { }
219
220       reference
221       operator*() const
222       { return this->m_cur->m_v; }
223   
224       pointer
225       operator->() const
226       { return &this->m_cur->m_v; }
227
228       node_const_iterator&
229       operator++()
230       { 
231         this->incr(); 
232         return *this; 
233       }
234   
235       node_const_iterator
236       operator++(int)
237       { 
238         node_const_iterator tmp(*this);
239         this->incr();
240         return tmp;
241       }
242     };
243
244   template<typename Value, bool cache>
245     struct hashtable_iterator_base
246     {
247       hashtable_iterator_base(hash_node<Value, cache>* node,
248                               hash_node<Value, cache>** bucket)
249       : m_cur_node(node), m_cur_bucket(bucket)
250       { }
251
252       void
253       incr()
254       {
255         m_cur_node = m_cur_node->m_next;
256         if (!m_cur_node)
257           m_incr_bucket();
258       }
259
260       void
261       m_incr_bucket();
262
263       hash_node<Value, cache>*  m_cur_node;
264       hash_node<Value, cache>** m_cur_bucket;
265     };
266
267   // Global iterators, used for arbitrary iteration within a hash
268   // table.  Larger and more expensive than local iterators.
269   template<typename Value, bool cache>
270     void
271     hashtable_iterator_base<Value, cache>::
272     m_incr_bucket()
273     {
274       ++m_cur_bucket;
275
276       // This loop requires the bucket array to have a non-null sentinel.
277       while (!*m_cur_bucket)
278         ++m_cur_bucket;
279       m_cur_node = *m_cur_bucket;
280     }
281
282   template<typename Value, bool cache>
283     inline bool
284     operator==(const hashtable_iterator_base<Value, cache>& x,
285                const hashtable_iterator_base<Value, cache>& y)
286     { return x.m_cur_node == y.m_cur_node; }
287
288   template<typename Value, bool cache>
289     inline bool
290     operator!=(const hashtable_iterator_base<Value, cache>& x,
291                const hashtable_iterator_base<Value, cache>& y)
292     { return x.m_cur_node != y.m_cur_node; }
293
294   template<typename Value, bool constant_iterators, bool cache>
295     struct hashtable_iterator
296     : public hashtable_iterator_base<Value, cache>
297     {
298       typedef Value                                    value_type;
299       typedef typename IF<constant_iterators, const Value*, Value*>::type
300                                                        pointer;
301       typedef typename IF<constant_iterators, const Value&, Value&>::type
302                                                        reference;
303       typedef std::ptrdiff_t                           difference_type;
304       typedef std::forward_iterator_tag                iterator_category;
305
306       hashtable_iterator(hash_node<Value, cache>* p,
307                          hash_node<Value, cache>** b)
308       : hashtable_iterator_base<Value, cache>(p, b) { }
309
310       explicit
311       hashtable_iterator(hash_node<Value, cache>** b)
312       : hashtable_iterator_base<Value, cache>(*b, b) { }
313   
314       reference
315       operator*() const
316       { return this->m_cur_node->m_v; }
317   
318       pointer
319       operator->() const
320       { return &this->m_cur_node->m_v; }
321
322       hashtable_iterator&
323       operator++()
324       { 
325         this->incr();
326         return *this;
327       }
328   
329       hashtable_iterator
330       operator++(int)
331       { 
332         hashtable_iterator tmp(*this);
333         this->incr();
334         return tmp;
335       }
336     };
337
338   template<typename Value, bool constant_iterators, bool cache>
339     struct hashtable_const_iterator
340     : public hashtable_iterator_base<Value, cache>
341     {
342       typedef Value                                    value_type;
343       typedef const Value*                             pointer;
344       typedef const Value&                             reference;
345       typedef std::ptrdiff_t                           difference_type;
346       typedef std::forward_iterator_tag                iterator_category;
347
348       hashtable_const_iterator(hash_node<Value, cache>* p,
349                                hash_node<Value, cache>** b)
350       : hashtable_iterator_base<Value, cache>(p, b) { }
351
352       explicit
353       hashtable_const_iterator(hash_node<Value, cache>** b)
354       : hashtable_iterator_base<Value, cache>(*b, b) { }
355   
356       hashtable_const_iterator(const hashtable_iterator<Value,
357                                constant_iterators, cache>& x)
358       : hashtable_iterator_base<Value, cache>(x.m_cur_node, x.m_cur_bucket) { }
359
360       reference
361       operator*() const
362       { return this->m_cur_node->m_v; }
363   
364       pointer
365       operator->() const
366       { return &this->m_cur_node->m_v; }
367
368       hashtable_const_iterator&
369       operator++()
370       { 
371         this->incr();
372         return *this;
373       }
374   
375       hashtable_const_iterator
376       operator++(int)
377       { 
378         hashtable_const_iterator tmp(*this);
379         this->incr();
380         return tmp;
381       }
382     };
383 } // namespace Internal
384
385
386 // ----------------------------------------------------------------------
387 // Many of class template hashtable's template parameters are policy
388 // classes.  These are defaults for the policies.
389
390 namespace Internal
391 {
392   // The two key extraction policies used by the *set and *map variants.
393   template<typename T>
394     struct identity
395     {
396       T
397       operator()(const T& t) const
398       { return t; }
399     };
400
401   template<typename Pair>
402     struct extract1st
403     {
404       typename Pair::first_type
405       operator()(const Pair& p) const
406       { return p.first; }
407     };
408
409   // Default range hashing function: use division to fold a large number
410   // into the range [0, N).
411   struct mod_range_hashing
412   {
413     typedef std::size_t first_argument_type;
414     typedef std::size_t second_argument_type;
415     typedef std::size_t result_type;
416
417     result_type
418     operator()(first_argument_type r, second_argument_type N) const
419     { return r % N; }
420   };
421
422   // Default ranged hash function H.  In principle it should be a
423   // function object composed from objects of type H1 and H2 such that
424   // h(k, N) = h2(h1(k), N), but that would mean making extra copies of
425   // h1 and h2.  So instead we'll just use a tag to tell class template
426   // hashtable to do that composition.
427   struct default_ranged_hash { };
428
429   // Default value for rehash policy.  Bucket size is (usually) the
430   // smallest prime that keeps the load factor small enough.
431   struct prime_rehash_policy
432   {
433     prime_rehash_policy(float z = 1.0);
434     
435     float
436     max_load_factor() const;
437
438     // Return a bucket size no smaller than n.
439     std::size_t
440     next_bkt(std::size_t n) const;
441     
442     // Return a bucket count appropriate for n elements
443     std::size_t
444     bkt_for_elements(std::size_t n) const;
445     
446     // n_bkt is current bucket count, n_elt is current element count,
447     // and n_ins is number of elements to be inserted.  Do we need to
448     // increase bucket count?  If so, return make_pair(true, n), where n
449     // is the new bucket count.  If not, return make_pair(false, 0).
450     std::pair<bool, std::size_t>
451     need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const;
452     
453     float               m_max_load_factor;
454     float               m_growth_factor;
455     mutable std::size_t m_next_resize;
456   };
457
458   // XXX This is a hack.  prime_rehash_policy's member functions, and
459   // certainly the list of primes, should be defined in a .cc file.
460   // We're temporarily putting them in a header because we don't have a
461   // place to put TR1 .cc files yet.  There's no good reason for any of
462   // prime_rehash_policy's member functions to be inline, and there's
463   // certainly no good reason for X<> to exist at all.
464   
465   struct lt
466   {
467     template<typename X, typename Y>
468       bool
469       operator()(X x, Y y)
470       { return x < y; }
471   };
472
473   template<int dummy>
474     struct X
475     {
476       static const int n_primes = 256;
477       static const unsigned long primes[n_primes + 1];
478     };
479
480   template<int dummy>
481     const int X<dummy>::n_primes;
482
483   template<int dummy>
484     const unsigned long X<dummy>::primes[n_primes + 1] =
485     {
486       2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
487       37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul,
488       83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul,
489       157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul,
490       277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul,
491       503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul,
492       953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul,
493       1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul,
494       3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul,
495       5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul,
496       11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul,
497       19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul,
498       33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul,
499       57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul,
500       99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul,
501       159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul,
502       256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul,
503       410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul,
504       658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul,
505       1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul,
506       1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul,
507       2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul,
508       4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul,
509       6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul,
510       11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul,
511       16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul,
512       24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul,
513       36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul,
514       54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul,
515       80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul,
516       118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul,
517       176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul,
518       260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul,
519       386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul,
520       573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul,
521       849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul,
522       1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul,
523       1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul,
524       2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul,
525       3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul,
526       4294967291ul,
527       4294967291ul // sentinel so we don't have to test result of lower_bound
528     };
529
530   inline
531   prime_rehash_policy::
532   prime_rehash_policy(float z)
533   : m_max_load_factor(z), m_growth_factor(2.f), m_next_resize(0)
534   { }
535
536   inline float
537   prime_rehash_policy::
538   max_load_factor() const
539   { return m_max_load_factor; }
540
541   // Return a prime no smaller than n.
542   inline std::size_t
543   prime_rehash_policy::
544   next_bkt(std::size_t n) const
545   {
546     const unsigned long* const last = X<0>::primes + X<0>::n_primes;
547     const unsigned long* p = std::lower_bound(X<0>::primes, last, n);
548     m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
549     return *p;
550   }
551
552   // Return the smallest prime p such that alpha p >= n, where alpha
553   // is the load factor.
554   inline std::size_t
555   prime_rehash_policy::
556   bkt_for_elements(std::size_t n) const
557   {
558     const unsigned long* const last = X<0>::primes + X<0>::n_primes;
559     const float min_bkts = n / m_max_load_factor;
560     const unsigned long* p = std::lower_bound(X<0>::primes, last,
561                                               min_bkts, lt());
562     m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
563     return *p;
564   }
565
566   // Finds the smallest prime p such that alpha p > n_elt + n_ins.
567   // If p > n_bkt, return make_pair(true, p); otherwise return
568   // make_pair(false, 0).  In principle this isn't very different from 
569   // bkt_for_elements.
570   
571   // The only tricky part is that we're caching the element count at
572   // which we need to rehash, so we don't have to do a floating-point
573   // multiply for every insertion.
574   
575   inline std::pair<bool, std::size_t>
576   prime_rehash_policy::
577   need_rehash(std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const
578   {
579     if (n_elt + n_ins > m_next_resize)
580       {
581         float min_bkts = (float(n_ins) + float(n_elt)) / m_max_load_factor;
582         if (min_bkts > n_bkt)
583           {
584             min_bkts = std::max(min_bkts, m_growth_factor * n_bkt);
585             const unsigned long* const last = X<0>::primes + X<0>::n_primes;
586             const unsigned long* p = std::lower_bound(X<0>::primes, last,
587                                                       min_bkts, lt());
588             m_next_resize = 
589               static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
590             return std::make_pair(true, *p);
591           }
592         else 
593           {
594             m_next_resize = 
595               static_cast<std::size_t>(std::ceil(n_bkt * m_max_load_factor));
596             return std::make_pair(false, 0);
597           }
598       }
599     else
600       return std::make_pair(false, 0);
601   }
602
603 } // namespace Internal
604
605
606 //----------------------------------------------------------------------
607 // Base classes for std::tr1::hashtable.  We define these base classes
608 // because in some cases we want to do different things depending on
609 // the value of a policy class.  In some cases the policy class affects
610 // which member functions and nested typedefs are defined; we handle that
611 // by specializing base class templates.  Several of the base class templates
612 // need to access other members of class template hashtable, so we use
613 // the "curiously recurring template pattern" for them.
614
615 namespace Internal
616 {
617   // class template map_base.  If the hashtable has a value type of the
618   // form pair<T1, T2> and a key extraction policy that returns the
619   // first part of the pair, the hashtable gets a mapped_type typedef.
620   // If it satisfies those criteria and also has unique keys, then it
621   // also gets an operator[].
622   
623   template<typename K, typename V, typename Ex, bool unique, typename Hashtable>
624     struct map_base { };
625           
626   template<typename K, typename Pair, typename Hashtable>
627     struct map_base<K, Pair, extract1st<Pair>, false, Hashtable>
628     {
629       typedef typename Pair::second_type mapped_type;
630     };
631
632   template<typename K, typename Pair, typename Hashtable>
633     struct map_base<K, Pair, extract1st<Pair>, true, Hashtable>
634     {
635       typedef typename Pair::second_type mapped_type;
636       
637       mapped_type&
638       operator[](const K& k)
639       {
640         Hashtable* h = static_cast<Hashtable*>(this);
641         typename Hashtable::iterator it = 
642           h->insert(std::make_pair(k, mapped_type())).first;
643         return it->second;
644       }
645     };
646
647   // class template rehash_base.  Give hashtable the max_load_factor
648   // functions iff the rehash policy is prime_rehash_policy.
649   template<typename RehashPolicy, typename Hashtable>
650     struct rehash_base { };
651
652   template<typename Hashtable>
653     struct rehash_base<prime_rehash_policy, Hashtable>
654     {
655       float
656       max_load_factor() const
657       {
658         const Hashtable* This = static_cast<const Hashtable*>(this);
659         return This->rehash_policy().max_load_factor();
660       }
661
662       void
663       max_load_factor(float z)
664       {
665         Hashtable* This = static_cast<Hashtable*>(this);
666         This->rehash_policy(prime_rehash_policy(z));    
667       }
668     };
669
670   // Class template hash_code_base.  Encapsulates two policy issues that
671   // aren't quite orthogonal.
672   //   (1) the difference between using a ranged hash function and using
673   //       the combination of a hash function and a range-hashing function.
674   //       In the former case we don't have such things as hash codes, so
675   //       we have a dummy type as placeholder.
676   //   (2) Whether or not we cache hash codes.  Caching hash codes is
677   //       meaningless if we have a ranged hash function.
678   // We also put the key extraction and equality comparison function 
679   // objects here, for convenience.
680   
681   // Primary template: unused except as a hook for specializations.
682   
683   template<typename Key, typename Value,
684            typename ExtractKey, typename Equal,
685            typename H1, typename H2, typename H,
686            bool cache_hash_code>
687     struct hash_code_base;
688
689   // Specialization: ranged hash function, no caching hash codes.  H1
690   // and H2 are provided but ignored.  We define a dummy hash code type.
691   template<typename Key, typename Value,
692            typename ExtractKey, typename Equal,
693            typename H1, typename H2, typename H>
694     struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, false>
695     {
696     protected:
697       hash_code_base(const ExtractKey& ex, const Equal& eq,
698                      const H1&, const H2&, const H& h)
699       : m_extract(ex), m_eq(eq), m_ranged_hash(h) { }
700
701       typedef void* hash_code_t;
702   
703       hash_code_t
704       m_hash_code(const Key& k) const
705       { return 0; }
706   
707       std::size_t
708       bucket_index(const Key& k, hash_code_t, std::size_t N) const
709       { return m_ranged_hash(k, N); }
710
711       std::size_t
712       bucket_index(const hash_node<Value, false>* p, std::size_t N) const
713       { return m_ranged_hash(m_extract(p->m_v), N); }
714   
715       bool
716       compare(const Key& k, hash_code_t, hash_node<Value, false>* n) const
717       { return m_eq(k, m_extract(n->m_v)); }
718
719       void
720       store_code(hash_node<Value, false>*, hash_code_t) const
721       { }
722
723       void
724       copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const
725       { }
726       
727       void
728       m_swap(hash_code_base& x)
729       {
730         std::swap(m_extract, x.m_extract);
731         std::swap(m_eq, x.m_eq);
732         std::swap(m_ranged_hash, x.m_ranged_hash);
733       }
734
735     protected:
736       ExtractKey m_extract;
737       Equal      m_eq;
738       H          m_ranged_hash;
739     };
740
741
742   // No specialization for ranged hash function while caching hash codes.
743   // That combination is meaningless, and trying to do it is an error.
744   
745   
746   // Specialization: ranged hash function, cache hash codes.  This
747   // combination is meaningless, so we provide only a declaration
748   // and no definition.
749   
750   template<typename Key, typename Value,
751             typename ExtractKey, typename Equal,
752             typename H1, typename H2, typename H>
753     struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, true>;
754
755
756   // Specialization: hash function and range-hashing function, no
757   // caching of hash codes.  H is provided but ignored.  Provides
758   // typedef and accessor required by TR1.
759   
760   template<typename Key, typename Value,
761            typename ExtractKey, typename Equal,
762            typename H1, typename H2>
763     struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2,
764                           default_ranged_hash, false>
765     {
766       typedef H1 hasher;
767       
768       hasher
769       hash_function() const
770       { return m_h1; }
771
772     protected:
773       hash_code_base(const ExtractKey& ex, const Equal& eq,
774                      const H1& h1, const H2& h2, const default_ranged_hash&)
775       : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { }
776
777       typedef std::size_t hash_code_t;
778       
779       hash_code_t
780       m_hash_code(const Key& k) const
781       { return m_h1(k); }
782       
783       std::size_t
784       bucket_index(const Key&, hash_code_t c, std::size_t N) const
785       { return m_h2(c, N); }
786
787       std::size_t
788       bucket_index(const hash_node<Value, false>* p, std::size_t N) const
789       { return m_h2(m_h1(m_extract(p->m_v)), N); }
790
791       bool
792       compare(const Key& k, hash_code_t, hash_node<Value, false>* n) const
793       { return m_eq(k, m_extract(n->m_v)); }
794
795       void
796       store_code(hash_node<Value, false>*, hash_code_t) const
797       { }
798
799       void
800       copy_code(hash_node<Value, false>*, const hash_node<Value, false>*) const
801       { }
802
803       void
804       m_swap(hash_code_base& x)
805       {
806         std::swap(m_extract, x.m_extract);
807         std::swap(m_eq, x.m_eq);
808         std::swap(m_h1, x.m_h1);
809         std::swap(m_h2, x.m_h2);
810       }
811
812     protected:
813       ExtractKey m_extract;
814       Equal      m_eq;
815       H1         m_h1;
816       H2         m_h2;
817     };
818
819   // Specialization: hash function and range-hashing function, 
820   // caching hash codes.  H is provided but ignored.  Provides
821   // typedef and accessor required by TR1.
822   template<typename Key, typename Value,
823            typename ExtractKey, typename Equal,
824            typename H1, typename H2>
825     struct hash_code_base<Key, Value, ExtractKey, Equal, H1, H2,
826                           default_ranged_hash, true>
827     {
828       typedef H1 hasher;
829       
830       hasher
831       hash_function() const
832       { return m_h1; }
833
834     protected:
835       hash_code_base(const ExtractKey& ex, const Equal& eq,
836                      const H1& h1, const H2& h2, const default_ranged_hash&)
837       : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { }
838
839       typedef std::size_t hash_code_t;
840   
841       hash_code_t
842       m_hash_code(const Key& k) const
843       { return m_h1(k); }
844   
845       std::size_t
846       bucket_index(const Key&, hash_code_t c, std::size_t N) const
847       { return m_h2(c, N); }
848
849       std::size_t
850       bucket_index(const hash_node<Value, true>* p, std::size_t N) const
851       { return m_h2(p->hash_code, N); }
852
853       bool
854       compare(const Key& k, hash_code_t c, hash_node<Value, true>* n) const
855       { return c == n->hash_code && m_eq(k, m_extract(n->m_v)); }
856
857       void
858       store_code(hash_node<Value, true>* n, hash_code_t c) const
859       { n->hash_code = c; }
860
861       void
862       copy_code(hash_node<Value, true>* to,
863                 const hash_node<Value, true>* from) const
864       { to->hash_code = from->hash_code; }
865
866       void
867       m_swap(hash_code_base& x)
868       {
869         std::swap(m_extract, x.m_extract);
870         std::swap(m_eq, x.m_eq);
871         std::swap(m_h1, x.m_h1);
872         std::swap(m_h2, x.m_h2);
873       }
874       
875     protected:
876       ExtractKey m_extract;
877       Equal      m_eq;
878       H1         m_h1;
879       H2         m_h2;
880     };
881
882 } // namespace internal
883
884 namespace std
885
886 _GLIBCXX_BEGIN_NAMESPACE(tr1)
887
888   //----------------------------------------------------------------------
889   // Class template hashtable, class definition.
890   
891   // Meaning of class template hashtable's template parameters
892   
893   // Key and Value: arbitrary CopyConstructible types.
894   
895   // Allocator: an allocator type ([lib.allocator.requirements]) whose
896   // value type is Value.
897   
898   // ExtractKey: function object that takes a object of type Value
899   // and returns a value of type Key.
900   
901   // Equal: function object that takes two objects of type k and returns
902   // a bool-like value that is true if the two objects are considered equal.
903   
904   // H1: the hash function.  A unary function object with argument type
905   // Key and result type size_t.  Return values should be distributed
906   // over the entire range [0, numeric_limits<size_t>:::max()].
907   
908   // H2: the range-hashing function (in the terminology of Tavori and
909   // Dreizin).  A binary function object whose argument types and result
910   // type are all size_t.  Given arguments r and N, the return value is
911   // in the range [0, N).
912   
913   // H: the ranged hash function (Tavori and Dreizin). A binary function
914   // whose argument types are Key and size_t and whose result type is
915   // size_t.  Given arguments k and N, the return value is in the range
916   // [0, N).  Default: h(k, N) = h2(h1(k), N).  If H is anything other
917   // than the default, H1 and H2 are ignored.
918   
919   // RehashPolicy: Policy class with three members, all of which govern
920   // the bucket count. n_bkt(n) returns a bucket count no smaller
921   // than n.  bkt_for_elements(n) returns a bucket count appropriate
922   // for an element count of n.  need_rehash(n_bkt, n_elt, n_ins)
923   // determines whether, if the current bucket count is n_bkt and the
924   // current element count is n_elt, we need to increase the bucket
925   // count.  If so, returns make_pair(true, n), where n is the new
926   // bucket count.  If not, returns make_pair(false, <anything>).
927   
928   // ??? Right now it is hard-wired that the number of buckets never
929   // shrinks.  Should we allow RehashPolicy to change that?
930   
931   // cache_hash_code: bool.  true if we store the value of the hash
932   // function along with the value.  This is a time-space tradeoff.
933   // Storing it may improve lookup speed by reducing the number of times
934   // we need to call the Equal function.
935   
936   // constant_iterators: bool.  true if iterator and const_iterator are
937   // both constant iterator types.  This is true for unordered_set and
938   // unordered_multiset, false for unordered_map and unordered_multimap.
939   
940   // unique_keys: bool.  true if the return value of hashtable::count(k)
941   // is always at most one, false if it may be an arbitrary number.  This
942   // true for unordered_set and unordered_map, false for unordered_multiset
943   // and unordered_multimap.
944   
945   template<typename Key, typename Value, 
946            typename Allocator,
947            typename ExtractKey, typename Equal,
948            typename H1, typename H2,
949            typename H, typename RehashPolicy,
950            bool cache_hash_code,
951            bool constant_iterators,
952            bool unique_keys>
953     class hashtable
954     : public Internal::rehash_base<RehashPolicy,
955                                    hashtable<Key, Value, Allocator, ExtractKey,
956                                              Equal, H1, H2, H, RehashPolicy,
957                                              cache_hash_code, constant_iterators,
958                                              unique_keys> >,
959       public Internal::hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H,
960                                       cache_hash_code>,
961       public Internal::map_base<Key, Value, ExtractKey, unique_keys,
962                                 hashtable<Key, Value, Allocator, ExtractKey,
963                                           Equal, H1, H2, H, RehashPolicy,
964                                           cache_hash_code, constant_iterators,
965                                           unique_keys> >
966     {
967     public:
968       typedef Allocator                                   allocator_type;
969       typedef Value                                       value_type;
970       typedef Key                                         key_type;
971       typedef Equal                                       key_equal;
972       // mapped_type, if present, comes from map_base.
973       // hasher, if present, comes from hash_code_base.
974       typedef typename Allocator::difference_type         difference_type;
975       typedef typename Allocator::size_type               size_type;
976       typedef typename Allocator::reference               reference;
977       typedef typename Allocator::const_reference         const_reference;
978       
979       typedef Internal::node_iterator<value_type, constant_iterators,
980                                       cache_hash_code>
981                                                           local_iterator;
982       typedef Internal::node_const_iterator<value_type, constant_iterators,
983                                             cache_hash_code>
984                                                           const_local_iterator;
985
986       typedef Internal::hashtable_iterator<value_type, constant_iterators,
987                                            cache_hash_code>
988                                                           iterator;
989       typedef Internal::hashtable_const_iterator<value_type, constant_iterators,
990                                                  cache_hash_code>
991                                                           const_iterator;
992
993     private:
994       typedef Internal::hash_node<Value, cache_hash_code> node;
995       typedef typename Allocator::template rebind<node>::other
996                                                           node_allocator_t;
997       typedef typename Allocator::template rebind<node*>::other
998                                                           bucket_allocator_t;
999
1000     private:
1001       node_allocator_t      m_node_allocator;
1002       node**                m_buckets;
1003       size_type             m_bucket_count;
1004       size_type             m_element_count;
1005       RehashPolicy          m_rehash_policy;
1006       
1007       node*
1008       m_allocate_node(const value_type& v);
1009   
1010       void
1011       m_deallocate_node(node* n);
1012   
1013       void
1014       m_deallocate_nodes(node**, size_type);
1015
1016       node**
1017       m_allocate_buckets(size_type n);
1018   
1019       void
1020       m_deallocate_buckets(node**, size_type n);
1021
1022     public:                         // Constructor, destructor, assignment, swap
1023       hashtable(size_type bucket_hint,
1024                 const H1&, const H2&, const H&,
1025                 const Equal&, const ExtractKey&,
1026                 const allocator_type&);
1027   
1028       template<typename InIter>
1029         hashtable(InIter first, InIter last,
1030                   size_type bucket_hint,
1031                   const H1&, const H2&, const H&, 
1032                   const Equal&, const ExtractKey&,
1033                   const allocator_type&);
1034   
1035       hashtable(const hashtable&);
1036       
1037       hashtable&
1038       operator=(const hashtable&);
1039   
1040       ~hashtable();
1041
1042       void swap(hashtable&);
1043
1044     public:                             // Basic container operations
1045       iterator
1046       begin()
1047       {
1048         iterator i(m_buckets);
1049         if (!i.m_cur_node)
1050           i.m_incr_bucket();
1051         return i;
1052       }
1053
1054       const_iterator
1055       begin() const
1056       {
1057         const_iterator i(m_buckets);
1058         if (!i.m_cur_node)
1059           i.m_incr_bucket();
1060         return i;
1061       }
1062
1063       iterator
1064       end()
1065       { return iterator(m_buckets + m_bucket_count); }
1066
1067       const_iterator
1068       end() const
1069       { return const_iterator(m_buckets + m_bucket_count); }
1070
1071       size_type
1072       size() const
1073       { return m_element_count; }
1074   
1075       bool
1076       empty() const
1077       { return size() == 0; }
1078
1079       allocator_type
1080       get_allocator() const
1081       { return m_node_allocator; }
1082   
1083       size_type
1084       max_size() const
1085       { return m_node_allocator.max_size(); }
1086
1087     public:                             // Observers
1088       key_equal
1089       key_eq() const
1090       { return this->m_eq; }
1091
1092       // hash_function, if present, comes from hash_code_base.
1093
1094     public:                             // Bucket operations
1095       size_type
1096       bucket_count() const
1097       { return m_bucket_count; }
1098   
1099       size_type
1100       max_bucket_count() const
1101       { return max_size(); }
1102   
1103       size_type
1104       bucket_size(size_type n) const
1105       { return std::distance(begin(n), end(n)); }
1106   
1107       size_type
1108       bucket(const key_type& k) const
1109       { 
1110         return this->bucket_index(k, this->m_hash_code(k),
1111                                   this->m_bucket_count);
1112       }
1113
1114       local_iterator
1115       begin(size_type n)
1116       { return local_iterator(m_buckets[n]); }
1117   
1118       local_iterator
1119       end(size_type)
1120       { return local_iterator(0); }
1121   
1122       const_local_iterator
1123       begin(size_type n) const
1124       { return const_local_iterator(m_buckets[n]); }
1125   
1126       const_local_iterator
1127       end(size_type) const
1128       { return const_local_iterator(0); }
1129
1130       float
1131       load_factor() const
1132       { 
1133         return static_cast<float>(size()) / static_cast<float>(bucket_count());
1134       }
1135
1136       // max_load_factor, if present, comes from rehash_base.
1137
1138       // Generalization of max_load_factor.  Extension, not found in TR1.  Only
1139       // useful if RehashPolicy is something other than the default.
1140       const RehashPolicy&
1141       rehash_policy() const
1142       { return m_rehash_policy; }
1143       
1144       void 
1145       rehash_policy(const RehashPolicy&);
1146
1147     public:                             // lookup
1148       iterator
1149       find(const key_type&);
1150
1151       const_iterator
1152       find(const key_type& k) const;
1153
1154       size_type
1155       count(const key_type& k) const;
1156
1157       std::pair<iterator, iterator>
1158       equal_range(const key_type& k);
1159
1160       std::pair<const_iterator, const_iterator>
1161       equal_range(const key_type& k) const;
1162
1163     private:                    // Insert and erase helper functions
1164       // ??? This dispatching is a workaround for the fact that we don't
1165       // have partial specialization of member templates; it would be
1166       // better to just specialize insert on unique_keys.  There may be a
1167       // cleaner workaround.
1168       typedef typename Internal::IF<unique_keys,
1169                                     std::pair<iterator, bool>, iterator>::type
1170         Insert_Return_Type;
1171
1172       typedef typename Internal::IF<unique_keys,
1173                                     Internal::extract1st<Insert_Return_Type>,
1174                                     Internal::identity<Insert_Return_Type>
1175                                    >::type
1176         Insert_Conv_Type;
1177
1178       node*
1179       find_node(node* p, const key_type& k,
1180                 typename hashtable::hash_code_t c) const;
1181
1182       std::pair<iterator, bool>
1183       insert(const value_type&, std::tr1::true_type);
1184   
1185       iterator
1186       insert(const value_type&, std::tr1::false_type);
1187
1188       void
1189       erase_node(node*, node**);
1190
1191     public:                             // Insert and erase
1192       Insert_Return_Type
1193       insert(const value_type& v) 
1194       { 
1195         return this->insert(v, std::tr1::integral_constant<bool,
1196                             unique_keys>());
1197       }
1198
1199       iterator
1200       insert(iterator, const value_type& v)
1201       { return iterator(Insert_Conv_Type()(this->insert(v))); }
1202       
1203       const_iterator
1204       insert(const_iterator, const value_type& v)
1205       { return const_iterator(Insert_Conv_Type()(this->insert(v))); }
1206
1207       template<typename InIter>
1208         void
1209         insert(InIter first, InIter last);
1210
1211       iterator
1212       erase(iterator);
1213
1214       const_iterator
1215       erase(const_iterator);
1216
1217       size_type
1218       erase(const key_type&);
1219
1220       iterator
1221       erase(iterator, iterator);
1222
1223       const_iterator
1224       erase(const_iterator, const_iterator);
1225
1226       void
1227       clear();
1228
1229     public:
1230       // Set number of buckets to be appropriate for container of n element.
1231       void rehash(size_type n);
1232       
1233     private:
1234       // Unconditionally change size of bucket array to n.
1235       void m_rehash(size_type n);
1236     };
1237
1238
1239   //----------------------------------------------------------------------
1240   // Definitions of class template hashtable's out-of-line member functions.
1241
1242   template<typename K, typename V, 
1243            typename A, typename Ex, typename Eq,
1244            typename H1, typename H2, typename H, typename RP,
1245            bool c, bool ci, bool u>
1246     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node*
1247     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1248     m_allocate_node(const value_type& v)
1249     {
1250       node* n = m_node_allocator.allocate(1);
1251       try
1252         {
1253           get_allocator().construct(&n->m_v, v);
1254           n->m_next = 0;
1255           return n;
1256         }
1257       catch(...)
1258         {
1259           m_node_allocator.deallocate(n, 1);
1260           __throw_exception_again;
1261         }
1262     }
1263
1264   template<typename K, typename V, 
1265            typename A, typename Ex, typename Eq,
1266            typename H1, typename H2, typename H, typename RP,
1267            bool c, bool ci, bool u>
1268     void
1269     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1270     m_deallocate_node(node* n)
1271     {
1272       get_allocator().destroy(&n->m_v);
1273       m_node_allocator.deallocate(n, 1);
1274     }
1275
1276   template<typename K, typename V, 
1277            typename A, typename Ex, typename Eq,
1278            typename H1, typename H2, typename H, typename RP,
1279            bool c, bool ci, bool u>
1280     void
1281     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1282     m_deallocate_nodes(node** array, size_type n)
1283     {
1284       for (size_type i = 0; i < n; ++i)
1285         {
1286           node* p = array[i];
1287           while (p)
1288             {
1289               node* tmp = p;
1290               p = p->m_next;
1291               m_deallocate_node(tmp);
1292             }
1293           array[i] = 0;
1294         }
1295     }
1296
1297   template<typename K, typename V, 
1298            typename A, typename Ex, typename Eq,
1299            typename H1, typename H2, typename H, typename RP,
1300            bool c, bool ci, bool u>
1301     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node**
1302     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1303     m_allocate_buckets(size_type n)
1304     {
1305       bucket_allocator_t alloc(m_node_allocator);
1306
1307       // We allocate one extra bucket to hold a sentinel, an arbitrary
1308       // non-null pointer.  Iterator increment relies on this.
1309       node** p = alloc.allocate(n + 1);
1310       std::fill(p, p + n, (node*) 0);
1311       p[n] = reinterpret_cast<node*>(0x1000);
1312       return p;
1313     }
1314
1315   template<typename K, typename V, 
1316            typename A, typename Ex, typename Eq,
1317            typename H1, typename H2, typename H, typename RP,
1318            bool c, bool ci, bool u>
1319     void
1320     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1321     m_deallocate_buckets(node** p, size_type n)
1322     {
1323       bucket_allocator_t alloc(m_node_allocator);
1324       alloc.deallocate(p, n + 1);
1325     }
1326
1327   template<typename K, typename V, 
1328            typename A, typename Ex, typename Eq,
1329            typename H1, typename H2, typename H, typename RP,
1330            bool c, bool ci, bool u>
1331     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1332     hashtable(size_type bucket_hint,
1333               const H1& h1, const H2& h2, const H& h,
1334               const Eq& eq, const Ex& exk,
1335               const allocator_type& a)
1336     : Internal::rehash_base<RP, hashtable>(),
1337       Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq, h1, h2, h),
1338       Internal::map_base<K, V, Ex, u, hashtable>(),
1339       m_node_allocator(a),
1340       m_bucket_count(0),
1341       m_element_count(0),
1342       m_rehash_policy()
1343     {
1344       m_bucket_count = m_rehash_policy.next_bkt(bucket_hint);
1345       m_buckets = m_allocate_buckets(m_bucket_count);
1346     }
1347
1348   template<typename K, typename V, 
1349            typename A, typename Ex, typename Eq,
1350            typename H1, typename H2, typename H, typename RP,
1351            bool c, bool ci, bool u>
1352     template<typename InIter>
1353       hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1354       hashtable(InIter f, InIter l,
1355                 size_type bucket_hint,
1356                 const H1& h1, const H2& h2, const H& h,
1357                 const Eq& eq, const Ex& exk,
1358                 const allocator_type& a)
1359       : Internal::rehash_base<RP, hashtable>(),
1360         Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq,
1361                                                              h1, h2, h),
1362         Internal::map_base<K, V, Ex, u, hashtable>(),
1363         m_node_allocator(a),
1364         m_bucket_count(0),
1365         m_element_count(0),
1366         m_rehash_policy()
1367       {
1368         m_bucket_count = std::max(m_rehash_policy.next_bkt(bucket_hint),
1369                                   m_rehash_policy.
1370                                   bkt_for_elements(Internal::
1371                                                    distance_fw(f, l)));
1372         m_buckets = m_allocate_buckets(m_bucket_count);
1373         try
1374           {
1375             for (; f != l; ++f)
1376               this->insert(*f);
1377           }
1378         catch(...)
1379           {
1380             clear();
1381             m_deallocate_buckets(m_buckets, m_bucket_count);
1382             __throw_exception_again;
1383           }
1384       }
1385   
1386   template<typename K, typename V, 
1387            typename A, typename Ex, typename Eq,
1388            typename H1, typename H2, typename H, typename RP,
1389            bool c, bool ci, bool u>
1390     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1391     hashtable(const hashtable& ht)
1392     : Internal::rehash_base<RP, hashtable>(ht),
1393       Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(ht),
1394       Internal::map_base<K, V, Ex, u, hashtable>(ht),
1395       m_node_allocator(ht.get_allocator()),
1396       m_bucket_count(ht.m_bucket_count),
1397       m_element_count(ht.m_element_count),
1398       m_rehash_policy(ht.m_rehash_policy)
1399     {
1400       m_buckets = m_allocate_buckets(m_bucket_count);
1401       try
1402         {
1403           for (size_type i = 0; i < ht.m_bucket_count; ++i)
1404             {
1405               node* n = ht.m_buckets[i];
1406               node** tail = m_buckets + i;
1407               while (n)
1408                 {
1409                   *tail = m_allocate_node(n->m_v);
1410                   this->copy_code(*tail, n);
1411                   tail = &((*tail)->m_next);
1412                   n = n->m_next;
1413                 }
1414             }
1415         }
1416       catch(...)
1417         {
1418           clear();
1419           m_deallocate_buckets(m_buckets, m_bucket_count);
1420           __throw_exception_again;
1421         }
1422     }
1423
1424   template<typename K, typename V, 
1425            typename A, typename Ex, typename Eq,
1426            typename H1, typename H2, typename H, typename RP,
1427            bool c, bool ci, bool u>
1428     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>&
1429     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1430     operator=(const hashtable& ht)
1431     {
1432       hashtable tmp(ht);
1433       this->swap(tmp);
1434       return *this;
1435     }
1436
1437   template<typename K, typename V, 
1438            typename A, typename Ex, typename Eq,
1439            typename H1, typename H2, typename H, typename RP,
1440            bool c, bool ci, bool u>
1441     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1442     ~hashtable()
1443     {
1444       clear();
1445       m_deallocate_buckets(m_buckets, m_bucket_count);
1446     }
1447
1448   template<typename K, typename V, 
1449            typename A, typename Ex, typename Eq,
1450            typename H1, typename H2, typename H, typename RP,
1451            bool c, bool ci, bool u>
1452     void
1453     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1454     swap(hashtable& x)
1455     {
1456       // The only base class with member variables is hash_code_base.  We
1457       // define hash_code_base::m_swap because different specializations
1458       // have different members.
1459       Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>::m_swap(x);
1460
1461       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1462       // 431. Swapping containers with unequal allocators.
1463       std::__alloc_swap<node_allocator_t>::_S_do_it(m_node_allocator,
1464                                                     x.m_node_allocator);
1465
1466       std::swap(m_rehash_policy, x.m_rehash_policy);
1467       std::swap(m_buckets, x.m_buckets);
1468       std::swap(m_bucket_count, x.m_bucket_count);
1469       std::swap(m_element_count, x.m_element_count);
1470     }
1471
1472   template<typename K, typename V, 
1473            typename A, typename Ex, typename Eq,
1474            typename H1, typename H2, typename H, typename RP,
1475            bool c, bool ci, bool u>
1476     void
1477     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1478     rehash_policy(const RP& pol)
1479     {
1480       m_rehash_policy = pol;
1481       size_type n_bkt = pol.bkt_for_elements(m_element_count);
1482       if (n_bkt > m_bucket_count)
1483         m_rehash(n_bkt);
1484     }
1485
1486   template<typename K, typename V, 
1487            typename A, typename Ex, typename Eq,
1488            typename H1, typename H2, typename H, typename RP,
1489            bool c, bool ci, bool u>
1490     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
1491     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1492     find(const key_type& k)
1493     {
1494       typename hashtable::hash_code_t code = this->m_hash_code(k);
1495       std::size_t n = this->bucket_index(k, code, this->bucket_count());
1496       node* p = find_node(m_buckets[n], k, code);
1497       return p ? iterator(p, m_buckets + n) : this->end();
1498     }
1499   
1500   template<typename K, typename V, 
1501            typename A, typename Ex, typename Eq,
1502            typename H1, typename H2, typename H, typename RP,
1503            bool c, bool ci, bool u>
1504     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
1505     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1506     find(const key_type& k) const
1507     {
1508       typename hashtable::hash_code_t code = this->m_hash_code(k);
1509       std::size_t n = this->bucket_index(k, code, this->bucket_count());
1510       node* p = find_node(m_buckets[n], k, code);
1511       return p ? const_iterator(p, m_buckets + n) : this->end();
1512     }
1513   
1514   template<typename K, typename V, 
1515            typename A, typename Ex, typename Eq,
1516            typename H1, typename H2, typename H, typename RP,
1517            bool c, bool ci, bool u>
1518     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::size_type
1519     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1520     count(const key_type& k) const
1521     {
1522       typename hashtable::hash_code_t code = this->m_hash_code(k);
1523       std::size_t n = this->bucket_index(k, code, this->bucket_count());
1524       std::size_t result = 0;
1525       for (node* p = m_buckets[n]; p; p = p->m_next)
1526         if (this->compare(k, code, p))
1527           ++result;
1528       return result;
1529     }
1530
1531   template<typename K, typename V, 
1532            typename A, typename Ex, typename Eq,
1533            typename H1, typename H2, typename H, typename RP,
1534            bool c, bool ci, bool u>
1535     std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
1536                                  H2, H, RP, c, ci, u>::iterator,
1537               typename hashtable<K, V, A, Ex, Eq, H1,
1538                                  H2, H, RP, c, ci, u>::iterator>
1539     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1540     equal_range(const key_type& k)
1541     {
1542       typename hashtable::hash_code_t code = this->m_hash_code(k);
1543       std::size_t n = this->bucket_index(k, code, this->bucket_count());
1544       node** head = m_buckets + n;
1545       node* p = find_node(*head, k, code);
1546       
1547       if (p)
1548         {
1549           node* p1 = p->m_next;
1550           for (; p1; p1 = p1->m_next)
1551             if (!this->compare(k, code, p1))
1552               break;
1553
1554           iterator first(p, head);
1555           iterator last(p1, head);
1556           if (!p1)
1557             last.m_incr_bucket();
1558           return std::make_pair(first, last);
1559         }
1560       else
1561         return std::make_pair(this->end(), this->end());
1562     }
1563
1564   template<typename K, typename V, 
1565            typename A, typename Ex, typename Eq,
1566            typename H1, typename H2, typename H, typename RP,
1567            bool c, bool ci, bool u>
1568     std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
1569                                  H2, H, RP, c, ci, u>::const_iterator,
1570               typename hashtable<K, V, A, Ex, Eq, H1,
1571                                  H2, H, RP, c, ci, u>::const_iterator>
1572     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1573     equal_range(const key_type& k) const
1574     {
1575       typename hashtable::hash_code_t code = this->m_hash_code(k);
1576       std::size_t n = this->bucket_index(k, code, this->bucket_count());
1577       node** head = m_buckets + n;
1578       node* p = find_node(*head, k, code);
1579
1580       if (p)
1581         {
1582           node* p1 = p->m_next;
1583           for (; p1; p1 = p1->m_next)
1584             if (!this->compare(k, code, p1))
1585               break;
1586
1587           const_iterator first(p, head);
1588           const_iterator last(p1, head);
1589           if (!p1)
1590             last.m_incr_bucket();
1591           return std::make_pair(first, last);
1592         }
1593       else
1594         return std::make_pair(this->end(), this->end());
1595     }
1596
1597   // Find the node whose key compares equal to k, beginning the search
1598   // at p (usually the head of a bucket).  Return nil if no node is found.
1599   template<typename K, typename V, 
1600            typename A, typename Ex, typename Eq,
1601            typename H1, typename H2, typename H, typename RP,
1602            bool c, bool ci, bool u>
1603     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node* 
1604     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1605     find_node(node* p, const key_type& k,
1606               typename hashtable::hash_code_t code) const
1607     {
1608       for (; p; p = p->m_next)
1609         if (this->compare(k, code, p))
1610           return p;
1611       return false;
1612     }
1613
1614   // Insert v if no element with its key is already present.
1615   template<typename K, typename V, 
1616            typename A, typename Ex, typename Eq,
1617            typename H1, typename H2, typename H, typename RP,
1618            bool c, bool ci, bool u>
1619     std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
1620                                  H2, H, RP, c, ci, u>::iterator, bool>
1621     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1622     insert(const value_type& v, std::tr1::true_type)
1623     {
1624       const key_type& k = this->m_extract(v);
1625       typename hashtable::hash_code_t code = this->m_hash_code(k);
1626       std::size_t n = this->bucket_index(k, code, m_bucket_count);
1627       
1628       if (node* p = find_node(m_buckets[n], k, code))
1629         return std::make_pair(iterator(p, m_buckets + n), false);
1630
1631       std::pair<bool, std::size_t> do_rehash
1632         = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);
1633
1634       // Allocate the new node before doing the rehash so that we don't
1635       // do a rehash if the allocation throws.
1636       node* new_node = m_allocate_node(v);
1637       
1638       try
1639         {
1640           if (do_rehash.first)
1641             {
1642               n = this->bucket_index(k, code, do_rehash.second);
1643               m_rehash(do_rehash.second);
1644             }
1645
1646           new_node->m_next = m_buckets[n];
1647           this->store_code(new_node, code);
1648           m_buckets[n] = new_node;
1649           ++m_element_count;
1650           return std::make_pair(iterator(new_node, m_buckets + n), true);
1651         }
1652       catch(...)
1653         {
1654           m_deallocate_node(new_node);
1655           __throw_exception_again;
1656         }
1657     }
1658   
1659   // Insert v unconditionally.
1660   template<typename K, typename V, 
1661            typename A, typename Ex, typename Eq,
1662            typename H1, typename H2, typename H, typename RP,
1663            bool c, bool ci, bool u>
1664     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
1665     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1666     insert(const value_type& v, std::tr1::false_type)
1667     {
1668       std::pair<bool, std::size_t> do_rehash
1669         = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);
1670       if (do_rehash.first)
1671         m_rehash(do_rehash.second);
1672
1673       const key_type& k = this->m_extract(v);
1674       typename hashtable::hash_code_t code = this->m_hash_code(k);
1675       std::size_t n = this->bucket_index(k, code, m_bucket_count);
1676       
1677       node* new_node = m_allocate_node(v);
1678       node* prev = find_node(m_buckets[n], k, code);
1679       if (prev)
1680         {
1681           new_node->m_next = prev->m_next;
1682           prev->m_next = new_node;
1683         }
1684       else
1685         {
1686           new_node->m_next = m_buckets[n];
1687           m_buckets[n] = new_node;
1688         }
1689       this->store_code(new_node, code);
1690
1691       ++m_element_count;
1692       return iterator(new_node, m_buckets + n);
1693     }
1694
1695   // For erase(iterator) and erase(const_iterator).
1696   template<typename K, typename V, 
1697            typename A, typename Ex, typename Eq,
1698            typename H1, typename H2, typename H, typename RP,
1699            bool c, bool ci, bool u>
1700     void
1701     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1702     erase_node(node* p, node** b)
1703     {
1704       node* cur = *b;
1705       if (cur == p)
1706         *b = cur->m_next;
1707       else
1708         {
1709           node* next = cur->m_next;
1710           while (next != p)
1711             {
1712               cur = next;
1713               next = cur->m_next;
1714             }
1715           cur->m_next = next->m_next;
1716         }
1717
1718       m_deallocate_node(p);
1719       --m_element_count;
1720     }
1721
1722   template<typename K, typename V, 
1723            typename A, typename Ex, typename Eq,
1724            typename H1, typename H2, typename H, typename RP,
1725            bool c, bool ci, bool u>
1726     template<typename InIter>
1727       void 
1728       hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1729       insert(InIter first, InIter last)
1730       {
1731         size_type n_elt = Internal::distance_fw(first, last);
1732         std::pair<bool, std::size_t> do_rehash
1733           = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, n_elt);
1734         if (do_rehash.first)
1735           m_rehash(do_rehash.second);
1736
1737         for (; first != last; ++first)
1738           this->insert(*first);
1739       }
1740
1741   template<typename K, typename V, 
1742            typename A, typename Ex, typename Eq,
1743            typename H1, typename H2, typename H, typename RP,
1744            bool c, bool ci, bool u>
1745     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
1746     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1747     erase(iterator i)
1748     {
1749       iterator result = i;
1750       ++result;
1751       erase_node(i.m_cur_node, i.m_cur_bucket);
1752       return result;
1753     }
1754   
1755   template<typename K, typename V, 
1756            typename A, typename Ex, typename Eq,
1757            typename H1, typename H2, typename H, typename RP,
1758            bool c, bool ci, bool u>
1759     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
1760     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1761     erase(const_iterator i)
1762     {
1763       const_iterator result = i;
1764       ++result;
1765       erase_node(i.m_cur_node, i.m_cur_bucket);
1766       return result;
1767     }
1768
1769   template<typename K, typename V, 
1770            typename A, typename Ex, typename Eq,
1771            typename H1, typename H2, typename H, typename RP,
1772            bool c, bool ci, bool u>
1773     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::size_type
1774     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1775     erase(const key_type& k)
1776     {
1777       typename hashtable::hash_code_t code = this->m_hash_code(k);
1778       std::size_t n = this->bucket_index(k, code, m_bucket_count);
1779       size_type result = 0;
1780       
1781       node** slot = m_buckets + n;
1782       while (*slot && !this->compare(k, code, *slot))
1783         slot = &((*slot)->m_next);
1784
1785       while (*slot && this->compare(k, code, *slot))
1786         {
1787           node* p = *slot;
1788           *slot = p->m_next;
1789           m_deallocate_node(p);
1790           --m_element_count;
1791           ++result;
1792         }
1793
1794       return result;
1795     }
1796
1797   // ??? This could be optimized by taking advantage of the bucket
1798   // structure, but it's not clear that it's worth doing.  It probably
1799   // wouldn't even be an optimization unless the load factor is large.
1800   template<typename K, typename V, 
1801            typename A, typename Ex, typename Eq,
1802            typename H1, typename H2, typename H, typename RP,
1803            bool c, bool ci, bool u>
1804     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
1805     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1806     erase(iterator first, iterator last)
1807     {
1808       while (first != last)
1809         first = this->erase(first);
1810       return last;
1811     }
1812   
1813   template<typename K, typename V, 
1814            typename A, typename Ex, typename Eq,
1815            typename H1, typename H2, typename H, typename RP,
1816            bool c, bool ci, bool u>
1817     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
1818     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1819     erase(const_iterator first, const_iterator last)
1820     {
1821       while (first != last)
1822         first = this->erase(first);
1823       return last;
1824     }
1825
1826   template<typename K, typename V, 
1827            typename A, typename Ex, typename Eq,
1828            typename H1, typename H2, typename H, typename RP,
1829            bool c, bool ci, bool u>
1830     void
1831     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1832     clear()
1833     {
1834       m_deallocate_nodes(m_buckets, m_bucket_count);
1835       m_element_count = 0;
1836     }
1837  
1838   template<typename K, typename V, 
1839            typename A, typename Ex, typename Eq,
1840            typename H1, typename H2, typename H, typename RP,
1841            bool c, bool ci, bool u>
1842     void
1843     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1844     rehash(size_type n)
1845     {
1846       m_rehash(std::max(m_rehash_policy.next_bkt(n),
1847                         m_rehash_policy.bkt_for_elements(m_element_count
1848                                                          + 1)));
1849     }
1850
1851   template<typename K, typename V, 
1852            typename A, typename Ex, typename Eq,
1853            typename H1, typename H2, typename H, typename RP,
1854            bool c, bool ci, bool u>
1855     void
1856     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1857     m_rehash(size_type n)
1858     {
1859       node** new_array = m_allocate_buckets(n);
1860       try
1861         {
1862           for (size_type i = 0; i < m_bucket_count; ++i)
1863             while (node* p = m_buckets[i])
1864               {
1865                 std::size_t new_index = this->bucket_index(p, n);
1866                 m_buckets[i] = p->m_next;
1867                 p->m_next = new_array[new_index];
1868                 new_array[new_index] = p;
1869               }
1870           m_deallocate_buckets(m_buckets, m_bucket_count);
1871           m_bucket_count = n;
1872           m_buckets = new_array;
1873         }
1874       catch(...)
1875         {
1876           // A failure here means that a hash function threw an exception.
1877           // We can't restore the previous state without calling the hash
1878           // function again, so the only sensible recovery is to delete
1879           // everything.
1880           m_deallocate_nodes(new_array, n);
1881           m_deallocate_buckets(new_array, n);
1882           m_deallocate_nodes(m_buckets, m_bucket_count);
1883           m_element_count = 0;
1884           __throw_exception_again;
1885         }
1886     }
1887
1888 _GLIBCXX_END_NAMESPACE
1889 }                               // Namespace std::tr1
1890
1891 #endif /* GNU_LIBSTDCXX_TR1_HASHTABLE_ */
1892