DIRECTORY
Basics USING [BITSHIFT, MoveWords],
BTree USING [Compare, CompareEntries, Comparison, EachEntryProc, Entry, EntrySize, EnumerateProc, Key, NewRecordFromEntry, PageNumber, PagePtr, PageSize, PageStorage, PageStoragePrimitives, Reason, Record, ReferencePage, ReferenceType, Relation, ReleasePage, RepresentationPrimitives, reservedWordsPerPage, State, statePage, TestEntryProc, UpdateState],
BTreeInternal USING [AssignRefESR, BackUpOneEntry, BTreeEntrySize, BTreePagePtr, BugType, Compare, CompareEntries, entry0Offset, entry1Offset,  <<entry2Offset,>> EntryOrdinal, entryOverhead, EntrySize, EntryTable, GetDefaultPathStk, Heap, Lock, LockMode, NewRecordFromEntry, nilOffset, nilPage, OffsetTable, OffsetTableObject, PageOffset, pageOverhead, PathEntryLE, PathStk, PathStkEntry, PathStkIndex, PathStkObject, PathToMaxDescendant, ReferencePage, ReferenceStack, ReleasePage, RepairOffsets, ReturnDefaultPathStk, sealValue, Tree, TreeObject, TreeState, Unlock, WriteStatePage];

BTreeRead: MONITOR
LOCKS tree USING tree: Tree
IMPORTS Basics, BTreeInternal      
EXPORTS BTree, BTreeInternal
= { OPEN BTree, BTreeInternal;
Tree: TYPE = REF TreeObject;
TreeObject: PUBLIC TYPE = BTreeInternal.TreeObject;
PathStk: TYPE = REF PathStkObject;
PathStkObject: PUBLIC TYPE = BTreeInternal.PathStkObject;
New: PUBLIC SAFE PROC
[repPrim: RepresentationPrimitives, storPrim: PageStoragePrimitives,
 minEntrySize: CARD ฌ 1, initialState: State[closed..suspended] ฌ closed]
RETURNS [tree: Tree] = CHECKED {
tree ฌ NEW [TreeObject ฌ [state: [], repPrim: repPrim, storPrim: storPrim, minEntrySize: minEntrySize, objectState: initialState]];
};
Open: PUBLIC SAFE PROC
[tree: Tree, storage: PageStorage, pageSize: PageSize,
 initialize: BOOL ฌ FALSE, maintainRecomputableState: BOOL ฌ TRUE] = TRUSTED {
DO
tree.Lock[update, FALSE];
IF tree.objectState#open THEN EXIT;
tree.Unlock[];
SetState[tree, closed];
ENDLOOP;
pageSize ฌ pageSize * SIZE[BYTE]; --Number of bytes in page
tree.state ฌ [pageSize: pageSize];
tree.maxFreeBytes ฌ pageSize-pageOverhead;
tree.maxRecordsPerPage ฌ tree.maxFreeBytes/(tree.minEntrySize+entryOverhead);
tree.awfullyFull ฌ (9*tree.maxFreeBytes)/10;
tree.prettyFull ฌ (2*tree.maxFreeBytes)/3;
tree.fairlyFull ฌ tree.maxFreeBytes/2;
tree.breathingSpace ฌ tree.maxFreeBytes-tree.awfullyFull;
tree.storage ฌ storage;
tree.maintainRecomputableState ฌ maintainRecomputableState;
tree.id ฌ (treeID ฌ treeID+1); -- this doesn't assign a reliably unique ID, since treeID is not protected by any monitor; but it doesn't really matter since the ID is merely protecting against client blunders anyway.
{
ENABLE UNWIND => tree.Unlock[];
IF initialize
THEN {
statePtr: LONG POINTER TO TreeState ฌ tree.ReferencePage[statePage, new];
LongZero[statePtr, pageSize];
IF ~maintainRecomputableState THEN tree.state.entryCount ฌ LAST[CARD];
statePtrญ ฌ tree.state;
tree.ReleasePage[statePage, endOfUpdate];
}
ELSE {
statePtr: LONG POINTER TO TreeState ฌ tree.ReferencePage[statePage, read];
IF statePtr.seal#sealValue THEN ERROR Error[badSeal];
IF statePtr.pageSize#pageSize THEN ERROR Error[wrongPageSize];
tree.state ฌ statePtrญ;
tree.ReleasePage[statePage];
IF tree.state.updateInProgress THEN SIGNAL UpdateInProgress;
};
tree.state.updateInProgress ฌ FALSE;
};
tree.objectState ฌ open;
tree.Unlock[];
};
SetState: PUBLIC SAFE PROC [tree: Tree, state: State[closed..suspended]] = TRUSTED {
DO
WaitUnlocked: ENTRY PROC [tree: Tree] = INLINE {
IF tree.longUpdate THEN WAIT tree.unlocked};
tree.Lock[update, FALSE];
IF tree.objectState#open OR ~tree.longUpdate THEN EXIT;
tree.Unlock[];
WaitUnlocked[tree];
ENDLOOP;
tree.objectState ฌ state;
tree.storage ฌ NIL;
tree.offsetTable ฌ NIL;
tree.defaultPathStk ฌ NIL;
tree.entryTable ฌ NIL;
tree.heap ฌ NIL;
tree.Unlock[];
};
GetState: PUBLIC ENTRY SAFE PROC [tree: Tree]
RETURNS [
  state: State,
  entryCount: CARD,
  greatestPage: PageNumber,
  depth: CARD,
  storage: PageStorage] = CHECKED {
RETURN [
state: tree.objectState,
entryCount: tree.state.entryCount,
greatestPage: tree.state.greatestPage,
depth: tree.state.depth,
storage: tree.storage];
};
Validate: PUBLIC SAFE PROC [tree: Tree] = TRUSTED {
CheckPair: TestEntryProc = {
size: CARD = tree.EntrySize[entry];
IF size+entryOverhead > tree.maxFreeBytes THEN ERROR Error[entrySizesWrong];
entryCount ฌ entryCount+1;
IF firstEntry
THEN firstEntry ฌ FALSE
ELSE IF tree.CompareEntries[prevEntry, entry]#less THEN
ERROR Error[entriesOutOfOrder];
Basics.MoveWords[dst: LOOPHOLE[prevEntry], src: LOOPHOLE[entry],
count: (size+BYTES[WORD]-1)/BYTES[WORD]];
RETURN [TRUE];
};
PrevRecord: TYPE = RECORD [entry: SEQUENCE maxLength: [0..LAST[PageSize]] OF WORD];
prevRecord: REF PrevRecord = NEW[PrevRecord[tree.state.pageSize-reservedWordsPerPage]];
prevEntry: Entry = BASE[DESCRIPTOR[prevRecord.entry]];
entryCount: CARD ฌ 0;
firstEntry: BOOL ฌ TRUE;
[] ฌ EnumerateEntries[tree: tree, key: NIL, Proc: CheckPair];
IF tree.maintainRecomputableState AND entryCount#tree.state.entryCount THEN {
tree.Lock[update];
tree.state.entryCount ฌ entryCount;
tree.WriteStatePage[endOfUpdate];
tree.Unlock[];
};
};
ReadRecord: PUBLIC SAFE PROC
[tree: Tree, key: Key,
 relation: Relation ฌ equal, pathStk: PathStk ฌ NIL, useExistingPath: BOOL ฌ FALSE]
