gcc/pointer-set.h

   1 /* Set operations on pointers
   2    Copyright (C) 2004-2014 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 it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 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 #ifndef POINTER_SET_H
  21 #define POINTER_SET_H
  22
  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   const void **slots;
  37 };
  38
  39 struct pointer_set_t *pointer_set_create (void);
  40 void pointer_set_destroy (struct pointer_set_t *pset);
  41 int pointer_set_contains (const struct pointer_set_t *pset, const void *p);
  42 int pointer_set_insert (struct pointer_set_t *pset, const void *p);
  43 void pointer_set_traverse (const struct pointer_set_t *,
  44                            bool (*) (const void *, void *),
  45                            void *);
  46 bool pointer_set_lookup (const pointer_set_t *, const void *, size_t *);
  47
  48 /* A pointer map is represented the same way as a pointer_set, so
  49    the hash code is based on the address of the key, rather than
  50    its contents.  Null keys are a reserved value.  Deletion is not
  51    supported (yet).  There is no mechanism for user control of hash
  52    function, equality comparison, initial size, or resizing policy.  */
  53
  54 template <typename T>
  55 class pointer_map : protected pointer_set_t
  56 {
  57   T *values;
  58
  59 public:
  60   pointer_map ();
  61   ~pointer_map ();
  62   T *contains (const void *p);
  63   T *insert (const void *p, bool *existed_p = NULL);
  64   void traverse (bool (*fn) (const void *, T *, void *), void *data);
  65 };
  66
  67 /* Allocate an empty pointer map.  */
  68 template <typename T>
  69 pointer_map<T>::pointer_map (void)
  70 {
  71   n_elements = 0;
  72   log_slots = 8;
  73   n_slots = (size_t) 1 << log_slots;
  74
  75   slots = XCNEWVEC (const void *, n_slots);
  76   values = XNEWVEC (T, n_slots);
  77 }
  78
  79 /* Reclaims all memory associated with PMAP.  */
  80 template <typename T>
  81 pointer_map<T>::~pointer_map (void)
  82 {
  83   XDELETEVEC (slots);
  84   XDELETEVEC (values);
  85 }
  86
  87 /* Returns a pointer to the value to which P maps, if PMAP contains P.  P
  88    must be nonnull.  Return NULL if PMAP does not contain P.
  89
  90    Collisions are resolved by linear probing.  */
  91 template <typename T>
  92 T *
  93 pointer_map<T>::contains (const void *p)
  94 {
  95   size_t n;
  96   if (!pointer_set_lookup (this, p, &n))
  97     return NULL;
  98   return &values[n];
  99 }
 100
 101 /* Inserts P into PMAP if it wasn't already there.  Returns a pointer
 102    to the value.  P must be nonnull.  */
 103 template <typename T>
 104 T *
 105 pointer_map<T>::insert (const void *p, bool *existed_p)
 106 {
 107   size_t n;
 108
 109   /* For simplicity, expand the map even if P is already there.  This can be
 110      superfluous but can happen at most once.  */
 111   /* ???  Fugly that we have to inline that here.  */
 112   if (n_elements > n_slots / 4)
 113     {
 114       size_t old_n_slots = n_slots;
 115       const void **old_keys = slots;
 116       T *old_values = values;
 117       log_slots = log_slots + 1;
 118       n_slots = n_slots * 2;
 119       slots = XCNEWVEC (const void *, n_slots);
 120       values = XNEWVEC (T, n_slots);
 121       for (size_t i = 0; i < old_n_slots; ++i)
 122         if (old_keys[i])
 123           {
 124             const void *key = old_keys[i];
 125             pointer_set_lookup (this, key, &n);
 126             slots[n] = key;
 127             values[n] = old_values[i];
 128           }
 129       XDELETEVEC (old_keys);
 130       XDELETEVEC (old_values);
 131     }
 132
 133   if (!pointer_set_lookup (this, p, &n))
 134     {
 135       ++n_elements;
 136       slots[n] = p;
 137       if (existed_p)
 138         *existed_p = false;
 139     }
 140   else if (existed_p)
 141     *existed_p = true;
 142
 143   return &values[n];
 144 }
 145
 146 /* Pass each pointer in PMAP to the function in FN, together with the pointer
 147    to the value and the fixed parameter DATA.  If FN returns false, the
 148    iteration stops.  */
 149
 150 template <class T>
 151 void
 152 pointer_map<T>::traverse (bool (*fn) (const void *, T *, void *), void *data)
 153 {
 154   for (size_t i = 0; i < n_slots; ++i)
 155     if (slots[i] && !fn (slots[i], &values[i], data))
 156       break;
 157 }
 158
 159
 160 struct pointer_map_t;
 161 pointer_map_t *pointer_map_create (void);
 162 void pointer_map_destroy (pointer_map_t *pmap);
 163
 164 void **pointer_map_contains (const pointer_map_t *pmap, const void *p);
 165 void **pointer_map_insert (pointer_map_t *pmap, const void *p);
 166 void pointer_map_traverse (const pointer_map_t *,
 167                            bool (*) (const void *, void **, void *), void *);
 168
 169
 170 #endif  /* POINTER_SET_H  */