diff options
author | Paolo Bonzini <bonzini@gnu.org> | 2004-05-24 10:50:45 +0000 |
---|---|---|
committer | Paolo Bonzini <bonzini@gcc.gnu.org> | 2004-05-24 10:50:45 +0000 |
commit | 4f4e53dd8517c0b2cbe36f0cf866f9f5ebe294e9 (patch) | |
tree | 5c68861b20c202df9c26dd8ebfaf794153accea0 /libcpp/symtab.c | |
parent | b1c5b5a09b545dabdd4a10d67f31d93779af95db (diff) | |
download | gcc-4f4e53dd8517c0b2cbe36f0cf866f9f5ebe294e9.zip gcc-4f4e53dd8517c0b2cbe36f0cf866f9f5ebe294e9.tar.gz gcc-4f4e53dd8517c0b2cbe36f0cf866f9f5ebe294e9.tar.bz2 |
Makefile.def (host_modules): add libcpp.
ChangeLog:
2004-05-23 Paolo Bonzini <bonzini@gnu.org>
* Makefile.def (host_modules): add libcpp.
* Makefile.tpl: Add dependencies on and for libcpp.
* Makefile.in: Regenerate.
* configure.in: Add libcpp host module.
* configure: Regenerate.
config/ChangeLog:
2004-05-23 Paolo Bonzini <bonzini@gnu.org>
* acx.m4 (ACX_HEADER_STDBOOL, ACX_HEADER_STRING):
From gcc.
gcc/ChangeLog:
2004-05-23 Paolo Bonzini <bonzini@gnu.org>
Move libcpp to the toplevel.
* Makefile.in: Remove references to libcpp files,
use CPPLIBS instead of libcpp.a. Define SYMTAB_H
and change hashtable.h to that.
* aclocal.m4 (gcc_AC_HEADER_STDBOOL,
gcc_AC_HEADER_STRING, gcc_AC_C__BOOL): Remove.
* configure.ac (gcc_AC_C__BOOL, HAVE_UCHAR): Remove tests.
* configure: Regenerate.
* config.in: Regenerate.
* c-ppoutput.c: Include ../libcpp/internal.h instead of cpphash.h.
* cppcharset.c: Removed.
* cpperror.c: Removed.
* cppexp.c: Removed.
* cppfiles.c: Removed.
* cpphash.c: Removed.
* cpphash.h: Removed.
* cppinit.c: Removed.
* cpplex.c: Removed.
* cpplib.c: Removed.
* cpplib.h: Removed.
* cppmacro.c: Removed.
* cpppch.c: Removed.
* cpptrad.c: Removed.
* cppucnid.h: Removed.
* cppucnid.pl: Removed.
* cppucnid.tab: Removed.
* hashtable.c: Removed.
* hashtable.h: Removed.
* line-map.c: Removed.
* line-map.h: Removed.
* mkdeps.c: Removed.
* mkdeps.h: Removed.
* stringpool.h: Include symtab.h instead of hashtable.h.
* tree.h: Include symtab.h instead of hashtable.h.
* system.h (O_NONBLOCK, O_NOCTTY): Do not define.
gcc/cp/ChangeLog:
2004-05-23 Paolo Bonzini <bonzini@gnu.org>
* Make-lang.in: No need to specify $(LIBCPP).
gcc/java/ChangeLog:
2004-05-23 Paolo Bonzini <bonzini@gnu.org>
* Make-lang.in: Link in $(LIBCPP) instead of mkdeps.o.
libcpp/ChangeLog:
2004-05-23 Paolo Bonzini <bonzini@gnu.org>
Moved libcpp from the gcc subdirectory to the toplevel.
* Makefile.am: New file.
* Makefile.in: Regenerate.
* configure.ac: New file.
* configure: Regenerate.
* config.in: Regenerate.
* charset.c: Moved from gcc/cppcharset.c. Add note about
brokenness of input charset detection. Adjust for change
in name of cppucnid.h.
* errors.c: Moved from gcc/cpperror.c. Do not include intl.h.
* expr.c: Moved from gcc/cppexp.c.
* files.c: Moved from gcc/cppfiles.c. Do not include intl.h.
Remove #define of O_BINARY, it is in system.h.
* identifiers.c: Moved from gcc/cpphash.c.
* internal.h: Moved from gcc/cpphash.h. Change header
guard name. All other files adjusted to match name change.
* init.c: Moved from gcc/cppinit.c.
(init_library) [ENABLE_NLS]: Call bindtextdomain.
* lex.c: Moved from gcc/cpplex.c.
* directives.c: Moved from gcc/cpplib.c.
* macro.c: Moved from gcc/cppmacro.c.
* pch.c: Moved from gcc/cpppch.c. Do not include intl.h.
* traditional.c: Moved from gcc/cpptrad.c.
* ucnid.h: Moved from gcc/cppucnid.h. Change header
guard name.
* ucnid.pl: Moved from gcc/cppucnid.pl.
* ucnid.tab: Moved from gcc/cppucnid.tab. Change header
guard name.
* symtab.c: Moved from gcc/hashtable.c.
* line-map.c: Moved from gcc. Do not include intl.h.
* mkdeps.c: Moved from gcc.
* system.h: New file.
libcpp/include/ChangeLog:
2004-05-23 Paolo Bonzini <bonzini@gnu.org>
* cpplib.h: Moved from gcc. Change header guard name.
* line-map.h: Moved from gcc. Change header guard name.
* mkdeps.h: Moved from gcc. Change header guard name.
* symtab.h: Moved from gcc/hashtable.h. Change header
guard name.
libcpp/po/ChangeLog:
2004-05-23 Paolo Bonzini <bonzini@gnu.org>
* be.po: Extracted from gcc/po/be.po.
* ca.po: Extracted from gcc/po/ca.po.
* da.po: Extracted from gcc/po/da.po.
* de.po: Extracted from gcc/po/de.po.
* el.po: Extracted from gcc/po/el.po.
* es.po: Extracted from gcc/po/es.po.
* fr.po: Extracted from gcc/po/fr.po.
* ja.po: Extracted from gcc/po/ja.po.
* nl.po: Extracted from gcc/po/nl.po.
* sv.po: Extracted from gcc/po/sv.po.
* tr.po: Extracted from gcc/po/tr.po.
From-SVN: r82199
Diffstat (limited to 'libcpp/symtab.c')
-rw-r--r-- | libcpp/symtab.c | 310 |
1 files changed, 310 insertions, 0 deletions
diff --git a/libcpp/symtab.c b/libcpp/symtab.c new file mode 100644 index 0000000..39ceced --- /dev/null +++ b/libcpp/symtab.c @@ -0,0 +1,310 @@ +/* Hash tables. + Copyright (C) 2000, 2001, 2003 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 +later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +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. + + 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 + what you give them. Help stamp out software-hoarding! */ + +#include "config.h" +#include "system.h" +#include "symtab.h" + +/* The code below is a specialization of Vladimir Makarov's expandable + 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. */ + +static unsigned int calc_hash (const unsigned char *, size_t); +static void ht_expand (hash_table *); +static double approx_sqrt (double); + +/* Calculate the hash of the string STR of length LEN. */ + +static unsigned int +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++); + + return r + len; +#undef HASHSTEP +} + +/* Initialize an identifier hashtable. */ + +hash_table * +ht_create (unsigned int order) +{ + unsigned int nslots = 1 << order; + hash_table *table; + + table = xcalloc (1, sizeof (hash_table)); + + /* Strings need no alignment. */ + _obstack_begin (&table->stack, 0, 0, + (void *(*) (long)) xmalloc, + (void (*) (void *)) free); + + obstack_alignment_mask (&table->stack) = 0; + + table->entries = xcalloc (nslots, sizeof (hashnode)); + table->nslots = nslots; + return table; +} + +/* Frees all memory associated with a hash table. */ + +void +ht_destroy (hash_table *table) +{ + obstack_free (&table->stack, NULL); + 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 + 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. */ +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); + unsigned int hash2; + unsigned int index; + size_t sizemask; + hashnode node; + + sizemask = table->nslots - 1; + index = hash & sizemask; + 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; + } + + /* hash2 must be odd, so we're guaranteed to visit every possible + location in the table during rehashing. */ + hash2 = ((hash * 17) & sizemask) | 1; + + for (;;) + { + table->collisions++; + index = (index + hash2) & sizemask; + node = table->entries[index]; + if (node == NULL) + break; + + 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 (insert == HT_NO_INSERT) + return NULL; + + 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); + else + HT_STR (node) = str; + + if (++table->nelements * 4 >= table->nslots * 3) + /* Must expand the string table. */ + ht_expand (table); + + return node; +} + +/* Double the size of a hash table, re-hashing existing entries. */ + +static void +ht_expand (hash_table *table) +{ + hashnode *nentries, *p, *limit; + unsigned int size, sizemask; + + size = table->nslots * 2; + nentries = xcalloc (size, sizeof (hashnode)); + sizemask = size - 1; + + p = table->entries; + limit = p + table->nslots; + do + if (*p) + { + unsigned int index, hash, hash2; + + hash = (*p)->hash_value; + index = hash & sizemask; + + if (nentries[index]) + { + hash2 = ((hash * 17) & sizemask) | 1; + do + { + index = (index + hash2) & sizemask; + } + while (nentries[index]); + } + nentries[index] = *p; + } + while (++p < limit); + + free (table->entries); + table->entries = nentries; + table->nslots = size; +} + +/* For all nodes in TABLE, callback CB with parameters TABLE->PFILE, + the node, and V. */ +void +ht_forall (hash_table *table, ht_cb cb, const void *v) +{ + hashnode *p, *limit; + + p = table->entries; + limit = p + table->nslots; + do + if (*p) + { + if ((*cb) (table->pfile, *p, v) == 0) + break; + } + while (++p < limit); +} + +/* 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; + hashnode *p, *limit; + +#define SCALE(x) ((unsigned long) ((x) < 1024*10 \ + ? (x) \ + : ((x) < 1024*1024*10 \ + ? (x) / 1024 \ + : (x) / (1024*1024)))) +#define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M')) + + total_bytes = longest = sum_of_squares = nids = 0; + p = table->entries; + limit = p + table->nslots; + do + if (*p) + { + size_t n = HT_LEN (*p); + + total_bytes += n; + sum_of_squares += n * n; + if (n > longest) + longest = n; + nids++; + } + while (++p < limit); + + nelts = table->nelements; + overhead = obstack_memory_used (&table->stack) - total_bytes; + headers = table->nslots * sizeof (hashnode); + + fprintf (stderr, "\nString pool\nentries\t\t%lu\n", + (unsigned long) nelts); + fprintf (stderr, "identifiers\t%lu (%.2f%%)\n", + (unsigned long) nids, nids * 100.0 / nelts); + fprintf (stderr, "slots\t\t%lu\n", + (unsigned long) table->nslots); + fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n", + SCALE (total_bytes), LABEL (total_bytes), + SCALE (overhead), LABEL (overhead)); + fprintf (stderr, "table size\t%lu%c\n", + SCALE (headers), LABEL (headers)); + + exp_len = (double)total_bytes / (double)nelts; + exp2_len = exp_len * exp_len; + exp_len2 = (double) sum_of_squares / (double) nelts; + + fprintf (stderr, "coll/search\t%.4f\n", + (double) table->collisions / (double) table->searches); + fprintf (stderr, "ins/search\t%.4f\n", + (double) nelts / (double) table->searches); + fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n", + exp_len, approx_sqrt (exp_len2 - exp2_len)); + fprintf (stderr, "longest entry\t%lu\n", + (unsigned long) longest); +#undef SCALE +#undef LABEL +} + +/* Return the approximate positive square root of a number N. This is for + statistical reports, not code generation. */ +static double +approx_sqrt (double x) +{ + double s, d; + + if (x < 0) + abort (); + if (x == 0) + return 0; + + s = x; + do + { + d = (s * s - x) / (2 * s); + s -= d; + } + while (d > .0001); + return s; +} |