]>
Commit | Line | Data |
---|---|---|
2b15d2ba | 1 | /* A type-safe hash table template. |
fbd26352 | 2 | Copyright (C) 2012-2019 Free Software Foundation, Inc. |
2b15d2ba | 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 | ||
fecd2208 | 25 | #ifdef GENERATOR_FILE |
26 | #include "bconfig.h" | |
27 | #else | |
2b15d2ba | 28 | #include "config.h" |
fecd2208 | 29 | #endif |
2b15d2ba | 30 | #include "system.h" |
31 | #include "coretypes.h" | |
32 | #include "hash-table.h" | |
33 | ||
2b15d2ba | 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 | ||
2b15d2ba | 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 | /* 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. */ | |
79 | ||
80 | unsigned int | |
81 | hash_table_higher_prime_index (unsigned long n) | |
82 | { | |
83 | unsigned int low = 0; | |
9af5ce0c | 84 | unsigned int high = sizeof (prime_tab) / sizeof (prime_tab[0]); |
2b15d2ba | 85 | |
86 | while (low != high) | |
87 | { | |
88 | unsigned int mid = low + (high - low) / 2; | |
89 | if (n > prime_tab[mid].prime) | |
90 | low = mid + 1; | |
91 | else | |
92 | high = mid; | |
93 | } | |
94 | ||
95 | /* If we've run out of primes, abort. */ | |
e2afa5c1 | 96 | gcc_assert (n <= prime_tab[low].prime); |
2b15d2ba | 97 | |
98 | return low; | |
99 | } | |
100 | ||
70e2fd2f | 101 | /* Return a reference to the lazily initialized hash-table usage description. |
102 | This needs to be a function rather than a simple global variable so that it | |
103 | is reliably initialized before hash table variables in other files such as | |
104 | sem_item::m_type_hash_cache. */ | |
105 | mem_alloc_description<mem_usage>& | |
106 | hash_table_usage () | |
107 | { | |
108 | static mem_alloc_description<mem_usage> usage; | |
109 | return usage; | |
110 | } | |
0ff42de5 | 111 | |
112 | /* Support function for statistics. */ | |
113 | void dump_hash_table_loc_statistics (void) | |
114 | { | |
f34a836c | 115 | if (!GATHER_STATISTICS) |
116 | return; | |
117 | ||
a80feb6c | 118 | for (unsigned i = HASH_TABLE_ORIGIN; i <= HASH_SET_ORIGIN; i++) |
0ff42de5 | 119 | { |
120 | mem_alloc_origin origin = (mem_alloc_origin) i; | |
70e2fd2f | 121 | hash_table_usage ().dump (origin); |
0ff42de5 | 122 | } |
123 | } |