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; 



InsertTwoEntriesToEmptyPage: PUBLIC PROC
[page: Page, first: LONG CARDINAL, key: IndexKey, second: LONG CARDINAL] = TRUSTED {
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 {
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;
ShiftLeft
[addr: CoreAddr[to, toSize - 1], nwords: SizeOfEntries[to, 0, toSize - 1], 
by: moveSize + length]; 
StoreKey[tocore, CoreIndexSize - moveSize - length, key]; 
PrincOpsUtils.LongCopy
[from: CoreAddr[from, fromSize - 1], to: EndAddr[to] - moveSize, 
nwords: moveSize]; 
FOR i DECREASING IN [0..toSize) DO 
tocore.index[i + nentries] _ tocore.index[i] - moveSize - length
ENDLOOP; 
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; 
SetSize[to, toSize + nentries]; 
SetSize[from, at]
}; 

MoveEntriesToLeftInternal: PUBLIC PROC
[from, to: Page, key: IndexKey, nentries: CARDINAL] = TRUSTED {
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]; 
PrincOpsUtils.LongCopy
[from: CoreAddr[from, nentries - 1], 
to: CoreAddr[to, toSize - 1] - length - moveSize, 
nwords: moveSize]; 
ShiftRight [addr: CoreAddr[from, fromSize - 1], 
nwords: SizeOfEntries[from, nentries + 1, fromSize - 1] + 2, 
by: fromShiftSize]; 
offset _ SizeOfEntries[to, 0, toSize - 1] + length; 
FOR i IN [toSize..toSize + nentries) DO 
tocore.index[i] _ fromcore.index[i - toSize] - offset
ENDLOOP; 
FOR i IN [nentries..fromSize) DO 
fromcore.index[i - nentries] _ fromcore.index[i] + fromShiftSize
ENDLOOP; 
SetSize[to, toSize + nentries]; 
SetSize[from, fromSize - nentries]
};


RemoveFromInternal: PUBLIC PROC [page: Page, deleting: CARDINAL] RETURNS [State] =
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;
LongCOPY[from: at, to: at + size, nwords: shiftSize];
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] =
TRUSTED BEGIN
fromSize: CARDINAL _ from.pointer.size;
moveSize: CARDINAL _ SizeOfEntries[from, at + 1, fromSize - 1] + 2;
splitKey: IndexKey;
i, offset: CARDINAL;
fromcore: LONG POINTER TO Core _ from.pointer;
tocore: LONG POINTER TO Core _ to.pointer;
DBIndexPage.WritePage[from];
DBIndexPage.WritePage[to];
splitKey _ CopyKey[Key[from, at]]; -- copy because later split can re-arrange from page!
PrincOpsUtils.LongCopy[
from: CoreAddr[from, fromSize - 1], to: EndAddr[to] - moveSize,
nwords: moveSize];
offset _ FrontSize[from, at] - 2;
FOR i IN [at..fromSize) DO
tocore.index[i - at] _ fromcore.index[i] + offset ENDLOOP;
SetSize[to, fromSize - at];
SetSize[from, at];
RETURN[splitKey];
END;



StoreEntryInPage:  PROC [
core: LONG POINTER TO Core, insertIndex: CARDINAL, key: IndexKey,
value: LONG CARDINAL] =
TRUSTED BEGIN
StoreEntry[LOOPHOLE[@core.index[insertIndex], ItemHandle], key, value];
END;

StoreEntry:  PROC [at: ItemHandle, key: IndexKey, value: LONG CARDINAL] =
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] =
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] =
TRUSTED BEGIN p^ _ PrincOpsUtils.BITAND[p^, 177400B]; END;




IncrementSize: PROC [p: Page] = TRUSTED {
core: LONG POINTER TO Core _ p.pointer;
IF core.size>100 THEN SIGNAL ThisLooksSuspicious;
core.size _ core.size + 1
}; 

