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 */
31 /* The old hash function was stolen from SDBM. This is what DB 3.0 uses now,
32 * and is better than the old one.
36 hash(void *addr
, int length
)
38 const unsigned char *k
, *e
;
41 k
= (const unsigned char *)addr
;
51 /* Growing the bcache's hash table. */
53 /* If the average chain length grows beyond this, then we want to
54 resize our hash table. */
55 #define CHAIN_LENGTH_THRESHOLD (5)
58 expand_hash_table (struct bcache
*bcache
)
60 /* A table of good hash table sizes. Whenever we grow, we pick the
61 next larger size from this table. sizes[i] is close to 1 << (i+10),
62 so we roughly double the table size each time. After we fall off
63 the end of this table, we just double. Don't laugh --- there have
64 been executables sighted with a gigabyte of debug info. */
65 static unsigned long sizes
[] = {
66 1021, 2053, 4099, 8191, 16381, 32771,
67 65537, 131071, 262144, 524287, 1048573, 2097143,
68 4194301, 8388617, 16777213, 33554467, 67108859, 134217757,
69 268435459, 536870923, 1073741827, 2147483659UL
71 unsigned int new_num_buckets
;
72 struct bstring
**new_buckets
;
75 /* Find the next size. */
76 new_num_buckets
= bcache
->num_buckets
* 2;
77 for (i
= 0; i
< (sizeof (sizes
) / sizeof (sizes
[0])); i
++)
78 if (sizes
[i
] > bcache
->num_buckets
)
80 new_num_buckets
= sizes
[i
];
84 /* Allocate the new table. */
86 size_t new_size
= new_num_buckets
* sizeof (new_buckets
[0]);
87 new_buckets
= (struct bstring
**) xmalloc (new_size
);
88 memset (new_buckets
, 0, new_size
);
90 bcache
->structure_size
-= (bcache
->num_buckets
91 * sizeof (bcache
->bucket
[0]));
92 bcache
->structure_size
+= new_size
;
95 /* Rehash all existing strings. */
96 for (i
= 0; i
< bcache
->num_buckets
; i
++)
98 struct bstring
*s
, *next
;
100 for (s
= bcache
->bucket
[i
]; s
; s
= next
)
102 struct bstring
**new_bucket
;
105 new_bucket
= &new_buckets
[(hash (&s
->d
.data
, s
->length
)
107 s
->next
= *new_bucket
;
112 /* Plug in the new table. */
114 free (bcache
->bucket
);
115 bcache
->bucket
= new_buckets
;
116 bcache
->num_buckets
= new_num_buckets
;
120 /* Looking up things in the bcache. */
122 /* The number of bytes needed to allocate a struct bstring whose data
124 #define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))
126 /* Find a copy of the LENGTH bytes at ADDR in BCACHE. If BCACHE has
127 never seen those bytes before, add a copy of them to BCACHE. In
128 either case, return a pointer to BCACHE's copy of that string. */
130 bcache (void *addr
, int length
, struct bcache
*bcache
)
135 /* If our average chain length is too high, expand the hash table. */
136 if (bcache
->unique_count
>= bcache
->num_buckets
* CHAIN_LENGTH_THRESHOLD
)
137 expand_hash_table (bcache
);
139 bcache
->total_count
++;
140 bcache
->total_size
+= length
;
142 hash_index
= hash (addr
, length
) % bcache
->num_buckets
;
144 /* Search the hash bucket for a string identical to the caller's. */
145 for (s
= bcache
->bucket
[hash_index
]; s
; s
= s
->next
)
146 if (s
->length
== length
147 && ! memcmp (&s
->d
.data
, addr
, length
))
150 /* The user's string isn't in the list. Insert it after *ps. */
153 = obstack_alloc (&bcache
->cache
, BSTRING_SIZE (length
));
154 memcpy (&new->d
.data
, addr
, length
);
155 new->length
= length
;
156 new->next
= bcache
->bucket
[hash_index
];
157 bcache
->bucket
[hash_index
] = new;
159 bcache
->unique_count
++;
160 bcache
->unique_size
+= length
;
161 bcache
->structure_size
+= BSTRING_SIZE (length
);
168 /* Freeing bcaches. */
170 /* Free all the storage associated with BCACHE. */
172 free_bcache (struct bcache
*bcache
)
174 obstack_free (&bcache
->cache
, 0);
176 free (bcache
->bucket
);
178 /* This isn't necessary, but at least the bcache is always in a
180 memset (bcache
, 0, sizeof (*bcache
));
185 /* Printing statistics. */
188 compare_ints (const void *ap
, const void *bp
)
190 /* Because we know we're comparing two ints which are positive,
191 there's no danger of overflow here. */
192 return * (int *) ap
- * (int *) bp
;
197 print_percentage (int portion
, int total
)
200 printf_filtered ("(not applicable)\n");
202 printf_filtered ("%3d%%\n", portion
* 100 / total
);
206 /* Print statistics on BCACHE's memory usage and efficacity at
207 eliminating duplication. NAME should describe the kind of data
208 BCACHE holds. Statistics are printed using `printf_filtered' and
211 print_bcache_statistics (struct bcache
*c
, char *type
)
213 int occupied_buckets
;
214 int max_chain_length
;
215 int median_chain_length
;
217 /* Count the number of occupied buckets, and measure chain lengths. */
221 = (int *) alloca (c
->num_buckets
* sizeof (*chain_length
));
223 occupied_buckets
= 0;
225 for (b
= 0; b
< c
->num_buckets
; b
++)
227 struct bstring
*s
= c
->bucket
[b
];
243 /* To compute the median, we need the set of chain lengths sorted. */
244 qsort (chain_length
, c
->num_buckets
, sizeof (chain_length
[0]),
247 if (c
->num_buckets
> 0)
249 max_chain_length
= chain_length
[c
->num_buckets
- 1];
250 median_chain_length
= chain_length
[c
->num_buckets
/ 2];
254 max_chain_length
= 0;
255 median_chain_length
= 0;
259 printf_filtered (" Cached '%s' statistics:\n", type
);
260 printf_filtered (" Total object count: %ld\n", c
->total_count
);
261 printf_filtered (" Unique object count: %lu\n", c
->unique_count
);
262 printf_filtered (" Percentage of duplicates, by count: ");
263 print_percentage (c
->total_count
- c
->unique_count
, c
->total_count
);
264 printf_filtered ("\n");
266 printf_filtered (" Total object size: %ld\n", c
->total_size
);
267 printf_filtered (" Unique object size: %ld\n", c
->unique_size
);
268 printf_filtered (" Percentage of duplicates, by size: ");
269 print_percentage (c
->total_size
- c
->unique_size
, c
->total_size
);
270 printf_filtered ("\n");
272 printf_filtered (" Total memory used by bcache, including overhead: %ld\n",
274 printf_filtered (" Percentage memory overhead: ");
275 print_percentage (c
->structure_size
- c
->unique_size
, c
->unique_size
);
276 printf_filtered (" Net memory savings: ");
277 print_percentage (c
->total_size
- c
->structure_size
, c
->total_size
);
278 printf_filtered ("\n");
280 printf_filtered (" Hash table size: %3d\n", c
->num_buckets
);
281 printf_filtered (" Hash table population: ");
282 print_percentage (occupied_buckets
, c
->num_buckets
);
283 printf_filtered (" Median hash chain length: %3d\n",
284 median_chain_length
);
285 printf_filtered (" Average hash chain length: ");
286 if (c
->num_buckets
> 0)
287 printf_filtered ("%3lu\n", c
->unique_count
/ c
->num_buckets
);
289 printf_filtered ("(not applicable)\n");
290 printf_filtered (" Maximum hash chain length: %3d\n", max_chain_length
);
291 printf_filtered ("\n");
This page took 0.035009 seconds and 4 git commands to generate.