DIRECTORY
DBCache,
DBCommon,
DBEnvironment,
DBStorageInternal,
DBStoragePagetags,
DBIndexFilePage,
DBIndex,
Rope;

DBIndexFilePageImpl: CEDAR PROGRAM
IMPORTS
DBEnvironment,
Rope
EXPORTS
DBIndexFilePage
= BEGIN



CoreIndexSize: CARDINAL = DBIndex.CoreIndexSize;
FullPage: CARDINAL = DBIndex.FullPage;

ROPE: TYPE = Rope.ROPE;

WhatDoYouThinkOfThis: SIGNAL = CODE; -- for debugging

Page: TYPE = DBIndex.Page;
ItemHandle: TYPE = DBIndex.ItemHandle;
IndexKey: TYPE = DBIndex.IndexKey;
KeyBody: TYPE = DBIndex.KeyBody;
FakeIndexKey: TYPE = REF KeyBody;


fakeIndexKeys: LIST OF FakeIndexKey;
fakeIndexKeyCount: INT _ 0; -- Should equal fakeIndexKey.Length[], never more than 2 or 3


SetSize: PUBLIC PROC [p: Page, i: CARDINAL] =
TRUSTED BEGIN p.pointer.size _ i END;


FreeSpace: PUBLIC PROC [p: Page] RETURNS [CARDINAL] =
TRUSTED BEGIN
indexArraySize: CARDINAL _ p.pointer.size;
free: CARDINAL_
IF indexArraySize=0 THEN CoreIndexSize
ELSE p.pointer.index[indexArraySize - 1] - indexArraySize;
IF free>CoreIndexSize THEN ERROR;
RETURN[free]
END;

FrontSize: PUBLIC PROC [p: Page, index: CARDINAL] RETURNS [CARDINAL] =
TRUSTED BEGIN RETURN[CoreIndexSize - p.pointer.index[index]] END;

CoreAddr: PUBLIC PROC [p: Page, i: CARDINAL] RETURNS [ItemHandle] =
TRUSTED BEGIN
base: LONG POINTER _ @p.pointer.index;
index: CARDINAL _ (base+i)^;
IF i>CoreIndexSize THEN ERROR;
RETURN[LOOPHOLE[base+index, ItemHandle]];
END;

EndAddr: PUBLIC PROC [p: Page] RETURNS [LONG POINTER] =
TRUSTED BEGIN RETURN[p.pointer + FullPage] END;

SizeOfEntries: PUBLIC PROC [page: Page, from: CARDINAL, to: CARDINAL]
RETURNS [CARDINAL] =
TRUSTED BEGIN
left, right: CARDINAL;
IF to < from THEN RETURN[0];
left _ page.pointer.index[to];
right _ IF from = 0 THEN CoreIndexSize ELSE page.pointer.index[from - 1];
RETURN[right - left]
END;


Value: PUBLIC PROC [p: Page, index: CARDINAL] RETURNS [DBCommon.DBPage] =
TRUSTED BEGIN
RETURN[LOOPHOLE[CoreAddr[p, index].value, DBCommon.DBPage]];
END;

Tid: PUBLIC PROC [p: Page, index: CARDINAL] RETURNS [DBStorageInternal.TID] =
TRUSTED BEGIN
RETURN[LOOPHOLE[CoreAddr[p, index].value, DBStorageInternal.TID]];
END;

