DIRECTORY
DBCommon, 
DBIndex, 
DBIndexOp,
DBIndexMod, 
DBIndexPage, 
DBIndexScan, 
DBSegment, 
DBStats, 
DBStorage, 
DBStorageConcrete,
DBStorageTuple USING[TIDOfTuple, ConsTupleObject], 
IO,
RefText,
Rope;

DBIndexImpl: CEDAR PROGRAM
IMPORTS 
DBCommon,
DBSegment, 
DBStats, 
DBIndexOp,
DBIndexMod, 
DBIndexPage, 
DBIndexScan, 
DBStorageTuple,
IO,
RefText,
Rope
EXPORTS DBIndex, DBStorage

= BEGIN OPEN DBIndexPage;


IndexScanObject: PUBLIC TYPE = DBStorageConcrete.IndexScanObject; 
IndexScanHandle: TYPE = REF IndexScanObject;

Page: TYPE = DBIndex.Page;
IndexKey: TYPE = DBIndex.IndexKey;
Core: TYPE = DBIndex.Core;
State: TYPE = DBIndex.State;
RealIndexHandle: TYPE = DBIndex.RealIndexHandle;
ItemHandle: TYPE = DBIndex.ItemHandle;

FullPage: CARDINAL = DBIndex.FullPage;
OverHead: CARDINAL = DBIndex.OverHead;

ROPE: TYPE = Rope.ROPE; 


BadBTree: SIGNAL = CODE;
KeyIsNotFound: ERROR = CODE; 
TakeALookAtThis: SIGNAL = CODE; -- for debugging 


DeletionOfNonExistentKey: CARDINAL = 201B; 
ThisIndexWasNotCreated: CARDINAL = 202B; 


CheckFlag: BOOLEAN _ FALSE; -- do checking for illegal B-Tree format after each operation
ExtraCheckFlag: BOOLEAN _ FALSE;  -- check for unusual but not illegal cases
PrintFlag: BOOLEAN _ FALSE;  -- turn on debugging output
PrintBreadth: CARDINAL _ 4; -- for debug output: # key entries to print per page
PrintInternalValues: BOOL _ TRUE; -- for debug output: print values associated with internal keys
PrintLeafValues: BOOL _ FALSE; -- for debug output: print values associated with leaf keys
opCount: INT _ 0; -- counts number of operations for printing purposes
watchForThisKey: ROPE _ NIL; -- prints this key when entered or deleted
stopAtOpCount: INT _ 0; -- signals when get to this op count
deletionTurnedOn: BOOL _ TRUE; -- this should normally be TRUE, to free B-Tree pages
tryRecovery: BOOL _ FALSE; -- tries to recover from bad B-Tree; this should normally be FALSE
prevDB, nextDB: DBCommon.DBPage; -- Used only by check programs



CreateIndex: PUBLIC PROC [x: DBStorage.IndexHandle] = {
DBIndexScan.CreateNewRealIndexHandle[DBStorageTuple.TIDOfTuple[x]]; 
WriteIndexTuple[tuple: x, root: DBCommon.NullDBPage, depth: 0]
}; 

DestroyIndex: PUBLIC PROC [x: DBStorage.IndexHandle] = {
q: RealIndexHandle _ DBIndexScan.GetOldRealIndexHandle[x];
DestroyTree[q]; 
DBIndexScan.DestroyIndexHandle[q]; 
WriteIndexTuple[tuple: x, root: DBCommon.NullDBPage, depth: 0]
};

InsertIntoIndex: PUBLIC PROC[x: DBStorage.IndexHandle, k: ROPE, v: DBStorage.TupleHandle] = TRUSTED {
newKey: REF TEXT;
keyText: REF TEXT = LOOPHOLE[RefText.TrustTextRopeAsText[Rope.Flatten[k]]];
q: RealIndexHandle _ DBIndexScan.GetOldRealIndexHandle[x]; 
newP, overFlow, root: Page; 
state: State; 
tid: DBCommon.TID _ DBStorageTuple.TIDOfTuple[v]; 
size: CARDINAL _ CheckTreeInit[q, "Inserting", k];
DBStats.Inc[DBIndexInsert]; 
IF q.depth = 0 THEN {
newP _ DBIndexPage.CreateEmptyPage[q, 1, -- the level -- q.segment]; 
DBIndexMod.InsertTheFirstLeafEntry[newP, keyText, tid]; 
PutRootPageToIndexHandle[q, newP]; 
IncrementDepth[q]; 
DBIndexScan.PutScanIndex[q, newP]; 
WriteIndexTuple[tuple: x, root: newP.db, depth: 1]; 
DBIndexPage.UnlockPage[newP] }
ELSE { 
root _ GetRootPage[q]; 
[state, overFlow, newKey] _ InsertIntoTree[root, keyText, tid]; 
SELECT state FROM 
deleteFromNextPage => ERROR KeyIsNotFound;
normal => NULL;
split =>  SplitRoot[tuple: x, root: q, overflow: overFlow, splitKey: newKey];
ENDCASE => ERROR; 
DBIndexPage.UnlockPage[root] }; 
CheckTreeFinal[q, size + 1] }; 

DeleteFromIndex: PUBLIC PROC [x: DBStorage.IndexHandle, k: Rope.ROPE, v: DBStorage.TupleHandle] = TRUSTED {
tid: DBCommon.TID = DBStorageTuple.TIDOfTuple[v]; 
q: RealIndexHandle = DBIndexScan.GetOldRealIndexHandle[x];
keyText: REF TEXT = LOOPHOLE[RefText.TrustTextRopeAsText[Rope.Flatten[k]]];
newRoot, overflow, root: Page; 
state: State; 
newKey: REF TEXT; 
size: CARDINAL _ CheckTreeInit[q, "Deleting", k];

DBStats.Inc[DBIndexDelete]; 
IF q.depth = 0 
THEN ERROR DBCommon.InternalError --  Deleting entry from empty index! 
ELSE 
{root _ GetRootPage[q]; 
[state, overflow, newKey] _ DeleteFromTree[root, keyText, tid]; 
SELECT state FROM 
deleteFromNextPage => ERROR KeyIsNotFound;
normal => DBIndexPage.UnlockPage[root];
merge => TRUSTED {
IF root.depth = 1 AND root.pointer.size = 0 
THEN
{IF ExtraCheckFlag THEN SIGNAL TakeALookAtThis;
DBIndexPage.DestroyPage[q.segment, root, root.db]; 
DBIndexScan.DeleteHandle[q]; 
DBIndexScan.ScanForNullTree[q]; 
WriteIndexTuple[tuple: x, root: q.rootDB, depth: 0] } 
ELSE 
IF root.depth > 1 AND root.pointer.size = 1 
THEN 
{IF ExtraCheckFlag THEN SIGNAL TakeALookAtThis;
newRoot _ DeleteRoot[root, q.rootDB]; 
PutRootPageToIndexHandle[q, newRoot]; 
DecrementDepth[q]; 
WriteIndexTuple[tuple: x, root: q.rootDB, depth: q.depth]; 
DBIndexPage.UnlockPage[newRoot] } 
ELSE 
DBIndexPage.UnlockPage[root];
};
split => 
{SplitRoot[tuple: x, root: q, overflow: overflow, splitKey: newKey]; 
DBIndexPage.UnlockPage[root] }
ENDCASE => ERROR }; 
CheckTreeFinal[q, size - 1] }; -- end of DeleteFromIndex

OpenScanIndex: PUBLIC PROC [x: DBStorage.IndexHandle, y: DBStorage.Selection, startPosition: DBStorage.FirstLast] RETURNS [scan: DBStorage.IndexScanHandle] = TRUSTED {
index: CARDINAL; 
page: DBCommon.DBPage; 
q: RealIndexHandle = DBIndexScan.GetOldRealIndexHandle[x]; 
size: CARDINAL = CheckTreeInit[q, "Scanning index from", y.lowerBound];
IF NOT y.lowerBoundInfinity AND NOT y.includeLowerBound THEN
y.lowerBound _ Rope.Concat[y.lowerBound, "\000"];
IF NOT y.upperBoundInfinity AND y.includeUpperBound THEN
y.upperBound _ Rope.Concat[y.upperBound, "\000"];
IF q.depth = 0 THEN {page _ DBCommon.NullDBPage; index _ 0}
ELSE 
IF startPosition = First 
THEN 
IF y.lowerBoundInfinity THEN {page _ SearchTheFirstPage[q]; index _ 0} 
ELSE [page, index] _ Search[q, LOOPHOLE[RefText.TrustTextRopeAsText[Rope.Flatten[y.lowerBound]]]]
ELSE 
IF y.upperBoundInfinity THEN [page, index] _ SearchTheLastPage[q] 
ELSE [page, index] _ Search[q, LOOPHOLE[RefText.TrustTextRopeAsText[Rope.Flatten[y.upperBound]]]]; 
scan _ DBIndexScan.CreateScanHandle[q, y, startPosition, page, index]; 
CheckTreeFinal[q, size]
}; 

