1 /* A type-safe hash table template.
2    Copyright (C) 2012-2013 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