Key: PUBLIC PROC [page: Page, index: CARDINAL] RETURNS [IndexKey] =
TRUSTED BEGIN
base: LONG POINTER _ @page.pointer.index;
offset: CARDINAL _ (base+index)^;
key: IndexKey_ LOOPHOLE[base+offset+2, IndexKey];
IF key.length>CoreIndexSize AND (page.depth=1 OR index#0) THEN ERROR;
RETURN[key]
END;


CopyKey: PUBLIC PROC[key: IndexKey] RETURNS [IndexKey] =
TRUSTED BEGIN
ret: IndexKey _ AllocateIndexKey[key.length];
FOR i: CARDINAL IN [0..key.length) DO ret.text[i]_ key.text[i] ENDLOOP;
RETURN[ret];
END;

CreateIndexKey: PUBLIC PROC [s: ROPE] RETURNS [IndexKey] =
TRUSTED BEGIN
sLength: INT _ s.Size[];
ret: IndexKey _ AllocateIndexKey[sLength];
IF sLength>CoreIndexSize THEN ERROR; -- key too big
FOR i: INT IN [0..sLength) DO ret.text[i]_ s.Fetch[i] ENDLOOP;
RETURN[ret]
END;

AllocateIndexKey: PUBLIC PROC [bytes: INT] RETURNS[key: IndexKey] =
BEGIN fk: FakeIndexKey;
fk_ NEW[KeyBody[bytes]];
fakeIndexKeys_ CONS[fk, fakeIndexKeys];
fakeIndexKeyCount_ fakeIndexKeyCount+1;
RETURN[LOOPHOLE[fk]]
END;

FreeKey: PUBLIC PROC[key: IndexKey] =
BEGIN fk: FakeIndexKey;
TRUSTED { fk _ LOOPHOLE[key] };
IF key=NIL THEN RETURN;
fakeIndexKeyCount_ fakeIndexKeyCount-1;
IF fakeIndexKeys=NIL THEN ERROR DBEnvironment.InternalError;
IF fk=fakeIndexKeys.first THEN {fakeIndexKeys_ fakeIndexKeys.rest; RETURN};
FOR fkl: LIST OF FakeIndexKey _ fakeIndexKeys, fkl.rest UNTIL fkl.rest=NIL DO
IF fkl.rest.first=fk THEN {fkl.rest_ fkl.rest.rest; RETURN} ENDLOOP;
ERROR DBEnvironment.InternalError;
END;



GreaterEq: PUBLIC PROC [left, right: IndexKey] RETURNS [BOOLEAN] =
TRUSTED BEGIN
rightChar: CHAR;
i: CARDINAL;
FOR i IN [0..MIN[left.length, right.length]) DO
rightChar _ right[i];
SELECT left[i] FROM
> rightChar => RETURN[TRUE];
< rightChar => RETURN[FALSE];
ENDCASE;
ENDLOOP;
IF left.length >= right.length THEN RETURN[TRUE] ELSE RETURN[FALSE]
END;

LessEq: PUBLIC PROC [left, right: IndexKey] RETURNS [BOOLEAN] =
TRUSTED BEGIN
rightChar: CHAR;
i: CARDINAL;
FOR i IN [0..MIN[left.length, right.length]) DO
rightChar _ right[i];
SELECT left[i] FROM
> rightChar => RETURN[FALSE];
< rightChar => RETURN[TRUE];
ENDCASE;
ENDLOOP;
IF left.length <= right.length THEN RETURN[TRUE] ELSE RETURN[FALSE]
END;

Less: PUBLIC PROC [left, right: IndexKey] RETURNS [BOOLEAN] =
BEGIN RETURN[NOT GreaterEq[left, right]] END;

Greater: PUBLIC PROC [left, right: IndexKey] RETURNS [BOOLEAN] =
BEGIN RETURN[NOT LessEq[left, right]] END;




FindTheFirstLeafKey: PUBLIC PROC [p: Page, key: IndexKey] RETURNS [ret:CARDINAL] =
TRUSTED BEGIN
m: CARDINAL;
low: CARDINAL _ 0;
high, sizePMinusOne: CARDINAL _ p.pointer.size-1;
m _ (low + high)/2;
IF p.pointer.size = 0 THEN  -- ouch!  try to push on anyway...
{SIGNAL WhatDoYouThinkOfThis; RETURN[0]};
UNTIL m = low DO
IF LessEq[key, Key[p, m]] THEN high _ m ELSE low _ m;
m _ (low + high)/2;
ENDLOOP;
IF low=0 THEN 
IF LessEq[key, Key[p, 0]] THEN ret _ 0 
ELSE IF high=sizePMinusOne AND Greater[key, Key[p, high]] 
THEN ret _ high+1
ELSE ret _ high
ELSE IF high=sizePMinusOne AND Less[Key[p, high], key] THEN ret _ high+1 
ELSE ret _ high; 
RETURN[ret]
END;

FindTheLastLeafKey: PUBLIC PROC [p: Page, key: IndexKey] RETURNS [ret: CARDINAL] =
TRUSTED BEGIN
pSize: CARDINAL _ p.pointer.size;
low: CARDINAL _ 0;
high: CARDINAL _ pSize - 1;
m: CARDINAL;
m _ (low + high)/2;
UNTIL m = low DO
IF GreaterEq[key, Key[p, m]] THEN low _ m ELSE high _ m;
m _ (low + high)/2;
ENDLOOP;
IF low=0 THEN 
IF Less[key, Key[p,0]] THEN ret _ 0 
ELSE IF high=pSize-1 AND GreaterEq[key, Key[p, high]] 
THEN ret _ high+1
ELSE ret _ high
ELSE IF high=pSize-1 AND GreaterEq[key, Key[p,high]] 
THEN ret _ high+1 
ELSE ret _ high
END;

FindTheInternalKey: PUBLIC PROC [
page: Page, key: IndexKey,
Upper, Lower: PROC [IndexKey, IndexKey] RETURNS [BOOLEAN]]
RETURNS [ret: CARDINAL] =
TRUSTED BEGIN
pageSize: CARDINAL _ page.pointer.size;
max: CARDINAL _ pageSize - 1;
min: CARDINAL _ 1;
m: CARDINAL;
IF min>max THEN RETURN[0];
DO
m _ (max + min)/2;
IF m = min THEN EXIT;
IF Upper[key, Key[page, m]] THEN min _ m ELSE max _ m;
ENDLOOP;
IF min=1 THEN 
IF Lower[key,Key[page,min]] THEN ret _ 0 
ELSE
IF min#max AND max=pageSize - 1 AND Upper[key, Key[page,max]] THEN ret _ max 
ELSE ret _ min
ELSE
IF max=pageSize-1 AND Upper[key, Key[page,max]] THEN ret _ max
ELSE ret _ min
END;

JustOver: PUBLIC PROC [p: Page, size: CARDINAL] RETURNS [CARDINAL] =
TRUSTED BEGIN
i: CARDINAL;
pSize: CARDINAL _ p.pointer.size;
FOR i IN [0..pSize) DO
IF p.pointer.index[i]+size < FullPage + (i + 1) THEN GOTO Over;
REPEAT Over => RETURN[i]; FINISHED => RETURN[pSize - 1];
ENDLOOP;
END;



END.


Change Log

Changed the meaning of FindTheLastLeafKey
by Suzuki: November 24, 1980  1:09 PM 

Changed JustOver to match the meaning
by Suzuki: December 2, 1980  9:46 AM 

Changed FindTheInternalKey to assign min to ret in the most general case
by Suzuki: December 3, 1980  9:28 AM 

Changed FindTheInternalKey so that it can handle 1 entry page
by Suzuki: December 3, 1980  1:11 PM 

Allocate storage from DBHeapStorage.
by MBrown: February 27, 1981  6:34 PM

Added checks on key lengths, index passed to CoreAddr, and FreeSize returned value.
by Cattell: June 19, 1982 3:51 pm

Changed name of CopyIndexKey to CreateIndexKey.  Added check on key length too big, and signal KeyTooBig.
by Cattell: June 20, 1982 6:32 pm

Changed FindTheFirstLeafKey to try to signal and attempt to push on if it encounters a zero-size page ('cause my personal database is in a rubble of bits otherwise...)
by Cattell: August 11, 1982 10:15 am

Removed some procs to DBIndexModImpl.  Moved some procs here.
by Cattell: September 21, 1982 8:37 pm

Fixed B-tree bug #19: this one took 4 man-hours, because it took so long to reproduce and involved a fairly complicated call stack.  The symptom was a garbage key in the root node after a deletion.  If re-arranging two sons of a node causes a new larger key to be stored in the node, which in turn is over threshold to cause the node to split, then in certain cases the pointer that SplitPage creates as the splitKey, the last key on the node, gets overwritten before it gets used by the grandparent.  The solution is that SplitPage should copy the key.  This ripples through several procedures in other modules which change their assumptions about allocation/deallocation of keys: DBIndexImpl.SplitInternal, etc.  

Changed by Willie-Sue on February 18, 1985

	τFile: DBIndexFilePageImpl.mesa
Copyright c 1985 by Xerox Corporation.  All rights reserved.
Contents: low-level operations on B-tree file pages
Last edited by:
MBrown on February 27, 1981  9:42 PM
Cattell on September 29, 1983 1:29 pm
Willie-Sue on February 18, 1985 1:49:33 pm PST 
Some index keys are on B-tree pages, and therefore must be DBIndex.IndexKey pointers.
Other ones are allocated as FakeIndexKeys, which are REFS loopholed into IndexKeys.
To keep the FakeIndexKeys from being freed by the garbage collector, we keep a list of
them in fakeIndexKeys, removing them when we are done with them. 
Changes the state of Btree page
Query the state of Btree page
Returns the number of free words available
Returns the size(in words) that entries from 0 to index occupy.
Returns the address of i-th entry in p
(Address of the word of the end of the page)+1
Returns the number of words, entries from "from" to "to" occupy in page
Query the value of elements
Returns the key of the index-th entry
Assert: key.length should be valid length unless 0th entry on non-leaf page
Allocate and de-allocate IndexKeys
Returns copy of the key.  WARNING: this copies words, not bytes, so may copy one
byte too many; however Cedar allocates an extra byte for FakeIndexKeys anyway,
so this is ok.
Copies rope s into a newly allocated IndexKey.
Allocates key; this is pretty gross, but seems to be the best solution, with mixed REFs and
LONG POINTERs.  Allocates an IndexKey by doing a NEW, then loopholes it into a
LONG POINTER.  We add the REF to the fakeIndexKeys list so that it won't be garbage
collected until someone calls FreeKey.
"Deallocates" key; actually, just removes it from the fakeIndexKeys list so that the
garbage collector will find it has zero reference count.
Key comparison functions.
Returns TRUE iff left>=right
Returns TRUE iff left<right
Basic utilities
Key search functions.
Returns i such that i=0&key<=a[i] OR 0<i<max[a]&a[i-1]<key<=a[i] OR i=max[a]&a[i-1]<key
Invariant: (low=0 | Key[p,low]<key)&(high=Size[p]-1 | key<=Key[p,high])
Returns i such taht
i=0&key<a[0] OR 0<i<max[a]&a[i-1]<=key<a[i] OR i=max[a]&a[i-1]<=key
Invariant: (low=0 | Key[p, low]<=key)&(high=Size[p]-1 | key<Key[p, high])
i=0&key(Lower)a[1] OR 0<i<max[a]&a[i](Upper)key(Lower)a[i+1]
OR i=max[a]&a[i](Upper)key
Invariant:
(min=1 | Key[page, min](Upper)key)&(max=Size[page]-1|key(Lower)Key[page,max])
Find index i such that entries from 0 to i and OverHead and
index arrays (=i+1) is greater than size, but not for i-1
made Cedar, added tioga formatting
Κ
v˜š
œ™Icodešœ
Οm
œ1™<—Jš
œ3™3Jš
œ™Jš
œ$™$Jš
œ%™%Jš
œ/™/˜š
Οk	˜	J˜J˜	J˜J˜J˜J˜J˜J˜J˜——šœžœ
ž˜"š
ž˜J˜J˜—š
ž˜J˜—Jšœž˜J˜J˜J˜Jšœžœ˜0Jšœ
žœ˜&J˜Jšžœžœžœ
˜J˜JšœžœžœΟc˜5J˜Jšœžœ˜Jšœžœ˜&Jšœ
žœ˜"Jšœ	žœ˜ Jšœžœžœ	˜!J˜Jš
œU™UJš
œS™SJš
œV™VJš
œA™AJ˜Jšœžœ
žœ˜$JšœžœŸ=˜YJ˜Jš
œ™J˜šΟnœžœ
žœžœ˜-Jšžœ
žœžœ
˜%J˜—Jš
œ™J˜š
 	œžœ
žœžœžœ˜5Jš
œ*™*Jšžœ
ž˜
Jšœžœ˜*šœžœ
˜Jšžœžœ˜&Jšžœ6˜:—Jšžœžœ
žœ
˜!Jšžœ˜Jšžœ
˜J˜—š 	œžœ
žœžœžœžœ˜FJš
œ?™?Jšžœ
žœ
žœ)žœ
˜AJ˜—š
 œžœ
žœžœžœ˜CJš
œ&™&Jšžœ
ž˜
Jšœžœ
žœ˜&Jšœžœ
˜Jšžœžœ
žœ
˜Jšžœ
žœ˜)Jšžœ
˜J˜—š œžœ
žœžœžœ
žœ˜7Jš
œ.™.Jšžœ
žœ
žœžœ
˜/J˜—š
 
