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