<<>> <> <> <> <> <> <> <> DIRECTORY Basics USING [MoveWords], BTree USING [Compare, EachEntryProc, Entry, EntryFromRecord, EntrySize, EntSize, Error, Key, PageNumber, Record, ReferencePage, ReleasePage, UpdateState, UpdateType], BTreeInternal USING [AdjustTreeState, AllocatePage, AssignRefESR, BackUpAndRemoveEntry, BackUpOneEntry, BTreeEntry, BTreeEntrySize, BTreePagePtr, Bug, Compare, entry0Offset, entry1Offset, <> EntryFromRecord, EntryOrdinal, entryOverhead, EntrySize, EntryTable, EntryTableRec, EntSeqRecord, FreePage, freePageMarker, GetDefaultPathStk, GetHeapAndTable, Heap, HeapIndex, InsertRecords, Lock, maxLevelsInTree, nilOffset, nilPage, pageOverhead, PathEntryLE, PathStk, PathStkEntry, PathStkIndex, PathStkObject, PathToMaxDescendant, ReferencePage, ReferenceStack, ReleasePage, RemoveEntry, RepairOffsets, ReturnDefaultPathStk, ReturnHeapAndTable, Tree, TreeObject, Unlock, WriteStatePage]; <> <> <> <> BTreeWrite: PROGRAM IMPORTS Basics, BTree, BTreeInternal <<,IO, Rope, Convert, SimpleStreams>> EXPORTS BTree, BTreeInternal = { OPEN BTree, BTreeInternal; <> <> <> Tree: TYPE = REF TreeObject; TreeObject: PUBLIC TYPE = BTreeInternal.TreeObject; PathStk: TYPE = REF PathStkObject; PathStkObject: PUBLIC TYPE = BTreeInternal.PathStkObject; PathStkEntryPtr: TYPE = POINTER TO PathStkEntry; BTreeEntryPtr: TYPE = POINTER TO BTreeEntry; silly: REF ¬ NEW[TreeObject]; DeleteKey: PUBLIC SAFE PROC [tree: Tree, key: Key, pathStk: PathStk ¬ NIL, useExistingPath: BOOL ¬ FALSE] RETURNS [found: BOOL] = TRUSTED { FatherMayNeedWork: PROC RETURNS [needsWork: BOOL] = { <> pagePtr, otherPtr: BTreePagePtr; fatherPSE: PathStkEntryPtr; fatherFreeWords: CARD; pse ¬ @pathStk.path[pathStk.top]; IF pse.eslFront=NIL THEN needsWork ¬ FALSE ELSE { tree.InsertRecords[pathStk]; needsWork ¬ pathStk.top#0 AND pathStk.path[pathStk.top-1].eslFront#NIL; }; pagePtr ¬ tree.ReferencePage[pse.pageNumber]; IF pathStk.top=1 AND pagePtr.freeBytes=tree.maxFreeBytes THEN { <> tree.state.rootPage ¬ pagePtr.minPage; tree.state.depth ¬ tree.state.depth-1; tree.ReleasePage[pse.pageNumber]; tree.FreePage[pse.pageNumber]; RETURN [FALSE]; }; IF pathStk.top=1 OR tree.maxFreeBytes-pagePtr.freeBytes >= tree.prettyFull THEN { tree.ReleasePage[pse.pageNumber]; RETURN; }; <> AppendEntSeqRecord[ pse: pse, esr: MakeEntSeqRecord[ entSeq: FirstEntry[pagePtr], length: tree.maxFreeBytes-pagePtr.freeBytes]]; fatherPSE ¬ @pathStk.path[pathStk.top-1]; otherPtr ¬ tree.ReferencePage[fatherPSE.pageNumber]; fatherFreeWords ¬ otherPtr.freeBytes; tree.ReleasePage[fatherPSE.pageNumber]; IF fatherPSE.offset < nilOffset+(tree.state.pageSize-fatherFreeWords) OR fatherPSE.eslFront#NIL THEN { <> rtBroPg: PageNumber; esr: REF EntSeqRecord; [esr: esr, grPage: rtBroPg] ¬ tree.RemoveEntry[fatherPSE]; AppendEntSeqRecord[pse: pse, esr: esr]; otherPtr ¬ tree.ReferencePage[fatherPSE.pageNumber, write]; IF otherPtr[fatherPSE.lastOffset].grPage # pse.pageNumber THEN ERROR Bug[mcCreightWasWrong]; otherPtr[fatherPSE.lastOffset].grPage ¬ rtBroPg; tree.ReleasePage[fatherPSE.pageNumber]; otherPtr ¬ tree.ReferencePage[rtBroPg, write]; otherPtr.minPage ¬ pagePtr.minPage; tree.ReleasePage[rtBroPg]; tree.ReleasePage[pse.pageNumber]; tree.FreePage[pse.pageNumber]; pse.pageNumber ¬ rtBroPg; pse.offset ¬ entry1Offset; pse.lastOffset ¬ entry0Offset; pse.nextToLastOffset ¬ nilOffset; } ELSE { <> esr: REF EntSeqRecord; tree.ReleasePage[pse.pageNumber]; [esr: esr] ¬ tree.BackUpAndRemoveEntry[fatherPSE]; PushEntSeqRecord[pse: pse, esr: esr]; tree.FreePage[pse.pageNumber]; otherPtr ¬ tree.ReferencePage[fatherPSE.pageNumber]; pse.pageNumber ¬ otherPtr[fatherPSE.lastOffset].grPage; tree.ReleasePage[fatherPSE.pageNumber]; pagePtr ¬ tree.ReferencePage[pse.pageNumber]; pse.offset ¬ nilOffset+(tree.state.pageSize-pagePtr.freeBytes); pse.lastOffset ¬ entry1Offset; pse.nextToLastOffset ¬ entry0Offset; tree.ReleasePage[pse.pageNumber]; tree.RepairOffsets[pse]; }; IF pse.eslFront#NIL THEN tree.InsertRecords[pathStk]; RETURN [TRUE]; }; pathStkWasNil: BOOL ¬ pathStk=NIL; pse: PathStkEntryPtr; tree.Lock[update]; IF pathStkWasNil THEN { IF useExistingPath THEN ERROR Error[nilPathStk]; pathStk ¬ tree.GetDefaultPathStk[]; }; { <> ENABLE UNWIND => { IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[]; }; origStkTop: PathStkIndex; pagePtr: BTreePagePtr ¬ NIL; descendantPg: PageNumber; simpleDelete: BOOL ¬ FALSE; <> equal: BOOL ¬ tree.PathEntryLE[key: key, pathStk: pathStk, useExistingPath: useExistingPath].equal; IF ~equal THEN { IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[]; RETURN [FALSE]; }; origStkTop ¬ pathStk.top; [ptr: pagePtr, pse: pse] ¬ tree.ReferenceStack[pathStk]; descendantPg ¬ pagePtr[pse.nextToLastOffset].grPage; IF descendantPg = nilPage THEN { bteSize: CARD ¬ tree.BTreeEntrySize[@pagePtr[pse.lastOffset]]; IF tree.maxFreeBytes - (pagePtr.freeBytes + bteSize) >= tree.prettyFull THEN simpleDelete ¬ TRUE; }; tree.ReleasePage[pse.pageNumber]; tree.version ¬ tree.version+1; <> <> tree.BackUpOneEntry[pse]; -- pse.offset should index deletion victim IF simpleDelete THEN { tree.AdjustTreeState[update: unchanged, deltaEntryCount: -1]; pagePtr ¬ tree.ReferencePage[pse.pageNumber, write]; [] ¬ tree.RemoveEntry[pse]; tree.ReleasePage[pse.pageNumber, IF tree.longUpdate THEN unchanged ELSE endOfUpdate]; } ELSE { tree.AdjustTreeState[update: startOfUpdate, deltaEntryCount: -1]; <> tree.PathToMaxDescendant[pathStk: pathStk, page: descendantPg]; IF pathStk.top > origStkTop THEN { dpse: PathStkEntryPtr = @pathStk.path[pathStk.top]; leafESR: REF EntSeqRecord ¬ tree.BackUpAndRemoveEntry[dpse].esr; [grPage: leafESR.entSeqP.grPage] ¬ tree.RemoveEntry[pse]; <> AppendEntSeqRecord[pse: pse, esr: leafESR]; } ELSE [] ¬ tree.RemoveEntry[pse]; tree.GetHeapAndTable[pathStk]; DO needsWork: BOOL ¬ FatherMayNeedWork[ ! UNWIND => tree.ReturnHeapAndTable[pathStk]]; IF pathStk.top=0 OR (~needsWork AND pathStk.top<=origStkTop) THEN EXIT ELSE pathStk.top ¬ pathStk.top-1; ENDLOOP; pathStk.top ¬ 0; tree.ReturnHeapAndTable[pathStk]; tree.AdjustTreeState[update: endOfUpdate, deltaEntryCount: 0]; }; }; IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[]; RETURN [TRUE]; }; UpdateRecord: PUBLIC SAFE PROC [tree: Tree, key: Key, pathStk: PathStk ¬ NIL, useExistingPath: BOOL ¬ FALSE, record: Record, updateType: UpdateType ¬ insertOrReplace] = TRUSTED { ProduceEntry: EachEntryProc = { Basics.MoveWords[dst: entry, src: tree.EntryFromRecord[record], count: BytesToWords[bytes]]; }; bytes: EntSize = tree.EntrySize[tree.EntryFromRecord[record]]; UpdateEntry[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, bytes: bytes, Proc: ProduceEntry, updateType: updateType]; }; UpdateEntry: PUBLIC PROC [tree: Tree, key: Key, pathStk: PathStk ¬ NIL, useExistingPath: BOOL ¬ FALSE, bytes: EntSize, Proc: EachEntryProc, updateType: UpdateType ¬ insertOrReplace] = { CallEntryProc: EachEntryProc = { Proc[entry]; IF tree.EntrySize[entry]#bytes OR tree.Compare[key, entry]#equal THEN ERROR Error[wrongEntryProduced]; }; pathStkWasNil: BOOL ¬ pathStk=NIL; tree.Lock[update]; IF pathStkWasNil THEN { IF useExistingPath THEN ERROR Error[nilPathStk]; pathStk ¬ tree.GetDefaultPathStk[]; }; <> { ENABLE UNWIND => { IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[]; }; leafStkTop: PathStkIndex; equal: BOOL; pse: PathStkEntryPtr; pagePtr: BTreePagePtr ¬ NIL; foundEntSize: CARD ¬ 0; -- zero means there is not an existing entry with this key IF CARD[bytes+entryOverhead] NOT IN [1+entryOverhead..tree.maxFreeBytes] THEN ERROR Error[entrySizesWrong]; [equal: equal, depth: leafStkTop] ¬ tree.PathEntryLE[key: key, pathStk: pathStk, useExistingPath: useExistingPath]; IF equal THEN { IF updateType=insert THEN ERROR Error[wrongUpdateType]; [pse: pse, ptr: pagePtr] ¬ tree.ReferenceStack[pathStk]; foundEntSize ¬ tree.EntrySize[@pagePtr[pse.lastOffset].entry]; tree.ReleasePage[pse.pageNumber]; } ELSE IF updateType=replace THEN ERROR Error[wrongUpdateType]; <> <<1. If replacing an existing entry of the same size, just overwrite it.>> <<2. If the new entry fits on the page (after removing the old entry if any), just slide up the entries beyond the insertion point and insert the new entry.>> <<3. Otherwise, leave the new entry as an EntSeqRecord at the appropriate stack level, and let InsertRecords cope with the problem.>> <> tree.version ¬ tree.version+1; -- invalidate existing PathStks that refer to this tree pse ¬ @pathStk.path[pathStk.top]; IF bytes=foundEntSize THEN { <> tree.AdjustTreeState[update: unchanged, deltaEntryCount: 0]; pagePtr ¬ tree.ReferencePage[pse.pageNumber, write]; CallEntryProc[@pagePtr[pse.lastOffset].entry]; tree.ReleasePage[pse.pageNumber, IF tree.longUpdate THEN unchanged ELSE endOfUpdate]; } ELSE { removedEntGrPage: PageNumber ¬ nilPage; newEntryFits: BOOL ¬ FALSE; IF foundEntSize=0 THEN { <> pathStk.top ¬ leafStkTop; pse ¬ @pathStk.path[pathStk.top]; }; <> IF pathStk.top>0 THEN { delta: CARD ¬ 0; IF foundEntSize # 0 THEN delta ¬ foundEntSize+entryOverhead; pagePtr ¬ tree.ReferencePage[pse.pageNumber]; newEntryFits ¬ (bytes+entryOverhead) <= (pagePtr.freeBytes+delta); tree.ReleasePage[pse.pageNumber]; }; tree.AdjustTreeState[update: IF newEntryFits THEN unchanged ELSE startOfUpdate, deltaEntryCount: IF foundEntSize=0 THEN 1 ELSE 0]; IF pathStk.top>0 THEN pagePtr ¬ tree.ReferencePage[pse.pageNumber, write]; IF foundEntSize#0 THEN <> [grPage: removedEntGrPage] ¬ tree.BackUpAndRemoveEntry[pse]; IF newEntryFits THEN { <> <<>> entPtr: BTreeEntryPtr ¬ @pagePtr[pse.offset]; Basics.MoveWords[ dst: LOOPHOLE[entPtr+bytes+entryOverhead], src: LOOPHOLE[entPtr], count: BytesToWords[nilOffset+(tree.state.pageSize-pagePtr.freeBytes)-pse.offset]]; CallEntryProc[@entPtr.entry]; entPtr.grPage ¬ removedEntGrPage; pagePtr.freeBytes ¬ pagePtr.freeBytes - (bytes+entryOverhead); tree.ReleasePage[pse.pageNumber, IF tree.longUpdate THEN unchanged ELSE endOfUpdate]; } ELSE { <> esr: REF EntSeqRecord ¬ NEW[EntSeqRecord[(bytes+entryOverhead)/SIZE[BYTE]]]; esr.entSeqP ¬ LOOPHOLE[BASE[DESCRIPTOR[esr.entSeq]]]; esr.entSeqLen ¬ bytes+entryOverhead; CallEntryProc[@esr.entSeqP.entry]; esr.entSeqP.grPage ¬ removedEntGrPage; AppendEntSeqRecord[pse: pse, esr: esr]; IF pathStk.top>0 THEN tree.ReleasePage[pse.pageNumber]; tree.GetHeapAndTable[pathStk]; WHILE pathStk.path[pathStk.top].eslFront#NIL DO tree.InsertRecords[pathStk ! UNWIND => tree.ReturnHeapAndTable[pathStk]]; IF pathStk.top=0 THEN EXIT ELSE pathStk.top ¬ pathStk.top-1; ENDLOOP; tree.ReturnHeapAndTable[pathStk]; tree.AdjustTreeState[update: endOfUpdate, deltaEntryCount: 0]; }; }; }; IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[]; }; SetUpdateInProgress: PUBLIC SAFE PROC [tree: Tree, updateInProgress: BOOL] = TRUSTED { tree.Lock[update]; tree.longUpdate ¬ updateInProgress; tree.AdjustTreeState[ update: IF updateInProgress THEN startOfUpdate ELSE endOfUpdate, deltaEntryCount: 0]; tree.Unlock[]; }; <> AdjustTreeState: PUBLIC PROC [tree: Tree, update: UpdateState, deltaEntryCount: INT] = { IF tree.maintainRecomputableState THEN { <> IF tree.state.entryCount#LAST[CARD] THEN tree.state.entryCount ¬ tree.state.entryCount+LOOPHOLE[deltaEntryCount, CARD]; IF update#unchanged AND ~(tree.state.updateInProgress AND tree.longUpdate) THEN { tree.state.updateInProgress ¬ update=startOfUpdate OR tree.longUpdate; tree.WriteStatePage[update: update]; }; } ELSE IF deltaEntryCount#0 AND tree.state.entryCount#LAST[CARD] THEN { <> tree.state.entryCount ¬ LAST[CARD]; tree.WriteStatePage[]; }; }; InsertRecords: PUBLIC PROC [tree: Tree, pathStk: PathStk] = { pse: PathStkEntryPtr = @pathStk.path[pathStk.top]; IF pse.eslFront#NIL THEN { pathStk.entryTable.length ¬ 0; pathStk.entryTable.map[0].cumEntSize ¬ 0; FOR esr: REF EntSeqRecord ¬ pse.eslFront, esr.fwdP UNTIL esr=NIL DO AppendEntSeqLengths[tree: tree, pathStk: pathStk, esr: esr]; ENDLOOP; IF pathStk.top=0 THEN { <> bytesToInsert: CARD = EntryIntervalSize[pathStk: pathStk, leftFather: 0]; newRootPage: PageNumber = tree.AllocatePage[]; pagePtr: BTreePagePtr = tree.ReferencePage[newRootPage, write]; IF tree.state.depth >= maxLevelsInTree THEN ERROR Error[depthExceeded]; pagePtr.minPage ¬ pathStk.path[0].leastSon; tree.ReleasePage[newRootPage]; IF bytesToInsert > tree.maxFreeBytes THEN ERROR Bug[newRootOverflow]; WritePage[tree: tree, pse: @pathStk.path[0], number: newRootPage, words: bytesToInsert]; tree.state.rootPage ¬ newRootPage; tree.state.depth ¬ tree.state.depth+1; } ELSE { pagePtr: BTreePagePtr = tree.ReferencePage[pse.pageNumber, write]; tailBlkPtr: BTreeEntryPtr = @pagePtr[pse.offset]; tailBlkLen: CARD = (nilOffset+tree.state.pageSize-pagePtr.freeBytes)-pse.offset; bytesToInsert: CARD = EntryIntervalSize[pathStk: pathStk]; IF bytesToInsert<=pagePtr.freeBytes THEN { <> Basics.MoveWords[ dst: LOOPHOLE[tailBlkPtr+bytesToInsert], src: LOOPHOLE[tailBlkPtr], count: BytesToWords[nilOffset+(tree.state.pageSize-pagePtr.freeBytes)-pse.offset]]; DepositESL[tree: tree, pse: pse, block: tailBlkPtr, length: bytesToInsert]; pagePtr.freeBytes ¬ pagePtr.freeBytes-bytesToInsert; tree.ReleasePage[pse.pageNumber]; } ELSE { <> rtBroPg1: PageNumber; esr: REF EntSeqRecord ¬ MakeEntSeqRecord[@pagePtr[entry1Offset], pse.offset-entry1Offset]; PushEntSeqRecord[pse: pse, esr: esr]; PushEntSeqLengths[tree: tree, pathStk: pathStk, esr: esr]; esr ¬ MakeEntSeqRecord[tailBlkPtr, tailBlkLen]; AppendEntSeqRecord[pse: pse, esr: esr]; AppendEntSeqLengths[tree: tree, pathStk: pathStk, esr: esr]; tree.ReleasePage[pse.pageNumber]; rtBroPg1 ¬ ComplexInsertRecords[tree: tree, pathStk: pathStk]; IF rtBroPg1#nilPage THEN HairyInsertRecords[tree: tree, pathStk: pathStk, rtBroPg1: rtBroPg1]; }; }; IF pse.eslFront#NIL THEN ERROR Bug[entriesLeftOver]; }; }; MakeEntSeqRecord: PUBLIC PROC [entSeq: BTreeEntryPtr, length: CARD] RETURNS [esr: REF EntSeqRecord ¬ NIL] = { IF length # 0 THEN { esr ¬ NEW[EntSeqRecord[length/SIZE[BYTE]]]; esr.entSeqP ¬ LOOPHOLE[BASE[DESCRIPTOR[esr.entSeq]]]; esr.entSeqLen ¬ length; Basics.MoveWords[dst: LOOPHOLE[esr.entSeqP], src: LOOPHOLE[entSeq], count: length/SIZE[BYTE]]; }; }; AppendEntSeqRecord: PUBLIC PROC [pse: PathStkEntryPtr, esr: REF EntSeqRecord] = { IF esr # NIL THEN { esr.fwdP ¬ NIL; IF pse.eslRear=NIL THEN AssignRefESR[@pse.eslFront, esr] ELSE pse.eslRear.fwdP ¬ esr; AssignRefESR[@pse.eslRear, esr]; }; }; PushEntSeqRecord: PUBLIC PROC [pse: PathStkEntryPtr, esr: REF EntSeqRecord] = { IF esr # NIL THEN { esr.fwdP ¬ pse.eslFront; AssignRefESR[@pse.eslFront, esr]; IF pse.eslRear=NIL THEN AssignRefESR[@pse.eslRear, esr]; }; }; RemoveEntry: PUBLIC PROC [tree: Tree, pse: PathStkEntryPtr, ignoreESL: BOOL ¬ FALSE] RETURNS [esr: REF EntSeqRecord ¬ NIL, grPage: PageNumber] = { IF ignoreESL OR pse.eslFront=NIL THEN { <> pagePtr: BTreePagePtr = tree.ReferencePage[pse.pageNumber, write]; entSize: CARD = tree.BTreeEntrySize[@pagePtr[pse.offset]]; esr ¬ MakeEntSeqRecord[entSeq: @pagePtr[pse.offset], length: entSize]; pagePtr.freeBytes ¬ pagePtr.freeBytes+entSize; Basics.MoveWords[ dst: LOOPHOLE[@pagePtr[pse.offset]], src: LOOPHOLE[@pagePtr[pse.offset]+entSize], count: (nilOffset+(tree.state.pageSize-pagePtr.freeBytes)-pse.offset)/SIZE[BYTE]]; tree.ReleasePage[pse.pageNumber]; } ELSE { <> entSize: CARD = tree.BTreeEntrySize[pse.eslFront.entSeqP]; esr ¬ NEW[EntSeqRecord[entSize/SIZE[BYTE]]]; esr.entSeqP ¬ LOOPHOLE[BASE[DESCRIPTOR[esr.entSeq]]]; esr.entSeqLen ¬ entSize; DepositESL[tree: tree, pse: pse, block: esr.entSeqP, length: entSize]; }; grPage ¬ esr.entSeqP.grPage; esr.entSeqP.grPage ¬ nilPage; IF grPage # nilPage THEN { pagePtr: BTreePagePtr = tree.ReferencePage[grPage]; esr.entSeqP.grPage ¬ pagePtr.minPage; tree.ReleasePage[grPage]; }; }; BackUpAndRemoveEntry: PUBLIC PROC [tree: Tree, pse: PathStkEntryPtr] RETURNS [esr: REF EntSeqRecord, grPage: PageNumber] = { tree.BackUpOneEntry[pse]; [esr: esr, grPage: grPage] ¬ tree.RemoveEntry[pse: pse, ignoreESL: TRUE]; }; AllocatePage: PUBLIC SAFE PROC [tree: Tree] RETURNS [number: PageNumber] = TRUSTED { pagePtr: BTreePagePtr; IF tree.state.firstFreePage=nilPage THEN { number ¬ (tree.state.greatestPage ¬ tree.state.greatestPage+1); pagePtr ¬ tree.ReferencePage[number, new]; } ELSE { number ¬ tree.state.firstFreePage; pagePtr ¬ tree.ReferencePage[number, write]; IF pagePtr.freeBytes#freePageMarker THEN ERROR Bug[pageNotFree]; tree.state.firstFreePage ¬ pagePtr.minPage; }; pagePtr.freeBytes ¬ tree.maxFreeBytes; tree.ReleasePage[number]; }; FreePage: PUBLIC SAFE PROC [tree: Tree, number: PageNumber] = TRUSTED { pagePtr: BTreePagePtr = tree.ReferencePage[number, write]; IF pagePtr.freeBytes=freePageMarker THEN ERROR Bug[pageAlreadyFree]; pagePtr.freeBytes ¬ freePageMarker; pagePtr.minPage ¬ tree.state.firstFreePage; tree.state.firstFreePage ¬ number; tree.ReleasePage[number]; }; <> AppendEntSeqLengths: PROC [tree: Tree, pathStk: PathStk, esr: REF EntSeqRecord] = { <> IF esr#NIL THEN { entryTable: REF EntryTable ¬ pathStk.entryTable; index: EntryOrdinal ¬ entryTable.length; bytesLeft: CARD ¬ esr.entSeqLen; entry: BTreeEntryPtr ¬ esr.entSeqP; WHILE bytesLeft>0 DO entrySize: CARD = tree.BTreeEntrySize[entry]; index ¬ index+1; IF index >= entryTable.maxLength THEN ERROR Bug[tooManyEntriesInPage]; entryTable.map[index].cumEntSize ¬ entryTable.map[index-1].cumEntSize+entrySize; entry ¬ entry+entrySize; bytesLeft ¬ bytesLeft-entrySize; ENDLOOP; entryTable.length ¬ index; }; }; PushEntSeqLengths: PROC [tree: Tree, pathStk: PathStk, esr: REF EntSeqRecord] = { <> IF esr#NIL THEN { entryTable: REF EntryTable = pathStk.entryTable; oldLen: EntryOrdinal = entryTable.length; tempFirstOldIndex: EntryOrdinal = entryTable.maxLength-oldLen; newLen: EntryOrdinal; delta: CARD; <> Basics.MoveWords[ dst: LOOPHOLE[@entryTable.map[tempFirstOldIndex]], src: LOOPHOLE[@entryTable.map[1]], count: BytesToWords[oldLen*SIZE[EntryTableRec]]]; <> entryTable.length ¬ 0; AppendEntSeqLengths[tree: tree, pathStk: pathStk, esr: esr]; newLen ¬ entryTable.length; IF newLen >= tempFirstOldIndex THEN ERROR Bug[tooManyEntriesInPage]; entryTable.length ¬ newLen+oldLen; <> delta ¬ entryTable.map[newLen].cumEntSize; FOR i: EntryOrdinal IN [0..oldLen) DO entryTable.map[newLen+1+i].cumEntSize ¬ entryTable.map[tempFirstOldIndex+i].cumEntSize+delta; ENDLOOP; }; }; DepositESL: PROC [tree: Tree, pse: PathStkEntryPtr, block: BTreeEntryPtr, length: CARD] = { <> WHILE length#0 AND pse.eslFront#NIL DO esr: REF EntSeqRecord ¬ pse.eslFront; entSeqP: BTreeEntryPtr = esr.entSeqP; IF esr.entSeqLen <= length THEN { Basics.MoveWords[dst: LOOPHOLE[block], src: LOOPHOLE[entSeqP], count: BytesToWords[esr.entSeqLen]]; block ¬ block+esr.entSeqLen; length ¬ length-esr.entSeqLen; AssignRefESR[@pse.eslFront, esr.fwdP]; esr.fwdP ¬ NIL; } ELSE { firstEntSize: CARD = tree.BTreeEntrySize[entSeqP]; IF firstEntSize <= length THEN { Basics.MoveWords[dst: LOOPHOLE[block], src: LOOPHOLE[entSeqP], count: BytesToWords[firstEntSize]]; block ¬ block+firstEntSize; length ¬ length-firstEntSize; esr.entSeqP ¬ entSeqP+firstEntSize; esr.entSeqLen ¬ esr.entSeqLen-firstEntSize; } ELSE ERROR Bug[depositESL]; -- block would end in middle of entry }; ENDLOOP; IF length#0 THEN ERROR Bug[depositESL]; -- ESL exhausted IF pse.eslFront=NIL THEN AssignRefESR[@pse.eslRear, NIL]; }; EntryIntervalSize: PROC [pathStk: PathStk, leftFather, rightFather: EntryOrdinal ¬ 0] RETURNS [words: CARD] = { <> <<>> cumulativeSize: CARD; IF rightFather = 0 THEN rightFather ¬ pathStk.entryTable.length+1; cumulativeSize ¬ pathStk.entryTable.map[rightFather-1].cumEntSize - pathStk.entryTable.map[leftFather].cumEntSize; RETURN [cumulativeSize]; }; <> <> ComplexInsertRecords: PROC [tree: Tree, pathStk: PathStk] RETURNS [rtBroPg1: PageNumber] = { <> pse: PathStkEntryPtr = @pathStk.path[pathStk.top]; fatherPSE: PathStkEntryPtr = @pathStk.path[pathStk.top-1]; entryTable: REF EntryTable = pathStk.entryTable; oneBrotherEnough: BOOL ¬ FALSE; fatherIndex, bestFatherIndex: EntryOrdinal; bestFatherSize: CARD ¬ tree.maxFreeBytes+1; fatherPSE.leastSon ¬ pse.pageNumber; -- in case this is the root page splitting rtBroPg1 ¬ nilPage; IF pathStk.top>1 THEN { rtBroPg1 ¬ FindRightBrother[ tree: tree, pathStk: pathStk, spaceNeeded: -tree.maxFreeBytes]; IF rtBroPg1=nilPage THEN <> rtBroPg1 ¬ FindLeftBrother[ tree: tree, pathStk: pathStk, spaceNeeded: -tree.maxFreeBytes]; }; IF rtBroPg1=nilPage THEN rtBroPg1 ¬ tree.AllocatePage[]; <> IF entryTable.length<3 THEN ERROR Bug[tooFewEntries]; <> fatherIndex ¬ FillLeftPage[tree: tree, pathStk: pathStk]; <> DO pl0, pl1, fatherSize: CARD; pl1 ¬ EntryIntervalSize[pathStk: pathStk, leftFather: fatherIndex]; IF pl1 > tree.maxFreeBytes THEN EXIT; pl0 ¬ EntryIntervalSize[pathStk: pathStk, rightFather: fatherIndex]; IF pl0=0 OR pl0+pl1 > tree.maxFreeBytes+tree.awfullyFull THEN EXIT; <> fatherSize ¬ IndexedEntrySize[pathStk: pathStk, index: fatherIndex]; IF fatherSize> TrickleDown: PROC [emptyIndex: HeapIndex, entry: EntryOrdinal] = { sonSize: CARD = IndexedEntrySize[pathStk: pathStk, index: entry]; son: HeapIndex ¬ emptyIndex; DO father: HeapIndex ¬ son/2; fatherEnt: EntryOrdinal; IF LOOPHOLE[father, CARD] <= 0 THEN EXIT; <> <> <> fatherEnt ¬ heap.entries[father]; IF IndexedEntrySize[pathStk: pathStk, index: fatherEnt] <= sonSize THEN EXIT; heap.entries[son] ¬ fatherEnt; entryTable.map[fatherEnt].heapPos ¬ son; son ¬ father; ENDLOOP; heap.entries[son] ¬ entry; entryTable.map[entry].heapPos ¬ son; }; <> entryTable: REF EntryTable = pathStk.entryTable; heap: REF Heap = pathStk.heap; pse: PathStkEntryPtr = @pathStk.path[pathStk.top]; fatherPSE: PathStkEntryPtr = @pathStk.path[pathStk.top-1]; -- father's pse rtBroPg2: PageNumber; fatherIndex, fatherIndex2, bestFatherIndex, bestFatherIndex2: EntryOrdinal; minFeasIndex, maxFeasIndex: EntryOrdinal; bestFatherSizeSum: CARD ¬ 2*tree.maxFreeBytes + 1; twoBrothersEnough: BOOL ¬ FALSE; breakSize1, breakSize2, totalSize: CARD; fatherESR: REF EntSeqRecord; <> fatherIndex ¬ FillLeftPage[tree: tree, pathStk: pathStk]; fatherIndex2 ¬ FillLeftPage[tree: tree, pathStk: pathStk, leftFather: fatherIndex]; <> rtBroPg2 ¬ FindRightBrother[ tree: tree, pathStk: pathStk, spaceNeeded: EntryIntervalSize[ pathStk: pathStk, leftFather: fatherIndex2] + 2*tree.breathingSpace]; IF rtBroPg2=nilPage THEN { <> fe2: EntryOrdinal = FillRightPage[tree: tree, pathStk: pathStk]; fe: EntryOrdinal = FillRightPage[tree: tree, pathStk: pathStk, rightFather: fe2]; rtBroPg2 ¬ FindLeftBrother[tree: tree, pathStk: pathStk, spaceNeeded: EntryIntervalSize[pathStk: pathStk, leftFather: 0, rightFather: fe] + 2*tree.breathingSpace]; IF rtBroPg2=nilPage THEN rtBroPg2 ¬ tree.AllocatePage[] -- still no luck, allocate new page ELSE { <> fatherIndex ¬ FillLeftPage[tree: tree, pathStk: pathStk]; fatherIndex2 ¬ FillLeftPage[tree: tree, pathStk: pathStk, leftFather: fatherIndex]; }; }; IF entryTable.length < 5 THEN ERROR Bug[tooFewEntries]; <> <> heap.length ¬ 0; maxFeasIndex ¬ fatherIndex2; WHILE EntryIntervalSize[pathStk: pathStk, leftFather: maxFeasIndex] <= tree.fairlyFull DO maxFeasIndex ¬ maxFeasIndex-1; ENDLOOP; minFeasIndex ¬ maxFeasIndex+1; WHILE EntryIntervalSize[pathStk: pathStk, rightFather: fatherIndex] > (IF twoBrothersEnough THEN tree.prettyFull ELSE 0) DO WHILE EntryIntervalSize[ pathStk: pathStk, leftFather: fatherIndex, rightFather: minFeasIndex-1] > 0 AND EntryIntervalSize[pathStk: pathStk, leftFather: minFeasIndex-1] <= tree.maxFreeBytes DO minFeasIndex ¬ minFeasIndex-1; IF minFeasIndex <= maxFeasIndex THEN { <> heap.length ¬ heap.length+1; TrickleDown[emptyIndex: heap.length, entry: minFeasIndex]; }; ENDLOOP; WHILE EntryIntervalSize[pathStk: pathStk, leftFather: fatherIndex, rightFather: maxFeasIndex] > tree.maxFreeBytes DO IF maxFeasIndex >= minFeasIndex THEN { <> heapPos: HeapIndex = entryTable.map[maxFeasIndex].heapPos; heap.length ¬ heap.length-1; IF heapPos <= heap.length THEN { replacementEntry: EntryOrdinal = heap.entries[heap.length+1]; IF IndexedEntrySize[pathStk: pathStk, index: replacementEntry] <= IndexedEntrySize[pathStk: pathStk, index: maxFeasIndex] THEN TrickleDown[emptyIndex: heapPos, entry: replacementEntry] ELSE { <> emptyIndex: HeapIndex ¬ heapPos; entrySize: CARD = IndexedEntrySize[pathStk: pathStk, index: replacementEntry]; DO son: HeapIndex ¬ emptyIndex*2; sonEntry: EntryOrdinal; IF son > heap.length THEN EXIT; sonEntry ¬ heap.entries[son]; IF son < heap.length AND IndexedEntrySize[pathStk: pathStk, index: heap.entries[son+1]] < IndexedEntrySize[pathStk: pathStk, index: sonEntry] THEN { son ¬ son+1; sonEntry ¬ heap.entries[son]; }; IF IndexedEntrySize[pathStk: pathStk, index: sonEntry] >= entrySize THEN EXIT; heap.entries[emptyIndex] ¬ sonEntry; entryTable.map[sonEntry].heapPos ¬ emptyIndex; emptyIndex ¬ son; ENDLOOP; heap.entries[emptyIndex] ¬ replacementEntry; entryTable.map[replacementEntry].heapPos ¬ emptyIndex; }; }; }; maxFeasIndex ¬ maxFeasIndex-1; ENDLOOP; IF heap.length>0 THEN { fatherSizeSum: CARD; fatherIndex2 ¬ heap.entries[1]; fatherSizeSum ¬ IndexedEntrySize[pathStk: pathStk, index: fatherIndex] + IndexedEntrySize[pathStk: pathStk, index: fatherIndex2]; IF fatherSizeSum> breakSize1 ¬ EntryIntervalSize[pathStk: pathStk, rightFather: bestFatherIndex]; breakSize2 ¬ EntryIntervalSize[pathStk: pathStk, rightFather: bestFatherIndex2]; totalSize ¬ EntryIntervalSize[pathStk: pathStk]; WritePage[tree: tree, pse: pse, number: pse.pageNumber, words: breakSize1]; fatherESR ¬ WriteRightBrother[tree: tree, pse: pse, rtBroPg: rtBroPg1, words: breakSize2-breakSize1]; PushEntSeqRecord[pse: fatherPSE, esr: WriteRightBrother[tree: tree, pse: pse, rtBroPg: rtBroPg2, words: totalSize-breakSize2]]; PushEntSeqRecord[pse: fatherPSE, esr: fatherESR]; }; FindRightBrother: PROC [tree: Tree, pathStk: PathStk, spaceNeeded: INT] RETURNS [rtBroPg: PageNumber] = { <> pse: PathStkEntryPtr = @pathStk.path[pathStk.top]; fatherPSE: PathStkEntryPtr = @pathStk.path[pathStk.top-1]; fatherEntSize: CARD; pagePtr: BTreePagePtr; fatherESR, rtBroESR: REF EntSeqRecord; IF fatherPSE.eslFront=NIL THEN { pagePtr ¬ tree.ReferencePage[fatherPSE.pageNumber]; IF fatherPSE.offset = nilOffset+(tree.state.pageSize-pagePtr.freeBytes) THEN { <> tree.ReleasePage[fatherPSE.pageNumber]; RETURN [nilPage]; }; fatherEntSize ¬ tree.BTreeEntrySize[@pagePtr[fatherPSE.offset]]; rtBroPg ¬ pagePtr[fatherPSE.offset].grPage; tree.ReleasePage[fatherPSE.pageNumber]; } ELSE { fatherEntSize ¬ tree.BTreeEntrySize[fatherPSE.eslFront.entSeqP]; rtBroPg ¬ fatherPSE.eslFront.entSeqP.grPage; }; pagePtr ¬ tree.ReferencePage[rtBroPg]; IF LOOPHOLE[pagePtr.freeBytes-fatherEntSize, INT] < spaceNeeded THEN { <> tree.ReleasePage[rtBroPg]; RETURN [nilPage]; }; rtBroESR ¬ MakeEntSeqRecord[ entSeq: FirstEntry[pagePtr], length: tree.maxFreeBytes-pagePtr.freeBytes]; tree.ReleasePage[rtBroPg]; [esr: fatherESR] ¬ tree.RemoveEntry[pse: fatherPSE]; AppendEntSeqLengths[tree: tree, pathStk: pathStk, esr: fatherESR]; AppendEntSeqRecord[pse: pse, esr: fatherESR]; AppendEntSeqLengths[tree: tree, pathStk: pathStk, esr: rtBroESR]; AppendEntSeqRecord[pse: pse, esr: rtBroESR]; }; FindLeftBrother: PROC [tree: Tree, pathStk: PathStk, spaceNeeded: INT] RETURNS [ltBroPg: PageNumber] = { <> pse: PathStkEntryPtr = @pathStk.path[pathStk.top]; fatherPSE: PathStkEntryPtr = @pathStk.path[pathStk.top-1]; fatherPagePtr, ltBroPagePtr, rtBroPagePtr: BTreePagePtr; fatherESR, ltBroESR: REF EntSeqRecord; fatherEntSize: CARD; rtBroOfLtBroPg: PageNumber; IF fatherPSE.offset <= entry1Offset THEN RETURN [nilPage]; fatherPagePtr ¬ tree.ReferencePage[fatherPSE.pageNumber]; ltBroPg ¬ fatherPagePtr[fatherPSE.nextToLastOffset].grPage; rtBroOfLtBroPg ¬ fatherPagePtr[fatherPSE.lastOffset].grPage; fatherEntSize ¬ tree.BTreeEntrySize[@fatherPagePtr[fatherPSE.lastOffset]]; tree.ReleasePage[fatherPSE.pageNumber]; ltBroPagePtr ¬ tree.ReferencePage[ltBroPg]; IF LOOPHOLE[ltBroPagePtr.freeBytes-fatherEntSize, INT] < spaceNeeded THEN { tree.ReleasePage[ltBroPg]; RETURN [nilPage]; }; ltBroESR ¬ MakeEntSeqRecord[ entSeq: FirstEntry[ltBroPagePtr], length: tree.maxFreeBytes-ltBroPagePtr.freeBytes]; fatherPagePtr ¬ tree.ReferencePage[fatherPSE.pageNumber, write]; fatherPagePtr[fatherPSE.nextToLastOffset].grPage ¬ rtBroOfLtBroPg; tree.ReleasePage[fatherPSE.pageNumber]; [esr: fatherESR] ¬ tree.BackUpAndRemoveEntry[pse: fatherPSE]; rtBroPagePtr ¬ tree.ReferencePage[rtBroOfLtBroPg, write]; fatherESR.entSeqP.grPage ¬ rtBroPagePtr.minPage; rtBroPagePtr.minPage ¬ ltBroPagePtr.minPage; tree.ReleasePage[rtBroOfLtBroPg]; tree.ReleasePage[ltBroPg]; PushEntSeqLengths[tree: tree, pathStk: pathStk, esr: fatherESR]; PushEntSeqRecord[pse: pse, esr: fatherESR]; PushEntSeqLengths[tree: tree, pathStk: pathStk, esr: ltBroESR]; PushEntSeqRecord[pse: pse, esr: ltBroESR]; }; WriteRightBrother: PROC [tree: Tree, pse: PathStkEntryPtr, rtBroPg: PageNumber, words: CARD] RETURNS [fatherESR: REF EntSeqRecord] = { <> pagePtr: BTreePagePtr; minPage: PageNumber; [esr: fatherESR, grPage: minPage] ¬ tree.RemoveEntry[pse: pse]; words ¬ words-fatherESR.entSeqLen; pagePtr ¬ tree.ReferencePage[rtBroPg, write]; pagePtr.minPage ¬ minPage; tree.ReleasePage[rtBroPg]; WritePage[tree: tree, pse: pse, number: rtBroPg, words: words]; fatherESR.entSeqP.grPage ¬ rtBroPg; }; WritePage: PROC [tree: Tree, pse: PathStkEntryPtr, number: PageNumber, words: CARD] = { <> pagePtr: BTreePagePtr = tree.ReferencePage[number, write]; DepositESL[tree: tree, pse: pse, block: FirstEntry[pagePtr], length: words]; pagePtr.freeBytes ¬ tree.maxFreeBytes-words; tree.ReleasePage[number]; }; IndexedEntrySize: PROC [pathStk: PathStk, index: EntryOrdinal] RETURNS [words: CARD] = INLINE { words ¬ EntryIntervalSize[pathStk: pathStk, leftFather: index-1, rightFather: index+1]; RETURN [words]; }; FillLeftPage: PROC [tree: Tree, pathStk: PathStk, leftFather, rightFather: EntryOrdinal ¬ 0] RETURNS [midFather: EntryOrdinal] = { <> IF rightFather=0 THEN rightFather ¬ pathStk.entryTable.length+1; midFather ¬ leftFather+2; WHILE midFather> IF rightFather=0 THEN rightFather ¬ pathStk.entryTable.length+1; midFather ¬ rightFather-2; WHILE midFather>leftFather+2 AND EntryIntervalSize[pathStk: pathStk, leftFather: midFather-1, rightFather: rightFather] <= tree.maxFreeBytes DO midFather ¬ midFather-1; ENDLOOP; }; <> <> < LOOPHOLE[src, CARD] AND LOOPHOLE[dst, CARD] - LOOPHOLE[src, CARD] < nBytes THEN {>> <> < 0 DO>> <> <> <> <> <<};>> <> <> <> <<};>> BytesToWords: PROC[nBytes: CARD] RETURNS[nWords: CARD] ~ INLINE { RETURN[ (nBytes+BYTES[WORD]-1)/BYTES[WORD] ]; }; FirstEntry: PROC [pagePtr: BTreePagePtr] RETURNS [BTreeEntryPtr] = INLINE { <> RETURN [LOOPHOLE[pagePtr + pageOverhead]]; }; <> <> <> <<>> <> <> <> <> <> <> <<>> <> <<>> <<>> <<};>> <<[inStream, outStream, errStream, hasEcho] _ SimpleStreams.Create[windowSystem: $uxio];>> }.