-- File: DBIndexFilePage.mesa
-- last edited by:
-- Cattell on September 29, 1983 11:22 am
-- MBrown on 17-Jun-81 9:56:21

DIRECTORY
DBCommon USING[DBPage],
DBStorageInternal USING[TID],
DBIndex USING[Page, IndexKey, ItemHandle],
PrincOpsUtils USING[LongCOPY],
Rope USING[ROPE];

DBIndexFilePage: DEFINITIONS
IMPORTS PrincOpsUtils =

BEGIN

Page: TYPE = DBIndex.Page;
IndexKey: TYPE = DBIndex.IndexKey;

ROPE: TYPE = Rope.ROPE;

-- Changes the state of Btree page

SetSize: PROC [p: Page, i: CARDINAL];

-- Query the state of Btree page

FreeSpace: PROC [p: Page] RETURNS [CARDINAL];
-- Returns the number free words available

FrontSize: PROC [p: Page, index: CARDINAL] RETURNS [CARDINAL];
-- Returns the size(in words) that entries from 0 to index occupy.

CoreAddr: PROC [p: Page, i: CARDINAL] RETURNS [DBIndex.ItemHandle];
-- Returns the address of i-th entry in p

EndAddr: PROC [p: Page] RETURNS [LONG POINTER];
-- (Address of the word of the end of the page)+1

SizeOfEntries: PROC [page: Page, from: CARDINAL, to: CARDINAL]
RETURNS [CARDINAL];
-- Returns the number of words, entries from "from" to "to"
-- occupy in page

-- Query the value of elements

Value: PROC [p: Page, index: CARDINAL] RETURNS [DBCommon.DBPage];

Tid: PROC [p: Page, index: CARDINAL] RETURNS [DBStorageInternal.TID];

Key: PROC [page: Page, index: CARDINAL] RETURNS [IndexKey];
-- Returns the key of index-th entry

CopyKey: PROC[key: IndexKey] RETURNS [IndexKey];
-- Returns the copy of the key

FreeKey: PROC [key: IndexKey];
-- "Deallocates" key

CreateIndexKey: PROC [s: ROPE] RETURNS [IndexKey];
-- Creates a new key with s as initial value

AllocateIndexKey: PUBLIC PROC [bytes: INT] RETURNS[key: IndexKey];
-- Create a new key with given number of bytes, but does not initialize its value.

-- Key comparison functions.

GreaterEq: PROC [left, right: IndexKey] RETURNS [BOOLEAN];
-- Returns TRUE iff left>=right

LessEq: PROC [left, right: IndexKey] RETURNS [BOOLEAN];
-- Returns TRUE iff left<right

Less: PROC [left, right: IndexKey] RETURNS [BOOLEAN];

Greater: PROC [left, right: IndexKey] RETURNS [BOOLEAN];

-- Basic utilities

LongCOPY: PROC [from, to: LONG POINTER, nwords: CARDINAL] =
INLINE BEGIN
i: CARDINAL;
IF nwords > 256 THEN ERROR;
IF LOOPHOLE[to, LONG CARDINAL] IN
(LOOPHOLE[from, LONG CARDINAL]..LOOPHOLE[from, LONG CARDINAL] + nwords) THEN
FOR i DECREASING IN [0..nwords) DO (to + i)^ ← (from + i)^; ENDLOOP
ELSE PrincOpsUtils.LongCOPY[from: from, nwords: nwords, to: to];
END;

-- Key search functions.

FindTheFirstLeafKey: PROC [p: Page, key: IndexKey] RETURNS [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

FindTheLastLeafKey: PROC [p: Page, key: IndexKey] RETURNS [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

FindTheFirstInternalKey: PROC [page: Page, key: IndexKey]
RETURNS [CARDINAL] =
-- i=0&key<=a[1] OR 0<i<max[a]&a[i]<key<=a[i+1] OR i=max[a]&a[i]<key
INLINE BEGIN RETURN[FindTheInternalKey[page, key, Greater, LessEq]]; END;

FindTheLastInternalKey: PROC [page: Page, key: IndexKey]
RETURNS [CARDINAL] =
-- i=0&key<a[1] OR 0<i<max[a]&a[i]<=key<a[i+1] OR i=max[a]&a[i]<=key
INLINE BEGIN RETURN[FindTheInternalKey[page, key, GreaterEq, Less]]; END;

FindTheInternalKey: PROC [
page: Page, key: IndexKey,
Upper, Lower: PROC [IndexKey, IndexKey] RETURNS [BOOLEAN]] RETURNS [CARDINAL];

JustOver: PROC [p: Page, size: CARDINAL] RETURNS [CARDINAL];
-- Find index i such that entries from 0 to i and OverHead and
-- index arrays (size=i+1) is greater than halfPage, but not for i-1


END.


CHANGE LOG

Created by Suzuki

Changed by MBrown on 17-Jun-81 9:55:35
-- IndexInternal -> DBIndexInternal.

Changed by Cattell on June 20, 1982 6:33 pm
-- CopyIndexKey -> CreateIndexKey. Add ERROR KeyTooBig. Rope.Ref -> ROPE.

Changed by Cattell on September 21, 1982 8:34 pm
-- Removed StoreEntry, StoreKey, StoreEntryInPage, moved to DBIndexModImpl.

Changed by Cattell on January 17, 1983 6:09 pm
-- Moved SplitPage to DBIndexOpImpl.