|
111
|
1 /* An expandable hash tables datatype.
|
|
145
|
2 Copyright (C) 1999-2020 Free Software Foundation, Inc.
|
|
111
|
3 Contributed by Vladimir Makarov <vmakarov@cygnus.com>.
|
|
|
4
|
|
|
5 This file is part of the GNU Offloading and Multi Processing Library
|
|
|
6 (libgomp).
|
|
|
7
|
|
|
8 Libgomp is free software; you can redistribute it and/or modify it
|
|
|
9 under the terms of the GNU General Public License as published by
|
|
|
10 the Free Software Foundation; either version 3, or (at your option)
|
|
|
11 any later version.
|
|
|
12
|
|
|
13 Libgomp is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
|
|
|
15 FOR A PARTICULAR PURPOSE. See the GNU General Public License for
|
|
|
16 more details.
|
|
|
17
|
|
|
18 Under Section 7 of GPL version 3, you are granted additional
|
|
|
19 permissions described in the GCC Runtime Library Exception, version
|
|
|
20 3.1, as published by the Free Software Foundation.
|
|
|
21
|
|
|
22 You should have received a copy of the GNU General Public License and
|
|
|
23 a copy of the GCC Runtime Library Exception along with this program;
|
|
|
24 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
|
|
|
25 <http://www.gnu.org/licenses/>. */
|
|
|
26
|
|
|
27 /* The hash table code copied from include/hashtab.[hc] and adjusted,
|
|
|
28 so that the hash table entries are in the flexible array at the end
|
|
|
29 of the control structure, no callbacks are used and the elements in the
|
|
|
30 table are of the hash_entry_type type.
|
|
|
31 Before including this file, define hash_entry_type type and
|
|
|
32 htab_alloc and htab_free functions. After including it, define
|
|
|
33 htab_hash and htab_eq inline functions. */
|
|
|
34
|
|
|
35 /* This package implements basic hash table functionality. It is possible
|
|
|
36 to search for an entry, create an entry and destroy an entry.
|
|
|
37
|
|
|
38 Elements in the table are generic pointers.
|
|
|
39
|
|
|
40 The size of the table is not fixed; if the occupancy of the table
|
|
|
41 grows too high the hash table will be expanded.
|
|
|
42
|
|
|
43 The abstract data implementation is based on generalized Algorithm D
|
|
|
44 from Knuth's book "The art of computer programming". Hash table is
|
|
|
45 expanded by creation of new hash table and transferring elements from
|
|
|
46 the old table to the new table. */
|
|
|
47
|
|
|
48 /* The type for a hash code. */
|
|
|
49 typedef unsigned int hashval_t;
|
|
|
50
|
|
|
51 static inline hashval_t htab_hash (hash_entry_type);
|
|
|
52 static inline bool htab_eq (hash_entry_type, hash_entry_type);
|
|
|
53
|
|
|
54 /* This macro defines reserved value for empty table entry. */
|
|
|
55
|
|
|
56 #define HTAB_EMPTY_ENTRY ((hash_entry_type) 0)
|
|
|
57
|
|
|
58 /* This macro defines reserved value for table entry which contained
|
|
|
59 a deleted element. */
|
|
|
60
|
|
|
61 #define HTAB_DELETED_ENTRY ((hash_entry_type) 1)
|
|
|
62
|
|
|
63 /* Hash tables are of the following type. The structure
|
|
|
64 (implementation) of this type is not needed for using the hash
|
|
|
65 tables. All work with hash table should be executed only through
|
|
|
66 functions mentioned below. The size of this structure is subject to
|
|
|
67 change. */
|
|
|
68
|
|
|
69 struct htab {
|
|
|
70 /* Current size (in entries) of the hash table. */
|
|
|
71 size_t size;
|
|
|
72
|
|
|
73 /* Current number of elements including also deleted elements. */
|
|
|
74 size_t n_elements;
|
|
|
75
|
|
|
76 /* Current number of deleted elements in the table. */
|
|
|
77 size_t n_deleted;
|
|
|
78
|
|
|
79 /* Current size (in entries) of the hash table, as an index into the
|
|
|
80 table of primes. */
|
|
|
81 unsigned int size_prime_index;
|
|
|
82
|
|
|
83 /* Table itself. */
|
|
|
84 hash_entry_type entries[];
|
|
|
85 };
|
|
|
86
|
|
|
87 typedef struct htab *htab_t;
|
|
|
88
|
|
|
89 /* An enum saying whether we insert into the hash table or not. */
|
|
|
90 enum insert_option {NO_INSERT, INSERT};
|
|
|
91
|
|
|
92 /* Table of primes and multiplicative inverses.
|
|
|
93
|
|
|
94 Note that these are not minimally reduced inverses. Unlike when generating
|
|
|
95 code to divide by a constant, we want to be able to use the same algorithm
|
|
|
96 all the time. All of these inverses (are implied to) have bit 32 set.
|
|
|
97
|
|
|
98 For the record, the function that computed the table is in
|
|
|
99 libiberty/hashtab.c. */
|
|
|
100
|
|
|
101 struct prime_ent
|
|
|
102 {
|
|
|
103 hashval_t prime;
|
|
|
104 hashval_t inv;
|
|
|
105 hashval_t inv_m2; /* inverse of prime-2 */
|
|
|
106 hashval_t shift;
|
|
|
107 };
|
|
|
108
|
|
|
109 static struct prime_ent const prime_tab[] = {
|
|
|
110 { 7, 0x24924925, 0x9999999b, 2 },
|
|
|
111 { 13, 0x3b13b13c, 0x745d1747, 3 },
|
|
|
112 { 31, 0x08421085, 0x1a7b9612, 4 },
|
|
|
113 { 61, 0x0c9714fc, 0x15b1e5f8, 5 },
|
|
|
114 { 127, 0x02040811, 0x0624dd30, 6 },
|
|
|
115 { 251, 0x05197f7e, 0x073260a5, 7 },
|
|
|
116 { 509, 0x01824366, 0x02864fc8, 8 },
|
|
|
117 { 1021, 0x00c0906d, 0x014191f7, 9 },
|
|
|
118 { 2039, 0x0121456f, 0x0161e69e, 10 },
|
|
|
119 { 4093, 0x00300902, 0x00501908, 11 },
|
|
|
120 { 8191, 0x00080041, 0x00180241, 12 },
|
|
|
121 { 16381, 0x000c0091, 0x00140191, 13 },
|
|
|
122 { 32749, 0x002605a5, 0x002a06e6, 14 },
|
|
|
123 { 65521, 0x000f00e2, 0x00110122, 15 },
|
|
|
124 { 131071, 0x00008001, 0x00018003, 16 },
|
|
|
125 { 262139, 0x00014002, 0x0001c004, 17 },
|
|
|
126 { 524287, 0x00002001, 0x00006001, 18 },
|
|
|
127 { 1048573, 0x00003001, 0x00005001, 19 },
|
|
|
128 { 2097143, 0x00004801, 0x00005801, 20 },
|
|
|
129 { 4194301, 0x00000c01, 0x00001401, 21 },
|
|
|
130 { 8388593, 0x00001e01, 0x00002201, 22 },
|
|
|
131 { 16777213, 0x00000301, 0x00000501, 23 },
|
|
|
132 { 33554393, 0x00001381, 0x00001481, 24 },
|
|
|
133 { 67108859, 0x00000141, 0x000001c1, 25 },
|
|
|
134 { 134217689, 0x000004e1, 0x00000521, 26 },
|
|
|
135 { 268435399, 0x00000391, 0x000003b1, 27 },
|
|
|
136 { 536870909, 0x00000019, 0x00000029, 28 },
|
|
|
137 { 1073741789, 0x0000008d, 0x00000095, 29 },
|
|
|
138 { 2147483647, 0x00000003, 0x00000007, 30 },
|
|
|
139 /* Avoid "decimal constant so large it is unsigned" for 4294967291. */
|
|
|
140 { 0xfffffffb, 0x00000006, 0x00000008, 31 }
|
|
|
141 };
|
|
|
142
|
|
|
143 /* The following function returns an index into the above table of the
|
|
|
144 nearest prime number which is greater than N, and near a power of two. */
|
|
|
145
|
|
|
146 static unsigned int
|
|
|
147 higher_prime_index (unsigned long n)
|
|
|
148 {
|
|
|
149 unsigned int low = 0;
|
|
|
150 unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]);
|
|
|
151
|
|
|
152 while (low != high)
|
|
|
153 {
|
|
|
154 unsigned int mid = low + (high - low) / 2;
|
|
|
155 if (n > prime_tab[mid].prime)
|
|
|
156 low = mid + 1;
|
|
|
157 else
|
|
|
158 high = mid;
|
|
|
159 }
|
|
|
160
|
|
|
161 /* If we've run out of primes, abort. */
|
|
|
162 if (n > prime_tab[low].prime)
|
|
|
163 abort ();
|
|
|
164
|
|
|
165 return low;
|
|
|
166 }
|
|
|
167
|
|
|
168 /* Return the current size of given hash table. */
|
|
|
169
|
|
|
170 static inline size_t
|
|
|
171 htab_size (htab_t htab)
|
|
|
172 {
|
|
|
173 return htab->size;
|
|
|
174 }
|
|
|
175
|
|
|
176 /* Return the current number of elements in given hash table. */
|
|
|
177
|
|
|
178 static inline size_t
|
|
|
179 htab_elements (htab_t htab)
|
|
|
180 {
|
|
|
181 return htab->n_elements - htab->n_deleted;
|
|
|
182 }
|
|
|
183
|
|
|
184 /* Return X % Y. */
|
|
|
185
|
|
|
186 static inline hashval_t
|
|
|
187 htab_mod_1 (hashval_t x, hashval_t y, hashval_t inv, int shift)
|
|
|
188 {
|
|
|
189 /* The multiplicative inverses computed above are for 32-bit types, and
|
|
|
190 requires that we be able to compute a highpart multiply. */
|
|
|
191 if (sizeof (hashval_t) * __CHAR_BIT__ <= 32)
|
|
|
192 {
|
|
|
193 hashval_t t1, t2, t3, t4, q, r;
|
|
|
194
|
|
|
195 t1 = ((unsigned long long)x * inv) >> 32;
|
|
|
196 t2 = x - t1;
|
|
|
197 t3 = t2 >> 1;
|
|
|
198 t4 = t1 + t3;
|
|
|
199 q = t4 >> shift;
|
|
|
200 r = x - (q * y);
|
|
|
201
|
|
|
202 return r;
|
|
|
203 }
|
|
|
204
|
|
|
205 /* Otherwise just use the native division routines. */
|
|
|
206 return x % y;
|
|
|
207 }
|
|
|
208
|
|
|
209 /* Compute the primary hash for HASH given HTAB's current size. */
|
|
|
210
|
|
|
211 static inline hashval_t
|
|
|
212 htab_mod (hashval_t hash, htab_t htab)
|
|
|
213 {
|
|
|
214 const struct prime_ent *p = &prime_tab[htab->size_prime_index];
|
|
|
215 return htab_mod_1 (hash, p->prime, p->inv, p->shift);
|
|
|
216 }
|
|
|
217
|
|
|
218 /* Compute the secondary hash for HASH given HTAB's current size. */
|
|
|
219
|
|
|
220 static inline hashval_t
|
|
|
221 htab_mod_m2 (hashval_t hash, htab_t htab)
|
|
|
222 {
|
|
|
223 const struct prime_ent *p = &prime_tab[htab->size_prime_index];
|
|
|
224 return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift);
|
|
|
225 }
|
|
|
226
|
|
|
227 /* Create hash table of size SIZE. */
|
|
|
228
|
|
|
229 static htab_t
|
|
|
230 htab_create (size_t size)
|
|
|
231 {
|
|
|
232 htab_t result;
|
|
|
233 unsigned int size_prime_index;
|
|
|
234
|
|
|
235 size_prime_index = higher_prime_index (size);
|
|
|
236 size = prime_tab[size_prime_index].prime;
|
|
|
237
|
|
|
238 result = (htab_t) htab_alloc (sizeof (struct htab)
|
|
|
239 + size * sizeof (hash_entry_type));
|
|
|
240 result->size = size;
|
|
|
241 result->n_elements = 0;
|
|
|
242 result->n_deleted = 0;
|
|
|
243 result->size_prime_index = size_prime_index;
|
|
|
244 memset (result->entries, 0, size * sizeof (hash_entry_type));
|
|
|
245 return result;
|
|
|
246 }
|
|
|
247
|
|
|
248 /* Similar to htab_find_slot, but without several unwanted side effects:
|
|
|
249 - Does not call htab_eq when it finds an existing entry.
|
|
|
250 - Does not change the count of elements in the hash table.
|
|
|
251 This function also assumes there are no deleted entries in the table.
|
|
|
252 HASH is the hash value for the element to be inserted. */
|
|
|
253
|
|
|
254 static hash_entry_type *
|
|
|
255 find_empty_slot_for_expand (htab_t htab, hashval_t hash)
|
|
|
256 {
|
|
|
257 hashval_t index = htab_mod (hash, htab);
|
|
|
258 size_t size = htab_size (htab);
|
|
|
259 hash_entry_type *slot = htab->entries + index;
|
|
|
260 hashval_t hash2;
|
|
|
261
|
|
|
262 if (*slot == HTAB_EMPTY_ENTRY)
|
|
|
263 return slot;
|
|
|
264 else if (*slot == HTAB_DELETED_ENTRY)
|
|
|
265 abort ();
|
|
|
266
|
|
|
267 hash2 = htab_mod_m2 (hash, htab);
|
|
|
268 for (;;)
|
|
|
269 {
|
|
|
270 index += hash2;
|
|
|
271 if (index >= size)
|
|
|
272 index -= size;
|
|
|
273
|
|
|
274 slot = htab->entries + index;
|
|
|
275 if (*slot == HTAB_EMPTY_ENTRY)
|
|
|
276 return slot;
|
|
|
277 else if (*slot == HTAB_DELETED_ENTRY)
|
|
|
278 abort ();
|
|
|
279 }
|
|
|
280 }
|
|
|
281
|
|
|
282 /* The following function changes size of memory allocated for the
|
|
|
283 entries and repeatedly inserts the table elements. The occupancy
|
|
|
284 of the table after the call will be about 50%. Naturally the hash
|
|
|
285 table must already exist. Remember also that the place of the
|
|
|
286 table entries is changed. */
|
|
|
287
|
|
|
288 static htab_t
|
|
|
289 htab_expand (htab_t htab)
|
|
|
290 {
|
|
|
291 htab_t nhtab;
|
|
|
292 hash_entry_type *olimit;
|
|
|
293 hash_entry_type *p;
|
|
|
294 size_t osize, elts;
|
|
|
295
|
|
|
296 osize = htab->size;
|
|
|
297 olimit = htab->entries + osize;
|
|
|
298 elts = htab_elements (htab);
|
|
|
299
|
|
|
300 /* Resize only when table after removal of unused elements is either
|
|
|
301 too full or too empty. */
|
|
|
302 if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
|
|
|
303 nhtab = htab_create (elts * 2);
|
|
|
304 else
|
|
|
305 nhtab = htab_create (osize - 1);
|
|
|
306 nhtab->n_elements = htab->n_elements - htab->n_deleted;
|
|
|
307
|
|
|
308 p = htab->entries;
|
|
|
309 do
|
|
|
310 {
|
|
|
311 hash_entry_type x = *p;
|
|
|
312
|
|
|
313 if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
|
|
|
314 *find_empty_slot_for_expand (nhtab, htab_hash (x)) = x;
|
|
|
315
|
|
|
316 p++;
|
|
|
317 }
|
|
|
318 while (p < olimit);
|
|
|
319
|
|
|
320 htab_free (htab);
|
|
|
321 return nhtab;
|
|
|
322 }
|
|
|
323
|
|
|
324 /* This function searches for a hash table entry equal to the given
|
|
|
325 element. It cannot be used to insert or delete an element. */
|
|
|
326
|
|
|
327 static hash_entry_type
|
|
|
328 htab_find (htab_t htab, const hash_entry_type element)
|
|
|
329 {
|
|
|
330 hashval_t index, hash2, hash = htab_hash (element);
|
|
|
331 size_t size;
|
|
|
332 hash_entry_type entry;
|
|
|
333
|
|
|
334 size = htab_size (htab);
|
|
|
335 index = htab_mod (hash, htab);
|
|
|
336
|
|
|
337 entry = htab->entries[index];
|
|
|
338 if (entry == HTAB_EMPTY_ENTRY
|
|
|
339 || (entry != HTAB_DELETED_ENTRY && htab_eq (entry, element)))
|
|
|
340 return entry;
|
|
|
341
|
|
|
342 hash2 = htab_mod_m2 (hash, htab);
|
|
|
343 for (;;)
|
|
|
344 {
|
|
|
345 index += hash2;
|
|
|
346 if (index >= size)
|
|
|
347 index -= size;
|
|
|
348
|
|
|
349 entry = htab->entries[index];
|
|
|
350 if (entry == HTAB_EMPTY_ENTRY
|
|
|
351 || (entry != HTAB_DELETED_ENTRY && htab_eq (entry, element)))
|
|
|
352 return entry;
|
|
|
353 }
|
|
|
354 }
|
|
|
355
|
|
|
356 /* This function searches for a hash table slot containing an entry
|
|
|
357 equal to the given element. To delete an entry, call this with
|
|
|
358 insert=NO_INSERT, then call htab_clear_slot on the slot returned
|
|
|
359 (possibly after doing some checks). To insert an entry, call this
|
|
|
360 with insert=INSERT, then write the value you want into the returned
|
|
|
361 slot. */
|
|
|
362
|
|
|
363 static hash_entry_type *
|
|
|
364 htab_find_slot (htab_t *htabp, const hash_entry_type element,
|
|
|
365 enum insert_option insert)
|
|
|
366 {
|
|
|
367 hash_entry_type *first_deleted_slot;
|
|
|
368 hashval_t index, hash2, hash = htab_hash (element);
|
|
|
369 size_t size;
|
|
|
370 hash_entry_type entry;
|
|
|
371 htab_t htab = *htabp;
|
|
|
372
|
|
|
373 size = htab_size (htab);
|
|
|
374 if (insert == INSERT && size * 3 <= htab->n_elements * 4)
|
|
|
375 {
|
|
|
376 htab = *htabp = htab_expand (htab);
|
|
|
377 size = htab_size (htab);
|
|
|
378 }
|
|
|
379
|
|
|
380 index = htab_mod (hash, htab);
|
|
|
381
|
|
|
382 first_deleted_slot = NULL;
|
|
|
383
|
|
|
384 entry = htab->entries[index];
|
|
|
385 if (entry == HTAB_EMPTY_ENTRY)
|
|
|
386 goto empty_entry;
|
|
|
387 else if (entry == HTAB_DELETED_ENTRY)
|
|
|
388 first_deleted_slot = &htab->entries[index];
|
|
|
389 else if (htab_eq (entry, element))
|
|
|
390 return &htab->entries[index];
|
|
|
391
|
|
|
392 hash2 = htab_mod_m2 (hash, htab);
|
|
|
393 for (;;)
|
|
|
394 {
|
|
|
395 index += hash2;
|
|
|
396 if (index >= size)
|
|
|
397 index -= size;
|
|
|
398
|
|
|
399 entry = htab->entries[index];
|
|
|
400 if (entry == HTAB_EMPTY_ENTRY)
|
|
|
401 goto empty_entry;
|
|
|
402 else if (entry == HTAB_DELETED_ENTRY)
|
|
|
403 {
|
|
|
404 if (!first_deleted_slot)
|
|
|
405 first_deleted_slot = &htab->entries[index];
|
|
|
406 }
|
|
|
407 else if (htab_eq (entry, element))
|
|
|
408 return &htab->entries[index];
|
|
|
409 }
|
|
|
410
|
|
|
411 empty_entry:
|
|
|
412 if (insert == NO_INSERT)
|
|
|
413 return NULL;
|
|
|
414
|
|
|
415 if (first_deleted_slot)
|
|
|
416 {
|
|
|
417 htab->n_deleted--;
|
|
|
418 *first_deleted_slot = HTAB_EMPTY_ENTRY;
|
|
|
419 return first_deleted_slot;
|
|
|
420 }
|
|
|
421
|
|
|
422 htab->n_elements++;
|
|
|
423 return &htab->entries[index];
|
|
|
424 }
|
|
|
425
|
|
|
426 /* This function clears a specified slot in a hash table. It is
|
|
|
427 useful when you've already done the lookup and don't want to do it
|
|
|
428 again. */
|
|
|
429
|
|
|
430 static inline void
|
|
|
431 htab_clear_slot (htab_t htab, hash_entry_type *slot)
|
|
|
432 {
|
|
|
433 if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
|
|
|
434 || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
|
|
|
435 abort ();
|
|
|
436
|
|
|
437 *slot = HTAB_DELETED_ENTRY;
|
|
|
438 htab->n_deleted++;
|
|
|
439 }
|
|
|
440
|
|
|
441 /* Returns a hash code for pointer P. Simplified version of evahash */
|
|
|
442
|
|
|
443 static inline hashval_t
|
|
|
444 hash_pointer (const void *p)
|
|
|
445 {
|
|
|
446 uintptr_t v = (uintptr_t) p;
|
|
|
447 if (sizeof (v) > sizeof (hashval_t))
|
|
|
448 v ^= v >> (sizeof (uintptr_t) / 2 * __CHAR_BIT__);
|
|
|
449 return v;
|
|
|
450 }
|
