1 | /* An incremental hash abstract data type. |
2 | Copyright (C) 2014-2017 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.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 | |
60 | /* Add HOST_WIDE_INT value V. */ |
61 | void add_hwi (HOST_WIDE_INT v) |
62 | { |
63 | val = iterative_hash_host_wide_int (v, val); |
64 | } |
65 | |
66 | /* Add wide_int-based value V. */ |
67 | template<typename T> |
68 | void add_wide_int (const generic_wide_int<T> &x) |
69 | { |
70 | add_int (x.get_len ()); |
71 | for (unsigned i = 0; i < x.get_len (); i++) |
72 | add_hwi (x.elt (i)); |
73 | } |
74 | |
75 | /* Hash in pointer PTR. */ |
76 | void add_ptr (const void *ptr) |
77 | { |
78 | add (&ptr, sizeof (ptr)); |
79 | } |
80 | |
81 | /* Add a memory block DATA with size LEN. */ |
82 | void add (const void *data, size_t len) |
83 | { |
84 | val = iterative_hash (data, len, val); |
85 | } |
86 | |
87 | /* Merge hash value OTHER. */ |
88 | void merge_hash (hashval_t other) |
89 | { |
90 | val = iterative_hash_hashval_t (other, val); |
91 | } |
92 | |
93 | /* Hash in state from other inchash OTHER. */ |
94 | void merge (hash &other) |
95 | { |
96 | merge_hash (other.val); |
97 | } |
98 | |
99 | template<class T> void add_object(T &obj) |
100 | { |
101 | add (&obj, sizeof(T)); |
102 | } |
103 | |
104 | /* Support for accumulating boolean flags */ |
105 | |
106 | void add_flag (bool flag) |
107 | { |
108 | bits = (bits << 1) | flag; |
109 | } |
110 | |
111 | void commit_flag () |
112 | { |
113 | add_int (bits); |
114 | bits = 0; |
115 | } |
116 | |
117 | /* Support for commutative hashing. Add A and B in a defined order |
118 | based on their value. This is useful for hashing commutative |
119 | expressions, so that A+B and B+A get the same hash. */ |
120 | |
121 | void add_commutative (hash &a, hash &b) |
122 | { |
123 | if (a.end() > b.end()) |
124 | { |
125 | merge (b); |
126 | merge (a); |
127 | } |
128 | else |
129 | { |
130 | merge (a); |
131 | merge (b); |
132 | } |
133 | } |
134 | |
135 | private: |
136 | hashval_t val; |
137 | unsigned bits; |
138 | }; |
139 | |
140 | } |
141 | |
142 | /* Borrowed from hashtab.c iterative_hash implementation. */ |
143 | #define mix(a,b,c) \ |
144 | { \ |
145 | a -= b; a -= c; a ^= (c>>13); \ |
146 | b -= c; b -= a; b ^= (a<< 8); \ |
147 | c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \ |
148 | a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \ |
149 | b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \ |
150 | c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \ |
151 | a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \ |
152 | b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \ |
153 | c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \ |
154 | } |
155 | |
156 | |
157 | /* Produce good hash value combining VAL and VAL2. */ |
158 | inline |
159 | hashval_t |
160 | iterative_hash_hashval_t (hashval_t val, hashval_t val2) |
161 | { |
162 | /* the golden ratio; an arbitrary value. */ |
163 | hashval_t a = 0x9e3779b9; |
164 | |
165 | mix (a, val, val2); |
166 | return val2; |
167 | } |
168 | |
169 | /* Produce good hash value combining VAL and VAL2. */ |
170 | |
171 | inline |
172 | hashval_t |
173 | iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2) |
174 | { |
175 | if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t)) |
176 | return iterative_hash_hashval_t (val, val2); |
177 | else |
178 | { |
179 | hashval_t a = (hashval_t) val; |
180 | /* Avoid warnings about shifting of more than the width of the type on |
181 | hosts that won't execute this path. */ |
182 | int zero = 0; |
183 | hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero)); |
184 | mix (a, b, val2); |
185 | if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t)) |
186 | { |
187 | hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero)); |
188 | hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero)); |
189 | mix (a, b, val2); |
190 | } |
191 | return val2; |
192 | } |
193 | } |
194 | |
195 | #endif |
196 | |