diff options
Diffstat (limited to 'gcc-4.8/gcc/hash-table.c')
| -rw-r--r-- | gcc-4.8/gcc/hash-table.c | 189 |
1 files changed, 189 insertions, 0 deletions
diff --git a/gcc-4.8/gcc/hash-table.c b/gcc-4.8/gcc/hash-table.c new file mode 100644 index 000000000..d3cb7b108 --- /dev/null +++ b/gcc-4.8/gcc/hash-table.c @@ -0,0 +1,189 @@ +/* A type-safe hash table template. + Copyright (C) 2012-2013 Free Software Foundation, Inc. + Contributed by Lawrence Crowl <crowl@google.com> + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + + +/* This file implements a typed hash table. + The implementation borrows from libiberty's hashtab. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "hash-table.h" + + +/* Table of primes and multiplicative inverses. + + Note that these are not minimally reduced inverses. Unlike when generating + code to divide by a constant, we want to be able to use the same algorithm + all the time. All of these inverses (are implied to) have bit 32 set. + + For the record, here's the function that computed the table; it's a + vastly simplified version of the function of the same name from gcc. */ + +#if 0 +unsigned int +ceil_log2 (unsigned int x) +{ + int i; + for (i = 31; i >= 0 ; --i) + if (x > (1u << i)) + return i+1; + abort (); +} + +unsigned int +choose_multiplier (unsigned int d, unsigned int *mlp, unsigned char *shiftp) +{ + unsigned long long mhigh; + double nx; + int lgup, post_shift; + int pow, pow2; + int n = 32, precision = 32; + + lgup = ceil_log2 (d); + pow = n + lgup; + pow2 = n + lgup - precision; + + nx = ldexp (1.0, pow) + ldexp (1.0, pow2); + mhigh = nx / d; + + *shiftp = lgup - 1; + *mlp = mhigh; + return mhigh >> 32; +} +#endif + +struct prime_ent const prime_tab[] = { + { 7, 0x24924925, 0x9999999b, 2 }, + { 13, 0x3b13b13c, 0x745d1747, 3 }, + { 31, 0x08421085, 0x1a7b9612, 4 }, + { 61, 0x0c9714fc, 0x15b1e5f8, 5 }, + { 127, 0x02040811, 0x0624dd30, 6 }, + { 251, 0x05197f7e, 0x073260a5, 7 }, + { 509, 0x01824366, 0x02864fc8, 8 }, + { 1021, 0x00c0906d, 0x014191f7, 9 }, + { 2039, 0x0121456f, 0x0161e69e, 10 }, + { 4093, 0x00300902, 0x00501908, 11 }, + { 8191, 0x00080041, 0x00180241, 12 }, + { 16381, 0x000c0091, 0x00140191, 13 }, + { 32749, 0x002605a5, 0x002a06e6, 14 }, + { 65521, 0x000f00e2, 0x00110122, 15 }, + { 131071, 0x00008001, 0x00018003, 16 }, + { 262139, 0x00014002, 0x0001c004, 17 }, + { 524287, 0x00002001, 0x00006001, 18 }, + { 1048573, 0x00003001, 0x00005001, 19 }, + { 2097143, 0x00004801, 0x00005801, 20 }, + { 4194301, 0x00000c01, 0x00001401, 21 }, + { 8388593, 0x00001e01, 0x00002201, 22 }, + { 16777213, 0x00000301, 0x00000501, 23 }, + { 33554393, 0x00001381, 0x00001481, 24 }, + { 67108859, 0x00000141, 0x000001c1, 25 }, + { 134217689, 0x000004e1, 0x00000521, 26 }, + { 268435399, 0x00000391, 0x000003b1, 27 }, + { 536870909, 0x00000019, 0x00000029, 28 }, + { 1073741789, 0x0000008d, 0x00000095, 29 }, + { 2147483647, 0x00000003, 0x00000007, 30 }, + /* Avoid "decimal constant so large it is unsigned" for 4294967291. */ + { 0xfffffffb, 0x00000006, 0x00000008, 31 } +}; + +/* The following function returns an index into the above table of the + nearest prime number which is greater than N, and near a power of two. */ + +unsigned int +hash_table_higher_prime_index (unsigned long n) +{ + unsigned int low = 0; + unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]); + + while (low != high) + { + unsigned int mid = low + (high - low) / 2; + if (n > prime_tab[mid].prime) + low = mid + 1; + else + high = mid; + } + + /* If we've run out of primes, abort. */ + if (n > prime_tab[low].prime) + { + fprintf (stderr, "Cannot find prime bigger than %lu\n", n); + abort (); + } + + return low; +} + +/* Return X % Y using multiplicative inverse values INV and SHIFT. + + The multiplicative inverses computed above are for 32-bit types, + and requires that we be able to compute a highpart multiply. + + FIX: I am not at all convinced that + 3 loads, 2 multiplications, 3 shifts, and 3 additions + will be faster than + 1 load and 1 modulus + on modern systems running a compiler. */ + +#ifdef UNSIGNED_64BIT_TYPE +static inline hashval_t +mul_mod (hashval_t x, hashval_t y, hashval_t inv, int shift) +{ + __extension__ typedef UNSIGNED_64BIT_TYPE ull; + hashval_t t1, t2, t3, t4, q, r; + + t1 = ((ull)x * inv) >> 32; + t2 = x - t1; + t3 = t2 >> 1; + t4 = t1 + t3; + q = t4 >> shift; + r = x - (q * y); + + return r; +} +#endif + +/* Compute the primary table index for HASH given current prime index. */ + +hashval_t +hash_table_mod1 (hashval_t hash, unsigned int index) +{ + const struct prime_ent *p = &prime_tab[index]; +#ifdef UNSIGNED_64BIT_TYPE + if (sizeof (hashval_t) * CHAR_BIT <= 32) + return mul_mod (hash, p->prime, p->inv, p->shift); +#endif + return hash % p->prime; +} + + +/* Compute the secondary table index for HASH given current prime index. */ + +hashval_t +hash_table_mod2 (hashval_t hash, unsigned int index) +{ + const struct prime_ent *p = &prime_tab[index]; +#ifdef UNSIGNED_64BIT_TYPE + if (sizeof (hashval_t) * CHAR_BIT <= 32) + return 1 + mul_mod (hash, p->prime - 2, p->inv_m2, p->shift); +#endif + return 1 + hash % (p->prime - 2); +} |