[Cyan]<CedarChest6.0>Cypress>DBIndexModImpl.mesa!2

File: DBIndexModImpl.mesa

Contents: All DBIndex package database modifications go through this module

Created from: pieces of former DBIndexFilePageImpl, DBIndexOpImpl, DBIndexImpl,

and DBIndexInternalImpl

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, March 19, 1985 6:14:09 pm PST

Donahue, September 5, 1985 4:23:50 pm PDT

DIRECTORY

Basics,

DBCommon,

DBSegment,

DBStoragePagetags,

DBIndexFilePage,

DBIndex,

DBIndexMod,

DBIndexOp,

DBIndexPage,

PrincOpsUtils;

DBIndexModImpl: CEDAR PROGRAM

IMPORTS

Basics,

DBSegment,

DBIndexFilePage,

DBIndexOp,

DBIndexPage,

PrincOpsUtils

EXPORTS

DBIndexMod

BEGIN OPEN DBIndexFilePage;

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;

From former DBIndexImpl

InsertTwoEntriesToEmptyPage: PUBLIC PROC

[page: Page, first: LONG CARDINAL, key: IndexKey, 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: IndexKey, 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: IndexKey, 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]

};

From former DBIndexInternalImpl

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

LongCOPY[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 [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".

Caller must free IndexKey returned.

TRUSTED BEGIN

fromSize: CARDINAL ← from.pointer.size;

moveSize: CARDINAL ← SizeOfEntries[from, at + 1, fromSize - 1] + 2;

splitKey: IndexKey;

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];

creates splitKey

splitKey ← CopyKey[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;

From former DBIndexFilePageImpl

StoreEntryInPage: PROC [

core: LONG POINTER TO Core, insertIndex: CARDINAL, key: IndexKey,

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: IndexKey, 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>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: IndexKey] =

Stores the key in core.index starting at index. Warning: index must point after

the value field of the ItemHandle, if present. The length field of the key will

get moved by the LongCopy below, so we must move 1+(key.length + 1)/2 words.

TRUSTED BEGIN

IF key.length>CoreIndexSize THEN ERROR;

PrincOpsUtils.LongCopy[

from: @key.text, to: @core.index[index], nwords: 1 + (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;

From former DBIndexOpImpl

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 # DBStoragePagetags.BTree THEN ERROR;

rightcore.left ← new.db;

DBSegment.WriteLockedPage[cache];

DBSegment.UnlockPage[cache]}

};

InsertTheFirstLeafEntry: PUBLIC PROC

[page: Page, key: IndexKey, 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: IndexKey, 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: IndexKey, 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: IndexKey, 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