<> <> <> <<>> <> <<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.>> DIRECTORY BTree, BTreeInternal, Environment USING [wordsPerPage], Inline USING [BITSHIFT, LongCOPY], SafeStorage USING [NewZone]; BTreeRead: MONITOR LOCKS tree USING tree: Tree IMPORTS BTreeInternal, Inline, SafeStorage EXPORTS BTree, BTreeInternal = BEGIN OPEN BTree, BTreeInternal; <<>> <> Tree: TYPE = REF TreeObject; TreeObject: PUBLIC TYPE = BTreeInternal.TreeObject; PathStk: TYPE = REF PathStkObject; PathStkObject: PUBLIC TYPE = BTreeInternal.PathStkObject; Open: PUBLIC SAFE PROCEDURE [repPrim: RepresentationPrimitives, storage: PageStorage, storPrim: PageStoragePrimitives, pageSize: PageSize _ Environment.wordsPerPage, minEntrySize: CARDINAL _ 1, initialize: BOOLEAN _ FALSE, maintainRecomputableState: BOOLEAN _ TRUE] RETURNS [tree: Tree] = TRUSTED BEGIN tree _ staticZone.NEW [TreeObject _ [state: [pageSize: pageSize], storage: storage, repPrim: repPrim, minEntrySize: minEntrySize, storPrim: storPrim, maintainRecomputableState: maintainRecomputableState]]; tree.maxFreeWords _ pageSize-pageOverhead; tree.maxRecordsPerPage _ tree.maxFreeWords/(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.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. tree.Lock[IF initialize THEN update ELSE read]; BEGIN ENABLE UNWIND => tree.Unlock[]; IF initialize THEN BEGIN statePtr: LONG POINTER TO TreeState _ tree.ReferencePage[statePage, new]; LongZero[statePtr, pageSize]; IF ~maintainRecomputableState THEN tree.state.entryCount _ LAST[LONG CARDINAL]; statePtr^ _ tree.state; tree.ReleasePage[statePage, endOfUpdate]; END ELSE BEGIN 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; END; tree.state.updateInProgress _ FALSE; END; tree.Unlock[]; END; ReOpen: PUBLIC SAFE PROCEDURE [tree: Tree] = TRUSTED BEGIN tree.Lock[update]; BEGIN ENABLE UNWIND => tree.Unlock[]; statePtr: LONG POINTER TO TreeState _ tree.ReferencePage[statePage, read]; tree.state _ statePtr^; tree.ReleasePage[statePage]; tree.version _ tree.version+1; -- this invalidates any extant PathStks END; tree.Unlock[]; END; Validate: PUBLIC SAFE PROCEDURE [tree: Tree] = TRUSTED BEGIN CheckPair: PROCEDURE [entry: Entry] RETURNS [continue: BOOLEAN] = BEGIN 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]; Inline.LongCOPY[to: prevEntry, from: entry, nwords: size]; RETURN [TRUE]; END; -- CheckPair PrevRecord: TYPE = RECORD [entry: SEQUENCE maxLength: [0..LAST[PageSize]] OF WORD]; prevRecord: REF PrevRecord = tempZone.NEW[PrevRecord[tree.state.pageSize-reservedWordsPerPage]]; prevEntry: Entry = BASE[DESCRIPTOR[prevRecord.entry]]; entryCount: LONG CARDINAL _ 0; firstEntry: BOOLEAN _ TRUE; [] _ EnumerateEntries[tree: tree, key: NIL, Proc: CheckPair]; IF tree.maintainRecomputableState AND entryCount#tree.state.entryCount THEN BEGIN tree.Lock[update]; tree.state.entryCount _ entryCount; tree.WriteStatePage[endOfUpdate]; tree.Unlock[]; END; END; GetState: PUBLIC SAFE PROCEDURE [tree: Tree] RETURNS [entryCount: LONG CARDINAL, greatestPage: PageNumber, depth: CARDINAL, storage: PageStorage] = CHECKED { RETURN [entryCount: tree.state.entryCount, greatestPage: tree.state.greatestPage, depth: tree.state.depth, storage: tree.storage] }; ReadRecord: PUBLIC SAFE PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [record: Record] = TRUSTED BEGIN EntryProc: PROCEDURE [entry: Entry] = { record _ IF entry#NIL THEN tree.NewRecordFromEntry[entry] ELSE NIL }; ReadEntry[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc]; END; ReadRecordL: PUBLIC SAFE PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [record: Record] = TRUSTED BEGIN EntryProc: PROCEDURE [entry: Entry] = { record _ IF entry#NIL THEN tree.NewRecordFromEntry[entry] ELSE NIL }; ReadEntryL[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc]; END; ReadRecordLE: PUBLIC SAFE PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [record: Record] = TRUSTED BEGIN EntryProc: PROCEDURE [entry: Entry] = { record _ IF entry#NIL THEN tree.NewRecordFromEntry[entry] ELSE NIL }; ReadEntryLE[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc]; END; ReadRecordGE: PUBLIC SAFE PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [record: Record] = TRUSTED BEGIN EntryProc: PROCEDURE [entry: Entry] = { record _ IF entry#NIL THEN tree.NewRecordFromEntry[entry] ELSE NIL }; ReadEntryGE[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc]; END; ReadRecordG: PUBLIC SAFE PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [record: Record] = TRUSTED BEGIN EntryProc: PROCEDURE [entry: Entry] = { record _ IF entry#NIL THEN tree.NewRecordFromEntry[entry] ELSE NIL }; ReadEntryG[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc]; END; EnumerateRecords: PUBLIC SAFE PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: PROCEDURE [record: Record] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN] = TRUSTED BEGIN EntryProc: PROCEDURE [entry: Entry] RETURNS [continue: BOOLEAN] = { RETURN [Proc[tree.NewRecordFromEntry[entry]]] }; exhausted _ EnumerateEntries[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc]; END; ReadEntry: PUBLIC PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: UNSAFE PROCEDURE [entry: Entry]] = BEGIN CallIfEqual: PROCEDURE [entry: Entry] = BEGIN IF key#NIL AND entry#NIL AND tree.Compare[key, entry] = equal THEN Proc[entry] ELSE Proc[NIL]; END; ReadEntryLE[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: CallIfEqual]; END; ReadEntryL: PUBLIC PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: UNSAFE PROCEDURE [entry: Entry]] = BEGIN pathStkWasNil: BOOLEAN _ pathStk=NIL; tree.Lock[read]; IF pathStkWasNil THEN BEGIN IF useExistingPath THEN ERROR Error[nilPathStk]; pathStk _ tree.GetDefaultPathStk[]; END; <> BEGIN ENABLE UNWIND => { IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[] }; pagePtr: BTreePagePtr; pse: LONG POINTER TO PathStkEntry; [] _ tree.PathEntryLE[key: key, pathStk: pathStk, useExistingPath: useExistingPath]; BEGIN -- More extra nesting so the EXITS are in the scope of the ENABLE IF pathStk.top=0 THEN GOTO nil; [ptr: pagePtr, pse: pse] _ tree.ReferenceStack[pathStk]; IF tree.Compare[key, @pagePtr[pse.lastOffset].entry]#greater THEN BEGIN -- need to back up to previous entry tree.BackUpOneEntry[pse]; IF pagePtr[pse.lastOffset].grPage=nilPage THEN BEGIN -- this is a leaf page WHILE pse.lastOffset tree.ReleasePage[pse.pageNumber]]; tree.ReleasePage[pse.pageNumber]; EXITS nil => Proc[NIL]; END; END; IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[]; END; ReadEntryLE: PUBLIC PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: UNSAFE PROCEDURE [entry: Entry]] = BEGIN pathStkWasNil: BOOLEAN _ pathStk=NIL; tree.Lock[read]; IF pathStkWasNil THEN BEGIN IF useExistingPath THEN ERROR Error[nilPathStk]; pathStk _ tree.GetDefaultPathStk[]; END; <> BEGIN ENABLE UNWIND => { IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[] }; [] _ tree.PathEntryLE[key: key, pathStk: pathStk, useExistingPath: useExistingPath]; IF pathStk.top=0 THEN Proc[NIL] ELSE BEGIN 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]; END; END; IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[]; END; ReadEntryGE: PUBLIC PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: UNSAFE PROCEDURE [entry: Entry]] = BEGIN CallWhenGE: PROCEDURE [entry: Entry] RETURNS [continue: BOOLEAN] = BEGIN IF key=NIL OR tree.Compare[key, entry] <= equal THEN { Proc[entry]; RETURN [FALSE] } ELSE RETURN [TRUE]; END; exhausted: BOOLEAN _ EnumerateEntries[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: CallWhenGE]; IF exhausted THEN Proc[NIL]; END; ReadEntryG: PUBLIC PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: UNSAFE PROCEDURE [entry: Entry]] = BEGIN CallWhenG: PROCEDURE [entry: Entry] RETURNS [continue: BOOLEAN] = BEGIN IF key=NIL OR tree.Compare[key, entry] = less THEN { Proc[entry]; RETURN [FALSE] } ELSE RETURN [TRUE]; END; exhausted: BOOLEAN _ EnumerateEntries[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: CallWhenG]; IF exhausted THEN Proc[NIL]; END; EnumerateEntries: PUBLIC PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: UNSAFE PROCEDURE [entry: Entry] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN] = BEGIN pathStkWasNil: BOOLEAN _ pathStk=NIL; tree.Lock[read]; IF pathStkWasNil THEN BEGIN IF useExistingPath THEN ERROR Error[nilPathStk]; pathStk _ tree.GetDefaultPathStk[]; END; <> BEGIN ENABLE UNWIND => { IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[] }; leafStkTop: PathStkIndex; pse: LONG POINTER TO PathStkEntry; pagePtr: BTreePagePtr _ NIL; leafStkTop _ tree.PathEntryLE[key: key, pathStk: pathStk, useExistingPath: useExistingPath]; IF pathStk.top=0 THEN BEGIN -- key is less than any existing entry in the tree. Set PathStk to first record in leftmost leaf page. IF leafStkTop=0 THEN GOTO exhausted; -- empty tree pathStk.top _ leafStkTop; pathStk.path[leafStkTop].lastOffset _ entry1Offset; END; exhausted _ FALSE; pse _ @pathStk.path[pathStk.top]; DO offset: PageOffset _ pse.lastOffset; endOffset: PageOffset; IF pagePtr=NIL THEN BEGIN pagePtr _ tree.ReferencePage[pse.pageNumber]; endOffset _ nilOffset+(tree.state.pageSize-pagePtr.freeWords); END; IF offset>=endOffset THEN BEGIN -- ran off end of page. Pop up a level and do the next entry in the father page tree.ReleasePage[pse.pageNumber]; IF offset>endOffset THEN ERROR Error[entrySizesWrong]; pagePtr _ NIL; IF (pathStk.top _ pathStk.top-1) = 0 THEN BEGIN -- ran off end of tree. PathStk is no longer valid. pathStk.version _ LAST[LONG CARDINAL]; GOTO exhausted; END; pse _ pse - SIZE[PathStkEntry]; END ELSE BEGIN -- enumerate this entry nxtPgNo: PageNumber _ pagePtr[offset].grPage; pse.offset _ offset + tree.BTreeEntrySize[@pagePtr[offset]]; 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; END; pse.nextToLastOffset _ pse.lastOffset; pse.lastOffset _ pse.offset; ENDLOOP; IF pagePtr#NIL THEN tree.ReleasePage[pse.pageNumber]; EXITS exhausted => exhausted _ TRUE; END; IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[]; END; NewPathStk: PUBLIC SAFE PROCEDURE RETURNS [pathStk: PathStk] = CHECKED BEGIN pathStk _ staticZone.NEW[PathStkObject]; pathStk.version _ LAST[LONG CARDINAL]; -- not valid END; <<>> <<>> <> PathEntryLE: PUBLIC PROCEDURE [tree: Tree, key: Key, pathStk: PathStk, useExistingPath: BOOLEAN _ FALSE] RETURNS [depth: PathStkIndex] = BEGIN BinSearchPage: PROCEDURE RETURNS [firstG: EntryOrdinal] = <> BEGIN firstBadOffset: PageOffset = nilOffset + (tree.state.pageSize - pagePtr.freeWords); midOffset: PageOffset _ Inline.BITSHIFT[firstBadOffset, -1]; curOffset: PageOffset _ entry1Offset; l, r: EntryOrdinal _ 2; <> IF key#NIL THEN DO IF curOffset>=midOffset THEN BEGIN IF curOffset>=firstBadOffset OR tree.Compare[key, @pagePtr[curOffset].entry] = less THEN EXIT; midOffset _ firstBadOffset; l _ r; END; curOffset _ curOffset + tree.BTreeEntrySize[@pagePtr[curOffset]]; r _ r+1; offsetTable[r] _ curOffset; ENDLOOP; IF curOffset>firstBadOffset THEN ERROR Error[entrySizesWrong]; <> WHILE l r _ m; equal => RETURN [m+1]; greater => l _ m+1; ENDCASE; ENDLOOP; RETURN [r]; END; -- BinSearchPage pse: LONG POINTER TO PathStkEntry; offsetTable: OffsetTable; curPage: PageNumber; pagePtr: BTreePagePtr; IF useExistingPath AND pathStk.treeID=tree.id AND pathStk.version=tree.version THEN BEGIN -- supplied PathStk is still valid. See if it is for the correct key. 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 => NULL; -- correct key greater => BEGIN 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 END; ENDCASE; tree.ReleasePage[pse.pageNumber]; IF useExistingPath THEN RETURN; EXITS dontUse => NULL; END; <> 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]; END; ReferenceStack: PUBLIC PROCEDURE [tree: Tree, pathStk: PathStk, type: ReferenceType _ read] RETURNS [pse: LONG POINTER TO PathStkEntry, ptr: PagePtr] = BEGIN pse _ @pathStk.path[pathStk.top]; ptr _ tree.ReferencePage[pse.pageNumber, type]; END; BackUpOneEntry: PUBLIC PROCEDURE [tree: Tree, pse: LONG POINTER TO PathStkEntry] = BEGIN tree.RepairOffsets[pse]; pse.offset _ pse.lastOffset; tree.RepairOffsets[pse]; END; RepairOffsets: PUBLIC PROCEDURE [tree: Tree, pse: LONG POINTER TO PathStkEntry] = BEGIN CheckProgression: PROCEDURE [offset1, offset2: PageOffset] RETURNS [ok: BOOLEAN] = BEGIN RETURN [SELECT TRUE FROM offset2=entry0Offset => offset1=nilOffset, offset2=entry1Offset => offset1=entry0Offset, offset1>=offset2 => FALSE, ENDCASE => offset1+tree.BTreeEntrySize[@pagePtr[offset1]] = offset2]; END; -- CheckProgression pagePtr: BTreePagePtr = tree.ReferencePage[pse.pageNumber]; IF ~(CheckProgression[pse.lastOffset, pse.offset] AND CheckProgression[pse.nextToLastOffset, pse.lastOffset]) THEN BEGIN 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; END; tree.ReleasePage[pse.pageNumber]; END; PathToMaxDescendant: PUBLIC PROCEDURE [tree: Tree, pathStk: PathStk, page: PageNumber] = BEGIN 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; END; WriteStatePage: PUBLIC PROCEDURE [tree: Tree, update: UpdateState _ unchanged] = BEGIN statePtr: LONG POINTER TO TreeState = tree.ReferencePage[statePage, write]; statePtr^ _ tree.state; tree.ReleasePage[statePage, update]; END; Lock: PUBLIC ENTRY PROCEDURE [tree: Tree, mode: LockMode] = BEGIN SELECT mode FROM read => BEGIN WHILE tree.lockCount<0 DO WAIT tree.unlocked; ENDLOOP; tree.lockCount _ tree.lockCount+1; END; update => BEGIN WHILE tree.lockCount#0 DO WAIT tree.unlocked; ENDLOOP; tree.lockCount _ -1; END; ENDCASE; END; Unlock: PUBLIC ENTRY PROCEDURE [tree: Tree] = BEGIN 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. END; GetHeapAndTable: PUBLIC ENTRY PROCEDURE [tree: Tree, pathStk: PathStk] = BEGIN pathStk.heap _ tree.heap; tree.heap _ NIL; pathStk.entryTable _ tree.entryTable; tree.entryTable _ NIL; IF pathStk.heap#NIL THEN heapsReused _ heapsReused+1 ELSE BEGIN pathStk.heap _ staticZone.NEW[Heap[tree.maxRecordsPerPage+1]]; -- heap holds at most one page's worth of entries at any given time pathStk.entryTable _ staticZone.NEW[EntryTable[3*tree.maxRecordsPerPage+1]]; -- may have to index scroll containing up to 3 pages' worth of entries heapsCreated _ heapsCreated+1; END; END; ReturnHeapAndTable: PUBLIC ENTRY PROCEDURE [tree: Tree, pathStk: PathStk] = BEGIN IF tree.heap=NIL THEN { tree.heap _ pathStk.heap; tree.entryTable _ pathStk.entryTable }; pathStk.heap _ NIL; pathStk.entryTable _ NIL; END; GetDefaultPathStk: PUBLIC ENTRY PROCEDURE [tree: Tree] RETURNS [pathStk: PathStk] = BEGIN pathStk _ tree.defaultPathStk; tree.defaultPathStk _ NIL; IF pathStk=NIL THEN { pathStk _ NewPathStk[]; pathStksCreated _ pathStksCreated+1 } ELSE { pathStk.version _ LAST [LONG CARDINAL]; pathStksReused _ pathStksReused+1 }; END; ReturnDefaultPathStk: PUBLIC ENTRY PROCEDURE [tree: Tree, pathStk: PathStk] = { IF tree.defaultPathStk=NIL THEN tree.defaultPathStk _ pathStk }; Error: PUBLIC SAFE ERROR [reason: Reason] = CODE; UpdateInProgress: PUBLIC SAFE SIGNAL = CODE; staticZone: PUBLIC ZONE = SafeStorage.NewZone[sr: prefixed]; tempZone: PUBLIC ZONE = SafeStorage.NewZone[sr: prefixed]; Bug: PUBLIC ERROR [type: BugType] = CODE; <<>> <<>> <> GetOffsetTable: ENTRY PROCEDURE [tree: Tree] RETURNS [offsetTable: OffsetTable] = <> BEGIN offsetTable _ tree.offsetTable; tree.offsetTable _ NIL; IF offsetTable#NIL THEN offsetTablesReused _ offsetTablesReused+1 ELSE BEGIN offsetTable _ staticZone.NEW[OffsetTableObject[tree.maxRecordsPerPage+2]]; offsetTablesCreated _ offsetTablesCreated+1; END; END; ReturnOffsetTable: ENTRY PROCEDURE [tree: Tree, offsetTable: OffsetTable] = <> { IF tree.offsetTable=NIL THEN tree.offsetTable _ offsetTable }; treeID: CARDINAL _ 0; offsetTablesReused, offsetTablesCreated: LONG CARDINAL _ 0; heapsReused, heapsCreated: LONG CARDINAL _ 0; pathStksReused, pathStksCreated: LONG CARDINAL _ 0; END.