File: DBIndexPage.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Willie-Sue, February 15, 1985 3:41:24 pm PST
Widom, September 4, 1985 9:07:35 pm PDT
Donahue, May 22, 1986 11:35:20 am PDT
Last edited by:
Suzuki: 2-Apr-81 16:09:21
Cattell: September 21, 1982 9:23 pm
DIRECTORY
DBCommon USING[DBPage, Segment, TID],
DBIndex USING [Core, Page, RealIndexHandle, ItemHandle, IndexKey],
DBStorage USING[TupleHandle],
Rope USING[ROPE];
DBIndexPage: CEDAR DEFINITIONS =
BEGIN
Page: TYPE = DBIndex.Page;
IndexKey: TYPE = DBIndex.IndexKey;
TupleTree: TYPE = REF TupleTreeRecord;
TupleTreeRecord:
TYPE =
MACHINE
DEPENDENT
RECORD[
This is the part of BTree that is permanently stored in the database.
rootPA: DBCommon.DBPage,
B-Tree root page address
depth:
CARDINAL,
B-Tree depth
tid: DBCommon.
TID,
TID of tuple that holds permanent copy of this object
segment: DBCommon.DBPage,
Segment containing this B-Tree (source of pages)
padding:
ARRAY[0..13)
OF
CARDINAL←
ALL[0]
SIZE must exactly equal DBStorage.IndexObjectSize now that copy REFs in/out of a db
];--TupleTreeRecord
Managing the BTree page cache
BadPage: SIGNAL; -- if page is not a B-Tree page
DestroyPageList:
PROC [s: DBCommon.Segment];
Frees the list of page records (DBIndex.Pages) that DBIndexPage maintains
DestroyPage:
PROC [segment: DBCommon.DBPage, p: DBIndex.Page, db: DBCommon.DBPage];
Unlock the page and de-allocate the page in the database for re-use.
UnlockPage:
PROC [p: DBIndex.Page];
Should be called when the client no longer has pointers into page and p thrown away
WritePage:
PROC [p: DBIndex.Page];
Mark page p as having been modified, but keep locked.
WriteAndUnlockPage:
PROC [p: DBIndex.Page];
Call when page no longer in use, and page has been modified.
CreateEmptyPage:
PROC [tree: DBIndex.RealIndexHandle, level:
CARDINAL, s: DBCommon.DBPage]
RETURNS [DBIndex.Page];
Allocates a new DBCommon.DBPage with associated DBIndex.Page, level = 1 if it is a leaf
GetPage:
PROC [tree: DBIndex.RealIndexHandle, db: DBCommon.DBPage, level:
CARDINAL]
RETURNS [DBIndex.Page];
Makes DBIndex.Page pointing to given DBCommon.DBPage.
CheckTag: PROC[LONG POINTER TO DBIndex.Core];
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 [DBCommon.TID];
Key:
PROC [page: Page, index:
CARDINAL]
RETURNS [IndexKey];
Returns the key of index-th entry
Key comparison functions.
GreaterEq:
PROC [left: Rope.
ROPE, right: IndexKey]
RETURNS [
BOOLEAN];
Returns TRUE iff left>=right
LessEq:
PROC [left: Rope.
ROPE, right: IndexKey]
RETURNS [
BOOLEAN];
Returns TRUE iff left<right
Less: PROC [left: Rope.ROPE, right: IndexKey] RETURNS [BOOLEAN];
Greater: PROC [left: Rope.ROPE, right: IndexKey] RETURNS [BOOLEAN];
Key search functions.
FindTheFirstLeafKey:
PROC [p: Page, key:
REF TEXT]
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:
REF TEXT]
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
FindTheFirstInternalKey:
PROC [page: Page, key:
REF TEXT]
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:
REF TEXT]
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:
REF
TEXT, Upper, Lower:
PROC [Rope.
ROPE, 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
Manipulating the index tuple handles.
ReadIndexObject:
PUBLIC
PROC[t: DBStorage.TupleHandle, result: 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.
WriteIndexObject:
PUBLIC
PROC[t: DBStorage.TupleHandle, val: 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.
END.
Change Log
By Cattell September 22, 1982 12:57 pm: Changed names to be clearer. Use UnlockPage instead of FreePage, GetPage instead of CreateOldPage, etc.
Changed by Willie-Sue on February 15, 1985
made Cedar, added tioga formatting