+/* We use the excellent Jenkins lookup3 hash; this is based on hash_word2.
+ * See: http://burtleburtle.net/bob/c/lookup3.c
+ */
+#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
+static void hash(uint32_t key, uint32_t *pc, uint32_t *pb)
+{
+ uint32_t a,b,c;
+
+ /* Set up the internal state */
+ a = b = c = 0xdeadbeef + *pc;
+ c += *pb;
+ a += key;
+ c ^= b; c -= rot(b,14);
+ a ^= c; a -= rot(c,11);
+ b ^= a; b -= rot(a,25);
+ c ^= b; c -= rot(b,16);
+ a ^= c; a -= rot(c,4);
+ b ^= a; b -= rot(a,14);
+ c ^= b; c -= rot(b,24);
+ *pc=c; *pb=b;
+}
+
+/*
+ We want to check that all free records are in the free list
+ (only once), and all free list entries are free records. Similarly
+ for each hash chain of used records.
+
+ Doing that naively (without walking hash chains, since we want to be
+ linear) means keeping a list of records which have been seen in each
+ hash chain, and another of records pointed to (ie. next pointers
+ from records and the initial hash chain heads). These two lists
+ should be equal. This will take 8 bytes per record, and require
+ sorting at the end.
+
+ So instead, we record each offset in a bitmap such a way that
+ recording it twice will cancel out. Since each offset should appear
+ exactly twice, the bitmap should be zero at the end.
+
+ The approach was inspired by Bloom Filters (see Wikipedia). For
+ each value, we flip K bits in a bitmap of size N. The number of
+ distinct arrangements is:
+
+ N! / (K! * (N-K)!)
+
+ Of course, not all arrangements are actually distinct, but testing
+ shows this formula to be close enough.
+
+ So, if K == 8 and N == 256, the probability of two things flipping the same
+ bits is 1 in 409,663,695,276,000.
+
+ Given that ldb uses a hash size of 10000, using 32 bytes per hash chain
+ (320k) seems reasonable.
+*/
+#define NUM_HASHES 8
+#define BITMAP_BITS 256
+
+static void bit_flip(unsigned char bits[], unsigned int idx)
+{
+ bits[idx / CHAR_BIT] ^= (1 << (idx % CHAR_BIT));
+}
+
+/* We record offsets in a bitmap for the particular chain it should be in. */
+static void record_offset(unsigned char bits[], tdb_off_t off)
+{
+ uint32_t h1 = off, h2 = 0;
+ unsigned int i;
+
+ /* We get two good hash values out of jhash2, so we use both. Then
+ * we keep going to produce further hash values. */
+ for (i = 0; i < NUM_HASHES / 2; i++) {
+ hash(off, &h1, &h2);
+ bit_flip(bits, h1 % BITMAP_BITS);
+ bit_flip(bits, h2 % BITMAP_BITS);
+ h2++;
+ }
+}
+
+/* Check that an in-use record is valid. */
projects / ccan / blobdiff