VersionMap.mesa
Copyright Ó 1985, 1986, 1987, 1989, 1991, 1992 by Xerox Corporation. All rights reserved.
Doug Wyatt, December 15, 1986 4:57:11 pm PST
Russ Atkinson (RRA) January 19, 1987 3:35:31 pm PST
JKF October 12, 1988 9:49:25 am PDT
Willie-Sue Orr, July 17, 1989 4:01:58 pm PDT
Willie-s, March 13, 1992 5:37 pm PST
VersionMap:
CEDAR
DEFINITIONS =
BEGIN
VersionStamp: TYPE ~ BasicVersionStamp.VersionStamp;
ROPE: TYPE ~ Rope.ROPE;
Map: TYPE = REF MapRep;
MapList: TYPE = LIST OF Map;
MapRep:
TYPE =
RECORD [
info about the file used to create this version map
fileName: PFS.PATH ¬ NIL,
uid: PFS.UniqueID ¬ PFS.nullUniqueID,
askedForUID: PFS.UniqueID ¬ PFS.nullUniqueID,
assumeImmutable: BOOL ¬ TRUE,
the map itself follows
names:
ROPE ¬
NIL,
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:
CARD16
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 ¬ nullStamp, -- the version stamp for the named file
created: BasicTime.GMT ¬ BasicTime.nullGMT, -- create time of the file
index: INT ¬ 0 -- position of the first char in the long name
];
MyStamp must be an integral number of quad-bytes
MyStamp:
TYPE =
MACHINE
DEPENDENT
RECORD [lo, num, hi, extra:
CARD16];
nullStamp: MyStamp = [0, 0, 0, 0];
This type must be as long as VersionStamp. We use the num field as uniformly distributed bits, so we can search by interpolation. To increase the uniformity of the distribution, 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: CARD16 OF CARD32];
MapAndName: TYPE = RECORD [map: Map, name: ROPE, created: BasicTime.GMT];
MapAndNameList: TYPE = LIST OF MapAndName;
Range:
TYPE =
RECORD [map: Map, first:
CARD16, len:
NAT15];
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: 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 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:
PFS.
PATH];
... saves a map in quickly machine-readable form.
VerboseRestoreMapFromFile:
PROC [
name:
PFS.
PATH, askedForUID:
PFS.UniqueID ¬
PFS.nullUniqueID,
assumeImmutable:
BOOL ¬
TRUE, out:
IO.
STREAM]
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).
RestoreMapFromFile:
PROC [name:
PFS.
PATH, askedForUID:
PFS.UniqueID ¬
PFS.nullUniqueID,
assumeImmutable:
BOOL ¬
TRUE]
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:
CARD16]
RETURNS [stamp: VersionStamp, name:
ROPE, created: BasicTime.
GMT];
... returns the name, stamp, and create date at the given index, where index IN [0..Length[map])
FetchCreated:
PROC [map: Map, index:
CARD16]
RETURNS [created: BasicTime.
GMT];
returns the created time at the given index, where index IN [0..Length[map])
FetchStamp:
PROC [map: Map, index:
CARD16]
RETURNS [stamp: VersionStamp];
returns the stamp at the given index, where index IN [0..Length[map])
FetchName:
PROC [map: Map, index:
CARD16]
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, created: BasicTime.
GMT, 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.
LookupByExtension:
PROC [mapList: MapList, base:
ROPE, extensions:
LIST
OF
ROPE]
RETURNS [
ROPE];
Returns a fullFName corresponding to the short name Rope.Cat[base, ".", ext], where ext is an element of extensions, or NIL if none such exists. Of the possible answers, it finds one with ext as early in the extensions list as possible. The extension ropes are actually used as patterns, with "*" matching any sequence of characters.
MapListForName:
PROC[fileName:
ROPE]
RETURNS[MapList];
Given a file name, returns the MapList to look for it in.
MapAtomForName:
PROC[fileName:
ROPE]
RETURNS[which, other:
ATOM];
Given a file name, returns the ATOM that identifies which mapList for that name - other is additional information, such as $opt for $Executable, or might give machine type.
GetMapAtomList:
PROC
RETURNS[
LIST
OF
ATOM];
Returns the list of the currently known map atoms.
END.