gcc/hash-table.c

   1 /* A type-safe hash table template.
   2    Copyright (C) 2012-2019 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 /* Table of primes and multiplicative inverses.
  35
  36    Note that these are not minimally reduced inverses.  Unlike when generating
  37    code to divide by a constant, we want to be able to use the same algorithm
  38    all the time.  All of these inverses (are implied to) have bit 32 set.
  39
  40    For the record, here's the function that computed the table; it's a
  41    vastly simplified version of the function of the same name from gcc.  */
  42
  43 struct prime_ent const prime_tab[] = {
  44   {          7, 0x24924925, 0x9999999b, 2 },
  45   {         13, 0x3b13b13c, 0x745d1747, 3 },
  46   {         31, 0x08421085, 0x1a7b9612, 4 },
  47   {         61, 0x0c9714fc, 0x15b1e5f8, 5 },
  48   {        127, 0x02040811, 0x0624dd30, 6 },
  49   {        251, 0x05197f7e, 0x073260a5, 7 },
  50   {        509, 0x01824366, 0x02864fc8, 8 },
  51   {       1021, 0x00c0906d, 0x014191f7, 9 },
  52   {       2039, 0x0121456f, 0x0161e69e, 10 },
  53   {       4093, 0x00300902, 0x00501908, 11 },
  54   {       8191, 0x00080041, 0x00180241, 12 },
  55   {      16381, 0x000c0091, 0x00140191, 13 },
  56   {      32749, 0x002605a5, 0x002a06e6, 14 },
  57   {      65521, 0x000f00e2, 0x00110122, 15 },
  58   {     131071, 0x00008001, 0x00018003, 16 },
  59   {     262139, 0x00014002, 0x0001c004, 17 },
  60   {     524287, 0x00002001, 0x00006001, 18 },
  61   {    1048573, 0x00003001, 0x00005001, 19 },
  62   {    2097143, 0x00004801, 0x00005801, 20 },
  63   {    4194301, 0x00000c01, 0x00001401, 21 },
  64   {    8388593, 0x00001e01, 0x00002201, 22 },
  65   {   16777213, 0x00000301, 0x00000501, 23 },
  66   {   33554393, 0x00001381, 0x00001481, 24 },
  67   {   67108859, 0x00000141, 0x000001c1, 25 },
  68   {  134217689, 0x000004e1, 0x00000521, 26 },
  69   {  268435399, 0x00000391, 0x000003b1, 27 },
  70   {  536870909, 0x00000019, 0x00000029, 28 },
  71   { 1073741789, 0x0000008d, 0x00000095, 29 },
  72   { 2147483647, 0x00000003, 0x00000007, 30 },
  73   /* Avoid "decimal constant so large it is unsigned" for 4294967291.  */
  74   { 0xfffffffb, 0x00000006, 0x00000008, 31 }
  75 };
  76
  77 /* Limit number of comparisons when calling hash_table<>::verify.  */
  78 unsigned int hash_table_sanitize_eq_limit;
  79
  80 /* The following function returns an index into the above table of the
  81    nearest prime number which is at least N, and near a power of two. */
  82
  83 unsigned int
  84 hash_table_higher_prime_index (unsigned long n)
  85 {
  86   unsigned int low = 0;
  87   unsigned int high = sizeof (prime_tab) / sizeof (prime_tab[0]);
  88
  89   while (low != high)
  90     {
  91       unsigned int mid = low + (high - low) / 2;
  92       if (n > prime_tab[mid].prime)
  93         low = mid + 1;
  94       else
  95         high = mid;
  96     }
  97
  98   /* If we've run out of primes, abort.  */
  99   gcc_assert (n <= prime_tab[low].prime);
 100
 101   return low;
 102 }
 103
 104 /* Return a reference to the lazily initialized hash-table usage description.
 105    This needs to be a function rather than a simple global variable so that it
 106    is reliably initialized before hash table variables in other files such as
 107    sem_item::m_type_hash_cache.  */
 108 mem_alloc_description<mem_usage>&
 109 hash_table_usage ()
 110 {
 111   static mem_alloc_description<mem_usage> usage;
 112   return usage;
 113 }
 114
 115 /* Support function for statistics.  */
 116 void dump_hash_table_loc_statistics (void)
 117 {
 118   if (!GATHER_STATISTICS)
 119     return;
 120
 121   for (unsigned i = HASH_TABLE_ORIGIN; i <= HASH_SET_ORIGIN; i++)
 122     {
 123       mem_alloc_origin origin = (mem_alloc_origin) i;
 124       hash_table_usage ().dump (origin);
 125     }
 126 }
 127
 128 /* Report a hash table checking error.  */
 129
 130 ATTRIBUTE_NORETURN ATTRIBUTE_COLD
 131 void
 132 hashtab_chk_error ()
 133 {
 134   fprintf (stderr, "hash table checking failed: "
 135            "equal operator returns true for a pair "
 136            "of values with a different hash value\n");
 137   gcc_unreachable ();
 138 }