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