From 04f575f9445589c64203a0204608a9751985ae68 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Mon, 26 Jun 2006 05:37:53 +0000 Subject: [PATCH] Small optimization for hash library. --- src/libpspp/ChangeLog | 10 ++++++++++ src/libpspp/hash.c | 20 +++++++++++++++++++- 2 files changed, 29 insertions(+), 1 deletion(-) diff --git a/src/libpspp/ChangeLog b/src/libpspp/ChangeLog index ec8a40de..892dcd31 100644 --- a/src/libpspp/ChangeLog +++ b/src/libpspp/ChangeLog @@ -1,3 +1,13 @@ +Sun Jun 25 22:35:28 2006 Ben Pfaff + + Optimize rehashing: we know that none of the entries in the hash + table are equal, so we need not compare them to each other during + rehashing. + + * hash.c: (locate_empty_entry) New function. + (rehash) Use locate_empty_entry() instead of + locate_matching_entry(). + Fri Jun 9 14:03:29 2006 Ben Pfaff Reform string library. diff --git a/src/libpspp/hash.c b/src/libpspp/hash.c index 55b3a6f1..dcf8d8ff 100644 --- a/src/libpspp/hash.c +++ b/src/libpspp/hash.c @@ -251,6 +251,24 @@ locate_matching_entry (struct hsh_table *h, const void *target) } } +/* Returns the index of an empty entry that indicates + where TARGET should go, assuming that TARGET is not equal to + any item already in the hash table. */ +static inline unsigned +locate_empty_entry (struct hsh_table *h, const void *target) +{ + unsigned i = h->hash (target, h->aux); + + assert (h->hash_ordered); + for (;;) + { + i &= h->size - 1; + if (h->entries[i] == NULL) + return i; + i--; + } +} + /* Changes the capacity of H to NEW_SIZE, which must be a positive power of 2 at least as large as the number of elements in H. */ @@ -277,7 +295,7 @@ rehash (struct hsh_table *h, size_t new_size) { void *entry = *table_p; if (entry != NULL) - h->entries[locate_matching_entry (h, entry)] = entry; + h->entries[locate_empty_entry (h, entry)] = entry; } free (begin); -- 2.30.2