pointer-set.h (struct pointer_set_t): Move here from pointer-set.c.

2013-06-24  Richard Biener  <rguenther@suse.de>

	* pointer-set.h (struct pointer_set_t): Move here from
	pointer-set.c.
	(pointer_set_lookup): Declare.
	(class pointer_map): New template class implementing a
	generic pointer to T map.
	(pointer_map<T>::pointer_map, pointer_map<T>::~pointer_map,
	pointer_map<T>::contains, pointer_map<T>::insert,
	pointer_map<T>::traverse): New functions.
	* pointer-set.c (struct pointer_set_t): Moved to pointer-set.h.
	(pointer_set_lookup): New function.
	(pointer_set_contains): Use pointer_set_lookup.
	(pointer_set_insert): Likewise.
	(insert_aux): Remove.
	(struct pointer_map_t): Embed a pointer_set_t.
	(pointer_map_create): Adjust.
	(pointer_map_destroy): Likewise.
	(pointer_map_contains): Likewise.
	(pointer_map_insert): Likewise.
	(pointer_map_traverse): Likewise.
	* tree-streamer.h (struct streamer_tree_cache_d): Use a
	pointer_map<unsigned> instead of a pointer_map_t.
	* tree-streamer.c (streamer_tree_cache_insert_1): Adjust.
	(streamer_tree_cache_lookup): Likewise.
	(streamer_tree_cache_create): Likewise.
	(streamer_tree_cache_delete): Likewise.
	* lto-streamer.h (struct lto_tree_ref_encoder): Use a
	pointer_map<unsigned> instead of a pointer_map_t.
	(lto_init_tree_ref_encoder): Adjust.
	(lto_destroy_tree_ref_encoder): Likewise.
	* lto-section-out.c (lto_output_decl_index): Likewise.
	(lto_record_function_out_decl_state): Likewise.
	* dominance.c (iterate_fix_dominators): Use pointer_map<int>.

From-SVN: r200367

1 files changed, 135 insertions, 7 deletions

diff --git a/gcc/pointer-set.h b/gcc/pointer-set.h
index 2d47c94..c026af7 100644
--- a/gcc/pointer-set.h
+++ b/gcc/pointer-set.h
@@ -20,23 +20,151 @@ along with GCC; see the file COPYING3.  If not see
 #ifndef POINTER_SET_H
 #define POINTER_SET_H
 
-struct pointer_set_t;
+
+/* A pointer set is represented as a simple open-addressing hash
+   table.  Simplifications: The hash code is based on the value of the
+   pointer, not what it points to.  The number of buckets is always a
+   power of 2.  Null pointers are a reserved value.  Deletion is not
+   supported (yet).  There is no mechanism for user control of hash
+   function, equality comparison, initial size, or resizing policy.  */
+
+struct pointer_set_t
+{
+  size_t log_slots;
+  size_t n_slots;		/* n_slots = 2^log_slots */
+  size_t n_elements;
+  const void **slots;
+};
+
 struct pointer_set_t *pointer_set_create (void);
 void pointer_set_destroy (struct pointer_set_t *pset);
-
 int pointer_set_contains (const struct pointer_set_t *pset, const void *p);
 int pointer_set_insert (struct pointer_set_t *pset, const void *p);
 void pointer_set_traverse (const struct pointer_set_t *,
 			   bool (*) (const void *, void *),
 			   void *);
