LCOV - code coverage report
Current view: top level - gcc - inchash.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 63 63 100.0 %
Date: 2020-04-04 11:58:09 Functions: 4 8 50.0 %
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-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 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.c.  */
      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                 : 1715405563 :   hash (hashval_t seed = 0)
      43                 :  755616257 :   {
      44                 : 1715405563 :     val = seed;
      45                 : 1692761823 :     bits = 0;
      46                 :            :   }
      47                 :            : 
      48                 :            :   /* End incremential hashing and provide the final value.  */
      49                 : 1483631673 :   hashval_t end ()
      50                 :            :   {
      51                 :  821006836 :     return val;
      52                 :            :   }
      53                 :            : 
      54                 :            :   /* Add unsigned value V.  */
      55                 : 1616921582 :   void add_int (unsigned v)
      56                 :            :   {
      57                 : 1477981541 :     val = iterative_hash_hashval_t (v, val);
      58                 :  708937216 :   }
      59                 :            : 
      60                 :            :   /* Add polynomial value V, treating each element as an unsigned int.  */
      61                 :            :   template<unsigned int N, typename T>
      62                 :   11355757 :   void add_poly_int (const poly_int_pod<N, T> &v)
      63                 :            :   {
      64                 :   77138157 :     for (unsigned int i = 0; i < N; ++i)
      65                 :   77138157 :       add_int (v.coeffs[i]);
      66                 :            :   }
      67                 :            : 
      68                 :            :   /* Add HOST_WIDE_INT value V.  */
      69                 : 1526360682 :   void add_hwi (HOST_WIDE_INT v)
      70                 :            :   {
      71                 :  620910510 :     val = iterative_hash_host_wide_int (v, val);
      72                 :  735751746 :   }
      73                 :            : 
      74                 :            :   /* Add polynomial value V, treating each element as a HOST_WIDE_INT.  */
      75                 :            :   template<unsigned int N, typename T>
      76                 :  167597000 :   void add_poly_hwi (const poly_int_pod<N, T> &v)
      77                 :            :   {
      78                 :  167597000 :     for (unsigned int i = 0; i < N; ++i)
      79                 :  167597000 :       add_hwi (v.coeffs[i]);
      80                 :            :   }
      81                 :            : 
      82                 :            :   /* Add wide_int-based value V.  */
      83                 :            :   template<typename T>
      84                 :     851466 :   void add_wide_int (const generic_wide_int<T> &x)
      85                 :            :   {
      86                 :     851466 :     add_int (x.get_len ());
      87                 :    1729360 :     for (unsigned i = 0; i < x.get_len (); i++)
      88                 :     877892 :       add_hwi (x.sext_elt (i));
      89                 :     851466 :   }
      90                 :            : 
      91                 :            :   /* Hash in pointer PTR.  */
      92                 :  169893794 :   void add_ptr (const void *ptr)
      93                 :            :   {
      94                 :  339787592 :     add (&ptr, sizeof (ptr));
      95                 :            :   }
      96                 :            : 
      97                 :            :   /* Add a memory block DATA with size LEN.  */
      98                 : 2471806936 :   void add (const void *data, size_t len)
      99                 :            :   {
     100                 : 2542401329 :     val = iterative_hash (data, len, val);
     101                 :  351035934 :   }
     102                 :            : 
     103                 :            :   /* Merge hash value OTHER.  */
     104                 :  212755558 :   void merge_hash (hashval_t other)
     105                 :            :   {
     106                 :  175322140 :     val = iterative_hash_hashval_t (other, val);
     107                 :   18576165 :   }
     108                 :            : 
     109                 :            :   /* Hash in state from other inchash OTHER.  */
     110                 :   66548100 :   void merge (hash &other)
     111                 :            :   {
     112                 :   66548100 :     merge_hash (other.val);
     113                 :   66548100 :   }
     114                 :            : 
     115                 : 1802340498 :   template<class T> void add_object(T &obj)
     116                 :            :   {
     117                 : 1970190298 :     add (&obj, sizeof(T));
     118                 : 1484409963 :   }
     119                 :            : 
     120                 :            :   /* Support for accumulating boolean flags */
     121                 :            : 
     122                 :   46505190 :   void add_flag (bool flag)
     123                 :            :   {
     124                 :   24979570 :     bits = (bits << 1) | flag;
     125                 :   22834330 :   }
     126                 :            : 
     127                 :   18877560 :   void commit_flag ()
     128                 :            :   {
     129                 :   18877560 :     add_int (bits);
     130                 :   17008200 :     bits = 0;
     131                 :    1869360 :   }
     132                 :            : 
     133                 :            :   /* Support for commutative hashing. Add A and B in a defined order
     134                 :            :      based on their value. This is useful for hashing commutative
     135                 :            :      expressions, so that A+B and B+A get the same hash.  */
     136                 :            : 
     137                 :   66548100 :   void add_commutative (hash &a, hash &b)
     138                 :            :   {
     139                 :   66548100 :     if (a.end() > b.end())
     140                 :            :       {
     141                 :   44086330 :         merge (b);
     142                 :   44086330 :         merge (a);
     143                 :            :       }
     144                 :            :     else
     145                 :            :       {
     146                 :   22461850 :         merge (a);
     147                 :   22461850 :         merge (b);
     148                 :            :       }
     149                 :   66548100 :   }
     150                 :            : 
     151                 :            :  private:
     152                 :            :   hashval_t val;
     153                 :            :   unsigned bits;
     154                 :            : };
     155                 :            : 
     156                 :            : }
     157                 :            : 
     158                 :            : /* Borrowed from hashtab.c iterative_hash implementation.  */
     159                 :            : #define mix(a,b,c) \
     160                 :            : { \
     161                 :            :   a -= b; a -= c; a ^= (c>>13); \
     162                 :            :   b -= c; b -= a; b ^= (a<< 8); \
     163                 :            :   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
     164                 :            :   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
     165                 :            :   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
     166                 :            :   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
     167                 :            :   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
     168                 :            :   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
     169                 :            :   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
     170                 :            : }
     171                 :            : 
     172                 :            : 
     173                 :            : /* Produce good hash value combining VAL and VAL2.  */
     174                 :            : inline
     175                 :            : hashval_t
     176                 : 2095326271 : iterative_hash_hashval_t (hashval_t val, hashval_t val2)
     177                 :            : {
     178                 :            :   /* the golden ratio; an arbitrary value.  */
     179                 : 2095326271 :   hashval_t a = 0x9e3779b9;
     180                 :            : 
     181                 : 2095326271 :   mix (a, val, val2);
     182                 : 2095326271 :   return val2;
     183                 :            : }
     184                 :            : 
     185                 :            : /* Produce good hash value combining VAL and VAL2.  */
     186                 :            : 
     187                 :            : inline
     188                 :            : hashval_t
     189                 : 8884546982 : iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
     190                 :            : {
     191                 : 8884546982 :   if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
     192                 :            :     return iterative_hash_hashval_t (val, val2);
     193                 :            :   else
     194                 :            :     {
     195                 : 8884546982 :       hashval_t a = (hashval_t) val;
     196                 :            :       /* Avoid warnings about shifting of more than the width of the type on
     197                 :            :          hosts that won't execute this path.  */
     198                 : 8884546982 :       int zero = 0;
     199                 : 8884546982 :       hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
     200                 : 8884546982 :       mix (a, b, val2);
     201                 : 8884546982 :       if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
     202                 :            :         {
     203                 :            :           hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
     204                 :            :           hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
     205                 :            :           mix (a, b, val2);
     206                 :            :         }
     207                 : 8884546982 :       return val2;
     208                 :            :     }
     209                 :            : }
     210                 :            : 
     211                 :            : #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.