gcc/pointer-set.c

   1 /* Set operations on pointers
   2    Copyright (C) 2004, 2006 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 set 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 (yet).  There is no mechanism for user control of hash
  30    function, equality comparison, initial size, or resizing policy.  */
  31
  32 struct pointer_set_t
  33 {
  34   size_t log_slots;
  35   size_t n_slots;               /* n_slots = 2^log_slots */
  36   size_t n_elements;
  37
  38   void **slots;
  39 };
  40
  41 /* Use the multiplicative method, as described in Knuth 6.4, to obtain
  42    a hash code for P in the range [0, MAX).  MAX == 2^LOGMAX.
  43
  44    Summary of this method: Multiply p by some number A that's
  45    relatively prime to 2^sizeof(size_t).  The result is two words.
  46    Discard the most significant word, and return the most significant
  47    N bits of the least significant word.  As suggested by Knuth, our
  48    choice for A is the integer part of (ULONG_MAX + 1.0) / phi, where phi
  49    is the golden ratio.
  50
  51    We don't need to do anything special for full-width multiplication
  52    because we're only interested in the least significant word of the
  53    product, and unsigned arithmetic in C is modulo the word size.  */
  54
  55 static inline size_t
  56 hash1 (const void *p, unsigned long max, unsigned long logmax)
  57 {
  58 #if HOST_BITS_PER_LONG == 32
  59   const unsigned long A = 0x9e3779b9u;
  60 #elif HOST_BITS_PER_LONG == 64
  61   const unsigned long A = 0x9e3779b97f4a7c16ul;
  62 #else
  63   const unsigned long A
  64     = (ULONG_MAX + 1.0L) * 0.6180339887498948482045868343656381177203L;
  65 #endif
  66   const unsigned long shift = HOST_BITS_PER_LONG - logmax;
  67
  68   return ((A * (unsigned long) p) >> shift) & (max - 1);
  69 }
  70
  71 /* Allocate an empty pointer set.  */
  72 struct pointer_set_t *
  73 pointer_set_create (void)
  74 {
  75   struct pointer_set_t *result = XNEW (struct pointer_set_t);
  76
  77   result->n_elements = 0;
  78   result->log_slots = 8;
  79   result->n_slots = (size_t) 1 << result->log_slots;
  80
  81   result->slots = XCNEWVEC (void *, result->n_slots);
  82   return result;
  83 }
  84
  85 /* Reclaims all memory associated with PSET.  */
  86 void
  87 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.  Return the insertion slot for P into
 117    an empty element of SLOTS, an array of length N_SLOTS.  */
 118 static inline size_t
 119 insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots)
 120 {
 121   size_t n = hash1 (p, n_slots, log_slots);
 122   while (true)
 123     {
 124       if (slots[n] == p || slots[n] == 0)
 125         return n;
 126       else
 127         {
 128           ++n;
 129           if (n == n_slots)
 130             n = 0;
 131         }
 132     }
 133 }
 134
 135 /* Inserts P into PSET if it wasn't already there.  Returns nonzero
 136    if it was already there. P must be nonnull.  */
 137 int
 138 pointer_set_insert (struct pointer_set_t *pset, void *p)
 139 {
 140   size_t n;
 141
 142   /* For simplicity, expand the set even if P is already there.  This can be
 143      superfluous but can happen at most once.  */
 144   if (pset->n_elements > pset->n_slots / 4)
 145     {
 146       size_t new_log_slots = pset->log_slots + 1;
 147       size_t new_n_slots = pset->n_slots * 2;
 148       void **new_slots = XCNEWVEC (void *, new_n_slots);
 149       size_t i;
 150
 151       for (i = 0; i < pset->n_slots; ++i)
 152         {
 153           void *value = pset->slots[i];
 154           n = insert_aux (value, new_slots, new_n_slots, new_log_slots);
 155           new_slots[n] = value;
 156         }
 157
 158       XDELETEVEC (pset->slots);
 159       pset->n_slots = new_n_slots;
 160       pset->log_slots = new_log_slots;
 161       pset->slots = new_slots;
 162     }
 163
 164   n = insert_aux (p, pset->slots, pset->n_slots, pset->log_slots);
 165   if (pset->slots[n])
 166     return 1;
 167
 168   pset->slots[n] = p;
 169   ++pset->n_elements;
 170   return 0;
 171 }
 172
 173 /* Pass each pointer in PSET to the function in FN, together with the fixed
 174    parameter DATA.  If FN returns false, the iteration stops.  */
 175
 176 void pointer_set_traverse (struct pointer_set_t *pset,
 177                            bool (*fn) (void *, void *), void *data)
 178 {
 179   size_t i;
 180   for (i = 0; i < pset->n_slots; ++i)
 181     if (pset->slots[i] && !fn (pset->slots[i], data))
 182       break;
 183 }
 184
 185 \f
 186 /* A pointer map is represented the same way as a pointer_set, so
 187    the hash code is based on the address of the key, rather than
 188    its contents.  Null keys are a reserved value.  Deletion is not
 189    supported (yet).  There is no mechanism for user control of hash
 190    function, equality comparison, initial size, or resizing policy.  */
 191
 192 struct pointer_map_t
 193 {
 194   size_t log_slots;
 195   size_t n_slots;               /* n_slots = 2^log_slots */
 196   size_t n_elements;
 197
 198   void **keys;
 199   void **values;
 200 };
 201
 202 /* Allocate an empty pointer map.  */
 203 struct pointer_map_t *
 204 pointer_map_create (void)
 205 {
 206   struct pointer_map_t *result = XNEW (struct pointer_map_t);
 207
 208   result->n_elements = 0;
 209   result->log_slots = 8;
 210   result->n_slots = (size_t) 1 << result->log_slots;
 211
 212   result->keys = XCNEWVEC (void *, result->n_slots);
 213   result->values = XCNEWVEC (void *, result->n_slots);
 214   return result;
 215 }
 216
 217 /* Reclaims all memory associated with PMAP.  */
 218 void pointer_map_destroy (struct pointer_map_t *pmap)
 219 {
 220   XDELETEVEC (pmap->keys);
 221   XDELETEVEC (pmap->values);
 222   XDELETE (pmap);
 223 }
 224
 225 /* Returns a pointer to the value to which P maps, if PMAP contains P.  P
 226    must be nonnull.  Return NULL if PMAP does not contain P.
 227
 228    Collisions are resolved by linear probing.  */
 229 void **
 230 pointer_map_contains (struct pointer_map_t *pmap, void *p)
 231 {
 232   size_t n = hash1 (p, pmap->n_slots, pmap->log_slots);
 233
 234   while (true)
 235     {
 236       if (pmap->keys[n] == p)
 237         return &pmap->values[n];
 238       else if (pmap->keys[n] == 0)
 239         return NULL;
 240       else
 241        {
 242          ++n;
 243          if (n == pmap->n_slots)
 244            n = 0;
 245        }
 246     }
 247 }
 248
 249 /* Inserts P into PMAP if it wasn't already there.  Returns a pointer
 250    to the value.  P must be nonnull.  */
 251 void **
 252 pointer_map_insert (struct pointer_map_t *pmap, void *p)
 253 {
 254   size_t n;
 255
 256   /* For simplicity, expand the map even if P is already there.  This can be
 257      superfluous but can happen at most once.  */
 258   if (pmap->n_elements > pmap->n_slots / 4)
 259     {
 260       size_t new_log_slots = pmap->log_slots + 1;
 261       size_t new_n_slots = pmap->n_slots * 2;
 262       void **new_keys = XCNEWVEC (void *, new_n_slots);
 263       void **new_values = XCNEWVEC (void *, new_n_slots);
 264       size_t i;
 265
 266       for (i = 0; i < pmap->n_slots; ++i)
 267         if (pmap->keys[i])
 268           {
 269             void *key = pmap->keys[i];
 270             n = insert_aux (key, new_keys, new_n_slots, new_log_slots);
 271             new_keys[n] = key;
 272             new_values[n] = pmap->values[i];
 273           }
 274
 275       XDELETEVEC (pmap->keys);
 276       XDELETEVEC (pmap->values);
 277       pmap->n_slots = new_n_slots;
 278       pmap->log_slots = new_log_slots;
 279       pmap->keys = new_keys;
 280       pmap->values = new_values;
 281     }
 282
 283   n = insert_aux (p, pmap->keys, pmap->n_slots, pmap->log_slots);
 284   if (!pmap->keys[n])
 285     {
 286       ++pmap->n_elements;
 287       pmap->keys[n] = p;
 288     }
 289
 290   return &pmap->values[n];
 291 }
 292
 293 /* Pass each pointer in PMAP to the function in FN, together with the pointer
 294    to the value and the fixed parameter DATA.  If FN returns false, the
 295    iteration stops.  */
 296
 297 void pointer_map_traverse (struct pointer_map_t *pmap,
 298                            bool (*fn) (void *, void **, void *), void *data)
 299 {
 300   size_t i;
 301   for (i = 0; i < pmap->n_slots; ++i)
 302     if (pmap->keys[i] && !fn (pmap->keys[i], &pmap->values[i], data))
 303       break;
 304 }