tdb2: change to using a hash tree.
authorRusty Russell <rusty@rustcorp.com.au>
Thu, 9 Sep 2010 09:29:18 +0000 (18:59 +0930)
committerRusty Russell <rusty@rustcorp.com.au>
Thu, 9 Sep 2010 09:29:18 +0000 (18:59 +0930)
commit6804501c350181dea8f531142b28c620b70edbd9
tree708db1cb49d4004d9cac3b24429a8adb009a6970
parent32710c917e41b6a283ab73190614623c1a8e9508
tdb2: change to using a hash tree.

As the locking issues with enlarging a hash were so nasty, we switch to a
tree structure for the entries.  It's a hash which expands to point to
sub-hashes when it fills.

This means we no longer have a 'volatile' header: the top hash cannot move.
In fact, we no longer store a copy of the header in the tdb_context; we only
need hash_seed.

New helper functions for accessing writable areas and committing the results
(if they had to be copied).  New debug test to make sure we don't hold access
while we're doing something which could cause us to unmap/remap.

Find becomes more complicated: we need to track where we found (or didn't
find) an entry so we can easily add/delete it.

Traverse becomes more complicated: we need to track where we were in the
hash tree.
32 files changed:
ccan/tdb2/check.c
ccan/tdb2/free.c
ccan/tdb2/hash.c [new file with mode: 0644]
ccan/tdb2/io.c
ccan/tdb2/lock.c
ccan/tdb2/private.h
ccan/tdb2/tdb.c
ccan/tdb2/test/layout.c
ccan/tdb2/test/layout.h
ccan/tdb2/test/run-001-encode.c
ccan/tdb2/test/run-001-fls.c
ccan/tdb2/test/run-01-new_database.c
ccan/tdb2/test/run-02-expand.c
ccan/tdb2/test/run-03-coalesce.c
ccan/tdb2/test/run-04-basichash.c [new file with mode: 0644]
ccan/tdb2/test/run-10-simple-store.c [new file with mode: 0644]
ccan/tdb2/test/run-11-simple-fetch.c [new file with mode: 0644]
ccan/tdb2/test/run-12-store.c [new file with mode: 0644]
ccan/tdb2/test/run-13-delete.c [new file with mode: 0644]
ccan/tdb2/test/run-15-append.c [new file with mode: 0644]
ccan/tdb2/test/run-20-growhash.c [new file with mode: 0644]
ccan/tdb2/test/run-append.c [deleted file]
ccan/tdb2/test/run-delete.c [deleted file]
ccan/tdb2/test/run-enlarge_hash.c [deleted file]
ccan/tdb2/test/run-hashclash.c [deleted file]
ccan/tdb2/test/run-missing-entries.c
ccan/tdb2/test/run-record-expand.c
ccan/tdb2/test/run-simple-delete.c
ccan/tdb2/test/run-simple-fetch.c [deleted file]
ccan/tdb2/test/run-simple-store.c [deleted file]
ccan/tdb2/test/run-traverse.c
ccan/tdb2/traverse.c