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