-- 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 15, 1983 3:36 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 does not point to real index
    ];

  IndexKey: TYPE = LONG POINTER TO KeyBody;
  KeyBody: TYPE = MACHINE DEPENDENT RECORD [
    text: PACKED SEQUENCE length: CARDINAL OF CHAR];
      
  Page: TYPE = REF PageObject;

  PageObject: TYPE = RECORD [
    tree: RealIndexHandle,
    db: DBCommon.DBPage,
    cache: DBCache.CacheHandle,
    depth: CARDINAL, -- depth = 1 for leaf, >1 for non-leaf (0 for empty tree)
    pointer: LONG POINTER TO Core, -- points to the cached page
    free: BOOLEAN, -- so that this page object may be re-used
    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 a Btree page.  The index array is further 
  -- divided as follows: The front part of index is ARRAY[0..size) OF 
  -- CARDINAL, whose elements are indices of this array.  They 
  -- represent the start index of the 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 a 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.

Changed by MBrown on September 15, 1983 12:46 pm
-- Conversion to 5.0.  IndexKeys may contains REFs to allocated storage, or pointers.