RCS and SCCS

[Richard Harter]

In article <10406 at ulysses.homer.nj.att.com> ekrell at hector (Eduardo Krell) writes:
>In article <290 at intelisc.UUCP> joel at intelisc.UUCP (Joel Clark) writes:

>>Can anyone explain to me how a program could store `the most recent version`
>>such that each line in the file does not need to be examined to determine
>>if it is in the most recent version?

>You store the most recent version at the beginning of the file in clear
>text followed by the reverse delta to get the previous version
>(followed by the reverse delta to get the version before that, etc.).

>Time to get the latest version is thus proportional only to the size of
>that version. Time to get version N is proportional to the size of
>the last version plus the size of all deltas necessary to get from there
>down to version N.

It is not quite that simple.  The obvious method to use to get a version
N down is to build N successive versions by applying the deltas in turn.
If you do this the cost is N times the average version size.  You can do
much better than this by maintaining linked lists and manipulating line
numbers only.  This reduces the size of the problem since each line is
only processed once; however the arrays of line numbers must be reworked
for each version.  This again is a cost of N times the average version
size, albeit with a much smaller constant.  This cost if (as far as I
know) unavoidable if deltas are framed in terms of line numbers.  The
cost can be reduced to size of last version plus deltas if line identifers
are associated with each line with deltas being recorded in the form of
references to line identifiers rather than line numbers.  However this
increases the time required for an update, since the table of line identifiers
must be updated with each version.  If this is managed correctly the
cost of updating line identifiers is less than the difference calculation
by a large margin.

If anyone has access to the RCS implementation (I do not) I would be
interested in hearing whether it uses raw line numbers in the implementation
or something more sophisticated.
-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.