diff options
Diffstat (limited to 'libiberty/hashtab.c')
| -rw-r--r-- | libiberty/hashtab.c | 148 |
1 files changed, 44 insertions, 104 deletions
diff --git a/libiberty/hashtab.c b/libiberty/hashtab.c index 5882c1f..d2b9c74 100644 --- a/libiberty/hashtab.c +++ b/libiberty/hashtab.c @@ -73,14 +73,14 @@ Boston, MA 02111-1307, USA. */ #define DELETED_ENTRY ((PTR) 1) -static unsigned int higher_prime_index PARAMS ((unsigned long)); -static hashval_t htab_mod_1 PARAMS ((hashval_t, hashval_t, hashval_t, int)); -static hashval_t htab_mod PARAMS ((hashval_t, htab_t)); -static hashval_t htab_mod_m2 PARAMS ((hashval_t, htab_t)); -static hashval_t hash_pointer PARAMS ((const void *)); -static int eq_pointer PARAMS ((const void *, const void *)); -static int htab_expand PARAMS ((htab_t)); -static PTR *find_empty_slot_for_expand PARAMS ((htab_t, hashval_t)); +static unsigned int higher_prime_index (unsigned long); +static hashval_t htab_mod_1 (hashval_t, hashval_t, hashval_t, int); +static hashval_t htab_mod (hashval_t, htab_t); +static hashval_t htab_mod_m2 (hashval_t, htab_t); +static hashval_t hash_pointer (const void *); +static int eq_pointer (const void *, const void *); +static int htab_expand (htab_t); +static PTR *find_empty_slot_for_expand (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 @@ -176,8 +176,7 @@ static struct prime_ent const prime_tab[] = { nearest prime number which is greater than N, and near a power of two. */ static unsigned int -higher_prime_index (n) - unsigned long n; +higher_prime_index (unsigned long n) { unsigned int low = 0; unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]); @@ -204,8 +203,7 @@ higher_prime_index (n) /* Returns a hash code for P. */ static hashval_t -hash_pointer (p) - const PTR p; +hash_pointer (const PTR p) { return (hashval_t) ((long)p >> 3); } @@ -213,9 +211,7 @@ hash_pointer (p) /* Returns non-zero if P1 and P2 are equal. */ static int -eq_pointer (p1, p2) - const PTR p1; - const PTR p2; +eq_pointer (const PTR p1, const PTR p2) { return p1 == p2; } @@ -223,8 +219,7 @@ eq_pointer (p1, p2) /* Return the current size of given hash table. */ inline size_t -htab_size (htab) - htab_t htab; +htab_size (htab_t htab) { return htab->size; } @@ -232,8 +227,7 @@ htab_size (htab) /* Return the current number of elements in given hash table. */ inline size_t -htab_elements (htab) - htab_t htab; +htab_elements (htab_t htab) { return htab->n_elements - htab->n_deleted; } @@ -241,9 +235,7 @@ htab_elements (htab) /* Return X % Y. */ static inline hashval_t -htab_mod_1 (x, y, inv, shift) - hashval_t x, y, inv; - int shift; +htab_mod_1 (hashval_t x, hashval_t y, hashval_t inv, int shift) { /* The multiplicative inverses computed above are for 32-bit types, and requires that we be able to compute a highpart multiply. */ @@ -271,9 +263,7 @@ htab_mod_1 (x, y, inv, shift) /* Compute the primary hash for HASH given HTAB's current size. */ static inline hashval_t -htab_mod (hash, htab) - hashval_t hash; - htab_t htab; +htab_mod (hashval_t hash, htab_t htab) { const struct prime_ent *p = &prime_tab[htab->size_prime_index]; return htab_mod_1 (hash, p->prime, p->inv, p->shift); @@ -282,9 +272,7 @@ htab_mod (hash, htab) /* Compute the secondary hash for HASH given HTAB's current size. */ static inline hashval_t -htab_mod_m2 (hash, htab) - hashval_t hash; - htab_t htab; +htab_mod_m2 (hashval_t hash, htab_t htab) { const struct prime_ent *p = &prime_tab[htab->size_prime_index]; return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift); @@ -296,13 +284,8 @@ htab_mod_m2 (hash, htab) created hash table, or NULL if memory allocation fails. */ htab_t -htab_create_alloc (size, hash_f, eq_f, del_f, alloc_f, free_f) - size_t size; - htab_hash hash_f; - htab_eq eq_f; - htab_del del_f; - htab_alloc alloc_f; - htab_free free_f; +htab_create_alloc (size_t size, htab_hash hash_f, htab_eq eq_f, + htab_del del_f, htab_alloc alloc_f, htab_free free_f) { htab_t result; unsigned int size_prime_index; @@ -374,14 +357,9 @@ htab_create_alloc_ex (size, hash_f, eq_f, del_f, alloc_arg, alloc_f, /* Update the function pointers and allocation parameter in the htab_t. */ void -htab_set_functions_ex (htab, hash_f, eq_f, del_f, alloc_arg, alloc_f, free_f) - htab_t htab; - htab_hash hash_f; - htab_eq eq_f; - htab_del del_f; - PTR alloc_arg; - htab_alloc_with_arg alloc_f; - htab_free_with_arg free_f; +htab_set_functions_ex (htab_t htab, htab_hash hash_f, htab_eq eq_f, + htab_del del_f, PTR alloc_arg, + htab_alloc_with_arg alloc_f, htab_free_with_arg free_f) { htab->hash_f = hash_f; htab->eq_f = eq_f; @@ -395,21 +373,13 @@ htab_set_functions_ex (htab, hash_f, eq_f, del_f, alloc_arg, alloc_f, free_f) #undef htab_create htab_t -htab_create (size, hash_f, eq_f, del_f) - size_t size; - htab_hash hash_f; - htab_eq eq_f; - htab_del del_f; +htab_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f) { return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free); } htab_t -htab_try_create (size, hash_f, eq_f, del_f) - size_t size; - htab_hash hash_f; - htab_eq eq_f; - htab_del del_f; +htab_try_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f) { return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free); } @@ -418,8 +388,7 @@ htab_try_create (size, hash_f, eq_f, del_f) Naturally the hash table must already exist. */ void -htab_delete (htab) - htab_t htab; +htab_delete (htab_t htab) { size_t size = htab_size (htab); PTR *entries = htab->entries; @@ -445,8 +414,7 @@ htab_delete (htab) /* This function clears all entries in the given hash table. */ void -htab_empty (htab) - htab_t htab; +htab_empty (htab_t htab) { size_t size = htab_size (htab); PTR *entries = htab->entries; @@ -468,9 +436,7 @@ htab_empty (htab) HASH is the hash value for the element to be inserted. */ static PTR * -find_empty_slot_for_expand (htab, hash) - htab_t htab; - hashval_t hash; +find_empty_slot_for_expand (htab_t htab, hashval_t hash) { hashval_t index = htab_mod (hash, htab); size_t size = htab_size (htab); @@ -506,8 +472,7 @@ find_empty_slot_for_expand (htab, hash) expanded. If all goes well, it will return a non-zero value. */ static int -htab_expand (htab) - htab_t htab; +htab_expand (htab_t htab) { PTR *oentries; PTR *olimit; @@ -575,10 +540,7 @@ htab_expand (htab) element. It cannot be used to insert or delete an element. */ PTR -htab_find_with_hash (htab, element, hash) - htab_t htab; - const PTR element; - hashval_t hash; +htab_find_with_hash (htab_t htab, const PTR element, hashval_t hash) { hashval_t index, hash2; size_t size; @@ -612,9 +574,7 @@ htab_find_with_hash (htab, element, hash) element. */ PTR -htab_find (htab, element) - htab_t htab; - const PTR element; +htab_find (htab_t htab, const PTR element) { return htab_find_with_hash (htab, element, (*htab->hash_f) (element)); } @@ -628,11 +588,8 @@ htab_find (htab, element) allocation fails. */ PTR * -htab_find_slot_with_hash (htab, element, hash, insert) - htab_t htab; - const PTR element; - hashval_t hash; - enum insert_option insert; +htab_find_slot_with_hash (htab_t htab, const PTR element, + hashval_t hash, enum insert_option insert) { PTR *first_deleted_slot; hashval_t index, hash2; @@ -699,10 +656,7 @@ htab_find_slot_with_hash (htab, element, hash, insert) element. */ PTR * -htab_find_slot (htab, element, insert) - htab_t htab; - const PTR element; - enum insert_option insert; +htab_find_slot (htab_t htab, const PTR element, enum insert_option insert) { return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element), insert); @@ -713,9 +667,7 @@ htab_find_slot (htab, element, insert) element in the hash table, this function does nothing. */ void -htab_remove_elt (htab, element) - htab_t htab; - PTR element; +htab_remove_elt (htab_t htab, PTR element) { htab_remove_elt_with_hash (htab, element, (*htab->hash_f) (element)); } @@ -726,10 +678,7 @@ htab_remove_elt (htab, element) function does nothing. */ void -htab_remove_elt_with_hash (htab, element, hash) - htab_t htab; - PTR element; - hashval_t hash; +htab_remove_elt_with_hash (htab_t htab, PTR element, hashval_t hash) { PTR *slot; @@ -749,9 +698,7 @@ htab_remove_elt_with_hash (htab, element, hash) again. */ void -htab_clear_slot (htab, slot) - htab_t htab; - PTR *slot; +htab_clear_slot (htab_t htab, PTR *slot) { if (slot < htab->entries || slot >= htab->entries + htab_size (htab) || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY) @@ -770,10 +717,7 @@ htab_clear_slot (htab, slot) argument. */ void -htab_traverse_noresize (htab, callback, info) - htab_t htab; - htab_trav callback; - PTR info; +htab_traverse_noresize (htab_t htab, htab_trav callback, PTR info) { PTR *slot; PTR *limit; @@ -796,10 +740,7 @@ htab_traverse_noresize (htab, callback, info) too empty to improve effectivity of subsequent calls. */ void -htab_traverse (htab, callback, info) - htab_t htab; - htab_trav callback; - PTR info; +htab_traverse (htab_t htab, htab_trav callback, PTR info) { if (htab_elements (htab) * 8 < htab_size (htab)) htab_expand (htab); @@ -811,8 +752,7 @@ htab_traverse (htab, callback, info) hash table. */ double -htab_collisions (htab) - htab_t htab; +htab_collisions (htab_t htab) { if (htab->searches == 0) return 0.0; @@ -846,8 +786,7 @@ htab_collisions (htab) function they just started using for Perl's hashes. */ hashval_t -htab_hash_string (p) - const PTR p; +htab_hash_string (const PTR p) { const unsigned char *str = (const unsigned char *) p; hashval_t r = 0; @@ -936,10 +875,11 @@ acceptable. Do NOT use for cryptographic purposes. -------------------------------------------------------------------- */ -hashval_t iterative_hash (k_in, length, initval) - const PTR k_in; /* the key */ - register size_t length; /* the length of the key */ - register hashval_t initval; /* the previous hash, or an arbitrary value */ +hashval_t +iterative_hash (const PTR k_in /* the key */, + register size_t length /* the length of the key */, + register hashval_t initval /* the previous hash, or + an arbitrary value */) { register const unsigned char *k = (const unsigned char *)k_in; register hashval_t a,b,c,len; |