RETURNS [record: Record] = TRUSTED {
EntryProc: PROC [entry: Entry] = {
record ฌ IF entry#NIL THEN tree.NewRecordFromEntry[entry] ELSE NIL;
};
ReadEntry[tree: tree, key: key, relation: relation, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc];
};
EnumerateRecords: PUBLIC SAFE PROC
[tree: Tree, key: Key,
 relation: Relation ฌ equal, pathStk: PathStk ฌ NIL, useExistingPath: BOOL ฌ FALSE,
 Proc: EnumerateProc]
RETURNS [exhausted: BOOL] = TRUSTED {
EntryProc: TestEntryProc = {
RETURN [Proc[tree.NewRecordFromEntry[entry]]];
};
exhausted ฌ EnumerateEntries[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc];
};
ReadEntry: PUBLIC PROC
[tree: Tree, key: Key,
 relation: Relation ฌ equal, pathStk: PathStk ฌ NIL, useExistingPath: BOOL ฌ FALSE,
 Proc: EachEntryProc] = {
SELECT relation FROM
less, lessEqual, equal => {
pathStkWasNil: BOOL ฌ pathStk=NIL;
tree.Lock[read];
IF pathStkWasNil THEN {
IF useExistingPath THEN ERROR Error[nilPathStk];
pathStk ฌ tree.GetDefaultPathStk[];
};
{
ENABLE UNWIND => {
IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk];
tree.Unlock[];
};
equal: BOOL ฌ tree.PathEntryLE[key: key, pathStk: pathStk, useExistingPath: useExistingPath].equal;
IF equal AND relation=less THEN [] ฌ PathToPreviousEntry[tree, pathStk];
IF pathStk.top=0 OR (~equal AND relation=equal)
THEN Proc[NIL]
ELSE {
pagePtr: BTreePagePtr;
pse: LONG POINTER TO PathStkEntry;
[ptr: pagePtr, pse: pse] ฌ tree.ReferenceStack[pathStk];
Proc[@pagePtr[pse.lastOffset].entry !
UNWIND => tree.ReleasePage[pse.pageNumber]];
tree.ReleasePage[pse.pageNumber];
};
};
IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk];
tree.Unlock[];
};
greaterEqual, greater => {
CallWhenRelationSatisfied: TestEntryProc = {
IF key=NIL OR tree.Compare[key, entry] <= maxComparison
THEN {Proc[entry]; RETURN [FALSE]}
ELSE RETURN [TRUE];
};
maxComparison: Comparison ฌ IF relation=greaterEqual THEN equal ELSE less;
exhausted: BOOL ฌ EnumerateEntries[
tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath,
Proc: CallWhenRelationSatisfied];
IF exhausted THEN Proc[NIL];
};
ENDCASE => ERROR;
};
EnumerateEntries: PUBLIC PROC
[tree: Tree, key: Key,
 relation: Relation ฌ equal, pathStk: PathStk ฌ NIL, useExistingPath: BOOL ฌ FALSE,
 Proc: TestEntryProc]
