X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fpointer-set.c;h=b57c404f6a1a5ead17e45ba7c2ae1f0d5f054234;hb=f090c9d06962930a4a782d0e78d71cababf0fdb7;hp=b7154deabd1450fd00b99a75a6a231292b290844;hpb=a1f487759c3044b9471a858df8127c6136fd22a1;p=pf3gnuchains%2Fgcc-fork.git

diff --git a/gcc/pointer-set.c b/gcc/pointer-set.c
index b7154deabd1..b57c404f6a1 100644
--- a/gcc/pointer-set.c
+++ b/gcc/pointer-set.c
@@ -1,11 +1,11 @@
 /* Set operations on pointers
-   Copyright (C) 2004 Free Software Foundation, Inc.
+   Copyright (C) 2004, 2006, 2007 Free Software Foundation, Inc.
 
 This file is part of GCC.
 
 GCC is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
+the Free Software Foundation; either version 3, or (at your option)
 any later version.
 
 GCC is distributed in the hope that it will be useful,
@@ -14,21 +14,19 @@ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.
 
 You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING.  If not, write to
-the Free Software Foundation, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA.  */
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
 
 #include "config.h"
 #include "system.h"
 #include "pointer-set.h"
 
-/* A pointer sets is represented as a simple open-addressing hash
+/* 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.  There is no mechanism for user control of hash
-   function, equality comparison, initial size, or resizing policy.
-*/
+   supported (yet).  There is no mechanism for user control of hash
+   function, equality comparison, initial size, or resizing policy.  */
 
 struct pointer_set_t
 {
@@ -36,7 +34,7 @@ struct pointer_set_t
   size_t n_slots;		/* n_slots = 2^log_slots */
   size_t n_elements;
 
-  void **slots;
+  const void **slots;
 };
 
 /* Use the multiplicative method, as described in Knuth 6.4, to obtain
@@ -51,7 +49,7 @@ struct pointer_set_t
 
    We don't need to do anything special for full-width multiplication
    because we're only interested in the least significant word of the
-   product, and unsigned arithmetic in C is modulo the word size. */
+   product, and unsigned arithmetic in C is modulo the word size.  */
 
 static inline size_t
 hash1 (const void *p, unsigned long max, unsigned long logmax)
@@ -69,7 +67,7 @@ hash1 (const void *p, unsigned long max, unsigned long logmax)
   return ((A * (unsigned long) p) >> shift) & (max - 1);
 }
 
-/* Allocate an empty pointer set. */
+/* Allocate an empty pointer set.  */
 struct pointer_set_t *
 pointer_set_create (void)
 {
@@ -79,12 +77,13 @@ pointer_set_create (void)
   result->log_slots = 8;
   result->n_slots = (size_t) 1 << result->log_slots;
 
-  result->slots = XCNEWVEC (void *, result->n_slots);
+  result->slots = XCNEWVEC (const void *, result->n_slots);
   return result;
 }
 
