]>
Commit | Line | Data |
---|---|---|
0823efed DN |
1 | /* A type-safe hash table template. |
2 | Copyright (C) 2012 | |
3 | Free Software Foundation, Inc. | |
4 | Contributed by Lawrence Crowl <crowl@google.com> | |
5 | ||
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify it under | |
9 | the terms of the GNU General Public License as published by the Free | |
10 | Software Foundation; either version 3, or (at your option) any later | |
11 | version. | |
12 | ||
13 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
14 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
15 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
16 | for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
19 | along with GCC; see the file COPYING3. If not see | |
20 | <http://www.gnu.org/licenses/>. */ | |
21 | ||
22 | ||
23 | /* This file implements a typed hash table. | |
24 | The implementation borrows from libiberty's hashtab. */ | |
25 | ||
26 | #include "config.h" | |
27 | #include "system.h" | |
28 | #include "coretypes.h" | |
29 | #include "hash-table.h" | |
30 | ||
31 | ||
32 | /* Table of primes and multiplicative inverses. | |
33 | ||
34 | Note that these are not minimally reduced inverses. Unlike when generating | |
35 | code to divide by a constant, we want to be able to use the same algorithm | |
36 | all the time. All of these inverses (are implied to) have bit 32 set. | |
37 | ||
38 | For the record, here's the function that computed the table; it's a | |
39 | vastly simplified version of the function of the same name from gcc. */ | |
40 | ||
41 | #if 0 | |
42 | unsigned int | |
43 | ceil_log2 (unsigned int x) | |
44 | { | |
45 | int i; | |
46 | for (i = 31; i >= 0 ; --i) | |
47 | if (x > (1u << i)) | |
48 | return i+1; | |
49 | abort (); | |
50 | } | |
51 | ||
52 | unsigned int | |
53 | choose_multiplier (unsigned int d, unsigned int *mlp, unsigned char *shiftp) | |
54 | { | |
55 | unsigned long long mhigh; | |
56 | double nx; | |
57 | int lgup, post_shift; | |
58 | int pow, pow2; | |
59 | int n = 32, precision = 32; | |
60 | ||
61 | lgup = ceil_log2 (d); | |
62 | pow = n + lgup; | |
63 | pow2 = n + lgup - precision; | |
64 | ||
65 | nx = ldexp (1.0, pow) + ldexp (1.0, pow2); | |
66 | mhigh = nx / d; | |
67 | ||
68 | *shiftp = lgup - 1; | |
69 | *mlp = mhigh; | |
70 | return mhigh >> 32; | |
71 | } | |
72 | #endif | |
73 | ||
74 | struct prime_ent const prime_tab[] = { | |
75 | { 7, 0x24924925, 0x9999999b, 2 }, | |
76 | { 13, 0x3b13b13c, 0x745d1747, 3 }, | |
77 | { 31, 0x08421085, 0x1a7b9612, 4 }, | |
78 | { 61, 0x0c9714fc, 0x15b1e5f8, 5 }, | |
79 | { 127, 0x02040811, 0x0624dd30, 6 }, | |
80 | { 251, 0x05197f7e, 0x073260a5, 7 }, | |
81 | { 509, 0x01824366, 0x02864fc8, 8 }, | |
82 | { 1021, 0x00c0906d, 0x014191f7, 9 }, | |
83 | { 2039, 0x0121456f, 0x0161e69e, 10 }, | |
84 | { 4093, 0x00300902, 0x00501908, 11 }, | |
85 | { 8191, 0x00080041, 0x00180241, 12 }, | |
86 | { 16381, 0x000c0091, 0x00140191, 13 }, | |
87 | { 32749, 0x002605a5, 0x002a06e6, 14 }, | |
88 | { 65521, 0x000f00e2, 0x00110122, 15 }, | |
89 | { 131071, 0x00008001, 0x00018003, 16 }, | |
90 | { 262139, 0x00014002, 0x0001c004, 17 }, | |
91 | { 524287, 0x00002001, 0x00006001, 18 }, | |
92 | { 1048573, 0x00003001, 0x00005001, 19 }, | |
93 | { 2097143, 0x00004801, 0x00005801, 20 }, | |
94 | { 4194301, 0x00000c01, 0x00001401, 21 }, | |
95 | { 8388593, 0x00001e01, 0x00002201, 22 }, | |
96 | { 16777213, 0x00000301, 0x00000501, 23 }, | |
97 | { 33554393, 0x00001381, 0x00001481, 24 }, | |
98 | { 67108859, 0x00000141, 0x000001c1, 25 }, | |
99 | { 134217689, 0x000004e1, 0x00000521, 26 }, | |
100 | { 268435399, 0x00000391, 0x000003b1, 27 }, | |
101 | { 536870909, 0x00000019, 0x00000029, 28 }, | |
102 | { 1073741789, 0x0000008d, 0x00000095, 29 }, | |
103 | { 2147483647, 0x00000003, 0x00000007, 30 }, | |
104 | /* Avoid "decimal constant so large it is unsigned" for 4294967291. */ | |
105 | { 0xfffffffb, 0x00000006, 0x00000008, 31 } | |
106 | }; | |
107 | ||
108 | /* The following function returns an index into the above table of the | |
109 | nearest prime number which is greater than N, and near a power of two. */ | |
110 | ||
111 | unsigned int | |
112 | hash_table_higher_prime_index (unsigned long n) | |
113 | { | |
114 | unsigned int low = 0; | |
115 | unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]); | |
116 | ||
117 | while (low != high) | |
118 | { | |
119 | unsigned int mid = low + (high - low) / 2; | |
120 | if (n > prime_tab[mid].prime) | |
121 | low = mid + 1; | |
122 | else | |
123 | high = mid; | |
124 | } | |
125 | ||
126 | /* If we've run out of primes, abort. */ | |
127 | if (n > prime_tab[low].prime) | |
128 | { | |
129 | fprintf (stderr, "Cannot find prime bigger than %lu\n", n); | |
130 | abort (); | |
131 | } | |
132 | ||
133 | return low; | |
134 | } | |
135 | ||
136 | /* Return X % Y using multiplicative inverse values INV and SHIFT. | |
137 | ||
138 | The multiplicative inverses computed above are for 32-bit types, | |
139 | and requires that we be able to compute a highpart multiply. | |
140 | ||
141 | FIX: I am not at all convinced that | |
142 | 3 loads, 2 multiplications, 3 shifts, and 3 additions | |
143 | will be faster than | |
144 | 1 load and 1 modulus | |
145 | on modern systems running a compiler. */ | |
146 | ||
147 | #ifdef UNSIGNED_64BIT_TYPE | |
148 | static inline hashval_t | |
149 | mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift) | |
150 | { | |
151 | __extension__ typedef UNSIGNED_64BIT_TYPE ull; | |
152 | hashval_t t1, t2, t3, t4, q, r; | |
153 | ||
154 | t1 = ((ull)x * inv) >> 32; | |
155 | t2 = x - t1; | |
156 | t3 = t2 >> 1; | |
157 | t4 = t1 + t3; | |
158 | q = t4 >> shift; | |
159 | r = x - (q * y); | |
160 | ||
161 | return r; | |
162 | } | |
163 | #endif | |
164 | ||
165 | /* Compute the primary table index for HASH given current prime index. */ | |
166 | ||
167 | hashval_t | |
168 | hash_table_mod1 (hashval_t hash, unsigned int index) | |
169 | { | |
170 | const struct prime_ent *p = &prime_tab[index]; | |
171 | #ifdef UNSIGNED_64BIT_TYPE | |
172 | if (sizeof (hashval_t) * CHAR_BIT <= 32) | |
173 | return mul_mod (hash, p->prime, p->inv, p->shift); | |
174 | #endif | |
175 | return hash % p->prime; | |
176 | } | |
177 | ||
178 | ||
179 | /* Compute the secondary table index for HASH given current prime index. */ | |
180 | ||
181 | hashval_t | |
182 | hash_table_mod2 (hashval_t hash, unsigned int index) | |
183 | { | |
184 | const struct prime_ent *p = &prime_tab[index]; | |
185 | #ifdef UNSIGNED_64BIT_TYPE | |
186 | if (sizeof (hashval_t) * CHAR_BIT <= 32) | |
187 | return 1 + mul_mod (hash, p->prime - 2, p->inv_m2, p->shift); | |
188 | #endif | |
189 | return 1 + hash % (p->prime - 2); | |
190 | } |