RETURNS [exhausted: BOOL] = {
pathStkWasNil: BOOL ฌ pathStk = NIL;
tree.Lock[read];
IF pathStkWasNil THEN {
IF useExistingPath THEN ERROR Error[nilPathStk];
pathStk ฌ tree.GetDefaultPathStk[];
};
{
ENABLE UNWIND => {
IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk];
tree.Unlock[];
};
leafStkTop: PathStkIndex;
pse: LONG POINTER TO PathStkEntry;
pagePtr: BTreePagePtr ฌ NIL;
skipFirstEntry: BOOL ฌ FALSE;
equal: BOOL;
[equal: equal, depth: leafStkTop] ฌ tree.PathEntryLE[key: key, pathStk: pathStk, useExistingPath: useExistingPath];
IF pathStk.top=0
THEN {
IF leafStkTop=0 THEN GOTO exhausted; -- empty tree
pathStk.top ฌ leafStkTop;
pathStk.path[leafStkTop].lastOffset ฌ entry1Offset;
}
ELSE
SELECT relation FROM
less =>
IF equal AND ~PathToPreviousEntry[tree, pathStk] THEN {
pathStk.top ฌ leafStkTop;
pathStk.path[leafStkTop].lastOffset ฌ entry1Offset;
};
lessEqual =>
NULL;
equal, greaterEqual =>
skipFirstEntry ฌ ~equal;
greater =>
skipFirstEntry ฌ TRUE;
ENDCASE;
exhausted ฌ FALSE;
pse ฌ @pathStk.path[pathStk.top];
DO
offset: PageOffset ฌ pse.lastOffset;
endOffset: PageOffset;
IF pagePtr=NIL THEN {
pagePtr ฌ tree.ReferencePage[pse.pageNumber];
endOffset ฌ nilOffset+(tree.state.pageSize-pagePtr.freeBytes);
};
IF offset>=endOffset
THEN {
tree.ReleasePage[pse.pageNumber];
IF offset>endOffset THEN ERROR Error[entrySizesWrong];
pagePtr ฌ NIL;
IF (pathStk.top ฌ pathStk.top-1) = 0 THEN {
pathStk.version ฌ LAST[CARD];
GOTO exhausted;
};
pse ฌ pse - SIZE[PathStkEntry];
}
ELSE {
nxtPgNo: PageNumber ฌ pagePtr[offset].grPage;
pse.offset ฌ offset + tree.BTreeEntrySize[@pagePtr[offset]];
IF skipFirstEntry THEN skipFirstEntry ฌ FALSE
ELSE IF ~Proc[@pagePtr[offset].entry !
UNWIND => tree.ReleasePage[pse.pageNumber]] THEN EXIT;
WHILE nxtPgNo#nilPage DO
tree.ReleasePage[pse.pageNumber];
pathStk.top ฌ pathStk.top+1;
pse ฌ pse + SIZE[PathStkEntry];
pagePtr ฌ tree.ReferencePage[nxtPgNo];
pse.pageNumber ฌ nxtPgNo;
pse.nextToLastOffset ฌ nilOffset;
pse.lastOffset ฌ entry0Offset;
pse.offset ฌ entry1Offset;
endOffset ฌ nilOffset+(tree.state.pageSize-pagePtr.freeBytes);
nxtPgNo ฌ pagePtr.minPage;
ENDLOOP;
};
pse.nextToLastOffset ฌ pse.lastOffset;
pse.lastOffset ฌ pse.offset;
ENDLOOP;
IF pagePtr#NIL THEN tree.ReleasePage[pse.pageNumber];
EXITS
exhausted => exhausted ฌ TRUE;
};
IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk];
tree.Unlock[];
};
SalvageEntries: PUBLIC PROC
[tree: Tree, Proc: TestEntryProc] RETURNS [exhausted: BOOL] = {
tree.Lock[read];
FOR page: PageNumber IN [statePage+1 .. tree.state.greatestPage] DO
ENABLE UNWIND => tree.Unlock[];
pagePtr: BTreePagePtr ฌ tree.ReferencePage[page];
IF pagePtr.freeBytes IN [0 .. CARD[tree.state.pageSize-pageOverhead]] THEN {
offset: PageOffset ฌ entry1Offset;
endOffset: PageOffset = nilOffset+(tree.state.pageSize-pagePtr.freeBytes);
WHILE offset<endOffset DO
entSize: CARD = tree.BTreeEntrySize[@pagePtr[offset]];
IF entSize<entryOverhead+tree.minEntrySize OR offset+entSize>endOffset THEN EXIT;
IF ~Proc[@pagePtr[offset].entry] THEN GOTO aborted;
offset ฌ offset+entSize;
ENDLOOP;
};
tree.ReleasePage[page];
REPEAT
aborted => exhausted ฌ FALSE;
FINISHED => exhausted ฌ TRUE;
ENDLOOP;
tree.Unlock[];
};
NewPathStk: PUBLIC SAFE PROC RETURNS [pathStk: PathStk] = CHECKED {
pathStk ฌ NEW[PathStkObject];
pathStk.version ฌ LAST[CARD]; -- not valid
};
PathEntryLE: PUBLIC PROC [tree: Tree, key: Key, pathStk: PathStk, useExistingPath: BOOL ฌ FALSE] RETURNS [equal: BOOL, depth: PathStkIndex] = {
BinSearchPage: PROC RETURNS [firstG: EntryOrdinal] = {
firstBadOffset: PageOffset = nilOffset + (tree.state.pageSize - pagePtr.freeBytes);
midOffset: PageOffset ฌ LOOPHOLE[Basics.BITSHIFT[LOOPHOLE[firstBadOffset], -1]];
curOffset: PageOffset ฌ entry1Offset;
l, r: EntryOrdinal ฌ 2;
IF key#NIL THEN DO
IF curOffset>=midOffset THEN {
IF curOffset>=firstBadOffset OR tree.Compare[key, @pagePtr[curOffset].entry] = less THEN EXIT;
midOffset ฌ firstBadOffset;
l ฌ r;
};
curOffset ฌ curOffset + tree.BTreeEntrySize[@pagePtr[curOffset]];
r ฌ r+1;
offsetTable[r] ฌ curOffset;
ENDLOOP;

IF curOffset>firstBadOffset THEN ERROR Error[entrySizesWrong];
WHILE l<r DO
m: EntryOrdinal ฌ Basics.BITSHIFT[l+r, -1];
SELECT tree.Compare[key, @pagePtr[offsetTable[m]].entry] FROM
less => r ฌ m;
equal => {equal ฌ TRUE; RETURN [m+1]};
greater => l ฌ m+1;
ENDCASE;
ENDLOOP;
RETURN [r];
};

pse: LONG POINTER TO PathStkEntry;
offsetTable: OffsetTable;
curPage: PageNumber;
pagePtr: BTreePagePtr;
equal ฌ FALSE;
IF useExistingPath
AND pathStk.treeID=tree.id
AND pathStk.version=tree.version
AND key#NIL THEN {
depth ฌ pathStk.top;
IF depth=0 THEN GOTO dontUse; -- who knows whether this is the min key or not?
WHILE pathStk.path[depth].leastSon # nilPage DO depth ฌ depth+1; ENDLOOP;
[pse: pse, ptr: pagePtr] ฌ tree.ReferenceStack[pathStk];
SELECT tree.Compare[key, @pagePtr[pse.lastOffset].entry] FROM
less => useExistingPath ฌ FALSE; -- wrong key
equal => equal ฌ TRUE; -- correct key
greater => {
IF depth=pathStk.top
AND pse.offset < nilOffset+(tree.state.pageSize-pagePtr.freeBytes)
AND tree.Compare[key, @pagePtr[pse.offset].entry] = less
THEN NULL -- key falls between this entry and next; ok
ELSE useExistingPath ฌ FALSE; -- wrong key, or too hard to decide 
};
ENDCASE;
tree.ReleasePage[pse.pageNumber];
IF useExistingPath THEN RETURN;
EXITS dontUse => NULL;
};
pathStk.top ฌ 0;
pathStk.path[0] ฌ [];
offsetTable ฌ GetOffsetTable[tree];
offsetTable[0] ฌ nilOffset;
offsetTable[1] ฌ entry0Offset;
offsetTable[2] ฌ entry1Offset;
depth ฌ 0;
pse ฌ @pathStk.path[0];
curPage ฌ tree.state.rootPage;
WHILE curPage#nilPage DO
firstG: EntryOrdinal;
pagePtr ฌ tree.ReferencePage[curPage];
depth ฌ depth+1;
pse ฌ pse+SIZE[PathStkEntry];
pse.pageNumber ฌ curPage;
firstG ฌ BinSearchPage[ !
UNWIND => {tree.ReleasePage[curPage]; ReturnOffsetTable[tree, offsetTable]}];
pse.offset ฌ offsetTable[firstG];
pse.lastOffset ฌ offsetTable[firstG-1];
pse.nextToLastOffset ฌ offsetTable[firstG-2];
pse.leastSon ฌ pagePtr.minPage;
IF firstG>2 THEN pathStk.top ฌ depth;  -- real entry in this page
AssignRefESR[@pse.eslFront, NIL];
AssignRefESR[@pse.eslRear, NIL];
curPage ฌ pagePtr[pse.lastOffset].grPage;
tree.ReleasePage[pse.pageNumber];
ENDLOOP;
pathStk.treeID ฌ tree.id;
pathStk.version ฌ tree.version;
ReturnOffsetTable[tree, offsetTable];
};
ReferenceStack: PUBLIC PROC [tree: Tree, pathStk: PathStk, type: ReferenceType ฌ read] RETURNS [pse: LONG POINTER TO PathStkEntry, ptr: PagePtr] = {
pse ฌ @pathStk.path[pathStk.top];
ptr ฌ tree.ReferencePage[pse.pageNumber, type];
};
BackUpOneEntry: PUBLIC PROC [tree: Tree, pse: LONG POINTER TO PathStkEntry] = {
tree.RepairOffsets[pse];
pse.offset ฌ pse.lastOffset;
tree.RepairOffsets[pse];
};
RepairOffsets: PUBLIC PROC [tree: Tree, pse: LONG POINTER TO PathStkEntry] = {
CheckProgression: PROC [offset1, offset2: PageOffset] RETURNS [ok: BOOL] = {
RETURN [SELECT TRUE FROM
offset2=entry0Offset => offset1=nilOffset,
offset2=entry1Offset => offset1=entry0Offset,
offset1>=offset2 => FALSE,
ENDCASE => offset1+tree.BTreeEntrySize[@pagePtr[offset1]] = offset2];
};
pagePtr: BTreePagePtr = tree.ReferencePage[pse.pageNumber];
IF ~(CheckProgression[pse.lastOffset, pse.offset] AND CheckProgression[pse.nextToLastOffset, pse.lastOffset]) THEN {
newOffset: PageOffset ฌ entry1Offset;
lastOffset: PageOffset ฌ entry0Offset;
nextToLastOffset: PageOffset ฌ nilOffset;
WHILE newOffset#pse.offset DO
nextToLastOffset ฌ lastOffset;
lastOffset ฌ newOffset;
newOffset ฌ newOffset+tree.BTreeEntrySize[@pagePtr[newOffset]];
ENDLOOP;
pse.lastOffset ฌ lastOffset;
pse.nextToLastOffset ฌ nextToLastOffset;
};
tree.ReleasePage[pse.pageNumber];
};
PathToMaxDescendant: PUBLIC PROC [tree: Tree, pathStk: PathStk, page: PageNumber] = {
pse: LONG POINTER TO PathStkEntry;
pagePtr: BTreePagePtr;
WHILE page#nilPage DO
pathStk.top ฌ pathStk.top+1;
pse ฌ @pathStk.path[pathStk.top];
pse.pageNumber ฌ page;
pagePtr ฌ tree.ReferencePage[page];
pse.offset ฌ nilOffset+(tree.state.pageSize-pagePtr.freeBytes);
pse.lastOffset ฌ entry1Offset;
pse.nextToLastOffset ฌ entry0Offset;
tree.RepairOffsets[pse];
AssignRefESR[@pse.eslFront, NIL];
AssignRefESR[@pse.eslRear, NIL];
pse.leastSon ฌ nilPage;
page ฌ pagePtr[pse.lastOffset].grPage;
tree.ReleasePage[pse.pageNumber];
ENDLOOP;
};
WriteStatePage: PUBLIC PROC [tree: Tree, update: UpdateState ฌ unchanged] = {
statePtr: LONG POINTER TO TreeState = tree.ReferencePage[statePage, write];
statePtrญ ฌ tree.state;
tree.ReleasePage[statePage, update];
};
Lock: PUBLIC ENTRY PROC [tree: Tree, mode: LockMode, checkState: BOOL ฌ TRUE] = {
DO
SELECT tree.objectState FROM
closed => IF checkState THEN RETURN WITH ERROR Error[closed];
suspended => IF checkState THEN {WAIT tree.unlocked; LOOP};
open => NULL
ENDCASE;
SELECT mode FROM
read =>
IF tree.lockCount>=0 THEN {tree.lockCount ฌ tree.lockCount+1; EXIT};
update =>
IF tree.lockCount=0 THEN {tree.lockCount ฌ -1; EXIT};
ENDCASE;
WAIT tree.unlocked; -- wait for tree to be unlocked
ENDLOOP;
};
Unlock: PUBLIC ENTRY PROC [tree: Tree] = {
IF tree.lockCount=0 THEN ERROR Bug[treeNotLocked];
tree.lockCount ฌ MAX[tree.lockCount-1, 0];
IF tree.lockCount=0 THEN BROADCAST tree.unlocked;
};
GetHeapAndTable: PUBLIC ENTRY PROC [tree: Tree, pathStk: PathStk] = {
pathStk.heap ฌ tree.heap;
tree.heap ฌ NIL;
pathStk.entryTable ฌ tree.entryTable;
tree.entryTable ฌ NIL;
IF pathStk.heap#NIL
THEN heapsReused ฌ heapsReused+1
ELSE {
pathStk.heap ฌ NEW[Heap[tree.maxRecordsPerPage + 1]];
pathStk.entryTable ฌ NEW[EntryTable[3*tree.maxRecordsPerPage + 2]];
heapsCreated ฌ heapsCreated+1;
};
};
ReturnHeapAndTable: PUBLIC ENTRY PROC [tree: Tree, pathStk: PathStk] = {
IF tree.heap=NIL THEN { tree.heap ฌ pathStk.heap; tree.entryTable ฌ pathStk.entryTable };
pathStk.heap ฌ NIL;
pathStk.entryTable ฌ NIL;
};
GetDefaultPathStk: PUBLIC ENTRY PROC [tree: Tree] RETURNS [pathStk: PathStk] = {
pathStk ฌ tree.defaultPathStk;
tree.defaultPathStk ฌ NIL;
IF pathStk=NIL
THEN { pathStk ฌ NewPathStk[]; pathStksCreated ฌ pathStksCreated+1 }
ELSE { pathStk.version ฌ LAST [CARD]; pathStksReused ฌ pathStksReused+1 };
};
ReturnDefaultPathStk: PUBLIC ENTRY PROC [tree: Tree, pathStk: PathStk] = {
IF tree.defaultPathStk=NIL THEN tree.defaultPathStk ฌ pathStk;
};
Error: PUBLIC SAFE ERROR [reason: Reason] = CODE;
UpdateInProgress: PUBLIC SAFE SIGNAL = CODE;
Bug: PUBLIC ERROR [type: BugType] = CODE;
PathToPreviousEntry: PROC [tree: Tree, pathStk: PathStk] RETURNS [ok: BOOL] = {
pagePtr: BTreePagePtr;
pse: LONG POINTER TO PathStkEntry ฌ @pathStk.path[pathStk.top];
IF pathStk.top=0 THEN RETURN [FALSE];
tree.BackUpOneEntry[pse];
[ptr: pagePtr, pse: pse] ฌ tree.ReferenceStack[pathStk];
IF pagePtr[pse.lastOffset].grPage=nilPage
THEN {
WHILE pse.lastOffset<entry1Offset DO
tree.ReleasePage[pse.pageNumber];
pathStk.top ฌ pathStk.top-1;
IF pathStk.top=0 THEN RETURN [FALSE];
[ptr: pagePtr, pse: pse] ฌ tree.ReferenceStack[pathStk];
ENDLOOP;
tree.ReleasePage[pse.pageNumber];
}
ELSE {
page: PageNumber ฌ pagePtr[pse.lastOffset].grPage;
tree.ReleasePage[pse.pageNumber];
tree.PathToMaxDescendant[pathStk: pathStk, page: page];
};
RETURN [TRUE];
};
GetOffsetTable: ENTRY PROC [tree: Tree] RETURNS [offsetTable: OffsetTable] = INLINE {
offsetTable ฌ tree.offsetTable;
tree.offsetTable ฌ NIL;
IF offsetTable#NIL
THEN offsetTablesReused ฌ offsetTablesReused+1
ELSE {
offsetTable ฌ NEW[OffsetTableObject[tree.maxRecordsPerPage + 2]];
offsetTablesCreated ฌ offsetTablesCreated+1;
};
};
ReturnOffsetTable: ENTRY PROC [tree: Tree, offsetTable: OffsetTable] = INLINE {
IF tree.offsetTable=NIL THEN tree.offsetTable ฌ offsetTable;
};

