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 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.  More complicated
  96    collision management schemes are only useful when the load factor
  97    significantly exceeds 0.5, and we never let that happen.  */
  98 int
  99 pointer_set_contains (struct pointer_set_t *pset, void *p)
 100 {
 101   size_t n = hash1 (p, pset->n_slots, pset->log_slots);
 102
 103   while (true)
 104     {
 105       if (pset->slots[n] == p)
 106         return 1;
 107       else if (pset->slots[n] == 0)
 108         return 0;
 109       else
 110         {
 111           ++n;
 112           if (n == pset->n_slots)
 113             n = 0;
 114         }
 115     }
 116 }
 117
 118 /* Subroutine of pointer_set_insert.  Inserts P into an empty
 119    element of SLOTS, an array of length N_SLOTS.  Returns nonzero
 120    if P was already present in N_SLOTS.  */
 121 static int
 122 insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots)
 123 {
 124   size_t n = hash1 (p, n_slots, log_slots);
 125   while (true)
 126     {
 127       if (slots[n] == p)
 128         return 1;
 129       else if (slots[n] == 0)
 130         {
 131           slots[n] = p;
 132           return 0;
 133         }
 134       else
 135         {
 136           ++n;
 137           if (n == n_slots)
 138             n = 0;
 139         }
 140     }
 141 }
 142
 143 /* Inserts P into PSET if it wasn't already there.  Returns nonzero
 144    if it was already there. P must be nonnull.  */
 145 int
 146 pointer_set_insert (struct pointer_set_t *pset, void *p)
 147 {
 148   if (insert_aux (p, pset->slots, pset->n_slots, pset->log_slots))
 149     return 1;
 150
 151   /* We've inserted a new element.  Expand the table if necessary to keep
 152      the load factor small.  */
 153   ++pset->n_elements;
 154   if (pset->n_elements > pset->n_slots / 4)
 155     {
 156       size_t new_log_slots = pset->log_slots + 1;
 157       size_t new_n_slots = pset->n_slots * 2;
 158       void **new_slots = XCNEWVEC (void *, new_n_slots);
 159       size_t i;
 160
 161       for (i = 0; i < pset->n_slots; ++i)
 162         {
 163           if (pset->slots[i])
 164             insert_aux (pset->slots[i], new_slots, new_n_slots, new_log_slots);
 165         }
 166
 167       XDELETEVEC (pset->slots);
 168       pset->n_slots = new_n_slots;
 169       pset->log_slots = new_log_slots;
 170       pset->slots = new_slots;
 171     }
 172
 173   return 0;
 174 }