cvs commit: src/sys/vfs/hammer hammer_btree.c hammer_cursor.h hammer_disk.h hammer_inode.c hammer_object.c hammer_vnops.c

[Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxxxxx>]

dillon      2008/01/15 17:15:37 PST

DragonFly src repository

  Modified files:
    sys/vfs/hammer       hammer_btree.c hammer_cursor.h 
                         hammer_disk.h hammer_inode.c 
                         hammer_object.c hammer_vnops.c 
  Log:
  HAMMER 20A/many: B-Tree lookup API cleanup, B-Tree changes.
  
  * Abstract the as-of TID in the cursor API to hide the implementation
    details.
  
  * 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)
         /    \
        6     16
  
    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


http://www.dragonflybsd.org/cvsweb/src/sys/vfs/hammer/hammer_btree.c.diff?r1=1.18&r2=1.19&f=u
http://www.dragonflybsd.org/cvsweb/src/sys/vfs/hammer/hammer_cursor.h.diff?r1=1.5&r2=1.6&f=u
http://www.dragonflybsd.org/cvsweb/src/sys/vfs/hammer/hammer_disk.h.diff?r1=1.16&r2=1.17&f=u
http://www.dragonflybsd.org/cvsweb/src/sys/vfs/hammer/hammer_inode.c.diff?r1=1.19&r2=1.20&f=u
http://www.dragonflybsd.org/cvsweb/src/sys/vfs/hammer/hammer_object.c.diff?r1=1.18&r2=1.19&f=u
http://www.dragonflybsd.org/cvsweb/src/sys/vfs/hammer/hammer_vnops.c.diff?r1=1.19&r2=1.20&f=u