libstdc++-v3/include/tr1/hashtable

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