X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=gcc%2Fhashtable.c;fp=gcc%2Fhashtable.c;h=0000000000000000000000000000000000000000;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=bd2b13727bb84dadb7edb6d2cc30949ebbe2bc9f;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git

diff --git a/gcc/hashtable.c b/gcc/hashtable.c
deleted file mode 100644
index bd2b1372..00000000
--- a/gcc/hashtable.c
+++ /dev/null
@@ -1,326 +0,0 @@
-/* Hash tables.
-   Copyright (C) 2000, 2001 Free Software Foundation, Inc.
-
-This program 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) any
-later version.
-
-This program 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 this program; if not, write to the Free Software
-Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
-
- In other words, you are welcome to use, share and improve this program.
- You are forbidden to forbid anyone else to use, share and improve
- what you give them.   Help stamp out software-hoarding!  */
-
-#include "config.h"
-#include "system.h"
-#include "hashtable.h"
-
-/* The code below is a specialization of Vladimir Makarov's expandable
-   hash tables (see libiberty/hashtab.c).  The abstraction penalty was
-   too high to continue using the generic form.  This code knows
-   intrinsically how to calculate a hash value, and how to compare an
-   existing entry with a potential new one.  Also, the ability to
-   delete members from the table has been removed.  */
-
-static unsigned int calc_hash PARAMS ((const unsigned char *, unsigned int));
-static void ht_expand PARAMS ((hash_table *));
-
-/* Let particular systems override the size of a chunk.  */
-#ifndef OBSTACK_CHUNK_SIZE
-#define OBSTACK_CHUNK_SIZE 0
-#endif
-  /* Let them override the alloc and free routines too.  */
-#ifndef OBSTACK_CHUNK_ALLOC
-#define OBSTACK_CHUNK_ALLOC xmalloc
-#endif
-#ifndef OBSTACK_CHUNK_FREE
-#define OBSTACK_CHUNK_FREE free
-#endif
-
-/* Initialise an obstack.  */
-void
-gcc_obstack_init (obstack)
-     struct obstack *obstack;
-{
-  _obstack_begin (obstack, OBSTACK_CHUNK_SIZE, 0,
-		  (void *(*) PARAMS ((long))) OBSTACK_CHUNK_ALLOC,
-		  (void (*) PARAMS ((void *))) OBSTACK_CHUNK_FREE);
-}
-
-/* Calculate the hash of the string STR of length LEN.  */
-
-static unsigned int
-calc_hash (str, len)
-     const unsigned char *str;
-     unsigned int len;
-{
-  unsigned int n = len;
-  unsigned int r = 0;
-#define HASHSTEP(r, c) ((r) * 67 + ((c) - 113));
-
-  while (n--)
-    r = HASHSTEP (r, *str++);
-
-  return r + len;
-#undef HASHSTEP
-}
-
-/* Initialize an identifier hashtable.  */
-
-hash_table *
-ht_create (order)
-     unsigned int order;
-{
-  unsigned int nslots = 1 << order;
-  hash_table *table;
-
-  table = (hash_table *) xmalloc (sizeof (hash_table));
-  memset (table, 0, sizeof (hash_table));
-
-  /* Strings need no alignment.  */
-  gcc_obstack_init (&table->stack);
-  obstack_alignment_mask (&table->stack) = 0;
-
-  table->entries = (hashnode *) xcalloc (nslots, sizeof (hashnode));
-  table->nslots = nslots;
-  return table;
-}
-
-/* Frees all memory associated with a hash table.  */
-
-void
-ht_destroy (table)
-     hash_table *table;
-{
-  obstack_free (&table->stack, NULL);
-  free (table->entries);
-  free (table);
-}
-
-/* Returns the hash entry for the a STR of length LEN.  If that string
-   already exists in the table, returns the existing entry, and, if
-   INSERT is CPP_ALLOCED, frees the last obstack object.  If the
-   identifier hasn't been seen before, and INSERT is CPP_NO_INSERT,
-   returns NULL.  Otherwise insert and returns a new entry.  A new
-   string is alloced if INSERT is CPP_ALLOC, otherwise INSERT is
-   CPP_ALLOCED and the item is assumed to be at the top of the
-   obstack.  */
-hashnode
-ht_lookup (table, str, len, insert)
-     hash_table *table;
-     const unsigned char *str;
-     unsigned int len;
-     enum ht_lookup_option insert;
-{
-  unsigned int hash = calc_hash (str, len);
-  unsigned int hash2;
-  unsigned int index;
-  size_t sizemask;
-  hashnode node;
-
-  sizemask = table->nslots - 1;
-  index = hash & sizemask;
-
-  /* hash2 must be odd, so we're guaranteed to visit every possible
-     location in the table during rehashing.  */
-  hash2 = ((hash * 17) & sizemask) | 1;
-  table->searches++;
-
-  for (;;)
-    {
-      node = table->entries[index];
-
-      if (node == NULL)
-	break;
-
-      if (HT_LEN (node) == len && !memcmp (HT_STR (node), str, len))
-	{
-	  if (insert == HT_ALLOCED)
-	    /* The string we search for was placed at the end of the
-	       obstack.  Release it.  */
-	    obstack_free (&table->stack, (PTR) str);
-	  return node;
-	}
-
-      index = (index + hash2) & sizemask;
-      table->collisions++;
-    }
-
-  if (insert == HT_NO_INSERT)
-    return NULL;
-
-  node = (*table->alloc_node) (table);
-  table->entries[index] = node;
-
-  HT_LEN (node) = len;
-  if (insert == HT_ALLOC)
-    HT_STR (node) = obstack_copy0 (&table->stack, str, len);
-  else
-    HT_STR (node) = str;
-
-  if (++table->nelements * 4 >= table->nslots * 3)
-    /* Must expand the string table.  */
-    ht_expand (table);
-
-  return node;
-}
-
-/* Double the size of a hash table, re-hashing existing entries.  */
-
-static void
-ht_expand (table)
-     hash_table *table;
-{
-  hashnode *nentries, *p, *limit;
-  unsigned int size, sizemask;
-
-  size = table->nslots * 2;
-  nentries = (hashnode *) xcalloc (size, sizeof (hashnode));
-  sizemask = size - 1;
-
-  p = table->entries;
-  limit = p + table->nslots;
-  do
-    if (*p)
-      {
-	unsigned int index, hash, hash2;
-
-	hash = calc_hash (HT_STR (*p), HT_LEN (*p));
-	hash2 = ((hash * 17) & sizemask) | 1;
-	index = hash & sizemask;
-
-	for (;;)
-	  {
-	    if (! nentries[index])
-	      {
-		nentries[index] = *p;
-		break;
-	      }
-
-	    index = (index + hash2) & sizemask;
-	  }
-      }
-  while (++p < limit);
-
-  free (table->entries);
-  table->entries = nentries;
-  table->nslots = size;
-}
-
-/* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
-   the node, and V.  */
-void
-ht_forall (table, cb, v)
-     hash_table *table;
-     ht_cb cb;
-     const PTR v;
-{
-  hashnode *p, *limit;
-
-  p = table->entries;
-  limit = p + table->nslots;
-  do
-    if (*p)
-      {
-	if ((*cb) (table->pfile, *p, v) == 0)
-	  break;
-      }
-  while (++p < limit);
-}
-
-/* Dump allocation statistics to stderr.  */
-
-void
-ht_dump_statistics (table)
-     hash_table *table;
-{
-  size_t nelts, nids, overhead, headers;
-  size_t total_bytes, longest, sum_of_squares;
-  double exp_len, exp_len2, exp2_len;
-  hashnode *p, *limit;
-
-#define SCALE(x) ((unsigned long) ((x) < 1024*10 \
-		  ? (x) \
-		  : ((x) < 1024*1024*10 \
-		     ? (x) / 1024 \
-		     : (x) / (1024*1024))))
-#define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
-
-  total_bytes = longest = sum_of_squares = nids = 0;
-  p = table->entries;
-  limit = p + table->nslots;
-  do
-    if (*p)
-      {
-	size_t n = HT_LEN (*p);
-
-	total_bytes += n;
-	sum_of_squares += n * n;
-	if (n > longest)
-	  longest = n;
-	nids++;
-      }
-  while (++p < limit);
-      
-  nelts = table->nelements;
-  overhead = obstack_memory_used (&table->stack) - total_bytes;
-  headers = table->nslots * sizeof (hashnode);
-
-  fprintf (stderr, "\nString pool\nentries\t\t%lu\n",
-	   (unsigned long) nelts);
-  fprintf (stderr, "identifiers\t%lu (%.2f%%)\n",
-	   (unsigned long) nids, nids * 100.0 / nelts);
-  fprintf (stderr, "slots\t\t%lu\n",
-	   (unsigned long) table->nslots);
-  fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n",
-	   SCALE (total_bytes), LABEL (total_bytes),
-	   SCALE (overhead), LABEL (overhead));
-  fprintf (stderr, "table size\t%lu%c\n",
-	   SCALE (headers), LABEL (headers));
-
-  exp_len = (double)total_bytes / (double)nelts;
-  exp2_len = exp_len * exp_len;
-  exp_len2 = (double) sum_of_squares / (double) nelts;
-
-  fprintf (stderr, "coll/search\t%.4f\n",
-	   (double) table->collisions / (double) table->searches);
-  fprintf (stderr, "ins/search\t%.4f\n",
-	   (double) nelts / (double) table->searches);
-  fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n",
-	   exp_len, approx_sqrt (exp_len2 - exp2_len));
-  fprintf (stderr, "longest entry\t%lu\n",
-	   (unsigned long) longest);
-#undef SCALE
-#undef LABEL
-}
-
-/* Return the approximate positive square root of a number N.  This is for
-   statistical reports, not code generation.  */
-double
-approx_sqrt (x)
-     double x;
-{
-  double s, d;
-
-  if (x < 0)
-    abort ();
-  if (x == 0)
-    return 0;
-
-  s = x;
-  do
-    {
-      d = (s * s - x) / (2 * s);
-      s -= d;
-    }
-  while (d > .0001);
-  return s;
-}