/* 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
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.
+Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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
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
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,
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;
}
/* 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 hash2;
unsigned int index;
+ unsigned int deleted_index = table->nslots;
size_t sizemask;
hashnode node;
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. */
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 = 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. */
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;
p = table->entries;
limit = p + table->nslots;
do
- if (*p)
+ 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,
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 \
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++;
(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));