hashtable_policy.h

Go to the documentation of this file.
00001 // Internal policy header for TR1 unordered_set and unordered_map -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file tr1_impl/hashtable_policy.h
00026  *  This is an internal header file, included by other library headers.
00027  *  You should not attempt to use it directly.
00028  */
00029 
00030 namespace std
00031 { 
00032 _GLIBCXX_BEGIN_NAMESPACE_TR1
00033 
00034 namespace __detail
00035 {
00036   // Helper function: return distance(first, last) for forward
00037   // iterators, or 0 for input iterators.
00038   template<class _Iterator>
00039     inline typename std::iterator_traits<_Iterator>::difference_type
00040     __distance_fw(_Iterator __first, _Iterator __last,
00041           std::input_iterator_tag)
00042     { return 0; }
00043 
00044   template<class _Iterator>
00045     inline typename std::iterator_traits<_Iterator>::difference_type
00046     __distance_fw(_Iterator __first, _Iterator __last,
00047           std::forward_iterator_tag)
00048     { return std::distance(__first, __last); }
00049 
00050   template<class _Iterator>
00051     inline typename std::iterator_traits<_Iterator>::difference_type
00052     __distance_fw(_Iterator __first, _Iterator __last)
00053     {
00054       typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
00055       return __distance_fw(__first, __last, _Tag());
00056     }
00057 
00058   template<typename _RAIter, typename _Tp>
00059     _RAIter
00060     __lower_bound(_RAIter __first, _RAIter __last, const _Tp& __val)
00061     {
00062       typedef typename std::iterator_traits<_RAIter>::difference_type _DType;
00063 
00064       _DType __len = __last - __first;
00065       while (__len > 0)
00066     {
00067       _DType __half = __len >> 1;
00068       _RAIter __middle = __first + __half;
00069       if (*__middle < __val)
00070         {
00071           __first = __middle;
00072           ++__first;
00073           __len = __len - __half - 1;
00074         }
00075       else
00076         __len = __half;
00077     }
00078       return __first;
00079     }
00080 
00081   // Auxiliary types used for all instantiations of _Hashtable: nodes
00082   // and iterators.
00083   
00084   // Nodes, used to wrap elements stored in the hash table.  A policy
00085   // template parameter of class template _Hashtable controls whether
00086   // nodes also store a hash code. In some cases (e.g. strings) this
00087   // may be a performance win.
00088   template<typename _Value, bool __cache_hash_code>
00089     struct _Hash_node;
00090 
00091   template<typename _Value>
00092     struct _Hash_node<_Value, true>
00093     {
00094       _Value       _M_v;
00095       std::size_t  _M_hash_code;
00096       _Hash_node*  _M_next;
00097 
00098 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
00099       template<typename... _Args>
00100         _Hash_node(_Args&&... __args)
00101       : _M_v(std::forward<_Args>(__args)...),
00102         _M_hash_code(), _M_next() { }
00103 #endif
00104     };
00105 
00106   template<typename _Value>
00107     struct _Hash_node<_Value, false>
00108     {
00109       _Value       _M_v;
00110       _Hash_node*  _M_next;
00111 
00112 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
00113       template<typename... _Args>
00114         _Hash_node(_Args&&... __args)
00115       : _M_v(std::forward<_Args>(__args)...),
00116         _M_next() { }
00117 #endif
00118     };
00119 
00120   // Local iterators, used to iterate within a bucket but not between
00121   // buckets.
00122   template<typename _Value, bool __cache>
00123     struct _Node_iterator_base
00124     {
00125       _Node_iterator_base(_Hash_node<_Value, __cache>* __p)
00126       : _M_cur(__p) { }
00127       
00128       void
00129       _M_incr()
00130       { _M_cur = _M_cur->_M_next; }
00131 
00132       _Hash_node<_Value, __cache>*  _M_cur;
00133     };
00134 
00135   template<typename _Value, bool __cache>
00136     inline bool
00137     operator==(const _Node_iterator_base<_Value, __cache>& __x,
00138            const _Node_iterator_base<_Value, __cache>& __y)
00139     { return __x._M_cur == __y._M_cur; }
00140 
00141   template<typename _Value, bool __cache>
00142     inline bool
00143     operator!=(const _Node_iterator_base<_Value, __cache>& __x,
00144            const _Node_iterator_base<_Value, __cache>& __y)
00145     { return __x._M_cur != __y._M_cur; }
00146 
00147   template<typename _Value, bool __constant_iterators, bool __cache>
00148     struct _Node_iterator
00149     : public _Node_iterator_base<_Value, __cache>
00150     {
00151       typedef _Value                                   value_type;
00152       typedef typename
00153       __gnu_cxx::__conditional_type<__constant_iterators,
00154                     const _Value*, _Value*>::__type
00155                                                        pointer;
00156       typedef typename
00157       __gnu_cxx::__conditional_type<__constant_iterators,
00158                     const _Value&, _Value&>::__type
00159                                                        reference;
00160       typedef std::ptrdiff_t                           difference_type;
00161       typedef std::forward_iterator_tag                iterator_category;
00162 
00163       _Node_iterator()
00164       : _Node_iterator_base<_Value, __cache>(0) { }
00165 
00166       explicit
00167       _Node_iterator(_Hash_node<_Value, __cache>* __p)
00168       : _Node_iterator_base<_Value, __cache>(__p) { }
00169 
00170       reference
00171       operator*() const
00172       { return this->_M_cur->_M_v; }
00173   
00174       pointer
00175       operator->() const
00176       { return &this->_M_cur->_M_v; }
00177 
00178       _Node_iterator&
00179       operator++()
00180       { 
00181     this->_M_incr();
00182     return *this; 
00183       }
00184   
00185       _Node_iterator
00186       operator++(int)
00187       { 
00188     _Node_iterator __tmp(*this);
00189     this->_M_incr();
00190     return __tmp;
00191       }
00192     };
00193 
00194   template<typename _Value, bool __constant_iterators, bool __cache>
00195     struct _Node_const_iterator
00196     : public _Node_iterator_base<_Value, __cache>
00197     {
00198       typedef _Value                                   value_type;
00199       typedef const _Value*                            pointer;
00200       typedef const _Value&                            reference;
00201       typedef std::ptrdiff_t                           difference_type;
00202       typedef std::forward_iterator_tag                iterator_category;
00203 
00204       _Node_const_iterator()
00205       : _Node_iterator_base<_Value, __cache>(0) { }
00206 
00207       explicit
00208       _Node_const_iterator(_Hash_node<_Value, __cache>* __p)
00209       : _Node_iterator_base<_Value, __cache>(__p) { }
00210 
00211       _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
00212                __cache>& __x)
00213       : _Node_iterator_base<_Value, __cache>(__x._M_cur) { }
00214 
00215       reference
00216       operator*() const
00217       { return this->_M_cur->_M_v; }
00218   
00219       pointer
00220       operator->() const
00221       { return &this->_M_cur->_M_v; }
00222 
00223       _Node_const_iterator&
00224       operator++()
00225       { 
00226     this->_M_incr();
00227     return *this; 
00228       }
00229   
00230       _Node_const_iterator
00231       operator++(int)
00232       { 
00233     _Node_const_iterator __tmp(*this);
00234     this->_M_incr();
00235     return __tmp;
00236       }
00237     };
00238 
00239   template<typename _Value, bool __cache>
00240     struct _Hashtable_iterator_base
00241     {
00242       _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node,
00243                    _Hash_node<_Value, __cache>** __bucket)
00244       : _M_cur_node(__node), _M_cur_bucket(__bucket) { }
00245 
00246       void
00247       _M_incr()
00248       {
00249     _M_cur_node = _M_cur_node->_M_next;
00250     if (!_M_cur_node)
00251       _M_incr_bucket();
00252       }
00253 
00254       void
00255       _M_incr_bucket();
00256 
00257       _Hash_node<_Value, __cache>*   _M_cur_node;
00258       _Hash_node<_Value, __cache>**  _M_cur_bucket;
00259     };
00260 
00261   // Global iterators, used for arbitrary iteration within a hash
00262   // table.  Larger and more expensive than local iterators.
00263   template<typename _Value, bool __cache>
00264     void
00265     _Hashtable_iterator_base<_Value, __cache>::
00266     _M_incr_bucket()
00267     {
00268       ++_M_cur_bucket;
00269 
00270       // This loop requires the bucket array to have a non-null sentinel.
00271       while (!*_M_cur_bucket)
00272     ++_M_cur_bucket;
00273       _M_cur_node = *_M_cur_bucket;
00274     }
00275 
00276   template<typename _Value, bool __cache>
00277     inline bool
00278     operator==(const _Hashtable_iterator_base<_Value, __cache>& __x,
00279            const _Hashtable_iterator_base<_Value, __cache>& __y)
00280     { return __x._M_cur_node == __y._M_cur_node; }
00281 
00282   template<typename _Value, bool __cache>
00283     inline bool
00284     operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x,
00285            const _Hashtable_iterator_base<_Value, __cache>& __y)
00286     { return __x._M_cur_node != __y._M_cur_node; }
00287 
00288   template<typename _Value, bool __constant_iterators, bool __cache>
00289     struct _Hashtable_iterator
00290     : public _Hashtable_iterator_base<_Value, __cache>
00291     {
00292       typedef _Value                                   value_type;
00293       typedef typename
00294       __gnu_cxx::__conditional_type<__constant_iterators,
00295                     const _Value*, _Value*>::__type
00296                                                        pointer;
00297       typedef typename
00298       __gnu_cxx::__conditional_type<__constant_iterators,
00299                     const _Value&, _Value&>::__type
00300                                                        reference;
00301       typedef std::ptrdiff_t                           difference_type;
00302       typedef std::forward_iterator_tag                iterator_category;
00303 
00304       _Hashtable_iterator()
00305       : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
00306 
00307       _Hashtable_iterator(_Hash_node<_Value, __cache>* __p,
00308               _Hash_node<_Value, __cache>** __b)
00309       : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
00310 
00311       explicit
00312       _Hashtable_iterator(_Hash_node<_Value, __cache>** __b)
00313       : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
00314 
00315       reference
00316       operator*() const
00317       { return this->_M_cur_node->_M_v; }
00318   
00319       pointer
00320       operator->() const
00321       { return &this->_M_cur_node->_M_v; }
00322 
00323       _Hashtable_iterator&
00324       operator++()
00325       { 
00326     this->_M_incr();
00327     return *this;
00328       }
00329   
00330       _Hashtable_iterator
00331       operator++(int)
00332       { 
00333     _Hashtable_iterator __tmp(*this);
00334     this->_M_incr();
00335     return __tmp;
00336       }
00337     };
00338 
00339   template<typename _Value, bool __constant_iterators, bool __cache>
00340     struct _Hashtable_const_iterator
00341     : public _Hashtable_iterator_base<_Value, __cache>
00342     {
00343       typedef _Value                                   value_type;
00344       typedef const _Value*                            pointer;
00345       typedef const _Value&                            reference;
00346       typedef std::ptrdiff_t                           difference_type;
00347       typedef std::forward_iterator_tag                iterator_category;
00348 
00349       _Hashtable_const_iterator()
00350       : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
00351 
00352       _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p,
00353                 _Hash_node<_Value, __cache>** __b)
00354       : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
00355 
00356       explicit
00357       _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b)
00358       : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
00359 
00360       _Hashtable_const_iterator(const _Hashtable_iterator<_Value,
00361                 __constant_iterators, __cache>& __x)
00362       : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node,
00363                           __x._M_cur_bucket) { }
00364 
00365       reference
00366       operator*() const
00367       { return this->_M_cur_node->_M_v; }
00368   
00369       pointer
00370       operator->() const
00371       { return &this->_M_cur_node->_M_v; }
00372 
00373       _Hashtable_const_iterator&
00374       operator++()
00375       { 
00376     this->_M_incr();
00377     return *this;
00378       }
00379   
00380       _Hashtable_const_iterator
00381       operator++(int)
00382       { 
00383     _Hashtable_const_iterator __tmp(*this);
00384     this->_M_incr();
00385     return __tmp;
00386       }
00387     };
00388 
00389 
00390   // Many of class template _Hashtable's template parameters are policy
00391   // classes.  These are defaults for the policies.
00392 
00393   // Default range hashing function: use division to fold a large number
00394   // into the range [0, N).
00395   struct _Mod_range_hashing
00396   {
00397     typedef std::size_t first_argument_type;
00398     typedef std::size_t second_argument_type;
00399     typedef std::size_t result_type;
00400 
00401     result_type
00402     operator()(first_argument_type __num, second_argument_type __den) const
00403     { return __num % __den; }
00404   };
00405 
00406   // Default ranged hash function H.  In principle it should be a
00407   // function object composed from objects of type H1 and H2 such that
00408   // h(k, N) = h2(h1(k), N), but that would mean making extra copies of
00409   // h1 and h2.  So instead we'll just use a tag to tell class template
00410   // hashtable to do that composition.
00411   struct _Default_ranged_hash { };
00412 
00413   // Default value for rehash policy.  Bucket size is (usually) the
00414   // smallest prime that keeps the load factor small enough.
00415   struct _Prime_rehash_policy
00416   {
00417     _Prime_rehash_policy(float __z = 1.0)
00418     : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0) { }
00419 
00420     float
00421     max_load_factor() const
00422     { return _M_max_load_factor; }      
00423 
00424     // Return a bucket size no smaller than n.
00425     std::size_t
00426     _M_next_bkt(std::size_t __n) const;
00427     
00428     // Return a bucket count appropriate for n elements
00429     std::size_t
00430     _M_bkt_for_elements(std::size_t __n) const;
00431     
00432     // __n_bkt is current bucket count, __n_elt is current element count,
00433     // and __n_ins is number of elements to be inserted.  Do we need to
00434     // increase bucket count?  If so, return make_pair(true, n), where n
00435     // is the new bucket count.  If not, return make_pair(false, 0).
00436     std::pair<bool, std::size_t>
00437     _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
00438            std::size_t __n_ins) const;
00439 
00440     enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
00441 
00442     float                _M_max_load_factor;
00443     float                _M_growth_factor;
00444     mutable std::size_t  _M_next_resize;
00445   };
00446 
00447   extern const unsigned long __prime_list[];
00448 
00449   // XXX This is a hack.  There's no good reason for any of
00450   // _Prime_rehash_policy's member functions to be inline.  
00451 
00452   // Return a prime no smaller than n.
00453   inline std::size_t
00454   _Prime_rehash_policy::
00455   _M_next_bkt(std::size_t __n) const
00456   {
00457     const unsigned long* __p = __lower_bound(__prime_list, __prime_list
00458                          + _S_n_primes, __n);
00459     _M_next_resize = 
00460       static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
00461     return *__p;
00462   }
00463 
00464   // Return the smallest prime p such that alpha p >= n, where alpha
00465   // is the load factor.
00466   inline std::size_t
00467   _Prime_rehash_policy::
00468   _M_bkt_for_elements(std::size_t __n) const
00469   {
00470     const float __min_bkts = __n / _M_max_load_factor;
00471     const unsigned long* __p = __lower_bound(__prime_list, __prime_list
00472                          + _S_n_primes, __min_bkts);
00473     _M_next_resize =
00474       static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
00475     return *__p;
00476   }
00477 
00478   // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
00479   // If p > __n_bkt, return make_pair(true, p); otherwise return
00480   // make_pair(false, 0).  In principle this isn't very different from 
00481   // _M_bkt_for_elements.
00482 
00483   // The only tricky part is that we're caching the element count at
00484   // which we need to rehash, so we don't have to do a floating-point
00485   // multiply for every insertion.
00486 
00487   inline std::pair<bool, std::size_t>
00488   _Prime_rehash_policy::
00489   _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
00490          std::size_t __n_ins) const
00491   {
00492     if (__n_elt + __n_ins > _M_next_resize)
00493       {
00494     float __min_bkts = ((float(__n_ins) + float(__n_elt))
00495                 / _M_max_load_factor);
00496     if (__min_bkts > __n_bkt)
00497       {
00498         __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
00499         const unsigned long* __p =
00500           __lower_bound(__prime_list, __prime_list + _S_n_primes,
00501                 __min_bkts);
00502         _M_next_resize = static_cast<std::size_t>
00503           (__builtin_ceil(*__p * _M_max_load_factor));
00504         return std::make_pair(true, *__p);
00505       }
00506     else 
00507       {
00508         _M_next_resize = static_cast<std::size_t>
00509           (__builtin_ceil(__n_bkt * _M_max_load_factor));
00510         return std::make_pair(false, 0);
00511       }
00512       }
00513     else
00514       return std::make_pair(false, 0);
00515   }
00516 
00517   // Base classes for std::tr1::_Hashtable.  We define these base
00518   // classes because in some cases we want to do different things
00519   // depending on the value of a policy class.  In some cases the
00520   // policy class affects which member functions and nested typedefs
00521   // are defined; we handle that by specializing base class templates.
00522   // Several of the base class templates need to access other members
00523   // of class template _Hashtable, so we use the "curiously recurring
00524   // template pattern" for them.
00525 
00526   // class template _Map_base.  If the hashtable has a value type of the
00527   // form pair<T1, T2> and a key extraction policy that returns the
00528   // first part of the pair, the hashtable gets a mapped_type typedef.
00529   // If it satisfies those criteria and also has unique keys, then it
00530   // also gets an operator[].  
00531   template<typename _Key, typename _Value, typename _Ex, bool __unique,
00532        typename _Hashtable>
00533     struct _Map_base { };
00534       
00535   template<typename _Key, typename _Pair, typename _Hashtable>
00536     struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable>
00537     {
00538       typedef typename _Pair::second_type mapped_type;
00539     };
00540 
00541   template<typename _Key, typename _Pair, typename _Hashtable>
00542     struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>
00543     {
00544       typedef typename _Pair::second_type mapped_type;
00545       
00546       mapped_type&
00547       operator[](const _Key& __k);
00548 
00549 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
00550       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00551       // DR 761. unordered_map needs an at() member function.
00552       mapped_type&
00553       at(const _Key& __k);
00554 
00555       const mapped_type&
00556       at(const _Key& __k) const;
00557 #endif
00558     };
00559 
00560   template<typename _Key, typename _Pair, typename _Hashtable>
00561     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
00562                true, _Hashtable>::mapped_type&
00563     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
00564     operator[](const _Key& __k)
00565     {
00566       _Hashtable* __h = static_cast<_Hashtable*>(this);
00567       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
00568       std::size_t __n = __h->_M_bucket_index(__k, __code,
00569                          __h->_M_bucket_count);
00570 
00571       typename _Hashtable::_Node* __p =
00572     __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
00573       if (!__p)
00574     return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()),
00575                      __n, __code)->second;
00576       return (__p->_M_v).second;
00577     }
00578 
00579 #ifdef _GLIBCXX_INCLUDE_AS_CXX0X
00580   template<typename _Key, typename _Pair, typename _Hashtable>
00581     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
00582                true, _Hashtable>::mapped_type&
00583     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
00584     at(const _Key& __k)
00585     {
00586       _Hashtable* __h = static_cast<_Hashtable*>(this);
00587       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
00588       std::size_t __n = __h->_M_bucket_index(__k, __code,
00589                          __h->_M_bucket_count);
00590 
00591       typename _Hashtable::_Node* __p =
00592     __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
00593       if (!__p)
00594     __throw_out_of_range(__N("_Map_base::at"));
00595       return (__p->_M_v).second;
00596     }
00597 
00598   template<typename _Key, typename _Pair, typename _Hashtable>
00599     const typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
00600                  true, _Hashtable>::mapped_type&
00601     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
00602     at(const _Key& __k) const
00603     {
00604       const _Hashtable* __h = static_cast<const _Hashtable*>(this);
00605       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
00606       std::size_t __n = __h->_M_bucket_index(__k, __code,
00607                          __h->_M_bucket_count);
00608 
00609       typename _Hashtable::_Node* __p =
00610     __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
00611       if (!__p)
00612     __throw_out_of_range(__N("_Map_base::at"));
00613       return (__p->_M_v).second;
00614     }
00615 #endif
00616 
00617   // class template _Rehash_base.  Give hashtable the max_load_factor
00618   // functions iff the rehash policy is _Prime_rehash_policy.
00619   template<typename _RehashPolicy, typename _Hashtable>
00620     struct _Rehash_base { };
00621 
00622   template<typename _Hashtable>
00623     struct _Rehash_base<_Prime_rehash_policy, _Hashtable>
00624     {
00625       float
00626       max_load_factor() const
00627       {
00628     const _Hashtable* __this = static_cast<const _Hashtable*>(this);
00629     return __this->__rehash_policy().max_load_factor();
00630       }
00631 
00632       void
00633       max_load_factor(float __z)
00634       {
00635     _Hashtable* __this = static_cast<_Hashtable*>(this);
00636     __this->__rehash_policy(_Prime_rehash_policy(__z));
00637       }
00638     };
00639 
00640   // Class template _Hash_code_base.  Encapsulates two policy issues that
00641   // aren't quite orthogonal.
00642   //   (1) the difference between using a ranged hash function and using
00643   //       the combination of a hash function and a range-hashing function.
00644   //       In the former case we don't have such things as hash codes, so
00645   //       we have a dummy type as placeholder.
00646   //   (2) Whether or not we cache hash codes.  Caching hash codes is
00647   //       meaningless if we have a ranged hash function.
00648   // We also put the key extraction and equality comparison function 
00649   // objects here, for convenience.
00650   
00651   // Primary template: unused except as a hook for specializations.  
00652   template<typename _Key, typename _Value,
00653        typename _ExtractKey, typename _Equal,
00654        typename _H1, typename _H2, typename _Hash,
00655        bool __cache_hash_code>
00656     struct _Hash_code_base;
00657 
00658   // Specialization: ranged hash function, no caching hash codes.  H1
00659   // and H2 are provided but ignored.  We define a dummy hash code type.
00660   template<typename _Key, typename _Value,
00661        typename _ExtractKey, typename _Equal,
00662        typename _H1, typename _H2, typename _Hash>
00663     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00664                _Hash, false>
00665     {
00666     protected:
00667       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
00668               const _H1&, const _H2&, const _Hash& __h)
00669       : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { }
00670 
00671       typedef void* _Hash_code_type;
00672   
00673       _Hash_code_type
00674       _M_hash_code(const _Key& __key) const
00675       { return 0; }
00676   
00677       std::size_t
00678       _M_bucket_index(const _Key& __k, _Hash_code_type,
00679               std::size_t __n) const
00680       { return _M_ranged_hash(__k, __n); }
00681 
00682       std::size_t
00683       _M_bucket_index(const _Hash_node<_Value, false>* __p,
00684               std::size_t __n) const
00685       { return _M_ranged_hash(_M_extract(__p->_M_v), __n); }
00686   
00687       bool
00688       _M_compare(const _Key& __k, _Hash_code_type,
00689          _Hash_node<_Value, false>* __n) const
00690       { return _M_eq(__k, _M_extract(__n->_M_v)); }
00691 
00692       void
00693       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
00694       { }
00695 
00696       void
00697       _M_copy_code(_Hash_node<_Value, false>*,
00698            const _Hash_node<_Value, false>*) const
00699       { }
00700       
00701       void
00702       _M_swap(_Hash_code_base& __x)
00703       {
00704     std::swap(_M_extract, __x._M_extract);
00705     std::swap(_M_eq, __x._M_eq);
00706     std::swap(_M_ranged_hash, __x._M_ranged_hash);
00707       }
00708 
00709     protected:
00710       _ExtractKey  _M_extract;
00711       _Equal       _M_eq;
00712       _Hash        _M_ranged_hash;
00713     };
00714 
00715 
00716   // No specialization for ranged hash function while caching hash codes.
00717   // That combination is meaningless, and trying to do it is an error.
00718   
00719   
00720   // Specialization: ranged hash function, cache hash codes.  This
00721   // combination is meaningless, so we provide only a declaration
00722   // and no definition.  
00723   template<typename _Key, typename _Value,
00724        typename _ExtractKey, typename _Equal,
00725        typename _H1, typename _H2, typename _Hash>
00726     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00727                _Hash, true>;
00728 
00729   // Specialization: hash function and range-hashing function, no
00730   // caching of hash codes.  H is provided but ignored.  Provides
00731   // typedef and accessor required by TR1.  
00732   template<typename _Key, typename _Value,
00733        typename _ExtractKey, typename _Equal,
00734        typename _H1, typename _H2>
00735     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00736                _Default_ranged_hash, false>
00737     {
00738       typedef _H1 hasher;
00739 
00740       hasher
00741       hash_function() const
00742       { return _M_h1; }
00743 
00744     protected:
00745       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
00746               const _H1& __h1, const _H2& __h2,
00747               const _Default_ranged_hash&)
00748       : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
00749 
00750       typedef std::size_t _Hash_code_type;
00751 
00752       _Hash_code_type
00753       _M_hash_code(const _Key& __k) const
00754       { return _M_h1(__k); }
00755       
00756       std::size_t
00757       _M_bucket_index(const _Key&, _Hash_code_type __c,
00758               std::size_t __n) const
00759       { return _M_h2(__c, __n); }
00760 
00761       std::size_t
00762       _M_bucket_index(const _Hash_node<_Value, false>* __p,
00763               std::size_t __n) const
00764       { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); }
00765 
00766       bool
00767       _M_compare(const _Key& __k, _Hash_code_type,
00768          _Hash_node<_Value, false>* __n) const
00769       { return _M_eq(__k, _M_extract(__n->_M_v)); }
00770 
00771       void
00772       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
00773       { }
00774 
00775       void
00776       _M_copy_code(_Hash_node<_Value, false>*,
00777            const _Hash_node<_Value, false>*) const
00778       { }
00779 
00780       void
00781       _M_swap(_Hash_code_base& __x)
00782       {
00783     std::swap(_M_extract, __x._M_extract);
00784     std::swap(_M_eq, __x._M_eq);
00785     std::swap(_M_h1, __x._M_h1);
00786     std::swap(_M_h2, __x._M_h2);
00787       }
00788 
00789     protected:
00790       _ExtractKey  _M_extract;
00791       _Equal       _M_eq;
00792       _H1          _M_h1;
00793       _H2          _M_h2;
00794     };
00795 
00796   // Specialization: hash function and range-hashing function, 
00797   // caching hash codes.  H is provided but ignored.  Provides
00798   // typedef and accessor required by TR1.
00799   template<typename _Key, typename _Value,
00800        typename _ExtractKey, typename _Equal,
00801        typename _H1, typename _H2>
00802     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
00803                _Default_ranged_hash, true>
00804     {
00805       typedef _H1 hasher;
00806       
00807       hasher
00808       hash_function() const
00809       { return _M_h1; }
00810 
00811     protected:
00812       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
00813               const _H1& __h1, const _H2& __h2,
00814               const _Default_ranged_hash&)
00815       : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
00816 
00817       typedef std::size_t _Hash_code_type;
00818   
00819       _Hash_code_type
00820       _M_hash_code(const _Key& __k) const
00821       { return _M_h1(__k); }
00822   
00823       std::size_t
00824       _M_bucket_index(const _Key&, _Hash_code_type __c,
00825               std::size_t __n) const
00826       { return _M_h2(__c, __n); }
00827 
00828       std::size_t
00829       _M_bucket_index(const _Hash_node<_Value, true>* __p,
00830               std::size_t __n) const
00831       { return _M_h2(__p->_M_hash_code, __n); }
00832 
00833       bool
00834       _M_compare(const _Key& __k, _Hash_code_type __c,
00835          _Hash_node<_Value, true>* __n) const
00836       { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); }
00837 
00838       void
00839       _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
00840       { __n->_M_hash_code = __c; }
00841 
00842       void
00843       _M_copy_code(_Hash_node<_Value, true>* __to,
00844            const _Hash_node<_Value, true>* __from) const
00845       { __to->_M_hash_code = __from->_M_hash_code; }
00846 
00847       void
00848       _M_swap(_Hash_code_base& __x)
00849       {
00850     std::swap(_M_extract, __x._M_extract);
00851     std::swap(_M_eq, __x._M_eq);
00852     std::swap(_M_h1, __x._M_h1);
00853     std::swap(_M_h2, __x._M_h2);
00854       }
00855       
00856     protected:
00857       _ExtractKey  _M_extract;
00858       _Equal       _M_eq;
00859       _H1          _M_h1;
00860       _H2          _M_h2;
00861     };
00862 } // namespace __detail
00863 
00864 _GLIBCXX_END_NAMESPACE_TR1
00865 }

Generated on Thu Jul 23 21:16:08 2009 for libstdc++ by  doxygen 1.5.8