gcc/pointer-set.c

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