LongZero: PROC [to: LONG POINTER, nwords: CARD] = {
Block: TYPE = ARRAY [0..3] OF WORD;
BlockPtr: TYPE = LONG POINTER TO Block;
WHILE nwords >= 4 * SIZE[BYTE] DO
LOOPHOLE[to, BlockPtr][0] ฌ 0;
LOOPHOLE[to, BlockPtr][1] ฌ 0;
LOOPHOLE[to, BlockPtr][2] ฌ 0;
LOOPHOLE[to, BlockPtr][3] ฌ 0;
to ฌ to + SIZE[Block];
nwords ฌ nwords - 4 * SIZE[BYTE];
ENDLOOP;
};
WordPtr: TYPE = LONG POINTER TO WORD;
treeID: CARD ฌ 0;
offsetTablesReused, offsetTablesCreated: CARD ฌ 0;
heapsReused, heapsCreated: CARD ฌ 0;
pathStksReused, pathStksCreated: CARD ฌ 0;


}.


โ
BTreeRead.mesa
Copyright ำ 1985, 1986, 1988, 1992 by Xerox Corporation.  All rights reserved.
This module contains everything you need to open and read BTrees.
Taft, November 25, 1983 3:02 pm
Russ Atkinson (RRA) June 3, 1988 12:25:25 pm PDT
Bob Hagmann April 30, 1985 7:14:30 am PDT
Brian Oki June 14, 1989 3:58:00 PDT

