Branch data Line data Source code
1 : : /* A type-safe hash table template.
2 : : Copyright (C) 2012-2024 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 : : { 7, 0x24924925, 0x9999999b, 2 },
45 : : { 13, 0x3b13b13c, 0x745d1747, 3 },
46 : : { 31, 0x08421085, 0x1a7b9612, 4 },
47 : : { 61, 0x0c9714fc, 0x15b1e5f8, 5 },
48 : : { 127, 0x02040811, 0x0624dd30, 6 },
49 : : { 251, 0x05197f7e, 0x073260a5, 7 },
50 : : { 509, 0x01824366, 0x02864fc8, 8 },
51 : : { 1021, 0x00c0906d, 0x014191f7, 9 },
52 : : { 2039, 0x0121456f, 0x0161e69e, 10 },
53 : : { 4093, 0x00300902, 0x00501908, 11 },
54 : : { 8191, 0x00080041, 0x00180241, 12 },
55 : : { 16381, 0x000c0091, 0x00140191, 13 },
56 : : { 32749, 0x002605a5, 0x002a06e6, 14 },
57 : : { 65521, 0x000f00e2, 0x00110122, 15 },
58 : : { 131071, 0x00008001, 0x00018003, 16 },
59 : : { 262139, 0x00014002, 0x0001c004, 17 },
60 : : { 524287, 0x00002001, 0x00006001, 18 },
61 : : { 1048573, 0x00003001, 0x00005001, 19 },
62 : : { 2097143, 0x00004801, 0x00005801, 20 },
63 : : { 4194301, 0x00000c01, 0x00001401, 21 },
64 : : { 8388593, 0x00001e01, 0x00002201, 22 },
65 : : { 16777213, 0x00000301, 0x00000501, 23 },
66 : : { 33554393, 0x00001381, 0x00001481, 24 },
67 : : { 67108859, 0x00000141, 0x000001c1, 25 },
68 : : { 134217689, 0x000004e1, 0x00000521, 26 },
69 : : { 268435399, 0x00000391, 0x000003b1, 27 },
70 : : { 536870909, 0x00000019, 0x00000029, 28 },
71 : : { 1073741789, 0x0000008d, 0x00000095, 29 },
72 : : { 2147483647, 0x00000003, 0x00000007, 30 },
73 : : /* Avoid "decimal constant so large it is unsigned" for 4294967291. */
74 : : { 0xfffffffb, 0x00000006, 0x00000008, 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 : 6834019964 : hash_table_higher_prime_index (unsigned long n)
85 : : {
86 : 6834019964 : unsigned int low = 0;
87 : 6834019964 : unsigned int high = ARRAY_SIZE (prime_tab);
88 : :
89 : 47838139748 : while (low != high)
90 : : {
91 : 34170099820 : unsigned int mid = low + (high - low) / 2;
92 : 34170099820 : if (n > prime_tab[mid].prime)
93 : 7019749958 : low = mid + 1;
94 : : else
95 : : high = mid;
96 : : }
97 : :
98 : : /* If we've run out of primes, abort. */
99 : 6834019964 : gcc_assert (n <= prime_tab[low].prime);
100 : :
101 : 6834019964 : 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 : 0 : hash_table_usage ()
110 : : {
111 : 0 : static mem_alloc_description<mem_usage> usage;
112 : 0 : return usage;
113 : : }
114 : :
115 : : /* Support function for statistics. */
116 : 0 : void dump_hash_table_loc_statistics (void)
117 : : {
118 : 0 : if (!GATHER_STATISTICS)
119 : 0 : 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 : 0 : hashtab_chk_error ()
133 : : {
134 : 0 : fprintf (stderr, "hash table checking failed: "
135 : : "equal operator returns true for a pair "
136 : : "of values with a different hash value\n");
137 : 0 : gcc_unreachable ();
138 : : }
|
