DIRECTORY
BTree USING [Compare, CompareEntries, Comparison, Entry, EntrySize, Key, NewRecordFromEntry, PageNumber, PagePtr, PageSize, PageStorage, PageStoragePrimitives, Reason, Record, ReferencePage, ReferenceType, Relation, ReleasePage, RepresentationPrimitives, State, statePage, UpdateState],
BTreeInternal USING [AssignRefESR, BackUpOneEntry, BTreeEntrySize, BTreePagePtr, BugType, Compare, CompareEntries, entry0Offset, entry1Offset, 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, reservedWordsPerPage, ReturnDefaultPathStk, sealValue, Tree, TreeObject, TreeState, Unlock, WriteStatePage],
File USING [Error, wordsPerPage],
PrincOpsUtils USING [BITSHIFT, LongCopy, LongZero];
BTreeRead: MONITOR
LOCKS tree USING tree: Tree
IMPORTS BTreeInternal, File, PrincOpsUtils
EXPORTS BTree, BTreeInternal
= { OPEN BTree, BTreeInternal;
CARD: TYPE = LONG CARDINAL;
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: CARDINAL _ 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 _ File.wordsPerPage, initialize: BOOL _ FALSE, maintainRecomputableState: BOOL _ TRUE] = TRUSTED {
DO
tree.Lock[update, FALSE];
IF tree.objectState#open THEN EXIT;
tree.Unlock[];
SetState[tree, closed];
ENDLOOP;
tree.state _ [pageSize: pageSize];
tree.maxFreeWords _ pageSize-pageOverhead;
tree.maxRecordsPerPage _ tree.maxFreeWords/(tree.minEntrySize+entryOverhead);
tree.awfullyFull _ (9*tree.maxFreeWords)/10;
tree.prettyFull _ (2*tree.maxFreeWords)/3;
tree.fairlyFull _ tree.maxFreeWords/2;
tree.breathingSpace _ tree.maxFreeWords-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];
PrincOpsUtils.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: CARDINAL, 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: PROC [entry: Entry] RETURNS [continue: BOOL] = {
size: CARDINAL = tree.EntrySize[entry];
IF size+entryOverhead > tree.maxFreeWords THEN ERROR Error[entrySizesWrong];
entryCount _ entryCount+1;
IF firstEntry
THEN firstEntry _ FALSE
ELSE IF tree.CompareEntries[prevEntry, entry]#less THEN
ERROR Error[entriesOutOfOrder];
PrincOpsUtils.LongCopy[to: prevEntry, from: entry, nwords: size];
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: PROC [record: Record] RETURNS [continue: BOOL]] RETURNS [exhausted: BOOL] = TRUSTED {
EntryProc: PROC [entry: Entry] RETURNS [continue: BOOL] = {
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: UNSAFE PROC [entry: Entry]] = {
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: PROC [entry: Entry] RETURNS [continue: BOOL] = {
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: UNSAFE PROC [entry: Entry] RETURNS [continue: BOOL]] 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.freeWords);
};
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.freeWords);
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: UNSAFE PROC [entry: Entry] RETURNS [continue: BOOL]] RETURNS [exhausted: BOOL] = {
tree.Lock[read];
FOR page: PageNumber IN [statePage+1 .. tree.state.greatestPage] DO
ENABLE UNWIND => tree.Unlock[];
pagePtr: BTreePagePtr;
pagePtr _ tree.ReferencePage[page ! File.Error => LOOP];
IF pagePtr.freeWords IN [0 .. CARDINAL[tree.state.pageSize-pageOverhead]] THEN {
offset: PageOffset _ entry1Offset;
endOffset: PageOffset = nilOffset+(tree.state.pageSize-pagePtr.freeWords);
WHILE offset<endOffset DO
entSize: CARDINAL = 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.freeWords);
midOffset: PageOffset _ LOOPHOLE[PrincOpsUtils.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 _ PrincOpsUtils.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.freeWords)
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.freeWords);
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; -- BROADCAST, not NOTIFY, because releasing a write lock might make multiple readers eligible to enter simultaneously.
};
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]]; -- heap holds at most one page's worth of entries at any given time
pathStk.entryTable _ NEW[EntryTable[3*tree.maxRecordsPerPage+1]]; -- may have to index scroll containing up to 3 pages' worth of entries
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;
};
treeID: CARDINAL _ 0;
offsetTablesReused, offsetTablesCreated: CARD _ 0;
heapsReused, heapsCreated: CARD _ 0;
pathStksReused, pathStksCreated: CARD _ 0;
}.


