Correct a function pre/postcondition [PR102403].

[thirdparty/gcc.git] / gcc / hash-table.c

diff --git a/gcc/hash-table.c b/gcc/hash-table.c
index 1cf7b234862fc5ee44844746c40f77cb0a2135a5..a1603ee017044e6696552152ed65bd64456a54e9 100644 (file)
--- a/gcc/hash-table.c
+++ b/gcc/hash-table.c
@@ -1,5 +1,5 @@
 /* A type-safe hash table template.
-   Copyright (C) 2012-2013 Free Software Foundation, Inc.
+   Copyright (C) 2012-2021 Free Software Foundation, Inc.
    Contributed by Lawrence Crowl <crowl@google.com>
 
 This file is part of GCC.
@@ -22,12 +22,15 @@ along with GCC; see the file COPYING3.  If not see
 /* This file implements a typed hash table.
    The implementation borrows from libiberty's hashtab.  */
 
+#ifdef GENERATOR_FILE
+#include "bconfig.h"
+#else
 #include "config.h"
+#endif
 #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
@@ -37,39 +40,6 @@ along with GCC; see the file COPYING3.  If not see
    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 },
@@ -104,8 +74,11 @@ struct prime_ent const prime_tab[] = {
   { 0xfffffffb, 0x00000006, 0x00000008, 31 }
 };
 
+/* Limit number of comparisons when calling hash_table<>::verify.  */
+unsigned int hash_table_sanitize_eq_limit;
+
 /* 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. */
+   nearest prime number which is at least N, and near a power of two. */
 
 unsigned int
 hash_table_higher_prime_index (unsigned long n)
@@ -123,67 +96,43 @@ hash_table_higher_prime_index (unsigned long n)
     }
 
   /* 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 ();
-    }
+  gcc_assert (n <= prime_tab[low].prime);
 
   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)
+/* Return a reference to the lazily initialized hash-table usage description.
+   This needs to be a function rather than a simple global variable so that it
+   is reliably initialized before hash table variables in other files such as
+   sem_item::m_type_hash_cache.  */
+mem_alloc_description<mem_usage>&
+hash_table_usage ()
 {
-  __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;
+  static mem_alloc_description<mem_usage> usage;
+  return usage;
 }
-#endif
-
-/* Compute the primary table index for HASH given current prime index.  */
 
-hashval_t
-hash_table_mod1 (hashval_t hash, unsigned int index)
+/* Support function for statistics.  */
+void dump_hash_table_loc_statistics (void)
 {
-  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;
-}
+  if (!GATHER_STATISTICS)
+    return;
 
+  for (unsigned i = HASH_TABLE_ORIGIN; i <= HASH_SET_ORIGIN; i++)
+    {
+      mem_alloc_origin origin = (mem_alloc_origin) i;
+      hash_table_usage ().dump (origin);
+    }
+}
 
-/* Compute the secondary table index for HASH given current prime index.  */
+/* Report a hash table checking error.  */
 
-hashval_t
-hash_table_mod2 (hashval_t hash, unsigned int index)
+ATTRIBUTE_NORETURN ATTRIBUTE_COLD
+void
+hashtab_chk_error ()
 {
-  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);
+  fprintf (stderr, "hash table checking failed: "
+          "equal operator returns true for a pair "
+          "of values with a different hash value\n");
+  gcc_unreachable ();
 }