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