|
111
|
1 /* An incremental hash abstract data type.
|
|
145
|
2 Copyright (C) 2014-2020 Free Software Foundation, Inc.
|
|
111
|
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.c. */
|
|
|
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 hash (hashval_t seed = 0)
|
|
|
43 {
|
|
|
44 val = seed;
|
|
|
45 bits = 0;
|
|
|
46 }
|
|
|
47
|
|
|
48 /* End incremential hashing and provide the final value. */
|
|
|
49 hashval_t end ()
|
|
|
50 {
|
|
|
51 return val;
|
|
|
52 }
|
|
|
53
|
|
|
54 /* Add unsigned value V. */
|
|
|
55 void add_int (unsigned v)
|
|
|
56 {
|
|
|
57 val = iterative_hash_hashval_t (v, val);
|
|
|
58 }
|
|
|
59
|
|
131
|
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
|
|
111
|
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
|
|
131
|
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
|
|
111
|
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++)
|
|
145
|
88 add_hwi (x.sext_elt (i));
|
|
111
|
89 }
|
|
|
90
|
|
|
91 /* Hash in pointer PTR. */
|
|
|
92 void add_ptr (const void *ptr)
|
|
|
93 {
|
|
|
94 add (&ptr, sizeof (ptr));
|
|
|
95 }
|
|
|
96
|
|
|
97 /* Add a memory block DATA with size LEN. */
|
|
|
98 void add (const void *data, size_t len)
|
|
|
99 {
|
|
|
100 val = iterative_hash (data, len, val);
|
|
|
101 }
|
|
|
102
|
|
|
103 /* Merge hash value OTHER. */
|
|
|
104 void merge_hash (hashval_t other)
|
|
|
105 {
|
|
|
106 val = iterative_hash_hashval_t (other, val);
|
|
|
107 }
|
|
|
108
|
|
|
109 /* Hash in state from other inchash OTHER. */
|
|
|
110 void merge (hash &other)
|
|
|
111 {
|
|
|
112 merge_hash (other.val);
|
|
|
113 }
|
|
|
114
|
|
|
115 template<class T> void add_object(T &obj)
|
|
|
116 {
|
|
|
117 add (&obj, sizeof(T));
|
|
|
118 }
|
|
|
119
|
|
|
120 /* Support for accumulating boolean flags */
|
|
|
121
|
|
|
122 void add_flag (bool flag)
|
|
|
123 {
|
|
|
124 bits = (bits << 1) | flag;
|
|
|
125 }
|
|
|
126
|
|
|
127 void commit_flag ()
|
|
|
128 {
|
|
|
129 add_int (bits);
|
|
|
130 bits = 0;
|
|
|
131 }
|
|
|
132
|
|
|
133 /* Support for commutative hashing. Add A and B in a defined order
|
|
|
134 based on their value. This is useful for hashing commutative
|
|
|
135 expressions, so that A+B and B+A get the same hash. */
|
|
|
136
|
|
|
137 void add_commutative (hash &a, hash &b)
|
|
|
138 {
|
|
|
139 if (a.end() > b.end())
|
|
|
140 {
|
|
|
141 merge (b);
|
|
|
142 merge (a);
|
|
|
143 }
|
|
|
144 else
|
|
|
145 {
|
|
|
146 merge (a);
|
|
|
147 merge (b);
|
|
|
148 }
|
|
|
149 }
|
|
|
150
|
|
|
151 private:
|
|
|
152 hashval_t val;
|
|
|
153 unsigned bits;
|
|
|
154 };
|
|
|
155
|
|
|
156 }
|
|
|
157
|
|
|
158 /* Borrowed from hashtab.c iterative_hash implementation. */
|
|
|
159 #define mix(a,b,c) \
|
|
|
160 { \
|
|
|
161 a -= b; a -= c; a ^= (c>>13); \
|
|
|
162 b -= c; b -= a; b ^= (a<< 8); \
|
|
|
163 c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
|
|
|
164 a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
|
|
|
165 b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
|
|
|
166 c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
|
|
|
167 a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
|
|
|
168 b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
|
|
|
169 c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
|
|
|
170 }
|
|
|
171
|
|
|
172
|
|
|
173 /* Produce good hash value combining VAL and VAL2. */
|
|
|
174 inline
|
|
|
175 hashval_t
|
|
|
176 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
|
|
|
177 {
|
|
|
178 /* the golden ratio; an arbitrary value. */
|
|
|
179 hashval_t a = 0x9e3779b9;
|
|
|
180
|
|
|
181 mix (a, val, val2);
|
|
|
182 return val2;
|
|
|
183 }
|
|
|
184
|
|
|
185 /* Produce good hash value combining VAL and VAL2. */
|
|
|
186
|
|
|
187 inline
|
|
|
188 hashval_t
|
|
|
189 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
|
|
|
190 {
|
|
|
191 if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
|
|
|
192 return iterative_hash_hashval_t (val, val2);
|
|
|
193 else
|
|
|
194 {
|
|
|
195 hashval_t a = (hashval_t) val;
|
|
|
196 /* Avoid warnings about shifting of more than the width of the type on
|
|
|
197 hosts that won't execute this path. */
|
|
|
198 int zero = 0;
|
|
|
199 hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
|
|
|
200 mix (a, b, val2);
|
|
|
201 if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
|
|
|
202 {
|
|
|
203 hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
|
|
|
204 hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
|
|
|
205 mix (a, b, val2);
|
|
|
206 }
|
|
|
207 return val2;
|
|
|
208 }
|
|
|
209 }
|
|
|
210
|
|
|
211 #endif
|
