+struct bcache
+{
+ /* All the bstrings are allocated here. */
+ struct obstack cache;
+
+ /* How many hash buckets we're using. */
+ unsigned int num_buckets;
+
+ /* Hash buckets. This table is allocated using malloc, so when we
+ grow the table we can return the old table to the system. */
+ struct bstring **bucket;
+
+ /* Statistics. */
+ unsigned long unique_count; /* number of unique strings */
+ long total_count; /* total number of strings cached, including dups */
+ long unique_size; /* size of unique strings, in bytes */
+ long total_size; /* total number of bytes cached, including dups */
+ long structure_size; /* total size of bcache, including infrastructure */
+ /* Number of times that the hash table is expanded and hence
+ re-built, and the corresponding number of times that a string is
+ [re]hashed as part of entering it into the expanded table. The
+ total number of hashes can be computed by adding TOTAL_COUNT to
+ expand_hash_count. */
+ unsigned long expand_count;
+ unsigned long expand_hash_count;
+ /* Number of times that the half-hash compare hit (compare the upper
+ 16 bits of hash values) hit, but the corresponding combined
+ length/data compare missed. */
+ unsigned long half_hash_miss_count;
+};
+
+/* The old hash function was stolen from SDBM. This is what DB 3.0 uses now,
+ * and is better than the old one.
+ */
+\f
+unsigned long
+hash(const void *addr, int length)
+{
+ const unsigned char *k, *e;
+ unsigned long h;
+
+ k = (const unsigned char *)addr;
+ e = k+length;
+ for (h=0; k< e;++k)
+ {
+ h *=16777619;
+ h ^= *k;
+ }
+ return (h);