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