aboutsummaryrefslogtreecommitdiff
path: root/libiberty/hashtab.c
diff options
context:
space:
mode:
authorH.J. Lu <hjl.tools@gmail.com>2000-06-15 20:56:25 +0000
committerH.J. Lu <hjl.tools@gmail.com>2000-06-15 20:56:25 +0000
commiteb383413c242546f266f9694071e0480806649b3 (patch)
tree95b240bd0c181ac81463ba1f0e6b97f06e973638 /libiberty/hashtab.c
parentb91280077a7ea882b26a1dfb84b1f314e84c6a86 (diff)
downloadgdb-eb383413c242546f266f9694071e0480806649b3.zip
gdb-eb383413c242546f266f9694071e0480806649b3.tar.gz
gdb-eb383413c242546f266f9694071e0480806649b3.tar.bz2
Synced with libiberty in the gcc repository.
Diffstat (limited to 'libiberty/hashtab.c')
-rw-r--r--libiberty/hashtab.c169
1 files changed, 107 insertions, 62 deletions
diff --git a/libiberty/hashtab.c b/libiberty/hashtab.c
index 6ae34aa..57b4041 100644
--- a/libiberty/hashtab.c
+++ b/libiberty/hashtab.c
@@ -1,5 +1,5 @@
/* An expandable hash tables datatype.
- Copyright (C) 1999 Free Software Foundation, Inc.
+ Copyright (C) 1999, 2000 Free Software Foundation, Inc.
Contributed by Vladimir Makarov (vmakarov@cygnus.com).
This file is part of the libiberty library.
@@ -59,8 +59,20 @@ Boston, MA 02111-1307, USA. */
#define DELETED_ENTRY ((void *) 1)
+static unsigned long higher_prime_number PARAMS ((unsigned long));
+static hashval_t hash_pointer PARAMS ((const void *));
+static int eq_pointer PARAMS ((const void *, const void *));
+static void htab_expand PARAMS ((htab_t));
+static void **find_empty_slot_for_expand PARAMS ((htab_t, hashval_t));
+
+/* At some point, we could make these be NULL, and modify the
+ hash-table routines to handle NULL specially; that would avoid
+ function-call overhead for the common case of hashing pointers. */
+htab_hash htab_hash_pointer = hash_pointer;
+htab_eq htab_eq_pointer = eq_pointer;
+
/* The following function returns the nearest prime number which is
- greater than given source number. */
+ greater than a given source number, N. */
static unsigned long
higher_prime_number (n)
@@ -68,24 +80,47 @@ higher_prime_number (n)
{
unsigned long i;
- n |= 0x01; /* Force N to be odd. */
+ /* Ensure we have a larger number and then force to odd. */
+ n++;
+ n |= 0x01;
+
+ /* All odd numbers < 9 are prime. */
if (n < 9)
- return n; /* All odd numbers < 9 are prime. */
+ return n;
+
+ /* Otherwise find the next prime using a sieve. */
next:
- n += 2;
- i = 3;
- do
- {
- if (n % i == 0)
- goto next;
- i += 2;
- }
- while ((i * i) <= n);
+
+ for (i = 3; i * i <= n; i += 2)
+ if (n % i == 0)
+ {
+ n += 2;
+ goto next;
+ }
return n;
}
+/* Returns a hash code for P. */
+
+static hashval_t
+hash_pointer (p)
+ const void *p;
+{
+ return (hashval_t) ((long)p >> 3);
+}
+
+/* Returns non-zero if P1 and P2 are equal. */
+
+static int
+eq_pointer (p1, p2)
+ const void *p1;
+ const void *p2;
+{
+ return p1 == p2;
+}
+
/* This function creates table with length slightly longer than given
source length. Created hash table is initiated as empty (all the
hash table entries are EMPTY_ENTRY). The function returns the
@@ -118,13 +153,12 @@ htab_delete (htab)
htab_t htab;
{
int i;
+
if (htab->del_f)
for (i = htab->size - 1; i >= 0; i--)
- {
- if (htab->entries[i] != EMPTY_ENTRY
- && htab->entries[i] != DELETED_ENTRY)
- (*htab->del_f) (htab->entries[i]);
- }
+ if (htab->entries[i] != EMPTY_ENTRY
+ && htab->entries[i] != DELETED_ENTRY)
+ (*htab->del_f) (htab->entries[i]);
free (htab->entries);
free (htab);
@@ -137,13 +171,12 @@ htab_empty (htab)
htab_t htab;
{
int i;
+
if (htab->del_f)
for (i = htab->size - 1; i >= 0; i--)
- {
- if (htab->entries[i] != EMPTY_ENTRY
- && htab->entries[i] != DELETED_ENTRY)
- (*htab->del_f) (htab->entries[i]);
- }
+ if (htab->entries[i] != EMPTY_ENTRY
+ && htab->entries[i] != DELETED_ENTRY)
+ (*htab->del_f) (htab->entries[i]);
memset (htab->entries, 0, htab->size * sizeof (void *));
}
@@ -154,22 +187,23 @@ htab_empty (htab)
hash table.
This function also assumes there are no deleted entries in the table.
HASH is the hash value for the element to be inserted. */
+
static void **
find_empty_slot_for_expand (htab, hash)
htab_t htab;
- unsigned int hash;
+ hashval_t hash;
{
size_t size = htab->size;
- unsigned int hash2 = 1 + hash % (size - 2);
+ hashval_t hash2 = 1 + hash % (size - 2);
unsigned int index = hash % size;
for (;;)
{
void **slot = htab->entries + index;
+
if (*slot == EMPTY_ENTRY)
return slot;
-
- if (*slot == DELETED_ENTRY)
+ else if (*slot == DELETED_ENTRY)
abort ();
index += hash2;
@@ -196,7 +230,7 @@ htab_expand (htab)
olimit = oentries + htab->size;
htab->size = higher_prime_number (htab->size * 2);
- htab->entries = xcalloc (htab->size, sizeof (void **));
+ htab->entries = (void **) xcalloc (htab->size, sizeof (void **));
htab->n_elements -= htab->n_deleted;
htab->n_deleted = 0;
@@ -205,14 +239,18 @@ htab_expand (htab)
do
{
void *x = *p;
+
if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
{
void **q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
+
*q = x;
}
+
p++;
}
while (p < olimit);
+
free (oentries);
}
@@ -223,33 +261,41 @@ void *
htab_find_with_hash (htab, element, hash)
htab_t htab;
const void *element;
- unsigned int hash;
+ hashval_t hash;
{
- unsigned int index, hash2;
+ unsigned int index;
+ hashval_t hash2;
size_t size;
+ void *entry;
htab->searches++;
size = htab->size;
- hash2 = 1 + hash % (size - 2);
index = hash % size;
+ entry = htab->entries[index];
+ if (entry == EMPTY_ENTRY
+ || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
+ return entry;
+
+ hash2 = 1 + hash % (size - 2);
+
for (;;)
{
- void *entry = htab->entries[index];
- if (entry == EMPTY_ENTRY)
- return NULL;
- else if (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element))
- return entry;
-
htab->collisions++;
index += hash2;
if (index >= size)
index -= size;
+
+ entry = htab->entries[index];
+ if (entry == EMPTY_ENTRY
+ || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
+ return entry;
}
}
/* Like htab_find_slot_with_hash, but compute the hash value from the
element. */
+
void *
htab_find (htab, element)
htab_t htab;
@@ -268,14 +314,15 @@ void **
htab_find_slot_with_hash (htab, element, hash, insert)
htab_t htab;
const void *element;
- unsigned int hash;
- int insert;
+ hashval_t hash;
+ enum insert_option insert;
{
void **first_deleted_slot;
- unsigned int index, hash2;
+ unsigned int index;
+ hashval_t hash2;
size_t size;
- if (insert && htab->size * 3 <= htab->n_elements * 4)
+ if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4)
htab_expand (htab);
size = htab->size;
@@ -290,7 +337,7 @@ htab_find_slot_with_hash (htab, element, hash, insert)
void *entry = htab->entries[index];
if (entry == EMPTY_ENTRY)
{
- if (!insert)
+ if (insert == NO_INSERT)
return NULL;
htab->n_elements++;
@@ -309,11 +356,8 @@ htab_find_slot_with_hash (htab, element, hash, insert)
if (!first_deleted_slot)
first_deleted_slot = &htab->entries[index];
}
- else
- {
- if ((*htab->eq_f) (entry, element))
- return &htab->entries[index];
- }
+ else if ((*htab->eq_f) (entry, element))
+ return &htab->entries[index];
htab->collisions++;
index += hash2;
@@ -324,11 +368,12 @@ htab_find_slot_with_hash (htab, element, hash, insert)
/* Like htab_find_slot_with_hash, but compute the hash value from the
element. */
+
void **
htab_find_slot (htab, element, insert)
htab_t htab;
const void *element;
- int insert;
+ enum insert_option insert;
{
return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
insert);
@@ -345,7 +390,7 @@ htab_remove_elt (htab, element)
{
void **slot;
- slot = htab_find_slot (htab, element, 0);
+ slot = htab_find_slot (htab, element, NO_INSERT);
if (*slot == EMPTY_ENTRY)
return;
@@ -368,8 +413,10 @@ htab_clear_slot (htab, slot)
if (slot < htab->entries || slot >= htab->entries + htab->size
|| *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
abort ();
+
if (htab->del_f)
(*htab->del_f) (*slot);
+
*slot = DELETED_ENTRY;
htab->n_deleted++;
}
@@ -385,12 +432,13 @@ htab_traverse (htab, callback, info)
htab_trav callback;
void *info;
{
- void **slot, **limit;
- slot = htab->entries;
- limit = slot + htab->size;
+ void **slot = htab->entries;
+ void **limit = slot + htab->size;
+
do
{
void *x = *slot;
+
if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
if (!(*callback) (slot, info))
break;
@@ -398,7 +446,7 @@ htab_traverse (htab, callback, info)
while (++slot < limit);
}
-/* The following function returns current size of given hash table. */
+/* Return the current size of given hash table. */
size_t
htab_size (htab)
@@ -407,8 +455,7 @@ htab_size (htab)
return htab->size;
}
-/* The following function returns current number of elements in given
- hash table. */
+/* Return the current number of elements in given hash table. */
size_t
htab_elements (htab)
@@ -417,17 +464,15 @@ htab_elements (htab)
return htab->n_elements - htab->n_deleted;
}
-/* The following function returns number of percents of fixed
- collisions during all work with given hash table. */
+/* Return the fraction of fixed collisions during all work with given
+ hash table. */
double
htab_collisions (htab)
htab_t htab;
{
- int searches;
-
- searches = htab->searches;
- if (searches == 0)
+ if (htab->searches == 0)
return 0.0;
- return (double)htab->collisions / (double)searches;
+
+ return (double) htab->collisions / (double) htab->searches;
}