X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;ds=sidebyside;f=libiberty%2Fhashtab.c;h=04607ea6a0167bb2c48a7ac847bc5ac968b3a783;hb=6622a3046a1bc94add0dba0d18529babb9d30026;hp=a5671a0a768041bc12a4e62473ea12aa3afc7fc4;hpb=01f0fe5e0450edf168c1f612feb93cf588e4e7ea;p=platform%2Fupstream%2Fbinutils.git diff --git a/libiberty/hashtab.c b/libiberty/hashtab.c index a5671a0..04607ea 100644 --- a/libiberty/hashtab.c +++ b/libiberty/hashtab.c @@ -1,5 +1,5 @@ /* An expandable hash tables datatype. - Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004 + Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2009, 2010 Free Software Foundation, Inc. Contributed by Vladimir Makarov (vmakarov@cygnus.com). @@ -50,6 +50,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 +194,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) ((long)p >> 3); -} - /* Returns non-zero if P1 and P2 are equal. */ static int @@ -288,20 +283,33 @@ 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; 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 +317,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 +355,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 +370,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 @@ -421,7 +447,28 @@ htab_empty (htab_t htab) if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY) (*htab->del_f) (entries[i]); - memset (entries, 0, size * sizeof (PTR)); + /* Instead of clearing megabyte, downsize the table. */ + if (size > 1024*1024 / sizeof (PTR)) + { + int nindex = higher_prime_index (1024 / sizeof (PTR)); + int nsize = prime_tab[nindex].prime; + + if (htab->free_f != NULL) + (*htab->free_f) (htab->entries); + else if (htab->free_with_arg_f != NULL) + (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries); + if (htab->alloc_with_arg_f != NULL) + htab->entries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize, + sizeof (PTR *)); + else + htab->entries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *)); + htab->size = nsize; + htab->size_prime_index = nindex; + } + else + memset (entries, 0, size * sizeof (PTR)); + htab->n_deleted = 0; + htab->n_elements = 0; } /* Similar to htab_find_slot, but without several unwanted side effects: @@ -738,7 +785,8 @@ htab_traverse_noresize (htab_t htab, htab_trav callback, PTR info) void htab_traverse (htab_t htab, htab_trav callback, PTR info) { - if (htab_elements (htab) * 8 < htab_size (htab)) + size_t size = htab_size (htab); + if (htab_elements (htab) * 8 < size && size > 32) htab_expand (htab); htab_traverse_noresize (htab, callback, info); @@ -932,3 +980,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; +}