-- File: DBIndexFilePageImpl.mesa
-- Contents: low-level operations on B-tree file pages
-- Last edited by:
-- MBrown: February 27, 1981 9:42 PM
-- Cattell: January 17, 1983 6:23 pm
-- Willie-Sue on June 25, 1982 9:23 am
DIRECTORY
DBCache,
DBCommon,
DBHeapStorage USING[Node, Free],
DBStorageInternal,
DBStoragePagetags,
DBIndexFilePage,
DBIndex,
Inline,
Rope;
DBIndexFilePageImpl: PROGRAM
IMPORTS
DBHeapStorage,
I: Inline,
Rope
EXPORTS
DBIndexFilePage
= BEGIN
Page: TYPE = DBIndex.Page;
IndexKey: TYPE = DBIndex.IndexKey;
ItemHandle: TYPE = DBIndex.ItemHandle;
CoreIndexSize: CARDINAL = DBIndex.CoreIndexSize;
FullPage: CARDINAL = DBIndex.FullPage;
ROPE: TYPE = Rope.ROPE;
WhatDoYouThinkOfThis: SIGNAL = CODE; -- for debugging
KeyTooBig: ERROR = CODE;
UnsplittablePage: ERROR = CODE;
keyCount: INT ← 0; -- A check on keys allocated/de-allocated
-- 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;
CopyKey: PUBLIC PROC[key: IndexKey] RETURNS [IndexKey] =
-- Returns the copy of the key
BEGIN
ret: IndexKey ← DBHeapStorage.Node[(key.length+3)/2];
keyCount← keyCount+1;
ret.length ← key.length;
I.LongCOPY[from: @key.text, to: @ret.text, nwords: (key.length+1)/2];
RETURN[ret];
END;
FreeKey: PUBLIC PROC[key: IndexKey] =
-- Deallocates key from MDS; this is gross.
BEGIN
IF key=NIL THEN RETURN;
keyCount← keyCount-1;
DBHeapStorage.Free[I.LowHalf[key]];
END;
CreateIndexKey: PUBLIC PROC [s: ROPE] RETURNS [IndexKey] =
BEGIN
sLength: CARDINAL ← I.LowHalf[s.Size[]];
ret: IndexKey ← DBHeapStorage.Node[(sLength+3)/2];
keyCount← keyCount+1;
ret.length ← sLength;
IF sLength>CoreIndexSize THEN ERROR KeyTooBig;
FOR i: CARDINAL IN [0..sLength) DO
ret.text[i]← s.Fetch[i] ENDLOOP;
IF (sLength MOD 2) = 1 THEN ret.text[sLength] ← 0C;
RETURN[ret]
END;
Mask: PUBLIC PROC [p: LONG POINTER] =
-- Turns the right most byte of p↑ to 0
BEGIN p↑ ← I.BITAND[p↑, 177400B]; END;
-- Key comparison functions.
GreaterEq: PUBLIC PROC [left, right: IndexKey] RETURNS [BOOLEAN] =
-- Returns TRUE iff left>=right
BEGIN
leftC: LONG POINTER TO ARRAY OF CARDINAL ← LOOPHOLE[@(left.text), LONG POINTER TO
ARRAY OF CARDINAL];
rightC: LONG POINTER TO ARRAY OF CARDINAL ← LOOPHOLE[@(right.text), LONG POINTER TO
ARRAY OF CARDINAL];
rightChar: CARDINAL;
i: CARDINAL;
FOR i IN [0..MIN[(left.length + 1)/2, (right.length + 1)/2]) DO
rightChar ← rightC[i];
SELECT leftC[i] FROM
> rightChar => RETURN[TRUE];
< rightChar => RETURN[FALSE];
ENDCASE;
REPEAT
FINISHED => IF left.length >= right.length THEN RETURN[TRUE] ELSE RETURN[FALSE];
ENDLOOP;
END;
LessEq: PUBLIC PROC [left, right: IndexKey] RETURNS [BOOLEAN] =
-- Returns TRUE iff left<right
BEGIN
leftC: LONG POINTER TO ARRAY OF CARDINAL ← LOOPHOLE[@(left.text), LONG POINTER TO
ARRAY OF CARDINAL];
rightChar: CARDINAL;
rightC: LONG POINTER TO ARRAY OF CARDINAL ← LOOPHOLE[@(right.text), LONG POINTER TO
ARRAY OF CARDINAL];
i: CARDINAL;
FOR i IN [0..MIN[(left.length + 1)/2, (right.length + 1)/2]) DO
rightChar ← rightC[i];
SELECT leftC[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.