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

Re: RFC: Revision indexes for 1.1

From: Branko Čibej <brane_at_xbc.nu>
Date: 2004-04-23 02:33:54 CEST

kfogel@collab.net wrote:

>Branko Čibej <brane@xbc.nu> writes:
>>>If revisions have their dates out of order, then -r {date}:{date} will
>>>evaluate to a revision range which does not reflect the date range. So
>>>I think we're better off trying to enforce in-date-order revisions than
>>>we are trying to make our system work with out-of-date-order revisions.
>>No, I'm totally against enforcing the date order, for the reasons I
>>stated. Instead we should just fix the API.
>The "date-search problem" that Greg Hudson was talking about isn't
>merely an issue of API, it's about implementation. The reason to
>enforce ordered dates is so we can use binary search, to narrow down a
>date range to a set of revisions very quickly. Otherwise, resolving
>dates to revisions requires a full scan of the revisions table.
It's an issue of both API and implementation, see below.

>You probably know all this already; it's just still not quite clear to
>me how your proposal solves the problem. Btw, I'm not advocating
>enforced ordering of revision dates, merely stating that it's one way
>to turn an O(N) problem into a O(logN) problem. The addition of a new
>index table might do the same thing, without enforcing ordering. (Was
>there such an index in your proposal, and I just missed it?)
The proposed revision indexes would by default create an injective
mapping between svn:date and revision numbers. The implementation change
is to use that index (when available) instead of the binary search, thus
doing away with the ordering restriction.

The API problem is that svn_repos_dated_revision looks for _one_
revision using _one_ date. So if your revisions aren't ordered by date,
you can't just use this function to find the first and last revision in
a date range and rely on the result. Instead, we need a new function
that accepts a start and end date, and returns a list of revision ranges
that fall within those two dates. The implementation of such a function
is trrivial and involves only a cursor traverse of the revision index,
not touching revision props at all.

-- Brane

To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Fri Apr 23 08:18:59 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.