X-Git-Url: http://git.efficios.com/?a=blobdiff_plain;f=libiberty%2Fhashtab.c;h=9f917c3571d96a6ebd1e472f85bb85787f715a6c;hb=98f9338a584c5f68595fc97e692e83f700c8da3d;hp=8c8bd3110ade2a1d509321a46341baa52a3f8131;hpb=fca6a796b7fafc1254c61fb2bf36e1bd8893eef8;p=deliverable%2Fbinutils-gdb.git diff --git a/libiberty/hashtab.c b/libiberty/hashtab.c index 8c8bd3110a..9f917c3571 100644 --- a/libiberty/hashtab.c +++ b/libiberty/hashtab.c @@ -1,6 +1,5 @@ /* An expandable hash tables datatype. - Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2009 - Free Software Foundation, Inc. + Copyright (C) 1999-2019 Free Software Foundation, Inc. Contributed by Vladimir Makarov (vmakarov@cygnus.com). This file is part of the libiberty library. @@ -50,6 +49,9 @@ Boston, MA 02110-1301, USA. */ #ifdef HAVE_LIMITS_H #include #endif +#ifdef HAVE_INTTYPES_H +#include +#endif #ifdef HAVE_STDINT_H #include #endif @@ -191,14 +193,6 @@ higher_prime_index (unsigned long n) return low; } -/* Returns a hash code for P. */ - -static hashval_t -hash_pointer (const PTR p) -{ - return (hashval_t) ((intptr_t)p >> 3); -} - /* Returns non-zero if P1 and P2 are equal. */ static int @@ -287,6 +281,19 @@ htab_mod_m2 (hashval_t hash, htab_t htab) htab_t 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) +{ + return htab_create_typed_alloc (size, hash_f, eq_f, del_f, alloc_f, alloc_f, + free_f); +} + +/* As above, but uses the variants of ALLOC_F and FREE_F which accept + an extra argument. */ + +htab_t +htab_create_alloc_ex (size_t size, htab_hash hash_f, htab_eq eq_f, + htab_del del_f, void *alloc_arg, + htab_alloc_with_arg alloc_f, + htab_free_with_arg free_f) { htab_t result; unsigned int size_prime_index; @@ -294,14 +301,14 @@ htab_create_alloc (size_t size, htab_hash hash_f, htab_eq eq_f, size_prime_index = higher_prime_index (size); size = prime_tab[size_prime_index].prime; - result = (htab_t) (*alloc_f) (1, sizeof (struct htab)); + result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab)); if (result == NULL) return NULL; - result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR)); + result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR)); if (result->entries == NULL) { if (free_f != NULL) - (*free_f) (result); + (*free_f) (alloc_arg, result); return NULL; } result->size = size; @@ -309,19 +316,37 @@ htab_create_alloc (size_t size, htab_hash hash_f, htab_eq eq_f, result->hash_f = hash_f; result->eq_f = eq_f; result->del_f = del_f; - result->alloc_f = alloc_f; - result->free_f = free_f; + result->alloc_arg = alloc_arg; + result->alloc_with_arg_f = alloc_f; + result->free_with_arg_f = free_f; return result; } -/* As above, but use the variants of alloc_f and free_f which accept - an extra argument. */ +/* + +@deftypefn Supplemental htab_t htab_create_typed_alloc (size_t @var{size}, @ +htab_hash @var{hash_f}, htab_eq @var{eq_f}, htab_del @var{del_f}, @ +htab_alloc @var{alloc_tab_f}, htab_alloc @var{alloc_f}, @ +htab_free @var{free_f}) + +This function creates a hash table that uses two different allocators +@var{alloc_tab_f} and @var{alloc_f} to use for allocating the table itself +and its entries respectively. This is useful when variables of different +types need to be allocated with different allocators. + +The created hash table is slightly larger than @var{size} and it is +initially empty (all the hash table entries are @code{HTAB_EMPTY_ENTRY}). +The function returns the created hash table, or @code{NULL} if memory +allocation fails. + +@end deftypefn + +*/ htab_t -htab_create_alloc_ex (size_t size, htab_hash hash_f, htab_eq eq_f, - htab_del del_f, void *alloc_arg, - htab_alloc_with_arg alloc_f, - htab_free_with_arg free_f) +htab_create_typed_alloc (size_t size, htab_hash hash_f, htab_eq eq_f, + htab_del del_f, htab_alloc alloc_tab_f, + htab_alloc alloc_f, htab_free free_f) { htab_t result; unsigned int size_prime_index; @@ -329,14 +354,14 @@ htab_create_alloc_ex (size_t size, htab_hash hash_f, htab_eq eq_f, size_prime_index = higher_prime_index (size); size = prime_tab[size_prime_index].prime; - result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab)); + result = (htab_t) (*alloc_tab_f) (1, sizeof (struct htab)); if (result == NULL) return NULL; - result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR)); + result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR)); if (result->entries == NULL) { if (free_f != NULL) - (*free_f) (alloc_arg, result); + (*free_f) (result); return NULL; } result->size = size; @@ -344,12 +369,12 @@ htab_create_alloc_ex (size_t size, htab_hash hash_f, htab_eq eq_f, result->hash_f = hash_f; result->eq_f = eq_f; result->del_f = del_f; - result->alloc_arg = alloc_arg; - result->alloc_with_arg_f = alloc_f; - result->free_with_arg_f = free_f; + result->alloc_f = alloc_f; + result->free_f = free_f; return result; } + /* Update the function pointers and allocation parameter in the htab_t. */ void @@ -700,7 +725,7 @@ htab_remove_elt_with_hash (htab_t htab, PTR element, hashval_t hash) PTR *slot; slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT); - if (*slot == HTAB_EMPTY_ENTRY) + if (slot == NULL) return; if (htab->del_f) @@ -936,17 +961,17 @@ iterative_hash (const PTR k_in /* the key */, c += length; switch(len) /* all the case statements fall through */ { - case 11: c+=((hashval_t)k[10]<<24); - case 10: c+=((hashval_t)k[9]<<16); - case 9 : c+=((hashval_t)k[8]<<8); + case 11: c+=((hashval_t)k[10]<<24); /* fall through */ + case 10: c+=((hashval_t)k[9]<<16); /* fall through */ + case 9 : c+=((hashval_t)k[8]<<8); /* fall through */ /* the first byte of c is reserved for the length */ - case 8 : b+=((hashval_t)k[7]<<24); - case 7 : b+=((hashval_t)k[6]<<16); - case 6 : b+=((hashval_t)k[5]<<8); - case 5 : b+=k[4]; - case 4 : a+=((hashval_t)k[3]<<24); - case 3 : a+=((hashval_t)k[2]<<16); - case 2 : a+=((hashval_t)k[1]<<8); + case 8 : b+=((hashval_t)k[7]<<24); /* fall through */ + case 7 : b+=((hashval_t)k[6]<<16); /* fall through */ + case 6 : b+=((hashval_t)k[5]<<8); /* fall through */ + case 5 : b+=k[4]; /* fall through */ + case 4 : a+=((hashval_t)k[3]<<24); /* fall through */ + case 3 : a+=((hashval_t)k[2]<<16); /* fall through */ + case 2 : a+=((hashval_t)k[1]<<8); /* fall through */ case 1 : a+=k[0]; /* case 0: nothing left to add */ } @@ -954,3 +979,19 @@ iterative_hash (const PTR k_in /* the key */, /*-------------------------------------------- report the result */ return c; } + +/* Returns a hash code for pointer P. Simplified version of evahash */ + +static hashval_t +hash_pointer (const PTR p) +{ + intptr_t v = (intptr_t) p; + unsigned a, b, c; + + a = b = 0x9e3779b9; + a += v >> (sizeof (intptr_t) * CHAR_BIT / 2); + b += v & (((intptr_t) 1 << (sizeof (intptr_t) * CHAR_BIT / 2)) - 1); + c = 0x42135234; + mix (a, b, c); + return c; +}