LCOV - code coverage report
Current view: top level - gcc - hash-traits.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 45 51 88.2 %
Date: 2020-04-04 11:58:09 Functions: 2 3 66.7 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Traits for hashable types.
       2                 :            :    Copyright (C) 2014-2020 Free Software Foundation, Inc.
       3                 :            : 
       4                 :            : This file is part of GCC.
       5                 :            : 
       6                 :            : GCC is free software; you can redistribute it and/or modify it under
       7                 :            : the terms of the GNU General Public License as published by the Free
       8                 :            : Software Foundation; either version 3, or (at your option) any later
       9                 :            : version.
      10                 :            : 
      11                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      12                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :            : for more details.
      15                 :            : 
      16                 :            : You should have received a copy of the GNU General Public License
      17                 :            : along with GCC; see the file COPYING3.  If not see
      18                 :            : <http://www.gnu.org/licenses/>.  */
      19                 :            : 
      20                 :            : #ifndef hash_traits_h
      21                 :            : #define hash_traits_h
      22                 :            : 
      23                 :            : /* Helpful type for removing with free.  */
      24                 :            : 
      25                 :            : template <typename Type>
      26                 :            : struct typed_free_remove
      27                 :            : {
      28                 :            :   static inline void remove (Type *p);
      29                 :            : };
      30                 :            : 
      31                 :            : 
      32                 :            : /* Remove with free.  */
      33                 :            : 
      34                 :            : template <typename Type>
      35                 :            : inline void
      36                 :   72651110 : typed_free_remove <Type>::remove (Type *p)
      37                 :            : {
      38                 :   61532660 :   free (p);
      39                 :   70009210 : }
      40                 :            : 
      41                 :            : /* Helpful type for removing with delete.  */
      42                 :            : 
      43                 :            : template <typename Type>
      44                 :            : struct typed_delete_remove
      45                 :            : {
      46                 :            :   static inline void remove (Type *p);
      47                 :            : };
      48                 :            : 
      49                 :            : 
      50                 :            : /* Remove with delete.  */
      51                 :            : 
      52                 :            : template <typename Type>
      53                 :            : inline void
      54                 :    4289198 : typed_delete_remove <Type>::remove (Type *p)
      55                 :            : {
      56                 :    5956428 :   delete p;
      57                 :    1668008 : }
      58                 :            : 
      59                 :            : /* Helpful type for a no-op remove.  */
      60                 :            : 
      61                 :            : template <typename Type>
      62                 :            : struct typed_noop_remove
      63                 :            : {
      64                 :            :   static inline void remove (Type &);
      65                 :            : };
      66                 :            : 
      67                 :            : 
      68                 :            : /* Remove doing nothing.  */
      69                 :            : 
      70                 :            : template <typename Type>
      71                 :            : inline void
      72                 :   69810382 : typed_noop_remove <Type>::remove (Type &)
      73                 :            : {
      74                 :            : }
      75                 :            : 
      76                 :            : 
      77                 :            : /* Hasher for integer type Type in which Empty is a spare value that can be
      78                 :            :    used to mark empty slots.  If Deleted != Empty then Deleted is another
      79                 :            :    spare value that can be used for deleted slots; if Deleted == Empty then
      80                 :            :    hash table entries cannot be deleted.  */
      81                 :            : 
      82                 :            : template <typename Type, Type Empty, Type Deleted = Empty>
      83                 :            : struct int_hash : typed_noop_remove <Type>
      84                 :            : {
      85                 :            :   typedef Type value_type;
      86                 :            :   typedef Type compare_type;
      87                 :            : 
      88                 :            :   static inline hashval_t hash (value_type);
      89                 :            :   static inline bool equal (value_type existing, value_type candidate);
      90                 :            :   static inline void mark_deleted (Type &);
      91                 :            :   static const bool empty_zero_p = Empty == 0;
      92                 :            :   static inline void mark_empty (Type &);
      93                 :            :   static inline bool is_deleted (Type);
      94                 :            :   static inline bool is_empty (Type);
      95                 :            : };
      96                 :            : 
      97                 :            : template <typename Type, Type Empty, Type Deleted>
      98                 :            : inline hashval_t
      99                 : 2064024109 : int_hash <Type, Empty, Deleted>::hash (value_type x)
     100                 :            : {
     101                 : 2047402983 :   return x;
     102                 :            : }
     103                 :            : 
     104                 :            : template <typename Type, Type Empty, Type Deleted>
     105                 :            : inline bool
     106                 : 1342879633 : int_hash <Type, Empty, Deleted>::equal (value_type x, value_type y)
     107                 :            : {
     108                 :            :   return x == y;
     109                 :            : }
     110                 :            : 
     111                 :            : template <typename Type, Type Empty, Type Deleted>
     112                 :            : inline void
     113                 :    1221642 : int_hash <Type, Empty, Deleted>::mark_deleted (Type &x)
     114                 :            : {
     115                 :            :   gcc_assert (Empty != Deleted);
     116                 :    1221642 :   x = Deleted;
     117                 :            : }
     118                 :            : 
     119                 :            : template <typename Type, Type Empty, Type Deleted>
     120                 :            : inline void
     121                 : 1260264155 : int_hash <Type, Empty, Deleted>::mark_empty (Type &x)
     122                 :            : {
     123                 : 1260264155 :   x = Empty;
     124                 :            : }
     125                 :            : 
     126                 :            : template <typename Type, Type Empty, Type Deleted>
     127                 :            : inline bool
     128                 : 2120534589 : int_hash <Type, Empty, Deleted>::is_deleted (Type x)
     129                 :            : {
     130                 :            :   return Empty != Deleted && x == Deleted;
     131                 :            : }
     132                 :            : 
     133                 :            : template <typename Type, Type Empty, Type Deleted>
     134                 :            : inline bool
     135                 : 6159005379 : int_hash <Type, Empty, Deleted>::is_empty (Type x)
     136                 :            : {
     137                 :            :   return x == Empty;
     138                 :            : }
     139                 :            : 
     140                 :            : /* Pointer hasher based on pointer equality.  Other types of pointer hash
     141                 :            :    can inherit this and override the hash and equal functions with some
     142                 :            :    other form of equality (such as string equality).  */
     143                 :            : 
     144                 :            : template <typename Type>
     145                 :            : struct pointer_hash
     146                 :            : {
     147                 :            :   typedef Type *value_type;
     148                 :            :   typedef Type *compare_type;
     149                 :            : 
     150                 :            :   static inline hashval_t hash (const value_type &);
     151                 :            :   static inline bool equal (const value_type &existing,
     152                 :            :                             const compare_type &candidate);
     153                 :            :   static inline void mark_deleted (Type *&);
     154                 :            :   static const bool empty_zero_p = true;
     155                 :            :   static inline void mark_empty (Type *&);
     156                 :            :   static inline bool is_deleted (Type *);
     157                 :            :   static inline bool is_empty (Type *);
     158                 :            : };
     159                 :            : 
     160                 :            : template <typename Type>
     161                 :            : inline hashval_t
     162                 :90057842022 : pointer_hash <Type>::hash (const value_type &candidate)
     163                 :            : {
     164                 :            :   /* This is a really poor hash function, but it is what the current code uses,
     165                 :            :      so I am reusing it to avoid an additional axis in testing.  */
     166                 :90054217960 :   return (hashval_t) ((intptr_t)candidate >> 3);
     167                 :            : }
     168                 :            : 
     169                 :            : template <typename Type>
     170                 :            : inline bool
     171                 :81716949894 : pointer_hash <Type>::equal (const value_type &existing,
     172                 :            :                            const compare_type &candidate)
     173                 :            : {
     174                 :            :   return existing == candidate;
     175                 :            : }
     176                 :            : 
     177                 :            : template <typename Type>
     178                 :            : inline void
     179                 :  412485809 : pointer_hash <Type>::mark_deleted (Type *&e)
     180                 :            : {
     181                 :  363641720 :   e = reinterpret_cast<Type *> (1);
     182                 :            : }
     183                 :            : 
     184                 :            : template <typename Type>
     185                 :            : inline void
     186                 :  147039510 : pointer_hash <Type>::mark_empty (Type *&e)
     187                 :            : {
     188                 :  147039510 :   e = NULL;
     189                 :            : }
     190                 :            : 
     191                 :            : template <typename Type>
     192                 :            : inline bool
     193                 :>14998*10^7 : pointer_hash <Type>::is_deleted (Type *e)
     194                 :            : {
     195                 :            :   return e == reinterpret_cast<Type *> (1);
     196                 :            : }
     197                 :            : 
     198                 :            : template <typename Type>
     199                 :            : inline bool
     200                 :>40892*10^7 : pointer_hash <Type>::is_empty (Type *e)
     201                 :            : {
     202                 :            :   return e == NULL;
     203                 :            : }
     204                 :            : 
     205                 :            : /* Hasher for "const char *" strings, using string rather than pointer
     206                 :            :    equality.  */
     207                 :            : 
     208                 :            : struct string_hash : pointer_hash <const char>
     209                 :            : {
     210                 :            :   static inline hashval_t hash (const char *);
     211                 :            :   static inline bool equal (const char *, const char *);
     212                 :            : };
     213                 :            : 
     214                 :            : inline hashval_t
     215                 :  939351592 : string_hash::hash (const char *id)
     216                 :            : {
     217                 :  939351592 :   return htab_hash_string (id);
     218                 :            : }
     219                 :            : 
     220                 :            : inline bool
     221                 :  872142785 : string_hash::equal (const char *id1, const char *id2)
     222                 :            : {
     223                 :  872142785 :   return strcmp (id1, id2) == 0;
     224                 :            : }
     225                 :            : 
     226                 :            : /* Remover and marker for entries in gc memory.  */
     227                 :            : 
     228                 :            : template<typename T>
     229                 :            : struct ggc_remove
     230                 :            : {
     231                 :   44040167 :   static void remove (T &) {}
     232                 :            : 
     233                 :            :   static void
     234                 :  212484615 :   ggc_mx (T &p)
     235                 :            :   {
     236                 :            :     extern void gt_ggc_mx (T &);
     237                 :  212484615 :     gt_ggc_mx (p);
     238                 :  212484615 :   }
     239                 :            : 
     240                 :            :   /* Overridden in ggc_cache_remove.  */
     241                 :            :   static void
     242                 :            :   ggc_maybe_mx (T &p)
     243                 :            :   {
     244                 :            :     ggc_mx (p);
     245                 :            :   }
     246                 :            : 
     247                 :            :   static void
     248                 :    1097325 :   pch_nx (T &p)
     249                 :            :   {
     250                 :            :     extern void gt_pch_nx (T &);
     251                 :    1097325 :     gt_pch_nx (p);
     252                 :    1097325 :   }
     253                 :            : 
     254                 :            :   static void
     255                 :    1097325 :   pch_nx (T &p, gt_pointer_operator op, void *cookie)
     256                 :            :   {
     257                 :    1097325 :     op (&p, cookie);
     258                 :    1097325 :   }
     259                 :            : };
     260                 :            : 
     261                 :            : /* Remover and marker for "cache" entries in gc memory.  These entries can
     262                 :            :    be deleted if there are no non-cache references to the data.  */
     263                 :            : 
     264                 :            : template<typename T>
     265                 :            : struct ggc_cache_remove : ggc_remove<T>
     266                 :            : {
     267                 :            :   /* Entries are weakly held because this is for caches.  */
     268                 :            :   static void ggc_maybe_mx (T &) {}
     269                 :            : 
     270                 :            :   static int
     271                 :   86942252 :   keep_cache_entry (T &e)
     272                 :            :   {
     273                 :   86942252 :     return ggc_marked_p (e) ? -1 : 0;
     274                 :            :   }
     275                 :            : };
     276                 :            : 
     277                 :            : /* Traits for pointer elements that should not be freed when an element
     278                 :            :    is deleted.  */
     279                 :            : 
     280                 :            : template <typename T>
     281                 :            : struct nofree_ptr_hash : pointer_hash <T>, typed_noop_remove <T *> {};
     282                 :            : 
     283                 :            : /* Traits for pointer elements that should be freed via free() when an
     284                 :            :    element is deleted.  */
     285                 :            : 
     286                 :            : template <typename T>
     287                 :            : struct free_ptr_hash : pointer_hash <T>, typed_free_remove <T> {};
     288                 :            : 
     289                 :            : /* Traits for pointer elements that should be freed via delete operand when an
     290                 :            :    element is deleted.  */
     291                 :            : 
     292                 :            : template <typename T>
     293                 :            : struct delete_ptr_hash : pointer_hash <T>, typed_delete_remove <T> {};
     294                 :            : 
     295                 :            : /* Traits for elements that point to gc memory.  The pointed-to data
     296                 :            :    must be kept across collections.  */
     297                 :            : 
     298                 :            : template <typename T>
     299                 :            : struct ggc_ptr_hash : pointer_hash <T>, ggc_remove <T *> {};
     300                 :            : 
     301                 :            : /* Traits for elements that point to gc memory.  The elements don't
     302                 :            :    in themselves keep the pointed-to data alive and they can be deleted
     303                 :            :    if the pointed-to data is going to be collected.  */
     304                 :            : 
     305                 :            : template <typename T>
     306                 :            : struct ggc_cache_ptr_hash : pointer_hash <T>, ggc_cache_remove <T *> {};
     307                 :            : 
     308                 :            : /* Traits for string elements that should not be freed when an element
     309                 :            :    is deleted.  */
     310                 :            : 
     311                 :            : struct nofree_string_hash : string_hash, typed_noop_remove <const char *> {};
     312                 :            : 
     313                 :            : /* Traits for pairs of values, using the first to record empty and
     314                 :            :    deleted slots.  */
     315                 :            : 
     316                 :            : template <typename T1, typename T2>
     317                 :            : struct pair_hash
     318                 :            : {
     319                 :            :   typedef std::pair <typename T1::value_type,
     320                 :            :                      typename T2::value_type> value_type;
     321                 :            :   typedef std::pair <typename T1::compare_type,
     322                 :            :                      typename T2::compare_type> compare_type;
     323                 :            : 
     324                 :            :   static inline hashval_t hash (const value_type &);
     325                 :            :   static inline bool equal (const value_type &, const compare_type &);
     326                 :            :   static inline void remove (value_type &);
     327                 :            :   static inline void mark_deleted (value_type &);
     328                 :            :   static const bool empty_zero_p = T1::empty_zero_p;
     329                 :            :   static inline void mark_empty (value_type &);
     330                 :            :   static inline bool is_deleted (const value_type &);
     331                 :            :   static inline bool is_empty (const value_type &);
     332                 :            : };
     333                 :            : 
     334                 :            : template <typename T1, typename T2>
     335                 :            : inline hashval_t
     336                 :          4 : pair_hash <T1, T2>::hash (const value_type &x)
     337                 :            : {
     338                 :          4 :   return iterative_hash_hashval_t (T1::hash (x.first), T2::hash (x.second));
     339                 :            : }
     340                 :            : 
     341                 :            : template <typename T1, typename T2>
     342                 :            : inline bool
     343                 :          0 : pair_hash <T1, T2>::equal (const value_type &x, const compare_type &y)
     344                 :            : {
     345                 :          0 :   return T1::equal (x.first, y.first) && T2::equal (x.second, y.second);
     346                 :            : }
     347                 :            : 
     348                 :            : template <typename T1, typename T2>
     349                 :            : inline void
     350                 :            : pair_hash <T1, T2>::remove (value_type &x)
     351                 :            : {
     352                 :            :   T1::remove (x.first);
     353                 :            :   T2::remove (x.second);
     354                 :            : }
     355                 :            : 
     356                 :            : template <typename T1, typename T2>
     357                 :            : inline void
     358                 :            : pair_hash <T1, T2>::mark_deleted (value_type &x)
     359                 :            : {
     360                 :            :   T1::mark_deleted (x.first);
     361                 :            : }
     362                 :            : 
     363                 :            : template <typename T1, typename T2>
     364                 :            : inline void
     365                 :          0 : pair_hash <T1, T2>::mark_empty (value_type &x)
     366                 :            : {
     367                 :          0 :   T1::mark_empty (x.first);
     368                 :            : }
     369                 :            : 
     370                 :            : template <typename T1, typename T2>
     371                 :            : inline bool
     372                 :          0 : pair_hash <T1, T2>::is_deleted (const value_type &x)
     373                 :            : {
     374                 :          0 :   return T1::is_deleted (x.first);
     375                 :            : }
     376                 :            : 
     377                 :            : template <typename T1, typename T2>
     378                 :            : inline bool
     379                 :     441060 : pair_hash <T1, T2>::is_empty (const value_type &x)
     380                 :            : {
     381                 :     441060 :   return T1::is_empty (x.first);
     382                 :            : }
     383                 :            : 
     384                 :            : template <typename T> struct default_hash_traits : T {};
     385                 :            : 
     386                 :            : template <typename T>
     387                 :            : struct default_hash_traits <T *> : ggc_ptr_hash <T> {};
     388                 :            : 
     389                 :            : #endif

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.