Loose ends:
1. Validate's repair of the entryCount is slightly flakey since the tree is unlocked between the EnumerateEntries that counts the entries and the setting of the entryCount.
Willie-s, April 15, 1992 12:15 pm PDT
IO,
Rope,
SimpleStreams USING [Create],
Convert;
inStream, outStream, errStream: IO.STREAM;
hasEcho: BOOL;
BTree.
first ensure that it's not already open
this actually wakes up every time the tree is unlocked, including the call to Unlock from SetUpdateInProgress
Tree is now locked in update mode with no update in progress
Extra nesting required so that pathStkWasNil is visible in the catch phrase (yecch)!
Extra nesting required so that pathStkWasNil is visible in the catch phrase (yecch)!
key is less than any existing entry in the tree.  Set PathStk to first record in leftmost leaf page.
ran off end of page.  Pop up a level and do the next entry in the father page
ran off end of tree.  PathStk is no longer valid.
enumerate this entry
In a non-leaf page, find the leftmost right descendant of the entry we just did.
BTreeInternal.
Returns an index r such that offsetTable[r] is the offset of the first entry strictly greater than key, and fills in offsetTable[2] through offsetTable[r] with the offsets of all entries up to and including that one.

Scan records linearly and build offsetTable until half the in-use portion of the BTree page has been examined.  Then do one key comparison to detemine which half of the page to direct our attention to, and build the rest of offsetTable only if necessary.  On the average this saves 25% of the work of building offsetTables, and costs no extra comparison since the first comparison would examine a middle record anyway (not necessarily the same one).
At this point, offsetTable[r] is the offset of the first non-entry, which we assume to have an infinite key (which we shall never test).  We shall leave r pointing at the offset of the first entry strictly greater than key.
Body of PathEntryLE
supplied PathStk is still valid.  See if it is for the correct key.
Perform the normal BTree lookup
BROADCAST, not NOTIFY, because releasing a write lock might make multiple readers eligible to enter simultaneously.
heap holds at most one page's worth of entries at any given time
may have to index scroll containing up to 3 pages' worth of entries
Private
Backs up the PathStk to refer to the previous entry in the tree. Returns TRUE normally, FALSE if there is no previous entry.
this is a leaf page
hit beginning of current page: previous entry is left father
this is not a leaf page: previous entry is rightmost left son
Obtains the OffsetTable associated with the BTree, if it is available; otherwise makes a new one.
Gives back the OffsetTable.
Zero out all the bytes in the thing pointed to by to
FOR i: [0..3] IN [0..nwords) DO -- doesn't seem necessary
LOOPHOLE[to, BlockPtr][i] _ 0;
ENDLOOP;
[inStream, outStream, errStream, hasEcho] _ SimpleStreams.Create[windowSystem: $uxio];
Bob Hagmann April 30, 1985 7:04:49 am PDT
Catch File.Error and skip those pages during SalvageEntries
changes to: SalvageEntries
Russ Atkinson (RRA) March 4, 1988 5:51:29 pm PST
converted to be Mimosa-compatible, removed dependence on File and PrincOpsUtils.



