-- File: DBIndex.mesa
-- Contents: Declarations of DBIndex level data types, and initialize/finalize procs.
-- Last edited by:
-- Suzuki on May 8, 1980 3:47 PM
-- Cattell on September 21, 1982 9:08 pm
-- MBrown on December 2, 1982 2:37 pm

DIRECTORY
DBCommon,
DBCache,
DBStorage,
DBStorageInternal,
DBStoragePagetags;

DBIndex: DEFINITIONS = BEGIN

RealIndexHandle: TYPE = REF IndexObject;

IndexObject: TYPE = RECORD [
tid: DBStorageInternal.TID,
segment: DBCommon.DBPage, -- segment in which the index lives
rootDB: DBCommon.DBPage, -- NullDBPage iff the index is empty
root: DBCache.CacheHandle, -- always a hint
depth: CARDINAL, -- 0 if the index is empty
front, back: RealIndexHandle, -- for doubly linkded lists
free: BOOLEAN -- TRUE iff it odes not point to real index
];

IndexKey: TYPE = LONG POINTER TO MACHINE DEPENDENT RECORD[length: CARDINAL, text: PACKED ARRAY [0..0) OF CHARACTER];

Page: TYPE = REF PageObject;

PageObject: TYPE = RECORD [
tree: RealIndexHandle,
db: DBCommon.DBPage,
cache: DBCache.CacheHandle,
depth: CARDINAL,
pointer: LONG POINTER TO Core, -- points to the cached page
free: BOOLEAN,
front: Page,
back: Page];

State: TYPE = {normal, split, merge, delete, deleteFromNextPage};

Core: TYPE = MACHINE DEPENDENT RECORD [
tag: DBStoragePagetags.PageHeader, -- =6 for Btree
left, right: DBCommon.DBPage,
size: CARDINAL,
index: ARRAY [0..CoreIndexSize) OF CARDINAL];

-- Core is the data structure of Btree page. Array index is further
--divided as follows: Front part of index is ARRAY[0..size) OF
--CARDINAL, whose elements are indices of this array. They
--represent the start index of i-th entry. The End part of index
--is the entries which are allocated from the end. Each entry
--consists of two words of value and Bstring. However, for internal
--nodes, the 0-th entry consists of only value.

ItemHandle: TYPE = LONG POINTER TO Item;

Item: TYPE = MACHINE DEPENDENT RECORD [
value: LONG CARDINAL,
length: CARDINAL,
text: PACKED ARRAY [0..0) OF CHARACTER];

-- Item is the internal object representing <key,value> pair.

-- Constants

OverHead: CARDINAL = 6;

FullPage: CARDINAL = DBCommon.WordsPerPage;
HalfPage: CARDINAL = FullPage/2 - 2;

CoreIndexSize: CARDINAL = FullPage - OverHead;



-- Initialization and finalization procs: here because they don't fit anywhere else

InitializeIndex: PROCEDURE;
-- RESULTS: initializes the internal structure of dbindeximpl.
-- NOTE: This procedure should be called from DBStorage.Initialize.

CallAfterFinishTransaction: PROC;


END.--DBIndex


CHANGE LOG

Created by Suzuki on May 8, 1980 3:49 PM
-- Created for use by DBStorage. They should be called by CreateDatabase, OpenDatabase, and CloseDatabase.

Re-created by Cattell on September 21, 1982 9:09 pm
-- Moved DBIndexInternal into here: its former log follows:

Changed halfPage from FullPage/2 to FullPage/2 - 2 to try to fix some boundary threshold problems on when to split and merge pages.
 by Cattell: June 22, 1982 10:32 am

Changed RealIndexHandle and Page to be REFs.
by Cattell: August 6, 1982 2:17 pm

Changed by MBrown on December 2, 1982 2:35 pm
-- Eliminated Finalize, added CallAfterFinishTransaction.