diff options
author | Tom Tromey <tromey@redhat.com> | 2008-05-21 15:00:59 +0000 |
---|---|---|
committer | Tom Tromey <tromey@gcc.gnu.org> | 2008-05-21 15:00:59 +0000 |
commit | dae4174e53945378f6878632e75e4c0f7a7679c3 (patch) | |
tree | 06f6431108f6797065ea5bc80a375513068f17a5 /libcpp/symtab.c | |
parent | ccbdd3bc4e25f642b37694b277af2fccf49496c6 (diff) | |
download | gcc-dae4174e53945378f6878632e75e4c0f7a7679c3.zip gcc-dae4174e53945378f6878632e75e4c0f7a7679c3.tar.gz gcc-dae4174e53945378f6878632e75e4c0f7a7679c3.tar.bz2 |
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
Diffstat (limited to 'libcpp/symtab.c')
-rw-r--r-- | libcpp/symtab.c | 97 |
1 files changed, 62 insertions, 35 deletions
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 @@ 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)); |