-- 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.