1 /* Implement a cached obstack.
2 Written by Fred Fish <fnf@cygnus.com>
3 Rewritten by Jim Blandy <jimb@cygnus.com>
5 Copyright 1999, 2000, 2002 Free Software Foundation, Inc.
7 This file is part of GDB.
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2 of the License, or
12 (at your option) any later version.
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 59 Temple Place - Suite 330,
22 Boston, MA 02111-1307, USA. */
27 #include "gdb_string.h" /* For memcpy declaration */
32 /* The old hash function was stolen from SDBM. This is what DB 3.0 uses now,
33 * and is better than the old one.
37 hash(const void *addr
, int length
)
39 const unsigned char *k
, *e
;
42 k
= (const unsigned char *)addr
;
52 /* Growing the bcache's hash table. */
54 /* If the average chain length grows beyond this, then we want to
55 resize our hash table. */
56 #define CHAIN_LENGTH_THRESHOLD (5)
59 expand_hash_table (struct bcache
*bcache
)
61 /* A table of good hash table sizes. Whenever we grow, we pick the
62 next larger size from this table. sizes[i] is close to 1 << (i+10),
63 so we roughly double the table size each time. After we fall off
64 the end of this table, we just double. Don't laugh --- there have
65 been executables sighted with a gigabyte of debug info. */
66 static unsigned long sizes
[] = {
67 1021, 2053, 4099, 8191, 16381, 32771,
68 65537, 131071, 262144, 524287, 1048573, 2097143,
69 4194301, 8388617, 16777213, 33554467, 67108859, 134217757,
70 268435459, 536870923, 1073741827, 2147483659UL
72 unsigned int new_num_buckets
;
73 struct bstring
**new_buckets
;
76 /* Find the next size. */
77 new_num_buckets
= bcache
->num_buckets
* 2;
78 for (i
= 0; i
< (sizeof (sizes
) / sizeof (sizes
[0])); i
++)
79 if (sizes
[i
] > bcache
->num_buckets
)
81 new_num_buckets
= sizes
[i
];
85 /* Allocate the new table. */
87 size_t new_size
= new_num_buckets
* sizeof (new_buckets
[0]);
88 new_buckets
= (struct bstring
**) xmalloc (new_size
);
89 memset (new_buckets
, 0, new_size
);
91 bcache
->structure_size
-= (bcache
->num_buckets
92 * sizeof (bcache
->bucket
[0]));
93 bcache
->structure_size
+= new_size
;
96 /* Rehash all existing strings. */
97 for (i
= 0; i
< bcache
->num_buckets
; i
++)
99 struct bstring
*s
, *next
;
101 for (s
= bcache
->bucket
[i
]; s
; s
= next
)
103 struct bstring
**new_bucket
;
106 new_bucket
= &new_buckets
[(hash (&s
->d
.data
, s
->length
)
108 s
->next
= *new_bucket
;
113 /* Plug in the new table. */
115 xfree (bcache
->bucket
);
116 bcache
->bucket
= new_buckets
;
117 bcache
->num_buckets
= new_num_buckets
;
121 /* Looking up things in the bcache. */
123 /* The number of bytes needed to allocate a struct bstring whose data
125 #define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))
127 /* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has
128 never seen those bytes before, add a copy of them to BCACHE. In
129 either case, return a pointer to BCACHE's copy of that string. */
131 bcache (const void *addr
, int length
, struct bcache
*bcache
)
136 /* If our average chain length is too high, expand the hash table. */
137 if (bcache
->unique_count
>= bcache
->num_buckets
* CHAIN_LENGTH_THRESHOLD
)
138 expand_hash_table (bcache
);
140 bcache
->total_count
++;
141 bcache
->total_size
+= length
;
143 hash_index
= hash (addr
, length
) % bcache
->num_buckets
;
145 /* Search the hash bucket for a string identical to the caller's. */
146 for (s
= bcache
->bucket
[hash_index
]; s
; s
= s
->next
)
147 if (s
->length
== length
148 && ! memcmp (&s
->d
.data
, addr
, length
))
151 /* The user's string isn't in the list. Insert it after *ps. */
154 = obstack_alloc (&bcache
->cache
, BSTRING_SIZE (length
));
155 memcpy (&new->d
.data
, addr
, length
);
156 new->length
= length
;
157 new->next
= bcache
->bucket
[hash_index
];
158 bcache
->bucket
[hash_index
] = new;
160 bcache
->unique_count
++;
161 bcache
->unique_size
+= length
;
162 bcache
->structure_size
+= BSTRING_SIZE (length
);
169 /* Freeing bcaches. */
171 /* Free all the storage associated with BCACHE. */
173 free_bcache (struct bcache
*bcache
)
175 obstack_free (&bcache
->cache
, 0);
177 xfree (bcache
->bucket
);
179 /* This isn't necessary, but at least the bcache is always in a
181 memset (bcache
, 0, sizeof (*bcache
));
186 /* Printing statistics. */
189 compare_ints (const void *ap
, const void *bp
)
191 /* Because we know we're comparing two ints which are positive,
192 there's no danger of overflow here. */
193 return * (int *) ap
- * (int *) bp
;
198 print_percentage (int portion
, int total
)
201 printf_filtered ("(not applicable)\n");
203 printf_filtered ("%3d%%\n", portion
* 100 / total
);
207 /* Print statistics on BCACHE's memory usage and efficacity at
208 eliminating duplication. NAME should describe the kind of data
209 BCACHE holds. Statistics are printed using `printf_filtered' and
212 print_bcache_statistics (struct bcache
*c
, char *type
)
214 int occupied_buckets
;
215 int max_chain_length
;
216 int median_chain_length
;
218 /* Count the number of occupied buckets, and measure chain lengths. */
222 = (int *) alloca (c
->num_buckets
* sizeof (*chain_length
));
224 occupied_buckets
= 0;
226 for (b
= 0; b
< c
->num_buckets
; b
++)
228 struct bstring
*s
= c
->bucket
[b
];
244 /* To compute the median, we need the set of chain lengths sorted. */
245 qsort (chain_length
, c
->num_buckets
, sizeof (chain_length
[0]),
248 if (c
->num_buckets
> 0)
250 max_chain_length
= chain_length
[c
->num_buckets
- 1];
251 median_chain_length
= chain_length
[c
->num_buckets
/ 2];
255 max_chain_length
= 0;
256 median_chain_length
= 0;
260 printf_filtered (" Cached '%s' statistics:\n", type
);
261 printf_filtered (" Total object count: %ld\n", c
->total_count
);
262 printf_filtered (" Unique object count: %lu\n", c
->unique_count
);
263 printf_filtered (" Percentage of duplicates, by count: ");
264 print_percentage (c
->total_count
- c
->unique_count
, c
->total_count
);
265 printf_filtered ("\n");
267 printf_filtered (" Total object size: %ld\n", c
->total_size
);
268 printf_filtered (" Unique object size: %ld\n", c
->unique_size
);
269 printf_filtered (" Percentage of duplicates, by size: ");
270 print_percentage (c
->total_size
- c
->unique_size
, c
->total_size
);
271 printf_filtered ("\n");
273 printf_filtered (" Total memory used by bcache, including overhead: %ld\n",
275 printf_filtered (" Percentage memory overhead: ");
276 print_percentage (c
->structure_size
- c
->unique_size
, c
->unique_size
);
277 printf_filtered (" Net memory savings: ");
278 print_percentage (c
->total_size
- c
->structure_size
, c
->total_size
);
279 printf_filtered ("\n");
281 printf_filtered (" Hash table size: %3d\n", c
->num_buckets
);
282 printf_filtered (" Hash table population: ");
283 print_percentage (occupied_buckets
, c
->num_buckets
);
284 printf_filtered (" Median hash chain length: %3d\n",
285 median_chain_length
);
286 printf_filtered (" Average hash chain length: ");
287 if (c
->num_buckets
> 0)
288 printf_filtered ("%3lu\n", c
->unique_count
/ c
->num_buckets
);
290 printf_filtered ("(not applicable)\n");
291 printf_filtered (" Maximum hash chain length: %3d\n", max_chain_length
);
292 printf_filtered ("\n");
This page took 0.034725 seconds and 4 git commands to generate.