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
diff --git a/libcpp/symtab.c b/libcpp/symtab.c
index ffa28f5..5414ff0 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 @@
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 @@
}
/* 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 @@
{
unsigned int hash2;
unsigned int index;
+ unsigned int deleted_index = table->nslots;
size_t sizemask;
hashnode node;
@@ -113,19 +113,15 @@
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 @@
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 @@
p = table->entries;
limit = p + table->nslots;
do
- if (*p)
+ if (*p && *p != DELETED)
{
unsigned int index, hash, hash2;
@@ -225,7 +230,7 @@
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 @@
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 @@
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 @@
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 @@
(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));