gcc/hash-table.c

   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 }