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
89 struct bstring **new_buckets;
92 /* Find the next size. */
93 for (i = 0; i < (sizeof (sizes) / sizeof (sizes[0])); i++)
94 if (sizes[i] > bcache->num_buckets)
96 new_num_buckets = sizes[i];
99 if (i >= (sizeof (sizes) / sizeof (sizes[0])))
100 new_num_buckets = bcache->num_buckets * 2;
102 /* Allocate the new table. */
104 size_t new_size = new_num_buckets * sizeof (new_buckets[0]);
105 new_buckets = (struct bstring **) xmalloc (new_size);
106 memset (new_buckets, 0, new_size);
108 bcache->structure_size -= (bcache->num_buckets
109 * sizeof (bcache->bucket[0]));
110 bcache->structure_size += new_size;
113 /* Rehash all existing strings. */
114 for (i = 0; i < bcache->num_buckets; i++)
116 struct bstring *s, *next;
118 for (s = bcache->bucket[i]; s; s = next)
120 struct bstring **new_bucket;
123 new_bucket = &new_buckets[(hash (&s->d.data, s->length)
125 s->next = *new_bucket;
130 /* Plug in the new table. */
132 free (bcache->bucket);
133 bcache->bucket = new_buckets;
134 bcache->num_buckets = new_num_buckets;
138 /* Looking up things in the bcache. */
140 /* The number of bytes needed to allocate a struct bstring whose data
142 #define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))
144 /* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has
145 never seen those bytes before, add a copy of them to BCACHE. In
146 either case, return a pointer to BCACHE's copy of that string. */
148 bcache (void *addr, int length, struct bcache *bcache)
153 /* If our average chain length is too high, expand the hash table. */
154 if (bcache->unique_count >= bcache->num_buckets * CHAIN_LENGTH_THRESHOLD)
155 expand_hash_table (bcache);
157 bcache->total_count++;
158 bcache->total_size += length;
160 hash_index = hash (addr, length) % bcache->num_buckets;
162 /* Search the hash bucket for a string identical to the caller's. */
163 for (s = bcache->bucket[hash_index]; s; s = s->next)
164 if (s->length == length
165 && ! memcmp (&s->d.data, addr, length))
168 /* The user's string isn't in the list. Insert it after *ps. */
171 = obstack_alloc (&bcache->cache, BSTRING_SIZE (length));
172 memcpy (&new->d.data, addr, length);
173 new->length = length;
174 new->next = bcache->bucket[hash_index];
175 bcache->bucket[hash_index] = new;
177 bcache->unique_count++;
178 bcache->unique_size += length;
179 bcache->structure_size += BSTRING_SIZE (length);
186 /* Freeing bcaches. */
188 /* Free all the storage associated with BCACHE. */
190 free_bcache (struct bcache *bcache)
192 obstack_free (&bcache->cache, 0);
193 free (bcache->bucket);
195 /* This isn't necessary, but at least the bcache is always in a
197 memset (bcache, 0, sizeof (*bcache));
202 /* Printing statistics. */
205 compare_ints (const void *ap, const void *bp)
207 /* Because we know we're comparing two ints which are positive,
208 there's no danger of overflow here. */
209 return * (int *) ap - * (int *) bp;
214 print_percentage (int portion, int total)
217 printf_filtered ("(not applicable)\n");
219 printf_filtered ("%3d%%\n", portion * 100 / total);
223 /* Print statistics on BCACHE's memory usage and efficacity at
224 eliminating duplication. NAME should describe the kind of data
225 BCACHE holds. Statistics are printed using `printf_filtered' and
228 print_bcache_statistics (struct bcache *c, char *type)
230 int occupied_buckets;
231 int max_chain_length;
232 int median_chain_length;
234 /* Count the number of occupied buckets, and measure chain lengths. */
238 = (int *) alloca (c->num_buckets * sizeof (*chain_length));
240 occupied_buckets = 0;
242 for (b = 0; b < c->num_buckets; b++)
244 struct bstring *s = c->bucket[b];
260 /* To compute the median, we need the set of chain lengths sorted. */
261 qsort (chain_length, c->num_buckets, sizeof (chain_length[0]),
264 if (c->num_buckets > 0)
266 max_chain_length = chain_length[c->num_buckets - 1];
267 median_chain_length = chain_length[c->num_buckets / 2];
271 max_chain_length = 0;
272 median_chain_length = 0;
276 printf_filtered (" Cached '%s' statistics:\n", type);
277 printf_filtered (" Total object count: %ld\n", c->total_count);
278 printf_filtered (" Unique object count: %ld\n", c->unique_count);
279 printf_filtered (" Percentage of duplicates, by count: ");
280 print_percentage (c->total_count - c->unique_count, c->total_count);
281 printf_filtered ("\n");
283 printf_filtered (" Total object size: %ld\n", c->total_size);
284 printf_filtered (" Unique object size: %ld\n", c->unique_size);
285 printf_filtered (" Percentage of duplicates, by size: ");
286 print_percentage (c->total_size - c->unique_size, c->total_size);
287 printf_filtered ("\n");
289 printf_filtered (" Total memory used by bcache, including overhead: %ld\n",
291 printf_filtered (" Percentage memory overhead: ");
292 print_percentage (c->structure_size - c->unique_size, c->unique_size);
293 printf_filtered (" Net memory savings: ");
294 print_percentage (c->total_size - c->structure_size, c->total_size);
295 printf_filtered ("\n");
297 printf_filtered (" Hash table size: %3d\n", c->num_buckets);
298 printf_filtered (" Hash table population: ");
299 print_percentage (occupied_buckets, c->num_buckets);
300 printf_filtered (" Median hash chain length: %3d\n",
301 median_chain_length);
302 printf_filtered (" Average hash chain length: ");
303 if (c->num_buckets > 0)
304 printf_filtered ("%3ld\n", c->unique_count / c->num_buckets);
306 printf_filtered ("(not applicable)\n");
307 printf_filtered (" Maximum hash chain length: %3d\n", max_chain_length);
308 printf_filtered ("\n");