File: DBIndexMod.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Willie-Sue, February 15, 1985 3:42:13 pm PST
Donahue, May 1, 1986 9:20:43 am PDT
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: CEDAR DEFINITIONS =
BEGIN OPEN DBIndex;
ReplaceKey: PROC [p: Page, key: REF TEXT, 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: REF TEXT, value: LONG CARDINAL];
Insert the first entry in an empty leaf page
InsertTwoEntriesToEmptyPage: PROC[page: Page, first: LONG CARDINAL, key: REF TEXT, 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: REF TEXT, 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: REF TEXT, 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 [REF TEXT];
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: REF TEXT, value: LONG CARDINAL] RETURNS [CARDINAL];
Inserts <key, value> between from[at] and from[at+1]. Since from will overflow, we move from[after+1..fromEnd] to the page to, and insert <key,value>. Returns the index where insertion occurred
SlideLeafAt: PROC[p: Page, index: CARDINAL, key: REF TEXT, value: LONG CARDINAL];
Shifts part of entries in p including and after the index and inserts <key, value>
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
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.
Changed by Willie-Sue on February 15, 1985
made Cedar, added tioga formatting