98 hash(
const void *addr,
int length)
108 const unsigned char *k, *e;
110 k = (
const unsigned char *)addr;
124 #define CHAIN_LENGTH_THRESHOLD (5)
134 static unsigned long sizes[] = {
135 1021, 2053, 4099, 8191, 16381, 32771,
136 65537, 131071, 262144, 524287, 1048573, 2097143,
137 4194301, 8388617, 16777213, 33554467, 67108859, 134217757,
138 268435459, 536870923, 1073741827, 2147483659UL
140 unsigned int new_num_buckets;
151 for (i = 0; i < (
sizeof (sizes) /
sizeof (sizes[0])); i++)
154 new_num_buckets = sizes[i];
160 size_t new_size = new_num_buckets *
sizeof (new_buckets[0]);
163 memset (new_buckets, 0, new_size);
166 *
sizeof (bcache->
bucket[0]));
175 for (s = bcache->
bucket[i]; s; s = next)
183 s->
next = *new_bucket;
191 bcache->
bucket = new_buckets;
200 #define BSTRING_SIZE(n) (offsetof (struct bstring, d.data) + (n))
220 unsigned long full_hash;
235 obstack_init (&bcache->
cache);
247 half_hash = (full_hash >> 16);
253 for (s = bcache->
bucket[hash_index]; s; s = s->
next)
270 memcpy (&newobj->
d.
data, addr, length);
274 bcache->
bucket[hash_index] = newobj;
283 return &newobj->
d.
data;
294 return memcmp (addr1, addr2, length) == 0;
333 obstack_free (&bcache->
cache, 0);
360 int occupied_buckets;
361 int max_chain_length;
362 int median_chain_length;
364 int median_entry_size;
370 int *chain_length = XCNEWVEC (
int, c->
num_buckets + 1);
374 occupied_buckets = 0;
391 entry_size[stringi++] = s->
length;
406 max_chain_length = chain_length[c->
num_buckets - 1];
407 median_chain_length = chain_length[c->
num_buckets / 2];
411 max_chain_length = 0;
412 median_chain_length = 0;
422 median_entry_size = 0;
425 xfree (chain_length);
453 Total memory used by bcache, including overhead: %ld\n"),
472 median_chain_length);
489 return obstack_memory_used (&bcache->
cache);
const void * bcache(const void *addr, int length, struct bcache *cache)
unsigned long hash_continue(const void *addr, int length, unsigned long h)
const void * bcache_full(const void *addr, int length, struct bcache *bcache, int *added)
#define CHAIN_LENGTH_THRESHOLD
unsigned long expand_count
void printf_filtered(const char *format,...)
static void expand_hash_table(struct bcache *bcache)
int(* compare_function)(const void *, const void *, int length)
static int bcache_compare(const void *addr1, const void *addr2, int length)
struct bcache * bcache_xmalloc(unsigned long(*hash_function)(const void *, int length), int(*compare_function)(const void *, const void *, int length))
int bcache_memory_used(struct bcache *bcache)
static void print_percentage(int portion, int total)
int compare_positive_ints(const void *ap, const void *bp)
unsigned long hash(const void *addr, int length)
const char const char int
void print_bcache_statistics(struct bcache *c, char *type)
unsigned long(* hash_function)(const void *addr, int length)
void bcache_xfree(struct bcache *bcache)
unsigned long half_hash_miss_count
unsigned long unique_count
unsigned long expand_hash_count