From c9ab9ae440a8066b2c2b85b157b1fdadcf09916a Mon Sep 17 00:00:00 2001 From: obrien Date: Fri, 1 Feb 2002 18:16:02 +0000 Subject: Enlist the FreeBSD-CURRENT users as testers of what is to become Gcc 3.1.0. These bits are taken from the FSF anoncvs repo on 1-Feb-2002 08:20 PST. --- contrib/gcc/hashtable.c | 326 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 326 insertions(+) create mode 100644 contrib/gcc/hashtable.c (limited to 'contrib/gcc/hashtable.c') diff --git a/contrib/gcc/hashtable.c b/contrib/gcc/hashtable.c new file mode 100644 index 0000000..bd2b137 --- /dev/null +++ b/contrib/gcc/hashtable.c @@ -0,0 +1,326 @@ +/* Hash tables. + Copyright (C) 2000, 2001 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 "hashtable.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 PARAMS ((const unsigned char *, unsigned int)); +static void ht_expand PARAMS ((hash_table *)); + +/* Let particular systems override the size of a chunk. */ +#ifndef OBSTACK_CHUNK_SIZE +#define OBSTACK_CHUNK_SIZE 0 +#endif + /* Let them override the alloc and free routines too. */ +#ifndef OBSTACK_CHUNK_ALLOC +#define OBSTACK_CHUNK_ALLOC xmalloc +#endif +#ifndef OBSTACK_CHUNK_FREE +#define OBSTACK_CHUNK_FREE free +#endif + +/* Initialise an obstack. */ +void +gcc_obstack_init (obstack) + struct obstack *obstack; +{ + _obstack_begin (obstack, OBSTACK_CHUNK_SIZE, 0, + (void *(*) PARAMS ((long))) OBSTACK_CHUNK_ALLOC, + (void (*) PARAMS ((void *))) OBSTACK_CHUNK_FREE); +} + +/* Calculate the hash of the string STR of length LEN. */ + +static unsigned int +calc_hash (str, len) + const unsigned char *str; + unsigned int len; +{ + unsigned int 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 (order) + unsigned int order; +{ + unsigned int nslots = 1 << order; + hash_table *table; + + table = (hash_table *) xmalloc (sizeof (hash_table)); + memset (table, 0, sizeof (hash_table)); + + /* Strings need no alignment. */ + gcc_obstack_init (&table->stack); + obstack_alignment_mask (&table->stack) = 0; + + table->entries = (hashnode *) xcalloc (nslots, sizeof (hashnode)); + table->nslots = nslots; + return table; +} + +/* Frees all memory associated with a hash table. */ + +void +ht_destroy (table) + 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 (table, str, len, insert) + hash_table *table; + const unsigned char *str; + unsigned int 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; + + /* hash2 must be odd, so we're guaranteed to visit every possible + location in the table during rehashing. */ + hash2 = ((hash * 17) & sizemask) | 1; + table->searches++; + + for (;;) + { + node = table->entries[index]; + + if (node == NULL) + break; + + if (HT_LEN (node) == 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, (PTR) str); + return node; + } + + index = (index + hash2) & sizemask; + table->collisions++; + } + + if (insert == HT_NO_INSERT) + return NULL; + + node = (*table->alloc_node) (table); + table->entries[index] = node; + + HT_LEN (node) = len; + 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 (table) + hash_table *table; +{ + hashnode *nentries, *p, *limit; + unsigned int size, sizemask; + + size = table->nslots * 2; + nentries = (hashnode *) xcalloc (size, sizeof (hashnode)); + sizemask = size - 1; + + p = table->entries; + limit = p + table->nslots; + do + if (*p) + { + unsigned int index, hash, hash2; + + hash = calc_hash (HT_STR (*p), HT_LEN (*p)); + hash2 = ((hash * 17) & sizemask) | 1; + index = hash & sizemask; + + for (;;) + { + if (! nentries[index]) + { + nentries[index] = *p; + break; + } + + index = (index + hash2) & sizemask; + } + } + 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 (table, cb, v) + hash_table *table; + ht_cb cb; + const PTR 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 (table) + 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. */ +double +approx_sqrt (x) + 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; +} -- cgit v1.1