| /* Hash tables. |
| 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 3, 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; see the file COPYING3. If not see |
| <http://www.gnu.org/licenses/>. |
| |
| 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. */ |
| |
| 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 |
| calc_hash (const unsigned char *str, size_t len) |
| { |
| size_t n = len; |
| unsigned int r = 0; |
| |
| while (n--) |
| r = HT_HASHSTEP (r, *str++); |
| |
| return HT_HASHFINISH (r, len); |
| } |
| |
| /* Initialize an identifier hashtable. */ |
| |
| hash_table * |
| ht_create (unsigned int order) |
| { |
| unsigned int nslots = 1 << order; |
| hash_table *table; |
| |
| table = XCNEW (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 = XCNEWVEC (hashnode, nslots); |
| table->entries_owned = true; |
| table->nslots = nslots; |
| return table; |
| } |
| |
| /* Frees all memory associated with a hash table. */ |
| |
| void |
| ht_destroy (hash_table *table) |
| { |
| obstack_free (&table->stack, NULL); |
| 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. 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 allocated. */ |
| hashnode |
| ht_lookup (hash_table *table, const unsigned char *str, size_t len, |
| enum ht_lookup_option insert) |
| { |
| 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; |
| |
| sizemask = table->nslots - 1; |
| index = hash & sizemask; |
| table->searches++; |
| |
| node = table->entries[index]; |
| |
| if (node != NULL) |
| { |
| 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. */ |
| hash2 = ((hash * 17) & sizemask) | 1; |
| |
| for (;;) |
| { |
| table->collisions++; |
| index = (index + hash2) & sizemask; |
| node = table->entries[index]; |
| if (node == NULL) |
| break; |
| |
| if (node == DELETED) |
| { |
| 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 (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) = (const unsigned char *) obstack_copy0 (&table->stack, |
| str, len); |
| |
| 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 = XCNEWVEC (hashnode, size); |
| sizemask = size - 1; |
| |
| p = table->entries; |
| limit = p + table->nslots; |
| do |
| if (*p && *p != DELETED) |
| { |
| 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); |
| |
| if (table->entries_owned) |
| free (table->entries); |
| table->entries_owned = true; |
| 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 && *p != DELETED) |
| { |
| if ((*cb) (table->pfile, *p, v) == 0) |
| break; |
| } |
| 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, deleted = 0; |
| double sum_of_squares, 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 == DELETED) |
| ++deleted; |
| else if (*p) |
| { |
| size_t n = HT_LEN (*p); |
| |
| total_bytes += n; |
| sum_of_squares += (double) 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, "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)); |
| 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; |
| } |