X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=libcpp%2Fsymtab.c;h=48a5338b1f865d6a26b8d67fd7c009bdb96d49b6;hb=1d9d9b4153de3180cdae1dc906ebdaff29b9c491;hp=39cecedf72f39cd8ad668e797a4105cc0ece5c75;hpb=d856c8a6b9ed6ffbbb012ce9f999e9db3a8ee302;p=pf3gnuchains%2Fgcc-fork.git diff --git a/libcpp/symtab.c b/libcpp/symtab.c index 39cecedf72f..48a5338b1f8 100644 --- a/libcpp/symtab.c +++ b/libcpp/symtab.c @@ -1,9 +1,10 @@ /* Hash tables. - Copyright (C) 2000, 2001, 2003 Free Software Foundation, Inc. + Copyright (C) 2000, 2001, 2003, 2004, 2008, 2009 + 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 +Free Software Foundation; either version 3, or (at your option) any later version. This program is distributed in the hope that it will be useful, @@ -12,8 +13,8 @@ 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. +along with this program; see the file COPYING3. If not see +. 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 @@ -27,13 +28,15 @@ Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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 @@ -41,13 +44,11 @@ calc_hash (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++); + r = HT_HASHSTEP (r, *str++); - return r + len; -#undef HASHSTEP + return HT_HASHFINISH (r, len); } /* Initialize an identifier hashtable. */ @@ -58,7 +59,7 @@ ht_create (unsigned int order) unsigned int nslots = 1 << order; hash_table *table; - table = xcalloc (1, sizeof (hash_table)); + table = XCNEW (hash_table); /* Strings need no alignment. */ _obstack_begin (&table->stack, 0, 0, @@ -67,7 +68,8 @@ ht_create (unsigned int order) obstack_alignment_mask (&table->stack) = 0; - table->entries = xcalloc (nslots, sizeof (hashnode)); + table->entries = XCNEWVEC (hashnode, nslots); + table->entries_owned = true; table->nslots = nslots; return table; } @@ -78,25 +80,32 @@ void ht_destroy (hash_table *table) { obstack_free (&table->stack, NULL); - free (table->entries); + if (table->entries_owned) + free (table->entries); free (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) { - unsigned int hash = calc_hash (str, len); + return ht_lookup_with_hash (table, str, len, calc_hash (str, len), + insert); +} + +hashnode +ht_lookup_with_hash (hash_table *table, const unsigned char *str, + size_t len, unsigned int hash, + enum ht_lookup_option insert) +{ unsigned int hash2; unsigned int index; + unsigned int deleted_index = table->nslots; size_t sizemask; hashnode node; @@ -105,19 +114,15 @@ ht_lookup (hash_table *table, const unsigned char *str, size_t len, 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. */ @@ -131,31 +136,41 @@ ht_lookup (hash_table *table, const unsigned char *str, size_t len, 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) = obstack_copy0 (&table->stack, str, len); + + if (table->alloc_subobject) + { + char *chars = (char *) 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. */ @@ -173,13 +188,13 @@ ht_expand (hash_table *table) unsigned int size, sizemask; size = table->nslots * 2; - nentries = xcalloc (size, sizeof (hashnode)); + nentries = XCNEWVEC (hashnode, size); sizemask = size - 1; p = table->entries; limit = p + table->nslots; do - if (*p) + if (*p && *p != DELETED) { unsigned int index, hash, hash2; @@ -199,7 +214,9 @@ ht_expand (hash_table *table) } while (++p < limit); - free (table->entries); + if (table->entries_owned) + free (table->entries); + table->entries_owned = true; table->entries = nentries; table->nslots = size; } @@ -214,7 +231,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; @@ -222,14 +239,46 @@ 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, + unsigned int nslots, unsigned int nelements, + bool own) +{ + if (ht->entries_owned) + free (ht->entries); + ht->entries = entries; + ht->nslots = nslots; + ht->nelements = nelements; + ht->entries_owned = own; +} + /* Dump allocation statistics to stderr. */ void ht_dump_statistics (hash_table *table) { size_t nelts, nids, overhead, headers; - size_t total_bytes, longest, sum_of_squares; - double exp_len, exp_len2, exp2_len; + size_t total_bytes, longest, deleted = 0; + double sum_of_squares, exp_len, exp_len2, exp2_len; hashnode *p, *limit; #define SCALE(x) ((unsigned long) ((x) < 1024*10 \ @@ -243,12 +292,14 @@ 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); total_bytes += n; - sum_of_squares += n * n; + sum_of_squares += (double) n * n; if (n > longest) longest = n; nids++; @@ -265,6 +316,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));