Written by Fred Fish <fnf@cygnus.com>
Rewritten by Jim Blandy <jimb@cygnus.com>
- Copyright (C) 1999, 2000, 2002, 2003, 2007, 2008
- Free Software Foundation, Inc.
+ Copyright (C) 1999-2014 Free Software Foundation, Inc.
This file is part of GDB.
#include "defs.h"
#include "gdb_obstack.h"
#include "bcache.h"
-#include "gdb_string.h" /* For memcpy declaration */
+#include <string.h> /* For memcpy declaration */
#include "gdb_assert.h"
#include <stddef.h>
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. */
\f
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);
}
\f
/* Growing the bcache's hash table. */
/* 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);
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;
/* 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);
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;
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++;
{
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];
bcache->unique_size += length;
bcache->structure_size += BSTRING_SIZE (length);
+ if (added)
+ *added = 1;
+
return &new->d.data;
}
}
+\f
-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;
}
-\f
+
/* 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;
}
{
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);
}
\f
/* 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));
}
}
- /* 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)
{
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);
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"),
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);
}