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