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

Generated on Sat Oct 1 15:08:52 2005 for libstdc++ source by  doxygen 1.4.4