Mercurial > hg > CbC > CbC_gcc
comparison gcc/inchash.h @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
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 |