gcc/hash-table.c

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