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