|
111
|
1 /* A type-safe hash table template.
|
|
145
|
2 Copyright (C) 2012-2020 Free Software Foundation, Inc.
|
|
111
|
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
|
|
145
|
77 /* Limit number of comparisons when calling hash_table<>::verify. */
|
|
|
78 unsigned int hash_table_sanitize_eq_limit;
|
|
|
79
|
|
111
|
80 /* The following function returns an index into the above table of the
|
|
145
|
81 nearest prime number which is at least N, and near a power of two. */
|
|
111
|
82
|
|
|
83 unsigned int
|
|
|
84 hash_table_higher_prime_index (unsigned long n)
|
|
|
85 {
|
|
|
86 unsigned int low = 0;
|
|
|
87 unsigned int high = sizeof (prime_tab) / sizeof (prime_tab[0]);
|
|
|
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
|
|
131
|
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 }
|
|
111
|
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;
|
|
131
|
124 hash_table_usage ().dump (origin);
|
|
111
|
125 }
|
|
|
126 }
|
|
145
|
127
|
|
|
128 /* Report a hash table checking error. */
|
|
|
129
|
|
|
130 ATTRIBUTE_NORETURN ATTRIBUTE_COLD
|
|
|
131 void
|
|
|
132 hashtab_chk_error ()
|
|
|
133 {
|
|
|
134 fprintf (stderr, "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 }
|
