<> <> <> <> <> <> <> <> <> DIRECTORY DBCommon, DBIndex, DBIndexOp, DBIndexMod, DBIndexPage, DBIndexScan USING [ManipulateScanIndex], DBStorage, DBStorageConcrete, RefText, Rope; DBIndexOpImpl: CEDAR PROGRAM IMPORTS DBIndexMod, DBIndexPage, DBIndexScan, RefText EXPORTS DBIndexOp, DBStorage = BEGIN OPEN DBIndexPage; IndexScanObject: PUBLIC TYPE = DBStorageConcrete.IndexScanObject; IndexScanHandle: TYPE = REF IndexScanObject; Page: TYPE = DBIndex.Page; IndexKey: TYPE = DBIndex.IndexKey; ItemHandle: TYPE = DBIndex.ItemHandle; State: TYPE = DBIndex.State; OverHead: CARDINAL = DBIndex.OverHead; FullPage: CARDINAL = DBIndex.FullPage; HalfPage: CARDINAL = DBIndex.HalfPage; <> KeyIsNotFound: ERROR = CODE; OutOfBound: ERROR = CODE; PageOverflow: ERROR = CODE; UnsplittablePage: ERROR = CODE; ThisLooksSuspicious: SIGNAL = CODE; <> CheckLength: PROC[c: CARDINAL] RETURNS[CARDINAL] = <> {IF c>250 THEN SIGNAL ThisLooksSuspicious; RETURN[c]}; OverFlow: PUBLIC PROC [p: Page, key: REF TEXT] RETURNS [BOOLEAN] = TRUSTED { RETURN [FreeSpace[p] < CARDINAL[(key.length + 9) / 2]] }; EntrySize: PUBLIC PROC [p: Page, i: CARDINAL] RETURNS [CARDINAL] = { <> IF p.depth # 1 AND i = 0 THEN RETURN [2] ELSE RETURN [CheckLength[(KeyLength[p, i] + 7) / 2]] }; KeyLength: PUBLIC PROC [page: Page, index: CARDINAL] RETURNS [CARDINAL] = TRUSTED { <> p: ItemHandle _ CoreAddr[page, index]; RETURN [CheckLength[p.length]] }; MakeSplitKey: PROC [left: REF TEXT, right: REF TEXT] RETURNS [key: REF TEXT] = TRUSTED { <> i, length: INT; keyText: REF TEXT; FOR i IN [0..left.length) DO IF left.text[i] # right.text[i] THEN GO TO Found REPEAT Found => length _ i + 1; FINISHED => length _ left.length; ENDLOOP; keyText _ RefText.New[length]; FOR i IN [0..length) DO keyText _ RefText.AppendChar[keyText, right.text[i]] ENDLOOP; RETURN [keyText] }; RopeForKey: PUBLIC PROC[key: IndexKey] RETURNS[REF TEXT] = TRUSTED { keyText: REF TEXT _ RefText.New[key.length]; FOR i: CARDINAL IN [0..key.length) DO keyText _ RefText.AppendChar[keyText, key.text[i]] ENDLOOP; RETURN [keyText] }; KeyInBetween: PROC [page: Page, after: CARDINAL] RETURNS [key: REF TEXT] = { <> leftKey: IndexKey = Key[page, after]; rightKey: IndexKey = Key[page, after + 1]; RETURN[MakeSplitKey[RopeForKey[leftKey], RopeForKey[rightKey]]] }; SplitPage: PUBLIC PROC [p: Page, loc: CARDINAL, insertSize: INTEGER] RETURNS [splitLoc: CARDINAL, splitKey: REF TEXT, overflow: Page] = <> BEGIN splitLoc _ FindSplitLoc[p, loc, insertSize]; overflow _ DBIndexPage.CreateEmptyPage[p.tree, p.depth, p.tree.segment]; splitKey _ DBIndexMod.SplitEntriesToRightPage[from: p, to: overflow, at: splitLoc]; END; FindSplitLoc: PROC [p: Page, loc: CARDINAL, size: INTEGER] RETURNS [CARDINAL] = TRUSTED BEGIN upper: CARDINAL _ p.pointer.size - 1; lower: CARDINAL _ 0; middle: CARDINAL; compareSize: CARDINAL; WHILE upper > lower DO middle _ (upper + lower)/2; IF middle = lower THEN EXIT; IF middle > loc THEN compareSize _ DBIndex.HalfPage - size ELSE compareSize _ DBIndex.HalfPage; IF FrontSize[p, middle] > compareSize THEN IF FrontSize[p, middle - 1] <= compareSize THEN RETURN[middle + 1] ELSE upper _ middle ELSE lower _ middle; ENDLOOP; IF upper=p.pointer.size-1 THEN RETURN[upper]; IF lower#0 THEN RETURN[lower]; ERROR UnsplittablePage; END; SplitLeaf: PUBLIC PROC[p: Page, key: REF TEXT, value: LONG CARDINAL] RETURNS [Page, REF TEXT] = TRUSTED { < pair. We allocate a page to the right of p and moves contents, and insert at the same time.>> insertIndex: CARDINAL; insertSize: CARDINAL _ CheckLength[(key.length + 9) / 2]; index: CARDINAL _ FindTheLastLeafKey[p, key]; frontSize: CARDINAL _ IF index = 0 THEN 0 ELSE FrontSize[p, index - 1]; <> overflow: Page; splitIndex: CARDINAL; splitKey: REF TEXT; SplitAtTheKey: PROC = CHECKED { splitKey _ MakeSplitKey[RopeForKey[Key[p, index - 1]], key]; MoveRightAfterSecond[from: p, to: overflow, after: index - 1, key: key, value: value] }; overflow _ DBIndexPage.CreateEmptyPage[p.tree, p.depth, p.tree.segment]; DBIndexMod.SetLinks[left: p, new: overflow]; IF frontSize + index + OverHead > HalfPage + 1 OR index >= p.pointer.size THEN {splitIndex _ JustOver[p, HalfPage]; IF splitIndex = index OR splitIndex = index - 1 THEN {SplitAtTheKey[]; RETURN [overflow, splitKey]}; IF splitIndex = p.pointer.size - 1 THEN ERROR PageOverflow; splitKey _ KeyInBetween[p, splitIndex]; insertIndex _ DBIndexMod.MoveRightAndInsert[from: p, to: overflow, after: splitIndex, at: index - 1, key: key, value: value]; MoveScanIndexRight[from: p, to: overflow, after: splitIndex]; IncrementScanIndex[overflow, insertIndex]; RETURN [overflow, splitKey]}; IF index # 0 AND frontSize + index + OverHead <= HalfPage + 1 AND frontSize + index + OverHead + insertSize > HalfPage THEN splitIndex _ index - 1 ELSE splitIndex _ JustOver[p, HalfPage - insertSize]; IF splitIndex = index - 1 THEN splitKey _ MakeSplitKey[key, RopeForKey[Key[p, splitIndex + 1]]] ELSE splitKey _ KeyInBetween[p, splitIndex]; [] _ DBIndexMod.MoveEntriesToRightLeaf[from: p, to: overflow, nentries: p.pointer.size - splitIndex - 1]; DBIndexMod.SlideLeafAt[p: p, index: index, key: key, value: value]; RETURN [overflow, splitKey] }; -- SplitLeaf SplitInternal: PUBLIC PROC[p: Page, insertLoc: CARDINAL, key: REF TEXT, value: LONG CARDINAL] RETURNS [Page, REF TEXT] = TRUSTED { <. Returns the of the newly created page, which locates to the right of p, and the key to separates the two pages. Caller must deallocate IndexKey returned.>> insertSize: INTEGER _ (key.length + 1) / 2 + 3; splitLoc: CARDINAL; splitKey: REF TEXT; overflow: Page; [splitLoc, splitKey, overflow] _ SplitPage[p, insertLoc, insertSize]; IF splitLoc > insertLoc THEN [] _ InsertInInternalPage[p, insertLoc, value, key] ELSE [] _ InsertInInternalPage[overflow, insertLoc - splitLoc, value, key]; RETURN [overflow, splitKey] }; InsertInInternalPage: PUBLIC PROC [ p: Page, i: CARDINAL, newPage: LONG CARDINAL, newKey: REF TEXT] RETURNS [State, Page, REF TEXT] = { < to the right of index. Caller must always deallocate IndexKey returned.>> overflow: Page; splitKey: REF TEXT; IF OverFlow[p, newKey] THEN { [overflow, splitKey] _ SplitInternal[p, i, newKey, newPage]; RETURN [split, overflow, splitKey] } ELSE { DBIndexMod.SlideLeafAt[p, i + 1, newKey, newPage]; RETURN [normal, NIL, NIL] } }; DeleteFromLeafPage: PUBLIC PROC [p: Page, key: REF TEXT, tid: DBCommon.TID] RETURNS [State, Page, REF TEXT] = TRUSTED { endIndex, i: CARDINAL; state: State; i _ FindTheFirstLeafKey[p, key]; IF i = CheckLength[endIndex _ p.pointer.size] THEN RETURN [deleteFromNextPage, NIL, NIL]; DO IF Less[RefText.TrustTextAsRope[key], Key[p, i]] THEN ERROR KeyIsNotFound; IF Tid[p, i] = tid THEN { state _ DBIndexMod.RemoveFromLeaf[p, i]; DBIndexPage.CheckTag[p.pointer]; RETURN [state, NIL, NIL] }; i _ i + 1; IF i >= endIndex THEN RETURN [deleteFromNextPage, NIL, NIL] ENDLOOP }; -- DeleteFromLeafPage MergeInLeafPage: PUBLIC PROC [p: Page, son: Page, index: CARDINAL] RETURNS [State, Page, REF TEXT] = TRUSTED { freeSon: CARDINAL _ FreeSpace[son]; i: CARDINAL; newKey, temp1: REF TEXT; sizeSon: CARDINAL _ son.pointer.size; state: State; overflow: Page; IF index # p.pointer.size - 1 <> THEN { right: Page _ DBIndexPage.GetPage[p.tree, Value[p, index + 1], son.depth]; IF FreeSpace[right] + freeSon + OverHead > FullPage THEN {DBIndexMod.MoveEntriesToRightLeaf[from: son, to: right, nentries: sizeSon]; DBIndexMod.RemoveLinks[son]; DBIndexPage.UnlockPage[right]; RETURN [delete, NIL, NIL]}; i _ JustOver[right, HalfPage - FrontSize[son, sizeSon - 1] - sizeSon]; IF i = 0 THEN {DBIndexPage.UnlockPage[right]; RETURN [normal, NIL, NIL]}; newKey _ KeyInBetween[right, i - 1]; DBIndexMod.MoveEntriesToLeftLeaf[from: right, to: son, nentries: i]; DBIndexPage.UnlockPage[right]; index _ index + 1 } ELSE {-- balance with the left page left: Page _ DBIndexPage.GetPage[p.tree, Value[p, index - 1], son.depth]; IF FreeSpace[left] + freeSon + OverHead > FullPage THEN {DBIndexMod.MoveEntriesToLeftLeaf[from: son, to: left, nentries: sizeSon]; DBIndexMod.RemoveLinks[son]; DBIndexPage.UnlockPage[left]; RETURN [delete, NIL, NIL]}; i _ JustOver[left, HalfPage]; IF i = left.pointer.size - 1 THEN {DBIndexPage.UnlockPage[left]; RETURN [normal, NIL, NIL]}; newKey _ KeyInBetween[left, i]; DBIndexMod.MoveEntriesToRightLeaf[from: left, to: son, nentries: left.pointer.size - i - 1]; DBIndexPage.UnlockPage[left] }; [state, overflow, temp1] _ ChangeKey[p, newKey, index]; RETURN [state, overflow, temp1] }; ChangeKey: PUBLIC PROC [p: Page, newKey: REF TEXT, index: CARDINAL] RETURNS [state: State, overflow: Page, key: REF TEXT] = { <> TRUSTED {IF newKey.length > DBIndex.CoreIndexSize THEN ERROR}; state _ ComputeResultOfKeyChange[p, newKey, index]; SELECT state FROM normal => {DBIndexMod.ReplaceKey[p, newKey, index]; RETURN [normal, NIL, NIL]}; split => {[overflow, newKey] _ ReplaceKeyAndSplit[p, newKey, index]; RETURN [split, overflow, newKey]}; merge => {DBIndexMod.ReplaceKey[p, newKey, index]; RETURN [merge, NIL, NIL]} ENDCASE => ERROR }; ComputeResultOfKeyChange: PROC[page: Page, key: REF TEXT, index: CARDINAL] RETURNS [State] = TRUSTED { <> oldKeyLength: CARDINAL _ KeyLength[page, index]; free: CARDINAL _ FreeSpace[page]; IF key.length > oldKeyLength THEN IF key.length > oldKeyLength + free THEN RETURN [split] ELSE RETURN [normal] ELSE IF oldKeyLength + free > HalfPage + LOOPHOLE[key.length, CARDINAL] THEN RETURN [merge] ELSE RETURN [normal] }; ReplaceKeyAndSplit: PROC[p: Page, key: REF TEXT, at: CARDINAL] RETURNS [Page, REF TEXT] = TRUSTED { <> insertSize: INTEGER = (key.length + 1) / 2 + 3 - EntrySize[p, at]; splitLoc: CARDINAL; splitKey: REF TEXT; overflow: Page; IF insertSize>DBIndex.CoreIndexSize THEN ERROR; [splitLoc, splitKey, overflow] _ SplitPage[p, at, insertSize]; IF splitLoc > at THEN DBIndexMod.ReplaceKey[p, key, at] ELSE IF splitLoc < at THEN DBIndexMod.ReplaceKey[overflow, key, at - splitLoc] ELSE -- splitLoc=at, the new split key should just be passed upward splitKey _ key; RETURN [overflow, splitKey] }; MoveScanIndexLeft: PUBLIC PROC [from, to: Page, nentries: CARDINAL] = { <> MoveLeft: PROC [scan: IndexScanHandle] = TRUSTED { IF scan.index < nentries OR to.pointer.size = 0 THEN {scan.index _ scan.index + to.pointer.size - nentries; scan.this _ to.db} ELSE scan.index _ scan.index - nentries }; DBIndexScan.ManipulateScanIndex[from, 0, MoveLeft] }; MoveScanIndexRight: PUBLIC PROC [from, to: Page, after: CARDINAL] = { <> Move: PROC [scan: IndexScanHandle] = { scan.index _ scan.index - after - 1; scan.this _ to.db }; DBIndexScan.ManipulateScanIndex[from, after + 1, Move] }; MoveRightAfterSecond: PROC[from, to: Page, after: CARDINAL, key: REF TEXT, value: LONG CARDINAL] = TRUSTED { < and move the entries [after..size) of "from" just after that. "to" is to the right of "from", and is empty to start with.>> DBIndexMod.InsertTheFirstLeafEntry[to, key, value]; DBIndexMod.MoveEntriesToRightLeafAfter[from, to, from.pointer.size - after - 1]; IncrementScanIndex[to, 0]; -- should be no refs to this new page, but Nori put this here }; DecrementScanIndex: PUBLIC PROC [page: Page, atOrAfter: CARDINAL] = { <> Decrement: PROC [scan: IndexScanHandle] = {scan.index _ scan.index - 1}; DBIndexScan.ManipulateScanIndex[page, atOrAfter, Decrement] }; IncrementScanIndex: PUBLIC PROC [page: Page, atOrAfter: CARDINAL, howMuch: CARDINAL _ 1] = { <> Increment: PROC [scan: IndexScanHandle] = {scan.index _ scan.index + howMuch}; DBIndexScan.ManipulateScanIndex[page, atOrAfter, Increment] }; END. Change Log Changed the meaning of SlideAt by Suzuki: November 24, 1980 1:04 PM Changed SplitLeaf so that there won't be an overflow even if index=0 by Suzuki: November 25, 1980 9:08 AM Changed MoveEntriesToRightLeaf so that it works even if toSize=0 by Suzuki: November 25, 1980 9:21 AM Changed offset in MoveEntriesToRightLeaf by Suzuki: November 25, 1980 9:52 AM Changed the definition of offset in MoveEntriesToRightLeaf so that it works even when the entire page is moved by Suzuki December 2, 1980 10:08 AM Changed FindSplitLoc; it now uses FrontSize instead of CoreIndex. by Suzuki December 3, 1980 10:07 AM Changed MoveRightAndInsert; it works now even if key is inserted at the index 0. by Suzuki December 4, 1980 10:57 AM Allocate storage from DBHeapStorage; define SplitKeyBufferWords. by MBrown February 27, 1981 6:12 PM All WriteAndFreePage are changed to FreePage. by Suzuki 2-Apr-81 14:31:47 Changed SplitLeaf, MoveEntriesToRightLeaf, MoveEntriesToLeftLeaf, Remove, ReplaceKey, SlideAt: WriteLockedPage is added. by Suzuki 2-Apr-81 15:52:37 Ran through formatter. by Cattell May 25, 1982 7:17 pm Added CheckLengths in various places where small numbers should be passed as arguments. Also adde ThisLooksSuspicious SIGNAL. by Cattell May 28, 1982 4:39 pm Add check in ShiftRight for by=0 by Willie-Sue June 4, 1982 9:40 am Removed most of the OPENs at the beginning. Yuck. Added some checks on key lengths. by Cattell June 19, 1982 3:23 pm Fixed bug #7! Both MoveEntriesToRightLeaf and MoveEntriesToLeftLeaf can be called with nentries=0 and an EMPTY from page. But these die in SizeOfEntries passed fromSize-1 (= 65536 as CARDINAL). I will still allow call with nentries=0, but only if fromSize=0, and will not call SizeOfEntries till after checking for nentries=0. Added more consistency checks. Particularly, CheckPage and CheckLeafPage check for empty pages, which should never be left after an operation has been completed. by Cattell July 28, 1982 11:48 am Oops! Boo-boo in above fix to MoveEntriesToLeftLeaf, it should pass SizeOfEntries nentries-1, not fromSize-1. by Cattell July 29, 1982 12:49 pm Changed some data structures from POINTERs to REFs. by Cattell August 6, 1982 5:01 pm Made RemoveLinks public. by Cattell August 19, 1982 2:18 pm Major re-organization: moved most procedures to new module DBIndexMod(Impl). This module never touches B-tree pages directly, now. The move involved inventing new procedures and re-organizing existing ones for the cleaner interface. by Cattell September 22, 1982 8:48 am B-Tree bug fix #20: In ReplaceKeyAndSplit, called by ChangeKey, called by MergeInInternalPage. IF the page happens to be be split at exactly the same place that the key was being changed (to reflect the merge of the sons by MergeInInternalPage), then an exception has to be made and the key must be passed up to be changed in the grandparent instead. So now the IF has three cases, >, <, =. by Cattell December 29, 1982 7:37 pm Moved some more procs here from DBIndexImpl, DBIndexPageImpl. by Cattell January 17, 1983 6:11 pm B-Tree bug fix #21: I don't see how MoveScanIndexLeft could ever have worked! If scan.index> Changed by Willie-Sue on September 16, 1986 <>