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
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.