]>
Commit | Line | Data |
---|---|---|
fbd26352 | 1 | /* Copyright (C) 2012-2019 Free Software Foundation, Inc. |
b710ec85 | 2 | |
3 | This file is part of GCC. | |
4 | ||
5 | GCC is free software; you can redistribute it and/or modify | |
6 | it under the terms of the GNU General Public License as published by | |
7 | the Free Software Foundation; either version 3, or (at your option) | |
8 | any later version. | |
9 | ||
10 | GCC is distributed in the hope that it will be useful, | |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
13 | GNU General Public License for more details. | |
14 | ||
15 | Under Section 7 of GPL version 3, you are granted additional | |
16 | permissions described in the GCC Runtime Library Exception, version | |
17 | 3.1, as published by the Free Software Foundation. | |
18 | ||
19 | You should have received a copy of the GNU General Public License and | |
20 | a copy of the GCC Runtime Library Exception along with this program; | |
21 | see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
22 | <http://www.gnu.org/licenses/>. */ | |
23 | ||
24 | #ifndef _VTV_MAP_H | |
25 | #define _VTV_MAP_H 1 | |
26 | ||
27 | #include <string.h> | |
5be42fa9 | 28 | |
29 | #ifdef __MINGW32__ | |
30 | #include <stdint.h> | |
31 | #include "vtv_utils.h" | |
32 | #else | |
b710ec85 | 33 | #include <vtv_utils.h> |
5be42fa9 | 34 | #endif |
b710ec85 | 35 | |
36 | inline uint64_t | |
37 | load8bytes (const void *p) | |
38 | { | |
39 | uint64_t result; | |
40 | memcpy (&result, p, 8); | |
41 | return result; | |
42 | } | |
43 | ||
44 | /* Insert_only_hash_map maps keys to values. The implementation is a | |
45 | basic hash table with open addressing. The keys are not "owned" by | |
46 | the table; it only stores pointers to keys. The key type is | |
47 | specified below (see insert_only_hash_map::key_type) and is, | |
48 | roughly speaking, a string of any length with the string length and | |
49 | a hash code stored at the front. The code here does not compute | |
50 | any hash codes, but rather uses what's given. */ | |
51 | ||
52 | template<typename T, typename Alloc> | |
53 | class insert_only_hash_map | |
54 | { | |
55 | public: | |
56 | typedef size_t size_type; | |
57 | typedef T value_type; | |
58 | typedef Alloc alloc_type; | |
59 | enum { min_capacity = 4 }; | |
60 | #if HASHMAP_STATS | |
61 | enum { stats = true }; | |
62 | #else | |
63 | enum { stats = false }; | |
64 | #endif | |
65 | ||
66 | /* Keys are a byte string (up to 2^32 - 1 long) plus a uint32_t | |
67 | that's used as a hash code. The latter can encode arbitrary | |
68 | information at the client's discretion, so, e.g., multiple keys | |
69 | that are the same string still "differ" if the hash codes differ. | |
70 | Keys are equal if the first 8 bytes are equal and the next n | |
71 | bytes are equal. */ | |
72 | struct key_type | |
73 | { | |
74 | uint32_t n; | |
75 | uint32_t hash; | |
76 | char bytes[0]; | |
77 | ||
78 | bool | |
79 | equals (const key_type *k) const; | |
80 | }; | |
81 | ||
82 | /* Create an empty map with a reasonable number of buckets for the | |
83 | expected size. Returns NULL if the allocator fails. */ | |
84 | ||
85 | static insert_only_hash_map * | |
86 | create (size_type expected_size); | |
87 | ||
88 | /* The opposite of create(). Free the memory for the given map. */ | |
89 | ||
90 | static void | |
91 | destroy (insert_only_hash_map *m) | |
92 | { Alloc().dealloc (m, m->size_in_bytes_); } | |
93 | ||
94 | /* Return a map identical to this except that *k is mapped to v. | |
95 | Typcially it's done by modifying this in place, but if a resize | |
96 | is necessary then this is deallocated and a new map is returned. | |
97 | Requires k to be non-NULL. Does nothing and returns NULL if the | |
98 | allocator fails. */ | |
99 | ||
100 | insert_only_hash_map* | |
101 | put (const key_type *k, const value_type &v) | |
102 | { return this->put_internal (k, v, false); } | |
103 | ||
104 | /* If *k is a key in this then set *v to point to the corresponding | |
105 | value. Otherwise, do the equivalent of insert(k, value_type()) | |
106 | and, if that succeeds, set *v to point to the inserted value. | |
107 | Requires k to be non-NULL. Does nothing and returns NULL if the | |
108 | allocator fails. Typically returns this, but will return a new | |
109 | insert_only_hash_map if a resize occurs. If the return value is | |
110 | non-NULL, *v is set and it's valid until a resize of the map that | |
111 | is the return value. */ | |
112 | ||
113 | insert_only_hash_map * | |
114 | find_or_add_key (const key_type *k, value_type **v); | |
115 | ||
116 | /* Get the value corresponding to *k. Returns NULL if there is | |
117 | none. Requires k to be non-NULL. The return value is valid | |
118 | until any resize. */ | |
119 | const value_type *get (const key_type *k) const; | |
120 | ||
121 | size_type | |
122 | size () const | |
123 | { return num_entries_; } | |
124 | ||
125 | bool | |
126 | empty () const | |
127 | { return this->size () == 0; } | |
128 | ||
129 | size_type | |
130 | bucket_count () const | |
131 | { return num_buckets_; } | |
132 | ||
133 | private: | |
134 | typedef std::pair <const key_type *, value_type> bucket_type; | |
135 | ||
136 | insert_only_hash_map *put_internal (const key_type *, const value_type &, | |
137 | bool); | |
138 | ||
139 | /* This function determines when to resize the table. */ | |
140 | bool | |
141 | is_too_full (size_type entries) const | |
142 | { return entries > (this->bucket_count () * 0.7); } | |
143 | ||
144 | /* Return a copy with double the number of buckets. Returns NULL if | |
145 | the allocator fails. Otherwise, calls destroy (this). */ | |
146 | insert_only_hash_map *destructive_copy (); | |
147 | ||
148 | /* Must be a power of 2 not less than min_capacity. */ | |
149 | size_type num_buckets_; | |
150 | size_type num_entries_; | |
151 | size_type size_in_bytes_; | |
152 | bucket_type buckets[0]; /* Actual array size is num_buckets. */ | |
153 | }; | |
154 | ||
155 | template <typename T, typename Alloc> | |
156 | insert_only_hash_map <T, Alloc> * | |
157 | insert_only_hash_map <T, Alloc>::create (size_type expected_size) | |
158 | { | |
159 | size_t cap = min_capacity; | |
160 | while (expected_size >= cap) | |
161 | { | |
162 | cap *= 2; | |
163 | } | |
164 | size_t size_in_bytes = sizeof (insert_only_hash_map <T, Alloc>) | |
165 | + cap * sizeof (bucket_type); | |
166 | insert_only_hash_map <T, Alloc>* result = | |
167 | static_cast <insert_only_hash_map <T, Alloc>*> (Alloc () | |
168 | .alloc (size_in_bytes)); | |
169 | if (result != NULL) | |
170 | { | |
171 | result->size_in_bytes_ = size_in_bytes; | |
172 | result->num_buckets_ = cap; | |
173 | result->num_entries_ = 0; | |
174 | memset (result->buckets, 0, cap * sizeof (bucket_type)); | |
175 | } | |
176 | return result; | |
177 | } | |
178 | ||
179 | template <typename T, typename Alloc> | |
180 | insert_only_hash_map <T, Alloc>* | |
181 | insert_only_hash_map <T, Alloc>::destructive_copy () | |
182 | { | |
183 | insert_only_hash_map* copy = create (this->bucket_count ()); | |
184 | if (copy == NULL) | |
185 | return NULL; | |
186 | VTV_DEBUG_ASSERT (copy->bucket_count () == 2 * this->bucket_count ()); | |
187 | for (size_type i = 0; i < this->bucket_count (); i++) | |
188 | if (this->buckets[i].first != NULL) | |
189 | copy->put_internal (this->buckets[i].first, this->buckets[i].second, | |
190 | true); | |
191 | VTV_DEBUG_ASSERT (copy->size () == this->size ()); | |
192 | destroy (this); | |
193 | return copy; | |
194 | } | |
195 | ||
196 | template <typename T, typename Alloc> | |
197 | insert_only_hash_map <T, Alloc>* | |
198 | insert_only_hash_map <T, Alloc>::find_or_add_key (const key_type *k, | |
199 | value_type **v) | |
200 | { | |
201 | /* Table size is always a power of 2. */ | |
202 | const size_type mask = this->bucket_count () - 1; | |
203 | size_type bucket_index = k->hash & mask; | |
204 | size_type step = 1; | |
205 | for (;;) | |
206 | { | |
207 | bucket_type &bucket = this->buckets[bucket_index]; | |
208 | if (bucket.first == NULL) | |
209 | { | |
210 | /* Key was not present. */ | |
211 | if (this->is_too_full (this->size () + 1)) | |
212 | { | |
213 | insert_only_hash_map <T, Alloc>* result = | |
214 | this->destructive_copy (); | |
215 | return result == NULL | |
216 | ? NULL | |
217 | : result->find_or_add_key (k, v); | |
218 | } | |
219 | else | |
220 | { | |
221 | bucket.first = k; | |
222 | bucket.second = T (); | |
223 | this->num_entries_++; | |
224 | *v = &bucket.second; | |
225 | return this; | |
226 | } | |
227 | } | |
228 | else if (bucket.first->equals (k)) | |
229 | { | |
230 | /* Key was present. */ | |
231 | *v = &bucket.second; | |
232 | return this; | |
233 | } | |
234 | else | |
235 | bucket_index = (bucket_index + step++) & mask; | |
236 | } | |
237 | } | |
238 | ||
239 | template <typename T, typename Alloc> | |
240 | insert_only_hash_map <T, Alloc>* | |
241 | insert_only_hash_map <T, Alloc>::put_internal ( | |
242 | const insert_only_hash_map::key_type *k, | |
243 | const insert_only_hash_map::value_type &v, | |
244 | bool unique_key_and_resize_not_needed) | |
245 | { | |
246 | /* Table size is always a power of 2. */ | |
247 | const size_type mask = this->bucket_count () - 1; | |
248 | size_type bucket_index = k->hash & mask; | |
249 | size_type step = 1; | |
250 | for (;;) | |
251 | { | |
252 | bucket_type &bucket = this->buckets[bucket_index]; | |
253 | if (bucket.first == NULL) | |
254 | { | |
255 | /* Key was not present. */ | |
256 | if (!unique_key_and_resize_not_needed | |
257 | && this->is_too_full (this->size () + 1)) | |
258 | { | |
259 | insert_only_hash_map <T, Alloc>* result = | |
260 | this->destructive_copy (); | |
261 | return result == NULL | |
262 | ? NULL | |
263 | : result->put_internal (k, v, true); | |
264 | } | |
265 | else | |
266 | { | |
267 | bucket.first = k; | |
268 | bucket.second = v; | |
269 | this->num_entries_++; | |
270 | return this; | |
271 | } | |
272 | } | |
273 | else if (!unique_key_and_resize_not_needed && bucket.first->equals (k)) | |
274 | { | |
275 | /* Key was present. Just change the value. */ | |
276 | bucket.second = v; | |
277 | return this; | |
278 | } | |
279 | else | |
280 | bucket_index = (bucket_index + step++) & mask; | |
281 | } | |
282 | } | |
283 | ||
284 | template <typename T, typename Alloc> | |
285 | inline const typename insert_only_hash_map <T, Alloc>::value_type* | |
286 | insert_only_hash_map <T, Alloc>::get (const insert_only_hash_map::key_type *k) | |
287 | const | |
288 | { | |
289 | /* Table size is always a power of 2. */ | |
290 | const size_type mask = this->bucket_count () - 1; | |
291 | size_type bucket_index = k->hash & mask; | |
292 | size_type step = 1; | |
293 | for (;;) | |
294 | { | |
295 | const bucket_type &bucket = this->buckets[bucket_index]; | |
296 | if (bucket.first == NULL) | |
297 | return NULL; | |
298 | else if (bucket.first->equals (k)) | |
299 | return &bucket.second; | |
300 | else | |
301 | bucket_index = (bucket_index + step++) & mask; | |
302 | } | |
303 | } | |
304 | ||
305 | template <typename T, typename Alloc> | |
306 | inline bool | |
307 | insert_only_hash_map <T, Alloc>::key_type::equals ( | |
308 | const typename insert_only_hash_map <T, Alloc>::key_type *k) const | |
309 | { | |
310 | const char* x = reinterpret_cast <const char *> (k); | |
311 | const char* y = reinterpret_cast <const char *> (this); | |
312 | return (load8bytes (x) == load8bytes (y) | |
313 | && memcmp (x + 8, y + 8, this->n) == 0); | |
314 | } | |
315 | ||
316 | #endif /* _VTV_MAP_H */ |