LCOV - code coverage report
Current view: top level - gcc - hash-traits.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 97.1 % 68 66
Test Date: 2024-11-30 13:30:02 Functions: 87.5 % 8 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-2024 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                 :             : template <typename Type>
      32                 :             : struct typed_const_free_remove
      33                 :             : {
      34                 :             :   static inline void remove (const Type *p);
      35                 :             : };
      36                 :             : 
      37                 :             : /* Remove with free.  */
      38                 :             : 
      39                 :             : template <typename Type>
      40                 :             : inline void
      41                 :    95003497 : typed_free_remove <Type>::remove (Type *p)
      42                 :             : {
      43                 :    95003497 :   free (p);
      44                 :    95003497 : }
      45                 :             : 
      46                 :             : template <typename Type>
      47                 :             : inline void
      48                 :    89958592 : typed_const_free_remove <Type>::remove (const Type *p)
      49                 :             : {
      50                 :    89958592 :   free (const_cast <Type *> (p));
      51                 :          58 : }
      52                 :             : 
      53                 :             : /* Helpful type for removing with delete.  */
      54                 :             : 
      55                 :             : template <typename Type>
      56                 :             : struct typed_delete_remove
      57                 :             : {
      58                 :             :   static inline void remove (Type *p);
      59                 :             : };
      60                 :             : 
      61                 :             : 
      62                 :             : /* Remove with delete.  */
      63                 :             : 
      64                 :             : template <typename Type>
      65                 :             : inline void
      66                 :     3648980 : typed_delete_remove <Type>::remove (Type *p)
      67                 :             : {
      68                 :    10102568 :   delete p;
      69                 :     3648980 : }
      70                 :             : 
      71                 :             : /* Helpful type for a no-op remove.  */
      72                 :             : 
      73                 :             : template <typename Type>
      74                 :             : struct typed_noop_remove
      75                 :             : {
      76                 :             :   static inline void remove (Type &);
      77                 :             : };
      78                 :             : 
      79                 :             : 
      80                 :             : /* Remove doing nothing.  */
      81                 :             : 
      82                 :             : template <typename Type>
      83                 :             : inline void
      84                 :   163046109 : typed_noop_remove <Type>::remove (Type &)
      85                 :             : {
      86                 :   163046109 : }
      87                 :             : 
      88                 :             : /* Base traits for integer type Type, providing just the hash and
      89                 :             :    comparison functionality.  */
      90                 :             : 
      91                 :             : template <typename Type>
      92                 :             : struct int_hash_base : typed_noop_remove <Type>
      93                 :             : {
      94                 :             :   typedef Type value_type;
      95                 :             :   typedef Type compare_type;
      96                 :             : 
      97                 :             :   static inline hashval_t hash (value_type);
      98                 :             :   static inline bool equal (value_type existing, value_type candidate);
      99                 :             : };
     100                 :             : 
     101                 :             : template <typename Type>
     102                 :             : inline hashval_t
     103                 :  3012967146 : int_hash_base <Type>::hash (value_type x)
     104                 :             : {
     105                 :  3012967146 :   return x;
     106                 :             : }
     107                 :             : 
     108                 :             : template <typename Type>
     109                 :             : inline bool
     110                 :             : int_hash_base <Type>::equal (value_type x, value_type y)
     111                 :             : {
     112                 :             :   return x == y;
     113                 :             : }
     114                 :             : 
     115                 :             : /* Hasher for integer type Type in which Empty is a spare value that can be
     116                 :             :    used to mark empty slots.  If Deleted != Empty then Deleted is another
     117                 :             :    spare value that can be used for deleted slots; if Deleted == Empty then
     118                 :             :    hash table entries cannot be deleted.  */
     119                 :             : 
     120                 :             : template <typename Type, Type Empty, Type Deleted = Empty>
     121                 :             : struct int_hash : int_hash_base <Type>
     122                 :             : {
     123                 :             :   typedef Type value_type;
     124                 :             :   typedef Type compare_type;
     125                 :             : 
     126                 :             :   static inline void mark_deleted (Type &);
     127                 :             :   static const bool empty_zero_p = Empty == 0;
     128                 :             :   static inline void mark_empty (Type &);
     129                 :             :   static inline bool is_deleted (Type);
     130                 :             :   static inline bool is_empty (Type);
     131                 :             : };
     132                 :             : 
     133                 :             : template <typename Type, Type Empty, Type Deleted>
     134                 :             : inline void
     135                 :     4596742 : int_hash <Type, Empty, Deleted>::mark_deleted (Type &x)
     136                 :             : {
     137                 :             :   gcc_assert (Empty != Deleted);
     138                 :     4596742 :   x = Deleted;
     139                 :             : }
     140                 :             : 
     141                 :             : template <typename Type, Type Empty, Type Deleted>
     142                 :             : inline void
     143                 :  1615475943 : int_hash <Type, Empty, Deleted>::mark_empty (Type &x)
     144                 :             : {
     145                 :  1615475943 :   x = Empty;
     146                 :             : }
     147                 :             : 
     148                 :             : template <typename Type, Type Empty, Type Deleted>
     149                 :             : inline bool
     150                 : 11612387246 : int_hash <Type, Empty, Deleted>::is_deleted (Type x)
     151                 :             : {
     152                 : 11612387246 :   return Empty != Deleted && x == Deleted;
     153                 :             : }
     154                 :             : 
     155                 :             : template <typename Type, Type Empty, Type Deleted>
     156                 :             : inline bool
     157                 :             : int_hash <Type, Empty, Deleted>::is_empty (Type x)
     158                 :             : {
     159                 :             :   return x == Empty;
     160                 :             : }
     161                 :             : 
     162                 :             : /* Pointer hasher based on pointer equality.  Other types of pointer hash
     163                 :             :    can inherit this and override the hash and equal functions with some
     164                 :             :    other form of equality (such as string equality).  */
     165                 :             : 
     166                 :             : template <typename Type>
     167                 :             : struct pointer_hash
     168                 :             : {
     169                 :             :   typedef Type *value_type;
     170                 :             :   typedef Type *compare_type;
     171                 :             : 
     172                 :             :   static inline hashval_t hash (const value_type &);
     173                 :             :   static inline bool equal (const value_type &existing,
     174                 :             :                             const compare_type &candidate);
     175                 :             :   static inline void mark_deleted (Type *&);
     176                 :             :   static const bool empty_zero_p = true;
     177                 :             :   static inline void mark_empty (Type *&);
     178                 :             :   static inline bool is_deleted (Type *);
     179                 :             :   static inline bool is_empty (Type *);
     180                 :             : };
     181                 :             : 
     182                 :             : template <typename Type>
     183                 :             : inline hashval_t
     184                 : >30031*10^7 : pointer_hash <Type>::hash (const value_type &candidate)
     185                 :             : {
     186                 :             :   /* This is a really poor hash function, but it is what the current code uses,
     187                 :             :      so I am reusing it to avoid an additional axis in testing.  */
     188                 : >30031*10^7 :   return (hashval_t) ((intptr_t)candidate >> 3);
     189                 :             : }
     190                 :             : 
     191                 :             : template <typename Type>
     192                 :             : inline bool
     193                 : >26937*10^7 : pointer_hash <Type>::equal (const value_type &existing,
     194                 :             :                            const compare_type &candidate)
     195                 :             : {
     196                 : >26937*10^7 :   return existing == candidate;
     197                 :             : }
     198                 :             : 
     199                 :             : template <typename Type>
     200                 :             : inline void
     201                 :   652077535 : pointer_hash <Type>::mark_deleted (Type *&e)
     202                 :             : {
     203                 :   541255101 :   e = reinterpret_cast<Type *> (1);
     204                 :             : }
     205                 :             : 
     206                 :             : template <typename Type>
     207                 :             : inline void
     208                 :   253892779 : pointer_hash <Type>::mark_empty (Type *&e)
     209                 :             : {
     210                 :   253892779 :   e = NULL;
     211                 :             : }
     212                 :             : 
     213                 :             : template <typename Type>
     214                 :             : inline bool
     215                 : >47018*10^7 : pointer_hash <Type>::is_deleted (Type *e)
     216                 :             : {
     217                 : >47018*10^7 :   return e == reinterpret_cast<Type *> (1);
     218                 :             : }
     219                 :             : 
     220                 :             : template <typename Type>
     221                 :             : inline bool
     222                 :             : pointer_hash <Type>::is_empty (Type *e)
     223                 :             : {
     224                 :             :   return e == NULL;
     225                 :             : }
     226                 :             : 
     227                 :             : /* Hasher for "const char *" strings, using string rather than pointer
     228                 :             :    equality.  */
     229                 :             : 
     230                 :             : struct string_hash : pointer_hash <const char>
     231                 :             : {
     232                 :             :   static inline hashval_t hash (const char *);
     233                 :             :   static inline bool equal (const char *, const char *);
     234                 :             : };
     235                 :             : 
     236                 :             : inline hashval_t
     237                 : 10258488872 : string_hash::hash (const char *id)
     238                 :             : {
     239                 : 10258488872 :   return htab_hash_string (id);
     240                 :             : }
     241                 :             : 
     242                 :             : inline bool
     243                 :  7736390295 : string_hash::equal (const char *id1, const char *id2)
     244                 :             : {
     245                 :  7736390295 :   return strcmp (id1, id2) == 0;
     246                 :             : }
     247                 :             : 
     248                 :             : /* Remover and marker for entries in gc memory.  */
     249                 :             : 
     250                 :             : template<typename T>
     251                 :             : struct ggc_remove
     252                 :             : {
     253                 :        1326 :   static void remove (T &) {}
     254                 :             : 
     255                 :             :   static void
     256                 :  4132614902 :   ggc_mx (T &p)
     257                 :             :   {
     258                 :             :     extern void gt_ggc_mx (T &);
     259                 :  3443068808 :     gt_ggc_mx (p);
     260                 :  1574150557 :   }
     261                 :             : 
     262                 :             :   /* Overridden in ggc_cache_remove.  */
     263                 :             :   static void
     264                 :  2558464345 :   ggc_maybe_mx (T &p)
     265                 :             :   {
     266                 :  2558464345 :     ggc_mx (p);
     267                 :  2558464345 :   }
     268                 :             : 
     269                 :             :   static void
     270                 :     1533437 :   pch_nx (T &p)
     271                 :             :   {
     272                 :             :     extern void gt_pch_nx (T &);
     273                 :     1533437 :     gt_pch_nx (p);
     274                 :     1533437 :   }
     275                 :             : 
     276                 :             :   static void
     277                 :     1533437 :   pch_nx (T &p, gt_pointer_operator op, void *cookie)
     278                 :             :   {
     279                 :     1533437 :     op (&p, NULL, cookie);
     280                 :     1533437 :   }
     281                 :             : };
     282                 :             : 
     283                 :             : /* Remover and marker for "cache" entries in gc memory.  These entries can
     284                 :             :    be deleted if there are no non-cache references to the data.  */
     285                 :             : 
     286                 :             : template<typename T>
     287                 :             : struct ggc_cache_remove : ggc_remove<T>
     288                 :             : {
     289                 :             :   /* Entries are weakly held because this is for caches.  */
     290                 :             :   static void ggc_maybe_mx (T &) {}
     291                 :             : 
     292                 :             :   static int
     293                 :   255097172 :   keep_cache_entry (T &e)
     294                 :             :   {
     295                 :   255097172 :     return ggc_marked_p (e) ? -1 : 0;
     296                 :             :   }
     297                 :             : };
     298                 :             : 
     299                 :             : /* Traits for pointer elements that should not be freed when an element
     300                 :             :    is deleted.  */
     301                 :             : 
     302                 :             : template <typename T>
     303                 :             : struct nofree_ptr_hash : pointer_hash <T>, typed_noop_remove <T *> {};
     304                 :             : 
     305                 :             : /* Traits for pointer elements that should be freed via free() when an
     306                 :             :    element is deleted.  */
     307                 :             : 
     308                 :             : template <typename T>
     309                 :             : struct free_ptr_hash : pointer_hash <T>, typed_free_remove <T> {};
     310                 :             : 
     311                 :             : /* Traits for pointer elements that should be freed via delete operand when an
     312                 :             :    element is deleted.  */
     313                 :             : 
     314                 :             : template <typename T>
     315                 :             : struct delete_ptr_hash : pointer_hash <T>, typed_delete_remove <T> {};
     316                 :             : 
     317                 :             : /* Traits for elements that point to gc memory.  The pointed-to data
     318                 :             :    must be kept across collections.  */
     319                 :             : 
     320                 :             : template <typename T>
     321                 :             : struct ggc_ptr_hash : pointer_hash <T>, ggc_remove <T *> {};
     322                 :             : 
     323                 :             : /* Traits for elements that point to gc memory.  The elements don't
     324                 :             :    in themselves keep the pointed-to data alive and they can be deleted
     325                 :             :    if the pointed-to data is going to be collected.  */
     326                 :             : 
     327                 :             : template <typename T>
     328                 :             : struct ggc_cache_ptr_hash : pointer_hash <T>, ggc_cache_remove <T *> {};
     329                 :             : 
     330                 :             : /* Traits for string elements that should be freed when an element is
     331                 :             :    deleted.  */
     332                 :             : 
     333                 :             : struct free_string_hash : string_hash, typed_const_free_remove <char> {};
     334                 :             : 
     335                 :             : /* Traits for string elements that should not be freed when an element
     336                 :             :    is deleted.  */
     337                 :             : 
     338                 :             : struct nofree_string_hash : string_hash, typed_noop_remove <const char *> {};
     339                 :             : 
     340                 :             : /* Traits for pairs of values, using the first to record empty and
     341                 :             :    deleted slots.  */
     342                 :             : 
     343                 :             : template <typename T1, typename T2>
     344                 :             : struct pair_hash
     345                 :             : {
     346                 :             :   typedef std::pair <typename T1::value_type,
     347                 :             :                      typename T2::value_type> value_type;
     348                 :             :   typedef std::pair <typename T1::compare_type,
     349                 :             :                      typename T2::compare_type> compare_type;
     350                 :             : 
     351                 :             :   static inline hashval_t hash (const value_type &);
     352                 :             :   static inline bool equal (const value_type &, const compare_type &);
     353                 :             :   static inline void remove (value_type &);
     354                 :             :   static inline void mark_deleted (value_type &);
     355                 :             :   static const bool empty_zero_p = T1::empty_zero_p;
     356                 :             :   static inline void mark_empty (value_type &);
     357                 :             :   static inline bool is_deleted (const value_type &);
     358                 :             :   static inline bool is_empty (const value_type &);
     359                 :             : };
     360                 :             : 
     361                 :             : template <typename T1, typename T2>
     362                 :             : inline hashval_t
     363                 :   281467680 : pair_hash <T1, T2>::hash (const value_type &x)
     364                 :             : {
     365                 :   281467680 :   return iterative_hash_hashval_t (T1::hash (x.first), T2::hash (x.second));
     366                 :             : }
     367                 :             : 
     368                 :             : template <typename T1, typename T2>
     369                 :             : inline bool
     370                 :   258512179 : pair_hash <T1, T2>::equal (const value_type &x, const compare_type &y)
     371                 :             : {
     372                 :   258512179 :   return T1::equal (x.first, y.first) && T2::equal (x.second, y.second);
     373                 :             : }
     374                 :             : 
     375                 :             : template <typename T1, typename T2>
     376                 :             : inline void
     377                 :             : pair_hash <T1, T2>::remove (value_type &x)
     378                 :             : {
     379                 :             :   T1::remove (x.first);
     380                 :             :   T2::remove (x.second);
     381                 :             : }
     382                 :             : 
     383                 :             : template <typename T1, typename T2>
     384                 :             : inline void
     385                 :             : pair_hash <T1, T2>::mark_deleted (value_type &x)
     386                 :             : {
     387                 :             :   T1::mark_deleted (x.first);
     388                 :             : }
     389                 :             : 
     390                 :             : template <typename T1, typename T2>
     391                 :             : inline void
     392                 :           0 : pair_hash <T1, T2>::mark_empty (value_type &x)
     393                 :             : {
     394                 :           0 :   T1::mark_empty (x.first);
     395                 :             : }
     396                 :             : 
     397                 :             : template <typename T1, typename T2>
     398                 :             : inline bool
     399                 :   344093444 : pair_hash <T1, T2>::is_deleted (const value_type &x)
     400                 :             : {
     401                 :    37109903 :   return T1::is_deleted (x.first);
     402                 :             : }
     403                 :             : 
     404                 :             : template <typename T1, typename T2>
     405                 :             : inline bool
     406                 :  1160627801 : pair_hash <T1, T2>::is_empty (const value_type &x)
     407                 :             : {
     408                 :  1123518490 :   return T1::is_empty (x.first);
     409                 :             : }
     410                 :             : 
     411                 :             : /* Base traits for vectors, providing just the hash and comparison
     412                 :             :    functionality.  Type gives the corresponding traits for the element
     413                 :             :    type.  */
     414                 :             : 
     415                 :             : template <typename Type>
     416                 :             : struct vec_hash_base
     417                 :             : {
     418                 :             :   typedef vec<typename Type::value_type> value_type;
     419                 :             :   typedef vec<typename Type::compare_type> compare_type;
     420                 :             : 
     421                 :             :   static inline hashval_t hash (value_type);
     422                 :             :   static inline bool equal (value_type, compare_type);
     423                 :             : };
     424                 :             : 
     425                 :             : template <typename Type>
     426                 :             : inline hashval_t
     427                 :       17532 : vec_hash_base <Type>::hash (value_type x)
     428                 :             : {
     429                 :       17532 :   inchash::hash hstate;
     430                 :       17532 :   hstate.add_int (x.length ());
     431                 :       85415 :   for (auto &value : x)
     432                 :       50351 :     hstate.merge_hash (Type::hash (value));
     433                 :       17532 :   return hstate.end ();
     434                 :             : }
     435                 :             : 
     436                 :             : template <typename Type>
     437                 :             : inline bool
     438                 :        4555 : vec_hash_base <Type>::equal (value_type x, compare_type y)
     439                 :             : {
     440                 :        9110 :   if (x.length () != y.length ())
     441                 :             :     return false;
     442                 :       11633 :   for (unsigned int i = 0; i < x.length (); ++i)
     443                 :        8103 :     if (!Type::equal (x[i], y[i]))
     444                 :             :       return false;
     445                 :             :   return true;
     446                 :             : }
     447                 :             : 
     448                 :             : /* Traits for vectors whose contents should be freed normally.  */
     449                 :             : 
     450                 :             : template <typename Type>
     451                 :             : struct vec_free_hash_base : vec_hash_base <Type>
     452                 :             : {
     453                 :             :   static void remove (typename vec_hash_base <Type>::value_type &);
     454                 :             : };
     455                 :             : 
     456                 :             : template <typename Type>
     457                 :             : void
     458                 :             : vec_free_hash_base <Type>
     459                 :             : ::remove (typename vec_hash_base <Type>::value_type &x)
     460                 :             : {
     461                 :             :   for (auto &value : x)
     462                 :             :     Type::remove (x);
     463                 :             :   x.release ();
     464                 :             : }
     465                 :             : 
     466                 :             : template <typename T> struct default_hash_traits : T {};
     467                 :             : 
     468                 :             : template <typename T>
     469                 :             : struct default_hash_traits <T *> : ggc_ptr_hash <T> {};
     470                 :             : 
     471                 :             : #endif
        

Generated by: LCOV version 2.1-beta

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,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.