DecrementSize: PROC [p: Page] = TRUSTED {
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 {
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 {
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 {
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! 
IF toSize # 0 THEN 
ShiftLeft[
addr: CoreAddr[to, toSize - 1],
nwords: SizeOfEntries[to, 0, toSize - 1], by: moveSize]; 
PrincOpsUtils.LongCopy[
from: CoreAddr[from, fromSize - 1], to: EndAddr[to] - moveSize, 
nwords: moveSize]; 
FOR i DECREASING IN [0..toSize) DO 
tocore.index[i + nentries] _ tocore.index[i] - moveSize
ENDLOOP; 
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; 
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 {
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]; 
IF toSize # 0 THEN 
PrincOpsUtils.LongCopy[
from: CoreAddr[from, nentries - 1], 
to: CoreAddr[to, toSize - 1] - moveSize,
nwords: moveSize]; 
ShiftRight[
addr: CoreAddr[from, fromSize - 1], 
nwords: SizeOfEntries[from, nentries, fromSize - 1],
by: moveSize]; 
offset _ SizeOfEntries[to, 0, toSize - 1]; 
FOR i IN [toSize..toSize + nentries) DO 
tocore.index[i] _ fromcore.index[i - toSize] - offset
ENDLOOP; 
FOR i IN [nentries..fromSize) DO 
fromcore.index[i - nentries] _ fromcore.index[i] + moveSize
ENDLOOP; 
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 {
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; 
ShiftRight[addr: at, by: size, nwords: deletingAt - offset]; 
ShiftIndex
[page: page, from: deleting, to: pageSizeMinusOne, offset: size, 
by: -1]}; 
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 
IF left # DBCommon.NullDBPage THEN 
{leftPage _ DBIndexPage.GetPage[page.tree, left, page.depth]; 
leftPage.pointer.right _ right; 
DBIndexPage.WriteAndUnlockPage[leftPage]}; 
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 {
PrincOpsUtils.LongCopy[from: addr, to: addr - by, nwords: nwords]
}; 

ShiftRight:  PROC[addr: LONG POINTER, nwords: CARDINAL, by: CARDINAL] = TRUSTED {
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 {
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;
[]_ 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 {
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 {
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 {
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 {
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 {
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; 
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; 
StoreEntry[at: CoreAddr[to, j], key: key, value: value]; 
j _ j + 1; 
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; 
SetSize[from, after + 1]; 
SetSize[to, fromEnd - after + 1]; 
RETURN [at - after - 1]
}; 

MoveEntriesToRightLeafAfter: PUBLIC PROC[
from, to: Page, nentries: CARDINAL] = TRUSTED {
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; 
PrincOpsUtils.LongCopy
[from: CoreAddr[from, fromSize - 1], 
to: CoreAddr[to, toSize - 1] - moveSize, nwords: moveSize]; 
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; 
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 {
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] =
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



ΤFile: DBIndexModImpl.mesa
Copyright c 1985 by Xerox Corporation.  All rights reserved.
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
From former DBIndexImpl
"page" is empty and an internal node.
Inserts two entries "first" and "second" with the separator "key"
"from" is to the left of "to"
"key" is the dividing key between from and to
"nentries" are moved (returns if 0)
Shifts entries in "to"
store key
move entries from "from" to "to"
shifts indexes in "to"
move indexes from "from" to "to"
set sizes
"from" is to the right of "to"
key is the dividing key between from and to
"nentries" are moved (0 => no-op)
move entries in "from" to "to"
shifts entries in "from" to the right
move indexes from "from" to "to"
shift indexes in "from"
set size
From former DBIndexInternalImpl
This works only for an internal node
Takes out the deleting-th entry and compresses
Compress data
Compress index array
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.
only the value of the entry is moved.
creates splitKey
move entries from "from" to "to"
move indexes from "from" to "to"
set size
mark pages dirty
From former DBIndexFilePageImpl
Stores the value, key to the page.
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.
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.
Turns the right most byte of p^ to 0
From former DBIndexOpImpl
Increment the size of entries in p
Decrement the size of entries in p
Inserts "new" between "left" and its right sibling
Insert the first entry in an empty page
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".
Shifts entries in "to"
Move entries from "from" to "to"
Shifts indexes in "to"
Move indexes from "from" to "to"
Set sizes
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.
Move entries from "from" to "to"
Shifts entries in "from" to the right
Move indexes from "from" to "to"
Shifts indexes in "from"
Set sizes
This works only for a leaf.  Takes out the deleting-th entry and compresses.
Compress data
Compress index array
Decrement size of the page
remove left links
remove right links
Shifts words of size nwords starting at addr to the left
Shifts words of size nwords starting at addr to the left
Replaces the key at "at" by "key" on leaf page
value is moved
Increments the contents of index array from "from" to "to"
Decrements the contents of index array from "from" to "to"
Slide entries in[from..to] to left, by "by" words, and make a 
room for one entry.  Returns the address of empty slot
Shifts right index array index[from..to] by size "by" and adds or subtracts offset
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
first move from[after+1..at]
then insert <key,value>
then move from[at+1..fromEnd]
fix size
Just like MoveEntriesToRightLeaf, except entries moved from "from"
are placed after entries of "to" instead of moving old entries in "to" down.
Move entries from "from" to "to"
Move indexes from "from" to "to"
Set sizes and update scan indices to moved entries
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.
Use to check that cardinals are reasonable in key lengths and indexes into core.
made Cedar, added tioga formatting
ΚΪ˜š
œ™Icodešœ
Οm
œ1™<—Jš
œK™KJš
œO™OJš
œ™Jš
œW™WJš
œK™KJš
œ0™0š
œ™Jš
œ$™$K™)K™)J˜—š
Οk	˜	J˜J˜	J˜
J˜J˜J˜J˜J˜
J˜J˜J˜—šœž
˜š
ž˜J˜J˜
J˜J˜
J˜J˜
—š
ž˜J˜
—J˜J˜—Jšžœ
žœ˜J˜J˜Jšœžœ˜Jšœžœ˜Jšœ
žœ˜"Jšœžœ˜&Jšœžœ˜J˜Jšœ
žœ˜&Jšœ
žœ˜&Jšœžœ˜0Jšœ
žœ˜'J˜Jšœ
žœžœ
˜Jšœ
žœžœ
˜Jšœžœžœ
˜Jšœžœžœ
˜#Jšœžœžœ˜J˜J˜Jš
œ™˜šΟnœžœ
ž˜(Jšœžœ
žœžœ
žœžœ˜TJš
œ%™%Jš
œA™AJšœžœ˜Jšœžœ
žœ
žœ˜*J˜Jšžœ žœ
žœ˜:J˜#Jšžœ<˜DJ˜?J˜J˜*J˜J˜—šŸœžœ
ž˜'Jšœ*žœžœ˜?Jš
œ™Jš
œ-™-Jš
œ#™#Jšœžœ˜)Jšœ
žœ˜(Jšœžœ˜$Jšœžœ˜$Jšœ
žœ˜Jšœžœ˜Jšœ
žœ
žœ
žœ˜/Jšœžœ
žœ
žœ˜*J˜J˜Jšžœžœ
žœ
˜Jšžœžœžœ
žœ˜5J˜8Jš
œ™˜	˜KJ˜——Jš
œ	™	J˜:Jš
œ ™ ˜˜AJ˜——Jš
œ™šžœž
œ
žœ
žœ
˜#J˜@Jšžœ˜	—Jš
œ ™ Jšœ	žœžœžœ-˜Kšžœžœžœ
˜J˜1Jšžœ˜	—Jš
œ	™	J˜ J˜J˜J˜—šŸœžœ
ž˜&Jšœ*žœžœ˜?Jš
œ™Jš
œ+™+Jš
œ!™!Jšœ
žœ˜(šœžœ˜Jšžœžœžœ#˜F—Jšœžœ˜$Jšœžœ˜)Jšœ
žœ˜Jšœžœ˜Jšœ
žœ
žœ
žœ˜/Jšœžœ
žœ
žœ˜*J˜J˜Jšžœžœ
žœ˜Jšžœžœžœ
žœ
˜4J˜/J˜:Jš
œ™˜˜%J˜2J˜——Jš
œ%™%˜0J˜=J˜—Jš
œ ™ J˜4šžœžœžœ
˜(J˜5Jšžœ˜	—Jš
œ™šžœžœžœ
˜!J˜@Jšžœ˜	—Jš
œ™J˜ J˜"J˜J˜——Jš
œ™˜š
Ÿœžœ
žœžœžœ
˜RJš
œ$™$Jš
œ.™.Jšžœ
ž˜
Jšœžœ
žœ
žœ˜*Jšœ
žœ˜'Jšœžœ
˜Jšœžœ
˜J˜šžœžœ˜J˜.J˜-šžœž˜J˜
—Jšžœ;˜?Jš
œ
™
J˜5Jš
œ™J˜T—J˜(Jš
žœžœ
žœžœ
žœ˜EJšžœ
˜J˜—š
Ÿœžœ
žœžœžœ
˜XJš
œ!™!Jš
œ1™1Jš
œ*™*Jš
œ#™#Jšžœ
ž˜
Jšœ
žœ˜'Jšœ
žœ1˜CJ˜Jš
œ%™%Jšœžœ
˜Jšœ
žœ
žœ
žœ˜.Jšœžœ
žœ
žœ˜*J˜J˜Jš
œ™Jšœ#Οc5˜XJš
œ ™ ˜J˜?J˜—Jš
œ ™ J˜!šžœžœž˜Jšœ2žœ
˜:—Jš
œ™J˜J˜Jš
œ™Jšžœ˜Jšžœ
˜J˜J˜——Jš
œ™˜šŸœžœ˜Jš	œžœ
žœ
žœžœ˜AJšœžœ
žœ˜Jš
œ"™"Jšžœ
ž˜
Jšœžœ4˜GJšžœ
˜J˜—šŸ
œžœ(žœ
žœ˜IJš
œ4™4Jš
œA™AJš
œK™KJšžœ
ž˜
Jšžœžœ
žœ
˜'J˜J˜Jš
žœžœ
žœžœžœ˜HJšžœžœžœ˜5Jšžœ
˜J˜—šŸœžœžœ
žœ
žœžœ˜NJš
œP™PJš
œP™PJš
œL™LJšžœ
ž˜
Jšžœžœ
žœ
˜'˜J˜I—Jšžœžœžœ-˜IJšžœ
˜J˜—šŸœžœžœ
žœ˜Jš
œ$™$Jšžœ
žœžœžœ
˜:J˜J˜——Jš
œ™J˜˜šŸ
œžœ
žœ˜)Jš
œ"™"Jšœžœ
žœ
žœ˜'Jšžœžœ
žœ˜1J˜J˜J˜—šŸ
œžœ
žœ˜)Jš
œ"™"Jšœžœ
žœ
žœ˜'Jšžœžœ
žœ˜1J˜J˜J˜—šŸœžœ
žœžœ˜3Jš
œ2™2Jš
œ˜Jšœ	žœ
žœ
žœ˜-Jšœ
žœ
žœ
žœ˜/Jšœžœ
žœ
žœ˜!J˜J˜(J˜J˜šžœžœ
˜$šœ0žœ˜6Jšžœ1žœ
žœ˜?J˜J˜"J˜——J˜J˜—šŸœžœ
ž˜$Jšœ#žœ
žœžœ˜=Jš
œ'™'Jšœžœ˜-Jšœžœ
žœ
žœ˜*J˜Jšžœžœ
žœ˜+J˜J˜9J˜>J˜J˜—š
Ÿœžœ
žœžœžœ˜TJš
œ=™=Jš
œU™UJš
œC™CJšœ
žœ˜(Jšœžœ˜$Jšœžœ˜$Jšœ
žœ˜Jšœžœ˜Jšœ
žœ
žœ
žœ˜/Jšœžœ
žœ
žœ˜*J˜J˜J˜$J˜"Jšžœžœ
žœ˜Jšžœžœžœ
žœ
˜6Jšœ1 ˜NJš
œ™šžœžœ
˜˜
J˜J˜9——Jš
œ ™ ˜J˜@J˜—Jš
œ™šžœž
œ
žœ
žœ
˜#J˜7Jšžœ˜	—Jš
œ ™ Jšœ	žœžœžœ-˜Kšžœžœžœ
˜J˜1Jšžœ˜	—Jš
œ	™	J˜ J˜J˜IJ˜QJ˜$J˜ J˜J˜—š
Ÿœžœ
žœžœžœ˜SJš
œ>™>Jš
œL™LJš
œ™Jšœ
žœ˜(Jšœžœ˜$Jšœ
žœ˜Jšœžœ˜Jšœ
žœ
žœ
žœ˜/Jšœžœ
žœ
žœ˜*J˜J˜J˜$J˜"Jšžœžœ
žœ˜Jšžœžœžœ
žœ
˜6J˜0Jš
œ ™ šžœžœ
˜˜J˜$J˜(J˜——Jš
œ%™%˜J˜$J˜4J˜—Jš
œ ™ J˜+šžœžœžœ
˜(J˜5Jšžœ˜	—Jš
œ™šžœžœžœ
˜!J˜;Jšžœ˜	—Jš
œ	™	J˜ J˜$J˜EJ˜$J˜ J˜J˜J˜—šŸœžœ
žœžœžœ
žœ˜VJš
œL™LJšœžœ
žœ
žœ˜+Jšœžœ˜+J˜šžœžœ
˜$šœžœ
žœ˜#Jšœžœ˜+šœžœ˜šœ
žœžœžœ˜CJ˜——Jšœžœ˜/Jšœžœ
žœ˜"Jš
œ
™
J˜=Jš
œ™˜
˜AJ˜
————Jš
œ™J˜J˜Ašžœ˜Jšžœ
žœ	žœ
žœ	˜(—J˜J˜—šŸœžœ
žœžœ˜1J˜J˜J˜J˜J˜Jšœ= ˜KJš
œ™šžœžœ
˜#˜>J˜ J˜+——Jš
œ™šžœžœ
˜$˜@J˜J˜*——J˜—J˜šŸ	œžœžœ
žœ
žœžœžœ˜PJš
œ8™8J˜AJ˜J˜—šŸ
œžœžœ
žœ
žœžœžœ˜QJš
œ8™8Jšžœžœ
žœ '˜@šžœ
žœžœ
˜J˜QJ˜Jšžœ˜	—J˜AJ˜J˜—š
Ÿ
œžœ
žœžœžœ˜JJš
œ.™.Jšœžœ˜"J˜,Jšœ	žœ#˜4Jšœ	žœ˜*šœ
žœ˜J˜8—Jš
œ™J˜J˜J˜J˜J˜$Jšžœ
žœžœ
žœ
˜1šžœ˜šžœ
˜˜J˜?——šžœ
˜J˜B——šžœ˜šžœ
˜˜J˜:——šžœ
˜˜J˜;———J˜1J˜J˜J˜—šŸœžœžœžœ˜JJš
œ:™:Jšœžœ
žœ
žœ˜+Jšœžœ
˜J˜@šžœžœžœ
˜J˜"Jš
ž˜—J˜J˜—šŸœžœžœžœ˜JJš
œ:™:Jšœžœ
žœ
žœ˜+Jšœžœ
˜J˜@šžœžœžœ
˜J˜"Jš
ž˜—J˜J˜—šŸœž˜Jš	œžœžœ
žœžœ˜@Jšœžœ5˜EJ˜"J˜J˜—š
Ÿœžœžœžœžœ
˜LJšžœžœ
žœžœ˜"Jš
œ>™>Jš
œ6™6J˜&Jšœžœ
žœ˜!Jšœžœ
˜Jšžœžœ
žœ˜Jšžœžœ
žœ	˜!J˜4J˜=J˜=Jšžœ˜J˜J˜—šŸ
œžœ
˜Jš	œžœ
žœžœžœ˜JJš
œR™RJšœžœ
žœ˜*Jšœžœ
žœ˜ Jšœžœ
˜šžœ˜
šžœ
˜šžœž
œ
žœžœ
˜"J˜"Jšžœ
˜——šžœ
˜šžœžœžœ
˜J˜"Jš
ž˜———J˜J˜—šŸœžœ
žœ
˜ Jšœžœžœ
˜4Jšœžœ
žœ
˜$Jšžœžœžœ˜Jš
œ™Jš
œ:™:Jš
œ/™/Jš
œ=™=Jš
œ*™*Jšœžœ˜J˜(šœžœ˜J˜4—Jšœžœ
žœ
žœ˜+Jšœ
žœ
žœ
žœ˜/Jšœ	žœ˜+Jšœžœ˜1Jšœžœ.˜>Jšœžœ
˜J˜J˜J˜šžœAžœ
˜HJšžœ˜—Jš
œ™J˜J˜LJ˜šžœžœžœ
˜J˜.J˜	Jšžœ˜	—˜Jšœ
žœžœžœ$˜E—Jš
œ™J˜9J˜Jš
œ™J˜!J˜@J˜$J˜Ošžœžœžœ
˜J˜;J˜	Jšžœ˜	—Jš
œ™J˜J˜"Jšžœ˜J˜J˜—šŸœžœ
žœ
˜)Jšœžœžœ˜/Jš
œB™BJš
œL™LJšœ
žœ˜(Jšœžœ˜$Jšœžœ%˜8Jšœžœ˜$Jšœ
žœ*˜<Jšœžœ˜Jšœ
žœ
žœ
žœ˜/Jšœžœ
žœ
žœ˜*šžœGžœ
˜NJšžœ˜—J˜J˜J˜$J˜"Jšžœžœ
žœ˜Jšžœžœ
žœ˜Jš
œ ™ ˜˜%J˜<——Jš
œ ™ ˜	šžœ˜
Jšžœžœ9˜D——šžœžœžœ
˜J˜5Jšžœ˜	—Jš
œ2™2J˜ J˜J˜RJ˜$J˜ J˜J˜—šŸœžœ
ž˜Jš	œžœžœ
žœžœ˜KJš
œR™RJš
œ1™1Jšœžœ˜-šœžœ
žœ˜J˜M—J˜J˜,J˜.J˜J˜&J˜J˜—š
Ÿœžœžœžœ
žœ˜2Jš
œP™PJš
žœžœžœ
žœžœ˜?J˜——Jšžœ
˜J˜J˜
J˜J˜6J˜J˜6J˜J˜@J˜˜*J™"—J˜J˜J˜—…—G>nμ