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];
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
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];
the full names follow the entries, sans prefix, follow the index
each full name ends in a CR (15C)
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] = {
looks up the version stamp in the list of maps
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] = {
looks up the version stamp in the list of maps
return all of the matches found
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] = {
returns the creating prefix for the map
RETURN [IndexToShortName[map, 0]];
};
StampToHex:
PUBLIC
PROC [stamp: TimeStamp.Stamp]
RETURNS [
ROPE] = {
useful little utility to turn a stamp into hex (Satterthwaite convention)
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 {
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)
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 {
make a rope that reads from the IO
we assume that the file will not change
offset: INT ← IO.GetIndex[st];
map.names ← substrCreator[name, offset, namesChars];
}
ELSE {
copy the chars from the file into storage
after all, the file could change!
map.names ← names ← Rope.FromProc[namesChars, eachChar];
};
IO.Close[st];
lastMap ← map;
};
Length:
PUBLIC
PROC [map: Map]
RETURNS [
INT] = {
returns the # of entries in the map
RETURN [IF map = NIL THEN 0 ELSE map.len];
};
Fetch:
PUBLIC
PROC
[map: Map, index: INT] RETURNS [stamp: TimeStamp.Stamp, name: ROPE] = {
returns the stamp and name at the given index
index must be in [0..Length[map])
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] = {
returns the stamp at the given index
index must be in [0..Length[map])
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] = {
returns the name at the given index
index must be in [0..Length[map])
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] = {
return the name without the prefix or version
names: ROPE ← map.names;
pos: INT ← names.SkipTo[index, "!\n"];
RETURN [names.Substr[index, pos-index]];
};
IndexToMidName:
PROC [map: Map, index: NameMapIndex]
RETURNS [
ROPE] = {
return the name without the prefix
names: ROPE ← map.names;
pos: INT ← names.Index[index, "\n"];
RETURN [names.Substr[index, pos-index]];
};
IndexToFullName:
PROC [map: Map, index: NameMapIndex]
RETURNS [
ROPE] = {
return the full path name
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;
assert: 0 < dt < dh, i < j
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;
try for the quick kill first (most likely)
IF m = mt THEN GO TO found;
otherwise, first search lower in the map
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;
sigh, must search higher in the map
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.