ส๒•NewlineDelimiter

–
(cedarcode) style™
codeš
œ™Kšœ
ฯe
œC™NK™AKš
ฯy™J™0K™)K™#K™š
œ™Kš
œฌ
™ฌ
—K™%—˜š
ฯk	˜	KšœŸœŸœ
˜#KšœŸœึ˜แKšœŸœต˜ศK˜KšŸœ
™Kš
œ™KšœŸœ
™Kš
œ™——
headšฯn	œŸ˜Icode2šŸœŸœ˜MšŸœ˜#MšŸœ˜MšœŸœ˜Mšœ Ÿœ
Ÿœ
™*Kšœ	Ÿœ
™—š
œ™MšœŸœŸœ˜MšœŸœ
Ÿœ˜3Mšœ	ŸœŸœ˜"MšœŸœ
Ÿœ˜9š œŸœ
Ÿœ
ŸœTŸœ7ŸœŸœ˜ล
MšœŸœy˜ƒ
Mš
œ˜—š œŸœ
Ÿœ
ŸœDŸœŸœŸœŸœŸœ˜œ
š
Ÿ˜Mš
œ'™'MšœŸœ˜MšŸœŸœ
Ÿœ
˜#M˜Mš
œ˜MšŸœ
˜—MšœŸœ
Ÿœ˜;M˜"M˜*M˜MM˜,M˜*M˜&M˜9M˜M˜;Mšœฯcน
˜ุ
š
œ
˜
MšŸœ
Ÿœ˜šŸœ˜
šŸœ˜Mšœ
Ÿœ
Ÿœ
Ÿœ0˜IMš
œ˜MšŸœŸœŸœ
Ÿœ˜FM˜Mš
œ)˜)Mš
œ
˜
—šŸœ˜Mšœ
Ÿœ
Ÿœ
Ÿœ1˜JMšŸœŸœ
Ÿœ˜5MšŸœŸœ
Ÿœ˜>M˜Mš
œ˜MšŸœŸœ
Ÿœ˜<Mš
œ˜——MšœŸœ
˜$Mš
œ˜—M˜M˜Mš
œ˜—š
 œŸœ
Ÿœ
Ÿœ1Ÿœ˜Tš
Ÿ˜š œŸœ
ŸœŸœ˜0MšŸœŸœ
Ÿœ˜,—MšœŸœ˜MšŸœŸœŸœ
Ÿœ
˜7M˜š
œ˜Mš
œm™m—MšŸœ
˜—M™<M˜MšœŸœ
˜MšœŸœ
˜MšœŸœ
˜MšœŸœ
˜MšœŸœ
˜M˜Mš
œ˜—š œŸœ
Ÿœ
ŸœŸœ!Ÿœ'ŸœŸœ˜ช
šŸœ˜Mš
œ˜Mš
œ"˜"Mš
œ&˜&Mš
œ˜Mš
œ˜—Mš
œ˜—š
 œŸœ
