/* Implement a cached obstack.
Written by Fred Fish <fnf@cygnus.com>
Rewritten by Jim Blandy <jimb@cygnus.com>
- Copyright 1999, 2000 Free Software Foundation, Inc.
+
+ Copyright 1999, 2000, 2002, 2003 Free Software Foundation, Inc.
This file is part of GDB.
Foundation, Inc., 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA. */
-#include <stddef.h>
-#include <stdlib.h>
-
#include "defs.h"
-#include "obstack.h"
+#include "gdb_obstack.h"
#include "bcache.h"
#include "gdb_string.h" /* For memcpy declaration */
+#include "gdb_assert.h"
+
+#include <stddef.h>
+#include <stdlib.h>
+
+/* 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
+ same alignment as the most strict alignment of any type on the host
+ machine. I don't know of any really correct way to do this in
+ stock ANSI C, so just do it the same way obstack.h does. */
+
+struct bstring
+{
+ struct bstring *next;
+ size_t length;
+
+ union
+ {
+ char data[1];
+ double dummy;
+ }
+ d;
+};
+
+
+/* The structure for a bcache itself. The bcache is initialized, in
+ bcache_xmalloc(), by filling it with zeros and then setting the
+ corresponding obstack's malloc() and free() methods. */
+
+struct bcache
+{
+ /* All the bstrings are allocated here. */
+ struct obstack cache;
+
+ /* How many hash buckets we're using. */
+ unsigned int num_buckets;
+
+ /* Hash buckets. This table is allocated using malloc, so when we
+ grow the table we can return the old table to the system. */
+ struct bstring **bucket;
+
+ /* Statistics. */
+ unsigned long unique_count; /* number of unique strings */
+ long total_count; /* total number of strings cached, including dups */
+ long unique_size; /* size of unique strings, in bytes */
+ long total_size; /* total number of bytes cached, including dups */
+ long structure_size; /* total size of bcache, including infrastructure */
+ /* Number of times that the hash table is expanded and hence
+ re-built, and the corresponding number of times that a string is
+ [re]hashed as part of entering it into the expanded table. The
+ total number of hashes can be computed by adding TOTAL_COUNT to
+ expand_hash_count. */
+ unsigned long expand_count;
+ unsigned long expand_hash_count;
+};
/* The old hash function was stolen from SDBM. This is what DB 3.0 uses now,
* and is better than the old one.
struct bstring **new_buckets;
unsigned int i;
+ /* Count the stats. Every unique item needs to be re-hashed and
+ re-entered. */
+ bcache->expand_count++;
+ bcache->expand_hash_count += bcache->unique_count;
+
/* Find the next size. */
new_num_buckets = bcache->num_buckets * 2;
for (i = 0; i < (sizeof (sizes) / sizeof (sizes[0])); i++)
}
\f
-/* Freeing bcaches. */
+/* Allocating and freeing bcaches. */
+
+struct bcache *
+bcache_xmalloc (void)
+{
+ /* Allocate the bcache pre-zeroed. */
+ struct bcache *b = XCALLOC (1, struct bcache);
+ obstack_specify_allocation (&b->cache, 0, 0, xmalloc, xfree);
+ return b;
+}
/* Free all the storage associated with BCACHE. */
void
-free_bcache (struct bcache *bcache)
+bcache_xfree (struct bcache *bcache)
{
+ if (bcache == NULL)
+ return;
obstack_free (&bcache->cache, 0);
- if (bcache->bucket)
- xfree (bcache->bucket);
-
- /* This isn't necessary, but at least the bcache is always in a
- consistent state. */
- memset (bcache, 0, sizeof (*bcache));
+ xfree (bcache->bucket);
+ xfree (bcache);
}
int occupied_buckets;
int max_chain_length;
int median_chain_length;
+ int max_entry_size;
+ int median_entry_size;
- /* Count the number of occupied buckets, and measure chain lengths. */
+ /* Count the number of occupied buckets, tally the various string
+ lengths, and measure chain lengths. */
{
unsigned int b;
- int *chain_length
- = (int *) alloca (c->num_buckets * sizeof (*chain_length));
+ int *chain_length = XCALLOC (c->num_buckets + 1, int);
+ int *entry_size = XCALLOC (c->unique_count + 1, int);
+ int stringi = 0;
occupied_buckets = 0;
while (s)
{
+ gdb_assert (b < c->num_buckets);
chain_length[b]++;
+ gdb_assert (stringi < c->unique_count);
+ entry_size[stringi++] = s->length;
s = s->next;
}
}
/* To compute the median, we need the set of chain lengths sorted. */
qsort (chain_length, c->num_buckets, sizeof (chain_length[0]),
compare_ints);
+ qsort (entry_size, c->unique_count, sizeof (entry_size[0]),
+ compare_ints);
if (c->num_buckets > 0)
{
max_chain_length = 0;
median_chain_length = 0;
}
+ if (c->unique_count > 0)
+ {
+ max_entry_size = entry_size[c->unique_count - 1];
+ median_entry_size = entry_size[c->unique_count / 2];
+ }
+ else
+ {
+ max_entry_size = 0;
+ median_entry_size = 0;
+ }
+
+ xfree (chain_length);
+ xfree (entry_size);
}
printf_filtered (" Cached '%s' statistics:\n", type);
print_percentage (c->total_size - c->unique_size, c->total_size);
printf_filtered ("\n");
+ printf_filtered (" Max entry size: %d\n", max_entry_size);
+ printf_filtered (" Average entry size: ");
+ if (c->unique_count > 0)
+ printf_filtered ("%ld\n", c->unique_size / c->unique_count);
+ else
+ 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",
c->structure_size);
printf_filtered (" Percentage memory overhead: ");
printf_filtered ("\n");
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",
+ c->total_count + c->expand_hash_count);
printf_filtered (" Hash table population: ");
print_percentage (occupied_buckets, c->num_buckets);
printf_filtered (" Median hash chain length: %3d\n",
printf_filtered (" Maximum hash chain length: %3d\n", max_chain_length);
printf_filtered ("\n");
}
+
+int
+bcache_memory_used (struct bcache *bcache)
+{
+ return obstack_memory_used (&bcache->cache);
+}
projects / deliverable / binutils-gdb.git / blobdiff