-- File: DBIndexMod.mesa -- Contents: All DBIndex package database modifications go through this interface -- Created from: pieces of former DBIndexFilePage, DBIndexOp, DBIndex, and DBIndexInternal -- Implementation: DBIndexModImpl.mesa -- Created by Cattell on September 21, 1982 8:28 pm -- Last edited by -- Cattell: September 21, 1982 8:28 pm DIRECTORY DBCommon, DBIndex; DBIndexMod: DEFINITIONS = BEGIN OPEN DBIndex; ReplaceKey: PROC [p: Page, key: IndexKey, at: CARDINAL]; -- Replaces the key in leaf at "at" by "key" in leaf page MoveEntriesToLeftLeaf: PROC [from, to: Page, nentries: CARDINAL]; -- Both from & to are internal pages. -- from is to the right of to. -- Move entries [0-nentries) in from page to to page. MoveEntriesToRightLeaf: PROC [from, to: Page, nentries: CARDINAL]; -- Both from & to are internal pages. -- from is to the left of to. -- Move entries [size-nentries..size) in from page to to page. MoveEntriesToRightLeafAfter: PROC [from, to: Page, nentries: CARDINAL]; -- Just like MoveEntriesToRightLeaf, except entries moved from "from" --are placed after entries of "to" InsertTheFirstLeafEntry: PROC [page: Page, key: IndexKey, value: LONG CARDINAL]; -- Insert the first entry in an empty leaf page InsertTwoEntriesToEmptyPage: PROC [page: Page, first: LONG CARDINAL, key: IndexKey, second: LONG CARDINAL]; -- "page" is empty and an internal node. -- Inserts two entries "first" and "second" with the separator "key" MoveEntriesToRightInternal: PROC [from, to: Page, key: IndexKey, nentries: CARDINAL]; -- "from" is to the left of "to" -- "key" is the dividing key between from and to -- "nentries" are moved (returns if 0) MoveEntriesToLeftInternal: PROC [from, to: Page, key: IndexKey, nentries: CARDINAL]; -- "from" is to the right of "to" -- key is the dividing key between from and to -- "nentries" are moved (0 => no-op) SplitEntriesToRightPage: PROC [from, to: Page, at: CARDINAL] RETURNS [IndexKey]; -- Both from & to are internal page. -- "From" is to the left of "to", and "to" is empty. -- Move entries [at..size) in "from" to "to" MoveRightAndInsert: PROC [from: Page, to: Page, after: CARDINAL, at: CARDINAL, key: IndexKey, value: LONG CARDINAL] RETURNS [CARDINAL]; -- Inserts between from[at] and --from[at+1]. Since from will overflow, we move --from[after+1..fromEnd] to the page to, and insert -- Returns the index where insertion occurred SlideLeafAt: PROC [p: Page, index: CARDINAL, key: IndexKey, value: LONG CARDINAL]; -- Shifts part of entries in p including and after the index and inserts -- It is guaranted that there won't be any overflow. RemoveFromInternal: PROC [page: Page, deleting: CARDINAL] RETURNS [State]; -- Takes out the deleting-th entry and compresses RemoveFromLeaf: PUBLIC PROC [page: Page, deleting: CARDINAL] RETURNS [State]; -- Takes out the deleting-th entry and compresses -- SplitPage: PROC [ p: Page, loc: CARDINAL, insertSize: INTEGER] -- RETURNS [ splitLoc: CARDINAL, splitKey: IndexKey, overflow: Page]; SetLinks: PROC [left, new: Page]; -- Inserts "new" between "left" and its right sibling RemoveLinks: PROC [page: Page]; -- Remove leaf page's left and right links. MUST call before destroying page. END. J