hashtable

Go to the documentation of this file.
00001 // Internal header for TR1 unordered_set and unordered_map -*- C++ -*-
00002 
00003 // Copyright (C) 2005 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 2, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // You should have received a copy of the GNU General Public License along
00017 // with this library; see the file COPYING.  If not, write to the Free
00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00019 // USA.
00020 
00021 // As a special exception, you may use this file as part of a free software
00022 // library without restriction.  Specifically, if other files instantiate
00023 // templates or use macros or inline functions from this file, or you compile
00024 // this file and link it with other files to produce an executable, this
00025 // file does not by itself cause the resulting executable to be covered by
00026 // the GNU General Public License.  This exception does not however
00027 // invalidate any other reasons why the executable file might be covered by
00028 // the GNU General Public License.
00029 
00030 /** @file 
00031  *  This is a TR1 C++ Library header. 
00032  */
00033 
00034 // This header file defines std::tr1::hashtable, which is used to
00035 // implement std::tr1::unordered_set, std::tr1::unordered_map, 
00036 // std::tr1::unordered_multiset, and std::tr1::unordered_multimap.
00037 // hashtable has many template parameters, partly to accommodate
00038 // the differences between those four classes and partly to 
00039 // accommodate policy choices that go beyond what TR1 calls for.
00040 
00041 // ??? Arguably this should be Internal::hashtable, not std::tr1::hashtable.
00042 
00043 // Class template hashtable attempts to encapsulate all reasonable
00044 // variation among hash tables that use chaining.  It does not handle
00045 // open addressing.
00046 
00047 // References: 
00048 // M. Austern, "A Proposal to Add Hash Tables to the Standard
00049 //    Library (revision 4)," WG21 Document N1456=03-0039, 2003.
00050 // D. E. Knuth, The Art of Computer Programming, v. 3, Sorting and Searching.
00051 // A. Tavori and V. Dreizin, "Generic Associative Containers", 2004.
00052 //    ??? Full citation?
00053 
00054 #ifndef GNU_LIBSTDCXX_TR1_HASHTABLE_
00055 #define GNU_LIBSTDCXX_TR1_HASHTABLE_
00056 
00057 #include <utility>      // For std::pair
00058 #include <iterator>
00059 #include <cstddef>
00060 #include <cstdlib>
00061 #include <cmath>
00062 #include <bits/functexcept.h>
00063 #include <tr1/type_traits>  // For true_type and false_type
00064 
00065 //----------------------------------------------------------------------
00066 // General utilities
00067 
00068 namespace Internal {
00069 template <bool Flag, typename IfTrue, typename IfFalse> struct IF;
00070 
00071 template <typename IfTrue, typename IfFalse>
00072 struct IF <true, IfTrue, IfFalse> { typedef IfTrue type; };
00073  
00074 template <typename IfTrue, typename IfFalse>
00075 struct IF <false, IfTrue, IfFalse> { typedef IfFalse type; };
00076 
00077 // Helper function: return distance(first, last) for forward
00078 // iterators, or 0 for input iterators.
00079 
00080 template <class Iterator>
00081 inline typename std::iterator_traits<Iterator>::difference_type
00082 distance_fw (Iterator first, Iterator last, std::input_iterator_tag)
00083 {
00084   return 0;
00085 }
00086 
00087 template <class Iterator>
00088 inline typename std::iterator_traits<Iterator>::difference_type
00089 distance_fw (Iterator first, Iterator last, std::forward_iterator_tag)
00090 {
00091   return std::distance(first, last);
00092 }
00093 
00094 template <class Iterator>
00095 inline typename std::iterator_traits<Iterator>::difference_type
00096 distance_fw (Iterator first, Iterator last)
00097 {
00098   typedef typename std::iterator_traits<Iterator>::iterator_category tag;
00099   return distance_fw(first, last, tag());
00100 }
00101 
00102 } // namespace Internal
00103 
00104 //----------------------------------------------------------------------
00105 // Auxiliary types used for all instantiations of hashtable: nodes
00106 // and iterators.
00107 
00108 // Nodes, used to wrap elements stored in the hash table.  A policy
00109 // template parameter of class template hashtable controls whether
00110 // nodes also store a hash code. In some cases (e.g. strings) this may
00111 // be a performance win.
00112 
00113 namespace Internal {
00114 
00115 template <typename Value, bool cache_hash_code> struct hash_node;
00116 
00117 template <typename Value>
00118 struct hash_node<Value, true> {
00119   Value m_v;
00120   std::size_t hash_code;
00121   hash_node* m_next;
00122 };
00123 
00124 template <typename Value>
00125 struct hash_node<Value, false> {
00126   Value m_v;
00127   hash_node* m_next;
00128 };
00129 
00130 // Local iterators, used to iterate within a bucket but not between
00131 // buckets.
00132 
00133 template <typename Value, bool cache>
00134 struct node_iterator_base {
00135   node_iterator_base(hash_node<Value, cache>* p) : m_cur(p) { }
00136   void incr() { m_cur = m_cur->m_next; }
00137 
00138   hash_node<Value, cache>* m_cur;
00139 };
00140 
00141 template <typename Value, bool cache>
00142 inline bool operator== (const node_iterator_base<Value, cache>& x,
00143             const node_iterator_base<Value, cache>& y)
00144 {
00145   return x.m_cur == y.m_cur;
00146 }
00147 
00148 template <typename Value, bool cache>
00149 inline bool operator!= (const node_iterator_base<Value, cache>& x,
00150             const node_iterator_base<Value, cache>& y)
00151 {
00152   return x.m_cur != y.m_cur;
00153 }
00154 
00155 template <typename Value, bool is_const, bool cache>
00156 struct node_iterator : public node_iterator_base<Value, cache> {
00157   typedef Value                                             value_type;
00158   typedef typename IF<is_const, const Value*, Value*>::type pointer;
00159   typedef typename IF<is_const, const Value&, Value&>::type reference;
00160   typedef std::ptrdiff_t                                    difference_type;
00161   typedef std::forward_iterator_tag                         iterator_category;
00162 
00163   explicit node_iterator (hash_node<Value, cache>* p = 0)
00164     : node_iterator_base<Value, cache>(p) { }
00165   node_iterator (const node_iterator<Value, false, cache>& x)
00166     : node_iterator_base<Value, cache>(x.m_cur) { }
00167 
00168   reference operator*() const { return this->m_cur->m_v; }
00169   pointer operator->() const { return &this->m_cur->m_v; }
00170 
00171   node_iterator& operator++() { this->incr(); return *this; }
00172   node_iterator operator++(int)
00173   { node_iterator tmp(*this); this->incr(); return tmp; }
00174 };
00175 
00176 template <typename Value, bool cache>
00177 struct hashtable_iterator_base {
00178   hashtable_iterator_base(hash_node<Value, cache>* node,
00179               hash_node<Value, cache>** bucket)
00180     : m_cur_node (node), m_cur_bucket (bucket)
00181   { }
00182 
00183   void incr() {
00184     m_cur_node = m_cur_node->m_next;
00185     if (!m_cur_node)
00186       m_incr_bucket();
00187   }
00188 
00189   void m_incr_bucket();
00190 
00191   hash_node<Value, cache>* m_cur_node;
00192   hash_node<Value, cache>** m_cur_bucket;
00193 };
00194 
00195 
00196 // Global iterators, used for arbitrary iteration within a hash
00197 // table.  Larger and more expensive than local iterators.
00198 
00199 template <typename Value, bool cache>
00200 void hashtable_iterator_base<Value, cache>::m_incr_bucket()
00201 {
00202   ++m_cur_bucket;
00203 
00204   // This loop requires the bucket array to have a non-null sentinel
00205   while (!*m_cur_bucket)
00206     ++m_cur_bucket;
00207   m_cur_node = *m_cur_bucket;
00208 }
00209 
00210 template <typename Value, bool cache>
00211 inline bool operator== (const hashtable_iterator_base<Value, cache>& x,
00212             const hashtable_iterator_base<Value, cache>& y)
00213 {
00214   return x.m_cur_node == y.m_cur_node;
00215 }
00216 
00217 template <typename Value, bool cache>
00218 inline bool operator!= (const hashtable_iterator_base<Value, cache>& x,
00219             const hashtable_iterator_base<Value, cache>& y)
00220 {
00221   return x.m_cur_node != y.m_cur_node;
00222 }
00223 
00224 template <typename Value, bool is_const, bool cache>
00225 struct hashtable_iterator : public hashtable_iterator_base<Value, cache>
00226 {
00227   typedef Value                                             value_type;
00228   typedef typename IF<is_const, const Value*, Value*>::type pointer;
00229   typedef typename IF<is_const, const Value&, Value&>::type reference;
00230   typedef std::ptrdiff_t                                    difference_type;
00231   typedef std::forward_iterator_tag                         iterator_category;
00232 
00233   hashtable_iterator (hash_node<Value, cache>* p, hash_node<Value, cache>** b)
00234     : hashtable_iterator_base<Value, cache>(p, b) { }
00235   hashtable_iterator (hash_node<Value, cache>** b)
00236     : hashtable_iterator_base<Value, cache>(*b, b) { }
00237   hashtable_iterator (const hashtable_iterator<Value, false, cache>& x)
00238     : hashtable_iterator_base<Value, cache>(x.m_cur_node, x.m_cur_bucket) { }
00239 
00240   reference operator*() const { return this->m_cur_node->m_v; }
00241   pointer operator->() const { return &this->m_cur_node->m_v; }
00242 
00243   hashtable_iterator& operator++() { this->incr(); return *this; }
00244   hashtable_iterator operator++(int)
00245   { hashtable_iterator tmp(*this); this->incr(); return tmp; }
00246 };
00247 
00248 } // namespace Internal
00249 
00250 // ----------------------------------------------------------------------
00251 // Many of class template hashtable's template parameters are policy
00252 // classes.  These are defaults for the policies.
00253 
00254 namespace Internal {
00255 
00256 // The two key extraction policies used by the *set and *map variants.
00257 template <typename T>
00258 struct identity {
00259   T operator()(const T& t) const { return t; }
00260 };
00261 
00262 template <typename Pair>
00263 struct extract1st {
00264   typename Pair::first_type operator()(const Pair& p) const { return p.first; }
00265 };
00266 
00267 // Default range hashing function: use division to fold a large number
00268 // into the range [0, N).
00269 struct mod_range_hashing
00270 {
00271   typedef std::size_t first_argument_type;
00272   typedef std::size_t second_argument_type;
00273   typedef std::size_t result_type;
00274 
00275   result_type operator() (first_argument_type r, second_argument_type N) const
00276     { return r % N; }
00277 };
00278 
00279 // Default ranged hash function H.  In principle it should be a
00280 // function object composed from objects of type H1 and H2 such that
00281 // h(k, N) = h2(h1(k), N), but that would mean making extra copies of
00282 // h1 and h2.  So instead we'll just use a tag to tell class template
00283 // hashtable to do that composition.
00284 struct default_ranged_hash { };
00285 
00286 // Default value for rehash policy.  Bucket size is (usually) the
00287 // smallest prime that keeps the load factor small enough.
00288 
00289 struct prime_rehash_policy
00290 {
00291   prime_rehash_policy (float z = 1.0);
00292 
00293   float max_load_factor() const;
00294 
00295   // Return a bucket size no smaller than n.
00296   std::size_t next_bkt (std::size_t n) const;
00297 
00298   // Return a bucket count appropriate for n elements
00299   std::size_t bkt_for_elements (std::size_t n) const;
00300 
00301   // n_bkt is current bucket count, n_elt is current element count,
00302   // and n_ins is number of elements to be inserted.  Do we need to
00303   // increase bucket count?  If so, return make_pair(true, n), where n
00304   // is the new bucket count.  If not, return make_pair(false, 0).
00305   std::pair<bool, std::size_t>
00306   need_rehash (std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const;
00307 
00308   float m_max_load_factor;
00309   float m_growth_factor;
00310   mutable std::size_t m_next_resize;
00311 };
00312 
00313 // XXX This is a hack.  prime_rehash_policy's member functions, and
00314 // certainly the list of primes, should be defined in a .cc file.
00315 // We're temporarily putting them in a header because we don't have a
00316 // place to put TR1 .cc files yet.  There's no good reason for any of
00317 // prime_rehash_policy's member functions to be inline, and there's
00318 // certainly no good reason for X<> to exist at all.
00319 
00320 struct lt {
00321   template <typename X, typename Y> bool operator()(X x, Y y) { return x < y; }
00322 };
00323 
00324 template <int dummy>
00325 struct X {
00326   static const int n_primes = 256;
00327   static const unsigned long primes[n_primes + 1];
00328 };
00329 
00330 template <int dummy>
00331 const int X<dummy>::n_primes;
00332 
00333 template <int dummy>
00334 const unsigned long X<dummy>::primes[n_primes + 1] =
00335   {
00336     2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
00337     37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul,
00338     83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul,
00339     157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul,
00340     277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul,
00341     503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul,
00342     953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul,
00343     1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul,
00344     3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul,
00345     5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul,
00346     11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul,
00347     19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul,
00348     33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul,
00349     57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul,
00350     99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul,
00351     159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul,
00352     256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul,
00353     410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul,
00354     658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul,
00355     1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul,
00356     1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul,
00357     2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul,
00358     4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul,
00359     6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul,
00360     11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul,
00361     16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul,
00362     24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul,
00363     36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul,
00364     54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul,
00365     80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul,
00366     118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul,
00367     176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul,
00368     260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul,
00369     386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul,
00370     573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul,
00371     849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul,
00372     1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul,
00373     1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul,
00374     2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul,
00375     3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul,
00376     4294967291ul,
00377     4294967291ul // sentinel so we don't have to test result of lower_bound
00378   };
00379 
00380 inline prime_rehash_policy::prime_rehash_policy (float z)
00381   : m_max_load_factor(z),
00382     m_growth_factor (2.f),
00383     m_next_resize (0)
00384 { }
00385 
00386 inline float prime_rehash_policy::max_load_factor() const
00387 {
00388   return m_max_load_factor;
00389 }
00390 
00391 // Return a prime no smaller than n.
00392 inline std::size_t prime_rehash_policy::next_bkt (std::size_t n) const
00393 {
00394   const unsigned long* const last = X<0>::primes + X<0>::n_primes;
00395   const unsigned long* p = std::lower_bound (X<0>::primes, last, n);
00396   m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
00397   return *p;
00398 }
00399 
00400 // Return the smallest prime p such that alpha p >= n, where alpha
00401 // is the load factor.
00402 inline std::size_t prime_rehash_policy::bkt_for_elements (std::size_t n) const
00403 {
00404   const unsigned long* const last = X<0>::primes + X<0>::n_primes;
00405   const float min_bkts = n / m_max_load_factor;
00406   const unsigned long* p = std::lower_bound (X<0>::primes, last, min_bkts, lt());
00407   m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
00408   return *p;
00409 }
00410 
00411 // Finds the smallest prime p such that alpha p > n_elt + n_ins.
00412 // If p > n_bkt, return make_pair(true, p); otherwise return
00413 // make_pair(false, 0).  In principle this isn't very different from 
00414 // bkt_for_elements.
00415 
00416 // The only tricky part is that we're caching the element count at
00417 // which we need to rehash, so we don't have to do a floating-point
00418 // multiply for every insertion.
00419 
00420 inline std::pair<bool, std::size_t>
00421 prime_rehash_policy
00422 ::need_rehash (std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const
00423 {
00424   if (n_elt + n_ins > m_next_resize) {
00425     float min_bkts = (float(n_ins) + float(n_elt)) / m_max_load_factor;
00426     if (min_bkts > n_bkt) {
00427       min_bkts = std::max (min_bkts, m_growth_factor * n_bkt);
00428       const unsigned long* const last = X<0>::primes + X<0>::n_primes;
00429       const unsigned long* p = std::lower_bound (X<0>::primes, last, min_bkts, lt());
00430       m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
00431       return std::make_pair(true, *p);
00432     }
00433     else {
00434       m_next_resize = static_cast<std::size_t>(std::ceil(n_bkt * m_max_load_factor));
00435       return std::make_pair(false, 0);
00436     }
00437   }
00438   else
00439     return std::make_pair(false, 0);
00440 }
00441 
00442 } // namespace Internal
00443 
00444 //----------------------------------------------------------------------
00445 // Base classes for std::tr1::hashtable.  We define these base classes
00446 // because in some cases we want to do different things depending on
00447 // the value of a policy class.  In some cases the policy class affects
00448 // which member functions and nested typedefs are defined; we handle that
00449 // by specializing base class templates.  Several of the base class templates
00450 // need to access other members of class template hashtable, so we use
00451 // the "curiously recurring template pattern" for them.
00452 
00453 namespace Internal {
00454 
00455 // class template map_base.  If the hashtable has a value type of the
00456 // form pair<T1, T2> and a key extraction policy that returns the
00457 // first part of the pair, the hashtable gets a mapped_type typedef.
00458 // If it satisfies those criteria and also has unique keys, then it
00459 // also gets an operator[].
00460 
00461 template <typename K, typename V, typename Ex, bool unique, typename Hashtable>
00462 struct map_base { };
00463       
00464 template <typename K, typename Pair, typename Hashtable>
00465 struct map_base<K, Pair, extract1st<Pair>, false, Hashtable>
00466 {
00467   typedef typename Pair::second_type mapped_type;
00468 };
00469 
00470 template <typename K, typename Pair, typename Hashtable>
00471 struct map_base<K, Pair, extract1st<Pair>, true, Hashtable>
00472 {
00473   typedef typename Pair::second_type mapped_type;
00474   mapped_type& operator[](const K& k) {
00475     Hashtable* h = static_cast<Hashtable*>(this);
00476     typename Hashtable::iterator it = h->insert(std::make_pair(k, mapped_type())).first;
00477     return it->second;
00478   }
00479 };
00480 
00481 // class template rehash_base.  Give hashtable the max_load_factor
00482 // functions iff the rehash policy is prime_rehash_policy.
00483 template <typename RehashPolicy, typename Hashtable>
00484 struct rehash_base { };
00485 
00486 template <typename Hashtable>
00487 struct rehash_base<prime_rehash_policy, Hashtable>
00488 {
00489   float max_load_factor() const {
00490     const Hashtable* This = static_cast<const Hashtable*>(this);
00491     return This->rehash_policy()->max_load_factor();
00492   }
00493 
00494   void max_load_factor(float z) {
00495     Hashtable* This = static_cast<Hashtable*>(this);
00496     This->rehash_policy(prime_rehash_policy(z));    
00497   }
00498 };
00499 
00500 // Class template hash_code_base.  Encapsulates two policy issues that
00501 // aren't quite orthogonal.
00502 //   (1) the difference between using a ranged hash function and using
00503 //       the combination of a hash function and a range-hashing function.
00504 //       In the former case we don't have such things as hash codes, so
00505 //       we have a dummy type as placeholder.
00506 //   (2) Whether or not we cache hash codes.  Caching hash codes is
00507 //       meaningless if we have a ranged hash function.
00508 // We also put the key extraction and equality comparison function 
00509 // objects here, for convenience.
00510 
00511 // Primary template: unused except as a hook for specializations.
00512 
00513 template <typename Key, typename Value,
00514       typename ExtractKey, typename Equal,
00515       typename H1, typename H2, typename H,
00516       bool cache_hash_code>
00517 struct hash_code_base;
00518 
00519 // Specialization: ranged hash function, no caching hash codes.  H1
00520 // and H2 are provided but ignored.  We define a dummy hash code type.
00521 template <typename Key, typename Value,
00522       typename ExtractKey, typename Equal,
00523       typename H1, typename H2, typename H>
00524 struct hash_code_base <Key, Value, ExtractKey, Equal, H1, H2, H, false>
00525 {
00526 protected:
00527   hash_code_base (const ExtractKey& ex, const Equal& eq,
00528             const H1&, const H2&, const H& h)
00529     : m_extract(ex), m_eq(eq), m_ranged_hash(h) { }
00530 
00531   typedef void* hash_code_t;
00532   hash_code_t m_hash_code (const Key& k) const { return 0; }
00533   std::size_t bucket_index (const Key& k, hash_code_t, std::size_t N) const
00534     { return m_ranged_hash (k, N); }
00535   std::size_t bucket_index (const hash_node<Value, false>* p, std::size_t N) const {
00536     return m_ranged_hash (m_extract (p->m_v), N); 
00537   }
00538   
00539   bool compare (const Key& k, hash_code_t, hash_node<Value, false>* n) const
00540     { return m_eq (k, m_extract(n->m_v)); }
00541 
00542   void store_code (hash_node<Value, false>*, hash_code_t) const { }
00543 
00544   void copy_code (hash_node<Value, false>*, const hash_node<Value, false>*) const { }
00545 
00546   void m_swap(hash_code_base& x) {
00547     std::swap(m_extract, x.m_extract);
00548     std::swap(m_eq, x.m_eq);
00549     std::swap(m_ranged_hash, x.m_ranged_hash);
00550   }
00551 
00552 protected:
00553   ExtractKey m_extract;
00554   Equal m_eq;
00555   H m_ranged_hash;
00556 };
00557 
00558 
00559 // No specialization for ranged hash function while caching hash codes.
00560 // That combination is meaningless, and trying to do it is an error.
00561 
00562 
00563 // Specialization: ranged hash function, cache hash codes.  This
00564 // combination is meaningless, so we provide only a declaration
00565 // and no definition.
00566 
00567 template <typename Key, typename Value,
00568       typename ExtractKey, typename Equal,
00569       typename H1, typename H2, typename H>
00570 struct hash_code_base <Key, Value, ExtractKey, Equal, H1, H2, H, true>;
00571 
00572 
00573 // Specialization: hash function and range-hashing function, no
00574 // caching of hash codes.  H is provided but ignored.  Provides
00575 // typedef and accessor required by TR1.
00576 
00577 template <typename Key, typename Value,
00578       typename ExtractKey, typename Equal,
00579       typename H1, typename H2>
00580 struct hash_code_base <Key, Value, ExtractKey, Equal, H1, H2, default_ranged_hash, false>
00581 {
00582   typedef H1 hasher;
00583   hasher hash_function() const { return m_h1; }
00584 
00585 protected:
00586   hash_code_base (const ExtractKey& ex, const Equal& eq,
00587           const H1& h1, const H2& h2, const default_ranged_hash&)
00588     : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { }
00589 
00590   typedef std::size_t hash_code_t;
00591   hash_code_t m_hash_code (const Key& k) const { return m_h1(k); }
00592   std::size_t bucket_index (const Key&, hash_code_t c, std::size_t N) const
00593     { return m_h2 (c, N); }
00594   std::size_t bucket_index (const hash_node<Value, false>* p, std::size_t N) const {
00595     return m_h2 (m_h1 (m_extract (p->m_v)), N);
00596   }
00597 
00598   bool compare (const Key& k, hash_code_t,  hash_node<Value, false>* n) const
00599     { return m_eq (k, m_extract(n->m_v)); }
00600   
00601   void store_code (hash_node<Value, false>*, hash_code_t) const { }
00602   
00603   void copy_code (hash_node<Value, false>*, const hash_node<Value, false>*) const { }
00604 
00605   void m_swap(hash_code_base& x) {
00606     std::swap(m_extract, x.m_extract);
00607     std::swap(m_eq, x.m_eq);
00608     std::swap(m_h1, x.m_h1);
00609     std::swap(m_h2, x.m_h2);
00610   }
00611 
00612 protected:
00613   ExtractKey m_extract;
00614   Equal m_eq;
00615   H1 m_h1;
00616   H2 m_h2;
00617 };
00618 
00619 // Specialization: hash function and range-hashing function, 
00620 // caching hash codes.  H is provided but ignored.  Provides
00621 // typedef and accessor required by TR1.
00622 template <typename Key, typename Value,
00623       typename ExtractKey, typename Equal,
00624       typename H1, typename H2>
00625 struct hash_code_base <Key, Value, ExtractKey, Equal, H1, H2, default_ranged_hash, true>
00626 {
00627   typedef H1 hasher;
00628   hasher hash_function() const { return m_h1; }
00629 
00630 protected:
00631   hash_code_base (const ExtractKey& ex, const Equal& eq,
00632             const H1& h1, const H2& h2, const default_ranged_hash&)
00633     : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { }
00634 
00635   typedef std::size_t hash_code_t;
00636   hash_code_t m_hash_code (const Key& k) const { return m_h1(k); }
00637   std::size_t bucket_index (const Key&, hash_code_t c, std::size_t N) const
00638     { return m_h2 (c, N); }
00639 
00640   std::size_t bucket_index (const hash_node<Value, true>* p, std::size_t N) const {
00641     return m_h2 (p->hash_code, N);
00642   }
00643 
00644   bool compare (const Key& k, hash_code_t c,  hash_node<Value, true>* n) const
00645     { return c == n->hash_code && m_eq (k, m_extract(n->m_v)); }
00646 
00647   void store_code (hash_node<Value, true>* n, hash_code_t c) const
00648     { n->hash_code = c; }
00649 
00650   void copy_code (hash_node<Value, true>* to, const hash_node<Value, true>* from) const
00651     { to->hash_code = from->hash_code; }
00652 
00653   void m_swap(hash_code_base& x) {
00654     std::swap(m_extract, x.m_extract);
00655     std::swap(m_eq, x.m_eq);
00656     std::swap(m_h1, x.m_h1);
00657     std::swap(m_h2, x.m_h2);
00658   }
00659 
00660 protected:
00661   ExtractKey m_extract;
00662   Equal m_eq;
00663   H1 m_h1;
00664   H2 m_h2;
00665 };
00666 
00667 } // namespace internal
00668 
00669 namespace std { namespace tr1 {
00670 
00671 //----------------------------------------------------------------------
00672 // Class template hashtable, class definition.
00673 
00674 // Meaning of class template hashtable's template parameters
00675 
00676 // Key and Value: arbitrary CopyConstructible types.
00677 
00678 // Allocator: an allocator type ([lib.allocator.requirements]) whose
00679 // value type is Value.
00680 
00681 // ExtractKey: function object that takes a object of type Value
00682 // and returns a value of type Key.
00683 
00684 // Equal: function object that takes two objects of type k and returns
00685 // a bool-like value that is true if the two objects are considered equal.
00686 
00687 // H1: the hash function.  A unary function object with argument type
00688 // Key and result type size_t.  Return values should be distributed
00689 // over the entire range [0, numeric_limits<size_t>:::max()].
00690 
00691 // H2: the range-hashing function (in the terminology of Tavori and
00692 // Dreizin).  A binary function object whose argument types and result
00693 // type are all size_t.  Given arguments r and N, the return value is
00694 // in the range [0, N).
00695 
00696 // H: the ranged hash function (Tavori and Dreizin). A binary function
00697 // whose argument types are Key and size_t and whose result type is
00698 // size_t.  Given arguments k and N, the return value is in the range
00699 // [0, N).  Default: h(k, N) = h2(h1(k), N).  If H is anything other
00700 // than the default, H1 and H2 are ignored.
00701 
00702 // RehashPolicy: Policy class with three members, all of which govern
00703 // the bucket count. n_bkt(n) returns a bucket count no smaller
00704 // than n.  bkt_for_elements(n) returns a bucket count appropriate
00705 // for an element count of n.  need_rehash(n_bkt, n_elt, n_ins)
00706 // determines whether, if the current bucket count is n_bkt and the
00707 // current element count is n_elt, we need to increase the bucket
00708 // count.  If so, returns make_pair(true, n), where n is the new
00709 // bucket count.  If not, returns make_pair(false, <anything>).
00710 
00711 // ??? Right now it is hard-wired that the number of buckets never
00712 // shrinks.  Should we allow RehashPolicy to change that?
00713 
00714 // cache_hash_code: bool.  true if we store the value of the hash
00715 // function along with the value.  This is a time-space tradeoff.
00716 // Storing it may improve lookup speed by reducing the number of times
00717 // we need to call the Equal function.
00718 
00719 // mutable_iterators: bool.  true if hashtable::iterator is a mutable
00720 // iterator, false if iterator and const_iterator are both const 
00721 // iterators.  This is true for unordered_map and unordered_multimap,
00722 // false for unordered_set and unordered_multiset.
00723 
00724 // unique_keys: bool.  true if the return value of hashtable::count(k)
00725 // is always at most one, false if it may be an arbitrary number.  This
00726 // true for unordered_set and unordered_map, false for unordered_multiset
00727 // and unordered_multimap.
00728 
00729 template <typename Key, typename Value, 
00730       typename Allocator,
00731       typename ExtractKey, typename Equal,
00732       typename H1, typename H2,
00733       typename H, typename RehashPolicy,
00734       bool cache_hash_code,
00735       bool mutable_iterators,
00736       bool unique_keys>
00737 class hashtable
00738   : public Internal::rehash_base<RehashPolicy, hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys> >,
00739     public Internal::hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, cache_hash_code>,
00740     public Internal::map_base<Key, Value, ExtractKey, unique_keys, hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys> >
00741 {
00742 public:
00743   typedef Allocator                           allocator_type;
00744   typedef Value                               value_type;
00745   typedef Key                                 key_type;
00746   typedef Equal                               key_equal;
00747   // mapped_type, if present, comes from map_base.
00748   // hasher, if present, comes from hash_code_base.
00749   typedef typename Allocator::difference_type difference_type;
00750   typedef typename Allocator::size_type       size_type;
00751   typedef typename Allocator::reference       reference;
00752   typedef typename Allocator::const_reference const_reference;
00753 
00754   typedef Internal::node_iterator<value_type, !mutable_iterators, cache_hash_code>
00755           local_iterator;
00756   typedef Internal::node_iterator<value_type, true,              cache_hash_code>
00757           const_local_iterator;
00758 
00759   typedef Internal::hashtable_iterator<value_type, !mutable_iterators, cache_hash_code>
00760           iterator;
00761   typedef Internal::hashtable_iterator<value_type, true,              cache_hash_code>
00762           const_iterator;
00763 
00764 private:
00765   typedef Internal::hash_node<Value, cache_hash_code>                 node;
00766   typedef typename Allocator::template rebind<node>::other  node_allocator_t;
00767   typedef typename Allocator::template rebind<node*>::other bucket_allocator_t;
00768 
00769 private:
00770   node_allocator_t m_node_allocator;
00771   node** m_buckets;
00772   size_type m_bucket_count;
00773   size_type m_element_count;
00774   RehashPolicy m_rehash_policy;
00775 
00776   node* m_allocate_node (const value_type& v);
00777   void m_deallocate_node (node* n);
00778   void m_deallocate_nodes (node**, size_type);
00779 
00780   node** m_allocate_buckets (size_type n);
00781   void m_deallocate_buckets (node**, size_type n);
00782 
00783 public:             // Constructor, destructor, assignment, swap
00784   hashtable(size_type bucket_hint,
00785         const H1&, const H2&, const H&,
00786         const Equal&, const ExtractKey&,
00787         const allocator_type&);
00788   
00789   template <typename InIter>
00790   hashtable(InIter first, InIter last,
00791         size_type bucket_hint,
00792         const H1&, const H2&, const H&,
00793         const Equal&, const ExtractKey&,
00794         const allocator_type&);
00795   
00796   hashtable(const hashtable&);
00797   hashtable& operator=(const hashtable&);
00798   ~hashtable();
00799 
00800   void swap(hashtable&);
00801 
00802 public:             // Basic container operations
00803   iterator       begin() {
00804     iterator i(m_buckets);
00805     if (!i.m_cur_node)
00806       i.m_incr_bucket();
00807     return i;
00808   }
00809 
00810   const_iterator begin() const {
00811     const_iterator i(m_buckets);
00812     if (!i.m_cur_node)
00813       i.m_incr_bucket();
00814     return i;
00815   }
00816 
00817   iterator       end()
00818     { return iterator(m_buckets + m_bucket_count); }
00819   const_iterator end() const
00820     { return const_iterator(m_buckets + m_bucket_count); }
00821 
00822   size_type size() const { return m_element_count; }
00823   bool empty() const { return size() == 0; }
00824 
00825   allocator_type get_allocator() const { return m_node_allocator; }
00826   size_type max_size() const { return m_node_allocator.max_size(); }
00827 
00828 public:             // Bucket operations
00829   size_type bucket_count() const
00830     { return m_bucket_count; }
00831   size_type max_bucket_count() const
00832     { return max_size(); }
00833   size_type bucket_size (size_type n) const
00834     { return std::distance(begin(n), end(n)); }
00835   size_type bucket (const key_type& k) const
00836     { return this->bucket_index (k, this->m_hash_code, this->m_bucket_count); }
00837 
00838   local_iterator begin(size_type n)
00839     { return local_iterator(m_buckets[n]); }
00840   local_iterator end(size_type n)
00841     { return local_iterator(0); }
00842   const_local_iterator begin(size_type n) const
00843     { return const_local_iterator(m_buckets[n]); }
00844   const_local_iterator end(size_type n) const
00845     { return const_local_iterator(0); }
00846 
00847   float load_factor() const
00848     { return static_cast<float>(size()) / static_cast<float>(bucket_count()); }
00849   // max_load_factor, if present, comes from rehash_base.
00850 
00851   // Generalization of max_load_factor.  Extension, not found in TR1.  Only
00852   // useful if RehashPolicy is something other than the default.
00853   const RehashPolicy& rehash_policy() const { return m_rehash_policy; }
00854   void rehash_policy (const RehashPolicy&);
00855 
00856 public:             // lookup
00857   iterator       find(const key_type&);
00858   const_iterator find(const key_type& k) const;
00859   size_type count(const key_type& k) const;
00860   std::pair<iterator, iterator> equal_range(const key_type& k);
00861   std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
00862 
00863 private:            // Insert and erase helper functions
00864   // ??? This dispatching is a workaround for the fact that we don't
00865   // have partial specialization of member templates; it would be
00866   // better to just specialize insert on unique_keys.  There may be a
00867   // cleaner workaround.
00868   typedef typename Internal::IF<unique_keys, std::pair<iterator, bool>, iterator>::type
00869           Insert_Return_Type;
00870 
00871   node* find_node (node* p, const key_type& k,
00872            typename hashtable::hash_code_t c) const;
00873 
00874   std::pair<iterator, bool> insert (const value_type&, std::tr1::true_type);
00875   iterator insert (const value_type&, std::tr1::false_type);
00876 
00877 public:             // Insert and erase
00878   Insert_Return_Type insert (const value_type& v) 
00879   { return this->insert (v, std::tr1::integral_constant<bool, unique_keys>()); }
00880   Insert_Return_Type insert (const_iterator, const value_type& v)
00881     { return this->insert(v); }
00882 
00883   template <typename InIter> void insert(InIter first, InIter last);
00884 
00885   void erase(const_iterator);
00886   size_type erase(const key_type&);
00887   void erase(const_iterator, const_iterator);
00888   void clear();
00889 
00890 public:
00891   // Set number of buckets to be apropriate for container of n element.
00892   void rehash (size_type n);
00893 
00894 private:
00895   // Unconditionally change size of bucket array to n.
00896   void m_rehash (size_type n);
00897 };
00898 
00899 //----------------------------------------------------------------------
00900 // Definitions of class template hashtable's out-of-line member functions.
00901 
00902 template <typename K, typename V, 
00903       typename A, typename Ex, typename Eq,
00904       typename H1, typename H2, typename H, typename RP,
00905       bool c, bool m, bool u>
00906 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::node*
00907 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_allocate_node (const value_type& v)
00908 {
00909   node* n = m_node_allocator.allocate(1);
00910   try {
00911     get_allocator().construct(&n->m_v, v);
00912     n->m_next = 0;
00913     return n;
00914   }
00915   catch(...) {
00916     m_node_allocator.deallocate(n, 1);
00917     __throw_exception_again;
00918   }
00919 }
00920 
00921 template <typename K, typename V, 
00922       typename A, typename Ex, typename Eq,
00923       typename H1, typename H2, typename H, typename RP,
00924       bool c, bool m, bool u>
00925 void
00926 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_deallocate_node (node* n)
00927 {
00928   get_allocator().destroy(&n->m_v);
00929   m_node_allocator.deallocate(n, 1);
00930 }
00931 
00932 template <typename K, typename V, 
00933       typename A, typename Ex, typename Eq,
00934       typename H1, typename H2, typename H, typename RP,
00935       bool c, bool m, bool u>
00936 void
00937 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
00938 ::m_deallocate_nodes (node** array, size_type n)
00939 {
00940   for (size_type i = 0; i < n; ++i) {
00941     node* p = array[i];
00942     while (p) {
00943       node* tmp = p;
00944       p = p->m_next;
00945       m_deallocate_node (tmp);
00946     }
00947     array[i] = 0;
00948   }
00949 }
00950 
00951 template <typename K, typename V, 
00952       typename A, typename Ex, typename Eq,
00953       typename H1, typename H2, typename H, typename RP,
00954       bool c, bool m, bool u>
00955 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::node**
00956 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_allocate_buckets (size_type n)
00957 {
00958   bucket_allocator_t alloc(m_node_allocator);
00959 
00960   // We allocate one extra bucket to hold a sentinel, an arbitrary
00961   // non-null pointer.  Iterator increment relies on this.
00962   node** p = alloc.allocate(n+1);
00963   std::fill(p, p+n, (node*) 0);
00964   p[n] = reinterpret_cast<node*>(0x1000);
00965   return p;
00966 }
00967 
00968 template <typename K, typename V, 
00969       typename A, typename Ex, typename Eq,
00970       typename H1, typename H2, typename H, typename RP,
00971       bool c, bool m, bool u>
00972 void
00973 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
00974 ::m_deallocate_buckets (node** p, size_type n)
00975 {
00976   bucket_allocator_t alloc(m_node_allocator);
00977   alloc.deallocate(p, n+1);
00978 }
00979 
00980 template <typename K, typename V, 
00981       typename A, typename Ex, typename Eq,
00982       typename H1, typename H2, typename H, typename RP,
00983       bool c, bool m, bool u>
00984 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
00985 ::hashtable(size_type bucket_hint,
00986         const H1& h1, const H2& h2, const H& h,
00987         const Eq& eq, const Ex& exk,
00988         const allocator_type& a)
00989   : Internal::rehash_base<RP,hashtable> (),
00990     Internal::hash_code_base<K,V,Ex,Eq,H1,H2,H,c> (exk, eq, h1, h2, h),
00991     Internal::map_base<K,V,Ex,u,hashtable> (),
00992     m_node_allocator(a),
00993     m_bucket_count (0),
00994     m_element_count (0),
00995     m_rehash_policy ()
00996 {
00997   m_bucket_count = m_rehash_policy.next_bkt(bucket_hint);
00998   m_buckets = m_allocate_buckets (m_bucket_count);
00999 }
01000 
01001 template <typename K, typename V, 
01002       typename A, typename Ex, typename Eq,
01003       typename H1, typename H2, typename H, typename RP,
01004       bool c, bool m, bool u>
01005 template <typename InIter>
01006 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
01007 ::hashtable(InIter f, InIter l,
01008         size_type bucket_hint,
01009         const H1& h1, const H2& h2, const H& h,
01010         const Eq& eq, const Ex& exk,
01011         const allocator_type& a)
01012   : Internal::rehash_base<RP,hashtable> (),
01013     Internal::hash_code_base<K,V,Ex,Eq,H1,H2,H,c> (exk, eq, h1, h2, h),
01014     Internal::map_base<K,V,Ex,u,hashtable> (),
01015     m_node_allocator(a),
01016     m_bucket_count (0),
01017     m_element_count (0),
01018     m_rehash_policy ()
01019 {
01020   m_bucket_count = std::max(m_rehash_policy.next_bkt(bucket_hint),
01021                 m_rehash_policy.bkt_for_elements(Internal::distance_fw(f, l)));
01022   m_buckets = m_allocate_buckets (m_bucket_count);
01023   try {
01024     for  (; f != l; ++f)
01025       this->insert (*f);
01026   }
01027   catch(...) {
01028     clear();
01029     m_deallocate_buckets (m_buckets, m_bucket_count);
01030     __throw_exception_again;
01031   }
01032 }
01033 
01034 template <typename K, typename V, 
01035       typename A, typename Ex, typename Eq,
01036       typename H1, typename H2, typename H, typename RP,
01037       bool c, bool m, bool u>
01038 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
01039 ::hashtable(const hashtable& ht)
01040   : Internal::rehash_base<RP,hashtable> (ht),
01041     Internal::hash_code_base<K,V,Ex,Eq,H1,H2,H,c> (ht),
01042     Internal::map_base<K,V,Ex,u,hashtable> (ht),
01043     m_node_allocator(ht.get_allocator()),
01044     m_bucket_count (ht.m_bucket_count),
01045     m_element_count (ht.m_element_count),
01046     m_rehash_policy (ht.m_rehash_policy)
01047 {
01048   m_buckets = m_allocate_buckets (m_bucket_count);
01049   try {
01050     for (size_t i = 0; i < ht.m_bucket_count; ++i) {
01051       node* n = ht.m_buckets[i];
01052       node** tail = m_buckets + i;
01053       while (n) {
01054     *tail = m_allocate_node(n->m_v);
01055     this->copy_code(*tail, n);
01056     tail = &((*tail)->m_next);
01057     n = n->m_next;
01058       }
01059     }
01060   }
01061   catch (...) {
01062     clear();
01063     m_deallocate_buckets (m_buckets, m_bucket_count);
01064     __throw_exception_again;
01065   }
01066 }
01067 
01068 template <typename K, typename V, 
01069       typename A, typename Ex, typename Eq,
01070       typename H1, typename H2, typename H, typename RP,
01071       bool c, bool m, bool u>
01072 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>&
01073 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::operator= (const hashtable& ht)
01074 {
01075   hashtable tmp(ht);
01076   this->swap(tmp);
01077   return *this;
01078 }
01079 
01080 template <typename K, typename V, 
01081       typename A, typename Ex, typename Eq,
01082       typename H1, typename H2, typename H, typename RP,
01083       bool c, bool m, bool u>
01084 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::~hashtable()
01085 {
01086   clear();
01087   m_deallocate_buckets(m_buckets, m_bucket_count);
01088 }
01089 
01090 template <typename K, typename V, 
01091       typename A, typename Ex, typename Eq,
01092       typename H1, typename H2, typename H, typename RP,
01093       bool c, bool m, bool u>
01094 void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::swap (hashtable& x)
01095 {
01096   // The only base class with member variables is hash_code_base.  We
01097   // define hash_code_base::m_swap because different specializations
01098   // have different members.
01099   Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>::m_swap(x);
01100 
01101   // open LWG issue 431
01102   // std::swap(m_node_allocator, x.m_node_allocator);
01103   std::swap (m_rehash_policy, x.m_rehash_policy);
01104   std::swap (m_buckets, x.m_buckets);
01105   std::swap (m_bucket_count, x.m_bucket_count);
01106   std::swap (m_element_count, x.m_element_count);
01107 }
01108 
01109 template <typename K, typename V, 
01110       typename A, typename Ex, typename Eq,
01111       typename H1, typename H2, typename H, typename RP,
01112       bool c, bool m, bool u>
01113 void
01114 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::rehash_policy (const RP& pol)
01115 {
01116   m_rehash_policy = pol;
01117   size_type n_bkt = pol.bkt_for_elements(m_element_count);
01118   if (n_bkt > m_bucket_count)
01119     m_rehash (n_bkt);
01120 }
01121 
01122 template <typename K, typename V, 
01123       typename A, typename Ex, typename Eq,
01124       typename H1, typename H2, typename H, typename RP,
01125       bool c, bool m, bool u>
01126 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator
01127 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::find (const key_type& k)
01128 {
01129   typename hashtable::hash_code_t code = this->m_hash_code (k);
01130   std::size_t n = this->bucket_index (k, code, this->bucket_count());
01131   node* p = find_node (m_buckets[n], k, code);
01132   return p ? iterator(p, m_buckets + n) : this->end();
01133 }
01134 
01135 template <typename K, typename V, 
01136       typename A, typename Ex, typename Eq,
01137       typename H1, typename H2, typename H, typename RP,
01138       bool c, bool m, bool u>
01139 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::const_iterator
01140 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::find (const key_type& k) const
01141 {
01142   typename hashtable::hash_code_t code = this->m_hash_code (k);
01143   std::size_t n = this->bucket_index (k, code, this->bucket_count());
01144   node* p = find_node (m_buckets[n], k, code);
01145   return p ? const_iterator(p, m_buckets + n) : this->end();
01146 }
01147 
01148 template <typename K, typename V, 
01149       typename A, typename Ex, typename Eq,
01150       typename H1, typename H2, typename H, typename RP,
01151       bool c, bool m, bool u>
01152 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::size_type
01153 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::count (const key_type& k) const
01154 {
01155   typename hashtable::hash_code_t code = this->m_hash_code (k);
01156   std::size_t n = this->bucket_index (k, code, this->bucket_count());
01157   size_t result = 0;
01158   for (node* p = m_buckets[n]; p ; p = p->m_next)
01159     if (this->compare (k, code, p))
01160       ++result;
01161   return result;
01162 }
01163 
01164 template <typename K, typename V, 
01165       typename A, typename Ex, typename Eq,
01166       typename H1, typename H2, typename H, typename RP,
01167       bool c, bool m, bool u>
01168 std::pair<typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator,
01169       typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator>
01170 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::equal_range (const key_type& k)
01171 {
01172   typename hashtable::hash_code_t code = this->m_hash_code (k);
01173   std::size_t n = this->bucket_index (k, code, this->bucket_count());
01174   node** head = m_buckets + n;
01175   node* p = find_node (*head, k, code);
01176 
01177   if (p) {
01178     node* p1 = p->m_next;
01179     for (; p1 ; p1 = p1->m_next)
01180       if (!this->compare (k, code, p1))
01181     break;
01182     iterator first(p, head);
01183     iterator last(p1, head);
01184     if (!p1)
01185       last.m_incr_bucket();
01186     return std::make_pair(first, last);
01187   }
01188   else
01189     return std::make_pair (this->end(), this->end());
01190 }
01191 
01192 template <typename K, typename V, 
01193       typename A, typename Ex, typename Eq,
01194       typename H1, typename H2, typename H, typename RP,
01195       bool c, bool m, bool u>
01196 std::pair<typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::const_iterator,
01197       typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::const_iterator>
01198 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::equal_range (const key_type& k) const
01199 {
01200   typename hashtable::hash_code_t code = this->m_hash_code (k);
01201   std::size_t n = this->bucket_index (k, code, this->bucket_count());
01202   node** head = m_buckets + n;
01203   node* p = find_node (*head, k, code);
01204 
01205   if (p) {
01206     node* p1 = p->m_next;
01207     for (; p1 ; p1 = p1->m_next)
01208       if (!this->compare (k, code, p1))
01209     break;
01210     const_iterator first(p, head);
01211     const_iterator last(p1, head);
01212     if (!p1)
01213       last.m_incr_bucket();
01214     return std::make_pair(first, last);
01215   }
01216   else
01217     return std::make_pair (this->end(), this->end());
01218 }
01219 
01220 // Find the node whose key compares equal to k, beginning the search
01221 // at p (usually the head of a bucket).  Return nil if no node is found.
01222 template <typename K, typename V, 
01223       typename A, typename Ex, typename Eq,
01224       typename H1, typename H2, typename H, typename RP,
01225       bool c, bool m, bool u>
01226 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::node* 
01227 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
01228 ::find_node (node* p, const key_type& k,
01229          typename hashtable::hash_code_t code) const
01230 {
01231   for ( ; p ; p = p->m_next)
01232     if (this->compare (k, code, p))
01233       return p;
01234   return false;
01235 }
01236 
01237 // Insert v if no element with its key is already present.
01238 template <typename K, typename V, 
01239       typename A, typename Ex, typename Eq,
01240       typename H1, typename H2, typename H, typename RP,
01241       bool c, bool m, bool u>
01242 std::pair<typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator, bool>
01243 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
01244 ::insert (const value_type& v, std::tr1::true_type)
01245 {
01246   const key_type& k = this->m_extract(v);
01247   typename hashtable::hash_code_t code = this->m_hash_code (k);
01248   size_type n = this->bucket_index (k, code, m_bucket_count);
01249 
01250   if (node* p = find_node (m_buckets[n], k, code))
01251     return std::make_pair(iterator(p, m_buckets + n), false);
01252 
01253   std::pair<bool, size_t> do_rehash
01254     = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);
01255 
01256   // Allocate the new node before doing the rehash so that we don't
01257   // do a rehash if the allocation throws.
01258   node* new_node = m_allocate_node (v);
01259 
01260   try {
01261     if (do_rehash.first) {
01262       n = this->bucket_index (k, code, do_rehash.second);
01263       m_rehash(do_rehash.second);
01264     }
01265 
01266     new_node->m_next = m_buckets[n];
01267     this->store_code(new_node, code);
01268     m_buckets[n] = new_node;
01269     ++m_element_count;
01270     return std::make_pair(iterator (new_node, m_buckets + n), true);
01271   }
01272   catch (...) {
01273     m_deallocate_node (new_node);
01274     __throw_exception_again;
01275   }
01276 }
01277 
01278 // Insert v unconditionally.
01279 template <typename K, typename V, 
01280       typename A, typename Ex, typename Eq,
01281       typename H1, typename H2, typename H, typename RP,
01282       bool c, bool m, bool u>
01283 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator
01284 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
01285 ::insert (const value_type& v, std::tr1::false_type)
01286 {
01287   std::pair<bool, std::size_t> do_rehash
01288     = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);
01289   if (do_rehash.first)
01290     m_rehash(do_rehash.second);
01291 
01292   const key_type& k = this->m_extract(v);
01293   typename hashtable::hash_code_t code = this->m_hash_code (k);
01294   size_type n = this->bucket_index (k, code, m_bucket_count);
01295 
01296   node* new_node = m_allocate_node (v);
01297   node* prev = find_node (m_buckets[n], k, code);
01298   if (prev) {
01299     new_node->m_next = prev->m_next;
01300     prev->m_next = new_node;
01301   }
01302   else {
01303     new_node->m_next = m_buckets[n];
01304     m_buckets[n] = new_node;
01305   }
01306   this->store_code(new_node, code);
01307 
01308   ++m_element_count;
01309   return iterator (new_node, m_buckets + n);
01310 }
01311 
01312 template <typename K, typename V, 
01313       typename A, typename Ex, typename Eq,
01314       typename H1, typename H2, typename H, typename RP,
01315       bool c, bool m, bool u>
01316 template <typename InIter>
01317 void 
01318 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::insert(InIter first, InIter last)
01319 {
01320   size_type n_elt = Internal::distance_fw (first, last);
01321   std::pair<bool, std::size_t> do_rehash
01322     = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, n_elt);
01323   if (do_rehash.first)
01324     m_rehash(do_rehash.second);
01325 
01326   for (; first != last; ++first)
01327     this->insert (*first);
01328 }
01329 
01330 // XXX We're following the TR in giving this a return type of void,
01331 // but that ought to change.  The return type should be const_iterator,
01332 // and it should return the iterator following the one we've erased.
01333 // That would simplify range erase.
01334 template <typename K, typename V, 
01335       typename A, typename Ex, typename Eq,
01336       typename H1, typename H2, typename H, typename RP,
01337       bool c, bool m, bool u>
01338 void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::erase (const_iterator i)
01339 {
01340   node* p = i.m_cur_node;
01341   node* cur = *i.m_cur_bucket;
01342   if (cur == p)
01343     *i.m_cur_bucket = cur->m_next;
01344   else {
01345     node* next = cur->m_next;
01346     while (next != p) {
01347       cur = next;
01348       next = cur->m_next;
01349     }
01350     cur->m_next = next->m_next;
01351   }
01352 
01353   m_deallocate_node (p);
01354   --m_element_count;
01355 }
01356 
01357 template <typename K, typename V, 
01358       typename A, typename Ex, typename Eq,
01359       typename H1, typename H2, typename H, typename RP,
01360       bool c, bool m, bool u>
01361 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::size_type 
01362 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::erase(const key_type& k)
01363 {
01364   typename hashtable::hash_code_t code = this->m_hash_code (k);
01365   size_type n = this->bucket_index (k, code, m_bucket_count);
01366   size_type result = 0;
01367 
01368   node** slot = m_buckets + n;
01369   while (*slot && ! this->compare (k, code, *slot))
01370     slot = &((*slot)->m_next);
01371 
01372   while (*slot && this->compare (k, code, *slot)) {
01373     node* n = *slot;
01374     *slot = n->m_next;
01375     m_deallocate_node (n);
01376     --m_element_count;
01377     ++result;
01378   }
01379 
01380   return result;
01381 }
01382 
01383 // ??? This could be optimized by taking advantage of the bucket
01384 // structure, but it's not clear that it's worth doing.  It probably
01385 // wouldn't even be an optimization unless the load factor is large.
01386 template <typename K, typename V,
01387       typename A, typename Ex, typename Eq,
01388       typename H1, typename H2, typename H, typename RP,
01389       bool c, bool m, bool u>
01390 void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
01391 ::erase(const_iterator first, const_iterator last)
01392 {
01393   while (first != last) {
01394     const_iterator next = first;
01395     ++next;
01396     this->erase(first);
01397     first = next;
01398   }
01399 }
01400 
01401 template <typename K, typename V, 
01402       typename A, typename Ex, typename Eq,
01403       typename H1, typename H2, typename H, typename RP,
01404       bool c, bool m, bool u>
01405 void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::clear()
01406 {
01407   m_deallocate_nodes (m_buckets, m_bucket_count);
01408   m_element_count = 0;
01409 }
01410 
01411 template <typename K, typename V, 
01412       typename A, typename Ex, typename Eq,
01413       typename H1, typename H2, typename H, typename RP,
01414       bool c, bool m, bool u>
01415 void
01416 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_rehash (size_type N)
01417 {
01418   node** new_array = m_allocate_buckets (N);
01419   try {
01420     for (size_type i = 0; i < m_bucket_count; ++i)
01421       while (node* p = m_buckets[i]) {
01422     size_type new_index = this->bucket_index (p, N);
01423     m_buckets[i] = p->m_next;
01424     p->m_next = new_array[new_index];
01425     new_array[new_index] = p;
01426       }
01427     m_deallocate_buckets (m_buckets, m_bucket_count);
01428     m_bucket_count = N;
01429     m_buckets = new_array;
01430   }
01431   catch (...) {
01432     // A failure here means that a hash function threw an exception.
01433     // We can't restore the previous state without calling the hash
01434     // function again, so the only sensible recovery is to delete
01435     // everything.
01436     m_deallocate_nodes (new_array, N);
01437     m_deallocate_buckets (new_array, N);
01438     m_deallocate_nodes (m_buckets, m_bucket_count);
01439     m_element_count = 0;
01440     __throw_exception_again;
01441   }
01442 }
01443 
01444 } }             // Namespace std::tr1
01445 
01446 #endif /* GNU_LIBSTDCXX_TR1_HASHTABLE_ */
01447 

Generated on Tue May 23 12:55:27 2006 for libstdc++ source by  doxygen 1.4.4