gcc/hash-table.c

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