LCOV - code coverage report
Current view: top level - gcc - inchash.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 100.0 % 65 65
Test Date: 2024-11-02 13:25:42 Functions: 73.3 % 15 11
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* An incremental hash abstract data type.
       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 INCHASH_H
      21                 :             : #define INCHASH_H 1
      22                 :             : 
      23                 :             : 
      24                 :             : /* This file implements an incremential hash function ADT, to be used
      25                 :             :    by code that incrementially hashes a lot of unrelated data
      26                 :             :    (not in a single memory block) into a single value. The goal
      27                 :             :    is to make it easy to plug in efficient hash algorithms.
      28                 :             :    Currently it just implements the plain old jhash based
      29                 :             :    incremental hash from gcc's tree.cc.  */
      30                 :             : 
      31                 :             : hashval_t iterative_hash_host_wide_int (HOST_WIDE_INT, hashval_t);
      32                 :             : hashval_t iterative_hash_hashval_t (hashval_t, hashval_t);
      33                 :             : 
      34                 :             : namespace inchash
      35                 :             : {
      36                 :             : 
      37                 :             : class hash
      38                 :             : {
      39                 :             :  public:
      40                 :             : 
      41                 :             :   /* Start incremential hashing, optionally with SEED.  */
      42                 :  6154027808 :   hash (hashval_t seed = 0)
      43                 :  3977291770 :   {
      44                 :  6154027808 :     val = seed;
      45                 :  6132607335 :     bits = 0;
      46                 :             :   }
      47                 :             : 
      48                 :             :   /* End incremential hashing and provide the final value.  */
      49                 :  3222399295 :   hashval_t end () const
      50                 :             :   {
      51                 :  1511927982 :     return val;
      52                 :             :   }
      53                 :             : 
      54                 :             :   /* Add unsigned value V.  */
      55                 : 10324303257 :   void add_int (unsigned v)
      56                 :             :   {
      57                 :  9686301582 :     val = iterative_hash_hashval_t (v, val);
      58                 :  6258117034 :   }
      59                 :             : 
      60                 :             :   /* Add polynomial value V, treating each element as an unsigned int.  */
      61                 :             :   template<unsigned int N, typename T>
      62                 :   206842050 :   void add_poly_int (const poly_int<N, T> &v)
      63                 :             :   {
      64                 :   413684100 :     for (unsigned int i = 0; i < N; ++i)
      65                 :   206842050 :       add_int (v.coeffs[i]);
      66                 :   206842050 :   }
      67                 :             : 
      68                 :             :   /* Add HOST_WIDE_INT value V.  */
      69                 :  7266951788 :   void add_hwi (HOST_WIDE_INT v)
      70                 :             :   {
      71                 :  5830514031 :     val = iterative_hash_host_wide_int (v, val);
      72                 :  1373466542 :   }
      73                 :             : 
      74                 :             :   /* Add polynomial value V, treating each element as a HOST_WIDE_INT.  */
      75                 :             :   template<unsigned int N, typename T>
      76                 :   296026404 :   void add_poly_hwi (const poly_int<N, T> &v)
      77                 :             :   {
      78                 :   592052808 :     for (unsigned int i = 0; i < N; ++i)
      79                 :   296026404 :       add_hwi (v.coeffs[i]);
      80                 :   296026404 :   }
      81                 :             : 
      82                 :             :   /* Add wide_int-based value V.  */
      83                 :             :   template<typename T>
      84                 :    95340942 :   void add_wide_int (const generic_wide_int<T> &x)
      85                 :             :   {
      86                 :    95340942 :     add_int (x.get_len ());
      87                 :   190936771 :     for (unsigned i = 0; i < x.get_len (); i++)
      88                 :    95595829 :       add_hwi (x.sext_elt (i));
      89                 :    95340942 :   }
      90                 :             : 
      91                 :             :   void add_real_value (const class real_value &v);
      92                 :             : 
      93                 :             :   /* Hash in pointer PTR.  */
      94                 :   631772217 :   void add_ptr (const void *ptr)
      95                 :             :   {
      96                 :  1145785341 :     add (&ptr, sizeof (ptr));
      97                 :             :   }
      98                 :             : 
      99                 :             :   /* Add a memory block DATA with size LEN.  */
     100                 :  8366963004 :   void add (const void *data, size_t len)
     101                 :             :   {
     102                 : 13256205294 :     val = iterative_hash (data, len, val);
     103                 :  2224996328 :   }
     104                 :             : 
     105                 :             :   /* Merge hash value OTHER.  */
     106                 :   816366961 :   void merge_hash (hashval_t other)
     107                 :             :   {
     108                 :   725569808 :     val = iterative_hash_hashval_t (other, val);
     109                 :   202774574 :   }
     110                 :             : 
     111                 :             :   /* Hash in state from other inchash OTHER.  */
     112                 :   138735217 :   void merge (const hash &other)
     113                 :             :   {
     114                 :   138735217 :     merge_hash (other.val);
     115                 :   138735217 :   }
     116                 :             : 
     117                 :  5609743535 :   template<class T> void add_object(T &obj)
     118                 :             :   {
     119                 :  5609743535 :     add (&obj, sizeof(T));
     120                 :  4729081553 :   }
     121                 :             : 
     122                 :             :   /* Support for accumulating boolean flags */
     123                 :             : 
     124                 :  1286205936 :   void add_flag (bool flag)
     125                 :             :   {
     126                 :  1258519159 :     bits = (bits << 1) | flag;
     127                 :    15172010 :   }
     128                 :             : 
     129                 :    16718974 :   void commit_flag ()
     130                 :             :   {
     131                 :    16718974 :     add_int (bits);
     132                 :    16718974 :     bits = 0;
     133                 :    16718974 :   }
     134                 :             : 
     135                 :             :   /* Support for commutative hashing. Add A and B in a defined order
     136                 :             :      based on their value. This is useful for hashing commutative
     137                 :             :      expressions, so that A+B and B+A get the same hash.  */
     138                 :             : 
     139                 :   138735217 :   void add_commutative (const hash &a, const hash &b)
     140                 :             :   {
     141                 :   138735217 :     if (a.end() > b.end())
     142                 :             :       {
     143                 :    78950887 :         merge (b);
     144                 :    78950887 :         merge (a);
     145                 :             :       }
     146                 :             :     else
     147                 :             :       {
     148                 :    59784330 :         merge (a);
     149                 :    59784330 :         merge (b);
     150                 :             :       }
     151                 :   138735217 :   }
     152                 :             : 
     153                 :             :  private:
     154                 :             :   hashval_t val;
     155                 :             :   unsigned bits;
     156                 :             : };
     157                 :             : 
     158                 :             : }
     159                 :             : 
     160                 :             : /* Borrowed from hashtab.c iterative_hash implementation.  */
     161                 :             : #define mix(a,b,c) \
     162                 :             : { \
     163                 :             :   a -= b; a -= c; a ^= (c>>13); \
     164                 :             :   b -= c; b -= a; b ^= (a<< 8); \
     165                 :             :   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
     166                 :             :   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
     167                 :             :   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
     168                 :             :   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
     169                 :             :   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
     170                 :             :   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
     171                 :             :   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
     172                 :             : }
     173                 :             : 
     174                 :             : 
     175                 :             : /* Produce good hash value combining VAL and VAL2.  */
     176                 :             : inline
     177                 :             : hashval_t
     178                 : 25532427177 : iterative_hash_hashval_t (hashval_t val, hashval_t val2)
     179                 :             : {
     180                 :             :   /* the golden ratio; an arbitrary value.  */
     181                 : 25532427177 :   hashval_t a = 0x9e3779b9;
     182                 :             : 
     183                 : 25532427177 :   mix (a, val, val2);
     184                 : 25532427177 :   return val2;
     185                 :             : }
     186                 :             : 
     187                 :             : /* Produce good hash value combining VAL and VAL2.  */
     188                 :             : 
     189                 :             : inline
     190                 :             : hashval_t
     191                 : >10754*10^7 : iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
     192                 :             : {
     193                 : >10754*10^7 :   if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
     194                 :             :     return iterative_hash_hashval_t (val, val2);
     195                 :             :   else
     196                 :             :     {
     197                 : >10754*10^7 :       hashval_t a = (hashval_t) val;
     198                 :             :       /* Avoid warnings about shifting of more than the width of the type on
     199                 :             :          hosts that won't execute this path.  */
     200                 : >10754*10^7 :       int zero = 0;
     201                 : >10754*10^7 :       hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
     202                 : >10754*10^7 :       mix (a, b, val2);
     203                 : >10754*10^7 :       if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
     204                 :             :         {
     205                 :             :           hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
     206                 :             :           hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
     207                 :             :           mix (a, b, val2);
     208                 :             :         }
     209                 : >10754*10^7 :       return val2;
     210                 :             :     }
     211                 :             : }
     212                 :             : 
     213                 :             : #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.