diff options
Diffstat (limited to 'libcpp')
| -rw-r--r-- | libcpp/ChangeLog | 13 | ||||
| -rw-r--r-- | libcpp/include/symtab.h | 8 | ||||
| -rw-r--r-- | libcpp/symtab.c | 97 |
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)); |