OSDN Git Service

ac3658f0148a85708aef5e52984c967783e9d109
[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       // max_load_factor, if present, comes from rehash_base.
1136
1137       // Generalization of max_load_factor.  Extension, not found in TR1.  Only
1138       // useful if RehashPolicy is something other than the default.
1139       const RehashPolicy&
1140       rehash_policy() const
1141       { return m_rehash_policy; }
1142       
1143       void 
1144       rehash_policy(const RehashPolicy&);
1145
1146     public:                             // lookup
1147       iterator
1148       find(const key_type&);
1149
1150       const_iterator
1151       find(const key_type& k) const;
1152
1153       size_type
1154       count(const key_type& k) const;
1155
1156       std::pair<iterator, iterator>
1157       equal_range(const key_type& k);
1158
1159       std::pair<const_iterator, const_iterator>
1160       equal_range(const key_type& k) const;
1161
1162     private:                    // Insert and erase helper functions
1163       // ??? This dispatching is a workaround for the fact that we don't
1164       // have partial specialization of member templates; it would be
1165       // better to just specialize insert on unique_keys.  There may be a
1166       // cleaner workaround.
1167       typedef typename Internal::IF<unique_keys,
1168                                     std::pair<iterator, bool>, iterator>::type
1169         Insert_Return_Type;
1170
1171       typedef typename Internal::IF<unique_keys,
1172                                     Internal::extract1st<Insert_Return_Type>,
1173                                     Internal::identity<Insert_Return_Type>
1174                                    >::type
1175         Insert_Conv_Type;
1176
1177       node*
1178       find_node(node* p, const key_type& k,
1179                 typename hashtable::hash_code_t c) const;
1180
1181       std::pair<iterator, bool>
1182       insert(const value_type&, std::tr1::true_type);
1183   
1184       iterator
1185       insert(const value_type&, std::tr1::false_type);
1186
1187       void
1188       erase_node(node*, node**);
1189
1190     public:                             // Insert and erase
1191       Insert_Return_Type
1192       insert(const value_type& v) 
1193       { 
1194         return this->insert(v, std::tr1::integral_constant<bool,
1195                             unique_keys>());
1196       }
1197
1198       iterator
1199       insert(iterator, const value_type& v)
1200       { return iterator(Insert_Conv_Type()(this->insert(v))); }
1201       
1202       const_iterator
1203       insert(const_iterator, const value_type& v)
1204       { return const_iterator(Insert_Conv_Type()(this->insert(v))); }
1205
1206       template<typename InIter>
1207         void
1208         insert(InIter first, InIter last);
1209
1210       iterator
1211       erase(iterator);
1212
1213       const_iterator
1214       erase(const_iterator);
1215
1216       size_type
1217       erase(const key_type&);
1218
1219       iterator
1220       erase(iterator, iterator);
1221
1222       const_iterator
1223       erase(const_iterator, const_iterator);
1224
1225       void
1226       clear();
1227
1228     public:
1229       // Set number of buckets to be apropriate for container of n element.
1230       void rehash(size_type n);
1231       
1232     private:
1233       // Unconditionally change size of bucket array to n.
1234       void m_rehash(size_type n);
1235     };
1236
1237
1238   //----------------------------------------------------------------------
1239   // Definitions of class template hashtable's out-of-line member functions.
1240
1241   template<typename K, typename V, 
1242            typename A, typename Ex, typename Eq,
1243            typename H1, typename H2, typename H, typename RP,
1244            bool c, bool ci, bool u>
1245     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node*
1246     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1247     m_allocate_node(const value_type& v)
1248     {
1249       node* n = m_node_allocator.allocate(1);
1250       try
1251         {
1252           get_allocator().construct(&n->m_v, v);
1253           n->m_next = 0;
1254           return n;
1255         }
1256       catch(...)
1257         {
1258           m_node_allocator.deallocate(n, 1);
1259           __throw_exception_again;
1260         }
1261     }
1262
1263   template<typename K, typename V, 
1264            typename A, typename Ex, typename Eq,
1265            typename H1, typename H2, typename H, typename RP,
1266            bool c, bool ci, bool u>
1267     void
1268     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1269     m_deallocate_node(node* n)
1270     {
1271       get_allocator().destroy(&n->m_v);
1272       m_node_allocator.deallocate(n, 1);
1273     }
1274
1275   template<typename K, typename V, 
1276            typename A, typename Ex, typename Eq,
1277            typename H1, typename H2, typename H, typename RP,
1278            bool c, bool ci, bool u>
1279     void
1280     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1281     m_deallocate_nodes(node** array, size_type n)
1282     {
1283       for (size_type i = 0; i < n; ++i)
1284         {
1285           node* p = array[i];
1286           while (p)
1287             {
1288               node* tmp = p;
1289               p = p->m_next;
1290               m_deallocate_node(tmp);
1291             }
1292           array[i] = 0;
1293         }
1294     }
1295
1296   template<typename K, typename V, 
1297            typename A, typename Ex, typename Eq,
1298            typename H1, typename H2, typename H, typename RP,
1299            bool c, bool ci, bool u>
1300     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node**
1301     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1302     m_allocate_buckets(size_type n)
1303     {
1304       bucket_allocator_t alloc(m_node_allocator);
1305
1306       // We allocate one extra bucket to hold a sentinel, an arbitrary
1307       // non-null pointer.  Iterator increment relies on this.
1308       node** p = alloc.allocate(n + 1);
1309       std::fill(p, p+n, (node*) 0);
1310       p[n] = reinterpret_cast<node*>(0x1000);
1311       return p;
1312     }
1313
1314   template<typename K, typename V, 
1315            typename A, typename Ex, typename Eq,
1316            typename H1, typename H2, typename H, typename RP,
1317            bool c, bool ci, bool u>
1318     void
1319     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1320     m_deallocate_buckets(node** p, size_type n)
1321     {
1322       bucket_allocator_t alloc(m_node_allocator);
1323       alloc.deallocate(p, n+1);
1324     }
1325
1326   template<typename K, typename V, 
1327            typename A, typename Ex, typename Eq,
1328            typename H1, typename H2, typename H, typename RP,
1329            bool c, bool ci, bool u>
1330     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1331     hashtable(size_type bucket_hint,
1332               const H1& h1, const H2& h2, const H& h,
1333               const Eq& eq, const Ex& exk,
1334               const allocator_type& a)
1335     : Internal::rehash_base<RP, hashtable>(),
1336       Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(exk, eq, h1, h2, h),
1337       Internal::map_base<K, V, Ex, u, hashtable>(),
1338       m_node_allocator(a),
1339       m_bucket_count(0),
1340       m_element_count(0),
1341       m_rehash_policy()
1342     {
1343       m_bucket_count = m_rehash_policy.next_bkt(bucket_hint);
1344       m_buckets = m_allocate_buckets(m_bucket_count);
1345     }
1346
1347   template<typename K, typename V, 
1348            typename A, typename Ex, typename Eq,
1349            typename H1, typename H2, typename H, typename RP,
1350            bool c, bool ci, bool u>
1351     template<typename InIter>
1352       hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1353       hashtable(InIter f, InIter l,
1354                 size_type bucket_hint,
1355                 const H1& h1, const H2& h2, const H& h,
1356                 const Eq& eq, const Ex& exk,
1357                 const allocator_type& a)
1358       : Internal::rehash_base<RP, hashtable>(),
1359         Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c> (exk, eq,
1360                                                               h1, h2, h),
1361         Internal::map_base<K, V, Ex, u, hashtable>(),
1362         m_node_allocator(a),
1363         m_bucket_count (0),
1364         m_element_count(0),
1365         m_rehash_policy()
1366       {
1367         m_bucket_count = std::max(m_rehash_policy.next_bkt(bucket_hint),
1368                                   m_rehash_policy.
1369                                   bkt_for_elements(Internal::
1370                                                    distance_fw(f, l)));
1371         m_buckets = m_allocate_buckets(m_bucket_count);
1372         try
1373           {
1374             for (; f != l; ++f)
1375               this->insert(*f);
1376           }
1377         catch(...)
1378           {
1379             clear();
1380             m_deallocate_buckets(m_buckets, m_bucket_count);
1381             __throw_exception_again;
1382           }
1383       }
1384   
1385   template<typename K, typename V, 
1386            typename A, typename Ex, typename Eq,
1387            typename H1, typename H2, typename H, typename RP,
1388            bool c, bool ci, bool u>
1389     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1390     hashtable(const hashtable& ht)
1391     : Internal::rehash_base<RP, hashtable>(ht),
1392       Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>(ht),
1393       Internal::map_base<K, V, Ex, u, hashtable>(ht),
1394       m_node_allocator(ht.get_allocator()),
1395       m_bucket_count(ht.m_bucket_count),
1396       m_element_count(ht.m_element_count),
1397       m_rehash_policy(ht.m_rehash_policy)
1398     {
1399       m_buckets = m_allocate_buckets (m_bucket_count);
1400       try
1401         {
1402           for (size_t i = 0; i < ht.m_bucket_count; ++i)
1403             {
1404               node* n = ht.m_buckets[i];
1405               node** tail = m_buckets + i;
1406               while (n)
1407                 {
1408                   *tail = m_allocate_node(n->m_v);
1409                   this->copy_code(*tail, n);
1410                   tail = &((*tail)->m_next);
1411                   n = n->m_next;
1412                 }
1413             }
1414         }
1415       catch(...)
1416         {
1417           clear();
1418           m_deallocate_buckets (m_buckets, m_bucket_count);
1419           __throw_exception_again;
1420         }
1421     }
1422
1423   template<typename K, typename V, 
1424            typename A, typename Ex, typename Eq,
1425            typename H1, typename H2, typename H, typename RP,
1426            bool c, bool ci, bool u>
1427     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>&
1428     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1429     operator=(const hashtable& ht)
1430     {
1431       hashtable tmp(ht);
1432       this->swap(tmp);
1433       return *this;
1434     }
1435
1436   template<typename K, typename V, 
1437            typename A, typename Ex, typename Eq,
1438            typename H1, typename H2, typename H, typename RP,
1439            bool c, bool ci, bool u>
1440     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1441     ~hashtable()
1442     {
1443       clear();
1444       m_deallocate_buckets(m_buckets, m_bucket_count);
1445     }
1446
1447   template<typename K, typename V, 
1448            typename A, typename Ex, typename Eq,
1449            typename H1, typename H2, typename H, typename RP,
1450            bool c, bool ci, bool u>
1451     void
1452     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1453     swap(hashtable& x)
1454     {
1455       // The only base class with member variables is hash_code_base.  We
1456       // define hash_code_base::m_swap because different specializations
1457       // have different members.
1458       Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>::m_swap(x);
1459
1460       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1461       // 431. Swapping containers with unequal allocators.
1462       std::__alloc_swap<node_allocator_t>::_S_do_it(m_node_allocator,
1463                                                     x.m_node_allocator);
1464
1465       std::swap(m_rehash_policy, x.m_rehash_policy);
1466       std::swap(m_buckets, x.m_buckets);
1467       std::swap(m_bucket_count, x.m_bucket_count);
1468       std::swap(m_element_count, x.m_element_count);
1469     }
1470
1471   template<typename K, typename V, 
1472            typename A, typename Ex, typename Eq,
1473            typename H1, typename H2, typename H, typename RP,
1474            bool c, bool ci, bool u>
1475     void
1476     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1477     rehash_policy(const RP& pol)
1478     {
1479       m_rehash_policy = pol;
1480       size_type n_bkt = pol.bkt_for_elements(m_element_count);
1481       if (n_bkt > m_bucket_count)
1482         m_rehash(n_bkt);
1483     }
1484
1485   template<typename K, typename V, 
1486            typename A, typename Ex, typename Eq,
1487            typename H1, typename H2, typename H, typename RP,
1488            bool c, bool ci, bool u>
1489     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
1490     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1491     find(const key_type& k)
1492     {
1493       typename hashtable::hash_code_t code = this->m_hash_code(k);
1494       std::size_t n = this->bucket_index(k, code, this->bucket_count());
1495       node* p = find_node(m_buckets[n], k, code);
1496       return p ? iterator(p, m_buckets + n) : this->end();
1497     }
1498   
1499   template<typename K, typename V, 
1500            typename A, typename Ex, typename Eq,
1501            typename H1, typename H2, typename H, typename RP,
1502            bool c, bool ci, bool u>
1503     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
1504     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1505     find(const key_type& k) const
1506     {
1507       typename hashtable::hash_code_t code = this->m_hash_code(k);
1508       std::size_t n = this->bucket_index(k, code, this->bucket_count());
1509       node* p = find_node(m_buckets[n], k, code);
1510       return p ? const_iterator(p, m_buckets + n) : this->end();
1511     }
1512   
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     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::size_type
1518     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1519     count(const key_type& k) const
1520     {
1521       typename hashtable::hash_code_t code = this->m_hash_code(k);
1522       std::size_t n = this->bucket_index(k, code, this->bucket_count());
1523       size_t result = 0;
1524       for (node* p = m_buckets[n]; p; p = p->m_next)
1525         if (this->compare(k, code, p))
1526           ++result;
1527       return result;
1528     }
1529
1530   template<typename K, typename V, 
1531            typename A, typename Ex, typename Eq,
1532            typename H1, typename H2, typename H, typename RP,
1533            bool c, bool ci, bool u>
1534     std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
1535                                  H2, H, RP, c, ci, u>::iterator,
1536               typename hashtable<K, V, A, Ex, Eq, H1,
1537                                  H2, H, RP, c, ci, u>::iterator>
1538     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1539     equal_range(const key_type& k)
1540     {
1541       typename hashtable::hash_code_t code = this->m_hash_code(k);
1542       std::size_t n = this->bucket_index(k, code, this->bucket_count());
1543       node** head = m_buckets + n;
1544       node* p = find_node (*head, k, code);
1545       
1546       if (p)
1547         {
1548           node* p1 = p->m_next;
1549           for (; p1; p1 = p1->m_next)
1550             if (!this->compare(k, code, p1))
1551               break;
1552
1553           iterator first(p, head);
1554           iterator last(p1, head);
1555           if (!p1)
1556             last.m_incr_bucket();
1557           return std::make_pair(first, last);
1558         }
1559       else
1560         return std::make_pair(this->end(), this->end());
1561     }
1562
1563   template<typename K, typename V, 
1564            typename A, typename Ex, typename Eq,
1565            typename H1, typename H2, typename H, typename RP,
1566            bool c, bool ci, bool u>
1567     std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
1568                                  H2, H, RP, c, ci, u>::const_iterator,
1569               typename hashtable<K, V, A, Ex, Eq, H1,
1570                                  H2, H, RP, c, ci, u>::const_iterator>
1571     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1572     equal_range(const key_type& k) const
1573     {
1574       typename hashtable::hash_code_t code = this->m_hash_code(k);
1575       std::size_t n = this->bucket_index(k, code, this->bucket_count());
1576       node** head = m_buckets + n;
1577       node* p = find_node(*head, k, code);
1578
1579       if (p)
1580         {
1581           node* p1 = p->m_next;
1582           for (; p1; p1 = p1->m_next)
1583             if (!this->compare(k, code, p1))
1584               break;
1585
1586           const_iterator first(p, head);
1587           const_iterator last(p1, head);
1588           if (!p1)
1589             last.m_incr_bucket();
1590           return std::make_pair(first, last);
1591         }
1592       else
1593         return std::make_pair(this->end(), this->end());
1594     }
1595
1596   // Find the node whose key compares equal to k, beginning the search
1597   // at p (usually the head of a bucket).  Return nil if no node is found.
1598   template<typename K, typename V, 
1599            typename A, typename Ex, typename Eq,
1600            typename H1, typename H2, typename H, typename RP,
1601            bool c, bool ci, bool u>
1602     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::node* 
1603     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1604     find_node(node* p, const key_type& k,
1605               typename hashtable::hash_code_t code) const
1606     {
1607       for (; p ; p = p->m_next)
1608         if (this->compare(k, code, p))
1609           return p;
1610       return false;
1611     }
1612
1613   // Insert v if no element with its key is already present.
1614   template<typename K, typename V, 
1615            typename A, typename Ex, typename Eq,
1616            typename H1, typename H2, typename H, typename RP,
1617            bool c, bool ci, bool u>
1618     std::pair<typename hashtable<K, V, A, Ex, Eq, H1,
1619                                  H2, H, RP, c, ci, u>::iterator, bool>
1620     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1621     insert(const value_type& v, std::tr1::true_type)
1622     {
1623       const key_type& k = this->m_extract(v);
1624       typename hashtable::hash_code_t code = this->m_hash_code(k);
1625       size_type n = this->bucket_index(k, code, m_bucket_count);
1626       
1627       if (node* p = find_node(m_buckets[n], k, code))
1628         return std::make_pair(iterator(p, m_buckets + n), false);
1629
1630       std::pair<bool, size_t> do_rehash
1631         = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);
1632
1633       // Allocate the new node before doing the rehash so that we don't
1634       // do a rehash if the allocation throws.
1635       node* new_node = m_allocate_node(v);
1636       
1637       try
1638         {
1639           if (do_rehash.first)
1640             {
1641               n = this->bucket_index(k, code, do_rehash.second);
1642               m_rehash(do_rehash.second);
1643             }
1644
1645           new_node->m_next = m_buckets[n];
1646           this->store_code(new_node, code);
1647           m_buckets[n] = new_node;
1648           ++m_element_count;
1649           return std::make_pair(iterator(new_node, m_buckets + n), true);
1650         }
1651       catch(...)
1652         {
1653           m_deallocate_node(new_node);
1654           __throw_exception_again;
1655         }
1656     }
1657   
1658   // Insert v unconditionally.
1659   template<typename K, typename V, 
1660            typename A, typename Ex, typename Eq,
1661            typename H1, typename H2, typename H, typename RP,
1662            bool c, bool ci, bool u>
1663     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
1664     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1665     insert(const value_type& v, std::tr1::false_type)
1666     {
1667       std::pair<bool, std::size_t> do_rehash
1668         = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);
1669       if (do_rehash.first)
1670         m_rehash(do_rehash.second);
1671
1672       const key_type& k = this->m_extract(v);
1673       typename hashtable::hash_code_t code = this->m_hash_code(k);
1674       size_type n = this->bucket_index(k, code, m_bucket_count);
1675       
1676       node* new_node = m_allocate_node(v);
1677       node* prev = find_node(m_buckets[n], k, code);
1678       if (prev)
1679         {
1680           new_node->m_next = prev->m_next;
1681           prev->m_next = new_node;
1682         }
1683       else
1684         {
1685           new_node->m_next = m_buckets[n];
1686           m_buckets[n] = new_node;
1687         }
1688       this->store_code(new_node, code);
1689
1690       ++m_element_count;
1691       return iterator(new_node, m_buckets + n);
1692     }
1693
1694   // For erase(iterator) and erase(const_iterator).
1695   template<typename K, typename V, 
1696            typename A, typename Ex, typename Eq,
1697            typename H1, typename H2, typename H, typename RP,
1698            bool c, bool ci, bool u>
1699     void
1700     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1701     erase_node(node* p, node** b)
1702     {
1703       node* cur = *b;
1704       if (cur == p)
1705         *b = cur->m_next;
1706       else
1707         {
1708           node* next = cur->m_next;
1709           while (next != p)
1710             {
1711               cur = next;
1712               next = cur->m_next;
1713             }
1714           cur->m_next = next->m_next;
1715         }
1716
1717       m_deallocate_node(p);
1718       --m_element_count;
1719     }
1720
1721   template<typename K, typename V, 
1722            typename A, typename Ex, typename Eq,
1723            typename H1, typename H2, typename H, typename RP,
1724            bool c, bool ci, bool u>
1725     template<typename InIter>
1726       void 
1727       hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1728       insert(InIter first, InIter last)
1729       {
1730         size_type n_elt = Internal::distance_fw (first, last);
1731         std::pair<bool, std::size_t> do_rehash
1732           = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, n_elt);
1733         if (do_rehash.first)
1734           m_rehash(do_rehash.second);
1735
1736         for (; first != last; ++first)
1737           this->insert(*first);
1738       }
1739
1740   template<typename K, typename V, 
1741            typename A, typename Ex, typename Eq,
1742            typename H1, typename H2, typename H, typename RP,
1743            bool c, bool ci, bool u>
1744     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
1745     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1746     erase(iterator i)
1747     {
1748       iterator result = i;
1749       ++result;
1750       erase_node(i.m_cur_node, i.m_cur_bucket);
1751       return result;
1752     }
1753   
1754   template<typename K, typename V, 
1755            typename A, typename Ex, typename Eq,
1756            typename H1, typename H2, typename H, typename RP,
1757            bool c, bool ci, bool u>
1758     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
1759     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1760     erase(const_iterator i)
1761     {
1762       const_iterator result = i;
1763       ++result;
1764       erase_node(i.m_cur_node, i.m_cur_bucket);
1765       return result;
1766     }
1767
1768   template<typename K, typename V, 
1769            typename A, typename Ex, typename Eq,
1770            typename H1, typename H2, typename H, typename RP,
1771            bool c, bool ci, bool u>
1772     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::size_type
1773     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1774     erase(const key_type& k)
1775     {
1776       typename hashtable::hash_code_t code = this->m_hash_code(k);
1777       size_type n = this->bucket_index(k, code, m_bucket_count);
1778       size_type result = 0;
1779       
1780       node** slot = m_buckets + n;
1781       while (*slot && !this->compare(k, code, *slot))
1782         slot = &((*slot)->m_next);
1783
1784       while (*slot && this->compare(k, code, *slot))
1785         {
1786           node* n = *slot;
1787           *slot = n->m_next;
1788           m_deallocate_node(n);
1789           --m_element_count;
1790           ++result;
1791         }
1792
1793       return result;
1794     }
1795
1796   // ??? This could be optimized by taking advantage of the bucket
1797   // structure, but it's not clear that it's worth doing.  It probably
1798   // wouldn't even be an optimization unless the load factor is large.
1799   template<typename K, typename V, 
1800            typename A, typename Ex, typename Eq,
1801            typename H1, typename H2, typename H, typename RP,
1802            bool c, bool ci, bool u>
1803     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::iterator
1804     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1805     erase(iterator first, iterator last)
1806     {
1807       while (first != last)
1808         first = this->erase(first);
1809       return last;
1810     }
1811   
1812   template<typename K, typename V, 
1813            typename A, typename Ex, typename Eq,
1814            typename H1, typename H2, typename H, typename RP,
1815            bool c, bool ci, bool u>
1816     typename hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::const_iterator
1817     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1818     erase(const_iterator first, const_iterator last)
1819     {
1820       while (first != last)
1821         first = this->erase(first);
1822       return last;
1823     }
1824
1825   template<typename K, typename V, 
1826            typename A, typename Ex, typename Eq,
1827            typename H1, typename H2, typename H, typename RP,
1828            bool c, bool ci, bool u>
1829     void
1830     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1831     clear()
1832     {
1833       m_deallocate_nodes(m_buckets, m_bucket_count);
1834       m_element_count = 0;
1835     }
1836
1837   template<typename K, typename V, 
1838            typename A, typename Ex, typename Eq,
1839            typename H1, typename H2, typename H, typename RP,
1840            bool c, bool ci, bool u>
1841     void
1842     hashtable<K, V, A, Ex, Eq, H1, H2, H, RP, c, ci, u>::
1843     m_rehash(size_type N)
1844     {
1845       node** new_array = m_allocate_buckets(N);
1846       try
1847         {
1848           for (size_type i = 0; i < m_bucket_count; ++i)
1849             while (node* p = m_buckets[i])
1850               {
1851                 size_type new_index = this->bucket_index(p, N);
1852                 m_buckets[i] = p->m_next;
1853                 p->m_next = new_array[new_index];
1854                 new_array[new_index] = p;
1855               }
1856           m_deallocate_buckets(m_buckets, m_bucket_count);
1857           m_bucket_count = N;
1858           m_buckets = new_array;
1859         }
1860       catch (...)
1861         {
1862           // A failure here means that a hash function threw an exception.
1863           // We can't restore the previous state without calling the hash
1864           // function again, so the only sensible recovery is to delete
1865           // everything.
1866           m_deallocate_nodes(new_array, N);
1867           m_deallocate_buckets(new_array, N);
1868           m_deallocate_nodes(m_buckets, m_bucket_count);
1869           m_element_count = 0;
1870           __throw_exception_again;
1871         }
1872     }
1873
1874 _GLIBCXX_END_NAMESPACE
1875 }                               // Namespace std::tr1
1876
1877 #endif /* GNU_LIBSTDCXX_TR1_HASHTABLE_ */
1878