DIRECTORY
Convert USING [Value, ValueToRope],
FileIO USING [Open],
Inline USING [LongDiv, LongMult],
IO USING
[Close, GetChar, GetIndex, PutChar, SetLength, STREAM, UnsafeGetBlock, UnsafePutBlock],
Rope USING
[Concat, Fetch, FromProc, Index, Match, ROPE, Size, SkipTo, Substr],
SafeStorage USING [NewZone],
Time USING [Current],
TimeStamp USING [Stamp],
VersionMap USING
[Map, MapList, MapRep, MapEntry, NameMapIndex, MyStamp, MapAndName, MapAndNameList];

VersionMapImpl: CEDAR MONITOR
IMPORTS Convert, FileIO, Inline, IO, Rope, SafeStorage, Time
EXPORTS VersionMap
SHARES VersionMap
= BEGIN OPEN Rope, VersionMap;

XMyStamp: TYPE = MACHINE DEPENDENT RECORD [lo,num,hi: CARDINAL];
NullStamp: MyStamp _ [0, 0, 0];
MyStampAsHex: TYPE = PACKED ARRAY [0..12) OF [0..16);

XMap: TYPE = REF MapRep;
XMapList: TYPE = LIST OF Map;
XMapRep: PUBLIC TYPE = RECORD
[names: ROPE _ NIL,
prefix: NameMapIndex _ 0,  -- place to find factored prefix
entries: SEQUENCE len: CARDINAL OF MapEntry];
XMapEntry: TYPE = RECORD
[stamp: MyStamp, index: NameMapIndex];
XNameMapIndex: TYPE = INT; -- byte index of name in map
NullNameIndex: NameMapIndex = LAST[NameMapIndex];

EntryIndex: TYPE = CARDINAL;
NullEntryIndex: EntryIndex = LAST[CARDINAL];

EntryRef: TYPE = REF EntryRep;
EntryRep: TYPE = RECORD [next: EntryRef, name: ROPE, version: MyStamp];

pz: ZONE _ SafeStorage.NewZone[prefixed];
qz: ZONE _ SafeStorage.NewZone[quantized];

lastMap: Map _ NIL; -- last map produced (useful for debugging)

-- **** BEGIN EXPORTED PROCEDURES **** --

VersionToName: PUBLIC PROC
[list: MapList, stamp: TimeStamp.Stamp]
RETURNS [result: MapAndName] = {
result _ [NIL, NIL];
FOR each: MapList _ list, each.rest WHILE each # NIL DO
map: Map _ each.first;
nx: EntryIndex _ FindIndex[map, stamp];
IF nx # NullEntryIndex THEN
{result.name _ IndexToFullName[map, map[nx].index];
result.map _ map;
RETURN};
ENDLOOP;
};

VersionToAllNames: PUBLIC PROC
[list: MapList, stamp: TimeStamp.Stamp]
RETURNS [result: MapAndNameList] = {
tail: MapAndNameList _ NIL;
result _ NIL;
FOR each: MapList _ list, each.rest WHILE each # NIL DO
map: Map _ each.first;
lo,hi: EntryIndex;
[lo,hi] _ FindIndexRange[map, stamp];
FOR x: EntryIndex IN [lo..hi] DO
name: ROPE _  IndexToFullName[map, map[x].index];
new: MapAndNameList _ qz.LIST[[map, name]];
IF tail = NIL THEN result _ new ELSE tail.rest _ new;
tail _ new;
ENDLOOP;
ENDLOOP;
};

GetPrefix: PUBLIC PROC [map: Map] RETURNS [ROPE] = {
RETURN [IndexToShortName[map, 0]];
};

StampToHex: PUBLIC PROC [stamp: TimeStamp.Stamp] RETURNS [ROPE] = {
RETURN [MyStampToHex[LOOPHOLE[stamp, MyStamp]]]};

BytesForEntries: PROC [n: INT] RETURNS [INT] = {
words: INT _ SIZE[MapEntry]*n + SIZE[MapRep[0]] - SIZE[ROPE];
RETURN [words+words]};

SaveMapToFile: PUBLIC PROC
[map: Map, name: ROPE] = TRUSTED {
st: IO.STREAM _ FileIO.Open[name, overwrite];
names: ROPE _ map.names;
namesChars: INT _ names.Size[];
len: NAT _ map.len;
bytes: INT _ BytesForEntries[len];
IO.UnsafePutBlock[st, [@len, 0, SIZE[NAT]*2]];  -- first, output the # of bytes
IO.UnsafePutBlock[st, [@map.prefix, 0, bytes]]; -- next, the table
IO.UnsafePutBlock[st, [@namesChars, 0, SIZE[INT]*2]]; -- next, the number of chars
MyPut[st, names];  -- and the names rope
MyPut[st, "\000\000"]; -- marker at end
IO.SetLength[st, IO.GetIndex[st]]; -- force goddamm truncation already!!!
IO.Close[st];
};  

