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