X-Git-Url: http://drtracing.org/?a=blobdiff_plain;f=gdb%2Fbcache.c;h=712142dac7f0693244bdf6951a2c5757acf80659;hb=45a466b578083a05f1138eff9232254b1a30f683;hp=cc4ee616e026d0d710d5f49cf5e168a2f45f0f9e;hpb=3d263c1d0a2f82fcf209a00e029b32ac8cf8f838;p=deliverable%2Fbinutils-gdb.git diff --git a/gdb/bcache.c b/gdb/bcache.c index cc4ee616e0..712142dac7 100644 --- a/gdb/bcache.c +++ b/gdb/bcache.c @@ -2,13 +2,13 @@ Written by Fred Fish Rewritten by Jim Blandy - Copyright 1999, 2000, 2002, 2003 Free Software Foundation, Inc. + Copyright (C) 1999-2013 Free Software Foundation, Inc. This file is part of GDB. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2 of the License, or + the Free Software Foundation; either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, @@ -17,9 +17,7 @@ GNU General Public License for more details. You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 59 Temple Place - Suite 330, - Boston, MA 02111-1307, USA. */ + along with this program. If not, see . */ #include "defs.h" #include "gdb_obstack.h" @@ -90,26 +88,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. */ @@ -153,6 +163,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); @@ -171,7 +182,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,14 +207,39 @@ expand_hash_table (struct bcache *bcache) /* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has 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. */ -static void * -bcache_data (const void *addr, int length, struct bcache *bcache) +const void * +bcache (const void *addr, int length, struct bcache *cache) +{ + return bcache_full (addr, length, cache, NULL); +} + +/* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has + 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. If + optional ADDED is not NULL, return 1 in case of new entry or 0 if + returning an old entry. */ + +const void * +bcache_full (const void *addr, int length, struct bcache *bcache, int *added) { unsigned long full_hash; unsigned short half_hash; int hash_index; struct bstring *s; + if (added) + *added = 0; + + /* Lazily initialize the obstack. This can save quite a bit of + memory in some cases. */ + if (bcache->total_count == 0) + { + /* We could use obstack_specify_allocation here instead, but + gdb_obstack.h specifies the allocation/deallocation + functions. */ + obstack_init (&bcache->cache); + } + /* If our average chain length is too high, expand the hash table. */ if (bcache->unique_count >= bcache->num_buckets * CHAIN_LENGTH_THRESHOLD) expand_hash_table (bcache); @@ -210,7 +247,8 @@ bcache_data (const void *addr, int length, struct bcache *bcache) 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; @@ -222,7 +260,7 @@ bcache_data (const void *addr, int length, struct bcache *bcache) 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++; @@ -233,6 +271,7 @@ bcache_data (const void *addr, int length, struct bcache *bcache) { 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]; @@ -243,33 +282,48 @@ bcache_data (const void *addr, int length, struct bcache *bcache) bcache->unique_size += length; bcache->structure_size += BSTRING_SIZE (length); + if (added) + *added = 1; + return &new->d.data; } } + -void * -deprecated_bcache (const void *addr, int length, struct bcache *bcache) -{ - return bcache_data (addr, length, bcache); -} +/* Compare the byte string at ADDR1 of lenght LENGHT to the + string at ADDR2. Return 1 if they are equal. */ -const void * -bcache (const void *addr, int length, struct bcache *bcache) +static int +bcache_compare (const void *addr1, const void *addr2, int length) { - return bcache_data (addr, length, bcache); + 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); - /* We could use obstack_specify_allocation here instead, but - gdb_obstack.h specifies the allocation/deallocation - functions. */ - obstack_init (&b->cache); + + 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; } @@ -279,7 +333,9 @@ bcache_xfree (struct bcache *bcache) { if (bcache == NULL) return; - obstack_free (&bcache->cache, 0); + /* Only free the obstack if we actually initialized it. */ + if (bcache->total_count > 0) + obstack_free (&bcache->cache, 0); xfree (bcache->bucket); xfree (bcache); } @@ -288,20 +344,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)); @@ -352,11 +399,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) { @@ -401,12 +449,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); @@ -414,7 +463,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"), @@ -429,14 +479,17 @@ 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"); } int bcache_memory_used (struct bcache *bcache) { + if (bcache->total_count == 0) + return 0; return obstack_memory_used (&bcache->cache); }