[PATCH] Provide a pointer_map<T> template

[Richard Biener <rguenther at suse dot de>]

This templates the pointer-map implementation (actually it copies
the implementation, leaving the old interface unchanged) providing
a templated value type.  That's suitable to replace the various
users requesting a pointer-to-integer-type map, like I noticed
for the two LTO tree recording mechanisms.  Which in turn saves
memory on 64bit hosts (and should be less heavy-weight on the cache).
Not very much, but a quarter of the old pointer-map memory usage.

LTO bootstrap and regtest running on x86_64-unknown-linux-gnu.

In theory we can typedef pointer_map<void *> pointer_map_t, but
that requires touching all pointer_map_t users to drop the
leading 'struct' and eventually include pointer-set.h.

I changed the insert () interface to get another output as to
whether the slot was present to avoid the need to have a special
"not present" value.  That also makes it unnecessary to zero
the values array.

Any comments?

If not then I'll comb over existing pointer -> integer type map
users and convert them.

Thanks,
Richard.


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

	* pointer-set.h (struct pointer_map_base): New struct.
	(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 (pointer_map_base::lookup): New function.
	* 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.

Index: gcc/pointer-set.c
===================================================================
*** gcc/pointer-set.c	(revision 200189)
--- gcc/pointer-set.c	(working copy)
*************** void pointer_map_traverse (const struct
*** 301,303 ****
--- 301,335 ----
      if (pmap->keys[i] && !fn (pmap->keys[i], &pmap->values[i], data))
        break;
  }
+ 
+ 
+ 
+ /* Lookup the slot for the pointer P and return true if it exists,
+    otherwise return false in which case *IX points to the slot that
+    would be used on insertion.  */
+ 
+ bool
+ pointer_map_base::lookup (const void *p, size_t *ix)
+ {
+   size_t n = hash1 (p, n_slots, log_slots);
+ 
+   while (true)
+     {
+       if (keys[n] == p)
+ 	{
+ 	  *ix = n;
+ 	  return true;
+ 	}
+       else if (keys[n] == 0)
+ 	{
+ 	  *ix = n;
+ 	  return false;
+ 	}
+       else
+        {
+          ++n;
+          if (n == n_slots)
+            n = 0;
+        }
+     }
+ }
Index: gcc/pointer-set.h
===================================================================
*** gcc/pointer-set.h	(revision 200189)
--- gcc/pointer-set.h	(working copy)
*************** void pointer_set_traverse (const struct
*** 30,42 ****
  			   bool (*) (const void *, void *),
  			   void *);
  
  struct pointer_map_t;
! struct pointer_map_t *pointer_map_create (void);
! void pointer_map_destroy (struct 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 *,
  			   bool (*) (const void *, void **, void *), void *);
  
  #endif  /* POINTER_SET_H  */
--- 30,166 ----
  			   bool (*) (const void *, void *),
  			   void *);
  
