File: DBIndexFilePage.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Willie-Sue, March 19, 1985 6:12:10 pm PST
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:
CEDAR
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] =
TRUSTED 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.
Changed by Willie-Sue on February 15, 1985
made Cedar, added tioga formatting