-- File: DBIndexFilePageImpl.mesa
-- 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 June 25, 1982 9:23 am
DIRECTORY
DBCache,
DBCommon,
DBEnvironment,
DBStorageInternal,
DBStoragePagetags,
DBIndexFilePage,
DBIndex,
Rope;
DBIndexFilePageImpl: 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;
-- 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] =
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
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.
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
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
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
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] =
BEGIN
RETURN[LOOPHOLE[CoreAddr[p, index].value, DBCommon.DBPage]];
END;
Tid: PUBLIC PROC [p: Page, index: CARDINAL] RETURNS [DBStorageInternal.TID] =
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
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.
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.
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← 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;
-- Key comparison functions.
GreaterEq: PUBLIC PROC [left, right: IndexKey] RETURNS [BOOLEAN] =
-- Returns TRUE iff left>=right
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
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
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
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
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
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.