DBIndexPageImpl:
CEDAR
PROGRAM
IMPORTS DBCommon, DBSegment, DBStorage, DBStorageField, Rope, RefText
EXPORTS DBIndexPage
= BEGIN
Core: TYPE = DBIndex.Core;
Page: TYPE = DBIndex.Page;
PageObject: TYPE = DBIndex.PageObject;
RealIndexHandle: TYPE = DBIndex.RealIndexHandle;
ItemHandle: TYPE = DBIndex.ItemHandle;
IndexKey: TYPE = DBIndex.IndexKey;
KeyBody: TYPE = DBIndex.KeyBody;
CoreIndexSize: CARDINAL = DBIndex.CoreIndexSize;
FullPage: CARDINAL = DBIndex.FullPage;
global vars
PageList: Page;
TakeALookAtThis: SIGNAL = CODE;
BadPage: PUBLIC SIGNAL = CODE;
WhatDoYouThinkOfThis: SIGNAL = CODE; -- for debugging
Public procs
DestroyPageList:
PUBLIC
PROC [s: DBCommon.Segment] =
BEGIN
p: Page;
segID: DBCommon.SegmentID = DBSegment.SegmentIDFromSegment[s];
p ← PageList;
DO
IF DBSegment.SegmentIDFromDBPage[p.db] = segID
THEN {
IF NOT p.free THEN UnlockPage[p]; -- unlock page
p.tree← NIL; p.cache← NIL; p.db← 0; p.pointer← NIL; p.depth← 0 }; -- erase invalid data
p ← p.front;
IF p=PageList THEN EXIT;
ENDLOOP;
END;
DestroyPage:
PUBLIC
PROC [segment: DBCommon.DBPage, p: Page, db: DBCommon.DBPage] =
Deallocates the Page and DBPage; it should have a lock count of 1
BEGIN
DBSegment.FreePage[segment, db, p.cache];
p.free ← TRUE;
END;
UnlockPage:
PUBLIC
PROC [p: Page] =
BEGIN
CheckTag[p.pointer];
DBSegment.UnlockPage[p.cache];
p.free ← TRUE;
END;
WriteAndUnlockPage:
PUBLIC
PROC [p: Page] =
BEGIN
CheckTag[p.pointer];
DBSegment.WriteLockedPage[p.cache];
DBSegment.UnlockPage[p.cache];
p.free ← TRUE;
END;
WritePage:
PUBLIC
PROC [p: DBIndex.Page] =
Mark page p as having been written, but keep locked.
BEGIN
CheckTag[p.pointer];
DBSegment.WriteLockedPage[p.cache];
END;
AllocatePage:
PROC
RETURNS [Page] =
Just allocates the DBIndex.Page, i.e. the HANDLE for the DBCommon.Page. Returns a "free" page; caller is responsible for marking it not free.
BEGIN
ret: Page;
p: Page ← PageList;
UNTIL p.free =
TRUE
DO
p ← p.front;
IF p=PageList THEN GOTO NoFreePage;
REPEAT
NoFreePage => {ret ←
NEW[PageObject];
PageList.front.back ← ret;
ret^ ← [NIL, DBCommon.NullDBPage, NIL, 0, NIL, TRUE, PageList.front, PageList];
PageList.front ← ret;
RETURN[ret]};
FINISHED => {RETURN[p]}
ENDLOOP;
END;
CreateEmptyPage:
PUBLIC
PROC [tree: RealIndexHandle, level:
CARDINAL, s: DBCommon.DBPage]
RETURNS [Page] = TRUSTED
level = 1 if it is a leaf
BEGIN
cache: DBCommon.CacheHandle;
db: DBCommon.DBPage;
h: Page;
p: LONG POINTER TO Core;
[db, cache, p] ← DBSegment.AllocPage[s];
p.tag.pageTag ← DBStoragePage.BTree;
p.left ← p.right ← DBCommon.NullDBPage;
p.size ← 0;
h ← AllocatePage[];
h.tree ← tree; h.db ← db; h.cache ← cache; h.depth ← level; h.pointer ← p;
h.free ← FALSE;
RETURN[h];
END;
GetPage:
PUBLIC
PROC [tree: RealIndexHandle, db: DBCommon.DBPage, level:
CARDINAL]
RETURNS [Page] =
TRUSTED BEGIN
p: Page ← AllocatePage[];
cache: DBCommon.CacheHandle;
pointer: LONG POINTER TO Core;
[cache, pointer] ← DBSegment.ReadPage[db, p.cache];
CheckTag[pointer];
p.tree ← tree; p.db ← db; p.cache ← cache; p.depth ← level; p.pointer ← pointer;
p.free ← FALSE;
RETURN[p]
END;
CheckTag:
PUBLIC
PROC[p:
LONG
POINTER
TO Core] =
TRUSTED {
IF p.tag.pageTag#DBStoragePage.BTree THEN SIGNAL BadPage};
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 [DBCommon.TID] =
TRUSTED BEGIN
RETURN[LOOPHOLE[CoreAddr[p, index].value, DBCommon.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;
Key comparison functions.
GreaterEq:
PUBLIC
PROC [left: Rope.
ROPE, right: IndexKey]
RETURNS [
BOOLEAN] =
Returns TRUE iff left>=right
TRUSTED BEGIN
rightChar: CHAR;
i: INT;
FOR i
IN [0..
MIN[left.Size[], right.length])
DO
rightChar ← right[i];
SELECT left.Fetch[i]
FROM
> rightChar => RETURN[TRUE];
< rightChar => RETURN[FALSE];
ENDCASE;
ENDLOOP;
IF left.Size[] >= right.length THEN RETURN[TRUE] ELSE RETURN[FALSE]
END;
LessEq:
PUBLIC
PROC [left: Rope.
ROPE, right: IndexKey]
RETURNS [
BOOLEAN] =
Returns TRUE iff left<right
TRUSTED BEGIN
rightChar: CHAR;
i: INT;
FOR i
IN [0..
MIN[left.Size[], right.length])
DO
rightChar ← right[i];
SELECT left.Fetch[i]
FROM
> rightChar => RETURN[FALSE];
< rightChar => RETURN[TRUE];
ENDCASE;
ENDLOOP;
IF left.Size[] <= right.length THEN RETURN[TRUE] ELSE RETURN[FALSE]
END;
Less:
PUBLIC
PROC [left: Rope.
ROPE, right: IndexKey]
RETURNS [
BOOLEAN] =
BEGIN RETURN[NOT GreaterEq[left, right]] END;
Greater:
PUBLIC
PROC [left: Rope.
ROPE, right: IndexKey]
RETURNS [
BOOLEAN] =
BEGIN RETURN[NOT LessEq[left, right]] END;
Basic utilities
Key search functions.
FindTheFirstLeafKey:
PUBLIC
PROC [p: Page, key:
REF TEXT]
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[RefText.TrustTextAsRope[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[RefText.TrustTextAsRope[key], Key[p, 0]] THEN ret ← 0
ELSE
IF high=sizePMinusOne
AND Greater[RefText.TrustTextAsRope[key], Key[p, high]]
THEN ret ← high+1
ELSE ret ← high
ELSE
IF high=sizePMinusOne
AND Greater[RefText.TrustTextAsRope[key], Key[p, high]]
THEN ret ← high+1
ELSE ret ← high;
RETURN[ret]
END;
FindTheLastLeafKey:
PUBLIC
PROC [p: Page, key:
REF TEXT]
RETURNS [ret:
CARDINAL] =
Returns i such that 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[RefText.TrustTextAsRope[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[RefText.TrustTextAsRope[key], Key[p,0]] THEN ret ← 0
ELSE
IF high=pSize-1
AND GreaterEq[RefText.TrustTextAsRope[key], Key[p, high]]
THEN ret ← high+1
ELSE ret ← high
ELSE
IF high=pSize-1
AND GreaterEq[RefText.TrustTextAsRope[key], Key[p,high]]
THEN ret ← high+1
ELSE ret ← high
END;
FindTheInternalKey:
PUBLIC
PROC [page: Page, key:
REF TEXT, Upper,
Lower:
PROC [Rope.
ROPE, 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[RefText.TrustTextAsRope[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[RefText.TrustTextAsRope[key], Key[page,min]] THEN ret ← 0
ELSE
IF min#max AND max=pageSize - 1 AND Upper[RefText.TrustTextAsRope[key], Key[page,max]] THEN ret ← max
ELSE ret ← min
ELSE
IF max=pageSize-1 AND Upper[RefText.TrustTextAsRope[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;
Manipulating the index tuple handles.
ReadIndexObject:
PUBLIC
PROC[t: DBStorage.TupleHandle, result: DBIndexPage.TupleTree] = {
PARAMETERS: t is an index tuple, i.e. a tuple whose first field is an index object; result points to a TupleTreeRecord that may be overwritten.
EFFECTS: the index object contained in tuple t is written into result.
IF SIZE[DBIndexPage.TupleTreeRecord] > DBStorage.IndexObjectSize THEN ERROR DBCommon.InternalError;
DBStorage.ReadNWord[t, DBStorageField.TuplesetFieldHandle[], result];
};--ReadIndexObject
WriteIndexObject:
PUBLIC
PROC[t: DBStorage.TupleHandle, val: DBIndexPage.TupleTree] = {
PARAMETERS: an index tuple, i.e. a tuple whose first field is an index object, and a value for such and object.
EFFECTS: writes the value val into the index object field of tuple t.
IF SIZE[DBIndexPage.TupleTreeRecord] # DBStorage.IndexObjectSize THEN ERROR DBCommon.InternalError;
DBStorage.WriteNWord[t, DBStorageField.TuplesetFieldHandle[], val];
};--WriteIndexObject