DragonFly commits List (threaded) for 2008-01
cvs commit: src/sys/vfs/hammer hammer_btree.c hammer_cursor.h hammer_disk.h hammer_inode.c hammer_object.c hammer_vnops.c
dillon 2008/01/15 17:15:37 PST
DragonFly src repository
sys/vfs/hammer hammer_btree.c hammer_cursor.h
HAMMER 20A/many: B-Tree lookup API cleanup, B-Tree changes.
* Abstract the as-of TID in the cursor API to hide the implementation
* Key off of delete_tid instead of create_tid.
* Deal with a boundary key issue related to as-of lookups. This issue arises
when several records which differ only by their create_tid/delete_tid
reside in different leaf nodes. For example:
o(10) (delete_tid's listed)
If we want to do an as-of lookup of say, (8), the btree scan will dive
into the left branch and fail to find any elements visible to our as-of
request. The element '16' in the right branch, however, is visible
because it was deleted after the as-of timestamp of 8.
When this case arises btree_search() now detects that the boundary
element (10) exactly matches the request except for the delete_tid
and btree_search() now automatically iterates if an as-of search
is being executed.
For non-asof searches, such as insertion searches, the delete_tid is
treated as an absolute and it is desireable to recurse into the left
branch and stop there. If we popped over to the right branch our
new element (8) would be to the right of our boundary element (10)
instead of to the left.
* Remove code related to dealing with spike ranges in preparation for
a major change in the way spikes operate.
Revision Changes Path
1.19 +137 -81 src/sys/vfs/hammer/hammer_btree.c
1.6 +4 -1 src/sys/vfs/hammer/hammer_cursor.h
1.17 +1 -1 src/sys/vfs/hammer/hammer_disk.h
1.20 +10 -6 src/sys/vfs/hammer/hammer_inode.c
1.19 +45 -39 src/sys/vfs/hammer/hammer_object.c
1.20 +18 -10 src/sys/vfs/hammer/hammer_vnops.c