]>
Commit | Line | Data |
---|---|---|
6d8eb96b AK |
1 | /* An incremental hash abstract data type. |
2 | Copyright (C) 2014 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 | #include "config.h" | |
24 | #include "system.h" | |
25 | #include "coretypes.h" | |
26 | #include "hashtab.h" | |
27 | ||
28 | /* This file implements an incremential hash function ADT, to be used | |
29 | by code that incrementially hashes a lot of unrelated data | |
30 | (not in a single memory block) into a single value. The goal | |
31 | is to make it easy to plug in efficient hash algorithms. | |
32 | Currently it just implements the plain old jhash based | |
33 | incremental hash from gcc's tree.c. */ | |
34 | ||
35 | extern hashval_t iterative_hash_host_wide_int (HOST_WIDE_INT, hashval_t); | |
36 | extern hashval_t iterative_hash_hashval_t (hashval_t, hashval_t); | |
37 | ||
38 | class inchash | |
39 | { | |
40 | public: | |
41 | ||
42 | /* Start incremential hashing, optionally with SEED. */ | |
43 | inchash (hashval_t seed = 0) | |
44 | { | |
45 | val = seed; | |
46 | bits = 0; | |
47 | } | |
48 | ||
49 | /* End incremential hashing and provide the final value. */ | |
50 | hashval_t end () | |
51 | { | |
52 | return val; | |
53 | } | |
54 | ||
55 | /* Add unsigned value V. */ | |
56 | void add_int (unsigned v) | |
57 | { | |
58 | val = iterative_hash_hashval_t (v, val); | |
59 | } | |
60 | ||
61 | /* Add HOST_WIDE_INT value V. */ | |
62 | void add_wide_int (HOST_WIDE_INT v) | |
63 | { | |
64 | val = iterative_hash_host_wide_int (v, val); | |
65 | } | |
66 | ||
67 | /* Hash in pointer PTR. */ | |
68 | void add_ptr (void *ptr) | |
69 | { | |
70 | add (&ptr, sizeof (ptr)); | |
71 | } | |
72 | ||
73 | /* Add a memory block DATA with size LEN. */ | |
74 | void add (const void *data, size_t len) | |
75 | { | |
76 | val = iterative_hash (data, len, val); | |
77 | } | |
78 | ||
79 | /* Merge hash value OTHER. */ | |
80 | void merge_hash (hashval_t other) | |
81 | { | |
82 | val = iterative_hash_hashval_t (other, val); | |
83 | } | |
84 | ||
85 | /* Hash in state from other inchash OTHER. */ | |
86 | void merge (inchash &other) | |
87 | { | |
88 | merge_hash (other.val); | |
89 | } | |
90 | ||
91 | /* Support for accumulating boolean flags */ | |
92 | ||
93 | void add_flag (bool flag) | |
94 | { | |
95 | bits = (bits << 1) | flag; | |
96 | } | |
97 | ||
98 | void commit_flag () | |
99 | { | |
100 | add_int (bits); | |
101 | bits = 0; | |
102 | } | |
103 | ||
104 | /* Support for commutative hashing. Add A and B in a defined order | |
105 | based on their value. This is useful for hashing commutative | |
106 | expressions, so that A+B and B+A get the same hash. */ | |
107 | ||
108 | void add_commutative (inchash &a, inchash &b) | |
109 | { | |
110 | if (a.end() > b.end()) | |
111 | { | |
112 | merge (b); | |
113 | merge (a); | |
114 | } | |
115 | else | |
116 | { | |
117 | merge (a); | |
118 | merge (b); | |
119 | } | |
120 | } | |
121 | ||
122 | private: | |
123 | hashval_t val; | |
124 | unsigned bits; | |
125 | }; | |
126 | ||
127 | #define add_object(o) add (&(o), sizeof (o)) | |
128 | ||
129 | #endif |