Ÿœ
ŸœŸœ˜3š 	œ˜MšœŸœ˜#MšŸœ(Ÿœ
Ÿœ˜LM˜šŸœ˜
MšŸœŸ˜šŸœ
Ÿœ,Ÿ˜7MšŸœ˜——Mš
œŸœŸœŸœ
ŸœŸœ
Ÿœ˜jMšŸœŸœ˜Mš
œ˜—Mš
œŸœŸœ	ŸœŸœŸœ
Ÿœ˜SMšœŸœŸœ7˜WMšœŸœ
Ÿ
œ˜6MšœŸœ˜MšœŸœŸœ
˜Mšœ'Ÿœ˜=šŸœ Ÿœ"Ÿœ˜MM˜M˜#M˜!M˜Mš
œ˜—Mš
œ˜—š 
œŸœ
Ÿœ
ŸœGŸœŸœŸœŸœŸœ˜ฌ
š 	œŸœ˜"Mšœ	ŸœŸœ
Ÿœ Ÿœ
Ÿœ
˜CMš
œ˜—Mš
œy˜yMš
œ˜—š œŸœ
Ÿœ
ŸœGŸœŸœŸœŸœ
ŸœŸœ˜ษ
š 	œ˜MšŸœ(˜.Mš
œ˜—M˜xMš
œ˜—š 	œŸœ
ŸœGŸœŸœŸœ˜›
šŸœ
Ÿ˜š
œ˜MšœŸœŸœ
˜"M˜šŸœŸœ˜MšŸœŸœ
Ÿœ˜0M˜#Mš
œ˜—š
œ
˜
Mš
œT™TšŸœ
Ÿœ˜MšŸœŸœ$˜9Mš
œ˜Mš
œ˜—MšœŸœX˜cMšŸœŸœŸœ)˜HšŸœŸœ	Ÿœ˜/MšŸœŸœ
˜šŸœ˜Mš
œ˜MšœŸœ
Ÿœ
Ÿœ˜"M˜8š
œ%˜%MšŸœ&˜,—Mš
œ!˜!Mš
œ˜——Mš
œ˜—MšŸœŸœ$˜9M˜Mš
œ˜—š
œ˜š œ˜,šŸœŸœ
Ÿœ*˜7MšŸœŸœŸœ˜"MšŸœ
ŸœŸœ˜—Mš
œ˜—MšœŸœŸœŸœ˜JMšœŸœ€
˜
MšŸœŸœŸœ˜Mš
œ˜—MšŸœŸœ
˜—Mš
œ˜—š œŸœ
ŸœGŸœŸœŸœŸœ
Ÿœ˜ผ
MšœŸœ
Ÿœ
˜$M˜šŸœŸœ˜MšŸœŸœ
Ÿœ˜0M˜#Mš
œ˜—š
œ
˜
Mš
œT™TšŸœ
Ÿœ˜MšŸœŸœ$˜9Mš
œ˜Mš
œ˜—Mš
œ˜MšœŸœ
Ÿœ
Ÿœ˜"MšœŸœ
˜MšœŸœŸœ
˜MšœŸœ
˜M˜sšŸœ˜šŸœ˜Mš
œd™dMšŸœŸœ
Ÿœก˜2M˜M˜3Mš
œ
˜
—š
Ÿ˜šŸœ
Ÿ˜˜šŸœŸœ%Ÿœ˜7M˜M˜3Mš
œ˜——š
œ˜MšŸœ
˜—š
œ˜M˜—š
œ
˜
MšœŸœ
˜—MšŸœ
˜———MšœŸœ
˜M˜!š
Ÿ˜M˜$M˜šŸœ	Ÿœ
Ÿœ˜M˜-M˜>Mš
œ˜—šŸœ˜šŸœ˜Mš
œM™MMš
œ!˜!MšŸœŸœ
Ÿœ˜6Mšœ
Ÿœ
˜šŸœ#Ÿœ˜+Mš
œ1™1MšœŸœ
Ÿœ˜MšŸœ˜Mš
œ˜—MšœŸœ˜Mš
œ
˜
—šŸœ˜Mš
œ™M˜-M˜<MšŸœŸœŸ˜-šŸœ˜&MšŸœ&Ÿœ
Ÿœ
˜6—šŸœŸ˜Mš
œP™PM˜!M˜MšœŸœ˜M˜&M˜M˜!M˜M˜M˜>M˜MšŸœ
˜—Mš
œ˜——M˜&M˜MšŸœ
˜—MšŸœ	Ÿœ
Ÿœ"˜5š
Ÿ˜MšœŸœ
˜—Mš
œ˜—MšŸœŸœ$˜9M˜Mš
œ˜—š
 œŸœ