œžœ
žœžœžœ
˜EJšžœžœ˜Jš
œG™GJšžœ
ž˜
Jšœ
žœ
˜Jšžœžœ
žœ˜J˜Jšœžœ
žœžœ˜IJšžœ˜Jšžœ
˜J˜—Jš
œ™J˜š
 œžœ
žœžœžœ˜IJšžœ
ž˜
Jšžœ
žœ-˜<Jšžœ
˜J˜—š œžœ
žœžœžœžœ˜MJšžœ
ž˜
Jšžœ
žœ-žœ˜BJšžœ
˜J˜—š
 œžœ
žœžœžœ
˜CJš
œ%™%Jš
œK™KJšžœ
ž˜
Jšœžœ
žœ˜)Jšœžœ˜!Jšœžœ˜1Jš
žœžœžœ
žœ
žœ
˜EJšžœ˜Jšžœ
˜J˜—Jš
œ"™"J˜š œžœ
žœžœ
˜8Jš
œP™PJš
œN™NJš
œ™Jšžœ
ž˜
J˜-Jš
žœžœ
žœžœžœ
˜GJšžœ˜Jšžœ
˜J˜—š
 œžœ
žœžœžœ
˜:Jš
œ.™.Jšžœ
ž˜
Jšœ	žœ˜J˜*Jšžœžœ
žœŸ˜3Jš
žœžœ
žœžœžœ
˜>Jšžœ˜Jšžœ
˜J˜—š
 œžœ
