1 /* Implement a cached obstack.
2 Written by Fred Fish <fnf@cygnus.com>
3 Rewritten by Jim Blandy <jimb@cygnus.com>
4 Copyright 1999 Free Software Foundation, Inc.
6 This file is part of GDB.
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
29 #include "gdb_string.h" /* For memcpy declaration */
33 /* The hash function. */
36 hash (void *addr, int length)
38 /* If it's a short string, hash on every character. Otherwise, sample
39 characters from throughout the string. */
46 for (i = 0; i < length; i++)
47 h = h * 65793 ^ (h >> (sizeof (h) * 8 - 6)) ^ byte[i];
57 for (n = i = 0; n < 64; n++)
59 h = h * 65793 + (h >> (sizeof (h) * 8 - 6)) + byte[i];
68 /* Growing the bcache's hash table. */
70 /* If the average chain length grows beyond this, then we want to
71 resize our hash table. */
72 #define CHAIN_LENGTH_THRESHOLD (5)
75 expand_hash_table (struct bcache *bcache)
77 /* A table of good hash table sizes. Whenever we grow, we pick the
78 next larger size from this table. sizes[i] is close to 1 << (i+10),
79 so we roughly double the table size each time. After we fall off
80 the end of this table, we just double. Don't laugh --- there have
81 been executables sighted with a gigabyte of debug info. */
82 static unsigned long sizes[] = {
83 1021, 2053, 4099, 8191, 16381, 32771,
84 65537, 131071, 262144, 524287, 1048573, 2097143,
85 4194301, 8388617, 16777213, 33554467, 67108859, 134217757,
86 268435459, 536870923, 1073741827, 2147483659UL
88 unsigned int new_num_buckets;
89 struct bstring **new_buckets;
92 /* Find the next size. */
93 new_num_buckets = bcache->num_buckets * 2;
94 for (i = 0; i < (sizeof (sizes) / sizeof (sizes[0])); i++)
95 if (sizes[i] > bcache->num_buckets)
97 new_num_buckets = sizes[i];
101 /* Allocate the new table. */
103 size_t new_size = new_num_buckets * sizeof (new_buckets[0]);
104 new_buckets = (struct bstring **) xmalloc (new_size);
105 memset (new_buckets, 0, new_size);
107 bcache->structure_size -= (bcache->num_buckets
108 * sizeof (bcache->bucket[0]));
109 bcache->structure_size += new_size;
112 /* Rehash all existing strings. */
113 for (i = 0; i < bcache->num_buckets; i++)
115 struct bstring *s, *next;
117 for (s = bcache->bucket[i]; s; s = next)
119 struct bstring **new_bucket;
122 new_bucket = &new_buckets[(hash (&s->d.data, s->length)
124 s->next = *new_bucket;
129 /* Plug in the new table. */
131 free (bcache->bucket);
132 bcache->bucket = new_buckets;
133 bcache->num_buckets = new_num_buckets;
137 /* Looking up things in the bcache. */
139 /* The number of bytes needed to allocate a struct bstring whose data
141 #define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))
143 /* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has
144 never seen those bytes before, add a copy of them to BCACHE. In
145 either case, return a pointer to BCACHE's copy of that string. */
147 bcache (void *addr, int length, struct bcache *bcache)
152 /* If our average chain length is too high, expand the hash table. */
153 if (bcache->unique_count >= bcache->num_buckets * CHAIN_LENGTH_THRESHOLD)
154 expand_hash_table (bcache);
156 bcache->total_count++;
157 bcache->total_size += length;
159 hash_index = hash (addr, length) % bcache->num_buckets;
161 /* Search the hash bucket for a string identical to the caller's. */
162 for (s = bcache->bucket[hash_index]; s; s = s->next)
163 if (s->length == length
164 && ! memcmp (&s->d.data, addr, length))
167 /* The user's string isn't in the list. Insert it after *ps. */
170 = obstack_alloc (&bcache->cache, BSTRING_SIZE (length));
171 memcpy (&new->d.data, addr, length);
172 new->length = length;
173 new->next = bcache->bucket[hash_index];
174 bcache->bucket[hash_index] = new;
176 bcache->unique_count++;
177 bcache->unique_size += length;
178 bcache->structure_size += BSTRING_SIZE (length);
185 /* Freeing bcaches. */
187 /* Free all the storage associated with BCACHE. */
189 free_bcache (struct bcache *bcache)
191 obstack_free (&bcache->cache, 0);
192 free (bcache->bucket);
194 /* This isn't necessary, but at least the bcache is always in a
196 memset (bcache, 0, sizeof (*bcache));
201 /* Printing statistics. */
204 compare_ints (const void *ap, const void *bp)
206 /* Because we know we're comparing two ints which are positive,
207 there's no danger of overflow here. */
208 return * (int *) ap - * (int *) bp;
213 print_percentage (int portion, int total)
216 printf_filtered ("(not applicable)\n");
218 printf_filtered ("%3d%%\n", portion * 100 / total);
222 /* Print statistics on BCACHE's memory usage and efficacity at
223 eliminating duplication. NAME should describe the kind of data
224 BCACHE holds. Statistics are printed using `printf_filtered' and
227 print_bcache_statistics (struct bcache *c, char *type)
229 int occupied_buckets;
230 int max_chain_length;
231 int median_chain_length;
233 /* Count the number of occupied buckets, and measure chain lengths. */
237 = (int *) alloca (c->num_buckets * sizeof (*chain_length));
239 occupied_buckets = 0;
241 for (b = 0; b < c->num_buckets; b++)
243 struct bstring *s = c->bucket[b];
259 /* To compute the median, we need the set of chain lengths sorted. */
260 qsort (chain_length, c->num_buckets, sizeof (chain_length[0]),
263 if (c->num_buckets > 0)
265 max_chain_length = chain_length[c->num_buckets - 1];
266 median_chain_length = chain_length[c->num_buckets / 2];
270 max_chain_length = 0;
271 median_chain_length = 0;
275 printf_filtered (" Cached '%s' statistics:\n", type);
276 printf_filtered (" Total object count: %ld\n", c->total_count);
277 printf_filtered (" Unique object count: %lu\n", c->unique_count);
278 printf_filtered (" Percentage of duplicates, by count: ");
279 print_percentage (c->total_count - c->unique_count, c->total_count);
280 printf_filtered ("\n");
282 printf_filtered (" Total object size: %ld\n", c->total_size);
283 printf_filtered (" Unique object size: %ld\n", c->unique_size);
284 printf_filtered (" Percentage of duplicates, by size: ");
285 print_percentage (c->total_size - c->unique_size, c->total_size);
286 printf_filtered ("\n");
288 printf_filtered (" Total memory used by bcache, including overhead: %ld\n",
290 printf_filtered (" Percentage memory overhead: ");
291 print_percentage (c->structure_size - c->unique_size, c->unique_size);
292 printf_filtered (" Net memory savings: ");
293 print_percentage (c->total_size - c->structure_size, c->total_size);
294 printf_filtered ("\n");
296 printf_filtered (" Hash table size: %3d\n", c->num_buckets);
297 printf_filtered (" Hash table population: ");
298 print_percentage (occupied_buckets, c->num_buckets);
299 printf_filtered (" Median hash chain length: %3d\n",
300 median_chain_length);
301 printf_filtered (" Average hash chain length: ");
302 if (c->num_buckets > 0)
303 printf_filtered ("%3lu\n", c->unique_count / c->num_buckets);
305 printf_filtered ("(not applicable)\n");
306 printf_filtered (" Maximum hash chain length: %3d\n", max_chain_length);
307 printf_filtered ("\n");