File: DBIndexModImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Contents: All DBIndex package database modifications go through this module
Invariant: All public procedures should set dirty bit for B-Tree page; no internal ones should do so. No other module should set dirty bit or modify B-Tree pages.
Created by Cattell on September 21, 1982 8:28 pm
Last edited by
Cattell: September 29, 1983 2:05 pm
Willie-Sue, September 17, 1986 10:09:11 am PDT
Donahue, May 22, 1986 10:27:26 am PDT
DIRECTORY
Basics,
DBCommon,
DBSegment,
DBStoragePage,
DBIndex,
DBIndexMod,
DBIndexOp,
DBIndexPage,
PrincOpsUtils,
Rope;
DBIndexModImpl: CEDAR PROGRAM
IMPORTS Basics, DBSegment, DBIndexOp, DBIndexPage, PrincOpsUtils
EXPORTS DBIndexMod =
BEGIN OPEN DBIndexPage;
Page: TYPE = DBIndex.Page;
Core: TYPE = DBIndex.Core;
IndexKey: TYPE = DBIndex.IndexKey;
ItemHandle: TYPE = DBIndex.ItemHandle;
State: TYPE = DBIndex.State;
OverHead: CARDINAL = DBIndex.OverHead;
FullPage: CARDINAL = DBIndex.FullPage;
CoreIndexSize: CARDINAL = DBIndex.CoreIndexSize;
HalfPage: CARDINAL = DBIndex.HalfPage;
KeyTooLarge: SIGNAL = CODE;
BadBTree: SIGNAL = CODE;
OutOfBound: SIGNAL = CODE;
ThisLooksSuspicious: SIGNAL = CODE;
PageOverflow: ERROR = CODE;
InsertTwoEntriesToEmptyPage: PUBLIC PROC[page: Page, first: LONG CARDINAL, key: REF TEXT, second: LONG CARDINAL] = TRUSTED {
"page" is empty and an internal node.
Inserts two entries "first" and "second" with the separator "key"
index: CARDINAL;
core: LONG POINTER TO Core ← page.pointer;
DBIndexPage.WritePage[page];
IF key.length > CoreIndexSize - 7 THEN ERROR KeyTooLarge;
core.index[0] ← CoreIndexSize - 2;
LOOPHOLE[@core.index[CoreIndexSize - 2], ItemHandle].value ← first;
index ← core.index[1] ← CoreIndexSize - (key.length + 11) / 2;
core.size ← 2;
StoreEntryInPage[core, index, key, second]
};
MoveEntriesToRightInternal: PUBLIC PROC[from, to: Page, key: REF TEXT, nentries: CARDINAL] = TRUSTED {
"from" is to the left of "to"
"key" is the dividing key between from and to
"nentries" are moved (returns if 0)
length: CARDINAL = (key.length + 3) / 2;
fromSize: CARDINAL = from.pointer.size;
toSize: CARDINAL = to.pointer.size;
at: CARDINAL = fromSize - nentries;
moveSize: CARDINAL;
i, offset: CARDINAL;
fromcore: LONG POINTER TO Core = from.pointer;
tocore: LONG POINTER TO Core = to.pointer;
DBIndexPage.WritePage[from];
DBIndexPage.WritePage[to];
IF nentries = 0 THEN RETURN;
IF nentries>1000 OR fromSize=0 THEN SIGNAL BadBTree;
moveSize← SizeOfEntries[from, at + 1, fromSize - 1] + 2;
Shifts entries in "to"
ShiftLeft[addr: CoreAddr[to, toSize - 1], nwords: SizeOfEntries[to, 0, toSize - 1], by: moveSize + length];
store key
StoreKey[tocore, CoreIndexSize - moveSize - length, key];
move entries from "from" to "to"
PrincOpsUtils.LongCopy[from: CoreAddr[from, fromSize - 1], to: EndAddr[to] - moveSize, nwords: moveSize];
shifts indexes in "to"
FOR i DECREASING IN [0..toSize) DO
tocore.index[i + nentries] ← tocore.index[i] - moveSize - length
ENDLOOP;
move indexes from "from" to "to"
offset ← IF at = 0 THEN 0 ELSE CoreIndexSize - from.pointer.index[at] - 2;
FOR i IN [at..fromSize) DO
tocore.index[i - at] ← fromcore.index[i] + offset
ENDLOOP;
set sizes
SetSize[to, toSize + nentries];
SetSize[from, at]
};
MoveEntriesToLeftInternal: PUBLIC PROC[from, to: Page, key: REF TEXT, nentries: CARDINAL] = TRUSTED {
"from" is to the right of "to"
key is the dividing key between from and to
"nentries" are moved (0 => no-op)
fromSize: CARDINAL = from.pointer.size;
fromShiftSize: CARDINAL = IF nentries >= fromSize THEN 0 ELSE SizeOfEntries[from, 1, nentries];
toSize: CARDINAL = to.pointer.size;
length: CARDINAL = (key.length + 3) / 2;
moveSize: CARDINAL;
i, offset: CARDINAL;
fromcore: LONG POINTER TO Core ← from.pointer;
tocore: LONG POINTER TO Core ← to.pointer;
DBIndexPage.WritePage[from];
DBIndexPage.WritePage[to];
IF nentries = 0 THEN RETURN;
IF nentries>1000 OR fromSize=0 THEN SIGNAL BadBTree;
moveSize ← SizeOfEntries[from, 0, nentries - 1];
StoreKey[tocore, tocore.index[toSize - 1] - length, key];
move entries in "from" to "to"
PrincOpsUtils.LongCopy[from: CoreAddr[from, nentries - 1], to: CoreAddr[to, toSize - 1] - length - moveSize, nwords: moveSize];
shifts entries in "from" to the right
ShiftRight[addr: CoreAddr[from, fromSize - 1], nwords: SizeOfEntries[from, nentries + 1, fromSize - 1] + 2, by: fromShiftSize];
move indexes from "from" to "to"
offset ← SizeOfEntries[to, 0, toSize - 1] + length;
FOR i IN [toSize..toSize + nentries) DO
tocore.index[i] ← fromcore.index[i - toSize] - offset
ENDLOOP;
shift indexes in "from"
FOR i IN [nentries..fromSize) DO
fromcore.index[i - nentries] ← fromcore.index[i] + fromShiftSize
ENDLOOP;
set size
SetSize[to, toSize + nentries];
SetSize[from, fromSize - nentries]
};
RemoveFromInternal: PUBLIC PROC [page: Page, deleting: CARDINAL] RETURNS [State] =
This works only for an internal node
Takes out the deleting-th entry and compresses
TRUSTED BEGIN
core: LONG POINTER TO Core = page.pointer;
pageSize: CARDINAL = page.pointer.size;
size: CARDINAL;
shiftSize: CARDINAL;
DBIndexPage.WritePage[page];
IF deleting#pageSize-1 THEN {
at: ItemHandle = CoreAddr[page, pageSize - 1];
size ← DBIndexOp.EntrySize[page, deleting+1];
IF deleting=pageSize-2 THEN shiftSize ← 2
ELSE shiftSize ← SizeOfEntries[page, deleting+2, pageSize-1]+2;
Compress data
PrincOpsUtils.LongMove[from: at, to: at + size, nwords: shiftSize];
Compress index array
ShiftIndex[page: page, from: deleting + 1, to: pageSize - 1, offset: size, by: -1]};
page.pointer.size ← page.pointer.size-1;
IF FreeSpace[page] >= HalfPage THEN RETURN[merge] ELSE RETURN[normal]
END;
SplitEntriesToRightPage: PUBLIC 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".
Caller must free IndexKey returned.
TRUSTED BEGIN
fromSize: CARDINAL ← from.pointer.size;
moveSize: CARDINAL ← SizeOfEntries[from, at + 1, fromSize - 1] + 2;
splitKey: REF TEXT;
only the value of the entry is moved.
i, offset: CARDINAL;
fromcore: LONG POINTER TO Core ← from.pointer;
tocore: LONG POINTER TO Core ← to.pointer;
DBIndexPage.WritePage[from];
DBIndexPage.WritePage[to];
splitKey ← DBIndexOp.RopeForKey[Key[from, at]]; -- copy because later split can re-arrange from page!
move entries from "from" to "to"
PrincOpsUtils.LongCopy[from: CoreAddr[from, fromSize - 1], to: EndAddr[to] - moveSize, nwords: moveSize];
move indexes from "from" to "to"
offset ← FrontSize[from, at] - 2;
FOR i IN [at..fromSize) DO tocore.index[i - at] ← fromcore.index[i] + offset ENDLOOP;
set size
SetSize[to, fromSize - at];
SetSize[from, at];
mark pages dirty
RETURN[splitKey];
END;
StoreEntryInPage: PROC [core: LONG POINTER TO Core, insertIndex: CARDINAL, key: REF TEXT, value: LONG CARDINAL] =
Stores the value, key to the page.
TRUSTED BEGIN
StoreEntry[LOOPHOLE[@core.index[insertIndex], ItemHandle], key, value];
END;
StoreEntry: PROC [at: ItemHandle, key: REF TEXT, value: LONG CARDINAL] =
Store the <key, value> at at, and make it the index. We copy the text bytes of the IndexKey and the length separately. We zero out the last byte on odd-lengthed text, though it shouldn't matter.
TRUSTED BEGIN
IF key.length = 0 OR key.length > CoreIndexSize THEN ERROR;
at.value ← value;
at.length ← key.length;
FOR i: CARDINAL IN [0..key.length) DO at.text[i] ← key.text[i] ENDLOOP;
IF key.length MOD 2 = 1 THEN at.text[key.length] ← 0C;
END;
StoreKey: PROC [core: LONG POINTER TO Core, index: CARDINAL, key: REF TEXT] =
Stores the key in core.index starting at index. Warning: index must point after the value field of the ItemHandle, if present.
TRUSTED BEGIN
TextSequenceType: TYPE = RECORD[PACKED SEQUENCE maxLength: NAT OF CHAR];
start: CARDINAL = SIZE[TextSequenceType[0]];
IF key.length = 0 OR key.length > CoreIndexSize THEN ERROR;
PrincOpsUtils.LongCopy[from: @key.length, to: @core.index[index], nwords: 1];
PrincOpsUtils.LongCopy[from: LOOPHOLE[@key.text+start], to: LOOPHOLE[@core.index[index]+1], nwords: (key.length + 1)/2];
IF key.length MOD 2 = 1 THEN Mask[@core.index[index + 1 + key.length/2]];
END;
Mask: PROC [p: LONG POINTER] =
Turns the right most byte of p^ to 0
TRUSTED BEGIN p^ ← PrincOpsUtils.BITAND[p^, 177400B]; END;
IncrementSize: PROC [p: Page] = TRUSTED {
Increment the size of entries in p
core: LONG POINTER TO Core ← p.pointer;
IF core.size>100 THEN SIGNAL ThisLooksSuspicious;
core.size ← core.size + 1
};
DecrementSize: PROC [p: Page] = TRUSTED {
Decrement the size of entries in p
core: LONG POINTER TO Core ← p.pointer;
IF core.size>100 THEN SIGNAL ThisLooksSuspicious;
core.size ← core.size - 1
};
SetLinks: PUBLIC PROC [left, new: Page] = TRUSTED {
Inserts "new" between "left" and its right sibling
cache: DBCommon.CacheHandle;
newcore: LONG POINTER TO Core ← new.pointer;
leftcore: LONG POINTER TO Core ← left.pointer;
rightcore: LONG POINTER TO Core;
right: DBCommon.DBPage;
right ← newcore.right ← leftcore.right;
leftcore.right ← new.db;
newcore.left ← left.db;
IF right # DBCommon.NullDBPage THEN
{[cache, rightcore] ← DBSegment.ReadPage[right, NIL];
IF rightcore.tag.pageTag # DBStoragePage.BTree THEN ERROR;
rightcore.left ← new.db;
DBSegment.WriteLockedPage[cache];
DBSegment.UnlockPage[cache]}
};
InsertTheFirstLeafEntry: PUBLIC PROC[page: Page, key: REF TEXT, value: LONG CARDINAL] = TRUSTED {
Insert the first entry in an empty page
insertSize: CARDINAL = (key.length + 7) / 2;
core: LONG POINTER TO Core ← page.pointer;
DBIndexPage.WritePage[page];
IF insertSize >= CoreIndexSize THEN ERROR;
core.size ← 1;
core.index[0] ← CheckLength[CoreIndexSize - insertSize];
StoreEntryInPage[core, CoreIndexSize - insertSize, key, value]
};
MoveEntriesToRightLeaf: PUBLIC PROC [from, to: Page, nentries: CARDINAL] = TRUSTED {
Both from & to are leaf pages, and from is to the left of to. Move entries [size-nentries..size) in from page to to page, and update any scans open on the entries moved from "from" or the entries moved down in "to".
fromSize: CARDINAL = from.pointer.size;
toSize: CARDINAL = to.pointer.size;
at: CARDINAL = fromSize - nentries;
moveSize: CARDINAL;
i, offset: CARDINAL;
fromcore: LONG POINTER TO Core ← from.pointer;
tocore: LONG POINTER TO Core ← to.pointer;
DBIndexPage.WritePage[from];
DBIndexPage.WritePage[to];
DBIndexPage.CheckTag[from.pointer];
DBIndexPage.CheckTag[to.pointer];
IF nentries = 0 THEN RETURN;
IF nentries > 40 OR fromSize = 0 THEN SIGNAL BadBTree;
moveSize← SizeOfEntries[from, at, fromSize - 1]; -- fromSize>0 if nentries>0!
Shifts entries in "to"
IF toSize # 0 THEN
ShiftLeft[
addr: CoreAddr[to, toSize - 1],
nwords: SizeOfEntries[to, 0, toSize - 1], by: moveSize];
Move entries from "from" to "to"
PrincOpsUtils.LongCopy[
from: CoreAddr[from, fromSize - 1], to: EndAddr[to] - moveSize,
nwords: moveSize];
Shifts indexes in "to"
FOR i DECREASING IN [0..toSize) DO
tocore.index[i + nentries] ← tocore.index[i] - moveSize
ENDLOOP;
Move indexes from "from" to "to"
offset ← IF at = 0 THEN 0 ELSE CoreIndexSize - from.pointer.index[at - 1];
FOR i IN [at..fromSize) DO tocore.index[i - at] ← fromcore.index[i] + offset ENDLOOP;
Set sizes
SetSize[to, toSize + nentries];
SetSize[from, at];
DBIndexOp.IncrementScanIndex[page: to, atOrAfter: 0, howMuch: nentries];
DBIndexOp.MoveScanIndexRight[from: from, to: to, after: fromSize - nentries - 1];
DBIndexPage.CheckTag[from.pointer];
DBIndexPage.CheckTag[to.pointer]
};
MoveEntriesToLeftLeaf: PUBLIC PROC [from, to: Page, nentries: CARDINAL] = TRUSTED {
Both from & to are leaf pages, and from is to the right of to. Move entries [0-nentries) in from page to to page, and update any scans open on the entries moved.
fromSize: CARDINAL ← from.pointer.size;
toSize: CARDINAL ← to.pointer.size;
moveSize: CARDINAL;
i, offset: CARDINAL;
fromcore: LONG POINTER TO Core ← from.pointer;
tocore: LONG POINTER TO Core ← to.pointer;
DBIndexPage.WritePage[from];
DBIndexPage.WritePage[to];
DBIndexPage.CheckTag[from.pointer];
DBIndexPage.CheckTag[to.pointer];
IF nentries = 0 THEN RETURN;
IF nentries > 40 OR fromSize = 0 THEN SIGNAL BadBTree;
moveSize← SizeOfEntries[from, 0, nentries - 1];
Move entries from "from" to "to"
IF toSize # 0 THEN
PrincOpsUtils.LongCopy[from: CoreAddr[from, nentries - 1], to: CoreAddr[to, toSize - 1] - moveSize,nwords: moveSize];
Shifts entries in "from" to the right
ShiftRight[addr: CoreAddr[from, fromSize - 1], nwords: SizeOfEntries[from, nentries, fromSize - 1], by: moveSize];
Move indexes from "from" to "to"
offset ← SizeOfEntries[to, 0, toSize - 1];
FOR i IN [toSize..toSize + nentries) DO
tocore.index[i] ← fromcore.index[i - toSize] - offset
ENDLOOP;
Shifts indexes in "from"
FOR i IN [nentries..fromSize) DO
fromcore.index[i - nentries] ← fromcore.index[i] + moveSize
ENDLOOP;
Set sizes
SetSize[to, toSize + nentries];
SetSize[from, fromSize - nentries];
DBIndexOp.MoveScanIndexLeft[from: from, to: to, nentries: nentries];
DBIndexPage.CheckTag[from.pointer];
DBIndexPage.CheckTag[to.pointer]
};
RemoveFromLeaf: PUBLIC PROC[page: Page, deleting: CARDINAL] RETURNS[State] = TRUSTED {
This works only for a leaf. Takes out the deleting-th entry and compresses.
core: LONG POINTER TO Core ← page.pointer;
pageSizeMinusOne: CARDINAL ← core.size - 1;
DBIndexPage.WritePage[page];
IF deleting # pageSizeMinusOne THEN
{base: LONG POINTER ← @core.index;
deletingAt: CARDINAL ← (base + deleting)^;
size: CARDINAL
(IF deleting = 0 THEN CoreIndexSize ELSE (base + deleting - 1)^) -
deletingAt;
offset: CARDINAL ← (base + pageSizeMinusOne)^;
at: LONG POINTER ← base + offset;
Compress data
ShiftRight[addr: at, by: size, nwords: deletingAt - offset];
Compress index array
ShiftIndex
[page: page, from: deleting, to: pageSizeMinusOne, offset: size,
by: -1]};
Decrement size of the page
core.size ← pageSizeMinusOne;
DBIndexOp.DecrementScanIndex[page: page, atOrAfter: deleting+1];
IF FreeSpace[page] >= HalfPage
THEN RETURN [merge] ELSE RETURN [normal]
};
RemoveLinks: PUBLIC PROC [page: Page] = TRUSTED {
left, right: DBCommon.DBPage;
leftPage, rightPage: Page;
DBIndexPage.WritePage[page];
left ← page.pointer.left;
right ← page.pointer.right;
page.pointer.left← page.pointer.right← DBCommon.NullDBPage; -- to be sure
remove left links
IF left # DBCommon.NullDBPage THEN
{leftPage ← DBIndexPage.GetPage[page.tree, left, page.depth];
leftPage.pointer.right ← right;
DBIndexPage.WriteAndUnlockPage[leftPage]};
remove right links
IF right # DBCommon.NullDBPage THEN
{rightPage ← DBIndexPage.GetPage[page.tree, right, page.depth];
rightPage.pointer.left ← left;
DBIndexPage.WriteAndUnlockPage[rightPage]}
};
ShiftLeft: PROC[addr: LONG POINTER, nwords: CARDINAL, by: CARDINAL] = TRUSTED {
Shifts words of size nwords starting at addr to the left
PrincOpsUtils.LongCopy[from: addr, to: addr - by, nwords: nwords]
};
ShiftRight: PROC[addr: LONG POINTER, nwords: CARDINAL, by: CARDINAL] = TRUSTED {
Shifts words of size nwords starting at addr to the left
IF by = 0 THEN RETURN;   -- special case, never finishes if by=0
WHILE NOT (by >= nwords) DO
PrincOpsUtils.LongCopy[from: addr + nwords - by, to: addr + nwords, nwords: by];
nwords ← nwords - by
ENDLOOP;
PrincOpsUtils.LongCopy[from: addr, to: addr + by, nwords: nwords]
};
ReplaceKey: PUBLIC PROC [p: Page, key: REF TEXT, at: CARDINAL] = TRUSTED {
Replaces the key at "at" by "key" on leaf page
pSize: CARDINAL = p.pointer.size;
start: ItemHandle = CoreAddr[p, pSize - 1];
oldSize: CARDINAL = DBIndexOp.EntrySize[p, at] - 3;
newSize: CARDINAL = (key.length + 1) / 2;
moveSize: CARDINAL = SizeOfEntries[page: p, from: at + 1, to: pSize - 1] + 2;
value is moved
[]← CheckLength[at];
[]← CheckLength[moveSize];
[]← CheckLength[oldSize];
[]← CheckLength[key.length];
DBSegment.WriteLockedPage[p.cache];
IF p.depth = 1 AND at = 0 THEN ERROR OutOfBound;
IF oldSize <= newSize THEN
PrincOpsUtils.LongCopy[from: start, to: start - newSize + oldSize, nwords: moveSize]
ELSE ShiftRight[addr: start, nwords: moveSize, by: oldSize - newSize];
IF newSize > oldSize THEN
DecrementIndexArray[page: p, from: at, to: pSize - 1, by: newSize - oldSize]
ELSE IncrementIndexArray[page: p, from: at, to: pSize - 1, by: oldSize - newSize];
StoreKey[p.pointer, p.pointer.index[at] + 2, key]
};
IncrementIndexArray: PROC [page: Page, from, to, by: CARDINAL] = TRUSTED {
Increments the contents of index array from "from" to "to"
core: LONG POINTER TO Core ← page.pointer;
i: CARDINAL;
[]← CheckLength[by]; []← CheckLength[to]; []← CheckLength[from];
FOR i IN [from..to] DO
core.index[i] ← core.index[i] + by
ENDLOOP
};
DecrementIndexArray: PROC [page: Page, from, to, by: CARDINAL] = TRUSTED {
Decrements the contents of index array from "from" to "to"
core: LONG POINTER TO Core ← page.pointer;
i: CARDINAL;
[]← CheckLength[by]; []← CheckLength[to]; []← CheckLength[from];
FOR i IN [from..to] DO
core.index[i] ← core.index[i] - by
ENDLOOP
};
SetIndex: PROC[page: Page, index: CARDINAL, address: LONG POINTER] = TRUSTED {
offset: CARDINAL ← Basics.LowHalf[address - page.pointer - OverHead];
page.pointer.index[index] ← offset
};
SlideLeafEntries: PROC[in: Page, from: CARDINAL, to: CARDINAL, by: CARDINAL]
RETURNS [LONG POINTER] = TRUSTED {
Slide entries in[from..to] to left, by "by" words, and make a
room for one entry. Returns the address of empty slot
start: ItemHandle = CoreAddr[in, to];
dest: LONG POINTER = start - by;
size: CARDINAL;
IF from > to + 1 THEN ERROR;
IF from > to THEN RETURN [dest];
size ← SizeOfEntries[page: in, from: from, to: to];
PrincOpsUtils.LongCopy[from: start, to: dest, nwords: size];
ShiftIndex[page: in, from: from, to: to, offset: by, by: 1];
RETURN [dest + size]
};
ShiftIndex: PROC[page: Page, from, to: CARDINAL, offset: CARDINAL, by: INTEGER] = TRUSTED {
Shifts right index array index[from..to] by size "by" and adds or subtracts offset
core: LONG POINTER ← @page.pointer.index;
dest: LONG POINTER ← core + by;
i: CARDINAL ← from + by;
IF by > 0 THEN
FOR i DECREASING IN [from..to] DO (dest + i)^ ← (core + i)^ - offset ENDLOOP
ELSE FOR i IN [from..to] DO (dest + i)^ ← (core + i)^ + offset ENDLOOP
};
MoveRightAndInsert: PUBLIC PROC[from: Page, to: Page, after: CARDINAL, at: CARDINAL, key: REF TEXT, value: LONG CARDINAL]
RETURNS [CARDINAL] = TRUSTED {
Assert after<at
We are trying to insert <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
i, j: CARDINAL;
start: ItemHandle ← CoreAddr[from, at];
newSize, size: CARDINAL ← SizeOfEntries[page: from, from: after + 1, to: at];
toCore: LONG POINTER TO Core = to.pointer;
fromCore: LONG POINTER TO Core = from.pointer;
fromEnd: CARDINAL = from.pointer.size - 1;
insertSize: CARDINAL = (key.length + 1) / 2 + 3;
offset: CARDINAL = CoreIndexSize - from.pointer.index[after];
temp: CARDINAL;
DBIndexPage.WritePage[from];
DBIndexPage.WritePage[to];
IF size + insertSize + (fromEnd + 1 - after) + OverHead > FullPage THEN ERROR PageOverflow;
first move from[after+1..at]
temp ← CoreIndexSize - size;
PrincOpsUtils.LongCopy[from: start, to: @toCore.index[temp], nwords: size];
j ← 0;
FOR i IN [after + 1..at] DO
toCore.index[j] ← fromCore.index[i] + offset;
j ← j + 1
ENDLOOP;
toCore.index[j] ← (IF j = 0 THEN CoreIndexSize ELSE toCore.index[j - 1]) - insertSize;
then insert <key,value>
StoreEntry[at: CoreAddr[to, j], key: key, value: value];
j ← j + 1;
then move from[at+1..fromEnd]
start ← CoreAddr[from, fromEnd];
newSize ← SizeOfEntries[page: from, from: at + 1, to: fromEnd];
temp ← temp - insertSize - newSize;
PrincOpsUtils.LongCopy[from: start, to: @toCore.index[temp], nwords: newSize];
FOR i IN [at + 1..fromEnd] DO
toCore.index[j] ← fromCore.index[i] + offset - insertSize;
j ← j + 1
ENDLOOP;
fix size
SetSize[from, after + 1];
SetSize[to, fromEnd - after + 1];
RETURN [at - after - 1]
};
MoveEntriesToRightLeafAfter: PUBLIC PROC[from, to: Page, nentries: CARDINAL] = TRUSTED {
Just like MoveEntriesToRightLeaf, except entries moved from "from" are placed after entries of "to" instead of moving old entries in "to" down.
fromSize: CARDINAL = from.pointer.size;
toSize: CARDINAL = to.pointer.size;
oldToSize: CARDINAL = SizeOfEntries[to, 0, toSize - 1];
at: CARDINAL = fromSize - nentries;
moveSize: CARDINAL = SizeOfEntries[from, at, fromSize - 1];
i, offset: CARDINAL;
fromcore: LONG POINTER TO Core = from.pointer;
tocore: LONG POINTER TO Core = to.pointer;
IF oldToSize + moveSize + OverHead + (toSize + fromSize - at) > FullPage THEN
ERROR PageOverflow;
DBIndexPage.WritePage[from];
DBIndexPage.WritePage[to];
DBIndexPage.CheckTag[from.pointer];
DBIndexPage.CheckTag[to.pointer];
IF nentries = 0 THEN RETURN;
IF nentries > 40 THEN ERROR;
Move entries from "from" to "to"
PrincOpsUtils.LongCopy[from: CoreAddr[from, fromSize - 1], to: CoreAddr[to, toSize - 1] - moveSize, nwords: moveSize];
Move indexes from "from" to "to"
offset ← IF at = 0 THEN 0 ELSE CoreIndexSize - from.pointer.index[at - 1] - oldToSize;
FOR i IN [at..fromSize) DO
tocore.index[i - at + 1] ← fromcore.index[i] + offset
ENDLOOP;
Set sizes and update scan indices to moved entries
SetSize[to, toSize + nentries];
SetSize[from, at];
DBIndexOp.MoveScanIndexRight[from: from, to: to, after: fromSize - nentries - 1];
DBIndexPage.CheckTag[from.pointer];
DBIndexPage.CheckTag[to.pointer]
};
SlideLeafAt: PUBLIC PROC[p: Page, index: CARDINAL, key: REF TEXT, value: LONG CARDINAL] = TRUSTED {
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.
insertSize: CARDINAL = (key.length + 7) / 2;
at: LONG POINTER = SlideLeafEntries[in: p, from: index, to: p.pointer.size - 1, by: insertSize];
DBIndexPage.WritePage[p];
StoreEntry[at: at, key: key, value: value];
SetIndex[page: p, index: index, address: at];
IncrementSize[p];
DBIndexOp.IncrementScanIndex[p, index]
};
CheckLength: PROC[c: CARDINAL] RETURNS[CARDINAL] =
Use to check that cardinals are reasonable in key lengths and indexes into core.
TRUSTED {IF c>250 THEN SIGNAL ThisLooksSuspicious; RETURN[c]};
END.
Change Log
By Cattell September 22, 1982 3:05 pm: Created module.
By Cattell May 27, 1983 2:11 pm: Added more comments.
By Cattell July 19, 1983 2:25 pm: Corrected and added comments.
Changed by Willie-Sue on February 18, 1985
made Cedar, added tioga formatting