DBIndexFilePageImpl:
CEDAR
PROGRAM
= 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;
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.
fakeIndexKeys: LIST OF FakeIndexKey;
fakeIndexKeyCount: INT ← 0; -- Should equal fakeIndexKey.Length[], never more than 2 or 3
Changes the state of Btree page
SetSize:
PUBLIC
PROC [p: Page, i:
CARDINAL] =
TRUSTED BEGIN p.pointer.size ← i END;
Query the state of Btree page
FreeSpace:
PUBLIC
PROC [p: Page]
RETURNS [
CARDINAL] =
Returns the number of free words available
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] =
Returns the size(in words) that entries from 0 to index occupy.
TRUSTED BEGIN RETURN[CoreIndexSize - p.pointer.index[index]] END;
CoreAddr:
PUBLIC
PROC [p: Page, i:
CARDINAL]
RETURNS [ItemHandle] =
Returns the address of i-th entry in p
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] =
(Address of the word of the end of the page)+1
TRUSTED BEGIN RETURN[p.pointer + FullPage] END;
SizeOfEntries:
PUBLIC
PROC [page: Page, from:
CARDINAL, to:
CARDINAL]
RETURNS [CARDINAL] =
Returns the number of words, entries from "from" to "to" occupy in page
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;
Query the value of elements
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] =
Returns the key of the index-th entry
Assert: key.length should be valid length unless 0th entry on non-leaf page
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;
Allocate and de-allocate IndexKeys
CopyKey:
PUBLIC
PROC[key: IndexKey]
RETURNS [IndexKey] =
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.
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] =
Copies rope s into a newly allocated 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] =
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.
BEGIN fk: FakeIndexKey;
fk← NEW[KeyBody[bytes]];
fakeIndexKeys← CONS[fk, fakeIndexKeys];
fakeIndexKeyCount← fakeIndexKeyCount+1;
RETURN[LOOPHOLE[fk]]
END;
FreeKey:
PUBLIC
PROC[key: IndexKey] =
"Deallocates" key; actually, just removes it from the fakeIndexKeys list so that the
garbage collector will find it has zero reference count.
BEGIN fk: FakeIndexKey;
TRUSTED { fk ← LOOPHOLE[key] };
IF key=NIL THEN RETURN;
fakeIndexKeyCount← fakeIndexKeyCount-1;
IF fakeIndexKeys=NIL THEN ERROR DB.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 DB.InternalError;
END;
Key comparison functions.
GreaterEq:
PUBLIC
PROC [left, right: IndexKey]
RETURNS [
BOOLEAN] =
Returns TRUE iff left>=right
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] =
Returns TRUE iff left<right
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;
Basic utilities
Key search functions.
FindTheFirstLeafKey:
PUBLIC
PROC [p: Page, key: IndexKey]
RETURNS [ret:
CARDINAL] =
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
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;
Invariant: (low=0 | Key[p,low]<key)&(high=Size[p]-1 | key<=Key[p,high])
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] =
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
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;
Invariant: (low=0 | Key[p, low]<=key)&(high=Size[p]-1 | key<Key[p, high])
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] =
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
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;
Invariant:
(min=1 | Key[page, min](Upper)key)&(max=Size[page]-1|key(Lower)Key[page,max])
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] =
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
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;