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 <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: IndexKey, 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
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.