+ 
+ struct pointer_map_base
+ {
+   size_t log_slots;
+   size_t n_slots;		/* n_slots = 2^log_slots */
+   size_t n_elements;
+   const void **keys;
+ 
+   bool lookup (const void *p, size_t *n);
+ };
+ 
+ /* 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_map_base
+ {
+   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;
+ 
+   keys = XCNEWVEC (const void *, n_slots);
+   values = XCNEWVEC (T, n_slots);
+ }
+ 
+ /* Reclaims all memory associated with PMAP.  */
+ template <typename T>
+ pointer_map<T>::~pointer_map (void)
+ {
+   XDELETEVEC (keys);
+   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 (!lookup (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 = keys;
+       T *old_values = values;
+       log_slots = log_slots + 1;
+       n_slots = n_slots * 2;
+       keys = XCNEWVEC (const void *, n_slots);
+       values = XCNEWVEC (T, n_slots);
+       for (size_t i = 0; i < old_n_slots; ++i)
+ 	if (old_keys[i])
+ 	  {
+ 	    const void *key = old_keys[i];
+ 	    lookup (key, &n);
+ 	    keys[n] = key;
+ 	    values[n] = old_values[i];
+ 	  }
+       XDELETEVEC (old_keys);
+       XDELETEVEC (old_values);
+     }
+ 
+   if (!lookup (p, &n))
+     {
+       ++n_elements;
+       keys[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 (keys[i] && !fn (keys[i], &values[i], data))
+       break;
+ }
+ 
+ 
  struct pointer_map_t;
! pointer_map_t *pointer_map_create (void);
! void pointer_map_destroy (pointer_map_t *pmap);
  
! 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  */
Index: gcc/tree-streamer.c
===================================================================
*** gcc/tree-streamer.c	(revision 200189)
--- gcc/tree-streamer.c	(working copy)
*************** streamer_tree_cache_insert_1 (struct str
*** 128,157 ****
  			      tree t, hashval_t hash, unsigned *ix_p,
  			      bool insert_at_next_slot_p)
  {
!   void **slot;
    unsigned ix;
    bool existed_p;
  
    gcc_assert (t);
  
!   slot = pointer_map_insert (cache->node_map, t);
!   if (!*slot)
      {
        /* Determine the next slot to use in the cache.  */
        if (insert_at_next_slot_p)
  	ix = cache->nodes.length ();
        else
  	ix = *ix_p;
!        *slot = (void *)(size_t) (ix + 1);
  
        streamer_tree_cache_add_to_node_array (cache, ix, t, hash);
- 
-       /* Indicate that the item was not present in the cache.  */
-       existed_p = false;
      }
    else
      {
!       ix = (size_t) *slot - 1;
  
        if (!insert_at_next_slot_p && ix != *ix_p)
  	{
--- 128,154 ----
  			      tree t, hashval_t hash, unsigned *ix_p,
  			      bool insert_at_next_slot_p)
  {
!   unsigned *slot;
    unsigned ix;
    bool existed_p;
  
    gcc_assert (t);
  
!   slot = cache->node_map->insert (t, &existed_p);
!   if (!existed_p)
      {
        /* Determine the next slot to use in the cache.  */
        if (insert_at_next_slot_p)
  	ix = cache->nodes.length ();
        else
  	ix = *ix_p;
!        *slot = ix;
  
        streamer_tree_cache_add_to_node_array (cache, ix, t, hash);
      }
    else
      {
!       ix = *slot;
  
        if (!insert_at_next_slot_p && ix != *ix_p)
  	{
*************** streamer_tree_cache_insert_1 (struct str
*** 160,170 ****
  	     the requested location slot.  */
  	  ix = *ix_p;
  	  streamer_tree_cache_add_to_node_array (cache, ix, t, hash);
! 	  *slot = (void *)(size_t) (ix + 1);
  	}
- 
-       /* Indicate that T was already in the cache.  */
-       existed_p = true;
      }
  
    if (ix_p)
--- 157,164 ----
  	     the requested location slot.  */
  	  ix = *ix_p;
  	  streamer_tree_cache_add_to_node_array (cache, ix, t, hash);
! 	  *slot = ix;
  	}
      }
  
    if (ix_p)
*************** bool
*** 225,237 ****
  streamer_tree_cache_lookup (struct streamer_tree_cache_d *cache, tree t,
  			    unsigned *ix_p)
  {
!   void **slot;
    bool retval;
    unsigned ix;
  
    gcc_assert (t);
  
!   slot = pointer_map_contains  (cache->node_map, t);
    if (slot == NULL)
      {
        retval = false;
--- 219,231 ----
  streamer_tree_cache_lookup (struct streamer_tree_cache_d *cache, tree t,
  			    unsigned *ix_p)
  {
!   unsigned *slot;
    bool retval;
    unsigned ix;
  
    gcc_assert (t);
  
!   slot = cache->node_map->contains (t);
    if (slot == NULL)
      {
        retval = false;
*************** streamer_tree_cache_lookup (struct strea
*** 240,246 ****
    else
      {
        retval = true;
!       ix = (size_t) *slot - 1;
      }
  
    if (ix_p)
--- 234,240 ----
    else
      {
        retval = true;
!       ix = *slot;
      }
  
    if (ix_p)
*************** streamer_tree_cache_create (bool with_ha
*** 332,338 ****
    cache = XCNEW (struct streamer_tree_cache_d);
  
    if (with_map)
!     cache->node_map = pointer_map_create ();
    cache->nodes.create (165);
    if (with_hashes)
      cache->hashes.create (165);
--- 326,332 ----
    cache = XCNEW (struct streamer_tree_cache_d);
  
    if (with_map)
!     cache->node_map = new pointer_map<unsigned>;
    cache->nodes.create (165);
    if (with_hashes)
      cache->hashes.create (165);
*************** streamer_tree_cache_delete (struct strea
*** 355,361 ****
      return;
  
    if (c->node_map)
!     pointer_map_destroy (c->node_map);
    c->nodes.release ();
    c->hashes.release ();
    free (c);
--- 349,355 ----
      return;
  
    if (c->node_map)
!     delete c->node_map;
    c->nodes.release ();
    c->hashes.release ();
    free (c);
Index: gcc/tree-streamer.h
===================================================================
*** gcc/tree-streamer.h	(revision 200189)
--- gcc/tree-streamer.h	(working copy)
*************** along with GCC; see the file COPYING3.
*** 47,53 ****
  struct streamer_tree_cache_d
  {
    /* The mapping between tree nodes and slots into the nodes array.  */
!   struct pointer_map_t *node_map;
  
    /* The nodes pickled so far.  */
    vec<tree> nodes;
--- 47,53 ----
  struct streamer_tree_cache_d
  {
    /* The mapping between tree nodes and slots into the nodes array.  */
!   pointer_map<unsigned> *node_map;
  
    /* The nodes pickled so far.  */
    vec<tree> nodes;
Index: gcc/lto-streamer.h
===================================================================
*** gcc/lto-streamer.h	(revision 200189)
--- gcc/lto-streamer.h	(working copy)
*************** struct GTY(()) lto_tree_ref_table
*** 479,485 ****
  
  struct lto_tree_ref_encoder
  {
!   pointer_map_t *tree_hash_table;	/* Maps pointers to indices. */
    vec<tree> trees;			/* Maps indices to pointers. */
  };
  
--- 479,485 ----
  
  struct lto_tree_ref_encoder
  {
!   pointer_map<unsigned> *tree_hash_table;	/* Maps pointers to indices. */
    vec<tree> trees;			/* Maps indices to pointers. */
  };
  
*************** lto_tag_check_range (enum LTO_tags actua
*** 997,1003 ****
  static inline void
  lto_init_tree_ref_encoder (struct lto_tree_ref_encoder *encoder)
  {
!   encoder->tree_hash_table = pointer_map_create ();
    encoder->trees.create (0);
  }
  
--- 997,1003 ----
  static inline void
  lto_init_tree_ref_encoder (struct lto_tree_ref_encoder *encoder)
  {
!   encoder->tree_hash_table = new pointer_map<unsigned>;
    encoder->trees.create (0);
  }
  
*************** lto_destroy_tree_ref_encoder (struct lto
*** 1009,1015 ****
  {
    /* Hash table may be delete already.  */
    if (encoder->tree_hash_table)
!     pointer_map_destroy (encoder->tree_hash_table);
    encoder->trees.release ();
  }
  
--- 1009,1015 ----
  {
    /* Hash table may be delete already.  */
    if (encoder->tree_hash_table)
!     delete encoder->tree_hash_table;
    encoder->trees.release ();
  }
  
Index: gcc/lto-section-out.c
===================================================================
*** gcc/lto-section-out.c	(revision 200189)
--- gcc/lto-section-out.c	(working copy)
*************** lto_output_decl_index (struct lto_output
*** 225,244 ****
  		       struct lto_tree_ref_encoder *encoder,
  		       tree name, unsigned int *this_index)
  {
!   void **slot;
!   int index;
    bool new_entry_p = FALSE;
  
!   slot = pointer_map_insert (encoder->tree_hash_table, name);
!   if (*slot == NULL)
      {
        index = encoder->trees.length ();
!       *slot = (void *)(uintptr_t) index;
        encoder->trees.safe_push (name);
        new_entry_p = TRUE;
      }
    else
!     index = (uintptr_t) *slot;
  
    if (obs)
      streamer_write_uhwi_stream (obs, index);
--- 233,253 ----
  		       struct lto_tree_ref_encoder *encoder,
  		       tree name, unsigned int *this_index)
  {
!   unsigned *slot;
!   unsigned int index;
    bool new_entry_p = FALSE;
+   bool existed_p;
  
!   slot = encoder->tree_hash_table->insert (name, &existed_p);
!   if (!existed_p)
      {
        index = encoder->trees.length ();
!       *slot = index;
        encoder->trees.safe_push (name);
        new_entry_p = TRUE;
      }
    else
!     index = *slot;
  
    if (obs)
      streamer_write_uhwi_stream (obs, index);
*************** lto_record_function_out_decl_state (tree
*** 438,444 ****
    for (i = 0; i < LTO_N_DECL_STREAMS; i++)
      if (state->streams[i].tree_hash_table)
        {
! 	pointer_map_destroy (state->streams[i].tree_hash_table);
  	state->streams[i].tree_hash_table = NULL;
        }
    state->fn_decl = fn_decl;
--- 447,453 ----
    for (i = 0; i < LTO_N_DECL_STREAMS; i++)
      if (state->streams[i].tree_hash_table)
        {
! 	delete state->streams[i].tree_hash_table;
  	state->streams[i].tree_hash_table = NULL;
        }
    state->fn_decl = fn_decl;