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