substrCreator: PROC [name: ROPE, start: INT, len: INT] RETURNS [rope: ROPE] _ NIL;
RestoreMapFromFile: PUBLIC PROC
[name: ROPE, assumeImmutable: BOOL _ FALSE] RETURNS [map: Map] = TRUSTED {
st: IO.STREAM _ FileIO.Open[name, read];
namesChars: INT _ 0;
bytes: INT _ 0;
len: NAT _ 0;
names: ROPE _ NIL;
eachChar: PROC RETURNS [c: CHAR] = TRUSTED {
c _ IO.GetChar[st]};
[] _ IO.UnsafeGetBlock[st, [@len, 0, SIZE[NAT]*2]];
map _ pz.NEW[MapRep[len]];
bytes _ BytesForEntries[len];
[] _ IO.UnsafeGetBlock[st, [@map.prefix, 0, bytes]];
[] _ IO.UnsafeGetBlock[st, [@namesChars, 0, SIZE[INT]*2]];
IF assumeImmutable AND substrCreator # NIL
THEN {
offset: INT _ IO.GetIndex[st];
map.names _ substrCreator[name, offset, namesChars];
}
ELSE {
map.names _ names _ Rope.FromProc[namesChars, eachChar];
};
IO.Close[st];
lastMap _ map;
};

Length: PUBLIC PROC [map: Map] RETURNS [INT] = {
RETURN [IF map = NIL THEN 0 ELSE map.len];
};

Fetch: PUBLIC PROC
[map: Map, index: INT] RETURNS [stamp: TimeStamp.Stamp, name: ROPE] = {
stamp _ LOOPHOLE[NullStamp];
name _ NIL;
IF map # NIL AND index IN [0..map.len) THEN {
entry: MapEntry _ map[index];
stamp _ LOOPHOLE[entry.stamp];
name _ IndexToFullName[map, entry.index]};
};

FetchStamp: PUBLIC PROC
[map: Map, index: INT] RETURNS [stamp: TimeStamp.Stamp] = {
stamp _ LOOPHOLE[NullStamp];
IF map # NIL AND index IN [0..map.len) THEN {
entry: MapEntry _ map[index];
stamp _ LOOPHOLE[entry.stamp]};
};

FetchName: PUBLIC PROC [map: Map, index: INT] RETURNS [name: ROPE] = {
name _ NIL;
IF map # NIL AND index IN [0..map.len) THEN {
entry: MapEntry _ map[index];
name _ IndexToFullName[map, entry.index]};
};

-- **** END EXPORTED PROCEDURES **** --

CurrentTime: PROC RETURNS [ROPE] = TRUSTED {
RETURN [Convert.ValueToRope[[time[Time.Current[]]]]];
};

MyStampToHex: PROC [stamp: MyStamp] RETURNS [ROPE] = {
index: NAT _ 0;
each: PROC RETURNS [c: CHAR] = {
x: CARDINAL [0..15] _ hex[index];
IF x IN [0..9] THEN c _ 'a + hex[index];
index _ index + 1;
};
hex: MyStampAsHex _ LOOPHOLE[stamp];
RETURN [Rope.FromProc[12, each]];
};

IndexToShortName: PROC [map: Map, index: NameMapIndex] RETURNS [ROPE] = {
names: ROPE _ map.names;
pos: INT _ names.SkipTo[index, "!\n"];
RETURN [names.Substr[index, pos-index]];
};

IndexToMidName: PROC [map: Map, index: NameMapIndex] RETURNS [ROPE] = {
names: ROPE _ map.names;
pos: INT _ names.Index[index, "\n"];
RETURN [names.Substr[index, pos-index]];
};

IndexToFullName: PROC [map: Map, index: NameMapIndex] RETURNS [ROPE] = {
names: ROPE _ map.names;
pos: INT _ names.Index[index, "\n"];
name: ROPE _ names.Substr[index, pos-index];
IF NOT Rope.Match["[*", name] THEN {
prepos: INT _ names.Index[0, "\n"];
prefix: ROPE _ names.Substr[0, prepos];
name _ prefix.Concat[name]};
RETURN [name];
};