-/* Reclaims all memory associated with PSET. */
-void pointer_set_destroy (struct pointer_set_t *pset)
+/* Reclaims all memory associated with PSET.  */
+void
+pointer_set_destroy (struct pointer_set_t *pset)
 {
   XDELETEVEC (pset->slots);
   XDELETE (pset);
@@ -92,45 +91,37 @@ void pointer_set_destroy (struct pointer_set_t *pset)
 
 /* Returns nonzero if PSET contains P.  P must be nonnull.
 
-   Collisions are resolved by linear probing.  More complicated
-   collision management schemes are only useful when the load factor
-   significantly exceeds 0.5, and we never let that happen. */
+   Collisions are resolved by linear probing.  */
 int
-pointer_set_contains (struct pointer_set_t *pset, void *p)
+pointer_set_contains (const struct pointer_set_t *pset, const void *p)
 {
   size_t n = hash1 (p, pset->n_slots, pset->log_slots);
 
   while (true)
     {
       if (pset->slots[n] == p)
-	return 1;
+       return 1;
       else if (pset->slots[n] == 0)
-	return 0;
+       return 0;
       else
-	{
-	  ++n;
-	  if (n == pset->n_slots)
-	    n = 0;
-	}
+       {
+         ++n;
+         if (n == pset->n_slots)
+           n = 0;
+       }
     }
 }
 
-/* Subroutine of pointer_set_insert.  Inserts P into an empty
-   element of SLOTS, an array of length N_SLOTS.  Returns nonzero
-   if P was already present in N_SLOTS. */
-static int
-insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots)
+/* Subroutine of pointer_set_insert.  Return the insertion slot for P into
+   an empty element of SLOTS, an array of length N_SLOTS.  */
+static inline size_t
+insert_aux (const void *p, const void **slots, size_t n_slots, size_t log_slots)
 {
   size_t n = hash1 (p, n_slots, log_slots);
   while (true)
     {
-      if (slots[n] == p)
-	return 1;
-      else if (slots[n] == 0)
-	{
-	  slots[n] = p;
-	  return 0;
-	}
+      if (slots[n] == p || slots[n] == 0)
+	return n;
       else
 	{
 	  ++n;
@@ -141,27 +132,26 @@ insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots)
 }
 
 /* Inserts P into PSET if it wasn't already there.  Returns nonzero
-   if it was already there. P must be nonnull. */
+   if it was already there. P must be nonnull.  */
 int
-pointer_set_insert (struct pointer_set_t *pset, void *p)
+pointer_set_insert (struct pointer_set_t *pset, const void *p)
 {
-  if (insert_aux (p, pset->slots, pset->n_slots, pset->log_slots))
-    return 1;
-      
-  /* We've inserted a new element.  Expand the table if necessary to keep
-     the load factor small. */
-  ++pset->n_elements;
+  size_t n;
+
+  /* For simplicity, expand the set even if P is already there.  This can be
+     superfluous but can happen at most once.  */
   if (pset->n_elements > pset->n_slots / 4)
     {
       size_t new_log_slots = pset->log_slots + 1;
       size_t new_n_slots = pset->n_slots * 2;
-      void **new_slots = XCNEWVEC (void *, new_n_slots);
+      const void **new_slots = XCNEWVEC (const void *, new_n_slots);
       size_t i;
 
       for (i = 0; i < pset->n_slots; ++i)
-	{
-	  if (pset->slots[i])
-	    insert_aux (pset->slots[i], new_slots, new_n_slots, new_log_slots);
+        {
+	  const void *value = pset->slots[i];
+	  n = insert_aux (value, new_slots, new_n_slots, new_log_slots);
+	  new_slots[n] = value;
 	}
 
       XDELETEVEC (pset->slots);
@@ -170,5 +160,144 @@ pointer_set_insert (struct pointer_set_t *pset, void *p)
       pset->slots = new_slots;
     }
 
+  n = insert_aux (p, pset->slots, pset->n_slots, pset->log_slots);
+  if (pset->slots[n])
+    return 1;
+
+  pset->slots[n] = p;
+  ++pset->n_elements;
   return 0;
 }
+
+/* Pass each pointer in PSET to the function in FN, together with the fixed
+   parameter DATA.  If FN returns false, the iteration stops.  */
+
+void pointer_set_traverse (const struct pointer_set_t *pset,
+			   bool (*fn) (const void *, void *), void *data)
+{
+  size_t i;
+  for (i = 0; i < pset->n_slots; ++i)
+    if (pset->slots[i] && !fn (pset->slots[i], data))
+      break;
+}
+
+
+/* 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.  */
+
+struct pointer_map_t
+{
+  size_t log_slots;
+  size_t n_slots;		/* n_slots = 2^log_slots */
+  size_t n_elements;
+
+  const void **keys;
+  void **values;
+};
+
+/* Allocate an empty pointer map.  */
+struct pointer_map_t *
+pointer_map_create (void)
+{
+  struct pointer_map_t *result = XNEW (struct pointer_map_t);
+
+  result->n_elements = 0;
+  result->log_slots = 8;
+  result->n_slots = (size_t) 1 << result->log_slots;
+
+  result->keys = XCNEWVEC (const void *, result->n_slots);
+  result->values = XCNEWVEC (void *, result->n_slots);
+  return result;
+}
+
+/* Reclaims all memory associated with PMAP.  */
+void pointer_map_destroy (struct pointer_map_t *pmap)
+{
+  XDELETEVEC (pmap->keys);
+  XDELETEVEC (pmap->values);
+  XDELETE (pmap);
+}
+
+/* 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.  */
+void **
+pointer_map_contains (const struct pointer_map_t *pmap, const void *p)
+{
+  size_t n = hash1 (p, pmap->n_slots, pmap->log_slots);
+
+  while (true)
+    {
+      if (pmap->keys[n] == p)
+	return &pmap->values[n];
+      else if (pmap->keys[n] == 0)
+	return NULL;
+      else
+       {
+         ++n;
+         if (n == pmap->n_slots)
+           n = 0;
+       }
+    }
+}
+
+/* Inserts P into PMAP if it wasn't already there.  Returns a pointer
+   to the value.  P must be nonnull.  */
+void **
+pointer_map_insert (struct pointer_map_t *pmap, const void *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.  */
+  if (pmap->n_elements > pmap->n_slots / 4)
+    {
+      size_t new_log_slots = pmap->log_slots + 1;
+      size_t new_n_slots = pmap->n_slots * 2;
+      const void **new_keys = XCNEWVEC (const void *, new_n_slots);
+      void **new_values = XCNEWVEC (void *, new_n_slots);
+      size_t i;
+
+      for (i = 0; i < pmap->n_slots; ++i)
+	if (pmap->keys[i])
+	  {
+	    const void *key = pmap->keys[i];
+	    n = insert_aux (key, new_keys, new_n_slots, new_log_slots);
+	    new_keys[n] = key;
+	    new_values[n] = pmap->values[i];
+	  }
+
+      XDELETEVEC (pmap->keys);
+      XDELETEVEC (pmap->values);
+      pmap->n_slots = new_n_slots;
+      pmap->log_slots = new_log_slots;
+      pmap->keys = new_keys;
+      pmap->values = new_values;
+    }
+
+  n = insert_aux (p, pmap->keys, pmap->n_slots, pmap->log_slots);
+  if (!pmap->keys[n])
+    {
+      ++pmap->n_elements;
+      pmap->keys[n] = p;
+    }
+
+  return &pmap->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.  */
+
+void pointer_map_traverse (const struct pointer_map_t *pmap,
+			   bool (*fn) (const void *, void **, void *), void *data)
+{
+  size_t i;
+  for (i = 0; i < pmap->n_slots; ++i)
+    if (pmap->keys[i] && !fn (pmap->keys[i], &pmap->values[i], data))
+      break;
+}