+/* The type used to hold a single bcache string. The user data is
+ stored in d.data. Since it can be any type, it needs to have the
+ same alignment as the most strict alignment of any type on the host
+ machine. I don't know of any really correct way to do this in
+ stock ANSI C, so just do it the same way obstack.h does. */
+
+struct bstring
+{
+ /* Hash chain. */
+ struct bstring *next;
+ /* Assume the data length is no more than 64k. */
+ unsigned short length;
+ /* The half hash hack. This contains the upper 16 bits of the hash
+ value and is used as a pre-check when comparing two strings and
+ avoids the need to do length or memcmp calls. It proves to be
+ roughly 100% effective. */
+ unsigned short half_hash;
+
+ union
+ {
+ char data[1];
+ double dummy;
+ }
+ d;
+};
+
+
+/* The structure for a bcache itself. The bcache is initialized, in
+ bcache_xmalloc(), by filling it with zeros and then setting the
+ corresponding obstack's malloc() and free() methods. */
+
+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;
+};
+