Initial checkin of GCC 4.9.0 from trunk (r208799).

Change-Id: I48a3c08bb98542aa215912a75f03c0890e497dba

1 files changed, 271 insertions, 0 deletions

diff --git a/gcc-4.9/gcc/pointer-set.c b/gcc-4.9/gcc/pointer-set.c
new file mode 100644
index 000000000..8b6a73257
--- /dev/null
+++ b/gcc-4.9/gcc/pointer-set.c
@@ -0,0 +1,271 @@
+/* Set operations on pointers
+   Copyright (C) 2004-2014 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 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+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 COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "pointer-set.h"
+
+
+/* Use the multiplicative method, as described in Knuth 6.4, to obtain
+   a hash code for P in the range [0, MAX).  MAX == 2^LOGMAX.
+
+   Summary of this method: Multiply p by some number A that's
+   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 (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.  */
+
+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;
+#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 * (uintptr_t) p) >> shift) & (max - 1);
+}
+
+
+/* Allocate an empty pointer set.  */
+struct pointer_set_t *
+pointer_set_create (void)
+{
+  struct pointer_set_t *result = XNEW (struct pointer_set_t);
+
+  result->n_elements = 0;
+  result->log_slots = 8;
+  result->n_slots = (size_t) 1 << result->log_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)
+{
+  XDELETEVEC (pset->slots);
+  XDELETE (pset);
+}
+
+
+/* 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_set_lookup (const pointer_set_t *pset, const void *p, size_t *ix)
+{
+  size_t n = hash1 (p, pset->n_slots, pset->log_slots);
+
+  while (true)
+    {
+      if (pset->slots[n] == p)
+	{
+	  *ix = n;
+	  return true;
+	}
+      else if (pset->slots[n] == 0)
+	{
+	  *ix = n;
+	  return false;
+	}
+      else
+       {
+         ++n;
+         if (n == pset->n_slots)
+           n = 0;
+       }
+    }
+}
+
+/* Returns nonzero if PSET contains P.  P must be nonnull.
+
+   Collisions are resolved by linear probing.  */
+int
+pointer_set_contains (const struct pointer_set_t *pset, const void *p)
+{
+  size_t n;
+  return pointer_set_lookup (pset, p, &n);
+}
+
+/* Inserts P into PSET if it wasn't already there.  Returns nonzero
+   if it was already there. P must be nonnull.  */
+int
+pointer_set_insert (struct pointer_set_t *pset, const void *p)
+{
+  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 old_n_slots = pset->n_slots;
+      const void **old_slots = pset->slots;
+      pset->log_slots = pset->log_slots + 1;
+      pset->n_slots = pset->n_slots * 2;
+      pset->slots = XCNEWVEC (const void *, pset->n_slots);
+      size_t i;
+
+      for (i = 0; i < old_n_slots; ++i)
+        {
+	  const void *value = old_slots[i];
+	  pointer_set_lookup (pset, value, &n);
+	  pset->slots[n] = value;
+	}
+
+      XDELETEVEC (old_slots);
+    }
+
+  if (pointer_set_lookup (pset, p, &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
+{
+  pointer_set_t pset;
+  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->pset.n_elements = 0;
+  result->pset.log_slots = 8;
+  result->pset.n_slots = (size_t) 1 << result->pset.log_slots;
+
+  result->pset.slots = XCNEWVEC (const void *, result->pset.n_slots);
+  result->values = XCNEWVEC (void *, result->pset.n_slots);
+  return result;
+}
+
+/* Reclaims all memory associated with PMAP.  */
+void pointer_map_destroy (struct pointer_map_t *pmap)
+{
+  XDELETEVEC (pmap->pset.slots);
+  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;
+  if (pointer_set_lookup (&pmap->pset, p, &n))
+    return &pmap->values[n];
+  else
+    return NULL;
+}
+
+/* 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->pset.n_elements > pmap->pset.n_slots / 4)
+    {
+      size_t old_n_slots = pmap->pset.n_slots;
+      const void **old_keys = pmap->pset.slots;
+      void **old_values = pmap->values;
+      pmap->pset.log_slots = pmap->pset.log_slots + 1;
+      pmap->pset.n_slots = pmap->pset.n_slots * 2;
+      pmap->pset.slots = XCNEWVEC (const void *, pmap->pset.n_slots);
+      pmap->values = XCNEWVEC (void *, pmap->pset.n_slots);
+      size_t i;
+
+      for (i = 0; i < old_n_slots; ++i)
+	if (old_keys[i])
+	  {
+	    const void *key = old_keys[i];
+	    pointer_set_lookup (&pmap->pset, key, &n);
+	    pmap->pset.slots[n] = key;
+	    pmap->values[n] = old_values[i];
+	  }
+
+      XDELETEVEC (old_keys);
+      XDELETEVEC (old_values);
+    }
+
+  if (!pointer_set_lookup (&pmap->pset, p, &n))
+    {
+      ++pmap->pset.n_elements;
+      pmap->pset.slots[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->pset.n_slots; ++i)
+    if (pmap->pset.slots[i]
+	&& !fn (pmap->pset.slots[i], &pmap->values[i], data))
+      break;
+}