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