LCOV - code coverage report
Current view: top level - tr1 - hashtable_policy.h (source / functions) Hit Total Coverage
Test: stap.info Lines: 76 77 98.7 %
Date: 2013-03-08 Functions: 127 128 99.2 %
Branches: 63 98 64.3 %

           Branch data     Line data    Source code
       1                 :            : // Internal policy header for TR1 unordered_set and unordered_map -*- C++ -*-
       2                 :            : 
       3                 :            : // Copyright (C) 2010, 2011 Free Software Foundation, Inc.
       4                 :            : //
       5                 :            : // This file is part of the GNU ISO C++ Library.  This library is free
       6                 :            : // software; you can redistribute it and/or modify it under the
       7                 :            : // terms of the GNU General Public License as published by the
       8                 :            : // Free Software Foundation; either version 3, or (at your option)
       9                 :            : // any later version.
      10                 :            : 
      11                 :            : // This library is distributed in the hope that it will be useful,
      12                 :            : // but WITHOUT ANY WARRANTY; without even the implied warranty of
      13                 :            : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14                 :            : // GNU General Public License for more details.
      15                 :            : 
      16                 :            : // Under Section 7 of GPL version 3, you are granted additional
      17                 :            : // permissions described in the GCC Runtime Library Exception, version
      18                 :            : // 3.1, as published by the Free Software Foundation.
      19                 :            : 
      20                 :            : // You should have received a copy of the GNU General Public License and
      21                 :            : // a copy of the GCC Runtime Library Exception along with this program;
      22                 :            : // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
      23                 :            : // <http://www.gnu.org/licenses/>.
      24                 :            : 
      25                 :            : /** @file tr1/hashtable_policy.h
      26                 :            :  *  This is an internal header file, included by other library headers.
      27                 :            :  *  Do not attempt to use it directly. 
      28                 :            :  *  @headername{tr1/unordered_map, tr1/unordered_set}
      29                 :            :  */
      30                 :            : 
      31                 :            : namespace std _GLIBCXX_VISIBILITY(default)
      32                 :            : { 
      33                 :            : namespace tr1
      34                 :            : {
      35                 :            : namespace __detail
      36                 :            : {
      37                 :            : _GLIBCXX_BEGIN_NAMESPACE_VERSION
      38                 :            : 
      39                 :            :   // Helper function: return distance(first, last) for forward
      40                 :            :   // iterators, or 0 for input iterators.
      41                 :            :   template<class _Iterator>
      42                 :            :     inline typename std::iterator_traits<_Iterator>::difference_type
      43                 :            :     __distance_fw(_Iterator __first, _Iterator __last,
      44                 :            :                   std::input_iterator_tag)
      45                 :            :     { return 0; }
      46                 :            : 
      47                 :            :   template<class _Iterator>
      48                 :            :     inline typename std::iterator_traits<_Iterator>::difference_type
      49                 :      41297 :     __distance_fw(_Iterator __first, _Iterator __last,
      50                 :            :                   std::forward_iterator_tag)
      51                 :      41297 :     { return std::distance(__first, __last); }
      52                 :            : 
      53                 :            :   template<class _Iterator>
      54                 :            :     inline typename std::iterator_traits<_Iterator>::difference_type
      55                 :      41297 :     __distance_fw(_Iterator __first, _Iterator __last)
      56                 :            :     {
      57                 :            :       typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
      58         [ +  - ]:      41297 :       return __distance_fw(__first, __last, _Tag());
      59                 :            :     }
      60                 :            : 
      61                 :            :   // Auxiliary types used for all instantiations of _Hashtable: nodes
      62                 :            :   // and iterators.
      63                 :            :   
      64                 :            :   // Nodes, used to wrap elements stored in the hash table.  A policy
      65                 :            :   // template parameter of class template _Hashtable controls whether
      66                 :            :   // nodes also store a hash code. In some cases (e.g. strings) this
      67                 :            :   // may be a performance win.
      68                 :            :   template<typename _Value, bool __cache_hash_code>
      69                 :            :     struct _Hash_node;
      70                 :            : 
      71                 :            :   template<typename _Value>
      72                 :            :     struct _Hash_node<_Value, true>
      73                 :            :     {
      74                 :            :       _Value       _M_v;
      75                 :            :       std::size_t  _M_hash_code;
      76                 :            :       _Hash_node*  _M_next;
      77                 :            :     };
      78                 :            : 
      79                 :            :   template<typename _Value>
      80                 :            :     struct _Hash_node<_Value, false>
      81                 :            :     {
      82                 :            :       _Value       _M_v;
      83                 :            :       _Hash_node*  _M_next;
      84                 :            :     };
      85                 :            : 
      86                 :            :   // Local iterators, used to iterate within a bucket but not between
      87                 :            :   // buckets.
      88                 :            :   template<typename _Value, bool __cache>
      89                 :            :     struct _Node_iterator_base
      90                 :            :     {
      91                 :            :       _Node_iterator_base(_Hash_node<_Value, __cache>* __p)
      92                 :            :       : _M_cur(__p) { }
      93                 :            :       
      94                 :            :       void
      95                 :            :       _M_incr()
      96                 :            :       { _M_cur = _M_cur->_M_next; }
      97                 :            : 
      98                 :            :       _Hash_node<_Value, __cache>*  _M_cur;
      99                 :            :     };
     100                 :            : 
     101                 :            :   template<typename _Value, bool __cache>
     102                 :            :     inline bool
     103                 :            :     operator==(const _Node_iterator_base<_Value, __cache>& __x,
     104                 :            :                const _Node_iterator_base<_Value, __cache>& __y)
     105                 :            :     { return __x._M_cur == __y._M_cur; }
     106                 :            : 
     107                 :            :   template<typename _Value, bool __cache>
     108                 :            :     inline bool
     109                 :            :     operator!=(const _Node_iterator_base<_Value, __cache>& __x,
     110                 :            :                const _Node_iterator_base<_Value, __cache>& __y)
     111                 :            :     { return __x._M_cur != __y._M_cur; }
     112                 :            : 
     113                 :            :   template<typename _Value, bool __constant_iterators, bool __cache>
     114                 :            :     struct _Node_iterator
     115                 :            :     : public _Node_iterator_base<_Value, __cache>
     116                 :            :     {
     117                 :            :       typedef _Value                                   value_type;
     118                 :            :       typedef typename
     119                 :            :       __gnu_cxx::__conditional_type<__constant_iterators,
     120                 :            :                                     const _Value*, _Value*>::__type
     121                 :            :                                                        pointer;
     122                 :            :       typedef typename
     123                 :            :       __gnu_cxx::__conditional_type<__constant_iterators,
     124                 :            :                                     const _Value&, _Value&>::__type
     125                 :            :                                                        reference;
     126                 :            :       typedef std::ptrdiff_t                           difference_type;
     127                 :            :       typedef std::forward_iterator_tag                iterator_category;
     128                 :            : 
     129                 :            :       _Node_iterator()
     130                 :            :       : _Node_iterator_base<_Value, __cache>(0) { }
     131                 :            : 
     132                 :            :       explicit
     133                 :            :       _Node_iterator(_Hash_node<_Value, __cache>* __p)
     134                 :            :       : _Node_iterator_base<_Value, __cache>(__p) { }
     135                 :            : 
     136                 :            :       reference
     137                 :            :       operator*() const
     138                 :            :       { return this->_M_cur->_M_v; }
     139                 :            :   
     140                 :            :       pointer
     141                 :            :       operator->() const
     142                 :            :       { return std::__addressof(this->_M_cur->_M_v); }
     143                 :            : 
     144                 :            :       _Node_iterator&
     145                 :            :       operator++()
     146                 :            :       { 
     147                 :            :         this->_M_incr();
     148                 :            :         return *this; 
     149                 :            :       }
     150                 :            :   
     151                 :            :       _Node_iterator
     152                 :            :       operator++(int)
     153                 :            :       { 
     154                 :            :         _Node_iterator __tmp(*this);
     155                 :            :         this->_M_incr();
     156                 :            :         return __tmp;
     157                 :            :       }
     158                 :            :     };
     159                 :            : 
     160                 :            :   template<typename _Value, bool __constant_iterators, bool __cache>
     161                 :            :     struct _Node_const_iterator
     162                 :            :     : public _Node_iterator_base<_Value, __cache>
     163                 :            :     {
     164                 :            :       typedef _Value                                   value_type;
     165                 :            :       typedef const _Value*                            pointer;
     166                 :            :       typedef const _Value&                            reference;
     167                 :            :       typedef std::ptrdiff_t                           difference_type;
     168                 :            :       typedef std::forward_iterator_tag                iterator_category;
     169                 :            : 
     170                 :            :       _Node_const_iterator()
     171                 :            :       : _Node_iterator_base<_Value, __cache>(0) { }
     172                 :            : 
     173                 :            :       explicit
     174                 :            :       _Node_const_iterator(_Hash_node<_Value, __cache>* __p)
     175                 :            :       : _Node_iterator_base<_Value, __cache>(__p) { }
     176                 :            : 
     177                 :            :       _Node_const_iterator(const _Node_iterator<_Value, __constant_iterators,
     178                 :            :                            __cache>& __x)
     179                 :            :       : _Node_iterator_base<_Value, __cache>(__x._M_cur) { }
     180                 :            : 
     181                 :            :       reference
     182                 :            :       operator*() const
     183                 :            :       { return this->_M_cur->_M_v; }
     184                 :            :   
     185                 :            :       pointer
     186                 :            :       operator->() const
     187                 :            :       { return std::__addressof(this->_M_cur->_M_v); }
     188                 :            : 
     189                 :            :       _Node_const_iterator&
     190                 :            :       operator++()
     191                 :            :       { 
     192                 :            :         this->_M_incr();
     193                 :            :         return *this; 
     194                 :            :       }
     195                 :            :   
     196                 :            :       _Node_const_iterator
     197                 :            :       operator++(int)
     198                 :            :       { 
     199                 :            :         _Node_const_iterator __tmp(*this);
     200                 :            :         this->_M_incr();
     201                 :            :         return __tmp;
     202                 :            :       }
     203                 :            :     };
     204                 :            : 
     205                 :            :   template<typename _Value, bool __cache>
     206                 :            :     struct _Hashtable_iterator_base
     207                 :            :     {
     208                 :  351111566 :       _Hashtable_iterator_base(_Hash_node<_Value, __cache>* __node,
     209                 :            :                                _Hash_node<_Value, __cache>** __bucket)
     210                 :  351111566 :       : _M_cur_node(__node), _M_cur_bucket(__bucket) { }
     211                 :            : 
     212                 :            :       void
     213                 :   48167284 :       _M_incr()
     214                 :            :       {
     215                 :   48167284 :         _M_cur_node = _M_cur_node->_M_next;
     216 [ +  + ][ +  + ]:   48167284 :         if (!_M_cur_node)
         [ +  - ][ +  + ]
         [ +  + ][ #  # ]
                 [ +  + ]
     217                 :   21398331 :           _M_incr_bucket();
     218                 :   48167284 :       }
     219                 :            : 
     220                 :            :       void
     221                 :            :       _M_incr_bucket();
     222                 :            : 
     223                 :            :       _Hash_node<_Value, __cache>*   _M_cur_node;
     224                 :            :       _Hash_node<_Value, __cache>**  _M_cur_bucket;
     225                 :            :     };
     226                 :            : 
     227                 :            :   // Global iterators, used for arbitrary iteration within a hash
     228                 :            :   // table.  Larger and more expensive than local iterators.
     229                 :            :   template<typename _Value, bool __cache>
     230                 :            :     void
     231                 :   21552590 :     _Hashtable_iterator_base<_Value, __cache>::
     232                 :            :     _M_incr_bucket()
     233                 :            :     {
     234                 :   21552590 :       ++_M_cur_bucket;
     235                 :            : 
     236                 :            :       // This loop requires the bucket array to have a non-null sentinel.
     237 [ +  + ][ +  + ]:   64131122 :       while (!*_M_cur_bucket)
         [ +  + ][ +  + ]
         [ +  + ][ #  # ]
                 [ +  + ]
     238                 :   42578532 :         ++_M_cur_bucket;
     239                 :   21552590 :       _M_cur_node = *_M_cur_bucket;
     240                 :   21552590 :     }
     241                 :            : 
     242                 :            :   template<typename _Value, bool __cache>
     243                 :            :     inline bool
     244                 :   80567326 :     operator==(const _Hashtable_iterator_base<_Value, __cache>& __x,
     245                 :            :                const _Hashtable_iterator_base<_Value, __cache>& __y)
     246                 :   80567326 :     { return __x._M_cur_node == __y._M_cur_node; }
     247                 :            : 
     248                 :            :   template<typename _Value, bool __cache>
     249                 :            :     inline bool
     250                 :   57349959 :     operator!=(const _Hashtable_iterator_base<_Value, __cache>& __x,
     251                 :            :                const _Hashtable_iterator_base<_Value, __cache>& __y)
     252                 :   57349959 :     { return __x._M_cur_node != __y._M_cur_node; }
     253                 :            : 
     254                 :            :   template<typename _Value, bool __constant_iterators, bool __cache>
     255                 :            :     struct _Hashtable_iterator
     256                 :            :     : public _Hashtable_iterator_base<_Value, __cache>
     257                 :            :     {
     258                 :            :       typedef _Value                                   value_type;
     259                 :            :       typedef typename
     260                 :            :       __gnu_cxx::__conditional_type<__constant_iterators,
     261                 :            :                                     const _Value*, _Value*>::__type
     262                 :            :                                                        pointer;
     263                 :            :       typedef typename
     264                 :            :       __gnu_cxx::__conditional_type<__constant_iterators,
     265                 :            :                                     const _Value&, _Value&>::__type
     266                 :            :                                                        reference;
     267                 :            :       typedef std::ptrdiff_t                           difference_type;
     268                 :            :       typedef std::forward_iterator_tag                iterator_category;
     269                 :            : 
     270                 :     210586 :       _Hashtable_iterator()
     271                 :     210586 :       : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
     272                 :            : 
     273                 :  123825676 :       _Hashtable_iterator(_Hash_node<_Value, __cache>* __p,
     274                 :            :                           _Hash_node<_Value, __cache>** __b)
     275                 :  123825676 :       : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
     276                 :            : 
     277                 :            :       explicit
     278                 :  227075304 :       _Hashtable_iterator(_Hash_node<_Value, __cache>** __b)
     279                 :  227075304 :       : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
     280                 :            : 
     281                 :            :       reference
     282                 :    8712113 :       operator*() const
     283                 :    8712113 :       { return this->_M_cur_node->_M_v; }
     284                 :            :   
     285                 :            :       pointer
     286                 :  164907009 :       operator->() const
     287                 :  164907009 :       { return std::__addressof(this->_M_cur_node->_M_v); }
     288                 :            : 
     289                 :            :       _Hashtable_iterator&
     290                 :   12009309 :       operator++()
     291                 :            :       { 
     292                 :   12009309 :         this->_M_incr();
     293                 :   12009309 :         return *this;
     294                 :            :       }
     295                 :            :   
     296                 :            :       _Hashtable_iterator
     297                 :   36157975 :       operator++(int)
     298                 :            :       { 
     299                 :   36157975 :         _Hashtable_iterator __tmp(*this);
     300                 :   36157975 :         this->_M_incr();
     301                 :   36157975 :         return __tmp;
     302                 :            :       }
     303                 :            :     };
     304                 :            : 
     305                 :            :   template<typename _Value, bool __constant_iterators, bool __cache>
     306                 :            :     struct _Hashtable_const_iterator
     307                 :            :     : public _Hashtable_iterator_base<_Value, __cache>
     308                 :            :     {
     309                 :            :       typedef _Value                                   value_type;
     310                 :            :       typedef const _Value*                            pointer;
     311                 :            :       typedef const _Value&                            reference;
     312                 :            :       typedef std::ptrdiff_t                           difference_type;
     313                 :            :       typedef std::forward_iterator_tag                iterator_category;
     314                 :            : 
     315                 :            :       _Hashtable_const_iterator()
     316                 :            :       : _Hashtable_iterator_base<_Value, __cache>(0, 0) { }
     317                 :            : 
     318                 :            :       _Hashtable_const_iterator(_Hash_node<_Value, __cache>* __p,
     319                 :            :                                 _Hash_node<_Value, __cache>** __b)
     320                 :            :       : _Hashtable_iterator_base<_Value, __cache>(__p, __b) { }
     321                 :            : 
     322                 :            :       explicit
     323                 :            :       _Hashtable_const_iterator(_Hash_node<_Value, __cache>** __b)
     324                 :            :       : _Hashtable_iterator_base<_Value, __cache>(*__b, __b) { }
     325                 :            : 
     326                 :            :       _Hashtable_const_iterator(const _Hashtable_iterator<_Value,
     327                 :            :                                 __constant_iterators, __cache>& __x)
     328                 :            :       : _Hashtable_iterator_base<_Value, __cache>(__x._M_cur_node,
     329                 :            :                                                   __x._M_cur_bucket) { }
     330                 :            : 
     331                 :            :       reference
     332                 :            :       operator*() const
     333                 :            :       { return this->_M_cur_node->_M_v; }
     334                 :            :   
     335                 :            :       pointer
     336                 :            :       operator->() const
     337                 :            :       { return std::__addressof(this->_M_cur_node->_M_v); }
     338                 :            : 
     339                 :            :       _Hashtable_const_iterator&
     340                 :            :       operator++()
     341                 :            :       { 
     342                 :            :         this->_M_incr();
     343                 :            :         return *this;
     344                 :            :       }
     345                 :            :   
     346                 :            :       _Hashtable_const_iterator
     347                 :            :       operator++(int)
     348                 :            :       { 
     349                 :            :         _Hashtable_const_iterator __tmp(*this);
     350                 :            :         this->_M_incr();
     351                 :            :         return __tmp;
     352                 :            :       }
     353                 :            :     };
     354                 :            : 
     355                 :            : 
     356                 :            :   // Many of class template _Hashtable's template parameters are policy
     357                 :            :   // classes.  These are defaults for the policies.
     358                 :            : 
     359                 :            :   // Default range hashing function: use division to fold a large number
     360                 :            :   // into the range [0, N).
     361                 :            :   struct _Mod_range_hashing
     362                 :            :   {
     363                 :            :     typedef std::size_t first_argument_type;
     364                 :            :     typedef std::size_t second_argument_type;
     365                 :            :     typedef std::size_t result_type;
     366                 :            : 
     367                 :            :     result_type
     368                 :  392373689 :     operator()(first_argument_type __num, second_argument_type __den) const
     369                 :  392373689 :     { return __num % __den; }
     370                 :            :   };
     371                 :            : 
     372                 :            :   // Default ranged hash function H.  In principle it should be a
     373                 :            :   // function object composed from objects of type H1 and H2 such that
     374                 :            :   // h(k, N) = h2(h1(k), N), but that would mean making extra copies of
     375                 :            :   // h1 and h2.  So instead we'll just use a tag to tell class template
     376                 :            :   // hashtable to do that composition.
     377                 :            :   struct _Default_ranged_hash { };
     378                 :            : 
     379                 :            :   // Default value for rehash policy.  Bucket size is (usually) the
     380                 :            :   // smallest prime that keeps the load factor small enough.
     381                 :            :   struct _Prime_rehash_policy
     382                 :            :   {
     383                 :     378422 :     _Prime_rehash_policy(float __z = 1.0)
     384                 :     378422 :     : _M_max_load_factor(__z), _M_growth_factor(2.f), _M_next_resize(0) { }
     385                 :            : 
     386                 :            :     float
     387                 :            :     max_load_factor() const
     388                 :            :     { return _M_max_load_factor; }      
     389                 :            : 
     390                 :            :     // Return a bucket size no smaller than n.
     391                 :            :     std::size_t
     392                 :            :     _M_next_bkt(std::size_t __n) const;
     393                 :            :     
     394                 :            :     // Return a bucket count appropriate for n elements
     395                 :            :     std::size_t
     396                 :            :     _M_bkt_for_elements(std::size_t __n) const;
     397                 :            :     
     398                 :            :     // __n_bkt is current bucket count, __n_elt is current element count,
     399                 :            :     // and __n_ins is number of elements to be inserted.  Do we need to
     400                 :            :     // increase bucket count?  If so, return make_pair(true, n), where n
     401                 :            :     // is the new bucket count.  If not, return make_pair(false, 0).
     402                 :            :     std::pair<bool, std::size_t>
     403                 :            :     _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
     404                 :            :                    std::size_t __n_ins) const;
     405                 :            : 
     406                 :            :     enum { _S_n_primes = sizeof(unsigned long) != 8 ? 256 : 256 + 48 };
     407                 :            : 
     408                 :            :     float                _M_max_load_factor;
     409                 :            :     float                _M_growth_factor;
     410                 :            :     mutable std::size_t  _M_next_resize;
     411                 :            :   };
     412                 :            : 
     413                 :            :   extern const unsigned long __prime_list[];
     414                 :            : 
     415                 :            :   // XXX This is a hack.  There's no good reason for any of
     416                 :            :   // _Prime_rehash_policy's member functions to be inline.  
     417                 :            : 
     418                 :            :   // Return a prime no smaller than n.
     419                 :            :   inline std::size_t
     420                 :     378422 :   _Prime_rehash_policy::
     421                 :            :   _M_next_bkt(std::size_t __n) const
     422                 :            :   {
     423                 :            :     const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
     424                 :     378422 :                                                 + _S_n_primes, __n);
     425                 :            :     _M_next_resize = 
     426                 :     378422 :       static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
     427                 :     378422 :     return *__p;
     428                 :            :   }
     429                 :            : 
     430                 :            :   // Return the smallest prime p such that alpha p >= n, where alpha
     431                 :            :   // is the load factor.
     432                 :            :   inline std::size_t
     433                 :            :   _Prime_rehash_policy::
     434                 :            :   _M_bkt_for_elements(std::size_t __n) const
     435                 :            :   {
     436                 :            :     const float __min_bkts = __n / _M_max_load_factor;
     437                 :            :     const unsigned long* __p = std::lower_bound(__prime_list, __prime_list
     438                 :            :                                                 + _S_n_primes, __min_bkts);
     439                 :            :     _M_next_resize =
     440                 :            :       static_cast<std::size_t>(__builtin_ceil(*__p * _M_max_load_factor));
     441                 :            :     return *__p;
     442                 :            :   }
     443                 :            : 
     444                 :            :   // Finds the smallest prime p such that alpha p > __n_elt + __n_ins.
     445                 :            :   // If p > __n_bkt, return make_pair(true, p); otherwise return
     446                 :            :   // make_pair(false, 0).  In principle this isn't very different from 
     447                 :            :   // _M_bkt_for_elements.
     448                 :            : 
     449                 :            :   // The only tricky part is that we're caching the element count at
     450                 :            :   // which we need to rehash, so we don't have to do a floating-point
     451                 :            :   // multiply for every insertion.
     452                 :            : 
     453                 :            :   inline std::pair<bool, std::size_t>
     454                 :  123670235 :   _Prime_rehash_policy::
     455                 :            :   _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
     456                 :            :                  std::size_t __n_ins) const
     457                 :            :   {
     458         [ +  + ]:  123670235 :     if (__n_elt + __n_ins > _M_next_resize)
     459                 :            :       {
     460                 :            :         float __min_bkts = ((float(__n_ins) + float(__n_elt))
     461                 :    1425066 :                             / _M_max_load_factor);
     462         [ +  - ]:    1425066 :         if (__min_bkts > __n_bkt)
     463                 :            :           {
     464                 :    1425066 :             __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt);
     465                 :            :             const unsigned long* __p =
     466                 :            :               std::lower_bound(__prime_list, __prime_list + _S_n_primes,
     467         [ +  - ]:    1425066 :                                __min_bkts);
     468                 :            :             _M_next_resize = static_cast<std::size_t>
     469                 :    1425066 :               (__builtin_ceil(*__p * _M_max_load_factor));
     470         [ +  - ]:    1425066 :             return std::make_pair(true, *__p);
     471                 :            :           }
     472                 :            :         else 
     473                 :            :           {
     474                 :            :             _M_next_resize = static_cast<std::size_t>
     475                 :          0 :               (__builtin_ceil(__n_bkt * _M_max_load_factor));
     476         [ #  # ]:    1425066 :             return std::make_pair(false, 0);
     477                 :            :           }
     478                 :            :       }
     479                 :            :     else
     480                 :  123670235 :       return std::make_pair(false, 0);
     481                 :            :   }
     482                 :            : 
     483                 :            :   // Base classes for std::tr1::_Hashtable.  We define these base
     484                 :            :   // classes because in some cases we want to do different things
     485                 :            :   // depending on the value of a policy class.  In some cases the
     486                 :            :   // policy class affects which member functions and nested typedefs
     487                 :            :   // are defined; we handle that by specializing base class templates.
     488                 :            :   // Several of the base class templates need to access other members
     489                 :            :   // of class template _Hashtable, so we use the "curiously recurring
     490                 :            :   // template pattern" for them.
     491                 :            : 
     492                 :            :   // class template _Map_base.  If the hashtable has a value type of the
     493                 :            :   // form pair<T1, T2> and a key extraction policy that returns the
     494                 :            :   // first part of the pair, the hashtable gets a mapped_type typedef.
     495                 :            :   // If it satisfies those criteria and also has unique keys, then it
     496                 :            :   // also gets an operator[].  
     497                 :            :   template<typename _Key, typename _Value, typename _Ex, bool __unique,
     498                 :            :            typename _Hashtable>
     499                 :            :     struct _Map_base { };
     500                 :            :           
     501                 :            :   template<typename _Key, typename _Pair, typename _Hashtable>
     502                 :            :     struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, false, _Hashtable>
     503                 :            :     {
     504                 :            :       typedef typename _Pair::second_type mapped_type;
     505                 :            :     };
     506                 :            : 
     507                 :            :   template<typename _Key, typename _Pair, typename _Hashtable>
     508                 :            :     struct _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>
     509                 :            :     {
     510                 :            :       typedef typename _Pair::second_type mapped_type;
     511                 :            :       
     512                 :            :       mapped_type&
     513                 :            :       operator[](const _Key& __k);
     514                 :            :     };
     515                 :            : 
     516                 :            :   template<typename _Key, typename _Pair, typename _Hashtable>
     517                 :            :     typename _Map_base<_Key, _Pair, std::_Select1st<_Pair>,
     518                 :            :                        true, _Hashtable>::mapped_type&
     519                 :   94657319 :     _Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::
     520                 :            :     operator[](const _Key& __k)
     521                 :            :     {
     522                 :   94657319 :       _Hashtable* __h = static_cast<_Hashtable*>(this);
     523                 :   94657319 :       typename _Hashtable::_Hash_code_type __code = __h->_M_hash_code(__k);
     524                 :            :       std::size_t __n = __h->_M_bucket_index(__k, __code,
     525                 :   94657319 :                                              __h->_M_bucket_count);
     526                 :            : 
     527                 :            :       typename _Hashtable::_Node* __p =
     528                 :   94657319 :         __h->_M_find_node(__h->_M_buckets[__n], __k, __code);
     529   [ +  +  +  +  :   94657319 :       if (!__p)
          +  +  +  +  +  
             +  +  +  +  
                      + ]
     530                 :            :         return __h->_M_insert_bucket(std::make_pair(__k, mapped_type()),
     531 [ +  - ][ +  - ]:   80966379 :                                      __n, __code)->second;
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
         [ +  - ][ +  - ]
     532                 :   94657319 :       return (__p->_M_v).second;
     533                 :            :     }
     534                 :            : 
     535                 :            :   // class template _Rehash_base.  Give hashtable the max_load_factor
     536                 :            :   // functions iff the rehash policy is _Prime_rehash_policy.
     537                 :            :   template<typename _RehashPolicy, typename _Hashtable>
     538                 :            :     struct _Rehash_base { };
     539                 :            : 
     540                 :            :   template<typename _Hashtable>
     541                 :            :     struct _Rehash_base<_Prime_rehash_policy, _Hashtable>
     542                 :            :     {
     543                 :            :       float
     544                 :            :       max_load_factor() const
     545                 :            :       {
     546                 :            :         const _Hashtable* __this = static_cast<const _Hashtable*>(this);
     547                 :            :         return __this->__rehash_policy().max_load_factor();
     548                 :            :       }
     549                 :            : 
     550                 :            :       void
     551                 :            :       max_load_factor(float __z)
     552                 :            :       {
     553                 :            :         _Hashtable* __this = static_cast<_Hashtable*>(this);
     554                 :            :         __this->__rehash_policy(_Prime_rehash_policy(__z));
     555                 :            :       }
     556                 :            :     };
     557                 :            : 
     558                 :            :   // Class template _Hash_code_base.  Encapsulates two policy issues that
     559                 :            :   // aren't quite orthogonal.
     560                 :            :   //   (1) the difference between using a ranged hash function and using
     561                 :            :   //       the combination of a hash function and a range-hashing function.
     562                 :            :   //       In the former case we don't have such things as hash codes, so
     563                 :            :   //       we have a dummy type as placeholder.
     564                 :            :   //   (2) Whether or not we cache hash codes.  Caching hash codes is
     565                 :            :   //       meaningless if we have a ranged hash function.
     566                 :            :   // We also put the key extraction and equality comparison function 
     567                 :            :   // objects here, for convenience.
     568                 :            :   
     569                 :            :   // Primary template: unused except as a hook for specializations.  
     570                 :            :   template<typename _Key, typename _Value,
     571                 :            :            typename _ExtractKey, typename _Equal,
     572                 :            :            typename _H1, typename _H2, typename _Hash,
     573                 :            :            bool __cache_hash_code>
     574                 :            :     struct _Hash_code_base;
     575                 :            : 
     576                 :            :   // Specialization: ranged hash function, no caching hash codes.  H1
     577                 :            :   // and H2 are provided but ignored.  We define a dummy hash code type.
     578                 :            :   template<typename _Key, typename _Value,
     579                 :            :            typename _ExtractKey, typename _Equal,
     580                 :            :            typename _H1, typename _H2, typename _Hash>
     581                 :            :     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
     582                 :            :                            _Hash, false>
     583                 :            :     {
     584                 :            :     protected:
     585                 :            :       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
     586                 :            :                       const _H1&, const _H2&, const _Hash& __h)
     587                 :            :       : _M_extract(__ex), _M_eq(__eq), _M_ranged_hash(__h) { }
     588                 :            : 
     589                 :            :       typedef void* _Hash_code_type;
     590                 :            :   
     591                 :            :       _Hash_code_type
     592                 :            :       _M_hash_code(const _Key& __key) const
     593                 :            :       { return 0; }
     594                 :            :   
     595                 :            :       std::size_t
     596                 :            :       _M_bucket_index(const _Key& __k, _Hash_code_type,
     597                 :            :                       std::size_t __n) const
     598                 :            :       { return _M_ranged_hash(__k, __n); }
     599                 :            : 
     600                 :            :       std::size_t
     601                 :            :       _M_bucket_index(const _Hash_node<_Value, false>* __p,
     602                 :            :                       std::size_t __n) const
     603                 :            :       { return _M_ranged_hash(_M_extract(__p->_M_v), __n); }
     604                 :            :   
     605                 :            :       bool
     606                 :            :       _M_compare(const _Key& __k, _Hash_code_type,
     607                 :            :                  _Hash_node<_Value, false>* __n) const
     608                 :            :       { return _M_eq(__k, _M_extract(__n->_M_v)); }
     609                 :            : 
     610                 :            :       void
     611                 :            :       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
     612                 :            :       { }
     613                 :            : 
     614                 :            :       void
     615                 :            :       _M_copy_code(_Hash_node<_Value, false>*,
     616                 :            :                    const _Hash_node<_Value, false>*) const
     617                 :            :       { }
     618                 :            :       
     619                 :            :       void
     620                 :            :       _M_swap(_Hash_code_base& __x)
     621                 :            :       {
     622                 :            :         std::swap(_M_extract, __x._M_extract);
     623                 :            :         std::swap(_M_eq, __x._M_eq);
     624                 :            :         std::swap(_M_ranged_hash, __x._M_ranged_hash);
     625                 :            :       }
     626                 :            : 
     627                 :            :     protected:
     628                 :            :       _ExtractKey  _M_extract;
     629                 :            :       _Equal       _M_eq;
     630                 :            :       _Hash        _M_ranged_hash;
     631                 :            :     };
     632                 :            : 
     633                 :            : 
     634                 :            :   // No specialization for ranged hash function while caching hash codes.
     635                 :            :   // That combination is meaningless, and trying to do it is an error.
     636                 :            :   
     637                 :            :   
     638                 :            :   // Specialization: ranged hash function, cache hash codes.  This
     639                 :            :   // combination is meaningless, so we provide only a declaration
     640                 :            :   // and no definition.  
     641                 :            :   template<typename _Key, typename _Value,
     642                 :            :            typename _ExtractKey, typename _Equal,
     643                 :            :            typename _H1, typename _H2, typename _Hash>
     644                 :            :     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
     645                 :            :                            _Hash, true>;
     646                 :            : 
     647                 :            :   // Specialization: hash function and range-hashing function, no
     648                 :            :   // caching of hash codes.  H is provided but ignored.  Provides
     649                 :            :   // typedef and accessor required by TR1.  
     650                 :            :   template<typename _Key, typename _Value,
     651                 :            :            typename _ExtractKey, typename _Equal,
     652                 :            :            typename _H1, typename _H2>
     653                 :            :     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
     654                 :            :                            _Default_ranged_hash, false>
     655                 :            :     {
     656                 :            :       typedef _H1 hasher;
     657                 :            : 
     658                 :            :       hasher
     659                 :            :       hash_function() const
     660                 :            :       { return _M_h1; }
     661                 :            : 
     662                 :            :     protected:
     663                 :     378422 :       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
     664                 :            :                       const _H1& __h1, const _H2& __h2,
     665                 :            :                       const _Default_ranged_hash&)
     666                 :     378422 :       : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
     667                 :            : 
     668                 :            :       typedef std::size_t _Hash_code_type;
     669                 :            : 
     670                 :            :       _Hash_code_type
     671                 :  226817659 :       _M_hash_code(const _Key& __k) const
     672 [ #  # ][ +  - ]:  226817659 :       { return _M_h1(__k); }
     673                 :            :       
     674                 :            :       std::size_t
     675                 :  228139180 :       _M_bucket_index(const _Key&, _Hash_code_type __c,
     676                 :            :                       std::size_t __n) const
     677                 :  228139180 :       { return _M_h2(__c, __n); }
     678                 :            : 
     679                 :            :       std::size_t
     680                 :  164234509 :       _M_bucket_index(const _Hash_node<_Value, false>* __p,
     681                 :            :                       std::size_t __n) const
     682 [ #  # ][ +  - ]:  164234509 :       { return _M_h2(_M_h1(_M_extract(__p->_M_v)), __n); }
     683                 :            : 
     684                 :            :       bool
     685                 :  182296240 :       _M_compare(const _Key& __k, _Hash_code_type,
     686                 :            :                  _Hash_node<_Value, false>* __n) const
     687                 :  182296240 :       { return _M_eq(__k, _M_extract(__n->_M_v)); }
     688                 :            : 
     689                 :            :       void
     690                 :  123628938 :       _M_store_code(_Hash_node<_Value, false>*, _Hash_code_type) const
     691                 :  123628938 :       { }
     692                 :            : 
     693                 :            :       void
     694                 :            :       _M_copy_code(_Hash_node<_Value, false>*,
     695                 :            :                    const _Hash_node<_Value, false>*) const
     696                 :            :       { }
     697                 :            : 
     698                 :            :       void
     699                 :            :       _M_swap(_Hash_code_base& __x)
     700                 :            :       {
     701                 :            :         std::swap(_M_extract, __x._M_extract);
     702                 :            :         std::swap(_M_eq, __x._M_eq);
     703                 :            :         std::swap(_M_h1, __x._M_h1);
     704                 :            :         std::swap(_M_h2, __x._M_h2);
     705                 :            :       }
     706                 :            : 
     707                 :            :     protected:
     708                 :            :       _ExtractKey  _M_extract;
     709                 :            :       _Equal       _M_eq;
     710                 :            :       _H1          _M_h1;
     711                 :            :       _H2          _M_h2;
     712                 :            :     };
     713                 :            : 
     714                 :            :   // Specialization: hash function and range-hashing function, 
     715                 :            :   // caching hash codes.  H is provided but ignored.  Provides
     716                 :            :   // typedef and accessor required by TR1.
     717                 :            :   template<typename _Key, typename _Value,
     718                 :            :            typename _ExtractKey, typename _Equal,
     719                 :            :            typename _H1, typename _H2>
     720                 :            :     struct _Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2,
     721                 :            :                            _Default_ranged_hash, true>
     722                 :            :     {
     723                 :            :       typedef _H1 hasher;
     724                 :            :       
     725                 :            :       hasher
     726                 :            :       hash_function() const
     727                 :            :       { return _M_h1; }
     728                 :            : 
     729                 :            :     protected:
     730                 :            :       _Hash_code_base(const _ExtractKey& __ex, const _Equal& __eq,
     731                 :            :                       const _H1& __h1, const _H2& __h2,
     732                 :            :                       const _Default_ranged_hash&)
     733                 :            :       : _M_extract(__ex), _M_eq(__eq), _M_h1(__h1), _M_h2(__h2) { }
     734                 :            : 
     735                 :            :       typedef std::size_t _Hash_code_type;
     736                 :            :   
     737                 :            :       _Hash_code_type
     738                 :            :       _M_hash_code(const _Key& __k) const
     739                 :            :       { return _M_h1(__k); }
     740                 :            :   
     741                 :            :       std::size_t
     742                 :            :       _M_bucket_index(const _Key&, _Hash_code_type __c,
     743                 :            :                       std::size_t __n) const
     744                 :            :       { return _M_h2(__c, __n); }
     745                 :            : 
     746                 :            :       std::size_t
     747                 :            :       _M_bucket_index(const _Hash_node<_Value, true>* __p,
     748                 :            :                       std::size_t __n) const
     749                 :            :       { return _M_h2(__p->_M_hash_code, __n); }
     750                 :            : 
     751                 :            :       bool
     752                 :            :       _M_compare(const _Key& __k, _Hash_code_type __c,
     753                 :            :                  _Hash_node<_Value, true>* __n) const
     754                 :            :       { return __c == __n->_M_hash_code && _M_eq(__k, _M_extract(__n->_M_v)); }
     755                 :            : 
     756                 :            :       void
     757                 :            :       _M_store_code(_Hash_node<_Value, true>* __n, _Hash_code_type __c) const
     758                 :            :       { __n->_M_hash_code = __c; }
     759                 :            : 
     760                 :            :       void
     761                 :            :       _M_copy_code(_Hash_node<_Value, true>* __to,
     762                 :            :                    const _Hash_node<_Value, true>* __from) const
     763                 :            :       { __to->_M_hash_code = __from->_M_hash_code; }
     764                 :            : 
     765                 :            :       void
     766                 :            :       _M_swap(_Hash_code_base& __x)
     767                 :            :       {
     768                 :            :         std::swap(_M_extract, __x._M_extract);
     769                 :            :         std::swap(_M_eq, __x._M_eq);
     770                 :            :         std::swap(_M_h1, __x._M_h1);
     771                 :            :         std::swap(_M_h2, __x._M_h2);
     772                 :            :       }
     773                 :            :       
     774                 :            :     protected:
     775                 :            :       _ExtractKey  _M_extract;
     776                 :            :       _Equal       _M_eq;
     777                 :            :       _H1          _M_h1;
     778                 :            :       _H2          _M_h2;
     779                 :            :     };
     780                 :            : _GLIBCXX_END_NAMESPACE_VERSION
     781                 :            : } // namespace __detail
     782                 :            : }
     783                 :            : }

Generated by: LCOV version 1.9