VersionMap.mesa
Russ Atkinson, November 14, 1983 11:24 pm
Paul Rovner, June 29, 1983 4:12 pm
Support for version stamp to long file name mapping, and for short name to long name mapping.
DIRECTORY
Rope USING [ROPE],
BcdDefs USING [VersionStamp];
VersionMap: CEDAR DEFINITIONS = BEGIN
ROPE: TYPE = Rope.ROPE;
VersionStamp: TYPE = BcdDefs.VersionStamp;
Map: TYPE = REF MapRep;
MapList: TYPE = LIST OF Map;
MapRep: TYPE = PRIVATE RECORD [
names: ROPENIL,
This can be a very long rope, since it contains ALL of the names. The first name (starting at position 0) is the prefix, which is usually (but not necessarily) factored out from the remainder of the names. Each name terminates in \n.
shortNameSeq: ShortNameSeq ← NIL,
Each index in shortNameSeq is the index of a MapEntry. The indexes in shortNameSeq are sorted to be in increasing short name order (a short name is a long name stripped of directory and version information). The sequence will have the same length as the entries sequence.
entries: SEQUENCE len: CARDINAL OF MapEntry];
Each entry is a version stamp and a position in the names rope where the long name starts. The entries are sorted in order of increasing values of the stamp.num field (followed by sorting on lo and hi).
MapEntry: TYPE = RECORD [
stamp: MyStamp, -- the version stamp for the named file
index: INT   -- position of the first char in the long name
];
MyStamp: TYPE = MACHINE DEPENDENT RECORD [lo,num,hi: CARDINAL];
This type must be as long as BcdDefs.VersionStamp. We use the num field as uniformly distributed bits, so we can search by interpolation. To increase the uniformity of the distributuion, num is chosen to be the low bits of the create time for source files.
ShortNameSeq: TYPE = REF ShortNameSeqRep;
ShortNameSeqRep: TYPE = PRIVATE RECORD [SEQUENCE len: CARDINAL OF CARDINAL];
MapAndName: TYPE = RECORD [map: Map, name: ROPE];
MapAndNameList: TYPE = LIST OF MapAndName;
Range: TYPE = RECORD [map: Map, first: CARDINAL, len: NAT];
When looking up short names, first indicates the first index in shortNameSeq for which the corresponding name is >= the given short name (using the standard Rope.Compare without case). Also, len gives the number of short names that are equal to the short name. However, if len = 0, first may not be a legal index into shortNameSeq if the given shortName is >= to all of the names in the version map.
RangeList: TYPE = LIST OF Range;
When looking up short names in multiple maps, there can be multiple matches, and therefore multiple results must be returned.
VersionToName: PROC
[list: MapList, stamp: BcdDefs.VersionStamp] RETURNS [MapAndName];
... returns a full path name (FS format) for the given version stamp. The list of maps is searched in order. For convenience on a match, the containing map is also returned. If the stamp is not found, [NIL, NIL] is returned.
VersionToAllNames: PROC
[list: MapList, stamp: VersionStamp] RETURNS [MapAndNameList];
... returns all of the full path names (FS format) for the given version stamp. The list of maps is searched in order. For convenience on a match, the containing map is also returned. If the stamp is not found, [NIL, NIL] is returned.
ShortName: PROC
[longName: ROPE] RETURNS [ROPE];
... returns the short name for the given long name. This simply involves stripping off the directory and version information.
ShortNameToNames: PROC
[list: MapList, shortName: ROPE] RETURNS [MapAndNameList];
... returns all of the full path names (FS format) for the given short name. The list of maps is searched in order. For convenience on a match, the containing map is also returned. If the stamp is not found, [NIL, NIL] is returned.
ShortNameToRanges: PROC
[list: MapList, shortName: ROPE] RETURNS [RangeList];
... returns all of the ranges that correspond to the given short name (see the comments for Range).
GetPrefix: PROC [map: Map] RETURNS [ROPE];
... returns the prefix for file names in the map. Uses FS format ("[host]<directory>").
StampToHex: PROC [stamp: VersionStamp] RETURNS [ROPE];
... returns the hex string for the version stamp. Uses standard hex format (0123456789ABCDEF).
SaveMapToFile: PROC [map: Map, name: ROPE];
... saves a map in quickly machine-readable form.
RestoreMapFromFile: PROC
[name: ROPE, assumeImmutable: BOOLTRUE] RETURNS [map: Map];
... restores a map from a file written by SaveMapToFile. If assumeImmutable, then the named file is assumed to not change (this may avoid some copying and storage costs).
FillInShortNames: PROC [map: Map];
... will create a shortNameSeq for version maps that do not have one. This is intended as an aid for external clients that would like to build version maps.
Length: PROC [map: Map] RETURNS [INT];
... returns the # of entries in the map.
Fetch: PROC
[map: Map, index: CARDINAL] RETURNS [stamp: VersionStamp, name: ROPE];
... returns the stamp and name at the given index, where index IN [0..Length[map])
FetchStamp: PROC
[map: Map, index: CARDINAL] RETURNS [stamp: VersionStamp];
returns the stamp at the given index, where index IN [0..Length[map])
FetchName: PROC [map: Map, index: CARDINAL] RETURNS [name: ROPE];
... returns the name at the given index, where index IN [0..Length[map])
RangeToEntry: PROC
[range: Range] RETURNS [name: ROPE, stamp: VersionStamp, next: Range];
... returns the name and stamp for the first entry in the range, also returning the next range. If an empty range is given, the name returned will be NIL, and the range returned will be empty.
END.