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, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, 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 double M = (ULONG_MAX + 1.0);
  65   const double B = M / ((sqrt (5) - 1) / 2.0);
  66   const unsigned long A = B - (floor (B / M) * M);
  67 #endif
  68   const unsigned long shift = sizeof (unsigned long) * CHAR_BIT - logmax;
  69
  70   return ((A * (unsigned long) p) >> shift) & (max - 1);
  71 }
  72
  73 /* Allocate an empty pointer set. */
  74 struct pointer_set_t *
  75 pointer_set_create (void)
  76 {
  77   struct pointer_set_t *result = XNEW (struct pointer_set_t);
  78
  79   result->n_elements = 0;
  80   result->log_slots = 8;
  81   result->n_slots = (size_t) 1 << result->log_slots;
  82
  83   result->slots = XCNEWVEC (void *, result->n_slots);
  84   return result;
  85 }
  86
  87 /* Reclaims all memory associated with PSET. */
  88 void pointer_set_destroy (struct pointer_set_t *pset)
  89 {
  90   XDELETEVEC (pset->slots);
  91   XDELETE (pset);
  92 }
  93
  94 /* Returns nonzero if PSET contains P.  P must be nonnull.
  95
  96    Collisions are resolved by linear probing.  More complicated
  97    collision management schemes are only useful when the load factor
  98    significantly exceeds 0.5, and we never let that happen. */
  99 int
 100 pointer_set_contains (struct pointer_set_t *pset, void *p)
 101 {
 102   size_t n = hash1 (p, pset->n_slots, pset->log_slots);
 103
 104   while (true)
 105     {
 106       if (pset->slots[n] == p)
 107         return 1;
 108       else if (pset->slots[n] == 0)
 109         return 0;
 110       else
 111         {
 112           ++n;
 113           if (n == pset->n_slots)
 114             n = 0;
 115         }
 116     }
 117 }
 118
 119 /* Subroutine of pointer_set_insert.  Inserts P into an empty
 120    element of SLOTS, an array of length N_SLOTS.  Returns nonzero
 121    if P was already present in N_SLOTS. */
 122 static int
 123 insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots)
 124 {
 125   size_t n = hash1 (p, n_slots, log_slots);
 126   while (true)
 127     {
 128       if (slots[n] == p)
 129         return 1;
 130       else if (slots[n] == 0)
 131         {
 132           slots[n] = p;
 133           return 0;
 134         }
 135       else
 136         {
 137           ++n;
 138           if (n == n_slots)
 139             n = 0;
 140         }
 141     }
 142 }
 143
 144 /* Inserts P into PSET if it wasn't already there.  Returns nonzero
 145    if it was already there. P must be nonnull. */
 146 int
 147 pointer_set_insert (struct pointer_set_t *pset, void *p)
 148 {
 149   if (insert_aux (p, pset->slots, pset->n_slots, pset->log_slots))
 150     return 1;
 151
 152   /* We've inserted a new element.  Expand the table if necessary to keep
 153      the load factor small. */
 154   ++pset->n_elements;
 155   if (pset->n_elements > pset->n_slots / 4)
 156     {
 157       size_t new_log_slots = pset->log_slots + 1;
 158       size_t new_n_slots = pset->n_slots * 2;
 159       void **new_slots = XCNEWVEC (void *, new_n_slots);
 160       size_t i;
 161
 162       for (i = 0; i < pset->n_slots; ++i)
 163         {
 164           if (pset->slots[i])
 165             insert_aux (pset->slots[i], new_slots, new_n_slots, new_log_slots);
 166         }
 167
 168       XDELETEVEC (pset->slots);
 169       pset->n_slots = new_n_slots;
 170       pset->log_slots = new_log_slots;
 171       pset->slots = new_slots;
 172     }
 173
 174   return 0;
 175 }