1 /* An expandable hash tables datatype.
2 Copyright (C) 1999-2023 Free Software Foundation, Inc.
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 static inline htab_t
228 htab_clear (htab_t htab)
229 {
230 htab->n_elements = 0;
231 htab->n_deleted = 0;
232 memset (htab->entries, 0, htab->size * sizeof (hash_entry_type));
233 return htab;
234 }
235
236 /* Create hash table of size SIZE. */
237
238 static htab_t
239 htab_create (size_t size)
240 {
241 htab_t result;
242 unsigned int size_prime_index;
243
244 size_prime_index = higher_prime_index (size);
245 size = prime_tab[size_prime_index].prime;
246
247 result = (htab_t) htab_alloc (sizeof (struct htab)
248 + size * sizeof (hash_entry_type));
249 result->size = size;
250 result->size_prime_index = size_prime_index;
251 return htab_clear (result);
252 }
253
254 /* Similar to htab_find_slot, but without several unwanted side effects:
255 - Does not call htab_eq when it finds an existing entry.
256 - Does not change the count of elements in the hash table.
257 This function also assumes there are no deleted entries in the table.
258 HASH is the hash value for the element to be inserted. */
259
260 static hash_entry_type *
261 find_empty_slot_for_expand (htab_t htab, hashval_t hash)
262 {
263 hashval_t index = htab_mod (hash, htab);
264 size_t size = htab_size (htab);
265 hash_entry_type *slot = htab->entries + index;
266 hashval_t hash2;
267
268 if (*slot == HTAB_EMPTY_ENTRY)
269 return slot;
270 else if (*slot == HTAB_DELETED_ENTRY)
271 abort ();
272
273 hash2 = htab_mod_m2 (hash, htab);
274 for (;;)
275 {
276 index += hash2;
277 if (index >= size)
278 index -= size;
279
280 slot = htab->entries + index;
281 if (*slot == HTAB_EMPTY_ENTRY)
282 return slot;
283 else if (*slot == HTAB_DELETED_ENTRY)
284 abort ();
285 }
286 }
287
288 /* The following function changes size of memory allocated for the
289 entries and repeatedly inserts the table elements. The occupancy
290 of the table after the call will be about 50%. Naturally the hash
291 table must already exist. Remember also that the place of the
292 table entries is changed. */
293
294 static htab_t
295 htab_expand (htab_t htab)
296 {
297 htab_t nhtab;
298 hash_entry_type *olimit;
299 hash_entry_type *p;
300 size_t osize, elts;
301
302 osize = htab->size;
303 olimit = htab->entries + osize;
304 elts = htab_elements (htab);
305
306 /* Resize only when table after removal of unused elements is either
307 too full or too empty. */
308 if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
309 nhtab = htab_create (elts * 2);
310 else
311 nhtab = htab_create (osize - 1);
312 nhtab->n_elements = htab->n_elements - htab->n_deleted;
313
314 p = htab->entries;
315 do
316 {
317 hash_entry_type x = *p;
318
319 if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
320 *find_empty_slot_for_expand (nhtab, htab_hash (x)) = x;
321
322 p++;
323 }
324 while (p < olimit);
325
326 htab_free (htab);
327 return nhtab;
328 }
329
330 /* This function searches for a hash table entry equal to the given
331 element. It cannot be used to insert or delete an element. */
332
333 static hash_entry_type
334 htab_find (htab_t htab, const hash_entry_type element)
335 {
336 hashval_t index, hash2, hash = htab_hash (element);
337 size_t size;
338 hash_entry_type entry;
339
340 size = htab_size (htab);
341 index = htab_mod (hash, htab);
342
343 entry = htab->entries[index];
344 if (entry == HTAB_EMPTY_ENTRY
345 || (entry != HTAB_DELETED_ENTRY && htab_eq (entry, element)))
346 return entry;
347
348 hash2 = htab_mod_m2 (hash, htab);
349 for (;;)
350 {
351 index += hash2;
352 if (index >= size)
353 index -= size;
354
355 entry = htab->entries[index];
356 if (entry == HTAB_EMPTY_ENTRY
357 || (entry != HTAB_DELETED_ENTRY && htab_eq (entry, element)))
358 return entry;
359 }
360 }
361
362 /* This function searches for a hash table slot containing an entry
363 equal to the given element. To delete an entry, call this with
364 insert=NO_INSERT, then call htab_clear_slot on the slot returned
365 (possibly after doing some checks). To insert an entry, call this
366 with insert=INSERT, then write the value you want into the returned
367 slot. */
368
369 static hash_entry_type *
370 htab_find_slot (htab_t *htabp, const hash_entry_type element,
371 enum insert_option insert)
372 {
373 hash_entry_type *first_deleted_slot;
374 hashval_t index, hash2, hash = htab_hash (element);
375 size_t size;
376 hash_entry_type entry;
377 htab_t htab = *htabp;
378
379 size = htab_size (htab);
380 if (insert == INSERT && size * 3 <= htab->n_elements * 4)
381 {
382 htab = *htabp = htab_expand (htab);
383 size = htab_size (htab);
384 }
385
386 index = htab_mod (hash, htab);
387
388 first_deleted_slot = NULL;
389
390 entry = htab->entries[index];
391 if (entry == HTAB_EMPTY_ENTRY)
392 goto empty_entry;
393 else if (entry == HTAB_DELETED_ENTRY)
394 first_deleted_slot = &htab->entries[index];
395 else if (htab_eq (entry, element))
396 return &htab->entries[index];
397
398 hash2 = htab_mod_m2 (hash, htab);
399 for (;;)
400 {
401 index += hash2;
402 if (index >= size)
403 index -= size;
404
405 entry = htab->entries[index];
406 if (entry == HTAB_EMPTY_ENTRY)
407 goto empty_entry;
408 else if (entry == HTAB_DELETED_ENTRY)
409 {
410 if (!first_deleted_slot)
411 first_deleted_slot = &htab->entries[index];
412 }
413 else if (htab_eq (entry, element))
414 return &htab->entries[index];
415 }
416
417 empty_entry:
418 if (insert == NO_INSERT)
419 return NULL;
420
421 if (first_deleted_slot)
422 {
423 htab->n_deleted--;
424 *first_deleted_slot = HTAB_EMPTY_ENTRY;
425 return first_deleted_slot;
426 }
427
428 htab->n_elements++;
429 return &htab->entries[index];
430 }
431
432 /* This function clears a specified slot in a hash table. It is
433 useful when you've already done the lookup and don't want to do it
434 again. */
435
436 static inline void
437 htab_clear_slot (htab_t htab, hash_entry_type *slot)
438 {
439 if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
440 || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
441 abort ();
442
443 *slot = HTAB_DELETED_ENTRY;
444 htab->n_deleted++;
445 }
446
447 /* Returns a hash code for pointer P. Simplified version of evahash */
448
449 static inline hashval_t
450 hash_pointer (const void *p)
451 {
452 uintptr_t v = (uintptr_t) p;
453 if (sizeof (v) > sizeof (hashval_t))
454 v ^= v >> (sizeof (uintptr_t) / 2 * __CHAR_BIT__);
455 return v;
456 }