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

29 files changed, 799 insertions, 669 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 8b4ebf3..a740a65 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,61 @@
+2001-05-20  Neil Booth  <neil@daikokuya.demon.co.uk>
+
+	* 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.
+
 Sat May 19 18:23:04 2001  Richard Henderson <rth@redhat.com>
 
 	* except.c (dw2_build_landing_pads): Use word_mode, not Pmode,
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 7a7f700..1c77cca 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -706,7 +706,7 @@ OBJS =									\
  dependence.o diagnostic.o doloop.o dominance.o dwarf2asm.o dwarf2out.o	\
  dwarfout.o emit-rtl.o except.o explow.o expmed.o expr.o final.o flow.o	\
  fold-const.o function.o gcse.o genrtl.o ggc-common.o global.o graph.o	\
- haifa-sched.o hash.o ifcvt.o insn-attrtab.o insn-emit.o		\
+ haifa-sched.o hash.o hashtable.o ifcvt.o insn-attrtab.o insn-emit.o	\
  insn-extract.o insn-opinit.o insn-output.o insn-peep.o insn-recog.o	\
  integrate.o intl.o jump.o lcm.o lists.o local-alloc.o loop.o mbchar.o	\
  optabs.o params.o predict.o print-rtl.o print-tree.o profile.o real.o	\
@@ -1294,6 +1294,8 @@ ggc-page.o: ggc-page.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TREE_H) flags.h \
 stringpool.o: stringpool.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) $(OBSTACK_H) \
 	flags.h toplev.h
 
+hashtable.o: hashtable.c hashtable.h $(CONFIG_H) $(SYSTEM_H) $(OBSTACK_H)
+
 ggc-none.o: ggc-none.c $(GCONFIG_H) $(SYSTEM_H) $(GGC_H)
 	$(CC) -c $(ALL_CFLAGS) -DGENERATOR_FILE $(ALL_CPPFLAGS) $(INCLUDES) $< $(OUTPUT_OPTION)
 
@@ -1890,9 +1892,9 @@ PREPROCESSOR_DEFINES = \
 
 LIBCPP_OBJS =	cpplib.o cpplex.o cppmacro.o cppexp.o cppfiles.o \
 		cpphash.o cpperror.o cppinit.o cppdefault.o \
-		mkdeps.o prefix.o version.o mbchar.o
+		hashtable.o mkdeps.o prefix.o version.o mbchar.o
 
-LIBCPP_DEPS =	cpplib.h cpphash.h intl.h $(SYSTEM_H)
+LIBCPP_DEPS =	cpplib.h cpphash.h hashtable.h intl.h $(OBSTACK_H) $(SYSTEM_H)
 
 # Most of the other archives built/used by this makefile are for
 # targets.  This one is strictly for the host.
@@ -1911,8 +1913,8 @@ cpperror.o: cpperror.c $(CONFIG_H) $(LIBCPP_DEPS)
 cppexp.o:   cppexp.c   $(CONFIG_H) $(LIBCPP_DEPS)
 cpplex.o:   cpplex.c   $(CONFIG_H) $(LIBCPP_DEPS) mbchar.h
 cppmacro.o: cppmacro.c $(CONFIG_H) $(LIBCPP_DEPS)
-cpplib.o:   cpplib.c   $(CONFIG_H) $(LIBCPP_DEPS) $(OBSTACK_H)
-cpphash.o:  cpphash.c  $(CONFIG_H) $(LIBCPP_DEPS) $(OBSTACK_H)
+cpplib.o:   cpplib.c   $(CONFIG_H) $(LIBCPP_DEPS)
+cpphash.o:  cpphash.c  $(CONFIG_H) $(LIBCPP_DEPS)
 cppfiles.o: cppfiles.c $(CONFIG_H) $(LIBCPP_DEPS) $(SPLAY_TREE_H) mkdeps.h
 cppinit.o:  cppinit.c  $(CONFIG_H) $(LIBCPP_DEPS) cppdefault.h \
 		mkdeps.h prefix.h output.h version.h
diff --git a/gcc/c-common.h b/gcc/c-common.h
index 78a7a08..8a5a759 100644
--- a/gcc/c-common.h
+++ b/gcc/c-common.h
@@ -23,6 +23,7 @@ Boston, MA 02111-1307, USA.  */
 #define GCC_C_COMMON_H
 
 #include "splay-tree.h"
+#include "cpplib.h"
 
 /* Usage of TREE_LANG_FLAG_?:
    0: COMPOUND_STMT_NO_SCOPE (in COMPOUND_STMT).
@@ -168,6 +169,17 @@ enum c_tree_index
     CTI_MAX
 };
 
+#define C_RID_CODE(id)	(((struct c_common_identifier *) (id))->rid_code)
+
+/* Identifier part common to the C front ends.  Inherits from
+   tree_identifier, despite appearances.  */
+struct c_common_identifier
+{
+  struct tree_common common;
+  struct cpp_hashnode node;
+  ENUM_BITFIELD(rid) rid_code: CHAR_BIT;
+};
+
 #define wchar_type_node			c_global_trees[CTI_WCHAR_TYPE]
 #define signed_wchar_type_node		c_global_trees[CTI_SIGNED_WCHAR_TYPE]
 #define unsigned_wchar_type_node	c_global_trees[CTI_UNSIGNED_WCHAR_TYPE]