+bool pointer_set_lookup (const pointer_set_t *, const void *, size_t *);
+
+/* A pointer map is represented the same way as a pointer_set, so
+   the hash code is based on the address of the key, rather than
+   its contents.  Null keys are a reserved value.  Deletion is not
+   supported (yet).  There is no mechanism for user control of hash
+   function, equality comparison, initial size, or resizing policy.  */
+
+template <typename T>
+class pointer_map : protected pointer_set_t
+{
+  T *values;
+
+public:
+  pointer_map ();
+  ~pointer_map ();
+  T *contains (const void *p);
+  T *insert (const void *p, bool *existed_p = NULL);
+  void traverse (bool (*fn) (const void *, T *, void *), void *data);
+};
+
+/* Allocate an empty pointer map.  */
+template <typename T>
+pointer_map<T>::pointer_map (void)
+{
+  n_elements = 0;
+  log_slots = 8;
+  n_slots = (size_t) 1 << log_slots;
+
+  slots = XCNEWVEC (const void *, n_slots);
+  values = XNEWVEC (T, n_slots);
+}
+
+/* Reclaims all memory associated with PMAP.  */
+template <typename T>
+pointer_map<T>::~pointer_map (void)
+{
+  XDELETEVEC (slots);
+  XDELETEVEC (values);
+}
+
+/* Returns a pointer to the value to which P maps, if PMAP contains P.  P
+   must be nonnull.  Return NULL if PMAP does not contain P.
+
+   Collisions are resolved by linear probing.  */
+template <typename T>
+T *
+pointer_map<T>::contains (const void *p)
+{
+  size_t n;
+  if (!pointer_set_lookup (this, p, &n))
+    return NULL;
+  return &values[n];
+}
+
+/* Inserts P into PMAP if it wasn't already there.  Returns a pointer
+   to the value.  P must be nonnull.  */
+template <typename T>
+T *
+pointer_map<T>::insert (const void *p, bool *existed_p)
+{
+  size_t n;
+
+  /* For simplicity, expand the map even if P is already there.  This can be
+     superfluous but can happen at most once.  */
+  /* ???  Fugly that we have to inline that here.  */
+  if (n_elements > n_slots / 4)
+    {
+      size_t old_n_slots = n_slots;
+      const void **old_keys = slots;
+      T *old_values = values;
+      log_slots = log_slots + 1;
+      n_slots = n_slots * 2;
+      slots = XCNEWVEC (const void *, n_slots);
+      values = XNEWVEC (T, n_slots);
+      for (size_t i = 0; i < old_n_slots; ++i)
+	if (old_keys[i])
+	  {
+	    const void *key = old_keys[i];
+	    pointer_set_lookup (this, key, &n);
+	    slots[n] = key;
+	    values[n] = old_values[i];
+	  }
+      XDELETEVEC (old_keys);
+      XDELETEVEC (old_values);
+    }
+
+  if (!pointer_set_lookup (this, p, &n))
+    {
+      ++n_elements;
+      slots[n] = p;
+      if (existed_p)
+	*existed_p = false;
+    }
+  else if (existed_p)
+    *existed_p = true;
+
+  return &values[n];
+}
+
+/* Pass each pointer in PMAP to the function in FN, together with the pointer
+   to the value and the fixed parameter DATA.  If FN returns false, the
+   iteration stops.  */
+
+template <class T>
+void
+pointer_map<T>::traverse (bool (*fn) (const void *, T *, void *), void *data)
+{
+  for (size_t i = 0; i < n_slots; ++i)
+    if (slots[i] && !fn (slots[i], &values[i], data))
+      break;
+}
+
 
 struct pointer_map_t;
-struct pointer_map_t *pointer_map_create (void);
-void pointer_map_destroy (struct pointer_map_t *pmap);
+pointer_map_t *pointer_map_create (void);
+void pointer_map_destroy (pointer_map_t *pmap);
 
-void **pointer_map_contains (const struct pointer_map_t *pmap, const void *p);
-void **pointer_map_insert (struct pointer_map_t *pmap, const void *p);
-void pointer_map_traverse (const struct pointer_map_t *,
+void **pointer_map_contains (const pointer_map_t *pmap, const void *p);
+void **pointer_map_insert (pointer_map_t *pmap, const void *p);
+void pointer_map_traverse (const pointer_map_t *,
 			   bool (*) (const void *, void **, void *), void *);
 
+
 #endif  /* POINTER_SET_H  */