111
|
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
|