[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: svn commit: r11847 - in branches/locking/subversion/libsvn_fs_base: bdb notes

From: Branko Čibej <brane_at_xbc.nu>
Date: 2004-11-12 06:34:37 CET

Greg Hudson wrote:

>On Thu, 2004-11-11 at 16:49, sussman@tigris.org wrote:
>>+To test if a path is locked, simply check if the path is a key in the
>>+`locks-nodes' table. To see if a certain directory has any locked
>>+children below, we ask BerkeleyDB to do a "greater or equal match" on
>>+the directory path, and see if any results come back. If they do,
>>+then at least one of the directory's children is locked, and thus the
>>+directory cannot be deleted without further investigation.
>I don't think it's *quite* that simple; you do need to check that the
>match you got back is a child of the directory you're testing.
>(You may have misinterpreted "greater or equal". What brane meant is
>that btree won't give you the closest match; it gives you the closest
>match which is greater than or equal to the key you asked for. That
>might or might not be a child of the directory you're searching for.)
Yup. Any time you do a search like this in a btree, you have to check
the returned key. You may have to move the cursor, depending on what
you're trying to accomplish.

I'll assume we have directory locks, even though we won't in the initial
implementation, because dir locks need to work with this table, too. Now
let's say you have the following keys in the lock-nodes table:

    A/B/ (a dir, note the trailing slash)
    A/B/lambda (a file)
    A/D/G/ (a dir)

1) Delete A/B/kappa
A greater-or-equal search for A/B/kappa will return the key A/B/lambda.
By checking the returned key, you notice that this file isn't locked,
but that's not enough. Because the returned key doesn't match the
search, and you're looking for a file, you move the cursor to the
previous record, which yields A/B/. That's A/B/, which kappa's immediate
parent, so the delete must fail if you don't own the lock on A/B.

2) Rename A/D/G/pi
A >= search for A/D/G/pi will fail (I think); but you can't rely on
that; you have to check the last key in the table, and a prefix-compare
with A/D/G/ shows that the parent is locked.

3) Commit A
This time you have to check if any of A's subordinates is locked. A >=
search on A/ (note the trailing slash!) yields A/B/. You check if the
prefixes match -- strncmp(A/, A/B/) -- and they do. Now you have to move
the cursor forward until you find the first record where this comparison
fails, and you'll have found all the locks you're interested in.

Note: The examples assume the BTree sorts its keys in "normal" ASCII
lexicographical order. But the actual ordering isn't important, as long
as the keys are ordered somehow. Nor does it matter if BDB orders the
keys differently than your str[n]cmp, because you're only interested in
exact (prefix) matches.

>(Hm, also, I think you need to be careful to search for the directory
>with a trailing slash, or you might get a lock entry for
>"<dirname><char>" where <char> is lexically less than '/', in which case
>you wouldn't be sure whether any descendants are locked.)
I said the very same thing (in different words) on #svn-dev. :-)

-- Brane

To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Fri Nov 12 06:34:43 2004

This is an archived mail posted to the Subversion Dev mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.