obtained gcc-4.6.4.tar.bz2 from upstream website;upstream

verified gcc-4.6.4.tar.bz2.sig;
imported gcc-4.6.4 source tree from verified upstream tarball.

downloading a git-generated archive based on the 'upstream' tag
should provide you with a source tree that is binary identical
to the one extracted from the above tarball.

if you have obtained the source via the command 'git clone',
however, do note that line-endings of files in your working
directory might differ from line-endings of the respective
files in the upstream repository.

1 files changed, 295 insertions, 0 deletions

diff --git a/libobjc/hash.c b/libobjc/hash.c
new file mode 100644
index 000000000..733fc6501
--- /dev/null
+++ b/libobjc/hash.c
@@ -0,0 +1,295 @@
+/* Hash tables for Objective C internal structures
+   Copyright (C) 1993, 1996, 1997, 2004, 2009, 2010
+   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.
+
+Under Section 7 of GPL version 3, you are granted additional
+permissions described in the GCC Runtime Library Exception, version
+3.1, as published by the Free Software Foundation.
+
+You should have received a copy of the GNU General Public License and
+a copy of the GCC Runtime Library Exception along with this program;
+see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+<http://www.gnu.org/licenses/>.  */
+
+#include "objc-private/common.h"
+#include <assert.h>               /* For assert.  */
+
+#include "objc/runtime.h"         /* For objc_calloc.  */
+#include "objc-private/hash.h"
+
+/* These two macros determine when a hash table is full and
+   by how much it should be expanded respectively.
+
+   These equations are percentages.  */
+#define FULLNESS(cache) \
+   ((((cache)->size * 75) / 100) <= (cache)->used)
+#define EXPANSION(cache) \
+  ((cache)->size * 2)
+
+cache_ptr
+objc_hash_new (unsigned int size, hash_func_type hash_func,
+	       compare_func_type compare_func)
+{
+  cache_ptr cache;
+
+  /* Pass me a value greater than 0 and a power of 2.  */
+  assert (size);
+  assert (! (size & (size - 1)));
+
+  /* Allocate the cache structure.  calloc insures its initialization
+     for default values.  */
+  cache = (cache_ptr) objc_calloc (1, sizeof (struct cache));
+  assert (cache);
+
+  /* Allocate the array of buckets for the cache.  calloc initializes
+     all of the pointers to NULL.  */
+  cache->node_table
+    = (node_ptr *) objc_calloc (size, sizeof (node_ptr));
+  assert (cache->node_table);
+
+  cache->size  = size;
+
+  /* This should work for all processor architectures (?).  */
+  cache->mask = (size - 1);
+	
+  /* Store the hashing function so that codes can be computed.  */
+  cache->hash_func = hash_func;
+
+  /* Store the function that compares hash keys to determine if they
+     are equal.  */
+  cache->compare_func = compare_func;
+
+  return cache;
+}
+
+
+void
+objc_hash_delete (cache_ptr cache)
+{
+  node_ptr node;
+  node_ptr next_node;
+  unsigned int i;
+
+  /* Purge all key/value pairs from the table.  */
+  /* Step through the nodes one by one and remove every node WITHOUT
+     using objc_hash_next. this makes objc_hash_delete much more
+     efficient. */
+  for (i = 0; i < cache->size; i++)
+    {
+      if ((node = cache->node_table[i]))
+	{
+	  /* An entry in the hash table has been found.  Now step
+	     through the nodes next in the list and free them.  */
+	  while ((next_node = node->next))
+	    {
+	      objc_hash_remove (cache,node->key);
+	      node = next_node;
+	    }
+	  objc_hash_remove (cache,node->key);
+	}
+    }
+
+  /* Release the array of nodes and the cache itself.  */
+  objc_free(cache->node_table);
+  objc_free(cache);
+}
+
+
+void
+objc_hash_add (cache_ptr *cachep, const void *key, void *value)
+{
+  size_t indx = (*(*cachep)->hash_func) (*cachep, key);
+  node_ptr node = (node_ptr) objc_calloc (1, sizeof (struct cache_node));
+
+  assert (node);
+
+  /* Initialize the new node.  */
+  node->key    = key;
+  node->value  = value;
+  node->next  = (*cachep)->node_table[indx];
+
+  /* Debugging.  Check the list for another key.  */
+#ifdef DEBUG
+  {
+    node_ptr node1 = (*cachep)->node_table[indx];
+    while (node1)
+      {
+	assert (node1->key != key);
+	node1 = node1->next;
+      }
+  }
+#endif
+
+  /* Install the node as the first element on the list.  */
+  (*cachep)->node_table[indx] = node;
+
+  /* Bump the number of entries in the cache.  */
+  ++(*cachep)->used;
+  
+  /* Check the hash table's fullness.  We're going to expand if it is
+     above the fullness level.  */
+  if (FULLNESS (*cachep))
+    {
+      /* The hash table has reached its fullness level.  Time to
+	 expand it.
+
+	 I'm using a slow method here but is built on other primitive
+	 functions thereby increasing its correctness.  */
+      node_ptr node1 = NULL;
+      cache_ptr new = objc_hash_new (EXPANSION (*cachep),
+				     (*cachep)->hash_func,
+				     (*cachep)->compare_func);
+      
+      DEBUG_PRINTF ("Expanding cache %#x from %d to %d\n",
+		    (int) *cachep, (*cachep)->size, new->size);
+      
+      /* Copy the nodes from the first hash table to the new one.  */
+      while ((node1 = objc_hash_next (*cachep, node1)))
+	objc_hash_add (&new, node1->key, node1->value);
+      
+      /* Trash the old cache.  */
+      objc_hash_delete (*cachep);
+      
+      /* Return a pointer to the new hash table.  */
+      *cachep = new;
+    }
+}
+
+void
+objc_hash_remove (cache_ptr cache, const void *key)
+{
+  size_t indx = (*cache->hash_func) (cache, key);
+  node_ptr node = cache->node_table[indx];
+
+  /* We assume there is an entry in the table.  Error if it is
+     not.  */
+  assert (node);
+
+  /* Special case.  First element is the key/value pair to be
+     removed.  */
+  if ((*cache->compare_func) (node->key, key))
+    {
+      cache->node_table[indx] = node->next;
+      objc_free(node);
+    }
+  else
+    {
+      /* Otherwise, find the hash entry.  */
+      node_ptr prev = node;
+      BOOL removed = NO;
+      do
+	{
+	  if ((*cache->compare_func) (node->key, key))
+	    {
+	      prev->next = node->next, removed = YES;
+	      objc_free(node);
+	    }
+	  else
+	    prev = node, node = node->next;
+	}
+      while (!removed && node);
+      assert (removed);
+    }
+  
+  /* Decrement the number of entries in the hash table.  */
+  --cache->used;
+}
+
+
+node_ptr
+objc_hash_next (cache_ptr cache, node_ptr node)
+{
+  /* If the scan is being started then reset the last node visitied
+     pointer and bucket index.  */
+  if (!node)
+    cache->last_bucket  = 0;
+  
+  /* If there is a node visited last then check for another entry in
+     the same bucket.  Otherwise step to the next bucket.  */
+  if (node)
+    {
+      if (node->next)
+	{
+	  /* There is a node which follows the last node returned.
+	     Step to that node and retun it.  */
+	  return node->next;
+	}
+      else
+	++cache->last_bucket;
+  }
+
+  /* If the list isn't exhausted then search the buckets for other
+     nodes.  */
+  if (cache->last_bucket < cache->size)
+    {
+      /*  Scan the remainder of the buckets looking for an entry at
+	  the head of the list.  Return the first item found.  */
+      while (cache->last_bucket < cache->size)
+	if (cache->node_table[cache->last_bucket])
+	  return cache->node_table[cache->last_bucket];
+	else
+	  ++cache->last_bucket;
+      
+      /* No further nodes were found in the hash table.  */
+      return NULL;
+    }
+  else
+    return NULL;
+}
+
+
+/* Given KEY, return corresponding value for it in CACHE.  Return NULL
+   if the KEY is not recorded.  */
+void *
+objc_hash_value_for_key (cache_ptr cache, const void *key)
+{
+  node_ptr node = cache->node_table[(*cache->hash_func) (cache, key)];
+  void *retval = NULL;
+
+  if (node)
+    do
+      {
+	if ((*cache->compare_func) (node->key, key))
+	  {
+	    retval = node->value;
+	    break;
+	  }
+	else
+	  node = node->next;
+      }
+    while (! retval && node);
+  
+  return retval;
+}
+
+/* Given KEY, return YES if it exists in the CACHE.  Return NO if it
+   does not */
+BOOL
+objc_hash_is_key_in_hash (cache_ptr cache, const void *key)
+{
+  node_ptr node = cache->node_table[(*cache->hash_func) (cache, key)];
+  
+  if (node)
+    do
+      {
+	if ((*cache->compare_func)(node->key, key))
+	  return YES;
+	else
+	  node = node->next;
+      }
+    while (node);
+
+  return NO;
+}