X-Git-Url: http://git.efficios.com/?a=blobdiff_plain;f=gdb%2Fbcache.c;h=65ff8445a9db8731717c991b907457a281887d46;hb=8929ad8bbca9a8b036eba0397992d6f3b4d1966b;hp=f96993ba52992eadaee98d1198f92eb7172d6f63;hpb=e6ad058ac447711a1175a07b168bfb27d3ed7ce8;p=deliverable%2Fbinutils-gdb.git diff --git a/gdb/bcache.c b/gdb/bcache.c index f96993ba52..65ff8445a9 100644 --- a/gdb/bcache.c +++ b/gdb/bcache.c @@ -2,8 +2,7 @@ Written by Fred Fish Rewritten by Jim Blandy - Copyright (C) 1999, 2000, 2002, 2003, 2007, 2008 - Free Software Foundation, Inc. + Copyright (C) 1999-2016 Free Software Foundation, Inc. This file is part of GDB. @@ -23,11 +22,6 @@ #include "defs.h" #include "gdb_obstack.h" #include "bcache.h" -#include "gdb_string.h" /* For memcpy declaration */ -#include "gdb_assert.h" - -#include -#include /* The type used to hold a single bcache string. The user data is stored in d.data. Since it can be any type, it needs to have the @@ -89,26 +83,38 @@ struct bcache 16 bits of hash values) hit, but the corresponding combined length/data compare missed. */ unsigned long half_hash_miss_count; + + /* Hash function to be used for this bcache object. */ + unsigned long (*hash_function)(const void *addr, int length); + + /* Compare function to be used for this bcache object. */ + int (*compare_function)(const void *, const void *, int length); }; -/* The old hash function was stolen from SDBM. This is what DB 3.0 uses now, - * and is better than the old one. - */ +/* The old hash function was stolen from SDBM. This is what DB 3.0 + uses now, and is better than the old one. */ unsigned long hash(const void *addr, int length) { - const unsigned char *k, *e; - unsigned long h; - - k = (const unsigned char *)addr; - e = k+length; - for (h=0; k< e;++k) - { - h *=16777619; - h ^= *k; - } - return (h); + return hash_continue (addr, length, 0); +} + +/* Continue the calculation of the hash H at the given address. */ + +unsigned long +hash_continue (const void *addr, int length, unsigned long h) +{ + const unsigned char *k, *e; + + k = (const unsigned char *)addr; + e = k+length; + for (; k< e;++k) + { + h *=16777619; + h ^= *k; + } + return (h); } /* Growing the bcache's hash table. */ @@ -152,6 +158,7 @@ expand_hash_table (struct bcache *bcache) /* Allocate the new table. */ { size_t new_size = new_num_buckets * sizeof (new_buckets[0]); + new_buckets = (struct bstring **) xmalloc (new_size); memset (new_buckets, 0, new_size); @@ -170,7 +177,8 @@ expand_hash_table (struct bcache *bcache) struct bstring **new_bucket; next = s->next; - new_bucket = &new_buckets[(hash (&s->d.data, s->length) + new_bucket = &new_buckets[(bcache->hash_function (&s->d.data, + s->length) % new_num_buckets)]; s->next = *new_bucket; *new_bucket = s; @@ -195,9 +203,9 @@ expand_hash_table (struct bcache *bcache) never seen those bytes before, add a copy of them to BCACHE. In either case, return a pointer to BCACHE's copy of that string. */ const void * -bcache (const void *addr, int length, struct bcache *bcache) +bcache (const void *addr, int length, struct bcache *cache) { - return bcache_full (addr, length, bcache, NULL); + return bcache_full (addr, length, cache, NULL); } /* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has @@ -234,7 +242,8 @@ bcache_full (const void *addr, int length, struct bcache *bcache, int *added) bcache->total_count++; bcache->total_size += length; - full_hash = hash (addr, length); + full_hash = bcache->hash_function (addr, length); + half_hash = (full_hash >> 16); hash_index = full_hash % bcache->num_buckets; @@ -246,7 +255,7 @@ bcache_full (const void *addr, int length, struct bcache *bcache, int *added) if (s->half_hash == half_hash) { if (s->length == length - && ! memcmp (&s->d.data, addr, length)) + && bcache->compare_function (&s->d.data, addr, length)) return &s->d.data; else bcache->half_hash_miss_count++; @@ -255,13 +264,15 @@ bcache_full (const void *addr, int length, struct bcache *bcache, int *added) /* The user's string isn't in the list. Insert it after *ps. */ { - struct bstring *new - = obstack_alloc (&bcache->cache, BSTRING_SIZE (length)); - memcpy (&new->d.data, addr, length); - new->length = length; - new->next = bcache->bucket[hash_index]; - new->half_hash = half_hash; - bcache->bucket[hash_index] = new; + struct bstring *newobj + = (struct bstring *) obstack_alloc (&bcache->cache, + BSTRING_SIZE (length)); + + memcpy (&newobj->d.data, addr, length); + newobj->length = length; + newobj->next = bcache->bucket[hash_index]; + newobj->half_hash = half_hash; + bcache->bucket[hash_index] = newobj; bcache->unique_count++; bcache->unique_size += length; @@ -270,17 +281,45 @@ bcache_full (const void *addr, int length, struct bcache *bcache, int *added) if (added) *added = 1; - return &new->d.data; + return &newobj->d.data; } } + +/* Compare the byte string at ADDR1 of lenght LENGHT to the + string at ADDR2. Return 1 if they are equal. */ + +static int +bcache_compare (const void *addr1, const void *addr2, int length) +{ + return memcmp (addr1, addr2, length) == 0; +} + /* Allocating and freeing bcaches. */ +/* Allocated a bcache. HASH_FUNCTION and COMPARE_FUNCTION can be used + to pass in custom hash, and compare functions to be used by this + bcache. If HASH_FUNCTION is NULL hash() is used and if + COMPARE_FUNCTION is NULL memcmp() is used. */ + struct bcache * -bcache_xmalloc (void) +bcache_xmalloc (unsigned long (*hash_function)(const void *, int length), + int (*compare_function)(const void *, + const void *, + int length)) { /* Allocate the bcache pre-zeroed. */ - struct bcache *b = XCALLOC (1, struct bcache); + struct bcache *b = XCNEW (struct bcache); + + if (hash_function) + b->hash_function = hash_function; + else + b->hash_function = hash; + + if (compare_function) + b->compare_function = compare_function; + else + b->compare_function = bcache_compare; return b; } @@ -301,20 +340,11 @@ bcache_xfree (struct bcache *bcache) /* Printing statistics. */ -static int -compare_ints (const void *ap, const void *bp) -{ - /* Because we know we're comparing two ints which are positive, - there's no danger of overflow here. */ - return * (int *) ap - * (int *) bp; -} - - static void print_percentage (int portion, int total) { if (total == 0) - /* i18n: Like "Percentage of duplicates, by count: (not applicable)" */ + /* i18n: Like "Percentage of duplicates, by count: (not applicable)". */ printf_filtered (_("(not applicable)\n")); else printf_filtered ("%3d%%\n", (int) (portion * 100.0 / total)); @@ -338,8 +368,8 @@ print_bcache_statistics (struct bcache *c, char *type) lengths, and measure chain lengths. */ { unsigned int b; - int *chain_length = XCALLOC (c->num_buckets + 1, int); - int *entry_size = XCALLOC (c->unique_count + 1, int); + int *chain_length = XCNEWVEC (int, c->num_buckets + 1); + int *entry_size = XCNEWVEC (int, c->unique_count + 1); int stringi = 0; occupied_buckets = 0; @@ -365,11 +395,12 @@ print_bcache_statistics (struct bcache *c, char *type) } } - /* To compute the median, we need the set of chain lengths sorted. */ + /* To compute the median, we need the set of chain lengths + sorted. */ qsort (chain_length, c->num_buckets, sizeof (chain_length[0]), - compare_ints); + compare_positive_ints); qsort (entry_size, c->unique_count, sizeof (entry_size[0]), - compare_ints); + compare_positive_ints); if (c->num_buckets > 0) { @@ -414,12 +445,13 @@ print_bcache_statistics (struct bcache *c, char *type) if (c->unique_count > 0) printf_filtered ("%ld\n", c->unique_size / c->unique_count); else - /* i18n: "Average entry size: (not applicable)" */ + /* i18n: "Average entry size: (not applicable)". */ printf_filtered (_("(not applicable)\n")); printf_filtered (_(" Median entry size: %d\n"), median_entry_size); printf_filtered ("\n"); - printf_filtered (_(" Total memory used by bcache, including overhead: %ld\n"), + printf_filtered (_(" \ +Total memory used by bcache, including overhead: %ld\n"), c->structure_size); printf_filtered (_(" Percentage memory overhead: ")); print_percentage (c->structure_size - c->unique_size, c->unique_size); @@ -427,7 +459,8 @@ print_bcache_statistics (struct bcache *c, char *type) print_percentage (c->total_size - c->structure_size, c->total_size); printf_filtered ("\n"); - printf_filtered (_(" Hash table size: %3d\n"), c->num_buckets); + printf_filtered (_(" Hash table size: %3d\n"), + c->num_buckets); printf_filtered (_(" Hash table expands: %lu\n"), c->expand_count); printf_filtered (_(" Hash table hashes: %lu\n"), @@ -442,9 +475,10 @@ print_bcache_statistics (struct bcache *c, char *type) if (c->num_buckets > 0) printf_filtered ("%3lu\n", c->unique_count / c->num_buckets); else - /* i18n: "Average hash chain length: (not applicable)" */ + /* i18n: "Average hash chain length: (not applicable)". */ printf_filtered (_("(not applicable)\n")); - printf_filtered (_(" Maximum hash chain length: %3d\n"), max_chain_length); + printf_filtered (_(" Maximum hash chain length: %3d\n"), + max_chain_length); printf_filtered ("\n"); }