PR c++/26068

[pf3gnuchains/gcc-fork.git] / gcc / pointer-set.c

diff --git a/gcc/pointer-set.c b/gcc/pointer-set.c
index 06592d7..460a2cf 100644 (file)
--- a/gcc/pointer-set.c
+++ b/gcc/pointer-set.c
@@ -15,8 +15,8 @@ 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.  */
+the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+Boston, MA 02110-1301, USA.  */
 
 #include "config.h"
 #include "system.h"
@@ -46,23 +46,30 @@ struct pointer_set_t
    relatively prime to 2^sizeof(size_t).  The result is two words.
    Discard the most significant word, and return the most significant
    N bits of the least significant word.  As suggested by Knuth, our
-   choice for A is the integer part of 2^32 / phi, where phi is the
-   golden ratio.
+   choice for A is the integer part of (ULONG_MAX + 1.0) / phi, where phi
+   is the golden ratio.
 
    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)
 {
+#if HOST_BITS_PER_LONG == 32
   const unsigned long A = 0x9e3779b9u;
-  const unsigned long shift = sizeof(unsigned long) * CHAR_BIT - logmax;
+#elif HOST_BITS_PER_LONG == 64
+  const unsigned long A = 0x9e3779b97f4a7c16ul;
+#else
+  const unsigned long A
+    = (ULONG_MAX + 1.0L) * 0.6180339887498948482045868343656381177203L;
+#endif
+  const unsigned long shift = HOST_BITS_PER_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)
 {
@@ -76,7 +83,7 @@ pointer_set_create (void)
   return result;
 }
 
-/* Reclaims all memory associated with PSET. */
+/* Reclaims all memory associated with PSET.  */
 void pointer_set_destroy (struct pointer_set_t *pset)
 {
   XDELETEVEC (pset->slots);
@@ -85,9 +92,7 @@ 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)
 {
@@ -96,21 +101,21 @@ pointer_set_contains (struct pointer_set_t *pset, void *p)
   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. */
+   if P was already present in N_SLOTS.  */
 static int
 insert_aux (void *p, void **slots, size_t n_slots, size_t log_slots)
 {
@@ -134,7 +139,7 @@ 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)
 {
@@ -142,7 +147,7 @@ pointer_set_insert (struct pointer_set_t *pset, void *p)
     return 1;
       
   /* We've inserted a new element.  Expand the table if necessary to keep
-     the load factor small. */
+     the load factor small.  */
   ++pset->n_elements;
   if (pset->n_elements > pset->n_slots / 4)
     {