NextScanIndex: PUBLIC PROC [x: IndexScanHandle]RETURNS [DBStorage.TupleHandle] = TRUSTED {
page: Page; 
tuple: DBStorage.TupleHandle; 
size: CARDINAL;
IF x=NIL THEN RETURN[NIL]; -- scans set to NIL when released.
size _ CheckTreeInit[x.tree, "NextScanIndex"];
IF x.this = DBCommon.NullDBPage THEN RETURN [NIL]; 
page _ DBIndexPage.GetPage[x.tree, x.this, 1]; 
IF x.index >= page.pointer.size 
THEN { IF page.pointer.right # DBCommon.NullDBPage THEN ERROR; tuple _ NIL }
ELSE {
key: IndexKey _ Key[page, x.index]; 
IF NOT x.upperBoundInfinity AND ( x.includeUpperBound AND Less[x.upperBound, key] OR NOT x.includeUpperBound AND LessEq[x.upperBound, key] ) THEN tuple _ NIL
ELSE {
tuple _ DBStorageTuple.ConsTupleObject[tid: Tid[page, x.index]]; 
page _ IncrementIndex[x, page] } };
DBIndexPage.UnlockPage[page]; 
CheckTreeFinal[x.tree, size]; 
RETURN [tuple]
}; 

NextScanKey: PUBLIC PROC [x: IndexScanHandle]RETURNS [key: DBIndex.IndexKey] = TRUSTED {
page: Page; 
IF x=NIL THEN RETURN[NIL]; -- scans set to NIL when released.
IF x.this = DBCommon.NullDBPage THEN RETURN [NIL]; 
page _ DBIndexPage.GetPage[x.tree, x.this, 1]; 
IF x.index >= page.pointer.size 
THEN { IF page.pointer.right # DBCommon.NullDBPage THEN ERROR; key _ NIL }
ELSE  {
key _ Key[page, x.index]; 
IF NOT x.upperBoundInfinity AND (x.includeUpperBound AND Less[x.upperBound, key] OR NOT x.includeUpperBound AND LessEq[x.upperBound, key]) 
THEN { key _ NIL; x.direction _ finished }
ELSE x.direction _ next };
RETURN [key]
};

PrevScanIndex: PUBLIC PROC[x: IndexScanHandle]RETURNS [tuple: DBStorage.TupleHandle] = {
page: Page; 
size: CARDINAL;
IF x=NIL THEN RETURN[NIL]; -- scans set to NIL when released.
size _ CheckTreeInit[x.tree, "PrevScanIndex"];
IF x.this = DBCommon.NullDBPage THEN RETURN [NIL]; 
page _ DBIndexPage.GetPage[x.tree, x.this, 1]; 
IF x.index = 0 AND NoPreviousPage[page] THEN tuple _ NIL
ELSE {
key: IndexKey _ Key[page, x.index]; 
page _ DecrementIndex[x, page]; 
IF NOT x.lowerBoundInfinity AND ( x.includeLowerBound AND Greater[x.lowerBound, key] OR NOT x.includeLowerBound AND GreaterEq[x.lowerBound, key] ) 
THEN tuple _ NIL
ELSE tuple _ DBStorageTuple.ConsTupleObject[Tid[page, x.index]] }; 
DBIndexPage.UnlockPage[page]; 
CheckTreeFinal[x.tree, size]; 
RETURN [tuple]
}; -- PredScanIndex

PrevScanKey: PUBLIC PROC[x: IndexScanHandle] RETURNS [key: DBIndex.IndexKey] = {
page: Page; 
IF x=NIL THEN RETURN[NIL]; -- scans set to NIL when released.
IF x.this = DBCommon.NullDBPage THEN RETURN [NIL]; 
page _ DBIndexPage.GetPage[x.tree, x.this, 1]; 
IF x.index = 0 AND NoPreviousPage[page] THEN { key _ NIL; x.direction _ finished }
ELSE {
key _ Key[page, x.index];
IF NOT x.lowerBoundInfinity AND (x.includeLowerBound AND Greater[x.lowerBound, key] OR NOT x.includeLowerBound AND GreaterEq[x.lowerBound, key]) 
THEN {key _ NIL; x.direction _ finished}
ELSE x.direction _ prev }; 
RETURN [key]
}; -- PrevScanKey

ThisScanTuple: PUBLIC PROC[x: IndexScanHandle]RETURNS [tuple: DBStorage.TupleHandle] = {
IF x.direction = finished THEN RETURN[NIL];
BEGIN
page: Page _ IF x.direction = next THEN DBIndexPage.GetPage[x.tree, x.this, 1] ELSE DecrementIndex[x, DBIndexPage.GetPage[x.tree, x.this, 1]];
tuple _ DBStorageTuple.ConsTupleObject[tid: Tid[page, x.index]];
IF x.direction = next THEN page _ IncrementIndex[x, page];
DBIndexPage.UnlockPage[page]
END };

IgnoreEntry: PUBLIC PROC[x: IndexScanHandle] = {
page: Page = IF x.direction = next THEN DBIndexPage.GetPage[x.tree, x.this, 1] ELSE DecrementIndex[x, DBIndexPage.GetPage[x.tree, x.this, 1]];
DBIndexPage.UnlockPage[page] };

TupleForKey: PUBLIC PROC[x: DBStorage.IndexHandle, key: Rope.ROPE] RETURNS[tuple: DBStorage.TupleHandle] = TRUSTED {
q: RealIndexHandle = DBIndexScan.GetOldRealIndexHandle[x];
IF q.rootDB = DBCommon.NullDBPage THEN tuple _ NIL
ELSE TRUSTED BEGIN
root: Page = GetRootPage[q];
tuplePage: DBCommon.DBPage;
thisPage: Page;
tupleIndex: CARDINAL;
[tuplePage, tupleIndex] _ SearchTree[root, LOOPHOLE[Rope.Flatten[key]]];
thisPage _ DBIndexPage.GetPage[q, tuplePage, q.depth];
IF tupleIndex >= thisPage.pointer.size OR Less[key, Key[thisPage, tupleIndex]]
THEN tuple _ NIL
ELSE tuple _ DBStorageTuple.ConsTupleObject[Tid[thisPage, tupleIndex]];
DBIndexPage.UnlockPage[thisPage];
DBIndexPage.UnlockPage[root];
END;
DBIndexScan.DeleteHandle[q] };

CallAfterFinishTransaction: PUBLIC PROC [s: DBCommon.Segment] = {
DBIndexPage.DestroyPageList[s]; 
DBIndexScan.FinalizeIndexHandle[s]; 
DBIndexScan.FreeScan[s] };



InsertIntoTree: PROC[page: Page, key: REF TEXT, value: DBCommon.TID] RETURNS [State, Page, REF TEXT] = {
i: CARDINAL;
newKey, newSplitKey: REF TEXT; 
newOverFlow, overFlow: Page; 
q: Page; 
state: State;
IF page.depth = 1 -- leaf --  THEN {
DBStats.Inc[BTreeSearchPage]; 
IF DBIndexOp.OverFlow[page, key] 
THEN {
[overFlow, newKey] _ DBIndexOp.SplitLeaf[page, key, value]; 
RETURN [split, overFlow, newKey] } 
ELSE {
SlideLeaf[page, key, value];
RETURN [normal, NIL, NIL] } } 
ELSE {
DBStats.Inc[BTreeSearchPage]; 
i _ FindTheLastInternalKey[page, key]; 
q _ DBIndexPage.GetPage[page.tree, Value[page, i], page.depth - 1]; 
[state, overFlow, newKey] _ InsertIntoTree[q, key, value]; 
SELECT state FROM 
normal => { DBIndexPage.UnlockPage[q]; RETURN [normal, NIL, NIL] };
split => {
[state, newOverFlow, newSplitKey] _ 
DBIndexOp.InsertInInternalPage[page, i, overFlow.db, newKey]; 
DBIndexPage.UnlockPage[q]; 
DBIndexPage.UnlockPage[overFlow]; 
RETURN [state, newOverFlow, newSplitKey] }
ENDCASE => ERROR}
}; 

SplitRoot: PROC [tuple: DBStorage.TupleHandle, root: RealIndexHandle, overflow: Page, 
splitKey: REF TEXT] = {
newP: Page;
newP _ DBIndexPage.CreateEmptyPage[root, root.depth + 1, root.segment]; 
DBIndexMod.InsertTwoEntriesToEmptyPage[newP, root.rootDB, splitKey, overflow.db]; 
PutRootPageToIndexHandle[root, newP]; 
IncrementDepth[root]; 
DBIndexPage.UnlockPage[overflow]; 
WriteIndexTuple[tuple: tuple, root: newP.db, depth: root.depth]; 
DBIndexPage.UnlockPage[newP]
}; 


DeleteFromTree: PROC[page: Page, key: REF TEXT, tid: DBCommon.TID] RETURNS [State, Page, REF TEXT] = {
i: CARDINAL;
newKey, retKey: REF TEXT; 
overflow, retOverflow, q: Page; 
state: State;
DBIndexPage.CheckTag[page.pointer]; 
IF page.depth = 1 THEN {
DBStats.Inc[BTreeSearchPage]; 
[state, ,] _ DBIndexOp.DeleteFromLeafPage[page, key, tid]; 
DBIndexPage.CheckTag[page.pointer]; 
RETURN [state, NIL, NIL] }; 
DBStats.Inc[BTreeSearchPage]; 
i _ FindTheFirstInternalKey[page, key]; 
DO q _ DBIndexPage.GetPage[page.tree, Value[page, i], page.depth - 1]; 
[state, overflow, newKey] _ DeleteFromTree[q, key, tid]; 
SELECT state FROM 
deleteFromNextPage =>  {
DBIndexPage.UnlockPage[q]; 
i _ i + 1; 
TRUSTED {IF i >= page.pointer.size THEN RETURN [state, overflow, newKey]}
};
normal => { DBIndexPage.UnlockPage[q]; RETURN [normal, NIL, NIL]};
merge => {
[state, overflow, retKey] _ MergeInThisPage[page, q, i]; 
RETURN [state, overflow, retKey] };
split => {
[state, retOverflow, retKey] _ DBIndexOp.InsertInInternalPage[page, i, overflow.db, newKey]; 
DBIndexPage.UnlockPage[q]; 
DBIndexPage.UnlockPage[overflow]; 
RETURN [state, retOverflow, retKey] }
ENDCASE => ERROR
ENDLOOP
}; -- DeleteFromTree

DestroyTree: PROC [q: RealIndexHandle] = {
DestroyBelow: PROC [tree: RealIndexHandle, root: Page] = {
db: DBCommon.DBPage; 
i: CARDINAL; 
q: Page;
IF root.depth = 1 
THEN RETURN -- leaves already freed by parent 
ELSE TRUSTED {
FOR i IN [0..root.pointer.size) DO 
q _ DBIndexPage.GetPage[tree, db _ Value[root, i], root.depth - 1
! DBIndexPage.BadPage => IF tryRecovery THEN LOOP]; 
DestroyBelow[tree, q]; 
DBIndexPage.DestroyPage[tree.segment, q, db]
ENDLOOP
};
}; -- end DestroyBelow
root: Page;
IF q.root=NIL AND q.rootDB=0 THEN RETURN;
root _ GetRootPage[q]; 
DestroyBelow[q, root]; 
DBIndexPage.DestroyPage[q.segment, root, q.rootDB]; 
q.rootDB _ DBCommon.NullDBPage; 
q.root _ NIL; 
q.depth _ 0; 
q.free _ TRUE
}; 


PutRootPageToIndexHandle: PROC [q: RealIndexHandle, p: Page] = {
q.rootDB _ p.db; q.root _ p.cache
}; 

IncrementDepth: PROC [q: RealIndexHandle] = {q.depth _ q.depth + 1}; 

GetRootPage: PROC [q: RealIndexHandle] RETURNS [Page] = {
RETURN[DBIndexPage.GetPage[tree: q, db: q.rootDB, level: q.depth]] };

DeleteRoot: PROC [p: Page, r: DBCommon.DBPage] RETURNS [Page] = {
son: Page _ DBIndexPage.GetPage[p.tree, Value[p, 0], p.depth - 1];
DBIndexPage.DestroyPage[p.tree.segment, p, r]; 
RETURN [son]
}; 

DecrementDepth: PROC [q: RealIndexHandle] = {q.depth _ q.depth - 1}; 

IncrementIndex: PROC [x: IndexScanHandle, p: Page] RETURNS [Page] = TRUSTED {
db: DBCommon.DBPage; 
q: Page;
IF x.index >= p.pointer.size - 1 
THEN {
[q, db] _ GetRightPage[p]; 
IF q = NIL THEN {x.index _ x.index + 1; RETURN [p]}; 
DBIndexPage.UnlockPage[p]; 
x.this _ db; 
x.index _ 0; 
RETURN [q] }
ELSE { x.index _ x.index + 1; RETURN [p] }
}; 

DecrementIndex: PROC [x: IndexScanHandle, p: Page] RETURNS [Page] = TRUSTED {
q: Page; 
db: DBCommon.DBPage;
IF x.index # 0 THEN {x.index _ x.index - 1; RETURN [p]}; 
[q, db] _ GetLeftPage[p]; 
IF q = NIL THEN RETURN [p]; 
DBIndexPage.UnlockPage[p]; 
x.this _ db; 
x.index _ q.pointer.size - 1; 
RETURN [q]
}; 

GetRightPage: PROC [p: Page] RETURNS [Page, DBCommon.DBPage] = TRUSTED {
rightDB: DBCommon.DBPage;
IF (rightDB _ p.pointer.right) = DBCommon.NullDBPage THEN 
RETURN [NIL, DBCommon.NullDBPage]; 
RETURN [DBIndexPage.GetPage[p.tree, rightDB, 1], rightDB]
}; 

GetLeftPage: PROC [p: Page] RETURNS [Page, DBCommon.DBPage] = TRUSTED {
leftDB: DBCommon.DBPage;
IF (leftDB _ p.pointer.left) = DBCommon.NullDBPage THEN 
RETURN [NIL, DBCommon.NullDBPage]; 
RETURN [DBIndexPage.GetPage[p.tree, leftDB, 1], leftDB]
}; 



SlideLeaf: PROC [p: Page, key: REF TEXT, value: LONG CARDINAL] = {
index: CARDINAL _ FindTheLastLeafKey[p, key];
DBIndexMod.SlideLeafAt[p, index, key, value]
}; 

MergeInThisPage: PROC [p: Page, son: Page, index: CARDINAL] RETURNS [State, Page, REF TEXT] = {
state: State; 
page: Page; 
key: REF TEXT;
IF son.depth = 1 
THEN [state, page, key] _ DBIndexOp.MergeInLeafPage[p, son, index] 
ELSE  [state, page, key] _ MergeInInternalPage[p, son, index]; 
IF state = delete THEN 
{state _ DBIndexMod.RemoveFromInternal[p, index]; DestroyThisPage[son]}
ELSE DBIndexPage.UnlockPage[son]; 
RETURN [state, page, key]
}; 

MergeInInternalPage: PROC [parent: Page, son: Page, index: CARDINAL] RETURNS [State, Page, REF TEXT] = TRUSTED {
freeSon: CARDINAL _ FreeSpace[son]; 
i: CARDINAL; 
newKey, tempKey: REF TEXT; 
sizeSon: CARDINAL _ son.pointer.size; 
state: State; 
overflow: Page;
IF index # parent.pointer.size - 1 THEN {-- balance the son with the right page
right: Page _ DBIndexPage.GetPage[parent.tree, Value[parent, index + 1], son.depth]; 
IF MergableToRightInternal
[parent: parent, leftFree: freeSon, rightFree: FreeSpace[right], 
leftAt: index] THEN {
DBIndexMod.MoveEntriesToRightInternal[from: son, to: right, key: DBIndexOp.RopeForKey[Key[parent, index + 1]], nentries: sizeSon]; 
DBIndexPage.UnlockPage[right]; 
RETURN [delete, NIL, NIL] }; 
i _ JustOver[right, DBIndex.HalfPage - FrontSize[son, sizeSon - 1] - sizeSon]; 
IF i = 0 OR i >= right.pointer.size - 1 THEN
{DBIndexPage.UnlockPage[right]; RETURN[normal, NIL, NIL]}; -- ... so do nothing
tempKey _ DBIndexOp.RopeForKey[Key[right, i]];
DBIndexMod.MoveEntriesToLeftInternal[from: right, to: son, key: DBIndexOp.RopeForKey[Key[parent, index + 1]], nentries: i]; 
DBIndexPage.UnlockPage[right]; 
[state, overflow, newKey] _ DBIndexOp.ChangeKey[parent, tempKey, index + 1] } 
ELSE 
{-- no right brother: balance with the left
left: Page _ 
DBIndexPage.GetPage[parent.tree, Value[parent, index - 1], son.depth]; 
IF MergableToLeftInternal
[parent: parent, leftFree: FreeSpace[left], rightFree: freeSon, 
rightAt: index] THEN {
DBIndexMod.MoveEntriesToLeftInternal[from: son, to: left, key: DBIndexOp.RopeForKey[Key[parent, index]], nentries: sizeSon]; 
DBIndexPage.UnlockPage[left]; 
RETURN [delete, NIL, NIL] }; 
i _ JustOver[left, DBIndex.HalfPage];
IF left.pointer.size = i + 1 OR  i =  0  THEN
{DBIndexPage.UnlockPage[left]; RETURN[normal, NIL, NIL]}; 
tempKey _ DBIndexOp.RopeForKey[Key[left, i + 1]]; 
DBIndexMod.MoveEntriesToRightInternal
[from: left, to: son, key: DBIndexOp.RopeForKey[Key[parent, index]], 
nentries: left.pointer.size - i - 1]; 
DBIndexPage.UnlockPage[left]; 
[state, overflow, newKey] _ DBIndexOp.ChangeKey[parent, tempKey, index] }; 
RETURN [state, overflow, newKey]
}; 

MergableToRightInternal: PROC [parent: Page, leftFree, rightFree: CARDINAL, leftAt: CARDINAL] RETURNS [BOOLEAN] = TRUSTED {
key: IndexKey _ Key[parent, leftAt+1]; 
length: CARDINAL _ (key.length + 3) / 2;
RETURN [rightFree + leftFree + OverHead > FullPage + length]
}; 

MergableToLeftInternal: PROC [parent: Page, leftFree, rightFree: CARDINAL, rightAt: CARDINAL] RETURNS [BOOLEAN] = TRUSTED {
key: IndexKey _ Key[parent, rightAt]; 
length: CARDINAL _ (key.length + 3) / 2;
RETURN [rightFree + leftFree + OverHead > FullPage + length]
}; 

NoPreviousPage: PROC [page: Page] RETURNS [BOOLEAN] = TRUSTED {
RETURN [page.pointer.left = DBCommon.NullDBPage]
};

DestroyThisPage: PROC [page: Page] = TRUSTED
BEGIN
IF page.pointer.size#0 THEN SIGNAL TakeALookAtThis;
IF page.pointer.left#DBCommon.NullDBPage
OR page.pointer.right#DBCommon.NullDBPage THEN
SIGNAL TakeALookAtThis; -- trying to destroy leaf without calling DBIndexOp.RemoveLinks
IF deletionTurnedOn THEN DBIndexPage.DestroyPage[page.tree.segment, page, page.db]
ELSE DBIndexPage.UnlockPage[page];
END;



Index: PROC [x: IndexScanHandle] RETURNS [CARDINAL] = {RETURN [x.index]}; 


Search: PROC [r: RealIndexHandle, y: REF TEXT] RETURNS [DBCommon.DBPage, CARDINAL] = {
p: Page _ GetRootPage[r]; 
db: DBCommon.DBPage; 
i: CARDINAL;
[db, i] _ SearchTree[p, y]; 
DBIndexPage.UnlockPage[p]; 
RETURN [db, i] };

SearchTree: PROC [page: Page, key: REF TEXT] RETURNS [db: DBCommon.DBPage, i: CARDINAL] = {
son: Page; 
temp: DBCommon.DBPage; 
GotoRightKey: PROC = TRUSTED {
core: LONG POINTER TO Core _ page.pointer;
IF core.right = DBCommon.NullDBPage THEN RETURN; 
db _ core.right; 
i _ 0
};
IF page.depth = 1 THEN -- leaf -- 
{db _ page.db; 
i _ FindTheFirstLeafKey[page, key]; 
TRUSTED {IF i = page.pointer.size THEN GotoRightKey[] }; 
RETURN [db, i]}; 
i _ FindTheFirstInternalKey[page, key]; 
son _ DBIndexPage.GetPage[page.tree, temp _ Value[page, i], page.depth - 1]; 
[db, i] _ SearchTree[son, key]; 
DBIndexPage.UnlockPage[son]; 
RETURN [db, i]
}; 

SearchTheFirstPage: PROC [r: RealIndexHandle] RETURNS [DBCommon.DBPage] = {
p: Page; 
db: DBCommon.DBPage;
IF r.depth = 1 THEN RETURN [r.rootDB]; 
p _ GetRootPage[r]; 
db _ SearchTheFirstTree[p]; 
DBIndexPage.UnlockPage[p]; 
RETURN [db]
}; 

SearchTheFirstTree: PROC [p: Page] RETURNS [DBCommon.DBPage] = {
db: DBCommon.DBPage;
IF p.depth = 2 THEN RETURN [Value[p, 0]] 
ELSE {
son: Page _ DBIndexPage.GetPage[p.tree, Value[p, 0], p.depth - 1]; 
db _ SearchTheFirstTree[son]; 
DBIndexPage.UnlockPage[son]; 
RETURN [db] }
}; 

SearchTheLastPage: PROC [r: RealIndexHandle] RETURNS [DBCommon.DBPage, CARDINAL] = {
p: Page _ GetRootPage[r]; 
db: DBCommon.DBPage; 
i, s: CARDINAL;
IF r.depth = 1 THEN 
TRUSTED {s _ p.pointer.size; DBIndexPage.UnlockPage[p]; RETURN [r.rootDB, s]}; 
[db, i] _ SearchTheLastTree[p]; 
DBIndexPage.UnlockPage[p]; 
RETURN [db, i]
}; 

SearchTheLastTree: PROC [p: Page] RETURNS [DBCommon.DBPage, CARDINAL] = TRUSTED {
l: CARDINAL _ p.depth; 
s: CARDINAL _ p.pointer.size; 
index, sonSize: CARDINAL; 
sonDB: DBCommon.DBPage _ Value[p, s - 1]; 
son: Page; 
db: DBCommon.DBPage;
son _ DBIndexPage.GetPage[p.tree, sonDB, l - 1]; 
IF l = 2 THEN {
sonSize _ son.pointer.size;
DBIndexPage.UnlockPage[son];
RETURN [sonDB, sonSize] } 
ELSE {
[db, index] _ SearchTheLastTree[son];
DBIndexPage.UnlockPage[son];
RETURN [db, index] }
}; 


WriteIndexTuple: PROC [tuple: DBStorage.TupleHandle, root: DBCommon.DBPage, depth: CARDINAL] = {
tid: DBCommon.TID = DBStorageTuple.TIDOfTuple[tuple];
page: DBCommon.DBPage = DBCommon.DecomposeTID[tid].page;
segment: DBCommon.SegmentID = DBSegment.SegmentIDFromDBPage[page];
ttr: DBIndexPage.TupleTree = NEW[DBIndexPage.TupleTreeRecord_ [root, depth, tid, segment]];
DBIndexPage.WriteIndexObject[tuple, ttr]
}; 


CheckTreeInit: PROC [q: RealIndexHandle, op: ROPE, item: ROPE _ NIL] RETURNS [size: CARDINAL] = {
prevDB _ DBCommon.NullDBPage; 
IF NOT CheckFlag THEN RETURN;
opCount_ opCount+1;
IF opCount=stopAtOpCount THEN SIGNAL TakeALookAtThis;
IF watchForThisKey#NIL AND
watchForThisKey.Equal[item.Substr[0, watchForThisKey.Length[]]] THEN
WriteHeaderStat[Rope.Cat["******Monitored key: ", op], item]; 
IF PrintFlag THEN WriteHeaderStat[op, item];
IF q.depth = 0 THEN RETURN [0] 
ELSE {
root: Page _ GetRootPage[q]; 
temp: IndexKey;
savePrintingFlag: BOOL_ PrintFlag;
PrintFlag_ FALSE;  -- only do printing during CheckTreeFinal, not CheckTreeInit 
[size, temp] _ CheckPage[root, NIL]; 
PrintFlag_ savePrintingFlag;
DBIndexPage.UnlockPage[root] }
}; 

CheckTreeFinal: PROC [q: RealIndexHandle, size: CARDINAL] = {
sonSize: CARDINAL;
prevDB _ DBCommon.NullDBPage; 
IF NOT CheckFlag THEN RETURN; 
IF q.depth = 0 THEN 
IF size # 0 THEN SIGNAL BadBTree ELSE RETURN; 
{root: Page _ GetRootPage[q]; 
temp: IndexKey; 
[sonSize, temp] _ CheckPage[root, NIL]; 
IF sonSize # size THEN SIGNAL BadBTree; 
DBIndexPage.UnlockPage[root]}; 
IF nextDB # DBCommon.NullDBPage THEN SIGNAL BadBTree
}; 

CheckPage: PROC [page: Page, start: IndexKey] RETURNS [size: CARDINAL, end: IndexKey] = TRUSTED {
er: IndexKey; 
son: Page; 
i, sonSize: CARDINAL;
size _ 0; 
CheckCacheLock[page.db, page.cache]; 
CheckPageSize[page]; 
IF page.depth=0 THEN SIGNAL BadBTree;
IF page.depth = 1 THEN 
{[size, end] _ CheckLeafPage[page, start]; RETURN}; 
IF PrintFlag THEN WritePageStat[page];
IF page.pointer.size=0 -- empty pages never permitted
OR page.pointer.size=1 -- only children of internal pages not permitted
OR page.pointer.size>1000 -- probably a subtraction from zero
THEN SIGNAL BadBTree;
CheckInternalEntries[page]; 
son _ DBIndexPage.GetPage[page.tree, Value[page, 0], page.depth - 1]; 
[sonSize, end] _ CheckPage[son, start]; 
size _ size + sonSize; 
DBIndexPage.UnlockPage[son]; 
FOR i IN [1..page.pointer.size) DO 
er _ Key[page, i]; 
IF end # NIL AND NOT LessEq[RefText.TrustTextAsRope[DBIndexOp.RopeForKey[er]], end] THEN SIGNAL BadBTree; 
son _ DBIndexPage.GetPage[page.tree, Value[page, i], page.depth - 1]; 
[sonSize, end] _ CheckPage[son, er]; 
size _ size + sonSize; 
DBIndexPage.UnlockPage[son]
ENDLOOP
}; 

CheckLeafPage: PROC [page: Page, start: IndexKey] RETURNS [size: CARDINAL, end: IndexKey] = TRUSTED {
i: CARDINAL; 
prevdesc: IndexKey _ start; 
left, right: DBCommon.DBPage;
left _ page.pointer.left; 
right _ page.pointer.right; 
IF left # prevDB THEN SIGNAL BadBTree; 
prevDB _ page.db; 
nextDB _ right; 
size _ 0; 
IF PrintFlag THEN WritePageStat[page];
IF page.pointer.size=0 OR page.pointer.size>1000 THEN SIGNAL BadBTree;
CheckLeafEntries[page]; 
FOR i IN [0..page.pointer.size) DO 
end _ Key[page, i]; 
size _ size + 1; 
IF prevdesc # NIL AND NOT LessEq[RefText.TrustTextAsRope[DBIndexOp.RopeForKey[end]], prevdesc] THEN SIGNAL BadBTree; 
prevdesc _ end
ENDLOOP
}; 

WriteHeaderStat: PROC [op: ROPE, item: ROPE] = {
debugStream: IO.STREAM_ DBCommon.GetDebugStream[];
debugStream.PutF["**Op #%g: %g %g\n", IO.int[opCount], IO.rope[op], IO.rope[item]]
}; 

WritePageStat: PROC [page: Page] = TRUSTED {
depth: CARDINAL _ page.depth;
debugStream: IO.STREAM_ DBCommon.GetDebugStream[];
IF depth>10 THEN SIGNAL TakeALookAtThis;
THROUGH [0..5-depth) DO 
debugStream.PutF[" "]; 
ENDLOOP; 
debugStream.PutF["%8bB (%2d):", IO.card[page.db], IO.card[page.pointer.size]];
FOR i: CARDINAL IN [0..page.pointer.size) DO WriteEntry[page, i] ENDLOOP;
debugStream.PutChar['\n];
}; 

WriteEntry: PROC[page: Page, entryNum: CARDINAL] = TRUSTED {
entry: ItemHandle = CoreAddr[page, entryNum];
debugStream: IO.STREAM = DBCommon.GetDebugStream[];
IF entryNum#0 OR page.depth=1 THEN
BEGIN -- non-leaf pages have no key for the zero-th entry, so do only leaves & non-0th entries
debugStream.PutChar[' ];
IF entry.length>DBIndex.CoreIndexSize THEN
debugStream.PutF[" ! entry too long(%g) ! ", IO.card[entry.length]]
ELSE
FOR j: CARDINAL IN [0..entry.length) DO
WriteChar[debugStream, entry.text[j]] ENDLOOP;
END;
IF PrintInternalValues AND page.depth#1 OR PrintLeafValues AND page.depth=1 THEN
debugStream.PutF[" (%bB)", IO.card[entry.value]];
};

WriteKey: PROC[entry: IndexKey] = TRUSTED {
debugStream: IO.STREAM_ DBCommon.GetDebugStream[];
debugStream.PutF["(length %g): ", IO.int[entry.length]];
FOR j: CARDINAL IN [0..entry.length) DO WriteChar[debugStream, entry.text[j]] ENDLOOP;
debugStream.PutChar['\n];
};

WriteItem: PROC[entry: ItemHandle] = TRUSTED {
debugStream: IO.STREAM_ DBCommon.GetDebugStream[];
debugStream.PutF["(length %g): ", IO.int[entry.length]];
FOR j: CARDINAL IN [0..entry.length) DO WriteChar[debugStream, entry.text[j]] ENDLOOP;
debugStream.PutChar['\n];
};

WriteChar: PROC[stream: IO.STREAM, char: CHAR] = {
i: CARDINAL = LOOPHOLE[char];
IF char>176C OR char<040C THEN stream.PutF["\\\\%g", IO.card[i]]
ELSE stream.PutChar[char]
};


CheckPageSize: PROC [page: Page] = TRUSTED {
IF page.pointer.size = 0 THEN SIGNAL BadBTree
}; 

CheckCacheLock: PROC [db: DBCommon.DBPage, cache: DBCommon.CacheHandle] = {
IF DBSegment.LockCount[db, cache] # 1 THEN SIGNAL BadBTree;
}; 

CheckLeafEntries: PROC [page: Page] = TRUSTED {
endIndex: LONG POINTER TO UNSPECIFIED _ EndAddr[page]; 
entry: ItemHandle; 
i: CARDINAL;
FOR i IN [0..page.pointer.size) DO 
entry _ CoreAddr[page, i]; 
IF @entry.text + (entry.length + 1) / 2 # endIndex THEN SIGNAL BadBTree; 
endIndex _ entry
ENDLOOP
};

CheckInternalEntries: PROC [page: Page] = TRUSTED {
endIndex: LONG POINTER TO UNSPECIFIED _ EndAddr[page] - 2; 
entry: ItemHandle; 
i: CARDINAL;
FOR i IN [1..page.pointer.size) DO 
entry _ CoreAddr[page, i]; 
IF @entry.text + (entry.length + 1) / 2 # endIndex THEN SIGNAL BadBTree; 
endIndex _ entry
ENDLOOP
};


DBIndexScan.InitScan[];

END. 

Change Log:

Added to check page tag in CreateRootPage
by Suzuki November 24, 1980  9:06 AM

Added to PutScanIndex in InsertIntoIndex
by Suzuki November 24, 1980  10:55 AM

Changed DeleteFromIndex so that if there is no element as the result of removing, the tree is destroyed
by Suzuki November 24, 1980  10:55 AM

Changed OpenScanIndex so that if the tree is empty, just create RealScanObject
by Suzuki November 24, 1980  10:55 AM

Added NormalizeKey so that the last byte of the last word of the string is 0 if the length is odd
by Suzuki November 24, 1980  4:40 PM

Added a statement to set core.size in InsertTwoEntriesToEmptyPage
by Suzuki November 25, 1980  8:35 AM

Added CheckTreeInit & CheckTreeFinal
by Suzuki November 28, 1980  4:19 PM

Changed the definition of offset in MoveEntriesToRightInternal so that it works even when the entire page is moved
by Suzuki December 2, 1980  10:08 AM

Renamed Split to SplitInternal 
by Suzuki:  December 3, 1980  10:14 AM 

Allocate storage from DBHeapStorage, define FreeIndexKey, use CWF for printing.
by MBrown:  February 27, 1981  5:56 PM 

Changed DBIndexPage.WriteAndUnlockPage to DBIndexPage.UnlockPage.  Added WriteLockedPage in MoveEntriesTORightInternal and MoveEntriesToLeftInternal.
by Suzuki:   2-Apr-81 15:41

Converted to Cedar
by Cattell: 6-Jul-81 19:12:36

Use IOStream for printing.
by Cattell:  11-Dec-81 10:06:11

DeleteFromIndex should generate ERROR KeyIsNotFound when state = deleteFromNextPage.  Also, ran through mesa formatter because the TABs screwed up Tioga's formatting.
by Cattell:  May 6, 1982 6:09 pm

DestroyTree didn't work when all the entries had been deleted from the tree, because the root page simply disappears in this case and GetRootPage does a DBSegment.ReadPage[0, NIL] (why doesn't ReadPage complain?).  GetRootPage failed on pointer.tag.pageTag # DBStoragePagetags.BTree check.
by Cattell:  May 25, 1982 6:27 pm

Put in checks for empty pages because zero-size pages aren't being cleaned up, and added other debugging checks.   Added some comments to procs, will add more.
by Cattell: May 27, 1982 11:01 am

Added set of printing routines, extended WritePageStat to print individual keys and values.  Added global variables for various debugging and printing flags.  Removed most of the 8 OPENs (!) in the module header.  Made printing procedures more robust.  Check for unusually large keys.
by Cattell: June 19, 1982 1:30 pm

Fixed two bugs in MergeInInternalPage.  Before calling MergeEntriesToLeftInternal, must COPY Key[right, i] else the bits move out from under it and a garbage key is later stored in a parent page.  Also, a similar problem when calling MergeEntriesToRightInternal.  I'm not sure keys are always being DE-allocated when they are allocated, but I traced up all the potential lines of call from MergeInInternalPage, InsertInThisPage, DeleteFromTree, etc., and found no error assuming the procedures in DBIndexInternalImpl are correct.  Added more comments, this module still badly needs reasonable documentation.
by Cattell: June 20, 1982 6:15 pm

Changed by Willie-Sue on June 25, 1982 9:21 am

Changed by Willie-Sue on July 7, 1982 11:01 am

Changed by Cattell on July 26, 1982 1:03 pm

Changed by Cattell on July 28, 1982 12:25 pm

Changed by Cattell on August 2, 1982 12:34 pm

Changed by Cattell on August 2, 1982 12:55 pm

Changed by Cattell on August 4, 1982 9:14 am

Changed by Cattell on August 5, 1982 5:55 pm

Changed by Cattell on August 6, 1982 4:53 pm

Changed by Cattell on August 18, 1982 1:00 pm

Changed by Cattell on August 19, 1982 8:13 am

Changed by Cattell on August 19, 1982 10:26 am

Changed by Cattell on August 19, 1982 7:03 pm

Changed by Cattell on August 20, 1982 12:15 pm

Changed by Cattell on September 21, 1982 8:45 pm

Changed by Cattell on September 23, 1982 10:28 am

Changed by Cattell on January 17, 1983 6:20 pm

Changed by Willie-Sue on February 18, 1985









*vFile: DBIndexImpl.mesa
Copyright c 1985 by Xerox Corporation.  All rights reserved.
Contents: Main portion of DBIndex B-Tree package, exported to DBStorage
Top-level procs: CreateIndex, InsertIntoIndex, OpenScanIndex, etc.
Last edited by:
Suzuki,  2-Apr-81 15:39:29
MBrown, February 27, 1981  10:27 PM
Cattell,  December 20, 1983 12:54 pm
Willie-Sue, February 18, 1985 1:30:09 pm PST
Widom, September 4, 1985 9:14:29 pm PDT
Donahue, June 20, 1986 9:25:49 am PDT
Types
Signals
Constants
Global vars (mainly for debugging)
Public procs
Destroys the tree itself and the index handle but not the tuple the latter is stored in
Deleted last entry in index (on root page).  Destroy the root page. 
One entry left on a non-root page; want to merge it.
Note that we fetch the tuple currently ref'd by x and THEN increment the scan to the next tuple, as the convention is that x already refs the next tuple to scan.
Note that we fetch the tuple currently ref'd by x and THEN increment the scan to the next tuple, as the convention is that x already refs the next tuple to scan.
Decrement scan and then fetch tuple ref'd by x.
Private Procedures
Insertion
Inserts <key, value> into the tree emanating from page a[0]<=key. Caller must deallocate IndexKey returned.
i=0&key<a[1] | i<a.length-1&a[i]<=key<a[i+1] | i=a.length-1&a[i]<=key
Splits the root into two and creates another page with two entries, root and overflow
Deletion
Deletes the entry with given key.  If multiple entries, then the entry with the value tid is deleted.  Deletion has difficult problems in cases  like ours, where we allow multiple entries with the same key.  If we find the entry at the beginning of the page, there is a  possibility that the same key exists in the left page.  Therefore,  the search algorithm is that in every internal page, look for the  left most key which has the same or equal value to the argument  key.  If the same, go down the left of the key; if greater go  down the right.
i=0&k<=a[i] OR 0<i<max[a]&a[i-1]<k<=a[i] OR i=max[a]&a[i]<key;
Deallocates all file pages of Btree
Deallocates all file pages emanating from this page. The root page is not destroyed.  If there is no root page (an empty B-Tree), simply return.
Sets DBPage and CacheHint of root
p contains one element.  Deletes p and returns the son
obtain the first item
Increments the index of scan.  If it falls off the page, then the right page is fetched and
returned.  The original page is deallocated in that case.
Returns the left page if the previous element is in the left page
p is a leaf page.  Reads in the right page.  If no right page, returns NIL
p is a leaf page.  Reads in the left page.  If no left page, returns NIL
Internal movement of Btree pages
Shifts part of entries in p and inserts, key and value It is guranteed that there won't be any overflow.
son is the index-th entry in p. son is sparse, so balance it. Returns normal if p is normal, delete if p needs balancing, split if p needs splitting, merge if p is less than half full This procedure does a UnlockPage or DestroyPage on son, caller should not touch it. Caller must free IndexKey returned.
"son" is an internal page. "son" is the index-th entry in "parent" "son" is sparse, so balance it. Returns normal if son is normal, delete if son needs balancing, split if son needs splitting, Caller must deallocate IndexKey returned.
We balance son with its right brother except in the unusual case in which it has no right brother (when index=parent.pointer.size-1).  There will always be a left or right brother because we don't permit "only child" leaf or internal pages.
move ALL entries from son to right; caller will delete son
Move zero or more entries from right to son to balance
If move would move no entries, or would leave zero or one entry on right,
then don't do it: return and leave tree as is.  We are moving i entries.
move ALL entries from son to left; caller will delete son
Move zero or more entries from left to son to balance, leaving i+1 in left:
If JustOver would have us move zero entries, or all but one entry in left,
then don't do it: return and leave tree as is.
"left" is the leftAt-th son of "parent" and "right" is just to the right of "left".  
Returns TRUE iff left and right can be merged.
Space used after merging less than a FullPage?  Following is equivalent to val returned:
(FullPage - leftFree) + (FullPage - rightFree) - Overhead + length < FullPage
"right" is the rightAt-th son of "parent" and "left" is just to the left of "right".   Returns TRUE iff left and right can be merged.
Does some checks, then call the real DestroyPage; use for pages removed from B-Tree. Currently only called by MergeInThisPage, we call directly if destroying whole tree.
Manipulations on IndexScanHandles
Search
Returns the index i such that db[i-1]<y<=db[i]
Returns the index i such that db[i-1]<key<=db[i]
Assigns <dbpage of right page, and 0> if there is a right page. Do nothing is there is no right page
Index tuple 
Writes out the new information into database
Check procedures
Checks tree for proper syntactic form. Note: page depth is 1 for leaf nodes, and for internal tree nodes depth is height of the tree (max distance from leaves).  If the tree is empty, then q.depth=0 and there is NO root node (the root node is allocated/deallocated when the first/last entry is inserted/deleted).
Debugging routine: check that this page of index and its descendants ok
Write page to debug stream, on one indented line, including up to PrintBreadth entries.
For calling from the debugger; print the whole key rather than 1st 10 chars as above
For calling from the debugger; print the whole key rather than 1st 10 chars as above
Main body
IOStream => IO
use DBCommon.GetDebugStream[]
Added WriteHeaderStat, opCount, fixed bug in writing leaf pages, changed CheckTreeInit to take operation, print header but not print tree till CheckTreeFinal.  SIGNAL BadBTree instead of ERROR so can proceed by fixing things up if necessary.
Fixed B-Tree bug #8: MoveEntriesToLeftInternal and MoveEntriesToRightInternal had a similar problem to the analogous procedures in DBIndexOpImpl: they try to pass nentries-1 to SizeOfEntries when nentries=0.  Not good on CARDINALs.  Also, added comments to the previous and check to CheckPage to insure that only children of internal pages never occur.  Added WriteKey debugging procedure.
Fixed B-Tree bug #9: MergeInInternalPage still tries to do DBIndexOp.ChangeKey[parent ...] in the "no right brother" case even when no elements moved (left.pointer.size - i - 1 = 0).  Put in explicit check to return early in this case.  I note that Nori has an explicit IF in the "balance with right brother" case, IF i >= right.pointer.size - 1, but its intentions are still obscure.
#9.5: Need to do UnlockPage[left] when return early in MergeInInternalPage as described above.
Added stopAtOpCount.
Fixed bug #10: JustOver in MergeInInternalPage, balance with right case, can return 1, leaving one entry on the page.  This is an illegal B-Tree state!  I tossed Nori's IF statement here that I didn't understand and put in my own, to ascertain that at least two entries are left on the right.  Also redid the balance with left case so the same clearly can't happen there.  There are no other calls to MoveEntriesToRightInternal or MoveEntriesToLeftInternal, and MoveLeafEntriesToLeft, etc., are OK 'cause leaving one entry is ok on a leaf; so no one else can screw up, he says confidently...
Converted most DBIndex data structures to REFs.
Fixed bug #11: MergableToRightInternal should set key: IndexKey _ Key[parent, leftAt+1], NOT leftAt; it was measuring the length of the wrong key!  This sometimes caused a merge to overflow and clobber a page.
Fixed bug #12: Index pages were hardly every being freed in the database!  As a result databases would grow in size indefinitely.  Put a call to DestroyPage of son into MergeInThisPage, in the case when state=delete.  (This seems better than putting a call to DestroyPage in the lower level routines, where it will have to go at least four places).  This means MergeInThisPage must do the UnlockPage (or DestroyPage) on its "son" argument, so caller (DeleteFromTree) cannot touch it after that. 
Fixed bugs #13 and #14: After a couple hours of tracking down all the possible call orderings, it appears there are two possible cases of failing to de-allocate an IndexKey that was allocated, and three possible cases of de-allocating it more than once.  A user report of the latter called this to my attention yesterday.  I changed most procedures to have one universal assumption: the caller must de-allocate the key that is returned, if it is non-NIL.  I think the performance effects of this will be minor, I'll check; it's too messy to keep track of what needs to be de-allocated otherwise.
Improvements:  Added DestroyThisPage to do more integrity checks; I want to make #12 really fixed the bug.  Got rid of FreeIndexKey, calling FreeKey in DBIndexPageImpl instead.  FreeKey, CreateIndexKey, and CopyKey maintain counts to check that we are allocating and de-allocating keys; the counts seem to balance on insertions and deletions, so fixes #13 and #14 seem to be working.  Changed CreateTheNextKey in OpenIndexScan to call CreateIndexKey instead of duplicating the same code here; it simply creates a key from a rope with a null byte on the end.  We no longer need yucky DBHeapStorage as a result.  Yay!
Fixed bugs #15 and #16, in DeleteFromTree merge and split branches of SELECT.  Apparently we had never made a key in a parent longer as a result of a balancing of sons and caused the parent to split before, my random tester would be unlikely to invoke this because it generates random keys rather than ones like Walnut's with varying common prefixes.  Nori should have been using a retKey in the merge case, and a retOverflow in the split case so that keys and pages get freed properly.
As a result of bugs #17 and #18, in which I discovered that B-tree pages were not always being marked dirty when they should be, I re-organized the DBIndex package altogether, moving all B-Tree modifying code to DBIndexMod(Impl).  The procedures from this module moved were InsertTwoEntriesToEmptyPage, MoveEntriesToRightInternal, MoveEntriesToLeftInternal.  Changed GetRootPage to call DBIndexPage.GetPage directly instead of mucking around with ten lines of doing mostly the same thing.  The only difference I see is that before it was getting the cache handle out of the root itself, but it is also cached in the DBIndex.Page.  As a result DBIndexPage.AllocatePage doesn't have to be externally available.
In association with bug fix #19, changed still more procs to require that caller de-allocate key returned, e.g. MergeInThisPage, MergeInInternalPage, and SplitInternal. 
Moved some procs to DBIndexOpImpl
made Cedar, added tioga formatting
Κ Ÿ˜š
œ™Icodešœ
Οm
œ1™<—Jš
œG™GJš
œB™BJš
œ™Jš
œ™Jš
œ#™#Jš
œ$™$Jš
œ,™,™'K™%—J˜š
Οk	˜	J˜
J˜	J˜
J˜J˜
J˜
J˜J˜	J˜J˜Jšœžœ˜3Jšžœ
˜J˜J˜J˜—šœ
žœ
ž˜šžœ
˜J˜	J˜J˜	J˜
J˜J˜
J˜
Jš
œ˜Jšžœ
˜J˜J˜—šžœ˜J˜—Jšœžœ
žœ
˜J˜Jš
œ™J˜Jšœžœ
žœ&˜BJšœžœžœ˜,J˜Jšœžœ˜Jšœ
žœ˜"Jšœžœ˜Jšœžœ˜Jšœžœ˜0Jšœžœ˜&J˜Jšœ
žœ˜&Jšœ
žœ˜&J˜Jšžœžœžœ˜J˜Jš
œ™J˜Jšœ
žœžœ
˜Jšœžœžœ˜JšœžœžœΟc˜1J˜Jš
œ	™	J˜Jšœžœ	˜+Jšœžœ	˜)J˜Jš
œ"™"J˜JšœžœžœŸ=˜YJšœžœžœŸ*˜LJšœžœžœŸ˜8Jšœž	œŸ4˜PJšœžœžœŸ?˜aJšœžœžœŸ;˜ZJšœ	žœŸ4˜FJšœžœžœŸ*˜GJšœžœŸ$˜<JšœžœžœŸ5˜TJšœ
žœžœŸB˜]Jšœ!Ÿ˜?J˜J˜Jš
œ™J˜šΟnœžœ
žœ˜7Jš
œD˜DJ˜>J˜J˜—š œžœ
žœ˜8Jš
œW™WJš
œ:˜:J˜Jš
œ#˜#J˜>J˜J˜—š
 œžœ
žœžœžœ˜eJšœžœ
žœ
˜Jšœ	žœ
žœžœ/˜KJš
œ;˜;J˜J˜Jš
œ2˜2Jšœžœ$˜2J˜šžœ
žœ˜Jšœ)Ÿœ
˜EJš
œ8˜8J˜#J˜J˜#J˜4J˜šžœ˜Jš
œ˜Jš
œ@˜@šžœžœ
˜Jšœžœ˜*Jšœ
žœ
˜J˜MJšžœžœ˜—J˜ ——J˜J˜—š
 œžœ
žœ$žœžœ˜kJš
œ2˜2Jš
œ:˜:Jšœ	žœ
žœžœ/˜KJ˜J˜Jšœžœ
žœ˜Jšœžœ#˜1J˜J˜šžœ
˜Jšžœ
žœ
žœ
Ÿ%˜Gšžœ
˜˜Jš
œ@˜@šžœžœ
˜Jšœžœ˜*J˜'šœ	žœ˜šžœžœ˜,š
ž˜Jš
œD™Dšœ
žœžœ
žœ˜/J˜3Jš
œ˜J˜ J˜6——šžœ
˜Jš
œ4™4šžœžœ˜,šžœ
˜šœ
žœžœ
žœ˜/J˜&J˜&J˜J˜;J˜"——šžœ
˜Jš
œ˜———J˜——˜	˜EJ˜——Jšžœžœ˜————JšœŸ˜8J˜—š
 
œžœ
žœXžœ%žœ˜§
Jšœžœ˜J˜Jš
œ;˜;Jšœžœ9˜Gš	žœ
žœžœ
žœž˜<Jš
œ1˜1—šžœ
žœžœž˜8Jš
œ1˜1—Jšžœ
žœ(˜;šžœ
˜Jšžœ˜šžœ
˜Jšžœžœ+˜GJšžœžœ:˜a—šžœ
˜Jšžœžœ&˜BJšžœžœ<˜c——J˜GJ˜J˜J˜—š
 
œžœ
žœžœžœ˜ZJš
œ‘
™‘
J˜J˜Jšœžœ
˜Jšžœžœ
žœ
žœ
žœŸ"˜=J˜.Jšžœžœ
žœžœ˜3J˜/šžœ˜ Jš
žœžœ*žœ
žœ
žœ
˜Lšžœ˜Jš
œ$˜$Jšžœ
žœžœžœžœ
žœžœžœ	ž˜
šžœ˜Jš
œA˜AJ˜#———J˜˜Jšžœ˜—J˜J˜—š
 œžœ
žœžœžœ˜XJš
œ‘
™‘
J˜Jšžœžœ
žœ
žœ
žœŸ"˜=Jšžœžœ
žœžœ˜3J˜/šžœ˜ Jš
žœžœ*žœ
žœžœ˜Jšžœ˜Jš
œ˜šžœ
žœžœžœžœ
žœžœ˜‹
Jšžœ	žœ˜*Jšžœ˜———Jšžœ˜J˜J˜—š 
œžœ
žœžœ#˜XJš
œ/™/J˜Jšœžœ
˜Jšžœžœ
žœ
žœ
žœŸ"˜=J˜.Jšžœžœ
žœžœ˜3J˜/Jšžœ
žœžœ	ž˜8šžœ˜Jš
œ$˜$J˜ Jšžœ
žœžœžœžœ
žœžœ ˜“
Jšžœ	ž˜Jšžœ?˜C—J˜J˜Jšžœ˜JšœŸ˜J˜—š œžœ
žœžœ˜PJ˜Jšžœžœ
žœ
žœ
žœŸ"˜=Jšžœžœ
žœžœ˜3J˜/Jšžœ
žœžœ	žœ˜Ršžœ˜Jš
œ˜Jšžœ
žœžœžœžœ
žœžœ˜‘
Jšžœžœ˜(Jšžœ˜—Jšžœ˜JšœŸ˜J˜—š 
œžœ
žœžœ#˜XJšžœžœ
žœ
žœ˜+š
ž˜Jšœ
žœžœ(žœ;˜Ž
Jš
œ@˜@Jšžœžœ ˜:Jš
œ˜Jšžœ˜——J˜š œžœ˜0Jšœ
žœžœ(žœ;˜Ž
Jš
œ˜—J˜š œžœ
žœ%žœžœ!žœ˜tJš
œ:˜:Jšžœ žœ	ž˜2šžœ
žœ
ž˜Jš
œ˜Jš
œ˜Jš
œ˜Jšœžœ
˜Jšœ+žœ˜HJš
œ6˜6šžœ%žœ%˜NJšžœ	ž˜—JšžœC˜GJš
œ!˜!Jš
œ˜Jšžœ
˜—Jš
œ˜—J˜š œžœ
žœ˜AJ˜ Jš
œ$˜$Jš
œ˜J˜—Jš
œ™J˜Jš
œ	™	J˜š œžœžœ
žœžœžœ
žœ˜hJš
œk™kJšœžœ
˜Jšœžœ
žœ˜J˜J˜	J˜
šžœŸ
œžœ˜$Jš
œ˜Jšžœ˜!šžœ˜Jš
œ<˜<Jšžœ˜#—šžœ˜Jš
œ˜Jšžœ
žœžœ˜——šžœ˜Jš
œ˜˜'Jš
œE™E—J˜DJš
œ;˜;šžœžœ
˜Jšœ'žœ
žœžœ˜C˜
J˜$J˜>J˜J˜"Jšžœ$˜*—Jšžœžœ
˜——J˜J˜—š 	œžœG˜VJšœ
žœ˜Jš
œU™UJ˜J˜HJ˜RJ˜&J˜J˜"J˜AJ˜J˜J˜—Jš
œ™J˜š
 œžœžœžœžœ˜fJš
œ₯™₯Jšœžœ
˜Jšœžœ˜J˜ J˜
J˜$šžœžœ˜Jš
œ˜Jš
œ;˜;J˜$Jšžœ	žœžœ˜—J˜Jš
œ(˜(Jš
œ>™>šžœE˜GJš
œ9˜9šžœžœ
˜˜J˜J˜Jšžœžœžœ
žœ˜IJš
œ˜—Jšœ&žœ
žœžœ˜B˜
J˜9Jšžœ˜#—˜
J˜]J˜J˜"Jšžœ˜%—Jšžœž˜—Jš
ž˜—JšœŸ˜J˜—š œžœ˜*Jš
œ#™#š œžœ(˜:Jš
œ
™
J˜Jšœžœ˜
J˜šžœ˜Jšžœ
žœ
Ÿ"˜.šžœ
žœ˜šžœžœžœ
˜#˜AJšœžœ
žœ
žœ˜4—J˜J˜,Jš
ž˜—J˜——JšœŸ˜—J˜Jš
žœžœ
žœžœ
žœ
˜)J˜J˜J˜4J˜ Jšœ	žœ˜J˜
Jšœ	ž˜
J˜J˜J˜—š œžœ"˜@Jš
œ!™!J˜!J˜J˜—Jš œžœ1˜EJ˜š œžœžœ˜9Jšžœ?˜EJ˜—š 
œžœžœ˜AJš
œ6™6J˜BJš
œ™J˜/Jšžœ˜J˜J˜—Jš œžœ1˜EJ˜š œžœžœ
žœ˜MJš
œ[™[Jš
œ9™9J˜J˜Jšžœ˜!šžœ˜Jš
œ˜Jšžœžœ
žœžœ˜5J˜J˜
J˜
Jšžœ˜—Jšžœžœ˜*J˜J˜—š œžœžœ
žœ˜MJš
œA™AJ˜	J˜Jšžœ
žœžœ˜9J˜Jšžœžœ
žœ
žœ˜J˜J˜
J˜Jšžœ˜
J˜J˜—š œžœžœžœ˜HJš
œJ™JJ˜šžœ3žœ
˜:Jšžœžœ˜#—Jšžœ3˜9J˜J˜—š œžœžœžœ˜GJš
œH™HJ˜šžœ1žœ
˜8Jšžœžœ˜#—Jšžœ1˜7J˜J˜J˜—Jš
œ ™ J˜š
 	œžœžœ	žœ
žœ˜BJš
œh™hJšœžœ˜-J˜,J˜J˜—š
 œžœžœ
žœžœ˜_Jš
œ―™―J˜J˜Jšœžœ
˜šžœ˜Jšžœ?˜CJšžœ;˜?—šžœžœ
˜J˜G—Jšžœ˜"Jšžœ˜J˜J˜—š œžœ"žœ
žœžœžœ˜pJš
œκ
™κ
Jšœ	žœ˜$Jšœžœ˜
Jšœžœ˜Jšœ	žœ˜&J˜J˜Jš
Ϲ
™π
šžœ!žœŸ&˜OJ˜Ušžœ˜˜AJšœžœ˜—Jš
œ:™:J˜ƒ
J˜Jšžœ
žœžœ˜—Jš
œ6™6J˜OJš
œI™IJš
œH™Hšžœžœž˜,Jšœ žœ	žœžœŸ˜O—J˜.J˜|J˜J˜Nšžœ
˜šœ
Ÿ*˜+˜
J˜G—šžœ˜˜@Jšœžœ˜—Jš
œ9™9J˜}J˜Jšžœ
žœžœ˜—Jš
œK™KJ˜%Jš
œJ™JJš
œ.™.šžœžœ
ž˜-Jšœžœ	žœžœ˜:—J˜2˜%˜EJ˜&——J˜J˜K———Jšžœ˜ J˜J˜—š œžœ%žœ
žœ
žœžœžœ˜{Jš
œU™UJš
œ.™.J˜'Jšœžœ˜(Jš
œX™XJš
œM™MJšžœ6˜<J˜J˜—š œžœ%žœžœ
žœžœžœ˜{Jš
œ…
™…
J˜&Jšœžœ˜(Jšžœ6˜<J˜J˜—š
 œžœžœžœžœ˜?Jšžœ*˜0J˜J˜—š œžœž˜,Jš
ϩ
™©
Jš
ž˜Jšžœžœ
žœ˜3Jšžœ&˜(šžœ(ž˜.JšžœŸ?˜W—Jšžœžœ:˜RJšžœ˜"Jšžœ
˜J˜J˜—Jš
œ!™!J˜Jš
 œžœžœžœžœ
˜JJ˜Jš
œ™J˜š
 œžœžœ
žœžœ˜VJš
œ.™.J˜J˜Jšœžœ
˜J˜J˜Jšžœ˜J˜—š
 
œžœžœ
žœžœ˜[Jš
œ0™0J˜J˜š œžœžœ˜Jš
œd™dJšœžœ
žœ
žœ˜*Jšžœ"žœ
žœ˜1J˜J˜J˜—šžœžœ
Ÿ
œ
˜"˜J˜$Jšžœžœžœ˜9Jšžœ˜——J˜(J˜MJ˜ J˜Jšžœ˜J˜J˜—š œžœžœ˜KJ˜	J˜Jšžœ
žœ
žœ
˜'J˜J˜J˜Jšžœ˜J˜J˜—š œžœžœ˜@J˜Jšžœ
žœ
žœ˜)šžœ˜Jš
œC˜CJ˜J˜Jšžœ˜
—J˜J˜—š œžœžœžœ˜TJ˜J˜Jšœžœ
˜šžœ
žœ
˜Jšžœ1žœ˜O—J˜ J˜Jšžœ˜J˜J˜—š
 œžœžœžœžœ˜QJšœžœ˜Jšœžœ˜Jšœžœ˜J˜*J˜J˜J˜1šžœžœ˜Jš
œ˜Jš
œ˜Jšžœ˜—šžœ˜Jš
œ%˜%Jš
œ˜Jšžœ˜—J˜J˜—Jš
œ™J˜š œžœ>žœ˜`Jš
œ,™,Jš
œ5˜5J˜8J˜BJšœžœ;˜[J˜(J˜J˜—Jš
œ™J˜š 
œžœžœžœžœžœžœ˜aJ˜Jšžœ
žœžœ
žœ
˜J˜Jšžœžœ
žœ˜5šžœžœ
ž˜Jšœ@ž˜DJ˜>—Jšžœžœ˜,Jšžœ
žœ
žœ˜šžœ˜Jš
œ˜J˜Jšœžœ˜"JšœžœŸ=˜PJšœžœ˜%J˜J˜—J˜J˜—š œžœžœ˜=Jš
œΈ™ΈJšœ	žœ
˜J˜Jšžœ
žœžœ
žœ˜šžœ
žœ
˜Jš
žœ
žœ
žœ
žœ
žœ˜.—˜J˜Jšœ"žœ˜(Jšžœžœ
žœ˜(J˜—Jšžœžœ
žœ	˜4J˜J˜—š
 	œžœžœžœžœ˜aJš
œG™GJ˜J˜Jšœžœ
˜J˜
J˜%J˜Jšžœžœ
žœ
˜%šžœžœ
˜Jšœ+žœ˜4—Jšžœžœ˜&šžœŸ˜5JšžœŸ0˜GJšžœŸ#˜=Jšžœ
žœ
˜—J˜J˜FJ˜(J˜J˜šžœžœžœ
˜#J˜Jšžœžœ
žœ
žœ@žœ
žœ˜jJ˜FJ˜%J˜J˜Jš
ž˜—J˜J˜—š
 
œžœžœžœžœ˜eJšœžœ˜
J˜J˜J˜J˜Jšžœžœ
žœ˜'J˜J˜J˜
Jšžœžœ˜&Jšžœžœžœ
žœ
˜FJ˜šžœžœžœ
˜#J˜J˜Jšžœžœ
žœ
žœFžœ
žœ˜uJ˜Jš
ž˜—J˜J˜—š œžœžœžœ˜0Jšœ
žœ
žœ˜2Jšœ&žœžœžœ˜RJ˜J˜—š 
œžœžœ˜,Jš
œW™WJšœžœ˜Jšœ
žœ
žœ˜2Jšžœ
žœ
žœ˜(šžœžœ
˜J˜Jšžœ˜	—Jšœ žœžœ˜NJš
žœžœ
žœžœžœ
˜IJ˜J˜J˜—š 
œžœžœžœ˜<J˜-Jšœ
žœ
žœ˜3šžœžœž˜"Jšžœ
ŸX˜^J˜šžœ$ž˜*Jšœ-žœ˜C—š
ž˜šžœžœ
žœž˜'Jšœ&žœ
˜.——Jšžœ
˜—š	žœžœžœžœž˜PJšœžœ˜1—J˜J˜—š œžœžœ˜+Jš
œT™TJšœ
žœ
žœ˜2Jšœ"žœ˜8Jš
žœžœ
žœžœ'žœ
˜VJ˜J˜J˜—š 	œžœžœ˜.Jš
œT™TJšœ
žœ
žœ˜2Jšœ"žœ˜8Jš
žœžœ
žœžœ'žœ
˜VJ˜J˜J˜—š
 	œžœ	žœ
žœžœ˜2Jšœžœžœ˜Jšžœžœžœžœ	˜@Jšžœ˜J˜J˜J˜—š 
œžœžœ˜,Jšžœžœ
žœ	˜-J˜J˜—š œžœ7˜KJšžœ$žœ
žœ
˜;J˜J˜—š œžœžœ˜/Jš	œ
žœ
žœ
žœ
žœ˜7J˜Jšœžœ
˜šžœžœžœ
˜#J˜Jšžœ1žœ
žœ˜IJ˜Jš
ž˜—J˜J˜—š œžœžœ˜3Jš	œ
žœ
žœ
žœ
žœ˜;J˜Jšœžœ
˜šžœžœžœ
˜#J˜Jšžœ1žœ
žœ˜IJ˜Jš
ž˜—J˜J˜Jš
œ	™	J˜J˜J˜Jšžœ˜J˜——J˜J˜˜)Jšœ"ž˜$J˜—˜(Jšœ#ž˜%J˜—˜gJšœ#ž˜%J˜—˜NJšœ#ž˜%J˜—˜aJšœ"ž˜$J˜—˜AJšœ"ž˜$J˜—˜$Jšœ"ž˜$J˜—˜rJšœ"ž˜$J˜—˜Jšœ$žœ
˜'J˜—šœ>žœ˜OJšœ$žœ
˜'J˜—˜•
J˜J˜—˜J˜J˜—˜J˜J˜—šœ žœ
˜¦
J˜ J˜—šœ―
žœo˜‘J˜!J˜—˜Ÿ
J˜!J˜—˜œJ˜!J˜—š	œXžœ¬
ž
œ"žœ(ž
œ‰˜ί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˜J˜-Jš
œο™οJ˜J˜.Jš
œΣ™ΣJ˜J˜-Jš
œη™ηJ˜J˜.Jš
œζ™ζJ˜J˜0Jš
œΔ™ΔJ˜J˜1Jš
ϩ
™©
J˜J˜.Jš
œ!™!J˜J˜*J™"J˜J˜J˜J˜J˜J˜J˜J˜J˜—…—}>ΘS