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