diff --git a/gcc/c-lang.c b/gcc/c-lang.c
index 22c9810..cb60002 100644
--- a/gcc/c-lang.c
+++ b/gcc/c-lang.c
@@ -59,7 +59,10 @@ c_post_options ()
 static void
 c_init_options ()
 {
-  parse_in = cpp_create_reader (CLK_GNUC89);
+  /* Make identifier nodes long enough for the language-specific slots.  */
+  set_identifier_size (sizeof (struct lang_identifier));
+
+  parse_in = cpp_create_reader (ident_hash, CLK_GNUC89);
 
   /* Mark as "unspecified".  */
   flag_bounds_check = -1;
diff --git a/gcc/c-lex.c b/gcc/c-lex.c
index 5585a16..bb09b88 100644
--- a/gcc/c-lex.c
+++ b/gcc/c-lex.c
@@ -997,7 +997,12 @@ c_lex (value)
       goto retry;
       
     case CPP_NAME:
-      *value = get_identifier ((const char *) NODE_NAME (tok.val.node));
+      {
+	tree node = HT_IDENT_TO_GCC_IDENT (HT_NODE (tok.val.node));
+	if (TREE_CODE (node) != IDENTIFIER_NODE)
+	  make_identifier (node);
+	*value = node;
+      }
       break;
 
     case CPP_INT:
diff --git a/gcc/c-pragma.h b/gcc/c-pragma.h
index 5e86745..e6af073 100644
--- a/gcc/c-pragma.h
+++ b/gcc/c-pragma.h
@@ -61,7 +61,7 @@ extern void init_pragma PARAMS ((void));
 
 /* Duplicate prototypes for the register_pragma stuff and the typedef for
    cpp_reader, to avoid dragging cpplib.h in almost everywhere... */
-#ifndef __GCC_CPPLIB__
+#ifndef GCC_CPPLIB_H
 typedef struct cpp_reader cpp_reader;
 
 extern void cpp_register_pragma PARAMS ((cpp_reader *,
diff --git a/gcc/c-tree.h b/gcc/c-tree.h
index c34bd9c..a33d64d 100644
--- a/gcc/c-tree.h
+++ b/gcc/c-tree.h
@@ -36,10 +36,9 @@ Boston, MA 02111-1307, USA.  */
 
 struct lang_identifier
 {
-  struct tree_identifier ignore;
+  struct c_common_identifier ignore;
   tree global_value, local_value, label_value, implicit_decl;
   tree error_locus, limbo_value;
-  enum rid rid_code;
 };
 
 /* Wrapping c_lang_decl in another struct is an unfortunate
@@ -98,8 +97,6 @@ struct lang_decl
    and C_RID_YYCODE is the token number wanted by Yacc.  */
 
 #define C_IS_RESERVED_WORD(id) TREE_LANG_FLAG_0 (id)
-#define C_RID_CODE(id) \
-  (((struct lang_identifier *) (id))->rid_code)
 
 /* In a RECORD_TYPE, a sorted array of the fields of the type.  */
 struct lang_type
diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index c2efbdf..233f804 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,10 @@
+2001-05-20  Neil Booth  <neil@daikokuya.demon.co.uk>
+
+	* 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.
+
 2001-05-18  Diego Novillo  <dnovillo@redhat.com>
 
 	* decl2.c (finish_objects): Use the original SYMBOL_REF from the
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 1735042..d0b34c9 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -270,13 +270,12 @@ extern int flag_huge_objects;
 
 struct lang_identifier
 {
-  struct tree_identifier ignore;
+  struct c_common_identifier ignore;
   tree namespace_bindings;
   tree bindings;
   tree class_value;
   tree class_template_info;
   struct lang_id2 *x;
-  enum rid rid_code;
 };
 
 /* In an IDENTIFIER_NODE, nonzero if this identifier is actually a
@@ -284,12 +283,9 @@ struct lang_identifier
    and C_RID_YYCODE is the token number wanted by Yacc.  */
 
 #define C_IS_RESERVED_WORD(id) TREE_LANG_FLAG_5 (id)
-#define C_RID_CODE(id) \
-  (((struct lang_identifier *) (id))->rid_code)
 
 extern const short rid_to_yy[RID_MAX];
-#define C_RID_YYCODE(id) \
-  rid_to_yy[((struct lang_identifier *) (id))->rid_code]
+#define C_RID_YYCODE(id) rid_to_yy[C_RID_CODE (id)]
 
 #define LANG_IDENTIFIER_CAST(NODE) \
 	((struct lang_identifier*)IDENTIFIER_NODE_CHECK (NODE))
@@ -1878,7 +1874,7 @@ struct lang_decl
   } u2;
 };
 
-#define DEFARG_POINTER(NODE) (DEFAULT_ARG_CHECK(NODE)->identifier.pointer)
+#define DEFARG_POINTER(NODE) (DEFAULT_ARG_CHECK(NODE)->identifier.id.str)
 
 /* Non-zero if NODE is a _DECL with TREE_READONLY set.  */
 #define TREE_READONLY_DECL_P(NODE) \
diff --git a/gcc/cp/lex.c b/gcc/cp/lex.c
index ac4c854..c466a73 100644
--- a/gcc/cp/lex.c
+++ b/gcc/cp/lex.c
@@ -258,7 +258,10 @@ cxx_post_options ()
 static void
 cxx_init_options ()
 {
-  parse_in = cpp_create_reader (CLK_GNUCXX);
+  /* Make identifier nodes long enough for the language-specific slots.  */
+  set_identifier_size (sizeof (struct lang_identifier));
+
+  parse_in = cpp_create_reader (ident_hash, CLK_GNUCXX);
 
   /* Default exceptions on.  */
   flag_exceptions = 1;
@@ -696,8 +699,6 @@ const char *
 init_parse (filename)
      const char *filename;
 {
-  /* Make identifier nodes long enough for the language-specific slots.  */
-  set_identifier_size (sizeof (struct lang_identifier));
   decl_printable_name = lang_printable_name;
 
   input_filename = "<internal>";
diff --git a/gcc/cpphash.c b/gcc/cpphash.c
index a47a635..9383c27 100644
--- a/gcc/cpphash.c
+++ b/gcc/cpphash.c
@@ -1,4 +1,4 @@
-/* Part of CPP library.  (Identifier and string tables.)
+/* Hash tables for the CPP library.
    Copyright (C) 1986, 1987, 1989, 1992, 1993, 1994, 1995, 1996, 1998,
    1999, 2000 Free Software Foundation, Inc.
    Written by Per Bothner, 1994.
@@ -27,266 +27,95 @@ Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 #include "system.h"
 #include "cpplib.h"
 #include "cpphash.h"
-#include "obstack.h"
 
-#define obstack_chunk_alloc xmalloc
-#define obstack_chunk_free free
+static cpp_hashnode *alloc_node PARAMS ((hash_table *));
 
-/* Initial hash table size.  (It can grow if necessary.)  This is the
-   largest prime number smaller than 2**12. */
-#define HASHSIZE 4093
+/* Return an identifier node for hashtable.c.  Used by cpplib except
+   when integrated with the C front ends.  */
 
-/* This is the structure used for the hash table.  */
-struct htab
+static cpp_hashnode *
+alloc_node (table)
+     hash_table *table;
 {
-  struct cpp_hashnode **entries;
-  size_t size;
-  size_t nelts;
-};
-
-static void expand_hash PARAMS ((struct htab *));
-static unsigned long higher_prime_number PARAMS ((unsigned long));
-
-/* Set up and tear down internal structures for macro expansion.  */
-void
-_cpp_init_hashtable (pfile)
-     cpp_reader *pfile;
-{
-  pfile->hash_ob = xnew (struct obstack);
-  obstack_init (pfile->hash_ob);
-
-  pfile->hashtab = xobnew (pfile->hash_ob, struct htab);
-
-  pfile->hashtab->nelts = 0;
-  pfile->hashtab->size = HASHSIZE;
-  pfile->hashtab->entries = xcnewvec (cpp_hashnode *, HASHSIZE);
+  cpp_hashnode *node;
+  
+  node = obstack_alloc (&table->pfile->hash_ob, sizeof (cpp_hashnode));
+  memset ((PTR) node, 0, sizeof (cpp_hashnode));
+  return node;
 }
 
+/* Set up the identifier hash table.  Use TABLE if non-null, otherwise
+   create our own.  */
+
 void
-_cpp_cleanup_hashtable (pfile)
+_cpp_init_hashtable (pfile, table)
      cpp_reader *pfile;
+     hash_table *table;
 {
-  cpp_hashnode **p, **limit;
-
-  p = pfile->hashtab->entries;
-  limit = p + pfile->hashtab->size;
-  do
+  if (table == NULL)
     {
-      if (*p)
-	_cpp_free_definition (*p);
+      pfile->our_hashtable = 1;
+      table = ht_create (13);	/* 8K (=2^13) entries.  */
+      table->alloc_node = (hashnode (*) PARAMS ((hash_table *))) alloc_node;
+      gcc_obstack_init (&pfile->hash_ob);
     }
-  while (++p < limit);
 
-  free (pfile->hashtab->entries);
-  obstack_free (pfile->hash_ob, 0);
-  free (pfile->hash_ob);
+  table->pfile = pfile;
+  pfile->hash_table = table;
 }
 
-/* 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.  */
+/* Tear down the identifier hash table.  */
 
-cpp_hashnode *
-cpp_lookup (pfile, name, len)
+void
+_cpp_destroy_hashtable (pfile)
      cpp_reader *pfile;
-     const U_CHAR *name;
-     size_t len;
 {
-  size_t n = len;
-  unsigned int r = 0;
-  const U_CHAR *str = name;
-  U_CHAR *dest = _cpp_pool_reserve (&pfile->ident_pool, len + 1);
-
-  do
+  if (pfile->our_hashtable)
     {
-      r = HASHSTEP (r, *str);
-      *dest++ = *str++;
+      free (pfile->hash_table);
+      obstack_free (&pfile->hash_ob, 0);
     }
-  while (--n);
-  *dest = '\0';
-
-  return _cpp_lookup_with_hash (pfile, len, r);
 }
 
-/* NAME is a null-terminated identifier of length len.  It is assumed
-   to have been placed at the front of the identifier pool.  */
+/* Returns the hash entry for the STR of length LEN, creating one
+   if necessary.  */
+
 cpp_hashnode *
-_cpp_lookup_with_hash (pfile, len, hash)
+cpp_lookup (pfile, str, len)
      cpp_reader *pfile;
-     size_t len;
-     unsigned int hash;
-{
-  unsigned int index;
-  size_t size;
-  cpp_hashnode *entry;
-  cpp_hashnode **entries;
-  unsigned char *name = POOL_FRONT (&pfile->ident_pool);
-
-  entries = pfile->hashtab->entries;
-  size = pfile->hashtab->size;
-
-  hash += len;
-  index = hash % size;
-
-  entry = entries[index];
-  if (entry)
-    {
-      unsigned int hash2;
-
-      if (entry->hash == hash && NODE_LEN (entry) == len
-	  && !memcmp (NODE_NAME (entry), name, len))
-	return entry;
-
-      hash2 = 1 + hash % (size - 2);
-
-      for (;;)
-	{
-	  index += hash2;
-	  if (index >= size)
-	    index -= size;
-	  entry = entries[index];
-
-	  if (entry == NULL)
-	    break;
-	  if (entry->hash == hash && NODE_LEN (entry) == len
-	      && !memcmp (NODE_NAME (entry), name, len))
-	    return entry;
-	}
-    }
-
-  /* Commit the memory for the identifier.  */
-  POOL_COMMIT (&pfile->ident_pool, len + 1);
-
-  /* Create a new hash node and insert it in the table.  */
-  entries[index] = obstack_alloc (pfile->hash_ob, sizeof (cpp_hashnode));
-
-  entry = entries[index];
-  entry->type = NT_VOID;
-  entry->flags = 0;
-  entry->directive_index = 0;
-  entry->arg_index = 0;
-  NODE_LEN (entry) = len;
-  entry->hash = hash;
-  NODE_NAME (entry) = name;
-  entry->value.macro = 0;
-
-  pfile->hashtab->nelts++;
-  if (size * 3 <= pfile->hashtab->nelts * 4)
-    expand_hash (pfile->hashtab);
-
-  return entry;
-}
-
-static void
-expand_hash (htab)
-     struct htab *htab;
+     const unsigned char *str;
+     unsigned int len;
 {
-  cpp_hashnode **oentries;
-  cpp_hashnode **olimit;
-  cpp_hashnode **p;
-  size_t size;
-
-  oentries = htab->entries;
-  olimit = oentries + htab->size;
-
-  htab->size = size = higher_prime_number (htab->size * 2);
-  htab->entries = xcnewvec (cpp_hashnode *, size);
-
-  for (p = oentries; p < olimit; p++)
-    {
-      if (*p != NULL)
-	{
-	  unsigned int index;
-	  unsigned int hash, hash2;
-	  cpp_hashnode *entry = *p;
-
-	  hash = entry->hash;
-	  index = hash % size;
-
-	  if (htab->entries[index] == NULL)
-	    {
-	    insert:
-	      htab->entries[index] = entry;
-	      continue;
-	    }
-
-	  hash2 = 1 + hash % (size - 2);
-	  for (;;)
-	    {
-	      index += hash2;
-	      if (index >= size)
-		index -= size;
-
-	      if (htab->entries[index] == NULL)
-		goto insert;
-	    }
-	}
-    }
-
-  free (oentries);
+  /* ht_lookup cannot return NULL.  */
+  return CPP_HASHNODE (ht_lookup (pfile->hash_table, str, len, HT_ALLOC));
 }
 
-/* The following function returns the nearest prime number which is
-   greater than a given source number, N. */
+/* Determine whether the str STR, of length LEN, is a defined macro.  */
 
-static unsigned long
-higher_prime_number (n)
-     unsigned long n;
+int
+cpp_defined (pfile, str, len)
+     cpp_reader *pfile;
+     const unsigned char *str;
+     int len;
 {
-  unsigned long i;
-
-  /* Ensure we have a larger number and then force to odd.  */
-  n++;  
-  n |= 0x01; 
+  cpp_hashnode *node;
 
-  /* All odd numbers < 9 are prime.  */
-  if (n < 9)
-    return n;
+  node = CPP_HASHNODE (ht_lookup (pfile->hash_table, str, len, HT_NO_INSERT));
 
-  /* Otherwise find the next prime using a sieve.  */
-
- next:
-  for (i = 3; i * i <= n; i += 2)
-    if (n % i == 0)
-      {
-	 n += 2;
-	 goto next;
-       }
-
-  return n;
+  /* If it's of type NT_MACRO, it cannot be poisoned.  */
+  return node && node->type == NT_MACRO;
 }
 
+/* For all nodes in the hashtable, callback CB with parameters PFILE,
+   the node, and V.  */
+
 void
 cpp_forall_identifiers (pfile, cb, v)
      cpp_reader *pfile;
-     int (*cb) PARAMS ((cpp_reader *, cpp_hashnode *, void *));
-     void *v;
+     cpp_cb cb;
+     PTR v;
 {
-    cpp_hashnode **p, **limit;
-
-  p = pfile->hashtab->entries;
-  limit = p + pfile->hashtab->size;
-  do
-    {
-      if (*p)
-	if ((*cb) (pfile, *p, v) == 0)
-	  break;
-    }
-  while (++p < limit);
-}
-
-/* Determine whether the identifier ID, of length LEN, is a defined macro.  */
-int
-cpp_defined (pfile, id, len)
-     cpp_reader *pfile;
-     const U_CHAR *id;
-     int len;
-{
-  cpp_hashnode *hp = cpp_lookup (pfile, id, len);
-
-  /* If it's of type NT_MACRO, it cannot be poisoned.  */
-  return hp->type == NT_MACRO;
+  /* We don't need a proxy since the hash table's identifier comes
+     first in cpp_hashnode.  */
+  ht_forall (pfile->hash_table, (ht_cb) cb, v);
 }
diff --git a/gcc/cpphash.h b/gcc/cpphash.h
index cf027f0..17438c7 100644
--- a/gcc/cpphash.h
+++ b/gcc/cpphash.h
@@ -19,11 +19,12 @@ Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
    that need to be visible across files.  It's called cpphash.h for
    historical reasons.  */
 
-#ifndef __GCC_CPPHASH__
-#define __GCC_CPPHASH__
+#ifndef GCC_CPPHASH_H
+#define GCC_CPPHASH_H
 
-struct directive;		/* These are deliberately incomplete.  */
-struct htab;
+#include "hashtable.h"
+
+struct directive;		/* Deliberately incomplete.  */
 
 /* Test if a sign is valid within a preprocessing number.  */
 #define VALID_SIGN(c, prevc) \
@@ -299,9 +300,6 @@ struct cpp_reader
   /* Current depth in #include directives.  */
   unsigned int include_depth;
 
-  /* Hash table of macros and assertions.  See cpphash.c.  */
-  struct htab *hashtab;
-
   /* Tree of other included files.  See cppfiles.c.  */
   struct splay_tree_s *all_include_files;
 
@@ -318,11 +316,11 @@ struct cpp_reader
 
   /* Obstack holding all macro hash nodes.  This never shrinks.
      See cpphash.c */
-  struct obstack *hash_ob;
+  struct obstack hash_ob;
 
   /* Obstack holding buffer and conditional structures.  This is a
-     real stack.  See cpplib.c */
-  struct obstack *buffer_ob;
+     real stack.  See cpplib.c.  */
+  struct obstack buffer_ob;
 
   /* Pragma table - dynamic, because a library user can add to the
      list of recognized pragmas.  */
@@ -331,6 +329,9 @@ struct cpp_reader
   /* Call backs.  */
   struct cpp_callbacks cb;
 
+  /* Identifier hash table.  */ 
+  struct ht *hash_table;
+
   /* User visible options.  */
   struct cpp_options opts;
 
@@ -347,6 +348,9 @@ struct cpp_reader
   /* Whether to print our version number.  Done this way so
      we don't get it twice for -v -version.  */
   unsigned char print_version;
+
+  /* Whether cpplib owns the hashtable.  */
+  unsigned char our_hashtable;
 };
 
 /* Character classes.  Based on the more primitive macros in safe-ctype.h.
@@ -384,10 +388,6 @@ extern unsigned char _cpp_trigraph_map[UCHAR_MAX + 1];
 #define CPP_PEDANTIC(PF) CPP_OPTION (PF, pedantic)
 #define CPP_WTRADITIONAL(PF) CPP_OPTION (PF, warn_traditional)
 
-/* Hash step.  The hash calculation is duplicated in cpp_lookup and
-   parse_name.  */
-#define HASHSTEP(r, c) ((r) * 67 + (c - 113));
-
 /* In cpperror.c  */
 enum error_type { WARNING = 0, WARNING_SYSHDR, PEDWARN, ERROR, FATAL, ICE };
 extern int _cpp_begin_message PARAMS ((cpp_reader *, enum error_type,
@@ -403,10 +403,8 @@ extern void _cpp_push_token		PARAMS ((cpp_reader *, const cpp_token *,
 						 const cpp_lexer_pos *));
 
 /* In cpphash.c */
-extern void _cpp_init_hashtable		PARAMS ((cpp_reader *));
-extern void _cpp_cleanup_hashtable	PARAMS ((cpp_reader *));
-extern cpp_hashnode *_cpp_lookup_with_hash PARAMS ((cpp_reader*, size_t,
-						    unsigned int));
+extern void _cpp_init_hashtable		PARAMS ((cpp_reader *, hash_table *));
+extern void _cpp_destroy_hashtable	PARAMS ((cpp_reader *));
 
 /* In cppfiles.c */
 extern void _cpp_fake_include		PARAMS ((cpp_reader *, const char *));
@@ -445,8 +443,7 @@ extern int _cpp_test_assertion PARAMS ((cpp_reader *, int *));
 extern int _cpp_handle_directive PARAMS ((cpp_reader *, int));
 extern void _cpp_define_builtin	PARAMS ((cpp_reader *, const char *));
 extern void _cpp_do__Pragma	PARAMS ((cpp_reader *));
-extern void _cpp_init_stacks	PARAMS ((cpp_reader *));
-extern void _cpp_cleanup_stacks	PARAMS ((cpp_reader *));
+extern void _cpp_init_directives PARAMS ((cpp_reader *));
 extern void _cpp_init_internal_pragmas PARAMS ((cpp_reader *));
 extern void _cpp_do_file_change PARAMS ((cpp_reader *, enum cpp_fc_reason,
 					 const char *, unsigned int));
@@ -517,4 +514,4 @@ ufputs (s, f)
   return fputs ((const char *)s, f);
 }
 
-#endif
+#endif /* GCC_CPPHASH_H */
diff --git a/gcc/cppinit.c b/gcc/cppinit.c
index fc15db4..fda406b 100644
--- a/gcc/cppinit.c
+++ b/gcc/cppinit.c
@@ -491,7 +491,8 @@ init_library ()
 
 /* Initialize a cpp_reader structure. */
 cpp_reader *
-cpp_create_reader (lang)
+cpp_create_reader (table, lang)
+     hash_table *table;
      enum c_lang lang;
 {
   struct spec_nodes *s;
@@ -536,8 +537,13 @@ cpp_create_reader (lang)
   /* Macro pool initially 8K.  Aligned, permanent pool.  */
   _cpp_init_pool (&pfile->macro_pool, 8 * 1024, 0, 0);
 
-  _cpp_init_hashtable (pfile);
-  _cpp_init_stacks (pfile);
+  /* Initialise the buffer obstack.  */
+  gcc_obstack_init (&pfile->buffer_ob);
+
+  /* Initialise the hashtable.  */
+  _cpp_init_hashtable (pfile, table);
+
+  _cpp_init_directives (pfile);
   _cpp_init_includes (pfile);
   _cpp_init_internal_pragmas (pfile);
 
@@ -577,11 +583,10 @@ cpp_destroy (pfile)
     }
 
   deps_free (pfile->deps);
+  obstack_free (&pfile->buffer_ob, 0);
 
+  _cpp_destroy_hashtable (pfile);
   _cpp_cleanup_includes (pfile);
-  _cpp_cleanup_stacks (pfile);
-  _cpp_cleanup_hashtable (pfile);
-
   _cpp_free_lookaheads (pfile);
 
   _cpp_free_pool (&pfile->ident_pool);
diff --git a/gcc/cpplex.c b/gcc/cpplex.c
index 30f739d..290d339 100644
--- a/gcc/cpplex.c
+++ b/gcc/cpplex.c
@@ -479,22 +479,14 @@ parse_identifier (pfile, c)
 {
   cpp_hashnode *result;
   cpp_buffer *buffer = pfile->buffer;
-  unsigned char *dest, *limit;
-  unsigned int r = 0, saw_dollar = 0;
-
-  dest = POOL_FRONT (&pfile->ident_pool);
-  limit = POOL_LIMIT (&pfile->ident_pool);
+  unsigned int saw_dollar = 0, len;
+  struct obstack *stack = &pfile->hash_table->stack;
 
   do
     {
       do
 	{
-	  /* Need room for terminating null.  */
-	  if (dest + 1 >= limit)
-	    limit = _cpp_next_chunk (&pfile->ident_pool, 0, &dest);
-
-	  *dest++ = c;
-	  r = HASHSTEP (r, c);
+	  obstack_1grow (stack, c);
 
 	  if (c == '$')
 	    saw_dollar++;
@@ -524,11 +516,12 @@ parse_identifier (pfile, c)
     cpp_pedwarn (pfile, "'$' character(s) in identifier");
 
   /* Identifiers are null-terminated.  */
-  *dest = '\0';
+  len = obstack_object_size (stack);
+  obstack_1grow (stack, '\0');
 
   /* This routine commits the memory if necessary.  */
-  result = _cpp_lookup_with_hash (pfile,
-				  dest - POOL_FRONT (&pfile->ident_pool), r);
+  result = (cpp_hashnode *)
+    ht_lookup (pfile->hash_table, obstack_finish (stack), len, HT_ALLOCED);
 
   /* Some identifiers require diagnostics when lexed.  */
   if (result->flags & NODE_DIAGNOSTIC && !pfile->skipping)
@@ -1905,7 +1898,8 @@ cpp_interpret_charconst (pfile, token, warn_multi, traditional, pchars_seen)
   const unsigned char *limit = str + token->val.str.len;
   unsigned int chars_seen = 0;
   unsigned int width, max_chars, c;
-  HOST_WIDE_INT result = 0, mask;
+  unsigned HOST_WIDE_INT mask;
+  HOST_WIDE_INT result = 0;
 
 #ifdef MULTIBYTE_CHARS
   (void) local_mbtowc (NULL, NULL, 0);
diff --git a/gcc/cpplib.c b/gcc/cpplib.c
index b5bdd94..96d296f 100644
--- a/gcc/cpplib.c
+++ b/gcc/cpplib.c
@@ -1043,12 +1043,12 @@ do_pragma (pfile)
   if (tok.type == CPP_NAME)
     {
       const cpp_hashnode *node = tok.val.node;
-      const U_CHAR *name = NODE_NAME (node);
       size_t len = NODE_LEN (node);
 
       while (p)
 	{
-	  if (strlen (p->name) == len && !memcmp (p->name, name, len))
+	  if (strlen (p->name) == len
+	      && !memcmp (p->name, NODE_NAME (node), len))
 	    {
 	      if (p->isnspace)
 		{
@@ -1403,7 +1403,7 @@ do_endif (pfile)
 
       buffer->if_stack = ifs->next;
       buffer->was_skipping = ifs->was_skipping;
-      obstack_free (pfile->buffer_ob, ifs);
+      obstack_free (&pfile->buffer_ob, ifs);
     }
 
   check_eol (pfile);
@@ -1423,7 +1423,7 @@ push_conditional (pfile, skip, type, cmacro)
   struct if_stack *ifs;
   cpp_buffer *buffer = pfile->buffer;
 
-  ifs = xobnew (pfile->buffer_ob, struct if_stack);
+  ifs = xobnew (&pfile->buffer_ob, struct if_stack);
   ifs->pos = pfile->directive_pos;
   ifs->next = buffer->if_stack;
   ifs->was_skipping = buffer->was_skipping;
@@ -1804,7 +1804,7 @@ cpp_push_buffer (pfile, buffer, len, type, filename)
      enum cpp_buffer_type type;
      const char *filename;
 {
-  cpp_buffer *new = xobnew (pfile->buffer_ob, cpp_buffer);
+  cpp_buffer *new = xobnew (&pfile->buffer_ob, cpp_buffer);
 
   if (type == BUF_FAKE)
     {
@@ -1905,22 +1905,17 @@ cpp_pop_buffer (pfile)
 		   buffer->nominal_fname);
     }
 
-  obstack_free (pfile->buffer_ob, buffer);
+  obstack_free (&pfile->buffer_ob, buffer);
   return pfile->buffer;
 }
 
-#define obstack_chunk_alloc xmalloc
-#define obstack_chunk_free free
 void
-_cpp_init_stacks (pfile)
+_cpp_init_directives (pfile)
      cpp_reader *pfile;
 {
   unsigned int i;
   cpp_hashnode *node;
 
-  pfile->buffer_ob = xnew (struct obstack);
-  obstack_init (pfile->buffer_ob);
-
   /* Register the directives.  */
   for (i = 0; i < (unsigned int) N_DIRECTIVES; i++)
     {
@@ -1928,11 +1923,3 @@ _cpp_init_stacks (pfile)
       node->directive_index = i + 1;
     }
 }
-
-void
-_cpp_cleanup_stacks (pfile)
-     cpp_reader *pfile;
-{
-  obstack_free (pfile->buffer_ob, 0);
-  free (pfile->buffer_ob);
-}
diff --git a/gcc/cpplib.h b/gcc/cpplib.h
index 7730a24..cc42e34 100644
--- a/gcc/cpplib.h
+++ b/gcc/cpplib.h
@@ -20,10 +20,11 @@ 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!  */
-#ifndef __GCC_CPPLIB__
-#define __GCC_CPPLIB__
+#ifndef GCC_CPPLIB_H
+#define GCC_CPPLIB_H
 
 #include <sys/types.h>
+#include "hashtable.h"
 
 #ifdef __cplusplus
 extern "C" {
@@ -45,6 +46,7 @@ typedef struct cpp_callbacks cpp_callbacks;
 
 struct answer;
 struct file_name_map_list;
+struct ht;
 
 /* The first two groups, apart from '=', can appear in preprocessor
    expressions.  This allows a lookup table to be implemented in
@@ -177,7 +179,7 @@ struct cpp_token
 
   union
   {
-    struct cpp_hashnode *node;	/* An identifier.  */
+    cpp_hashnode *node;		/* An identifier.  */
     struct cpp_string str;	/* A string, or number.  */
     unsigned int arg_no;	/* Argument no. for a CPP_MACRO_ARG.  */
     unsigned char c;		/* Character represented by CPP_OTHER.  */
@@ -466,18 +468,22 @@ enum builtin_type
   BT_STDC			/* `__STDC__' */
 };
 
-#define NODE_LEN(NODE)		(NODE->len)
-#define NODE_NAME(NODE)		(NODE->name)
+#define CPP_HASHNODE(HNODE)	((cpp_hashnode *) (HNODE))
+#define HT_NODE(NODE)		((ht_identifier *) (NODE))
+#define NODE_LEN(NODE)		HT_LEN (&(NODE)->ident)
+#define NODE_NAME(NODE)		HT_STR (&(NODE)->ident)
 
+/* The common part of an identifier node shared amongst all 3 C front
+   ends.  Also used to store CPP identifiers, which are a superset of
+   identifiers in the grammatical sense.  */
 struct cpp_hashnode
 {
-  const unsigned char *name;		/* Null-terminated name.  */
-  unsigned int hash;			/* Cached hash value.  */
-  unsigned short len;			/* Length of name excluding null.  */
+  struct ht_identifier ident;
   unsigned short arg_index;		/* Macro argument index.  */
   unsigned char directive_index;	/* Index into directive table.  */
-  ENUM_BITFIELD(node_type) type : 8;	/* Node type.  */
-  unsigned char flags;			/* Node flags.  */
+  unsigned char rid_code;		/* Rid code - for front ends.  */
+  ENUM_BITFIELD(node_type) type : 8;	/* CPP node type.  */
+  unsigned char flags;			/* CPP flags.  */
 
   union
   {
@@ -488,8 +494,12 @@ struct cpp_hashnode
   } value;
 };
 
-/* Call this first to get a handle to pass to other functions.  */
-extern cpp_reader *cpp_create_reader PARAMS ((enum c_lang));
+/* Call this first to get a handle to pass to other functions.  If you
+   want cpplib to manage its own hashtable, pass in a NULL pointer.
+   Or you can pass in an initialised hash table that cpplib will use;
+   this technique is used by the C front ends.  */
+extern cpp_reader *cpp_create_reader PARAMS ((struct ht *,
+					      enum c_lang));
 
 /* Call this to release the handle.  Any use of the handle after this
    function returns is invalid.  Returns cpp_errors (pfile).  */
@@ -593,13 +603,16 @@ extern void cpp_output_token		PARAMS ((const cpp_token *, FILE *));
 extern const char *cpp_type2name	PARAMS ((enum cpp_ttype));
 
 /* In cpphash.c */
+
+/* Lookup an identifier in the hashtable.  Puts the identifier in the
+   table if it is not already there.  */
 extern cpp_hashnode *cpp_lookup		PARAMS ((cpp_reader *,
-						 const unsigned char *, size_t));
+						 const unsigned char *,
+						 unsigned int));
+
+typedef int (*cpp_cb) PARAMS ((cpp_reader *, cpp_hashnode *, void *));
 extern void cpp_forall_identifiers	PARAMS ((cpp_reader *,
-						 int (*) PARAMS ((cpp_reader *,
-								  cpp_hashnode *,
-								  void *)),
-						 void *));
+						 cpp_cb, void *));
 
 /* In cppmacro.c */
 extern void cpp_scan_buffer_nooutput	PARAMS ((cpp_reader *, int));
@@ -614,4 +627,4 @@ extern void cpp_make_system_header PARAMS ((cpp_reader *, int, int));
 #ifdef __cplusplus
 }
 #endif
-#endif /* __GCC_CPPLIB__ */
+#endif /* GCC_CPPLIB_H */
diff --git a/gcc/cppmacro.c b/gcc/cppmacro.c
index 1dc902f..40c6176 100644
--- a/gcc/cppmacro.c
+++ b/gcc/cppmacro.c
@@ -1536,7 +1536,8 @@ check_trad_stringification (pfile, macro, string)
 	{
 	  const cpp_hashnode *node = macro->params[i];
 
-	  if (NODE_LEN (node) == len && !memcmp (p, NODE_NAME (node), len))
+	  if (NODE_LEN (node) == len
+	      && !memcmp (p, NODE_NAME (node), len))
 	    {
 	      cpp_warning (pfile,
 	   "macro argument \"%s\" would be stringified with -traditional.",
diff --git a/gcc/cppmain.c b/gcc/cppmain.c
index 0ae2c67..0c5dc3d 100644
--- a/gcc/cppmain.c
+++ b/gcc/cppmain.c
@@ -74,7 +74,7 @@ main (argc, argv)
   general_init (argv[0]);
 
   /* Contruct a reader with default language GNU C89.  */
-  pfile = cpp_create_reader (CLK_GNUC89);
+  pfile = cpp_create_reader (NULL, CLK_GNUC89);
   options = cpp_get_options (pfile);
   
   do_preprocessing (argc, argv);
diff --git a/gcc/fix-header.c b/gcc/fix-header.c
index d2e7f78..8d80128 100644
--- a/gcc/fix-header.c
+++ b/gcc/fix-header.c
@@ -621,7 +621,7 @@ read_scan_file (in_fname, argc, argv)
 
   obstack_init (&scan_file_obstack); 
 
-  scan_in = cpp_create_reader (CLK_GNUC89);
+  scan_in = cpp_create_reader (NULL, CLK_GNUC89);
   cb = cpp_get_callbacks (scan_in);
   cb->file_change = cb_file_change;
 
diff --git a/gcc/flags.h b/gcc/flags.h
index d637826..92492ac 100644
--- a/gcc/flags.h
+++ b/gcc/flags.h
@@ -146,7 +146,7 @@ extern int warn_cast_align;
    characters.  The value N is in `id_clash_len'.  */
 
 extern int warn_id_clash;
-extern int id_clash_len;
+extern unsigned int id_clash_len;
 
 /* Nonzero means warn about any objects definitions whose size is larger
    than N bytes.  Also want about function definitions whose returned
diff --git a/gcc/ggc.h b/gcc/ggc.h
index 91bd137..2d214a9 100644
--- a/gcc/ggc.h
+++ b/gcc/ggc.h
@@ -84,6 +84,13 @@ extern void ggc_mark_rtvec_children PARAMS ((struct rtvec_def *));
       VARRAY_PUSH_TREE (ggc_pending_trees, t__);	\
   } while (0)
 
+#define ggc_mark_nonnull_tree(EXPR)			\
+  do {							\
+    tree t__ = (EXPR);					\
+    if (! ggc_set_mark (t__))				\
+      VARRAY_PUSH_TREE (ggc_pending_trees, t__);	\
+  } while (0)
+
 #define ggc_mark_rtvec(EXPR)                    \
   do {                                          \
     rtvec v__ = (EXPR);                         \
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;
+}
diff --git a/gcc/hashtable.h b/gcc/hashtable.h
new file mode 100644
index 0000000..5b08fde
--- /dev/null
+++ b/gcc/hashtable.h
@@ -0,0 +1,85 @@
+/* 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.  */
+
+#ifndef GCC_HASHTABLE_H
+#define GCC_HASHTABLE_H
+
+#include "obstack.h"
+
+/* This is what each hash table entry points to.  It may be embedded
+   deeply within another object.  */
+typedef struct ht_identifier ht_identifier;
+struct ht_identifier
+{
+  unsigned int len;
+  const unsigned char *str;
+};
+
+#define HT_LEN(NODE) ((NODE)->len)
+#define HT_STR(NODE) ((NODE)->str)
+
+/* We want code outside cpplib, such as the compiler front-ends, to be
+   able to include this header, and to be able to link with
+   cpphashtbl.o without pulling in any other parts of cpplib.  */
+
+struct cpp_reader;
+typedef struct ht hash_table;
+typedef struct ht_identifier *hashnode;
+
+enum ht_lookup_option {HT_NO_INSERT = 0, HT_ALLOC, HT_ALLOCED};
+
+/* An identifier hash table for cpplib and the front ends.  */
+struct ht
+{
+  /* Identifiers are allocated from here.  */
+  struct obstack stack;
+
+  hashnode *entries;
+  /* Call back.  */
+  hashnode (*alloc_node) PARAMS ((hash_table *));
+
+  unsigned int nslots;		/* Total slots in the entries array.  */
+  unsigned int nelements;	/* Number of live elements.  */
+
+  /* Link to reader, if any.  For the benefit of cpplib.  */
+  struct cpp_reader *pfile;
+
+  /* Table usage statistics.  */
+  unsigned int searches;
+  unsigned int collisions;
+};
+
+extern void gcc_obstack_init PARAMS ((struct obstack *));
+/* Initialise the hashtable with 2 ^ order entries.  */
+extern hash_table *ht_create PARAMS ((unsigned int order));
+extern hashnode ht_lookup PARAMS ((hash_table *, const unsigned char *,
+				   unsigned int, enum ht_lookup_option));
+
+/* For all nodes in TABLE, make a callback.  The callback takes
+   TABLE->PFILE, the node, and a PTR, and the callback sequence stops
+   if the callback returns zero.  */
+typedef int (*ht_cb) PARAMS ((struct cpp_reader *, hashnode, const void *));
+extern void ht_forall PARAMS ((hash_table *, ht_cb, const void *));
+
+/* Dump allocation statistics to stderr.  */
+extern void ht_dump_statistics PARAMS ((hash_table *));
+
+/* Approximate positive square root of a host double.  This is for
+   statistical reports, not code generation.  */
+extern double approx_sqrt PARAMS ((double));
+
+#endif /* GCC_HASHTABLE_H */
diff --git a/gcc/objc/objc-act.c b/gcc/objc/objc-act.c
index 6f04357..81e1619 100644
--- a/gcc/objc/objc-act.c
+++ b/gcc/objc/objc-act.c
@@ -727,7 +727,10 @@ generate_struct_by_value_array ()
 static void
 objc_init_options ()
 {
-  parse_in = cpp_create_reader (CLK_OBJC);
+  /* Make identifier nodes long enough for the language-specific slots.  */
+  set_identifier_size (sizeof (struct lang_identifier));
+
+  parse_in = cpp_create_reader (ident_hash, CLK_OBJC);
   c_language = clk_objective_c;
 }
 
diff --git a/gcc/stringpool.c b/gcc/stringpool.c
index 0346dcf..6d44005 100644
--- a/gcc/stringpool.c
+++ b/gcc/stringpool.c
@@ -1,5 +1,5 @@
 /* String pool for GCC.
-   Copyright (C) 2000 Free Software Foundation, Inc.
+   Copyright (C) 2000, 2001 Free Software Foundation, Inc.
 
 This file is part of GNU CC.
 
@@ -18,25 +18,25 @@ along with GNU CC; see the file COPYING.  If not, write to the Free
 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 02111-1307, USA.  */
 
-/* String pool allocator.  All strings allocated by ggc_alloc_string are
-   uniquified and stored in an obstack which is never shrunk.  You can
-   associate a tree with a string if you wish; this is used to implement
-   get_identifier.
+/* String text, identifer text and identifier node allocator.  Strings
+   allocated by ggc_alloc_string are stored in an obstack which is
+   never shrunk.  Identifiers are uniquely stored in a hash table.
 
-   We have our own private hash table implementation which is similar
-   to the one in cpphash.c (actually, it's a further refinement of
-   that code).  libiberty's hashtab.c is not used because it requires
-   100% average space overhead per string, which is unacceptable.
-   Also, this algorithm is faster.  */
+   We have our own private hash table implementation.  libiberty's
+   hashtab.c is not used because it requires 100% average space
+   overhead per string, which is unacceptable.  Also, this algorithm
+   is faster.  */
 
 #include "config.h"
 #include "system.h"
 #include "ggc.h"
 #include "tree.h"
-#include "obstack.h"
+#include "hashtable.h"
 #include "flags.h"
 #include "toplev.h"
 
+#define IS_FE_IDENT(NODE) (TREE_CODE (NODE) == IDENTIFIER_NODE)
+
 /* The "" allocated string.  */
 const char empty_string[] = "";
 
@@ -47,194 +47,33 @@ const char digit_vector[] = {
   '5', 0, '6', 0, '7', 0, '8', 0, '9', 0
 };
 
+struct ht *ident_hash;
 static struct obstack string_stack;
-
-/* Each hashnode is just a pointer to a TREE_IDENTIFIER.  */
-typedef struct tree_identifier *sp_hashnode;
-
-#define SP_EMPTY(NODE) ((NODE) == NULL)
-#define SP_LEN(NODE) ((NODE)->length)
-#define SP_TREE(NODE) ((tree) NODE)
-#define SP_STR(NODE) ((NODE)->pointer)
-#define SP_VALID(NODE) (TREE_CODE (SP_TREE (NODE)) == IDENTIFIER_NODE)
-
-/* This is the hash table structure.  There's only one.  */
-struct str_hash
-{
-  sp_hashnode *entries;
-  size_t nslots;	/* total slots in the entries array */
-  size_t nelements;	/* number of live elements */
-
-  /* table usage statistics */
-  unsigned int searches;
-  unsigned int collisions;
-};
-#define INITIAL_HASHSIZE (16*1024)
-
-static struct str_hash string_hash = { 0, INITIAL_HASHSIZE, 0, 0, 0 };
-
-enum insert_option { INSERT, NO_INSERT };
-
-static sp_hashnode alloc_ident PARAMS ((const char *, size_t,
-					enum insert_option));
-static inline unsigned int calc_hash PARAMS ((const unsigned char *, size_t));
-static void mark_string_hash PARAMS ((void *));
-static void expand_string_table PARAMS ((void));
-
-/* Convenience macro for iterating over the hash table.  E is set to
-   each live entry in turn.  */
-#define FORALL_IDS(E) \
-for (E = string_hash.entries; E < string_hash.entries+string_hash.nslots; E++) \
-  if (!SP_EMPTY (*E) && SP_VALID (*E))
-
-/* 0 while creating built-in identifiers.  */
 static int do_identifier_warnings;
 
+static hashnode alloc_node PARAMS ((hash_table *));
+static int mark_ident PARAMS ((struct cpp_reader *, hashnode, const PTR));
+static void mark_ident_hash PARAMS ((void *));
+static int scan_for_clashes PARAMS ((struct cpp_reader *, hashnode,
+				     const char *));
+
 /* Initialize the string pool.  */
 void
 init_stringpool ()
 {
+  /* Create with 16K (2^14) entries.  */
+  ident_hash = ht_create (14);
+  ident_hash->alloc_node = alloc_node;
   gcc_obstack_init (&string_stack);
-  ggc_add_root (&string_hash, 1, sizeof string_hash, mark_string_hash);
-
-  /* Strings need no alignment.  */
-  obstack_alignment_mask (&string_stack) = 0;
-
-  string_hash.entries = (sp_hashnode *)
-    xcalloc (string_hash.nslots, sizeof (sp_hashnode));
+  ggc_add_root (&ident_hash, 1, sizeof ident_hash, mark_ident_hash);
 }
 
-/* Enable warnings on similar identifiers (if requested).
-   Done after the built-in identifiers are created.  */
-void
-start_identifier_warnings ()
-{
-  do_identifier_warnings = 1;
-}
-
-/* Record the size of an identifier node for the language in use.
-   SIZE is the total size in bytes.
-   This is called by the language-specific files.  This must be
-   called before allocating any identifiers.  */
-void
-set_identifier_size (size)
-     int size;
+/* Allocate a hash node.  */
+static hashnode
+alloc_node (table)
+     hash_table *table ATTRIBUTE_UNUSED;
 {
-  tree_code_length[(int) IDENTIFIER_NODE]
-    = (size - sizeof (struct tree_common)) / sizeof (tree);
-}
-
-/* Calculate the hash of the string STR, which is of length LEN.  */
-static inline unsigned int
-calc_hash (str, len)
-     const unsigned char *str;
-     size_t len;
-{
-  size_t 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
-}
-
-/* Internal primitive: returns the header structure for the identifier
-   of length LENGTH, containing CONTENTS.  If that identifier already
-   exists in the table, returns the existing entry.  If the identifier
-   hasn't been seen before and the last argument is INSERT, inserts
-   and returns a new entry. Otherwise returns NULL.  */
-static sp_hashnode
-alloc_ident (contents, length, insert)
-     const char *contents;
-     size_t length;
-     enum insert_option insert;
-{
-  unsigned int hash = calc_hash ((const unsigned char *)contents, length);
-  unsigned int hash2;
-  unsigned int index;
-  size_t sizemask;
-  sp_hashnode entry;
-
-  sizemask = string_hash.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;
-  string_hash.searches++;
-
-  for (;;)
-    {
-      entry = string_hash.entries[index];
-
-      if (SP_EMPTY (entry))
-	break;
-
-      if ((size_t) SP_LEN (entry) == length
-	  && !memcmp (SP_STR (entry), contents, length))
-	return entry;
-
-      index = (index + hash2) & sizemask;
-      string_hash.collisions++;
-    }
-
-  if (insert == NO_INSERT)
-    return NULL;
-
-  entry = (sp_hashnode) make_node (IDENTIFIER_NODE);
-  string_hash.entries[index] = entry;
-  SP_STR (entry) = ggc_alloc_string (contents, length);
-  SP_LEN (entry) = length;
-  /* This is not yet an identifier.  */
-  TREE_SET_CODE (entry, ERROR_MARK);
-
-  if (++string_hash.nelements * 4 >= string_hash.nslots * 3)
-    /* Must expand the string table.  */
-    expand_string_table ();
-
-  return entry;
-}
-
-/* Subroutine of alloc_ident which doubles the size of the hash table
-   and rehashes all the strings into the new table.  Returns the entry
-   in the new table corresponding to ENTRY.  */
-static void
-expand_string_table ()
-{
-  sp_hashnode *nentries;
-  sp_hashnode *e;
-  size_t size, sizemask;
-
-  size = string_hash.nslots * 2;
-  nentries = (sp_hashnode *) xcalloc (size, sizeof (sp_hashnode));
-  sizemask = size - 1;
-
-  FORALL_IDS (e)
-    {
-      unsigned int index, hash, hash2;
-
-      hash = calc_hash ((const unsigned char *) SP_STR (*e), SP_LEN (*e));
-      hash2 = ((hash * 17) & sizemask) | 1;
-      index = hash & sizemask;
-
-      for (;;)
-	{
-	  if (SP_EMPTY (nentries[index]))
-	    {
-	      nentries[index] = *e;
-	      break;
-	    }
-
-	  index = (index + hash2) & sizemask;
-	}
-    }
-
-  free (string_hash.entries);
-  string_hash.entries = nentries;
-  string_hash.nslots = size;
+  return GCC_IDENT_TO_HT_IDENT (make_node (IDENTIFIER_NODE));
 }
 
 /* Allocate and return a string constant of length LENGTH, containing
@@ -260,43 +99,40 @@ ggc_alloc_string (contents, length)
   return obstack_finish (&string_stack);
 }
 
+/* NODE is an identifier known to the preprocessor.  Make it known to
+   the front ends as well.  */
+
+void
+make_identifier (node)
+     tree node;
+{
+  /* If this identifier is longer than the clash-warning length,
+     do a brute force search of the entire table for clashes.  */
+  if (warn_id_clash && do_identifier_warnings
+      && IDENTIFIER_LENGTH (node) >= id_clash_len)
+    ht_forall (ident_hash, (ht_cb) scan_for_clashes,
+	       IDENTIFIER_POINTER (node));
+
+  TREE_SET_CODE (node, IDENTIFIER_NODE);
+#ifdef GATHER_STATISTICS
+  id_string_size += IDENTIFIER_LENGTH (node);
+#endif
+}
+
 /* Return an IDENTIFIER_NODE whose name is TEXT (a null-terminated string).
    If an identifier with that name has previously been referred to,
    the same node is returned this time.  */
+
 tree
 get_identifier (text)
      const char *text;
 {
-  sp_hashnode node;
-  size_t length = strlen (text);
-
-  node = alloc_ident (text, length, INSERT);
-  if (!SP_VALID (node))
-    {
-      /* If this identifier is longer than the clash-warning length,
-	 do a brute force search of the entire table for clashes.  */
-      if (warn_id_clash && do_identifier_warnings && length >= (size_t) id_clash_len)
-	{
-	  sp_hashnode *e;
-	  FORALL_IDS (e)
-	    {
-	      if (SP_LEN (*e) >= id_clash_len
-		  && !strncmp (SP_STR (*e), text, id_clash_len))
-		{
-		  warning ("\"%s\" and \"%s\" identical in first %d characters",
-			   text, SP_STR (*e), id_clash_len);
-		  break;
-		}
-	    }
-	}
-
-      TREE_SET_CODE (node, IDENTIFIER_NODE);
-#ifdef GATHER_STATISTICS
-      id_string_size += length;
-#endif
-    }
+  hashnode ht_node = ht_lookup (ident_hash,
+				(const unsigned char *) text,
+				strlen (text), HT_ALLOC);
 
-  return SP_TREE (node);
+  /* ht_node can't be NULL here.  */
+  return HT_IDENT_TO_GCC_IDENT (ht_node);
 }
 
 /* If an identifier with the name TEXT (a null-terminated string) has
@@ -307,90 +143,92 @@ tree
 maybe_get_identifier (text)
      const char *text;
 {
-  sp_hashnode node;
+  hashnode ht_node;
+  tree node;
   size_t length = strlen (text);
 
-  node = alloc_ident (text, length, NO_INSERT);
-  if (!SP_EMPTY (node) && SP_VALID (node))
-    return SP_TREE (node);
+  ht_node = ht_lookup (ident_hash, (const unsigned char *) text,
+		       length, HT_NO_INSERT);
+  if (ht_node)
+    {
+      node = HT_IDENT_TO_GCC_IDENT (ht_node);
+      if (IS_FE_IDENT (node))
+	return node;
+    }
 
   return NULL_TREE;
 }
 
+/* If this identifier is longer than the clash-warning length,
+   do a brute force search of the entire table for clashes.  */
+
+static int
+scan_for_clashes (pfile, h, text)
+     struct cpp_reader *pfile ATTRIBUTE_UNUSED;
+     hashnode h;
+     const char *text;
+{
+  tree node = HT_IDENT_TO_GCC_IDENT (h);
+
+  if (IS_FE_IDENT (node)
+      && IDENTIFIER_LENGTH (node) >= id_clash_len
+      && !memcmp (IDENTIFIER_POINTER (node), text, id_clash_len))
+    {
+      warning ("\"%s\" and \"%s\" identical in first %d characters",
+	       text, IDENTIFIER_POINTER (node), id_clash_len);
+      return 0;
+    }
+
+  return 1;
+}
+
+/* Record the size of an identifier node for the language in use.
+   SIZE is the total size in bytes.
+   This is called by the language-specific files.  This must be
+   called before allocating any identifiers.  */
+
+void
+set_identifier_size (size)
+     int size;
+{
+  tree_code_length[(int) IDENTIFIER_NODE]
+    = (size - sizeof (struct tree_common)) / sizeof (tree);
+}
+
+/* Enable warnings on similar identifiers (if requested).
+   Done after the built-in identifiers are created.  */
+
+void
+start_identifier_warnings ()
+{
+  do_identifier_warnings = 1;
+}
+
 /* Report some basic statistics about the string pool.  */
 
 void
 stringpool_statistics ()
 {
-  size_t nelts, nids, overhead, headers;
-  size_t total_bytes, longest, sum_of_squares;
-  double exp_len, exp_len2, exp2_len;
-  sp_hashnode *e;
-#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;
-  FORALL_IDS (e)
-    {
-      size_t n = SP_LEN (*e);
-
-      total_bytes += n;
-      sum_of_squares += n*n;
-      if (n > longest)
-	longest = n;
-      if (SP_VALID (*e))
-	nids++;
-    }
-      
-  nelts = string_hash.nelements;
-  overhead = obstack_memory_used (&string_stack) - total_bytes;
-  headers = string_hash.nslots * sizeof (sp_hashnode);
-
-  fprintf (stderr,
-"\nString pool\n\
-entries\t\t%lu\n\
-identifiers\t%lu (%.2f%%)\n\
-slots\t\t%lu\n\
-bytes\t\t%lu%c (%lu%c overhead)\n\
-table size\t%lu%c\n",
-	   (unsigned long) nelts,
-	   (unsigned long) nids, nids * 100.0 / nelts,
-	   (unsigned long) string_hash.nslots,
-	   SCALE (total_bytes), LABEL (total_bytes),
-	   SCALE (overhead), LABEL (overhead),
-	   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\
-ins/search\t%.4f\n\
-avg. entry\t%.2f bytes (+/- %.2f)\n\
-longest entry\t%lu\n",
-	   (double) string_hash.collisions / (double) string_hash.searches,
-	   (double) nelts / (double) string_hash.searches,
-	   exp_len, approx_sqrt (exp_len2 - exp2_len),
-	   (unsigned long) longest);
-#undef SCALE
-#undef LABEL
+  ht_dump_statistics (ident_hash);
 }
 
-/* Mark the string hash for GC.  */
+/* Mark an identifier for GC.  */
 
-static void
-mark_string_hash (arg)
-     void *arg ATTRIBUTE_UNUSED;
+static int
+mark_ident (pfile, h, v)
+     struct cpp_reader *pfile ATTRIBUTE_UNUSED;
+     hashnode h;
+     const PTR v ATTRIBUTE_UNUSED;
 {
-  sp_hashnode *h;
+  ggc_mark_nonnull_tree (HT_IDENT_TO_GCC_IDENT (h));
+  return 1;
+}
 
-  FORALL_IDS (h)
-    {
-      ggc_mark_tree (SP_TREE (*h));
-    }
+/* Mark all identifiers for GC.  */
+
+static void
+mark_ident_hash (arg)
+     PTR arg ATTRIBUTE_UNUSED;
+{
+  ht_forall (ident_hash, mark_ident, NULL);
 }
diff --git a/gcc/toplev.c b/gcc/toplev.c
index 802446e..74b43de 100644
--- a/gcc/toplev.c
+++ b/gcc/toplev.c
@@ -1421,7 +1421,7 @@ int warn_cast_align;
    characters.  The value N is in `id_clash_len'.  */
 
 int warn_id_clash;
-int id_clash_len;
+unsigned int id_clash_len;
 
 /* Nonzero means warn about any objects definitions whose size is larger
    than N bytes.  Also want about function definitions whose returned
@@ -1612,29 +1612,6 @@ floor_log2_wide (x)
   return log;
 }
 
-/* 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;
-}
-
 static int float_handler_set;
 int float_handled;
 jmp_buf float_handler;
diff --git a/gcc/toplev.h b/gcc/toplev.h
index 1f8f7d0..ef411bb 100644
--- a/gcc/toplev.h
+++ b/gcc/toplev.h
@@ -169,6 +169,9 @@ struct lang_hooks
 /* Each front end provides its own.  */
 extern struct lang_hooks lang_hooks;
 
+/* The hashtable, so that the C front ends can pass it to cpplib.  */
+extern struct ht *ident_hash;
+
 /* These functions can be used by targets to set the flags originally
    implied by -ffast-math and -fno-fast-math.  */
 
diff --git a/gcc/tree.c b/gcc/tree.c
index 1d880d7..9245449 100644
--- a/gcc/tree.c
+++ b/gcc/tree.c
@@ -238,26 +238,6 @@ init_obstacks ()
   lang_set_decl_assembler_name = set_decl_assembler_name;
 }
 
-void
-gcc_obstack_init (obstack)
-     struct obstack *obstack;
-{
-  /* 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
-  _obstack_begin (obstack, OBSTACK_CHUNK_SIZE, 0,
-		  (void *(*) PARAMS ((long))) OBSTACK_CHUNK_ALLOC,
-		  (void (*) PARAMS ((void *))) OBSTACK_CHUNK_FREE);
-}
-
 
 /* Allocate SIZE bytes in the permanent obstack
    and return a pointer to them.  */
diff --git a/gcc/tree.h b/gcc/tree.h
index 91328c4..e10352f 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -729,16 +729,27 @@ struct tree_complex
   union tree_node *imag;
 };
 
+#include "hashtable.h"
+
 /* Define fields and accessors for some special-purpose tree nodes.  */
 
-#define IDENTIFIER_LENGTH(NODE) (IDENTIFIER_NODE_CHECK (NODE)->identifier.length)
-#define IDENTIFIER_POINTER(NODE) (IDENTIFIER_NODE_CHECK (NODE)->identifier.pointer)
+#define IDENTIFIER_LENGTH(NODE) \
+	(IDENTIFIER_NODE_CHECK (NODE)->identifier.id.len)
+#define IDENTIFIER_POINTER(NODE) \
+	((char *) IDENTIFIER_NODE_CHECK (NODE)->identifier.id.str)
+
+/* Translate a hash table identifier pointer to a tree_identifier
+   pointer, and vice versa.  */
+
+#define HT_IDENT_TO_GCC_IDENT(NODE) \
+	((tree) ((char *) (NODE) - sizeof (struct tree_common)))
+#define GCC_IDENT_TO_HT_IDENT(NODE) \
+	(&((struct tree_identifier *) (NODE))->id)
 
 struct tree_identifier
 {
   struct tree_common common;
-  int length;
-  const char *pointer;
+  struct ht_identifier id;
 };
 
 /* In a TREE_LIST node.  */
@@ -1947,6 +1958,10 @@ extern tree make_tree_vec		PARAMS ((int));
 
 extern tree get_identifier		PARAMS ((const char *));
 
+/* NODE is an identifier known to the preprocessor.  Make it known to
+   the front ends as well.  */
+extern void make_identifier		PARAMS ((tree node));
+
 /* If an identifier with the name TEXT (a null-terminated string) has
    previously been referred to, return that node; otherwise return
    NULL_TREE.  */