Ÿœ"Ÿœ
Ÿœ˜[M˜šŸœŸœ*Ÿ˜CMšŸœ
Ÿœ˜M˜1šŸœŸœŸœ$Ÿœ˜LM˜"Mš
œJ˜JšŸœŸ˜Mšœ	Ÿœ)˜6MšŸœ)ŸœŸœ
Ÿœ
˜QMšŸœŸœ
Ÿœ	˜3M˜MšŸœ
˜—Mš
œ˜—M˜š
Ÿ˜MšœŸœ
˜MšŸœŸœ
˜—MšŸœ
˜—M˜Mš
œ˜—š 
œŸœ
Ÿœ
Ÿœ
ŸœŸœ˜CMšœ
Ÿœ˜MšœŸœ
Ÿœก˜*Mš
œ˜——š
œ™š œŸœ
Ÿœ;ŸœŸœŸœ	Ÿœ˜
š 
œŸœ
Ÿœ˜6Mš
œุ
™ุ
M˜SMšœŸœŸœ
Ÿœ˜PM˜%M˜M™Mš
œม™มšŸœŸœ
Ÿœ
Ÿ˜šŸœŸœ˜MšŸœŸœ5Ÿœ
Ÿœ
˜^M˜M˜Mš
œ˜—M˜AM˜M˜MšŸœ
˜M˜—MšŸœŸœ
Ÿœ˜>Mš
œ฿
™฿
šŸœŸ˜MšœŸœ
˜+šŸœ3Ÿ˜=M˜MšœŸœŸœ˜&M˜MšŸœ
˜—MšŸœ
˜—MšŸœ˜Mš
œ˜—M˜M™MšœŸœ
Ÿœ
Ÿœ˜"M˜M˜M˜MšœŸœ
˜šŸœŸœŸœŸœŸœ
Ÿœ˜aMš
œC™CM˜MšŸœ	Ÿœ
Ÿœ
ก0˜NMšŸœ(ŸœŸœ
˜IM˜8šŸœ3Ÿ˜=MšœŸœก˜-MšœŸœก˜%š
œ˜šŸœŸœ@Ÿœ5˜
MšŸœ
Ÿœ
ก,˜6MšŸœŸœก$˜B—Mš
œ˜—MšŸœ
˜—M˜!MšŸœŸœ
Ÿœ
˜MšŸœŸœ
˜Mš
œ˜—Mš
œ™M˜M˜M˜#M˜M˜M˜M˜
M˜M˜šŸœŸ˜Mš
œ˜M˜&M˜Mšœ
Ÿœ˜M˜˜MšŸœG˜M—M˜!M˜'M˜-M˜MšŸœ
Ÿœก˜AMšœŸœ˜!MšœŸœ˜ M˜)Mš
œ!˜!MšŸœ
˜—M˜M˜Mš
œ%˜%Mš
œ˜—š œŸœ
Ÿœ<ŸœŸœ
Ÿœ
Ÿœ ˜”
M˜!M˜/Mš
œ˜—š œŸœ
ŸœŸœ
Ÿœ
Ÿœ˜OM˜M˜M˜Mš
œ˜—š 
œŸœ
ŸœŸœ
Ÿœ
Ÿœ˜Nš œŸœ ŸœŸœ˜LšŸœŸœ
Ÿœ
Ÿ˜M˜*M˜-MšœŸœ
˜MšŸœ>˜E—Mš
œ˜—M˜;šŸœ0Ÿœ9Ÿœ˜tM˜%M˜&M˜)šŸœŸ˜M˜M˜M˜?MšŸœ
˜—M˜M˜(Mš
œ˜—M˜!Mš
œ˜—š œŸœ
Ÿœ5˜UMšœŸœ
Ÿœ
Ÿœ˜"M˜šŸœŸ˜M˜M˜!M˜M˜#M˜?M˜M˜$M˜MšœŸœ˜!MšœŸœ˜ M˜M˜&Mš
œ!˜!MšŸœ
˜—Mš
œ˜—š œŸœ
Ÿœ2˜MMšœ
Ÿœ
Ÿœ
Ÿœ2˜KM˜Mš
œ$˜$Mš
œ˜—š œŸœ
Ÿœ
Ÿœ*ŸœŸœ˜Qš
Ÿ˜šŸœŸ˜Mšœ
ŸœŸœ
Ÿœ
Ÿœ
Ÿœ˜=Mš	œ
ŸœŸœŸœŸœ˜;MšœŸ˜MšŸœ
˜—šŸœŸ˜˜MšŸœŸœ%Ÿœ˜D—˜	MšŸœŸœŸœ˜5—MšŸœ
˜—MšŸœก˜3MšŸœ
˜—Mš
œ˜—š œŸœ
Ÿœ
Ÿœ˜*MšŸœŸœ
Ÿœ˜2MšœŸœ˜*šŸœŸœ
Ÿ	œ˜1Mš
œs™s—Mš
œ˜—š œŸœ
Ÿœ
Ÿœ#˜EM˜MšœŸœ
˜M˜%MšœŸœ
˜šŸœŸ˜MšŸœ˜ šŸœ˜šœŸœ#˜5Mš
œ@™@—šœŸœ+˜CMš
œC™C—M˜Mš
œ˜——Mš
œ˜—š œŸœ
Ÿœ
Ÿœ#˜HMšŸœŸœ
ŸœD˜YMšœŸœ
˜MšœŸœ
˜Mš
œ˜—š
 œŸœ
Ÿœ
ŸœŸœ˜PM˜MšœŸœ
˜šŸœ	Ÿ˜MšŸœ@˜DMšŸœŸœŸœ'˜J—Mš
œ˜—š œŸœ
Ÿœ
Ÿœ#˜JMšŸœŸœ
Ÿœ˜>Mš
œ˜—Mš	œŸœ
Ÿœ
ŸœŸœ
˜1Mš	œŸœ
Ÿœ
ŸœŸœ
˜,MšœŸœ
ŸœŸœ
˜)—š
œ™š œŸœ ŸœŸœ˜OMšœIŸœŸœ™|Mš
œ˜MšœŸœ
Ÿœ
Ÿœ+˜?MšŸœŸœ
ŸœŸœ˜%M˜M˜8šŸœ'˜)šŸœ˜Mš
œ™šŸœŸ˜$Mš
œ<™<Mš
œ!˜!M˜MšŸœŸœ
ŸœŸœ˜%M˜8MšŸœ
˜—Mš
œ!˜!Mš
œ
˜
—šŸœ
˜Mš
œ=™=M˜2Mš
œ!˜!Mš
œ7˜7Mš
œ˜——MšŸœŸœ˜Mš
œ˜—š
 œŸœ
ŸœŸœŸœ˜UMš
œa™aM˜MšœŸœ
˜šŸœ
Ÿ˜MšŸœ*˜.šŸœ˜MšœŸœ0˜AM˜,Mš
œ˜——Mš
œ˜—š œŸœ
Ÿœ*Ÿœ˜OMš
œ™MšŸœŸœ
Ÿœ ˜<Mš
œ˜M˜—Mš
œ4™4š
 œŸœŸœ
Ÿœ
Ÿœ˜3Mš	œŸœŸœŸœ
Ÿœ
˜#Mš	œ
ŸœŸœ
Ÿœ
Ÿœ˜'šŸœŸœ
ŸœŸ˜!MšŸœ˜MšŸœ˜MšŸœ˜MšŸœ˜Mšœ
Ÿœ˜MšœŸœ
Ÿœ˜!MšŸœ
˜—šŸœŸœ
Ÿ™9MšŸœ™MšŸœ
™—M˜—Mšœ	ŸœŸœ
Ÿœ
Ÿœ
Ÿœ
˜%MšœŸœ˜Mšœ)Ÿœ˜2MšœŸœ˜$Mšœ!Ÿœ˜*M˜Mš
œV™VM˜—š
œ˜M˜—™)Kš
œ;™;Kšœฯr™—™0KšœOข
™P—K™K™K™—…—Lฎq‚