diff options
| -rw-r--r-- | include/ChangeLog | 7 | ||||
| -rw-r--r-- | include/hashtab.h | 16 | ||||
| -rw-r--r-- | libiberty/ChangeLog | 11 | ||||
| -rw-r--r-- | libiberty/hashtab.c | 68 |
4 files changed, 90 insertions, 12 deletions
diff --git a/include/ChangeLog b/include/ChangeLog index be7061c..e36ba70 100644 --- a/include/ChangeLog +++ b/include/ChangeLog @@ -1,3 +1,10 @@ +2000-03-14 Bernd Schmidt <bernds@cygnus.co.uk> + + * hashtab.h (htab_trav): Modify type so that first arg is of type + void **. + (htab_find_with_hash, htab_find_slot_with_hash): Declare new + functions. + 2000-03-09 Alex Samuel <samuel@codesourcery.com> * partition.h: New file. diff --git a/include/hashtab.h b/include/hashtab.h index e6e38e4..5fe2393 100644 --- a/include/hashtab.h +++ b/include/hashtab.h @@ -44,7 +44,10 @@ extern "C" { typedef unsigned int (*htab_hash) PARAMS ((const void *)); /* Compare a table entry with a possible entry. The entry already in - the table always comes first. */ + the table always comes first, so the second element can be of a + different type (but in this case htab_find and htab_find_slot + cannot be used; instead the variants that accept a hash value + must be used). */ typedef int (*htab_eq) PARAMS ((const void *, const void *)); /* Cleanup function called whenever a live element is removed from @@ -52,9 +55,10 @@ typedef int (*htab_eq) PARAMS ((const void *, const void *)); typedef void (*htab_del) PARAMS ((void *)); /* Function called by htab_traverse for each live element. The first - arg is the element, the second arg is the auxiliary pointer handed - to htab_traverse. Return 1 to continue scan, 0 to stop. */ -typedef int (*htab_trav) PARAMS ((void *, void *)); + arg is the slot of the element (which can be passed to htab_clear_slot + if desired), the second arg is the auxiliary pointer handed to + htab_traverse. Return 1 to continue scan, 0 to stop. */ +typedef int (*htab_trav) PARAMS ((void **, void *)); /* Hash tables are of the following type. The structure (implementation) of this type is not needed for using the hash @@ -104,6 +108,10 @@ extern void htab_empty PARAMS ((htab_t)); extern void *htab_find PARAMS ((htab_t, const void *)); extern void **htab_find_slot PARAMS ((htab_t, const void *, int)); +extern void *htab_find_with_hash PARAMS ((htab_t, const void *, + unsigned int)); +extern void **htab_find_slot_with_hash PARAMS ((htab_t, const void *, + unsigned int, int)); extern void htab_clear_slot PARAMS ((htab_t, void **)); extern void htab_remove_elt PARAMS ((htab_t, void *)); diff --git a/libiberty/ChangeLog b/libiberty/ChangeLog index de8ed94..7557f62 100644 --- a/libiberty/ChangeLog +++ b/libiberty/ChangeLog @@ -1,3 +1,14 @@ +2000-03-14 Bernd Schmidt <bernds@cygnus.co.uk> + + * hashtab.c (find_empty_slot_for_expand): New function. + (htab_expand): Use it instead of htab_find_slot. + (htab_find_with_hash): Renamed from htab_find; now accepts extra + argument HASH. + (htab_find_slot_with_hash): Likewise for htab_find_slot. + (htab_find): New wrapper function. + (htab_find_slot): Likewise. + (htab_traverse): Pass slot, not entry, to called function. + 2000-03-09 Alex Samuel <samuel@codesourcery.com> * Makefile.in (CFILES): Add partition.c. diff --git a/libiberty/hashtab.c b/libiberty/hashtab.c index 0bc9e48..16c5d3e 100644 --- a/libiberty/hashtab.c +++ b/libiberty/hashtab.c @@ -144,6 +144,36 @@ htab_empty (htab) memset (htab->entries, 0, htab->size * sizeof (void *)); } +/* Similar to htab_find_slot, but without several unwanted side effects: + - Does not call htab->eq_f when it finds an existing entry. + - Does not change the count of elements/searches/collisions in the + 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; +{ + size_t size = htab->size; + unsigned int 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) + abort (); + + index += hash2; + if (index >= size) + index -= size; + } +} + /* The following function changes size of memory allocated for the entries and repeatedly inserts the table elements. The occupancy of the table after the call will be about 50%. Naturally the hash @@ -173,7 +203,7 @@ htab_expand (htab) void *x = *p; if (x != EMPTY_ENTRY && x != DELETED_ENTRY) { - void **q = htab_find_slot (htab, x, 1); + void **q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x)); *q = x; } p++; @@ -186,16 +216,16 @@ htab_expand (htab) element. It cannot be used to insert or delete an element. */ void * -htab_find (htab, element) +htab_find_with_hash (htab, element, hash) htab_t htab; const void *element; + unsigned int hash; { - unsigned int index, hash, hash2; + unsigned int index, hash2; size_t size; htab->searches++; size = htab->size; - hash = (*htab->hash_f) (element); hash2 = 1 + hash % (size - 2); index = hash % size; @@ -214,6 +244,16 @@ htab_find (htab, element) } } +/* Like htab_find_slot_with_hash, but compute the hash value from the + element. */ +void * +htab_find (htab, element) + htab_t htab; + const void *element; +{ + return htab_find_with_hash (htab, element, (*htab->hash_f) (element)); +} + /* This function searches for a hash table slot containing an entry equal to the given element. To delete an entry, call this with INSERT = 0, then call htab_clear_slot on the slot returned (possibly @@ -221,20 +261,20 @@ htab_find (htab, element) INSERT = 1, then write the value you want into the returned slot. */ void ** -htab_find_slot (htab, element, insert) +htab_find_slot_with_hash (htab, element, hash, insert) htab_t htab; const void *element; + unsigned int hash; int insert; { void **first_deleted_slot; - unsigned int index, hash, hash2; + unsigned int index, hash2; size_t size; if (insert && htab->size * 3 <= htab->n_elements * 4) htab_expand (htab); size = htab->size; - hash = (*htab->hash_f) (element); hash2 = 1 + hash % (size - 2); index = hash % size; @@ -278,6 +318,18 @@ htab_find_slot (htab, element, 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; +{ + return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element), + insert); +} + /* This function deletes an element with the given value from hash table. If there is no matching element in the hash table, this function does nothing. */ @@ -336,7 +388,7 @@ htab_traverse (htab, callback, info) { void *x = *slot; if (x != EMPTY_ENTRY && x != DELETED_ENTRY) - if (!(*callback) (x, info)) + if (!(*callback) (slot, info)) break; } while (++slot < limit); |