DIRECTORY
Ascii USING [Lower],
BTree USING [Compare, CompareEntries, DeleteKey, Entry, EntryFromRecord, EntrySize, EnumerateEntries, GetState, Key, New, NewPathStk, NewRecordFromEntry, Open, PageNumber, PagePtr, PageStorage, PathStk, ReadEntry, ReferencePage, Relation, ReleasePage, SalvageEntries, SetState, SetUpdateInProgress, State, statePage, Tree, UpdateEntry, UpdateType, Validate],
BTreeSimple,
BTreeVM USING [CacheSize, FilePagesPerPage],
FS USING [BytesForPages, GetInfo, OpenFile, Read, SetByteCountAndCreatedTime, SetPageCount, WordsForPages, Write],
PrincOpsUtils USING [GetClockPulses, LongCopy],
Process USING [Detach],
Rope USING [InlineFlatten, TextRep],
SafeStorage USING [CantEstablishFinalization, EnableFinalization, EstablishFinalization, FinalizationQueue, FQNext, NewFQ, ReEstablishFinalization],
VM USING [AddressForPageNumber, Allocate, Free, Interval, PagesForWords, PageNumberForAddress];

BTreeSimpleImpl: CEDAR MONITOR -- the monitor protects the BTreeVM cache only
LOCKS h USING h: Handle
IMPORTS Ascii, BTree, FS, PrincOpsUtils, Process, Rope, SafeStorage, VM
EXPORTS BTreeSimple
SHARES Rope
= { OPEN BTreeSimple;
KeyFromEntry: PUBLIC UNSAFE PROC [entryKey: EntryKey] RETURNS [key: InternalKey] = UNCHECKED {
IF entryKey=NIL THEN RETURN[NIL];
key _ NEW[Rope.TextRep[entryKey.length] _ [text[length: entryKey.length, text: ]]];
PrincOpsUtils.LongCopy[to: BASE[DESCRIPTOR[key.text]], from: BASE[DESCRIPTOR[entryKey.text]], nwords: (entryKey.length+1)/2];
};

ValueFromEntry: PUBLIC UNSAFE PROC [entryValue: EntryValue] RETURNS [value: Value] = UNCHECKED {
IF entryValue=NIL THEN RETURN[NIL];
value _ NEW[ValueObject[entryValue.length]];
PrincOpsUtils.LongCopy[to: BASE[DESCRIPTOR[value.words]], from: BASE[DESCRIPTOR[entryValue.words]], nwords: entryValue.length];
};

DefaultCompare: Compare --[key: InternalKey, entryKey: EntryKey] RETURNS [Comparison]-- = UNCHECKED {
FOR i: CARDINAL IN [0 .. MIN[key.length, entryKey.length]) DO
kc: CHAR _ Ascii.Lower[key[i]];
ec: CHAR _ Ascii.Lower[entryKey[i]];
IF kc#ec THEN RETURN[IF kc<ec THEN less ELSE greater];
ENDLOOP;
RETURN[IF key.length=entryKey.length THEN equal
ELSE IF key.length<entryKey.length THEN less ELSE greater];
};

DefaultCompareEntries: CompareEntries --[entryKey1, entryKey2: EntryKey] RETURNS [Comparison]-- = UNCHECKED {
FOR i: CARDINAL IN [0 .. MIN[entryKey1.length, entryKey2.length]) DO
c1: CHAR _ Ascii.Lower[entryKey1[i]];
c2: CHAR _ Ascii.Lower[entryKey2[i]];
IF c1#c2 THEN RETURN[IF c1<c2 THEN less ELSE greater];
ENDLOOP;
RETURN[IF entryKey1.length=entryKey2.length THEN equal
ELSE IF entryKey1.length<entryKey2.length THEN less ELSE greater];
};

defaultCompareProcs: PUBLIC CompareProcs _ [compare: DefaultCompare, compareEntries: DefaultCompareEntries];
New: PUBLIC PROC [compareProcs: CompareProcs _ defaultCompareProcs, initialState: State[closed..suspended] _ closed] RETURNS [tree: Tree] = {
RETURN[BTree.New[repPrim: [compare: LOOPHOLE[compareProcs.compare], compareEntries: LOOPHOLE[compareProcs.compareEntries], entrySize: EntrySize, entryFromRecord: EntryFromRecord, newRecordFromEntry: NewRecordFromEntry], storPrim: [referencePage: ReferencePage, releasePage: ReleasePage], minEntrySize: EntryKeyObject[1].SIZE+ValueObject[0].SIZE, initialState: initialState]];
};

Open: PUBLIC PROC [tree: Tree, file: FS.OpenFile, filePagesPerPage: FilePagesPerPage _ 1, cacheSize: CacheSize _ 25, initialize: BOOLEAN _ FALSE, maintainRecomputableState: BOOLEAN _ TRUE] = {
storage: Handle = CacheOpen[file: file, filePagesPerPage: filePagesPerPage, cacheSize: cacheSize];
tree.Open[storage: storage, pageSize: FS.WordsForPages[filePagesPerPage], initialize: initialize, maintainRecomputableState: maintainRecomputableState];
};

SetState: PUBLIC PROC [tree: Tree, state: State[closed..suspended]] = {
tree.SetState[state];
};

GetState: PUBLIC PROC [tree: Tree] RETURNS [state: State, entryCount: LONG CARDINAL, greatestPage: INT, depth: CARDINAL, file: FS.OpenFile] = {
storage: BTree.PageStorage;
[state: state, entryCount: entryCount, greatestPage: greatestPage, depth: depth, storage: storage] _ tree.GetState[];
file _ NARROW[storage, Handle].file;
};

GetStatistics: PUBLIC PROC [tree: Tree] RETURNS [hits, misses, reads, writes, cumChainLength, cumReadWriteTime: LONG CARDINAL] = {
RETURN GetCacheStats[NARROW[tree.GetState[].storage]];
};

Validate: PUBLIC PROC [tree: Tree] = {
tree.Validate[];
};

SetUpdateInProgress: PUBLIC PROC [tree: Tree, updateInProgress: BOOLEAN] = {
tree.SetUpdateInProgress[updateInProgress];
};
ReadRecord: PUBLIC PROC [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [actualKey: InternalKey, value: Value] = TRUSTED {
EntryProc: UNSAFE PROC [key: EntryKey, value: EntryValue] = UNCHECKED {
IF key=NIL THEN {actualKey _ NIL; returnValue _ NIL}
ELSE {actualKey _ KeyFromEntry[key]; returnValue _ ValueFromEntry[value]};
};
returnValue: Value;
ReadEntry[tree: tree, key: key, relation: relation, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc];
RETURN [actualKey, returnValue];
};

ReadValue: PUBLIC PROC [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [value: Value] = TRUSTED {
EntryProc: UNSAFE PROC [key: EntryKey, value: EntryValue] = UNCHECKED {
returnValue _ (IF value=NIL THEN NIL ELSE ValueFromEntry[value]);
};
returnValue: Value;
ReadEntry[tree: tree, key: key, relation: relation, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc];
RETURN [returnValue];
};

EnumerateRecords: PUBLIC PROC [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: PROC [key: InternalKey, value: Value] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN] = TRUSTED {
EntryProc: UNSAFE PROC [key: EntryKey, value: EntryValue] RETURNS [continue: BOOLEAN] = UNCHECKED {
RETURN [Proc[key: KeyFromEntry[key], value: ValueFromEntry[value]]] };
exhausted _ EnumerateEntries[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc];
};

UpdateRecord: PUBLIC PROC [tree: Tree, key: Key, value: Value, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, updateType: UpdateType _ insertOrReplace] = TRUSTED {
ProduceEntry: UNSAFE PROC [value: EntryValue] = UNCHECKED {
PrincOpsUtils.LongCopy[to: value, from: suppliedValue, nwords: ValueObject[suppliedValue.length].SIZE]};
suppliedValue: LONG POINTER TO ValueObject = LOOPHOLE[value];
UpdateEntry[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, valueLength: suppliedValue.length, Proc: ProduceEntry, updateType: updateType];
};

DeleteKey: PUBLIC PROC [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [found: BOOLEAN] = {
RETURN[tree.DeleteKey[key: key.InlineFlatten[], pathStk: pathStk, useExistingPath: useExistingPath]];
};
ReadEntry: PUBLIC UNSAFE PROC [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: UNSAFE PROC [key: EntryKey, value: EntryValue]] = UNCHECKED {
EntryProc: UNSAFE PROC [entry: BTree.Entry] = UNCHECKED {
IF entry=NIL THEN Proc[NIL, NIL]
ELSE Proc[entry, entry+EntryKeyObject[LOOPHOLE[entry, EntryKey].length].SIZE];
};
tree.ReadEntry[key: key.InlineFlatten[], relation: relation, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc];
};

EnumerateEntries: PUBLIC UNSAFE PROC [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: UNSAFE PROC [key: EntryKey, value: EntryValue] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN] = UNCHECKED {
EntryProc: UNSAFE PROC [entry: BTree.Entry] RETURNS [continue: BOOLEAN] = UNCHECKED {
RETURN[Proc[entry, entry+EntryKeyObject[LOOPHOLE[entry, EntryKey].length].SIZE]]};
exhausted _ tree.EnumerateEntries[key: key.InlineFlatten[], relation: relation, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc];
};

UpdateEntry: PUBLIC UNSAFE PROC [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, valueLength: CARDINAL, Proc: UNSAFE PROC [value: EntryValue], updateType: UpdateType _ insertOrReplace] = UNCHECKED {
EntryProc: UNSAFE PROC [entry: BTree.Entry] = UNCHECKED {
entryKey: EntryKey = LOOPHOLE[entry];
entryValue: EntryValue = LOOPHOLE[entry+entryKeySize];
LOOPHOLE[entryKey, LONG POINTER TO CARDINAL]^ _ internalKey.length; -- entryKey.length _ internalKey.length
PrincOpsUtils.LongCopy[to: BASE[DESCRIPTOR[entryKey.text]], from: BASE[DESCRIPTOR[internalKey.text]], nwords: (internalKey.length+1)/2];
Proc[entryValue];
LOOPHOLE[entryValue, LONG POINTER TO CARDINAL]^ _ valueLength; -- entryValue.length _ valueLength
};
internalKey: InternalKey = key.InlineFlatten[];
entryKeySize: CARDINAL = EntryKeyObject[internalKey.length].SIZE;
tree.UpdateEntry[key: internalKey, pathStk: pathStk, useExistingPath: useExistingPath, words: entryKeySize+ValueObject[valueLength].SIZE, Proc: EntryProc, updateType: updateType];
};

SalvageEntries: PUBLIC UNSAFE PROC [tree: Tree, Proc: UNSAFE PROC [key: EntryKey, value: EntryValue] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN] = UNCHECKED {
EntryProc: UNSAFE PROC [entry: BTree.Entry] RETURNS [continue: BOOLEAN] = UNCHECKED {
RETURN[Proc[entry, entry+EntryKeyObject[LOOPHOLE[entry, EntryKey].length].SIZE]]};
exhausted _ tree.SalvageEntries[Proc: EntryProc];
};
NewPathStk: PUBLIC PROC RETURNS [pathStk: PathStk] = {
RETURN[BTree.NewPathStk[]];
};
EntrySize: BTree.EntrySize --[entry: BTree.Entry] RETURNS [words: BTree.EntSize]-- = UNCHECKED {
words _ EntryKeyObject[LOOPHOLE[entry, EntryKey].length].SIZE;
words _ words + ValueObject[LOOPHOLE[entry+words, EntryValue].length].SIZE;
};

EntryFromRecord: BTree.EntryFromRecord --[record: BTree.Record] RETURNS [entry: BTree.Entry]-- = UNCHECKED {
ERROR Bug[cantGetHere]; -- we never call the BTree procedures that traffic in Records
};

NewRecordFromEntry: BTree.NewRecordFromEntry --[entry: BTree.Entry] RETURNS [record: BTree.Record]-- = UNCHECKED {
ERROR Bug[cantGetHere]; -- we never call the BTree procedures that traffic in Records
};
CacheIndex: TYPE = [0 .. LAST[BTreeVM.CacheSize]];
noIndex: CacheIndex = LAST[CacheIndex];
Handle: TYPE = REF VMObject;
VMObject: TYPE = MONITORED RECORD [
file: FS.OpenFile,
filePages: INT,
filePagesPerPage: BTreeVM.FilePagesPerPage,
vmPagesPerPage: CARDINAL,
rover: CacheIndex,
cache: REF Cache,
hits, misses, reads, writes, cumChainLength, cumReadWriteTime: LONG CARDINAL _ 0,
hashTable: PACKED SEQUENCE count: CARDINAL OF CacheIndex
]; 
Cache: TYPE = RECORD [PACKED SEQUENCE count: CacheIndex OF CacheEntry];
CacheEntry: TYPE = RECORD [
pNum: BTree.PageNumber,
ptr: BTree.PagePtr,
referenceCount: [0..256),
hash: CacheIndex,
empty, recentlyUsed, dirty: BOOLEAN
]; 
CacheOpen: PROC [file: FS.OpenFile, filePagesPerPage: BTreeVM.FilePagesPerPage,
cacheSize: BTreeVM.CacheSize] RETURNS [Handle] = {
h: Handle _ NEW[VMObject[2*cacheSize+1]];
h.file _ file;
h.filePages _ 0; -- indicates that we don't know --
h.filePagesPerPage _ filePagesPerPage;
h.vmPagesPerPage _ VM.PagesForWords[FS.WordsForPages[filePagesPerPage]];
h.rover _ 0;
h.cache _ NEW[Cache[cacheSize]];
FOR i: CacheIndex IN [0 .. h.cache.count) DO
h.cache[i].ptr _ NIL;
h.cache[i].empty _ TRUE;
ENDLOOP;
FOR c: CARDINAL IN [0..h.count) DO
h.hashTable[c] _ noIndex;
ENDLOOP;
SafeStorage.EnableFinalization[h];
RETURN [h];
};

ReferencePage: BTree.ReferencePage --[storage: PageStorage, number: PageNumber, type: ReferenceType] RETURNS [ptr: PagePtr]-- = {
InnerReference: ENTRY PROC [h: Handle] = INLINE {
hash: CARDINAL = HashIndex[h, number];
i: CacheIndex;
FOR i _ h.hashTable[hash], h.cache[i].hash UNTIL i = noIndex DO
h.cumChainLength _ h.cumChainLength+1;
IF h.cache[i].pNum = number THEN { h.hits _ h.hits+1; EXIT };
REPEAT FINISHED => { -- not found --
h.misses _ h.misses+1;
i _ GetEmptyCacheEntry[h];
h.cache[i].pNum _ number;
h.cache[i].empty _ FALSE;
IF type # new THEN LoadCachePage[h, i];
h.cache[i].hash _ h.hashTable[hash];
h.hashTable[hash] _ i;
};
ENDLOOP;
h.cache[i].recentlyUsed _ TRUE;
h.cache[i].referenceCount _ h.cache[i].referenceCount + 1;
IF type # read THEN h.cache[i].dirty _ TRUE;
IF type = new THEN ExtendFile[h, number];
ptr _ h.cache[i].ptr;
};
InnerReference[NARROW[storage]];
};

ReleasePage: BTree.ReleasePage --[storage: PageStorage, number: PageNumber, update: UpdateState]-- = {
InnerRelease: ENTRY PROC [h: Handle] = INLINE {
i: CacheIndex;
FOR i _ h.hashTable[HashIndex[h, number]], h.cache[i].hash UNTIL i = noIndex DO
IF h.cache[i].pNum = number THEN EXIT;
REPEAT FINISHED => ERROR Bug[pageNotInUse];
ENDLOOP;
IF h.cache[i].referenceCount = 0
THEN ERROR Bug[pageNotInUse]
ELSE h.cache[i].referenceCount _ h.cache[i].referenceCount - 1;
IF update # unchanged THEN {
IF number = BTree.statePage
THEN { -- is the statePage; can be either startOfUpdate or endOfUpdate
IF update = startOfUpdate
THEN StoreCachePage[h, i] -- only this page is dirty, so just write it
ELSE WriteDirtyPagesWithStatePageLast[h]; -- many pages possibly dirty
}
ELSE StoreCachePage[h, i]; -- is not the statePage; must be endOfUpdate; only page i is dirty
};
};
InnerRelease[NARROW[storage]];
};

GetCacheStats: ENTRY PROC [h: Handle] RETURNS [hits, misses, reads, writes, cumChainLength, cumReadWriteTime: LONG CARDINAL] = {
RETURN [hits: h.hits, misses: h.misses, reads: h.reads, writes: h.writes, cumChainLength: h.cumChainLength, cumReadWriteTime: h.cumReadWriteTime];
};

FreeBuffers: ENTRY PROC [h: Handle] = {
FOR i: CacheIndex IN [0 .. h.cache.count) DO
IF h.cache[i].ptr#NIL THEN {ReleaseSpace[h, h.cache[i].ptr]; h.cache[i].ptr _ NIL};
h.cache[i].empty _ TRUE;
ENDLOOP;
FOR c: CARDINAL IN [0..h.count) DO
h.hashTable[c] _ noIndex;
ENDLOOP;
};

HashIndex: INTERNAL PROC [h: Handle, pNum: BTree.PageNumber] 
RETURNS [CARDINAL] = INLINE {
RETURN [pNum MOD h.count];
};

WriteDirtyPagesWithStatePageLast: INTERNAL PROC [h: Handle] = {
statePageIndex: CacheIndex _ noIndex;
FOR i: CacheIndex IN [0 .. h.cache.count) DO
IF NOT h.cache[i].empty AND h.cache[i].dirty
THEN {
IF h.cache[i].pNum = BTree.statePage
THEN statePageIndex _ i
ELSE StoreCachePage[h, i];
};
ENDLOOP;
IF statePageIndex # noIndex THEN StoreCachePage[h, statePageIndex];
};

GetEmptyCacheEntry: INTERNAL PROC [h: Handle] RETURNS [i: CacheIndex] = {
FOR cntr: CARDINAL IN [0..2*h.cache.count) DO
i _ (h.rover + cntr) MOD h.cache.count;
SELECT TRUE FROM
h.cache[i].empty => {
IF h.cache[i].ptr = NIL
THEN h.cache[i].ptr _ GetSpace[h];
h.cache[i].recentlyUsed _ FALSE;
h.cache[i].dirty _ FALSE;
h.cache[i].referenceCount _ 0;
EXIT;
};
h.cache[i].referenceCount = 0 => {
IF h.cache[i].recentlyUsed
THEN h.cache[i].recentlyUsed _ FALSE
ELSE {  -- not even recently used
IF h.cache[i].dirty THEN
IF h.cache[i].pNum = BTree.statePage
THEN LOOP -- never force out the statePage
ELSE StoreCachePage[h, i];
EXIT;
};
};
ENDCASE;
REPEAT FINISHED => ERROR Bug[noAvailableCacheEntries];
ENDLOOP;
IF NOT h.cache[i].empty THEN {
hx: CARDINAL = HashIndex[h, h.cache[i].pNum];
IF h.hashTable[hx] = i
THEN h.hashTable[hx] _ h.cache[i].hash
ELSE FOR j: CacheIndex _ h.hashTable[hx], h.cache[j].hash UNTIL j = noIndex DO
IF h.cache[j].hash = i THEN {h.cache[j].hash _ h.cache[i].hash; EXIT};
REPEAT FINISHED => ERROR Bug[cacheEntryNotInHashTable];
ENDLOOP;
h.cache[i].empty _ TRUE;
};
h.rover _ (i+1) MOD h.cache.count;
};

ExtendFile: INTERNAL PROC [h: Handle, n: BTree.PageNumber] = {
fileSizeForNPlus1: INT = (n+1)*h.filePagesPerPage;
IF h.filePages = 0 THEN h.filePages _ h.file.GetInfo[].pages;
IF h.filePages < fileSizeForNPlus1
THEN {
h.filePages _ fileSizeForNPlus1 + 8*h.filePagesPerPage;
h.file.SetPageCount[h.filePages];
h.file.SetByteCountAndCreatedTime[bytes: FS.BytesForPages[h.filePages]];
};
};

LoadCachePage: INTERNAL PROC [h: Handle, i: CacheIndex] = {
then: LONG CARDINAL = PrincOpsUtils.GetClockPulses[];
TRUSTED {h.file.Read[from: h.cache[i].pNum*h.filePagesPerPage, nPages: h.filePagesPerPage, to: h.cache[i].ptr]};
h.cumReadWriteTime _ h.cumReadWriteTime + (PrincOpsUtils.GetClockPulses[]-then);
h.reads _ h.reads+1;
};

StoreCachePage: INTERNAL PROC [h: Handle, i: CacheIndex] =  {
then: LONG CARDINAL = PrincOpsUtils.GetClockPulses[];
TRUSTED {h.file.Write[to: h.cache[i].pNum*h.filePagesPerPage, nPages: h.filePagesPerPage, from: h.cache[i].ptr]};
h.cumReadWriteTime _ h.cumReadWriteTime + (PrincOpsUtils.GetClockPulses[]-then);
h.writes _ h.writes+1;
h.cache[i].dirty _ FALSE;
};

GetSpace: INTERNAL PROC [h: Handle] RETURNS [BTree.PagePtr] = TRUSTED {
interval: VM.Interval = VM.Allocate[count: h.vmPagesPerPage];
RETURN [VM.AddressForPageNumber[interval.page]];
};

ReleaseSpace: INTERNAL PROC [h: Handle, ptr: BTree.PagePtr] = TRUSTED {
VM.Free[[page: VM.PageNumberForAddress[ptr], count: h.vmPagesPerPage]];
};
Bug: ERROR [type: BugType] = CODE;
BugType: TYPE = {cacheEntryNotInHashTable, cantGetHere, noAvailableCacheEntries, pageNotInUse};
Initialize: PROC = {
finalizationQueue _ SafeStorage.NewFQ[];
SafeStorage.EstablishFinalization[type: VMObject.CODE, npr: 0, fq: finalizationQueue
! SafeStorage.CantEstablishFinalization =>
SafeStorage.ReEstablishFinalization[type: VMObject.CODE, npr: 0, fq: finalizationQueue]];
TRUSTED {Process.Detach[FORK FinalizationProcess]};
};

FinalizationProcess: PROC = {
DO
h: Handle _ NARROW [SafeStorage.FQNext[finalizationQueue]];
FreeBuffers[h];
h _ NIL;
ENDLOOP;
};

finalizationQueue: SafeStorage.FinalizationQueue;
Initialize[];
}.
¼BTreeSimpleImpl.mesa
Copyright c 1985 by Xerox Corporation.  All rights reserved.
Taft, January 21, 1984 5:00:25 pm PST
Russ Atkinson (RRA) March 11, 1985 9:48:59 pm PST

BTree representation
BTree global operations
Higher-level BTree access
Lower-level BTree access
PathStk hints
Private
The following are the procedures passed to the BTree package as the RepresentationPrimitives (in addition to the client's Compare and CompareEntries procedures).
Storage primitives and BTree cache
This is almost identical to BTreeVMImpl, and perhaps someday most of the code should be shared (in particular, everything to do with VM cache management as opposed to file I/O). The main difference is that the BTree is designated by an FS.OpenFile rather than a File.Handle.
FlushCache: ENTRY PROC [h: Handle] = {
WriteDirtyPagesWithStatePageLast[h];
FOR i: CacheIndex IN [0 .. h.cache.count) DO
h.cache[i].empty _ TRUE;
ENDLOOP;
FOR c: CARDINAL IN [0..h.count) DO
h.hashTable[c] _ noIndex;
ENDLOOP;
};

The cache entry that is returned is empty; it has a valid space and a useCount of zero.  It may be assocaited with a page by setting pNum.
empty entry
not currently being used
Errors
Initialization and finalization
�ÊÝ–

"Cedar" style˜
head™Icodešœ
Ïm
œ1™<L™%L™1L™š
Ïk	˜	Lšœžœ	˜LšœžœÛ˜æL˜Lšœžœ˜,Lšœžœj˜rLšœžœ˜/Lšœžœ
˜Lšœžœ˜$Lšœžœƒ
˜”
LšœžœW˜_L˜——šÏbœž
œ
Ïc.˜MLšžœžœ
˜Lšžœ@˜GLšžœ˜Lšžœ˜Lšœžœ
˜—š
œ™šÏnœžœ
žœ
žœžœž	œ˜^Lš
žœ
žœ
žœ
žœ
žœ˜!LšœžœJ˜SLš	œžœ
ž
œžœ
ž
œ1˜}Lš
œ˜L˜—š¡œžœ
žœ
žœžœž	œ˜`Lš
žœžœ
žœ
žœ
žœ˜#Lšœžœ!˜,Lš	œžœ
ž
œžœ
ž
œ0˜Lš
œ˜L˜—š¡œ
 )Ðck œž	œ˜eš	žœžœ
žœžœž˜=Lšœžœ˜Lšœžœ˜$Lšžœžœ
žœ
žœžœžœ
˜6Lšžœ
˜—Lšžœ
žœžœ˜/Lšžœ
žœžœžœ
˜;Lš
œ˜L˜—š¡œ #¢ œž	œ˜mš	žœžœ
žœžœ&ž˜DLšœžœ˜%Lšœžœ˜%Lšžœžœ
žœ
žœžœžœ
˜6Lšžœ
˜—Lšžœ
žœ#žœ˜6Lšžœ
žœ#žœžœ
˜BLš
œ˜L˜—LšœžœQ˜l—š
œ™š¡œžœežœ˜�
Lš
žœžœ(žœä
žœžœ˜÷Lš
œ˜L˜—š¡œžœpžœžœžœžœ˜À
Lš
œb˜bLš
œ˜
˜˜
Lš
œ˜L˜—š¡œžœ2˜GL˜Lš
œ˜L˜—š¡œžœžœžœ
žœžœ	žœ˜�
L˜Lš
œu˜uLšœžœ˜$Lš
œ˜L˜—š
¡
œžœžœAžœ
žœ˜‚
Lšžœžœ˜6Lš
œ˜L˜—š¡œžœ˜&L˜Lš
œ˜L˜—š¡œžœ žœ˜LLš
œ+˜+Lš
œ˜——š
œ™š¡
œžœ
žœGžœžœžœžœ*žœ˜¿
š¡	œžœ
žœ&ž	œ˜GLš
žœžœ
žœžœžœ
˜4LšžœF˜JLš
œ˜—L˜Lš
œy˜yLšžœ˜ Lš
œ˜L˜—š¡	œžœGžœžœžœžœžœ˜¦
š¡	œžœ
žœ&ž	œ˜GLšœžœžœ
žœ
žœ
žœ˜ALš
œ˜—L˜Lš
œy˜yLšžœ˜Lš
œ˜L˜—š¡œžœGžœžœžœžœ"žœžœžœ
žœžœ˜ü
š¡	œžœ
žœ$žœžœž	œ˜cLšžœ@˜F—Lš
œx˜xLš
œ˜L˜—š¡œžœ9žœžœžœ.žœ˜®
š¡œžœ
žœž	œ˜;Lšœažœ˜h—Lš	œžœ
žœ
žœžœ˜=Lš
ϴ
˜¥
Lš
œ˜L˜—š¡	œžœ+žœžœžœžœ	žœ˜„
Lšžœ_˜eLš
œ˜——š
œ™š¡	œžœ
žœ
žœGžœžœžœžœ
žœ'ž	œ˜Î
š¡	œžœ
žœž	œ˜9Lš
žœžœ
žœžœžœ
˜ Lšžœ"žœžœ˜NLš
œ˜—Lš
œ‚
˜‚
Lš
œ˜L˜—š¡œž
œ
žœGžœžœžœžœ
žœ$žœžœžœ
žœž	œ˜Žš¡	œžœ
žœžœžœž	œ˜ULšžœ"žœžœ˜R—Lš
ϥ
˜•
Lš
œ˜L˜—š¡œž
œ
žœ+žœžœžœžœžœ
žœBž	œ˜æ
š¡	œžœ
žœž	œ˜9Lšœžœ˜%Lšœžœ˜6Lšžœžœ
žœ
žœ
žœ '˜kLš	œžœ
ž
œžœ
ž
œ7˜ˆ
L˜Lšžœ
žœ
žœ
žœ
žœ "˜aLš
œ˜—L˜/Lšœžœ&žœ
˜ALšœ„
žœ+˜³
Lš
œ˜L˜—š¡œž
œ
žœžœ
žœ$žœžœžœ
žœž	œ˜¬
š¡	œžœ
žœžœžœž	œ˜ULšžœ"žœžœ˜R—Lš
œ1˜1Lš
œ˜——š
œ
™
š¡
œžœ
žœ˜6Lšžœ˜Lš
œ˜——™L™¡
š¡	œ ¢ œž	œ˜`Lšœžœžœ
˜>Lšœžœ"žœ
˜KLš
œ˜L˜—š¡œ ¢ œž	œ˜lLšžœ =˜ULš
œ˜L˜—š¡œ ¢ œž	œ˜rLšžœ =˜ULš
œ˜——™"L™’Lšœžœ	žœ˜2Lšœžœ
˜'Lšœžœžœ
˜šœ
žœž	œ
žœ˜#Lš
œ˜Lšœžœ
˜Lš
œ+˜+Lšœžœ
˜Lš
œ˜Lšœžœ˜Lšœ?žœ
žœ˜QLš	œžœ
žœžœ
žœ˜8Lš
œ˜—Lšœžœžœžœ
žœžœ
˜Gšœžœžœ˜Lš
œ˜Lš
œ˜Lš
œ˜Lš
œ˜Lšœž˜#Lš
œ˜—š¡	œžœ_žœ
˜‚
Lšœžœ˜)Lš
œ˜Lšœ "˜3Lš
œ&˜&Lš
œH˜HL˜Lšœ
žœ˜ šžœžœž˜,Lšœžœ
˜Lšœžœ
˜Lšžœ
˜—šžœžœ
žœž˜"Lš
œ˜Lšžœ
˜—L˜"Lšžœ˜Lš
œ˜L˜—š¡
œ B¢ œ˜�
š¡œžœ
žœžœ˜1Lšœžœ˜&Lš
œ˜šžœ(žœ
ž˜?L˜&Lšžœžœžœ˜=šžœ
žœ ˜$L˜Lš
œ˜Lš
œ˜Lšœžœ
˜Lšžœžœ˜'Lš
œ$˜$Lš
œ˜Lš
œ˜—Lšžœ
˜—Lšœžœ
˜Lš
œ:˜:Lšžœ
žœžœ
˜,Lšžœžœ˜)Lš
œ˜Lš
œ˜—Lšœžœ˜ Lš
œ˜L˜—š¡œ Cœ˜fš¡œžœ
žœžœ˜/Lš
œ˜šžœ8žœ
ž˜OLšžœžœ
žœ
˜&Lšžœ
žœžœ˜+Lšžœ
˜—Lšžœ˜ Lšžœ
žœ˜Lšžœ;˜?šžœžœ˜šžœ˜šžœ ?˜FLšžœ˜Lšžœ ,˜FLšžœ& ˜FLš
œ
˜
—Lšžœ B˜]—Lš
œ˜—Lš
œ˜—Lšœ
žœ˜Lš
œ˜L˜—š¡
œžœ
žœ
žœAžœ
žœ˜€
LšžœŒ
˜’
Lš
œ˜L˜—š¡
œžœ
žœ™&Lš
œ$™$šžœžœž™,Lšœžœ
™Lšžœ
™—šžœžœ
žœž™"Lš
œ™Lšžœ
™—Lš
œ™L™—š¡œžœ
žœ˜'šžœžœž˜,Lšžœžœ
žœ4žœ˜SLšœžœ
˜Lšžœ
˜—šžœžœ
žœž˜"Lš
œ˜Lšžœ
˜—Lš
œ˜L˜—š¡	œžœ
žœ&žœžœžœ˜[Lšžœžœ
˜Lš
œ˜—L˜š¡ œžœ
žœ˜?Lš
œ%˜%šžœžœž˜,Lšžœ
žœžœ˜,šžœ˜Lšžœ"˜$Lšžœ˜Lšžœ˜Lš
œ˜—Lšžœ
˜—Lšžœžœ#˜CLš
œ˜L˜—š¡œžœ
žœ
žœ˜ILšœ) œ Fœ 
™Š
šžœžœ
žœž˜-Lšœžœ˜'šžœ
žœ
ž˜š
œ˜Lš
œ™Lšžœž˜Lšžœ˜"Lšœžœ
˜ Lšœžœ
˜Lš
œ˜Lšžœ
˜Lš
œ˜—š
œ"˜"Lš
œ™Lšžœ˜Lšžœž˜$šžœ ˜!šžœž˜Lšžœ"˜$Lšžœ
žœ
  ˜*Lšžœ˜—Lšžœ
