1 | /* A type-safe hash table template. |
2 | Copyright (C) 2012-2023 Free Software Foundation, Inc. |
3 | Contributed by Lawrence Crowl <crowl@google.com> |
4 | |
5 | This file is part of GCC. |
6 | |
7 | GCC is free software; you can redistribute it and/or modify it under |
8 | the terms of the GNU General Public License as published by the Free |
9 | Software Foundation; either version 3, or (at your option) any later |
10 | version. |
11 | |
12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
15 | for more details. |
16 | |
17 | You should have received a copy of the GNU General Public License |
18 | along 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 | |
43 | struct 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. */ |
78 | unsigned 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 | |
83 | unsigned int |
84 | hash_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. */ |
108 | mem_alloc_description<mem_usage>& |
109 | hash_table_usage () |
110 | { |
111 | static mem_alloc_description<mem_usage> usage; |
112 | return usage; |
113 | } |
114 | |
115 | /* Support function for statistics. */ |
116 | void 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 | |
130 | ATTRIBUTE_NORETURN ATTRIBUTE_COLD |
131 | void |
132 | hashtab_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 | |