lastProbes: INT _ 0;
totalProbes: INT _ 0;
totalTries: INT _ 0;
totalFinds: INT _ 0;
lastEntry: MapEntry;

GetStats: PROC RETURNS [lastProbes, totalProbes, totalTries, totalFinds: INT] = {
RETURN [lastProbes, totalProbes, totalTries, totalFinds];
};

FindIndex: PUBLIC PROC
[vmap: Map, t: TimeStamp.Stamp]
RETURNS [index: EntryIndex] = {
mt: MyStamp _ LOOPHOLE[t];
mn: CARDINAL _ mt.num;
i,k: CARDINAL _ 0;
j: CARDINAL _ vmap.len-1;
lo,mid: CARDINAL _ vmap[i].stamp.num;
hi: CARDINAL _ vmap[j].stamp.num;
probes: NAT _ 0;
totalTries _ totalTries + 1;
DO
SELECT mn FROM
< lo, > hi => EXIT; -- can never find it!
= lo => k _ i; -- found it at the low point!
= hi => k _ j; -- found it at the high point!
ENDCASE =>
{-- use interpolation for speed!
dh: CARDINAL = hi-lo;
dt: CARDINAL = mn-lo;
TRUSTED
{k _ Inline.LongDiv[Inline.LongMult[j-i, dt], dh] + i};
mid _ vmap[k].stamp.num;
probes _ probes + 1;
SELECT mid FROM
< mn => {lo _ vmap[i _ k + 1].stamp.num; LOOP};
> mn => {hi _ vmap[j _ k - 1].stamp.num; LOOP};
ENDCASE};
{-- at this point, we are in a range of stamps that have equal mid-values; also, vmap[k].stamp.num = mt; a sequential search will do just fine
km: CARDINAL _ k;
m: MyStamp _ vmap[k].stamp;
IF m = mt THEN GO TO found;
WHILE km > i DO
km _ km-1;
m _ vmap[km].stamp;
IF m = mt THEN {k _ km; GO TO found};
IF m.num # mn THEN EXIT;
ENDLOOP;
WHILE k < j DO
k _ k+1;
m _ vmap[k].stamp;
IF m = mt THEN GO TO found;
IF m.num # mn THEN EXIT;
ENDLOOP;
EXIT; -- not found
EXITS
found =>  {
lastProbes _ probes;
totalProbes _ totalProbes + probes;
totalFinds _ totalFinds + 1;
lastEntry _ vmap[k];
RETURN [k]}};
ENDLOOP;
lastProbes _ probes;
totalProbes _ totalProbes + probes;
RETURN [NullEntryIndex];
};

FindIndexRange: PUBLIC PROC
[vmap: Map, t: TimeStamp.Stamp]
RETURNS [lo,hi: EntryIndex] = {
stamp: MyStamp _ LOOPHOLE[t];
lim: EntryIndex _ vmap.len - 1;
hi _ 0;
lo _ FindIndex[vmap, t];
IF lo = NullEntryIndex THEN RETURN;
hi _ lo;
WHILE lo > 0 DO
IF vmap[lo-1].stamp # stamp THEN EXIT;
lo _ lo-1;
ENDLOOP;
WHILE hi < lim DO
IF vmap[hi+1].stamp # stamp THEN EXIT;
hi _ hi + 1;
ENDLOOP;
};

SingleTestFindIndex: PROC [map: Map, i: NAT] RETURNS [index: NameMapIndex] = {
lo,hi: EntryIndex;
entry: MapEntry _ map[i];
[lo,hi] _ FindIndexRange[map, LOOPHOLE[map[i].stamp]];
IF i NOT IN [lo..hi] THEN ERROR TestFindIndexFailed;
};

TestFindIndexFailed: ERROR = CODE;
TestFindIndex: PROC [map: Map] RETURNS [allProbes: INT, len: NAT] = {
allProbes _ 0;
len _ map.len;
FOR i: NAT IN [0..len) DO
[] _ SingleTestFindIndex[map, i];
allProbes _ allProbes + lastProbes;
ENDLOOP;
};

MyPut: PROC [st: IO.STREAM, r: ROPE] = {
FOR i: INT IN [0..r.Size[]) DO
IO.PutChar[st, r.Fetch[i]];
ENDLOOP;
};

END.