˜Lš
œ˜—Lš
œ˜—Lšžœ
˜—Lšžœ
žœžœ˜6Lšžœ
˜—šžœ
žœžœ˜Lšœžœ!˜-Lšžœ˜Lšžœ"˜&šžœ
žœ2žœ
ž˜NLšžœžœ%žœ˜FLšžœ
žœžœ˜7Lšžœ
˜—Lšœžœ
˜Lš
œ˜—Lšœžœ˜"Lš
œ˜L˜—š¡
œžœ
žœ%˜>Lšœžœ˜2Lšžœžœ&˜=Lšžœ ˜"šžœ˜Lš
œ7˜7Lš
œ!˜!Lš
œH˜HLš
œ˜—Lš
œ˜L˜—š¡
œžœ
žœ˜;Lšœžœ
žœ"˜5Lšžœi˜pLš
œP˜PL˜Lš
œ˜L˜—š¡œžœ
žœ ˜=Lšœžœ
žœ"˜5Lšžœj˜qLš
œP˜PL˜Lšœžœ
˜Lš
œ˜L˜—š
¡œžœ
žœ
žœžœ˜GLš
œ=˜=Lšžœ*˜0Lš
œ˜L˜—š¡œžœ
žœ#žœ˜GLš
œG˜GLš
œ˜——™Lšœžœžœ
˜"Lšœ	žœR˜_—™š¡
œžœ˜Lš
œ(˜(šœ1žœ˜Tš
œ*˜*Lšœ3žœ"˜Y——Lšžœžœ˜3Lš
œ˜L˜—š¡œžœ˜š
ž˜Lšœžœ)˜;L˜Lšœžœ
˜Lšžœ
˜—Lš
œ˜L˜—Lš
œ1˜1L˜
Lš
œ˜——…—Dš\3