1 /* Copyright (C) 2012-2023 Free Software Foundation, Inc.
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>
28
29 #ifdef __MINGW32__
30 #include <stdint.h>
31 #include "vtv_utils.h"
32 #else
33 #include <vtv_utils.h>
34 #endif
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 */