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 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 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 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 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