diff options
| -rw-r--r-- | libiberty/ChangeLog | 6 | ||||
| -rw-r--r-- | libiberty/hashtab.c | 78 |
2 files changed, 52 insertions, 32 deletions
diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog index 56bd231..63efe6e 100644 --- a/libiberty/ChangeLog +++ b/libiberty/ChangeLog @@ -1,3 +1,9 @@ +2002-04-09 Richard Henderson <rth@redhat.com> + + * 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. + 2002-04-01 Phil Edwards <pme@gcc.gnu.org> * cp-demangle.c (__cxa_demangle): Also protect with IN_GLIBCPP_V3. 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 |