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);
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: %lu\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 ("%3lu\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");
This page took 0.037465 seconds and 4 git commands to generate.