Makefile.in (OBJS, [...]): Update.

	* Makefile.in (OBJS, LIBCPP_OBJS, LIBCPP_DEPS,
	cpplib.o, cpphash.o, fix-header): Update.
	(hashtable.o): New target.
	* c-common.h: Include cpplib.h.  Define C_RID_CODE and
	struct c_common_identifier here.
	* c-lang.c (c_init_options): Update.  Call set_identifier_size.
	* c-lex.c (c_lex): Update.
	* c-pragma.h: Update.
	* c-tree.h (struct lang_identifier): Contain c_common_identifier.
	Delete rid_code.
	(C_RID_CODE): Delete.
	* cpphash.c: Rewrite to use hashtable.c.
	* cpphash.h: Update include guards.
	(struct cpp_reader): Remove hashtab.
	hash_ob and buffer_ob are no longer pointers.  Add hash_table
	and our_hashtable.
	(HASHSTEP, _cpp_init_hashtable,	_cpp_lookup_with_hash): Delete.
	(_cpp_cleanup_hashtable): Rename _cpp_destroy_hashtable.
	(_cpp_cleanup_stacks): Rename _cpp_init_directives.
	* cppinit.c (cpp_create_reader): Update.
	* cpplex.c (cpp_ideq, parse_identifier, cpp_output_token): Update.
	(cpp_interpret_charconst): Eliminate warning.
	* cpplib.c (do_pragma, do_endif, push_conditional,
	cpp_push_buffer, cpp_pop_buffer): Update.
	(_cpp_init_stacks): Rename cpp_init_directives.
	(_cpp_cleanup_stacks): Remove.
	* cpplib.h: Update include guards.  Include tree-core.h and c-rid.h.
	(cpp_hashnode, cpp_token, NODE_LEN, NODE_NAME,
	 cpp_forall_identifiers, cpp_create_reader): Update.
	(C_RID_CODE, cpp_make_node): New.
	(c_common_identifier): New identifier node for C front ends.
	* cppmain.c (main): Update.
	* fix-header.c (read_scan_file): Update.
	* flags.h (id_clash_len): Make unsigned.
	* ggc.h (ggc_mark_nonnull_tree): New.
	* hashtable.c: New.
	* hashtable.h: New.
	* stringpool.c: Update comments and copyright.  Update to use
	hashtable.c.
	* toplev.c (approx_sqrt): Move to hashtable.c.
	(id_clash_len): Make unsigned.
	* toplev.h (ident_hash): New.
	* tree.c (gcc_obstack_init): Move to hashtable.c.
	* tree.h: Include hashtable.h.
	(IDENTIFIER_POINTER, IDENTIFIER_LENGTH): Update.
	(GCC_IDENT_TO_HT_IDENT, HT_IDENT_TO_GCC_IDENT): New.
	(struct tree_identifier): Update.
	(make_identifier): New.
cp:
	* cp-tree.h (struct lang_identifier, C_RID_YYCODE): Update.
	(C_RID_CODE): Remove.
	* lex.c (cxx_init_options): Call set_identifier_size.  Update.
	(init_parse): Don't do it here.
objc:
	* objc-act.c (objc_init_options): Call set_identifier_size. Update.

From-SVN: r42334

1 files changed, 315 insertions, 0 deletions

diff --git a/gcc/hashtable.c b/gcc/hashtable.c
new file mode 100644
index 0000000..f77eb7f
--- /dev/null
+++ b/gcc/hashtable.c
@@ -0,0 +1,315 @@
+/* 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;
+}
+
+/* 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_copy (&table->stack, str, len + 1);
+  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;
+}