WPBTreeImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Last Edited by: Swinehart, October 28, 1985 12:05:26 pm PST
DIRECTORY
Atom,
Basics,
BTree,
BTreeSimple,
BTreeVM,
Commander,
CommandTool,
FS,
FSBackdoor,
IO,
LupineRuntime,
PrincOps,
PrincOpsUtils,
ProcessProps,
RefTab,
RefText,
Rope,
ThNet,
UserProfile,
VoiceUtils
;
WPBTreeImpl: PROGRAM
IMPORTS Atom, Basics, BTree, BTreeSimple, BTreeVM, Commander, CommandTool, FS, FSBackdoor, IO, LupineRuntime, RefTab, PrincOpsUtils, ProcessProps, RefText, Rope, ThNet, UserProfile, VoiceUtils
EXPORTS ThNet SHARES Rope
= BEGIN
OPEN IO;
ROPE: TYPE = Rope.ROPE;
Attrs: TYPE = ThNet.Attrs;
WPListing: TYPE = ThNet.WPListing;
Representation primitives
Top-level State
WPState: TYPE = ThNet.WPState;
WPStateRecord: TYPE = ThNet.WPStateRecord;
Key Value:
WPValue: TYPE = LONG POINTER TO RECORD [ linkIndex: INT ];
Data Page Values
EntSize: TYPE = [0..LAST[BTree.PageSize]-BTree.reservedWordsPerPage+1];
lastEnt: EntSize = LAST[EntSize]-1;
Entry: TYPE = LONG POINTER TO WPEntryRecord;
WPEntryRecord: TYPE = RECORD
[
recordSize: EntSize,
recordData: SEQUENCE COMPUTED EntSize OF INTEGER
];
Used in enumeration routines to determine actual matches
CompareRopes: PROC[s1: ROPE, s2: ROPE, substringEqual: BOOL]
RETURNS[res: BTreeSimple.Comparison] = {
ss1: INT=Rope.Size[s1];
r2: ROPEIF substringEqual THEN Rope.Substr[s2, 0, ss1] ELSE s2;
RETURN [Rope.Compare[s1, r2, FALSE]];
};
Tables of mappings between small integers (wpAttrs) or external strings (wpExtInt) and attribute names
wpAttrs: RefTab.Ref;
ThNet Procedures
InitWhitePagesDatabase: PUBLIC SAFE PROC[
fileName: ROPE, extIntMapName: ROPE, accessOptions: FS.AccessOptions ← $read,
howToComplain: VoiceUtils.WhereToReport←$System]
RETURNS[wpState: WPState←NIL] = TRUSTED {
buffer: REF TEXT = RefText.ObtainScratch[100];
s: IO.STREAM;
wpState ← NEW[WPStateRecord];
wpState.accessOptions ← accessOptions;
IF fileName=NIL THEN
fileName ← UserProfile.Token[key: "ThrushWPTreeName", default: "WPTree"];
wpState.treeRootName ← FS.ExpandName[fileName].fullFName;
IF extIntMapName=NIL THEN extIntMapName ←
UserProfile.Token[key:"ThrushWPMappings", default: "IntExt.map"];
IF wpAttrs=NIL THEN {
wpAttrs ← RefTab.Create[];
FOR attr: Attrs IN Attrs DO
IF keysForAttributes[attr] # $unassigned THEN
[]←RefTab.Store[wpAttrs, keysForAttributes[attr], NEW[Attrs𡤊ttr]];
ENDLOOP;
};
s ← FS.StreamOpen[extIntMapName];
wpState.wpExtInt ← RefTab.Create[];
WHILE ~s.EndOf[] DO
ENABLE IO.EndOfStream=>EXIT;
int: ATOM ← Atom.MakeAtomFromRefText[s.GetCedarToken[buffer: buffer].token];
ext: ATOM;
[]←s.GetChar[];
ext ← Atom.MakeAtomFromRefText[s.GetLine[buffer]];
[]←wpState.wpExtInt.Store[ext, int]; -- external version is the key.
ENDLOOP;
s.Close[];
RefText.ReleaseScratch[buffer];
[]←OpenWhitePagesDatabase[wpState, howToComplain];
};
OpenWhitePagesDatabase: SAFE PROC[
wpState: WPState, howToComplain: VoiceUtils.WhereToReport←$System]
RETURNS [ok: BOOLFALSE] = TRUSTED {
ENABLE BTree.Error => {
VoiceUtils.Problem["Trouble opening BTree", howToComplain]; CONTINUE };
treeName: ROPE←wpState.treeRootName.Concat[".Tree"];
dataName: ROPE←wpState.treeRootName.Concat[".TreeData"];
feepTreeName: ROPE←wpState.treeRootName.Concat[".FTree"];
treeFile, dataFile, feepFile: FS.OpenFile;
init: BOOL;
IF wpState=NIL THEN RETURN[FALSE];
IF wpState.wpOpen THEN RETURN;
wpState.wpTree ← BTreeSimple.New[];
wpState.wpFeepTree ← BTreeSimple.New[];
{ ENABLE FS.Error => IF error.group = user THEN {
VoiceUtils.Problem[error.explanation, howToComplain]; treeFile←FS.nullOpenFile; CONTINUE; };
SELECT wpState.accessOptions FROM
$read => {
treeFile←FS.Open[name: treeName];
feepFile←FS.Open[name: feepTreeName];
dataFile ← FS.Open[name: dataName];
};
$create => {
treeFile←FS.Create[name: treeName, keep: 2, setKeep: TRUE, pages: 100];
feepFile←FS.Create[name: feepTreeName, keep: 2, setKeep: TRUE, pages: 100];
dataFile ← FS.Create[name: dataName, keep: 2, setKeep: TRUE, pages: 300];
};
$write => {
treeFile←FS.OpenOrCreate[name: treeName, keep: 2, pages: 100];
feepFile←FS.OpenOrCreate[name: feepTreeName, keep: 2, pages: 100];
dataFile ← FS.OpenOrCreate[name: dataName, keep: 2, pages: 300];
};
ENDCASE => VoiceUtils.Problem["Don't request $append option for BTree", howToComplain];
};
IF treeFile=NIL OR dataFile = NIL OR feepFile=NIL THEN RETURN[FALSE];
wpState.wpFile ← treeFile;
wpState.wpFeepFile ← feepFile;
wpState.wpDataVMFile ← dataFile;
wpState.wpDataVMLen ← FS.GetInfo[dataFile].bytes/2;
wpState.wpDataVM ← BTreeVM.Open[file: FSBackdoor.GetFileHandle[dataFile], filePagesPerPage: 1, cacheSize: 10];
init ← FS.GetInfo[dataFile].bytes=0;
BTreeSimple.Open[tree: wpState.wpTree, file: wpState.wpFile, initialize: init];
BTreeSimple.Open[tree: wpState.wpFeepTree, file: wpState.wpFeepFile, initialize: init];
IF wpState.accessOptions = $create THEN wpState.accessOptions ← $write;
ok ← wpState.wpOpen ← TRUE;
};
CloseWhitePagesDatabase: PUBLIC SAFE PROC[wpState: WPState, howToComplain: VoiceUtils.WhereToReport←$System] RETURNS [ok: BOOLTRUE] = TRUSTED {
IF wpState=NIL OR ~wpState.wpOpen THEN RETURN;
BTreeSimple.SetState[wpState.wpTree, closed!BTree.Error => { ok←FALSE; CONTINUE}];
BTreeSimple.SetState[wpState.wpTree, closed!BTree.Error => { ok←FALSE; CONTINUE}];
wpState.wpDataVM.FlushCache[];
wpState.wpDataVM.FreeBuffers[];
IF wpState.accessOptions # $read THEN
FS.SetByteCountAndCreatedTime[wpState.wpDataVMFile, wpState.wpDataVMLen*2!FS.Error => IF error.group=user THEN { VoiceUtils.Problem[error.explanation, howToComplain]; CONTINUE; }];
wpState.wpFile.Close[!FS.Error => IF error.group>=lock THEN CONTINUE];
wpState.wpFeepFile.Close[!FS.Error => IF error.group>=lock THEN CONTINUE];
wpState.wpDataVMFile.Close[!FS.Error => IF error.group>=lock THEN CONTINUE];
wpState.wpDataVMValid ← TRUE;
wpState.wpOpen ← FALSE;
};
SetProperLength: SAFE PROC[name: ROPE] = CHECKED {
pages: INT;
file: FS.OpenFile ← FS.Open[name, $write];
pages ← FS.GetInfo[file].pages;
FS.SetByteCountAndCreatedTime[file, FS.BytesForPages[pages]];
FS.Close[file];
};
WhitePagesLookup: PUBLIC SAFE PROC[
wpState: WPState, name: ROPE, feep: BOOLFALSE ]
RETURNS [ listing: WPListing←NIL ] = TRUSTED {
name must be in form rr.xxxxxxx
Returns first listing for which name is a substring, case unimportant, of the listing
FindOne: UNSAFE PROC[key: BTreeSimple.EntryKey, value: BTreeSimple.EntryValue]
RETURNS [continue: BOOLEANFALSE] = {
index: EntSize;
entry: Entry;
wpValue: WPValue = LOOPHOLE[@value[0]];
recordKey: ATOM;
recordValue: ROPE;
SELECT CompareRopes[name, BTreeSimple.KeyFromEntry[key], TRUE] FROM
greater => RETURN[TRUE];
equal => NULL;
ENDCASE => RETURN[FALSE];
IF feep AND listing#NIL THEN { listing ← NIL; RETURN; };
IF (entry ← GetLinkedEntry[wpState, wpValue, $read]) = NIL
THEN RETURN[feep];
listing ← RefTab.Create[];
[index, recordKey, recordValue] ← RopeFromWPEntry[entry, 0];
WHILE index#lastEnt DO
[]←listing.Store[recordKey, recordValue];
[index, recordKey, recordValue] ← RopeFromWPEntry[entry, index];
ENDLOOP;
ReleaseLinkedEntry[wpState, wpValue];
RETURN[feep];
};
IF ~wpState.wpOpen AND ~OpenWhitePagesDatabase[wpState] THEN RETURN;
[]𡤋TreeSimple.EnumerateEntries[
tree: IF feep THEN wpState.wpFeepTree ELSE wpState.wpTree,
key: name, relation: less, Proc: FindOne
];
};
WhitePagesEntry: PUBLIC SAFE PROC[
wpState: WPState, name: ROPENIL, key: ATOM←$officeNumber, feep: BOOLFALSE,
listing: WPListing ← NIL]
RETURNS [fullRName: ROPENIL, entry: ROPENIL, newListing: WPListing←NIL] = TRUSTED {
IF listing = NIL THEN listing ← WhitePagesLookup[wpState, name, feep];
IF listing = NIL THEN RETURN;
newListing ← listing;
fullRName ← NARROW[listing.Fetch[$rName].val];
IF key#NIL THEN entry ← NARROW[listing.Fetch[key].val];
};
WhitePagesEnter: PUBLIC SAFE PROC[wpState: WPState, listing: WPListing] = TRUSTED {
IF ~wpState.wpOpen AND ~OpenWhitePagesDatabase[wpState] THEN RETURN;
WhitePagesDo[wpState, listing, enter];
};
WhitePagesPrint: PUBLIC SAFE PROC[wpState: WPState, listing: WPListing] = TRUSTED {
WhitePagesDo[wpState, listing, print];
};
WPFn: TYPE = { print, enter, note };
WhitePagesDo: SAFE PROC[wpState: WPState, listing: WPListing, fn: WPFn] = TRUSTED {
Put in something new, or replace something old.
dataPage: BTree.PagePtr;
dummyData: ARRAY [0..4) OF CARDINAL; -- For collecting length statistics
entry: Entry ← LOOPHOLE[LONG[@dummyData[0]]];
name, feepName: ROPE;
linkIndex: INT← wpState.wpDataVMLen;
linkPage: INT;
inPageIndex: INT;
refType: BTree.ReferenceType ← $write;
doIt: BOOLFALSE;
EPA: RefTab.EachPairAction = TRUSTED {
realKey: ATOMNARROW[key,ATOM];
SELECT fn FROM
enter => RopeToWPEntry[entry, realKey, NARROW[val], doIt];
print => PrintWPEntry[realKey, NARROW[val]];
ENDCASE;
RETURN[FALSE];
};
Start Here
name←NARROW[listing.Fetch[$rName].val];
feepName ← ThNet.FeepName[name];
IF name=NIL THEN ERROR;
SELECT fn FROM
note => { (GetCommanderHandle[]).out.Put[rope[name], rope["\n"]]; RETURN; };
ENDCASE;
entry.recordSize𡤀
[]←RefTab.Pairs[listing, EPA];
entry.recordSize𡤎ntry.recordSize + (1+1); -- one for size field, one for ending 0
IF fn#enter THEN RETURN;
IF ~([linkPage, inPageIndex, ]←GetLinkValues[wpState, linkIndex]).ok THEN RETURN;
IF inPageIndex=0 OR inPageIndex+entry.recordSize>FS.WordsForPages[1] THEN {
New Page needed.
refType ← $new;
IF inPageIndex#0 THEN {
linkPage←SUCC[linkPage];
inPageIndex ← 0;
linkIndex ← FS.WordsForPages[linkPage];
};
};
dataPage ← BTreeVM.ReferencePage[wpState.wpDataVM, linkPage, refType];
entry ← dataPage+inPageIndex;
entry.recordSize ← 0;
doIt ← TRUE;
[]←RefTab.Pairs[listing, EPA];
entry[entry.recordSize] ← 0;
entry.recordSize ← entry.recordSize + (1+1);
wpState.wpDataVMLen ← linkIndex+entry.recordSize;
BTreeVM.ReleasePage[wpState.wpDataVM, linkPage, endOfUpdate];
{
SetVal: PROC[value: BTreeSimple.EntryValue] = {
LOOPHOLE[value, LONG POINTER TO CARDINAL]^ ← 2; -- Compensate BTree bug!
LOOPHOLE[@value[0], LONG POINTER TO INT]^ ← linkIndex;
};
BTreeSimple.UpdateEntry[tree: wpState.wpTree, key: name,
valueLength: 2, Proc: SetVal];
BTreeSimple.UpdateEntry[tree: wpState.wpFeepTree, key: feepName,
valueLength: 2, Proc: SetVal];
};
};
PrintWPEntry: PROC[key: ATOM, val: ROPE] = {
h: Commander.Handle = GetCommanderHandle[];
h.out.PutF["%g: %g\n", atom[key], rope[val]];
IF key=$rName AND h.out#h.err THEN h.err.Put[rope[val], rope["\n"]];
};
GetCommanderHandle: PROC RETURNS[handle: Commander.Handle] = {
p: Atom.PropList = ProcessProps.GetPropList[];
IF p=NIL THEN RETURN[NIL];
RETURN[NARROW[Commander.GetProperty[$CommanderHandle, p]]];
};
GetLinkedEntry: SAFE PROC[wpState: WPState, wpValue: WPValue, access: FS.AccessOptions]
RETURNS[entry: Entry ←NIL] = TRUSTED {
linkIndex: INT ← wpValue.linkIndex;
linkPage: INT;
inPageIndex: INT;
pagePtr: BTree.PagePtr;
IF ([linkPage, inPageIndex,]←GetLinkValues[wpState, linkIndex]).ok=FALSE THEN RETURN;
pagePtr ← BTreeVM.ReferencePage[wpState.wpDataVM, linkPage,
SELECT access FROM $read => $read, $create => $new, ENDCASE => $write];
entry ← pagePtr+inPageIndex;
};
ReleaseLinkedEntry: SAFE PROC[wpState: WPState, wpValue: WPValue] = TRUSTED {
linkPage: INT;
IF ([linkPage,,]←GetLinkValues[wpState, wpValue.linkIndex]).ok=FALSE THEN RETURN;
BTreeVM.ReleasePage[wpState.wpDataVM, linkPage, endOfUpdate];
};
GetLinkValues: SAFE PROC[wpState: WPState, linkIndex: INT]
RETURNS[linkPage, inPageIndex: INT, ok: BOOLFALSE] = TRUSTED {
IF linkIndex<0 OR linkIndex> wpState.wpDataVMLen THEN {
VoiceUtils.Problem["BTree structure error"]; RETURN;
};
ok←TRUE;
linkPage ← FS.PagesForWords[linkIndex+1]-1;
inPageIndex ← linkIndex - FS.WordsForPages[linkPage];
};
RopeFromWPEntry: PROC[entry: Entry, index: EntSize]
RETURNS[newIndex: EntSize←lastEnt, key: ATOM, rope: ROPE] = {
code: INTEGER;
keyRope: ROPE;
IF index=lastEnt THEN RETURN;
code ← entry[index];
SELECT code FROM
0 => RETURN;
<0 => {
key ← keysForAttributes[LOOPHOLE[-code]];
index←index+1;
};
ENDCASE => {
[index, keyRope] ← RFromWPE[entry, index];
key ← Atom.MakeAtom[keyRope];
};
[newIndex, rope] ← RFromWPE[entry, index];
};
RFromWPE: PROC[entry: Entry, index: EntSize]
RETURNS[newIndex: EntSize←lastEnt, rope: ROPE] = {
length: INTEGER;
wfc: LONG CARDINAL;
textRope: Rope.Text;
IF index=lastEnt THEN RETURN;
length ← entry[index];
rope ← textRope ← Rope.NewText[size: length];
wfc ← LupineRuntime.WordsForChars[length];
PrincOpsUtils.LongCopy[
from: @entry[index+1],
to: BASE[DESCRIPTOR[textRope.text]],
nwords: wfc
];
newIndex ← index+wfc+1;
};
RopeToWPEntry: PROC[entry: Entry, key: ATOM, rope: ROPE, doIt: BOOL] = {
index: EntSize ← entry.recordSize;
attr: REF Attrs ← NARROW[wpAttrs.Fetch[key].val];
IF attr#NIL THEN {
IF doIt THEN entry[index]←-LOOPHOLE[attr^, INTEGER];
entry.recordSize ← index+1;
}
ELSE RToWPE[entry, Atom.GetPName[key], doIt];
RToWPE[entry, rope, doIt];
};
RToWPE: PROC[entry: Entry, rope: ROPE, doIt: BOOL] = {
index: EntSize ← entry.recordSize;
wfc: LONG CARDINAL;
len: INTEGER ← rope.Length[];
IF doIt THEN entry[index] ← len;
wfc ← LupineRuntime.WordsForChars[len];
IF doIt THEN PrincOpsUtils.LongCopy[
to: @entry[index+1],
from: BASE[DESCRIPTOR[Rope.Flatten[rope].text]],
nwords: wfc
];
entry.recordSize ← index+wfc+1;
};
Subsidiary procedures
WhitePagesFill: SAFE PROC[cmd: Commander.Handle, accessOptions: FS.AccessOptions←$write] = TRUSTED {
s: IO.STREAM;
lineBuffer: REF TEXT = RefText.ObtainScratch[100];
tokenBuffer: REF TEXT = RefText.ObtainScratch[100];
listing: WPListing←NIL;
wpState: WPState;
numEntries: CARDINAL ← 0;
sourceFile: ROPE ← CommandTool.NextArgument[cmd];
treeRoot, intExt: ROPE;
IF sourceFile=NIL THEN {
VoiceUtils.Problem["Source file not specified", $System]; RETURN; };
s ← FS.StreamOpen[sourceFile];
treeRoot ← CommandTool.NextArgument[cmd];
intExt ← CommandTool.NextArgument[cmd];
wpState ← InitWhitePagesDatabase[ treeRoot, intExt, accessOptions];
IF wpState#NIL THEN WHILE ~s.EndOf[] DO
ENABLE IO.EndOfStream=>EXIT;
line: REF TEXT ← s.GetLine[buffer: lineBuffer];
lineS: IO.STREAM;
extKey, key: ATOM←NIL;
value: ROPE;
keyVal: REF TEXT;
KeyProc: IO.BreakProc = TRUSTED { RETURN[IF char=': THEN sepr ELSE other]; };
IF line.length=0 THEN {
IF listing#NIL THEN {
IF ~wpState.wpOpen AND ~OpenWhitePagesDatabase[wpState] THEN EXIT;
WhitePagesDo[wpState, listing, note];
WhitePagesEnter[wpState, listing];
key ← extKey ← NIL;
numEntries ← SUCC[numEntries];
IF Basics.BITSHIFT[numEntries, 8]=0 THEN []𡤌loseWhitePagesDatabase[wpState];
};
listing ← NIL;
LOOP;
};
IF listing = NIL THEN listing ← NewListing[];
lineS ← IO.TIS[line];
keyVal ← NIL;
keyVal ← lineS.GetToken[KeyProc, tokenBuffer!IO.EndOfStream => CONTINUE].token;
IF lineS.EndOf[] THEN { -- no key, extension of previous value.
IF key#NIL THEN value ← value.Cat["\n", Rope.FromRefText[keyVal]];
}
ELSE {
extKey ← Atom.MakeAtomFromRefText[keyVal];
key ← NARROW[wpState.wpExtInt.Fetch[extKey].val];
IF key=NIL THEN key𡤎xtKey;
[]←lineS.GetChar[!IO.EndOfStream => CONTINUE];
[]←lineS.SkipWhitespace[!IO.EndOfStream => CONTINUE];
value ← lineS.GetLineRope[!IO.EndOfStream => CONTINUE];
};
IF key#NIL THEN List[listing, key, value];
ENDLOOP;
(GetCommanderHandle[]).err.PutRope["-- Updates done.\n"];
s.Close[];
RefText.ReleaseScratch[lineBuffer];
RefText.ReleaseScratch[tokenBuffer];
[]𡤌loseWhitePagesDatabase[wpState];
SetProperLength[wpState.treeRootName.Concat[".Tree"]];
SetProperLength[wpState.treeRootName.Concat[".FTree"]];
};
NewListing: PUBLIC SAFE PROC RETURNS [WPListing] = TRUSTED { RETURN[RefTab.Create[]]; };
List: PUBLIC SAFE PROC[listing: WPListing, key: ATOM, value: ROPE] = TRUSTED {
[]←RefTab.Store[listing, key, value];
};
FillCmdInit: Commander.CommandProc = TRUSTED {
WhitePagesFill[cmd, $create];
};
FillCmd: Commander.CommandProc = TRUSTED {
WhitePagesFill[cmd, $write];
};
keysForAttributes: ARRAY ThNet.Attrs OF ATOM = [
$unassigned, $name, $rName, $officeNumber, $officeDDDNumber, $outsideNumber, $officeAddress, $officeLocation, $organization, $homeAddress, $frequency, $mailSystem, $primaryKey, $unassigned, $unassigned, $unassigned
];
Commander.Register["WPFill", FillCmdInit, "WPFill <textEntriesFile> <treeName <intExtMapName (opt)> (opt)> creates new set of tree files from entries in textEntriesFile"];
Commander.Register["WPRefill", FillCmd, "WPRefill <textEntriesFile> <treeName <intExtMapName (opt)> (opt)> adds to set of tree files from entries in textEntriesFile"];
END.
Swinehart, May 16, 1985 9:16:38 am PDT
Cedar 6.0
changes to: DIRECTORY, WPBTreeImpl, WhitePagesFill
Swinehart, October 28, 1985 12:05:20 pm PST
Log => VoiceUtils
changes to: DIRECTORY, WPBTreeImpl, InitWhitePagesDatabase, OpenWhitePagesDatabase, CloseWhitePagesDatabase, GetLinkValues, WhitePagesFill