Copyright © 1985 by Xerox Corporation. All rights reserved.

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

Basics,

DBCommon,

DBSegment,

DBStoragePage,

DBIndex,

DBIndexMod,

DBIndexOp,

DBIndexPage,

PrincOpsUtils,

Rope;

IMPORTS Basics, DBSegment, DBIndexOp, DBIndexPage, PrincOpsUtils

EXPORTS DBIndexMod =

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

};

"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

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

set sizes

SetSize[to, toSize + nentries];

SetSize[from, at]

};

"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

shift indexes in "from"

FOR i IN [nentries..fromSize) DO

set size

SetSize[to, toSize + nentries];

SetSize[from, fromSize - nentries]

};

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 {

page.pointer.size ← page.pointer.size-1;

IF FreeSpace[page] >= HalfPage THEN RETURN[merge] ELSE RETURN[normal]

END;

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;

Stores the value, key to the page.

TRUSTED BEGIN

StoreEntry[LOOPHOLE[@core.index[insertIndex], ItemHandle], key, value];

END;

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;

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;

Turns the right most byte of p^ to 0

TRUSTED BEGIN p^ ← PrincOpsUtils.BITAND[p^, 177400B]; END;

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

};

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

};

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

};

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]

};

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

Move entries from "from" to "to"

PrincOpsUtils.LongCopy[

Shifts indexes in "to"

FOR i DECREASING IN [0..toSize) DO

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]

};

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

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

Shifts indexes in "from"

FOR i IN [nentries..fromSize) DO

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]

};

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

Decrement size of the page

core.size ← pageSizeMinusOne;

DBIndexOp.DecrementScanIndex[page: page, atOrAfter: deleting+1];

IF FreeSpace[page] >= HalfPage

};

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

remove right links

IF right # DBCommon.NullDBPage THEN

};

Shifts words of size nwords starting at addr to the left

PrincOpsUtils.LongCopy[from: addr, to: addr - by, nwords: nwords]

};

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, to: addr + by, nwords: nwords]

};

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

IF newSize > oldSize THEN

StoreKey[p.pointer, p.pointer.index[at] + 2, key]

};

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

};

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

};

offset: CARDINAL ← Basics.LowHalf[address - page.pointer - OverHead];

page.pointer.index[index] ← offset

};

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]

};

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

ELSE FOR i IN [from..to] DO (dest + i)^ ← (core + i)^ + offset ENDLOOP

};

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] ← (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

fix size

SetSize[from, after + 1];

SetSize[to, fromEnd - after + 1];

RETURN [at - after - 1]

};

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

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

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]

};

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]

};

Use to check that cardinals are reasonable in key lengths and indexes into core.

TRUSTED {IF c>250 THEN SIGNAL ThisLooksSuspicious; RETURN[c]};

made Cedar, added tioga formatting