Line data Source code
1 : /* An incremental hash abstract data type. 2 : Copyright (C) 2014-2023 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 632036994 : hash (hashval_t seed = 0) 43 632036838 : { 44 632036994 : val = seed; 45 632036994 : bits = 0; 46 : } 47 : 48 : /* End incremential hashing and provide the final value. */ 49 632036838 : hashval_t end () 50 : { 51 632036838 : return val; 52 : } 53 : 54 : /* Add unsigned value V. */ 55 5344992 : void add_int (unsigned v) 56 : { 57 5344992 : val = iterative_hash_hashval_t (v, val); 58 : } 59 : 60 : /* Add polynomial value V, treating each element as an unsigned int. */ 61 : template<unsigned int N, typename T> 62 : void add_poly_int (const poly_int_pod<N, T> &v) 63 : { 64 : for (unsigned int i = 0; i < N; ++i) 65 : add_int (v.coeffs[i]); 66 : } 67 : 68 : /* Add HOST_WIDE_INT value V. */ 69 : void add_hwi (HOST_WIDE_INT v) 70 : { 71 : val = iterative_hash_host_wide_int (v, val); 72 : } 73 : 74 : /* Add polynomial value V, treating each element as a HOST_WIDE_INT. */ 75 : template<unsigned int N, typename T> 76 : void add_poly_hwi (const poly_int_pod<N, T> &v) 77 : { 78 : for (unsigned int i = 0; i < N; ++i) 79 : add_hwi (v.coeffs[i]); 80 : } 81 : 82 : /* Add wide_int-based value V. */ 83 : template<typename T> 84 : void add_wide_int (const generic_wide_int<T> &x) 85 : { 86 : add_int (x.get_len ()); 87 : for (unsigned i = 0; i < x.get_len (); i++) 88 : add_hwi (x.sext_elt (i)); 89 : } 90 : 91 : void add_real_value (const class real_value &v); 92 : 93 : /* Hash in pointer PTR. */ 94 : void add_ptr (const void *ptr) 95 : { 96 : add (&ptr, sizeof (ptr)); 97 : } 98 : 99 : /* Add a memory block DATA with size LEN. */ 100 : void add (const void *data, size_t len) 101 : { 102 : val = iterative_hash (data, len, val); 103 : } 104 : 105 : /* Merge hash value OTHER. */ 106 2681810 : void merge_hash (hashval_t other) 107 : { 108 2681810 : val = iterative_hash_hashval_t (other, val); 109 : } 110 : 111 : /* Hash in state from other inchash OTHER. */ 112 : void merge (hash &other) 113 : { 114 : merge_hash (other.val); 115 : } 116 : 117 : template<class T> void add_object(T &obj) 118 : { 119 : add (&obj, sizeof(T)); 120 : } 121 : 122 : /* Support for accumulating boolean flags */ 123 : 124 : void add_flag (bool flag) 125 : { 126 : bits = (bits << 1) | flag; 127 : } 128 : 129 : void commit_flag () 130 : { 131 : add_int (bits); 132 : bits = 0; 133 : } 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 : void add_commutative (hash &a, hash &b) 140 : { 141 : if (a.end() > b.end()) 142 : { 143 : merge (b); 144 : merge (a); 145 : } 146 : else 147 : { 148 : merge (a); 149 : merge (b); 150 : } 151 : } 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 146031147 : iterative_hash_hashval_t (hashval_t val, hashval_t val2) 179 : { 180 : /* the golden ratio; an arbitrary value. */ 181 146031147 : hashval_t a = 0x9e3779b9; 182 : 183 146031147 : mix (a, val, val2); 184 146031147 : return val2; 185 : } 186 : 187 : /* Produce good hash value combining VAL and VAL2. */ 188 : 189 : inline 190 : hashval_t 191 : iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2) 192 : { 193 : if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t)) 194 : return iterative_hash_hashval_t (val, val2); 195 : else 196 : { 197 : 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 : int zero = 0; 201 : hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero)); 202 : mix (a, b, val2); 203 : 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 : return val2; 210 : } 211 : } 212 : 213 : #endif
