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 {
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 {
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: REF TEXT, 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;
PrincOpsUtils.LongMove[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 [REF TEXT] =
TRUSTED BEGIN
fromSize: CARDINAL _ from.pointer.size;
moveSize: CARDINAL _ SizeOfEntries[from, at + 1, fromSize - 1] + 2;
splitKey: REF TEXT;
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!
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: REF TEXT, value: LONG CARDINAL] =
TRUSTED BEGIN
StoreEntry[LOOPHOLE[@core.index[insertIndex], ItemHandle], key, value];
END;

StoreEntry:  PROC [at: ItemHandle, key: REF TEXT, value: LONG CARDINAL] =
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] =
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] =
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 # 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 {
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: REF TEXT, 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: REF TEXT, 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: REF TEXT, 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



zFile: DBIndexModImpl.mesa
Copyright c 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
"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
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.
move entries from "from" to "to"
move indexes from "from" to "to"
set size
mark pages dirty
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.
Turns the right most byte of p^ to 0
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š
ϣ
™£
Jš
œ0™0š
œ™Jš
œ$™$K™.K™%J˜—š
Οk	˜	J˜J˜	J˜
J˜J˜J˜J˜
J˜J˜Jš
œ˜J˜—šœž
˜Jšžœ9˜@Jšžœ˜J˜—Jšžœ
žœ
˜J˜J˜Jšœžœ˜Jšœžœ˜Jšœ
žœ˜"Jšœžœ˜&Jšœžœ˜J˜Jšœ
žœ˜&Jšœ
žœ˜&Jšœžœ˜0Jšœ
žœ˜'J˜Jšœ
žœžœ
˜Jšœ
žœžœ
˜Jšœžœžœ
˜Jšœžœžœ
˜#Jšœžœžœ˜J˜šΟnœžœ
žœžœ
žœžœ
žœ
žœžœ˜|Jš
œ%™%Jš
œA™AJšœžœ˜Jšœžœ
žœ
žœ˜*J˜Jšžœ žœ
žœ˜:J˜#Jšžœ<˜DJ˜?J˜J˜*J˜J˜—šŸœžœ
žœžœžœžœ˜fJš
œ™Jš
œ-™-Jš
œ#™#Jšœžœ˜)Jšœ
žœ˜(Jšœžœ˜$Jšœžœ˜$Jšœ
žœ˜Jšœžœ˜Jšœ
žœ
žœ
žœ˜/Jšœžœ
žœ
žœ˜*J˜J˜Jšžœžœ
žœ
˜Jšžœžœžœ
žœ˜5J˜8Jš
œ™J˜lJš
œ	™	J˜:Jš
œ ™ J˜jJš
œ™šžœž
œ
žœ
žœ
˜#J˜@Jšžœ˜	—Jš
œ ™ Jšœ	žœžœžœ-˜Kšžœžœžœ
˜J˜1Jšžœ˜	—Jš
œ	™	J˜ J˜J˜J˜—šŸœžœ
žœžœžœžœ˜eJš
œ™Jš
œ+™+Jš
œ!™!Jšœ
žœ˜(Jš	œžœžœžœžœ#˜aJšœžœ˜$Jšœžœ˜)Jšœ
žœ˜Jšœžœ˜Jšœ
žœ
žœ
žœ˜/Jšœžœ
žœ
žœ˜*J˜J˜Jšžœžœ
žœ˜Jšžœžœžœ
žœ
˜4J˜0J˜:Jš
œ™J˜€
Jš
œ%™%J˜€
Jš
œ ™ J˜4šžœžœžœ
˜(J˜5Jšžœ˜	—Jš
œ™šžœžœžœ
˜!J˜@Jšžœ˜	—Jš
œ™J˜ J˜"J˜J˜—š
Ÿœžœ
žœžœžœ
˜RJš
œ$™$Jš
œ.™.Jšžœ
ž˜
Jšœžœ
žœ
žœ˜*Jšœ
žœ˜'Jšœžœ
˜Jšœžœ
˜J˜šžœžœ˜J˜.J˜-Jšžœžœ˜)Jšžœ;˜?Jš
œ
™
Jš
œC˜CJš
œ™J˜T—J˜(Jš
žœžœ
žœžœ
žœ˜EJšžœ
˜J˜—šŸœžœ
žœžœžœžœ˜XJš
œ!™!Jš
œ1™1Jš
œ*™*Jš
œ#™#Jšžœ
ž˜
Jšœ
žœ˜'Jšœ
žœ1˜CJšœ
žœ
˜Jš
œ%™%Jšœžœ
˜Jšœ
žœ
žœ
žœ˜.Jšœžœ
žœ
žœ˜*J˜J˜Jšœ0Οc5˜eJš
œ ™ J˜iJš
œ ™ J˜!Jšžœžœžœ3žœ
˜UJš
œ™J˜J˜Jš
œ™Jšžœ˜Jšžœ
˜J˜—šŸœžœžœ
žœ
žœžœžœ	žœ
žœ˜rJš
œ"™"Jšžœ
ž˜
Jšœžœ4˜GJšžœ
˜J˜—š
Ÿ
œžœžœ	žœ
žœ˜IJš
œΒ
™Β
Jšžœ
ž˜
Jšžœžœžœ
žœ
˜;J˜Jš
œ˜Jš
žœžœ
žœžœžœ˜IJšžœžœžœ˜6Jšžœ
˜J˜—šŸœžœžœ
žœ
žœžœžœ
žœ˜NJš
œ™Jšžœ
ž˜
Jšœžœžœ
žœ
žœžœ
žœ
žœ˜HJšœžœžœ˜,Jšžœžœžœ
žœ
˜;Jš
œM˜MJšœžœžœ4˜xJšžœžœžœ-˜IJšžœ
˜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šžœ-žœ
žœ˜;J˜J˜"J˜——J˜J˜—šŸœžœ
žœžœ	žœ
žœžœ˜aJš
œ'™'Jšœžœ˜-Jšœžœ
žœ
žœ˜*J˜Jšžœžœ
žœ˜+J˜J˜9J˜>J˜J˜—š
Ÿœžœ
žœžœžœ˜TJš
œΧ
™Χ
Jšœ
žœ˜(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šœ	žœžœžœ-˜KJšžœžœžœ2žœ
˜UJš
œ	™	J˜ J˜J˜IJ˜QJ˜$J˜ J˜J˜—š
Ÿœžœ
žœžœžœ˜SJš
œ‘
™‘
Jšœ
žœ˜(Jšœžœ˜$Jšœ
žœ˜Jšœžœ˜Jšœ
žœ
žœ
žœ˜/Jšœžœ
žœ
žœ˜*J˜J˜J˜$J˜"Jšžœžœ
žœ˜Jšžœžœžœ
žœ
˜6J˜0Jš
œ ™ šžœžœ
˜J˜u—Jš
œ%™%J˜rJš
œ ™ J˜+šžœžœžœ
˜(J˜5Jšžœ˜	—Jš
œ™šžœžœžœ
˜!J˜;Jšžœ˜	—Jš
œ	™	J˜ J˜$J˜EJ˜$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šœ
žœ;˜MJš
œ™J˜J˜J˜J˜J˜$Jšžœ
žœžœ
žœ
˜1šžœžœ
˜J˜UJšžœC˜G—šžœžœ
˜J˜MJšžœO˜S—J˜1J˜J˜J˜—šŸœžœžœžœ˜JJš
œ:™:Jšœžœ
žœ
žœ˜+Jšœžœ
˜J˜@šžœžœžœ
˜J˜"Jš
ž˜—J˜J˜—šŸœžœžœžœ˜JJš
œ:™:Jšœžœ
žœ
žœ˜+Jšœžœ
˜J˜@šžœžœžœ
˜J˜"Jš
ž˜—J˜J˜—šŸœžœžœžœ
žœžœ˜NJšœžœ5˜EJ˜"J˜J˜—š
Ÿœžœžœžœžœ
˜LJšžœžœ
žœžœ˜"Jš
œ>™>Jš
œ6™6J˜&Jšœžœ
žœ˜!Jšœžœ
˜Jšžœžœ
žœ˜Jšžœžœ
žœ	˜!J˜4J˜=J˜=Jšžœ˜J˜J˜—šŸ
œžœžœ
žœžœžœ˜[Jš
œR™RJšœžœ
žœ˜*Jšœžœ
žœ˜ Jšœžœ
˜šžœžœ
˜Jš
žœž
œ
žœžœ#žœ
˜M—Jš	žœ
žœžœžœ#ž˜FJ˜J˜—šŸœžœ
žœžœžœžœ	žœ
žœ
˜yJšžœžœžœ˜Jš
œ™Jš
œΡ
™Ρ
Jšœžœ˜J˜(Jšœžœ7˜NJšœžœ
žœ
žœ˜+Jšœ
žœ
žœ
žœ˜/Jšœ	žœ˜+Jšœžœ˜1Jšœžœ.˜>Jšœžœ
˜J˜J˜J˜JšžœAžœ
žœ˜\Jš
œ™J˜J˜LJ˜šžœžœžœ
˜J˜.J˜	Jšžœ˜	—Jšœžœžœžœ$˜WJš
œ™J˜9J˜Jš
œ™J˜!J˜@J˜$J˜Ošžœžœžœ
˜J˜;J˜	Jšžœ˜	—Jš
œ™J˜J˜"Jšžœ˜J˜J˜—š
Ÿœžœ
žœžœžœ˜XJš
œ
™
Jšœ
žœ˜(Jšœžœ˜$Jšœžœ%˜8Jšœžœ˜$Jšœ
žœ*˜<Jšœžœ˜Jšœ
žœ
žœ
žœ˜/Jšœžœ
žœ
žœ˜*šžœGžœ
˜NJšžœ˜—J˜J˜J˜$J˜"Jšžœžœ
žœ˜Jšžœžœ
žœ˜Jš
œ ™ J˜wJš
œ ™ Jšœ	žœžœžœ9˜Wšžœžœžœ
˜J˜5Jšžœ˜	—Jš
œ2™2J˜ J˜J˜RJ˜$J˜ J˜J˜—šŸœžœ
žœžœžœ	žœ
žœžœ˜cJš
œ„
™„
Jšœžœ˜-Jšœžœ
žœP˜`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ώm*