aboutsummaryrefslogtreecommitdiff
path: root/libiberty/hashtab.c
diff options
context:
space:
mode:
authorRichard Henderson <rth@redhat.com>2002-04-10 00:43:27 +0000
committerRichard Henderson <rth@redhat.com>2002-04-10 00:43:27 +0000
commitb1c933fc526667539eda62ccabefbfe3764dc677 (patch)
treea0a3e8f09b8396b7b9a9f60b45318ca1839b5791 /libiberty/hashtab.c
parentca439ad26a484e0a818095509fb57f8ef0b98314 (diff)
downloadgdb-b1c933fc526667539eda62ccabefbfe3764dc677.zip
gdb-b1c933fc526667539eda62ccabefbfe3764dc677.tar.gz
gdb-b1c933fc526667539eda62ccabefbfe3764dc677.tar.bz2
* hashtab.c (higher_prime_number): Use 7 as minimum.
(find_empty_slot_for_expand): Don't compute hash2 unless needed. (htab_find_slot_with_hash): Likewise.
Diffstat (limited to 'libiberty/hashtab.c')
-rw-r--r--libiberty/hashtab.c78
1 files changed, 46 insertions, 32 deletions
diff --git a/libiberty/hashtab.c b/libiberty/hashtab.c
index 36ad6e4..7477c35 100644
--- a/libiberty/hashtab.c
+++ b/libiberty/hashtab.c
@@ -1,5 +1,5 @@
/* An expandable hash tables datatype.
- Copyright (C) 1999, 2000, 2001 Free Software Foundation, Inc.
+ Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
Contributed by Vladimir Makarov (vmakarov@cygnus.com).
This file is part of the libiberty library.
@@ -81,7 +81,6 @@ higher_prime_number (n)
/* These are primes that are near, but slightly smaller than, a
power of two. */
static const unsigned long primes[] = {
- (unsigned long) 2,
(unsigned long) 7,
(unsigned long) 13,
(unsigned long) 31,
@@ -264,21 +263,27 @@ find_empty_slot_for_expand (htab, hash)
hashval_t hash;
{
size_t size = htab->size;
- hashval_t hash2 = 1 + hash % (size - 2);
unsigned int index = hash % size;
+ PTR *slot = htab->entries + index;
+ hashval_t hash2;
+
+ if (*slot == EMPTY_ENTRY)
+ return slot;
+ else if (*slot == DELETED_ENTRY)
+ abort ();
+ hash2 = 1 + hash % (size - 2);
for (;;)
{
- PTR *slot = htab->entries + index;
+ index += hash2;
+ if (index >= size)
+ index -= size;
+ slot = htab->entries + index;
if (*slot == EMPTY_ENTRY)
return slot;
else if (*slot == DELETED_ENTRY)
abort ();
-
- index += hash2;
- if (index >= size)
- index -= size;
}
}
@@ -405,50 +410,59 @@ htab_find_slot_with_hash (htab, element, hash, insert)
unsigned int index;
hashval_t hash2;
size_t size;
+ PTR entry;
if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
&& htab_expand (htab) == 0)
return NULL;
size = htab->size;
- hash2 = 1 + hash % (size - 2);
index = hash % size;
htab->searches++;
first_deleted_slot = NULL;
+ entry = htab->entries[index];
+ if (entry == EMPTY_ENTRY)
+ goto empty_entry;
+ else if (entry == DELETED_ENTRY)
+ first_deleted_slot = &htab->entries[index];
+ else if ((*htab->eq_f) (entry, element))
+ return &htab->entries[index];
+
+ hash2 = 1 + hash % (size - 2);
for (;;)
{
- PTR entry = htab->entries[index];
+ htab->collisions++;
+ index += hash2;
+ if (index >= size)
+ index -= size;
+
+ entry = htab->entries[index];
if (entry == EMPTY_ENTRY)
- {
- if (insert == NO_INSERT)
- return NULL;
-
- htab->n_elements++;
-
- if (first_deleted_slot)
- {
- *first_deleted_slot = EMPTY_ENTRY;
- return first_deleted_slot;
- }
-
- return &htab->entries[index];
- }
-
- if (entry == DELETED_ENTRY)
+ goto empty_entry;
+ else if (entry == DELETED_ENTRY)
{
if (!first_deleted_slot)
first_deleted_slot = &htab->entries[index];
}
- else if ((*htab->eq_f) (entry, element))
+ else if ((*htab->eq_f) (entry, element))
return &htab->entries[index];
-
- htab->collisions++;
- index += hash2;
- if (index >= size)
- index -= size;
}
+
+ empty_entry:
+ if (insert == NO_INSERT)
+ return NULL;
+
+ htab->n_elements++;
+
+ if (first_deleted_slot)
+ {
+ *first_deleted_slot = EMPTY_ENTRY;
+ return first_deleted_slot;
+ }
+
+ return &htab->entries[index];
}
/* Like htab_find_slot_with_hash, but compute the hash value from the