symtab.h (HT_ALLOCED): Remove.

libcpp
	* include/symtab.h (HT_ALLOCED): Remove.
	(ht_purge): Declare.
	* symtab.c (DELETED): New define.
	(ht_lookup): Update comment.
	(ht_lookup_with_hash): Handle deleted entries.  Remove HT_ALLOCED
	code.  Use subobject allocator for strings, if it exists.
	(ht_expand): Handle deleted entries.
	(ht_forall): Likewise.
	(ht_purge): New function.
	(ht_dump_statistics): Print deletion statistics.
gcc
	* ggc-zone.c (lookup_page_table_if_allocated): New function.
	(zone_find_object_offset): Likewise.
	(gt_ggc_m_S): Likewise.
	(highest_bit): Likewise.
	* ggc-page.c (gt_ggc_m_S): New function.
	* stringpool.c (string_stack): Remove.
	(init_stringpool): Update.
	(ggc_alloc_string): Use ggc_alloc.
	(maybe_delete_ident): New function.
	(ggc_purge_stringpool): Likewise.
	(gt_ggc_m_S): Remove.
	* ggc-common.c (ggc_protect_identifiers): New global.
	(ggc_mark_roots): Call ggc_purge_stringpool.  Use
	ggc_protect_identifiers.
	* ggc.h (ggc_protect_identifiers): Declare.
	(gt_ggc_m_S): Update.
	(ggc_purge_stringpool): Declare.
	* toplev.c (compile_file): Set and reset ggc_protect_identifiers.
	* gengtype.c (write_types_process_field) <TYPE_STRING>: Remove
	special case.
	(write_root): Cast gt_ggc_m_S to gt_pointer_walker.
gcc/cp
	* mangle.c (save_partially_mangled_name): Remove.
	(restore_partially_mangled_name): Likewise.
	(write_encoding): Update.
	(write_unqualified_name): Likewise.
	(start_mangling): Always use name_obstack.  Remove 'ident_p'
	argument.
	(get_identifier_nocopy): Remove.
	(finish_mangling_internal): Rename from finish_mangling.
	(finish_mangling): New function.
	(finish_mangling_get_identifier): Likewise.
	(partially_mangled_name, partially_mangled_name_len): Remove.
	(mangle_decl_string): Change return type.  Update.
	(mangle_decl, mangle_type_string, mangle_special_for_type,
	mangle_ctor_vtbl_for_type, mangle_thunk, mangle_guard_variable,
	mangle_ref_init_variable): Update.

From-SVN: r135720

3 files changed, 81 insertions, 37 deletions

diff --git a/libcpp/ChangeLog b/libcpp/ChangeLog
index fc226b452bb..58632e3f548 100644
--- a/libcpp/ChangeLog
+++ b/libcpp/ChangeLog
@@ -1,3 +1,16 @@
+2008-05-21  Tom Tromey  <tromey@redhat.com>
+
+	* include/symtab.h (HT_ALLOCED): Remove.
+	(ht_purge): Declare.
+	* symtab.c (DELETED): New define.
+	(ht_lookup): Update comment.
+	(ht_lookup_with_hash): Handle deleted entries.  Remove HT_ALLOCED
+	code.  Use subobject allocator for strings, if it exists.
+	(ht_expand): Handle deleted entries.
+	(ht_forall): Likewise.
+	(ht_purge): New function.
+	(ht_dump_statistics): Print deletion statistics.
+
 2008-05-13  Tom Tromey  <tromey@redhat.com>
 
 	PR preprocessor/22168:
diff --git a/libcpp/include/symtab.h b/libcpp/include/symtab.h
index 2bd45cf7f19..c016be3755b 100644
--- a/libcpp/include/symtab.h
+++ b/libcpp/include/symtab.h
@@ -1,5 +1,5 @@
 /* Hash tables.
-   Copyright (C) 2000, 2001, 2003, 2004, 2007 Free Software Foundation, Inc.
+   Copyright (C) 2000, 2001, 2003, 2004, 2007, 2008 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
@@ -39,7 +39,7 @@ struct ht_identifier GTY(())
 typedef struct ht hash_table;
 typedef struct ht_identifier *hashnode;
 
-enum ht_lookup_option {HT_NO_INSERT = 0, HT_ALLOC, HT_ALLOCED};
+enum ht_lookup_option {HT_NO_INSERT = 0, HT_ALLOC};
 
 /* An identifier hash table for cpplib and the front ends.  */
 struct ht