VVersionMapImpl.mesa
Russ Atkinson, April 21, 1983 7:09 pm
must be as long as TimeStamp.Stamp
we extract num to use as uniformly distributed bits
num should be the low bits of the time
the full names follow the entries, sans prefix, follow the index
each full name ends in a CR (15C)
looks up the version stamp in the list of maps
looks up the version stamp in the list of maps
return all of the matches found
returns the creating prefix for the map
useful little utility to turn a stamp into hex (Satterthwaite convention)
restores a map from a file written by SaveMapToFile
if assumeImmutable, then the named file is assumed to not change
(this avoids copying the file names from the save file) 
make a rope that reads from the IO
we assume that the file will not change
copy the chars from the file into storage
after all, the file could change!
returns the # of entries in the map 
returns the stamp and name at the given index
index must be in [0..Length[map])
returns the stamp at the given index
index must be in [0..Length[map])
returns the name at the given index
index must be in [0..Length[map])
return the name without the prefix or version
return the name without the prefix
return the full path name
assert: 0 < dt < dh, i < j
try for the quick kill first (most likely)
otherwise, first search lower in the map
sigh, must search higher in the map
�Ê
…˜J˜Jš
œ™Jš
œ%™%J˜š
Ïk	˜	Jšœ�œ˜#Jšœ�œ˜Jšœ�œ˜!š�œ
�˜Jšœ/�œ"˜W—šœ�˜
Jšœ(�œ˜D—Jšœ�œ˜Jšœ�œ˜Jšœ
�œ	˜šœ�˜˜TJ˜———šœ�œ
�˜Jš�œ�œ˜<Jš�œ˜Jš�œ˜Jšœ�œ
�œ˜J˜šœ
�œ�œ
�	œ
�œ
�œ˜@Jš
œ"™"Jš
œ3™3Jš
œ&™&—J˜Jš	œ�œ�œ
�œ	�œ	˜5J˜Jšœ�œ�œ˜Jšœ
�œ�œ
�œ˜šœ	�œ
�œ�˜šœ�œ�œ
˜JšœÏc ˜;Jšœ	�œ�œ
�œ˜-—Jš
œ@™@Jš
œ!™!—šœ�œ�˜J˜&—Jšœ�œ�œž˜7Jšœ�œ˜1J˜Jšœ�œ�œ
˜Jšœ�œ
�œ˜,J˜Jšœ
�œ�œ
˜Jšœ
�œ�œ�œ˜GJ˜Jšœ�œ!˜)Jšœ�œ"˜*J˜Jšœ�œž+˜?J˜Jš
ž)˜)J˜šÏn
œ�œ
�˜J˜'Jš�œ˜ Jš
œ.™.Jšœ
�œ�œ˜š�œ!�œ�œ
�˜7J˜J˜'š�œ�˜˜3J˜Jš�œ˜——Jš�œ
˜—J˜J˜—šŸœ�œ
�˜J˜'Jš�œ˜$Jš
œ.™.Jš
œ™Jšœ�œ
˜Jšœ	�œ
˜
š�œ!�œ�œ
�˜7J˜J˜J˜%š�œ�œ
�˜ Jšœ�œ'˜1Jšœ�œ˜+Jš�œ�œ
�œ�œ˜5J˜Jš�œ
˜—Jš�œ
˜—J˜J˜—š
Ÿ	œ�œ
�œ�œ�œ˜4Jš
œ'™'Jš�œ˜"J˜J˜—š
Ÿ
œ�œ
�œ�œ�œ˜CJš
œI™IJš�œ�œ˜1J˜—š
Ÿœ�œ�œ�œ�œ˜0Jšœ�œ�œ�œ�œ
�œ˜=Jš�œ˜J˜—šŸ
œ�œ
�˜Jšœ�œ�œ˜"Jšœ�œ
�œ ˜-Jšœ�œ
˜Jšœ�œ˜Jšœ�œ˜Jšœ�œ˜"Jš�œ�œ
�œž˜OJš�œ.ž˜BJš�œ%�œ
�œž˜RJšœž˜(Jšœž˜'Jš�œ�œž&˜IJš�œ˜
J˜J˜—Jšœ�œ�œ	�œ�œ�œ�œ�œ
˜RšŸœ�œ
�˜Jšœ�œ�œ�œ�œ�œ˜JJš
œ3™3Jš
œ@™@Jš
œ8™8Jšœ�œ
�œ˜(Jšœ�œ˜Jšœ�œ˜Jšœ�œ˜
Jšœ�œ�œ
˜š	œ
�œ
�œ�œ�œ˜,Jšœ�œ˜—Jšœ�œ�œ
�œ˜3Jšœ	�œ˜J˜Jšœ�œ-˜4Jšœ�œ%�œ
�œ˜:š�œ�œ�˜*š�œ˜Jš
œ"™"Jš
œ'™'Jšœ�œ�œ˜Jš
œ4˜4J˜
—š�œ˜Jš
œ)™)Jš
œ!™!J˜8Jš
œ˜——Jš�œ˜
J˜J˜J˜—š
Ÿœ�œ
�œ�œ�œ˜0Jš
œ$™$Jš
�œ�œ�œ
�œ�œ
˜*J˜J˜—šŸœ�œ
�˜Jšœ�œ�œ �œ˜GJš
œ-™-Jš
œ!™!Jšœ�œ˜Jšœ�œ
˜š
�œ�œ
�œ�œ�œ˜-Jš
œ˜Jšœ�œ˜J˜*—J˜J˜—šŸ
œ�œ
�˜Jšœ�œ�œ˜;Jš
œ$™$Jš
œ!™!Jšœ�œ˜š
�œ�œ
�œ�œ�œ˜-Jš
œ˜Jšœ�œ˜—J˜J˜—šŸ	œ�œ
�œ�œ�œ�œ˜FJš
œ#™#Jš
œ!™!Jšœ�œ
˜š
�œ�œ
�œ�œ�œ˜-Jš
œ˜J˜*—J˜J˜—Jš
ž'˜'J˜š
Ÿœ�œ
�œ�œ�œ˜,Jš�œ/˜5J˜J˜—šŸœ�œ�œ�œ˜6Jšœ�œ˜šœ�œ
�œ�œ˜ Jšœ�œ˜!Jš�œ�œ�œ˜(J˜J˜—Jšœ�œ˜$Jš�œ˜!J˜J˜—šŸœ�œ!�œ�œ˜IJš
œ-™-Jšœ�œ
˜Jšœ�œ˜&Jš�œ"˜(J˜J˜—šŸœ�œ!�œ�œ˜GJš
œ"™"Jšœ�œ
˜Jšœ�œ˜$Jš�œ"˜(J˜J˜—šŸœ�œ!�œ�œ˜HJš
œ™Jšœ�œ
˜Jšœ�œ˜$Jšœ�œ"˜,š�œ
�œ�œ˜$Jšœ�œ˜#Jšœ�œ˜'J˜—Jš�œ˜J˜J˜—Jšœ�œ˜Jšœ
�œ˜Jšœ�œ˜Jšœ�œ˜J˜J˜šŸœ�œ
�œ3�œ˜QJš�œ3˜9J˜J˜—šŸ	œ�œ
�˜J˜Jš�œ˜Jšœ�œ˜Jšœ�œ
˜Jšœ�œ˜Jšœ�œ˜Jšœ�œ˜%Jšœ�œ˜!Jšœ�œ˜J˜š
�˜š�œ�˜Jšœ�œž˜)Jšœž˜,Jšœž˜-š�œ˜
šœ
ž˜ Jšœ�œ	˜Jšœ�œ	˜Jš
œ™š
�˜J˜7—J˜J˜š�œ�˜Jšœ)�œ˜/šœ)�œ˜/Jš�œ˜	—————šœ
ž�
˜Ž
Jšœ�œ˜J˜Jš
œ*™*Jš�œ�œ
�œ
�œ˜Jš
œ(™(š�œ�˜J˜
J˜Jš�œ�œ
�œ
�œ˜%Jš�œ�œ
�œ
˜Jš�œ
˜—Jš
œ#™#š�œ�˜J˜J˜Jš�œ�œ
�œ
�œ˜Jš�œ�œ
�œ
˜Jš�œ
˜—Jš�œž˜—š
�˜˜J˜J˜#J˜J˜Jš�œ˜
——Jš�œ
˜—J˜J˜#Jš�œ˜J˜J˜—šŸœ�œ
�˜J˜Jš�œ˜Jšœ�œ˜J˜J˜J˜Jš�œ�œ
�œ
˜#J˜š�œ�˜Jš�œ�œ
�œ
˜&J˜
Jš�œ
˜—š�œ
�˜Jš�œ�œ
�œ
˜&J˜Jš�œ
˜—J˜J˜—šŸœ�œ�œ�œ˜NJ˜J˜Jšœ�œ˜6Jš
�œ�œ
�œ
�œ
�œ˜4J˜J˜—Jšœ�œ�œ
˜"š
Ÿ
œ�œ�œ
�œ�œ˜EJ˜J˜š�œ�œ
�œ
�˜J˜!J˜#Jš�œ
˜—J˜J˜—š
Ÿœ�œ�œ
�œ�œ˜(š�œ�œ
�œ�˜Jš�œ˜Jš�œ
˜—J˜J˜—Jš�œ
˜J˜J˜——…—"z5U