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 |