@@ -88,6 +88,10 @@ extern hashnode ht_lookup_with_hash (hash_table *, const unsigned char *,
 typedef int (*ht_cb) (struct cpp_reader *, hashnode, const void *);
 extern void ht_forall (hash_table *, ht_cb, const void *);
 
+/* For all nodes in TABLE, call the callback.  If the callback returns
+   a nonzero value, the node is removed from the table.  */
+extern void ht_purge (hash_table *, ht_cb, const void *);
+
 /* Restore the hash table.  */
 extern void ht_load (hash_table *ht, hashnode *entries,
 		     unsigned int nslots, unsigned int nelements, bool own);
diff --git a/libcpp/symtab.c b/libcpp/symtab.c
index ffa28f5f7a5..5414ff05fc9 100644
--- a/libcpp/symtab.c
+++ b/libcpp/symtab.c
@@ -1,5 +1,5 @@
 /* Hash tables.
-   Copyright (C) 2000, 2001, 2003, 2004 Free Software Foundation, Inc.
+   Copyright (C) 2000, 2001, 2003, 2004, 2008 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
@@ -27,13 +27,15 @@ Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
    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.  */
+   existing entry with a potential new one.  */
 
 static unsigned int calc_hash (const unsigned char *, size_t);
 static void ht_expand (hash_table *);
 static double approx_sqrt (double);
 
+/* A deleted entry.  */
+#define DELETED ((hashnode) -1)
+
 /* Calculate the hash of the string STR of length LEN.  */
 
 static unsigned int
@@ -83,13 +85,10 @@ ht_destroy (hash_table *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
+   already exists in the table, returns the existing entry.  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.  */
+   string is allocated.  */
 hashnode
 ht_lookup (hash_table *table, const unsigned char *str, size_t len,
 	   enum ht_lookup_option insert)
@@ -105,6 +104,7 @@ ht_lookup_with_hash (hash_table *table, const unsigned char *str,
 {
   unsigned int hash2;
   unsigned int index;
+  unsigned int deleted_index = table->nslots;
   size_t sizemask;
   hashnode node;
 
@@ -113,19 +113,15 @@ ht_lookup_with_hash (hash_table *table, const unsigned char *str,
   table->searches++;
 
   node = table->entries[index];
- 
+
   if (node != NULL)
     {
-      if (node->hash_value == hash
-	  && HT_LEN (node) == (unsigned int) 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, (void *) str);
-	  return node;
-	}
+      if (node == DELETED)
+	deleted_index = index;
+      else if (node->hash_value == hash
+	       && HT_LEN (node) == (unsigned int) len
+	       && !memcmp (HT_STR (node), str, len))
+	return node;
 
       /* hash2 must be odd, so we're guaranteed to visit every possible
 	 location in the table during rehashing.  */
@@ -139,32 +135,41 @@ ht_lookup_with_hash (hash_table *table, const unsigned char *str,
 	  if (node == NULL)
 	    break;
 
-	  if (node->hash_value == hash
-	      && HT_LEN (node) == (unsigned int) len
-	      && !memcmp (HT_STR (node), str, len))
+	  if (node == DELETED)
 	    {
-	      if (insert == HT_ALLOCED)
-	      /* The string we search for was placed at the end of the
-		 obstack.  Release it.  */
-		obstack_free (&table->stack, (void *) str);
-	      return node;
+	      if (deleted_index != table->nslots)
+		deleted_index = index;
 	    }
+	  else if (node->hash_value == hash
+		   && HT_LEN (node) == (unsigned int) len
+		   && !memcmp (HT_STR (node), str, len))
+	    return node;
 	}
     }
 
   if (insert == HT_NO_INSERT)
     return NULL;
 
+  /* We prefer to overwrite the first deleted slot we saw.  */
+  if (deleted_index != table->nslots)
+    index = deleted_index;
+
   node = (*table->alloc_node) (table);
   table->entries[index] = node;
 
   HT_LEN (node) = (unsigned int) len;
   node->hash_value = hash;
-  if (insert == HT_ALLOC)
-    HT_STR (node) = (const unsigned char *) obstack_copy0 (&table->stack,
-                                                           str, len);
+
+  if (table->alloc_subobject)
+    {
+      char *chars = table->alloc_subobject (len + 1);
+      memcpy (chars, str, len);
+      chars[len] = '\0';
+      HT_STR (node) = (const unsigned char *) chars;
+    }
   else
-    HT_STR (node) = str;
+    HT_STR (node) = (const unsigned char *) obstack_copy0 (&table->stack,
+							   str, len);
 
   if (++table->nelements * 4 >= table->nslots * 3)
     /* Must expand the string table.  */
@@ -188,7 +193,7 @@ ht_expand (hash_table *table)
   p = table->entries;
   limit = p + table->nslots;
   do
-    if (*p)
+    if (*p && *p != DELETED)
       {
 	unsigned int index, hash, hash2;
 
@@ -225,7 +230,7 @@ ht_forall (hash_table *table, ht_cb cb, const void *v)
   p = table->entries;
   limit = p + table->nslots;
   do
-    if (*p)
+    if (*p && *p != DELETED)
       {
 	if ((*cb) (table->pfile, *p, v) == 0)
 	  break;
@@ -233,6 +238,24 @@ ht_forall (hash_table *table, ht_cb cb, const void *v)
   while (++p < limit);
 }
 
+/* Like ht_forall, but a nonzero return from the callback means that
+   the entry should be removed from the table.  */
+void
+ht_purge (hash_table *table, ht_cb cb, const void *v)
+{
+  hashnode *p, *limit;
+
+  p = table->entries;
+  limit = p + table->nslots;
+  do
+    if (*p && *p != DELETED)
+      {
+	if ((*cb) (table->pfile, *p, v))
+	  *p = DELETED;
+      }
+  while (++p < limit);
+}
+
 /* Restore the hash table.  */
 void
 ht_load (hash_table *ht, hashnode *entries,
@@ -253,7 +276,7 @@ void
 ht_dump_statistics (hash_table *table)
 {
   size_t nelts, nids, overhead, headers;
-  size_t total_bytes, longest;
+  size_t total_bytes, longest, deleted = 0;
   double sum_of_squares, exp_len, exp_len2, exp2_len;
   hashnode *p, *limit;
 
@@ -268,7 +291,9 @@ ht_dump_statistics (hash_table *table)
   p = table->entries;
   limit = p + table->nslots;
   do
-    if (*p)
+    if (*p == DELETED)
+      ++deleted;
+    else if (*p)
       {
 	size_t n = HT_LEN (*p);
 
@@ -290,6 +315,8 @@ ht_dump_statistics (hash_table *table)
 	   (unsigned long) nids, nids * 100.0 / nelts);
   fprintf (stderr, "slots\t\t%lu\n",
 	   (unsigned long) table->nslots);
+  fprintf (stderr, "deleted\t\t%lu\n",
+	   (unsigned long) deleted);
   fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n",
 	   SCALE (total_bytes), LABEL (total_bytes),
 	   SCALE (overhead), LABEL (overhead));