gcc/pointer-set.c

   1 /* Set operations on pointers
   2    Copyright (C) 2004 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  19 Boston, MA 02110-1301, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "pointer-set.h"
  24
  25 /* A pointer sets is represented as a simple open-addressing hash
  26    table.  Simplifications: The hash code is based on the value of the
  27    pointer, not what it points to.  The number of buckets is always a
  28    power of 2.  Null pointers are a reserved value.  Deletion is not
  29    supported.  There is no mechanism for user control of hash
  30    function, equality comparison, initial size, or resizing policy.
  31 */
  32
  33 struct pointer_set_t
  34 {
  35   size_t log_slots;
  36   size_t n_slots;               /* n_slots = 2^log_slots */
  37   size_t n_elements;
  38
  39   void **slots;
  40 };
  41
  42 /* Use the multiplicative method, as described in Knuth 6.4, to obtain
  43    a hash code for P in the range [0, MAX).  MAX == 2^LOGMAX.
  44
  45    Summary of this method: Multiply p by some number A that's
  46    relatively prime to 2^sizeof(size_t).  The result is two words.
  47    Discard the most significant word, and return the most significant
  48    N bits of the least significant word.  As suggested by Knuth, our
  49    choice for A is the integer part of (ULONG_MAX + 1.0) / phi, where phi
  50    is the golden ratio.
  51
  52    We don't need to do anything special for full-width multiplication
  53    because we're only interested in the least significant word of the
  54    product, and unsigned arithmetic in C is modulo the word size.  */
  55
  56 static inline size_t
  57 hash1 (const void *p, unsigned long max, unsigned long logmax)
  58 {
  59 #if HOST_BITS_PER_LONG == 32
  60   const unsigned long A = 0x9e3779b9u;
  61 #elif HOST_BITS_PER_LONG == 64
  62   const unsigned long A = 0x9e3779b97f4a7c16ul;
  63 #else
  64   const unsigned long A
  65     = (ULONG_MAX + 1.0L) * 0.6180339887498948482045868343656381177203L;
  66 #endif
  67   const unsigned long shift = HOST_BITS_PER_LONG - logmax;
  68
  69   return ((A * (unsigned long) p) >> shift) & (max - 1);
  70 }
  71
  72 /* Allocate an empty pointer set.  */
  73 struct pointer_set_t *
  74 pointer_set_create (void)
  75 {
  76   struct pointer_set_t *result = XNEW (struct pointer_set_t);
  77
  78   result->n_elements = 0;
  79   result->log_slots = 8;
  80   result->n_slots = (size_t) 1 << result->log_slots;
  81
  82   result->slots = XCNEWVEC (void *, result->n_slots);
  83   return result;
  84 }
  85
  86 /* Reclaims all memory associated with PSET.  */
  87 void pointer_set_destroy (struct pointer_set_t *pset)
  88 {
  89   XDELETEVEC (pset->slots);
  90   XDELETE (pset);
  91 }
  92
  93 /* Returns nonzero if PSET contains P.  P must be nonnull.
  94
  95    Collisions are resolved by linear probing.  */
  96 int
  97 pointer_set_contains (struct pointer_set_t *pset, void *p)
  98 {
  99   size_t n = hash1 (p, pset->n_slots, pset->log_slots);
 100
 101   while (true)
 102     {
 103       if (pset->slots[n] == p)
 104        return 1;
 105       else if (pset->slots[n] == 0)
 106        return 0;
 107       else
 108        {
 109          ++n;
 110          if (n == pset->n_slots)
 111            n = 0;
 112        }
 113     }
 114 }
 115
 116 /* Subroutine of pointer_set_insert.  Inserts P into an empty
 117    element of SLOTS, an array of length N_SLOTS.  Returns nonzero
 118    if P was already present in N_SLOTS.  */
 119 static int
 120 insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots)
 121 {
 122   size_t n = hash1 (p, n_slots, log_slots);
 123   while (true)
 124     {
 125       if (slots[n] == p)
 126         return 1;
 127       else if (slots[n] == 0)
 128         {
 129           slots[n] = p;
 130           return 0;
 131         }
 132       else
 133         {
 134           ++n;
 135           if (n == n_slots)
 136             n = 0;
 137         }
 138     }
 139 }
 140
 141 /* Inserts P into PSET if it wasn't already there.  Returns nonzero
 142    if it was already there. P must be nonnull.  */
 143 int
 144 pointer_set_insert (struct pointer_set_t *pset, void *p)
 145 {
 146   if (insert_aux (p, pset->slots, pset->n_slots, pset->log_slots))
 147     return 1;
 148
 149   /* We've inserted a new element.  Expand the table if necessary to keep
 150      the load factor small.  */
 151   ++pset->n_elements;
 152   if (pset->n_elements > pset->n_slots / 4)
 153     {
 154       size_t new_log_slots = pset->log_slots + 1;
 155       size_t new_n_slots = pset->n_slots * 2;
 156       void **new_slots = XCNEWVEC (void *, new_n_slots);
 157       size_t i;
 158
 159       for (i = 0; i < pset->n_slots; ++i)
 160         {
 161           if (pset->slots[i])
 162             insert_aux (pset->slots[i], new_slots, new_n_slots, new_log_slots);
 163         }
 164
 165       XDELETEVEC (pset->slots);
 166       pset->n_slots = new_n_slots;
 167       pset->log_slots = new_log_slots;
 168       pset->slots = new_slots;
 169     }
 170
 171   return 0;
 172 }