1 /* A type-safe hash table template.
2 Copyright (C) 2012-2016 Free Software Foundation, Inc.
3 Contributed by Lawrence Crowl <crowl@google.com>
5 This file is part of GCC.
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
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
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/>. */
22 /* This file implements a typed hash table.
23 The implementation borrows from libiberty's hashtab. */
31 #include "coretypes.h"
32 #include "hash-table.h"
34 /* Table of primes and multiplicative inverses.
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.
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. */
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 }
77 /* The following function returns an index into the above table of the
78 nearest prime number which is greater than N, and near a power of two. */
81 hash_table_higher_prime_index (unsigned long n)
84 unsigned int high = sizeof (prime_tab) / sizeof (prime_tab[0]);
88 unsigned int mid = low + (high - low) / 2;
89 if (n > prime_tab[mid].prime)
95 /* If we've run out of primes, abort. */
96 gcc_assert (n <= prime_tab[low].prime);
101 mem_alloc_description<mem_usage> hash_table_usage;
103 /* Support function for statistics. */
104 void dump_hash_table_loc_statistics (void)
106 if (!GATHER_STATISTICS)
109 for (unsigned i = HASH_TABLE_ORIGIN; i <= HASH_SET_ORIGIN; i++)
111 mem_alloc_origin origin = (mem_alloc_origin) i;
112 hash_table_usage.dump (origin);