’BTreeRead.mesa
Copyright c 1985, 1986 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) April 28, 1986 1:00:26 pm PDT
Bob Hagmann April 30, 1985 7:14:30 am 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.
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.
supplied PathStk is still valid.  See if it is for the correct key.
Perform the normal BTree lookup
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.
Bob Hagmann April 30, 1985 7:04:49 am PDT
Catch File.Error and skip those pages during SalvageEntries
changes to: SalvageEntries

ΚH–

"Cedar" style˜
headš
œ™Icodešœ
Οm
œ7™BL™AL™J™1L™)—™š
œ™Lš
œ¬
™¬
——˜š
Οk	˜	Lšœžœ“˜žLšœžœΈ˜ΛLšœžœ˜!Lšœžœžœ˜3——šΟn	œž˜Icode2šžœžœ˜Mšžœ#˜*Mšžœ˜Mšœžœ˜Mšžœžœžœ
žœ
˜—š
œ™Mšœžœžœ˜Mšœžœ
žœ˜3Mšœ	žœžœ˜"Mšœžœ
žœ˜9šŸœžœ
žœ
žœTžœ7žœžœ˜Θ
Mšœžœy˜ƒ
Mš
œ˜—šŸœžœ
žœ
žœXžœžœžœžœžœ˜―
š
ž˜Mš
œ'™'Mšœžœ˜Mšžœžœ
žœ
˜#M˜Mš
œ˜Mšžœ
˜—M˜"Mš
œ*˜*Mš
œM˜MMš
œ,˜,Mš
œ*˜*Mš
œ&˜&Mš
œ9˜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š
œ˜—š
Ÿœžœ
žœ
žœžœ˜3šŸ	œžœžœžœ˜;Mšœžœ˜'Mšžœ(žœ
žœ˜LM˜šžœ˜
Mšžœž˜šžœ
žœ,ž˜7Mšžœ˜——Mš
œA˜AMšžœžœ˜Mš
œ˜—Mš
œžœžœ	žœžœžœ
žœ˜SMšœžœžœ7˜WMšœžœ
ž
œ˜6Mšœžœ˜Mšœžœžœ
˜Mšœ'žœ˜=šžœ žœ"žœ˜MM˜M˜#M˜!M˜Mš
œ˜—Mš
œ˜—šŸ
œžœ
žœ
žœGžœžœžœžœžœ˜«
šŸ	œžœ˜"Mšœ	žœžœ
žœ žœ
žœ
˜CMš
œ˜—Mš
œy˜yMš
œ˜—šŸœžœ
žœ
žœGžœžœžœžœžœžœžœ
žœžœ˜θ
šŸ	œžœžœžœ˜;Mšžœ(˜.Mš
œ˜—Mš
œx˜xMš
œ˜—šŸ	œžœ
žœGžœžœžœžœ
žœ˜¦
šžœ
ž˜š
œ˜Mšœžœžœ
˜"M˜šžœžœ˜Mšžœžœ
žœ˜0M˜#Mš
œ˜—š
œ
˜
Mš
œT™Tšžœ
žœ˜Mšžœžœ$˜9Mš
œ˜Mš
œ˜—MšœžœX˜cMšžœžœžœ)˜Hšžœžœ	žœ˜/Mšžœžœ
˜šžœ˜Mš
œ˜Mšœžœ
žœ
žœ˜"Mš
œ8˜8š
œ%˜%Mšžœ&˜,—Mš
œ!˜!Mš
œ˜——Mš
œ˜—Mšžœžœ$˜9M˜Mš
œ˜—š
œ˜šŸœžœžœžœ˜Kšžœžœ
žœ*˜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˜sšžœ˜šžœ˜Mš
œd™dMšžœžœ
žœ ˜2Mš
œ˜Mš
œ3˜3Mš
œ
˜
—š
ž˜šžœ
ž˜˜šžœžœ%žœ˜7Mš
œ˜Mš
œ3˜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˜Mšœ2žœ˜8šžœžœžœ$žœ˜PM˜"Mš
œJ˜Jšžœž˜Mšœ	žœ)˜:Mšžœ)žœžœ
žœ
˜QMšžœžœ
žœ	˜3M˜Mšžœ
˜—Mš
œ˜—M˜š
ž˜Mšœžœ
˜Mšžœžœ
˜—Mšžœ
˜—M˜Mš
œ˜—šŸ
œžœ
žœ
žœ
žœžœ˜CMšœ
žœ˜Mšœžœ
žœ ˜*Mš
œ˜——š
œ™šŸœžœ
žœ;žœžœžœ	žœ˜
šŸ
œžœ
žœ˜6Mš
œΨ
™Ψ
M˜SMšœžœžœ
žœ˜WM˜%Mš
œ˜Mš
œΑ™Αšžœžœ
žœ
ž˜šžœžœ˜Mšžœžœ5žœ
žœ
˜^Mš
œ˜M˜Mš
œ˜—Mš
œA˜AM˜M˜Mšžœ
˜—Mšžœžœ
žœ˜>Mš
œί
™ί
šžœž˜Mš
œ2˜2šžœ3ž˜=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šœžœ˜*Mšžœžœ
ž	œ Πck	 ‘ ^˜¨
Mš
œ˜—šŸœžœ
žœ
žœ#˜EM˜Mšœžœ
˜Mš
œ%˜%Mšœžœ
˜Mšžœžœ
žœ˜4šžœ˜Mšœžœ" C˜wMšœžœ* F˜ˆ
Mš
œ˜Mš
œ˜—Mš
œ˜—šŸœžœ
žœ
žœ#˜Hšžœžœ
ž˜Mš
œC˜C—Mšœžœ
˜Mšœžœ
˜Mš
œ˜—š
Ÿœžœ
žœ
žœžœ˜PMš
œ˜Mšœžœ
˜Mšžœ	ž˜Mšžœ@˜DMšžœžœžœ'˜JMš
œ˜—šŸœžœ
žœ
žœ#˜JMšžœžœ
žœ˜>Mš
œ˜—Mš	œžœ
žœ
žœžœ
˜1Mš	œžœ
žœ
žœžœ
˜,Mšœžœ
žœžœ
˜)—š
œ™šŸœžœ žœžœ˜OMšœIžœžœ™|Mš
œ˜Mšœžœ
žœ
žœ+˜?Mšžœžœ
žœžœ˜%M˜Mš
œ8˜8šžœ'˜)šžœ˜Mš
œ™šžœž˜$Mš
œ<™<Mš
œ!˜!M˜Mšžœžœ
žœžœ˜%Mš
œ8˜8Mšžœ
˜—Mš
œ!˜!Mš
œ
˜
—šžœ
˜Mš
œ=™=Mš
œ2˜2Mš
œ!˜!Mš
œ7˜7Mš
œ˜——Mšžœžœ˜Mš
œ˜—š
Ÿœžœ
žœžœžœ˜UMš
œa™aM˜Mšœžœ
˜šžœ
ž˜Mšžœ*˜.šžœ˜Mšœžœ.˜?Mš
œ,˜,Mš
œ˜——Mš
œ˜—šŸœžœ
žœ+žœ˜PMš
œ™Mšžœžœ
žœ ˜<Mš
œ˜—Mšœžœ˜Mšœ)žœ˜2Mšœžœ˜$Mšœ!žœ˜*Mš
œ˜M˜—™)Lš
œ;™;LšœΟr™—L™—…—Lτmή