žœ	žœžœ˜CJš
œ[™[Jš
œN™NJš
œS™SJš
œ&™&Jšžœ˜Jšœžœ˜Jšœžœ˜'J˜'Jšžœ
žœ˜Jšžœ
˜J˜—š œžœ
žœ˜%Jš
œT™TJš
œ8™8Jšžœ˜Jšžœžœ˜Jšžœžœ
žœ
žœ
˜J˜'Jšžœžœ
žœ
žœ˜<Jšžœžœ%žœ˜Kšžœžœ
žœ(žœ
žœ
ž˜MJšžœžœžœžœ
˜D—Jšžœ˜"Jšžœ
˜J˜J˜—Jš
œ™J˜š
 	œžœ
žœžœžœ˜BJš
œ™Jšžœ
ž˜
Jšœžœ
˜Jšœžœ
˜šžœžœžœž˜/J˜šžœ	ž˜Jšœžœ
žœ˜Jšœžœ
žœ˜Jšžœ
˜—Jšžœ
˜—Jšžœžœ
žœ
žœžœ
žœ
žœ
˜CJšžœ
˜J˜—š
 œžœ
žœžœžœ˜?Jš
œ™Jšžœ
ž˜
Jšœžœ
˜Jšœžœ
˜šžœžœžœž˜/J˜šžœ	ž˜Jšœžœ
žœ˜Jšœžœ
žœ˜Jšžœ
˜—Jšžœ
˜—Jšžœžœ
žœ
žœžœ
žœ
žœ
˜CJšžœ
˜J˜—š
 œžœ
žœžœžœ˜=Jšžœ
žœ
žœžœ
˜-J˜—š
 œžœ
žœžœžœ˜@Jšžœ
žœ
žœžœ
˜*J˜J˜—Jš
œ™J˜Jš
œ™J˜š
 œžœ
žœžœžœ˜RJš
œW™WJšžœ
ž˜
Jšœžœ
˜Jšœžœ˜Jšœžœ˜1J˜šžœžœŸ"˜>Jšœ
žœžœ˜)—šžœ	ž˜Jšžœžœ
žœ	˜5Jš
œG™GJ˜Jšžœ
˜—šžœžœ
˜Jšžœžœ	˜'šžœ
žœžœ˜:Jšžœ
˜Jšžœ˜——šžœ
žœžœžœ˜IJšžœ
˜—Jšžœ˜Jšžœ
˜J˜—š
 œžœ
žœžœžœ˜RJš
œ™Jš
œC™CJšžœ
ž˜
Jšœžœ˜!Jšœžœ˜Jšœžœ
˜Jšœžœ
˜J˜šžœ	ž˜Jšžœžœ	žœ
˜8Jš
œI™IJ˜Jšžœ
˜—šžœžœ
˜Jšžœžœ	˜$šžœ
žœžœ˜6Jšžœ
˜—Jšžœ˜—šžœ
žœžœ˜5Jšžœ˜—Jšžœ˜Jšžœ
˜J˜—š œžœ
žœ˜!J˜Jš	œ œžœžœžœ˜:Jšžœžœ˜Jš
œ<™<Jš
œ™Jšžœ
ž˜
Jšœ
žœ˜'Jšœžœ˜Jšœžœ˜Jšœžœ
˜Jšžœ	žœ
žœ˜š
ž˜J˜Jšžœ	žœ
žœ
˜Jšžœžœ	žœ	˜6Jš
œ
™
Jš
œM™MJšžœ
˜—šžœžœ
˜Jšžœžœ	˜)š
ž˜Jšžœ	žœžœžœ˜MJšžœ
˜—š
ž˜Jšžœžœžœ
˜>Jšžœ
˜——Jšžœ
˜J˜—š œžœ
žœžœžœžœ˜DJš
œ;™;Jš
œ9™9Jšžœ
ž˜
Jšœžœ
˜Jšœžœ˜!šžœžœž˜Jšžœ.žœ
žœ˜?Jšžœ	žœžœžœ˜8Jšžœ
˜—Jšžœ
˜J˜J˜J˜——Jšžœ
˜J˜J˜J˜
J˜˜)Jšœ#žœ
˜&J˜—˜%Jšœ"žœ
˜%J˜—˜HJšœ"žœ
˜%J˜—˜=Jšœ"žœ
˜%J˜—˜$Jšœ#ž˜%J˜—˜SJ˜!J˜—˜iJ˜!J˜—˜§
J˜$J˜—˜=J˜&J˜—Jšœž
œΔ˜ΛJ˜˜*J™"—J˜—…—! 8Š