1/* A type-safe hash table template.
2 Copyright (C) 2012-2025 Free Software Foundation, Inc.
3 Contributed by Lawrence Crowl <crowl@google.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
21
22/* This file implements a typed hash table.
23 The implementation borrows from libiberty's hashtab. */
24
25#ifdef GENERATOR_FILE
26#include "bconfig.h"
27#else
28#include "config.h"
29#endif
30#include "system.h"
31#include "coretypes.h"
32#include "hash-table.h"
33
34/* Table of primes and multiplicative inverses.
35
36 Note that these are not minimally reduced inverses. Unlike when generating
37 code to divide by a constant, we want to be able to use the same algorithm
38 all the time. All of these inverses (are implied to) have bit 32 set.
39
40 For the record, here's the function that computed the table; it's a
41 vastly simplified version of the function of the same name from gcc. */
42
43struct prime_ent const prime_tab[] = {
44 { .prime: 7, .inv: 0x24924925, .inv_m2: 0x9999999b, .shift: 2 },
45 { .prime: 13, .inv: 0x3b13b13c, .inv_m2: 0x745d1747, .shift: 3 },
46 { .prime: 31, .inv: 0x08421085, .inv_m2: 0x1a7b9612, .shift: 4 },
47 { .prime: 61, .inv: 0x0c9714fc, .inv_m2: 0x15b1e5f8, .shift: 5 },
48 { .prime: 127, .inv: 0x02040811, .inv_m2: 0x0624dd30, .shift: 6 },
49 { .prime: 251, .inv: 0x05197f7e, .inv_m2: 0x073260a5, .shift: 7 },
50 { .prime: 509, .inv: 0x01824366, .inv_m2: 0x02864fc8, .shift: 8 },
51 { .prime: 1021, .inv: 0x00c0906d, .inv_m2: 0x014191f7, .shift: 9 },
52 { .prime: 2039, .inv: 0x0121456f, .inv_m2: 0x0161e69e, .shift: 10 },
53 { .prime: 4093, .inv: 0x00300902, .inv_m2: 0x00501908, .shift: 11 },
54 { .prime: 8191, .inv: 0x00080041, .inv_m2: 0x00180241, .shift: 12 },
55 { .prime: 16381, .inv: 0x000c0091, .inv_m2: 0x00140191, .shift: 13 },
56 { .prime: 32749, .inv: 0x002605a5, .inv_m2: 0x002a06e6, .shift: 14 },
57 { .prime: 65521, .inv: 0x000f00e2, .inv_m2: 0x00110122, .shift: 15 },
58 { .prime: 131071, .inv: 0x00008001, .inv_m2: 0x00018003, .shift: 16 },
59 { .prime: 262139, .inv: 0x00014002, .inv_m2: 0x0001c004, .shift: 17 },
60 { .prime: 524287, .inv: 0x00002001, .inv_m2: 0x00006001, .shift: 18 },
61 { .prime: 1048573, .inv: 0x00003001, .inv_m2: 0x00005001, .shift: 19 },
62 { .prime: 2097143, .inv: 0x00004801, .inv_m2: 0x00005801, .shift: 20 },
63 { .prime: 4194301, .inv: 0x00000c01, .inv_m2: 0x00001401, .shift: 21 },
64 { .prime: 8388593, .inv: 0x00001e01, .inv_m2: 0x00002201, .shift: 22 },
65 { .prime: 16777213, .inv: 0x00000301, .inv_m2: 0x00000501, .shift: 23 },
66 { .prime: 33554393, .inv: 0x00001381, .inv_m2: 0x00001481, .shift: 24 },
67 { .prime: 67108859, .inv: 0x00000141, .inv_m2: 0x000001c1, .shift: 25 },
68 { .prime: 134217689, .inv: 0x000004e1, .inv_m2: 0x00000521, .shift: 26 },
69 { .prime: 268435399, .inv: 0x00000391, .inv_m2: 0x000003b1, .shift: 27 },
70 { .prime: 536870909, .inv: 0x00000019, .inv_m2: 0x00000029, .shift: 28 },
71 { .prime: 1073741789, .inv: 0x0000008d, .inv_m2: 0x00000095, .shift: 29 },
72 { .prime: 2147483647, .inv: 0x00000003, .inv_m2: 0x00000007, .shift: 30 },
73 /* Avoid "decimal constant so large it is unsigned" for 4294967291. */
74 { .prime: 0xfffffffb, .inv: 0x00000006, .inv_m2: 0x00000008, .shift: 31 }
75};
76
77/* Limit number of comparisons when calling hash_table<>::verify. */
78unsigned int hash_table_sanitize_eq_limit;
79
80/* The following function returns an index into the above table of the
81 nearest prime number which is at least N, and near a power of two. */
82
83unsigned int
84hash_table_higher_prime_index (unsigned long n)
85{
86 unsigned int low = 0;
87 unsigned int high = ARRAY_SIZE (prime_tab);
88
89 while (low != high)
90 {
91 unsigned int mid = low + (high - low) / 2;
92 if (n > prime_tab[mid].prime)
93 low = mid + 1;
94 else
95 high = mid;
96 }
97
98 /* If we've run out of primes, abort. */
99 gcc_assert (n <= prime_tab[low].prime);
100
101 return low;
102}
103
104/* Return a reference to the lazily initialized hash-table usage description.
105 This needs to be a function rather than a simple global variable so that it
106 is reliably initialized before hash table variables in other files such as
107 sem_item::m_type_hash_cache. */
108mem_alloc_description<mem_usage>&
109hash_table_usage ()
110{
111 static mem_alloc_description<mem_usage> usage;
112 return usage;
113}
114
115/* Support function for statistics. */
116void dump_hash_table_loc_statistics (void)
117{
118 if (!GATHER_STATISTICS)
119 return;
120
121 for (unsigned i = HASH_TABLE_ORIGIN; i <= HASH_SET_ORIGIN; i++)
122 {
123 mem_alloc_origin origin = (mem_alloc_origin) i;
124 hash_table_usage ().dump (origin);
125 }
126}
127
128/* Report a hash table checking error. */
129
130ATTRIBUTE_NORETURN ATTRIBUTE_COLD
131void
132hashtab_chk_error ()
133{
134 fprintf (stderr, format: "hash table checking failed: "
135 "equal operator returns true for a pair "
136 "of values with a different hash value\n");
137 gcc_unreachable ();
138}
139

source code of gcc/hash-table.cc