-- File: DBIndexFilePageImpl.mesa
-- Contents: low-level operations on B-tree file pages
-- Last edited by:
--   MBrown:  February 27, 1981  9:42 PM
--   Cattell: January 17, 1983 6:23 pm
--   Willie-Sue on June 25, 1982 9:23 am 

  DIRECTORY
    DBCache,
    DBCommon,
    DBHeapStorage USING[Node, Free],
    DBStorageInternal,
    DBStoragePagetags,
    DBIndexFilePage,
    DBIndex,
    Inline,
    Rope;

DBIndexFilePageImpl: PROGRAM
  IMPORTS
    DBHeapStorage,
    I: Inline,
    Rope
  EXPORTS
    DBIndexFilePage
  = BEGIN

  Page: TYPE = DBIndex.Page;
  IndexKey: TYPE = DBIndex.IndexKey;
  ItemHandle: TYPE = DBIndex.ItemHandle;
  
  CoreIndexSize: CARDINAL = DBIndex.CoreIndexSize;
  FullPage: CARDINAL = DBIndex.FullPage;
  
  ROPE: TYPE = Rope.ROPE;
  
  WhatDoYouThinkOfThis: SIGNAL = CODE; -- for debugging
  KeyTooBig: ERROR = CODE;
  UnsplittablePage: ERROR = CODE;
  
  keyCount: INT _ 0; -- A check on keys allocated/de-allocated
  
  -- Changes the state of Btree page

  SetSize: PUBLIC PROC [p: Page, i: CARDINAL] =
    BEGIN p.pointer.size _ i END;

  -- Query the state of Btree page

  FreeSpace: PUBLIC PROC [p: Page] RETURNS [CARDINAL] =
    -- Returns the number of free words available
    BEGIN
    indexArraySize: CARDINAL _ p.pointer.size;
    free: CARDINAL_
      IF indexArraySize=0 THEN CoreIndexSize
      ELSE p.pointer.index[indexArraySize - 1] - indexArraySize;
    IF free>CoreIndexSize THEN ERROR;
    RETURN[free]
    END;

  FrontSize: PUBLIC PROC [p: Page, index: CARDINAL] RETURNS [CARDINAL] =
    -- Returns the size(in words) that entries from 0 to index occupy.
    BEGIN RETURN[CoreIndexSize - p.pointer.index[index]] END;

  CoreAddr: PUBLIC PROC [p: Page, i: CARDINAL] RETURNS [ItemHandle] =
    -- Returns the address of i-th entry in p
    BEGIN
    base: LONG POINTER _ @p.pointer.index;
    index: CARDINAL _ (base+i)^;
    IF i>CoreIndexSize THEN ERROR;
    RETURN[
      LOOPHOLE[base+index, ItemHandle]];
    END;

  EndAddr: PUBLIC PROC [p: Page] RETURNS [LONG POINTER] =
    -- (Address of the word of the end of the page)+1
    BEGIN RETURN[p.pointer + FullPage] END;

  SizeOfEntries: PUBLIC PROC [page: Page, from: CARDINAL, to: CARDINAL]
    RETURNS [CARDINAL] =
    -- Returns the number of words, entries from "from" to "to" 
    -- occupy in page
    BEGIN
    left, right: CARDINAL;
    IF to < from THEN RETURN[0];
    left _ page.pointer.index[to];
    right _ IF from = 0 THEN CoreIndexSize ELSE page.pointer.index[from - 1];
    RETURN[right - left]
    END;

  -- Query the value of elements

  Value: PUBLIC PROC [p: Page, index: CARDINAL] RETURNS [DBCommon.DBPage] =
    BEGIN
    RETURN[LOOPHOLE[CoreAddr[p, index].value, DBCommon.DBPage]];
    END;

  Tid: PUBLIC PROC [p: Page, index: CARDINAL] RETURNS [DBStorageInternal.TID] =
    BEGIN
    RETURN[LOOPHOLE[CoreAddr[p, index].value, DBStorageInternal.TID]];
    END;

  Key: PUBLIC PROC [page: Page, index: CARDINAL] RETURNS [IndexKey] =
    -- Returns the key of the index-th entry
    -- Assert: key.length should be valid length unless 0th entry on non-leaf page
    BEGIN
    base: LONG POINTER _ @page.pointer.index;
    offset: CARDINAL _ (base+index)^;
    key: IndexKey_ LOOPHOLE[base+offset+2, IndexKey];
    IF key.length>CoreIndexSize AND (page.depth=1 OR index#0) THEN ERROR;
    RETURN[key]
    END;

  CopyKey: PUBLIC PROC[key: IndexKey] RETURNS [IndexKey] =
    -- Returns the copy of the key
    BEGIN
    ret: IndexKey _ DBHeapStorage.Node[(key.length+3)/2];
    keyCount_ keyCount+1;
    ret.length _ key.length;
    I.LongCOPY[from: @key.text, to: @ret.text, nwords: (key.length+1)/2];
    RETURN[ret];
    END;

  FreeKey: PUBLIC PROC[key: IndexKey] =
    -- Deallocates key from MDS; this is gross.
    BEGIN
    IF key=NIL THEN RETURN;
    keyCount_ keyCount-1;
    DBHeapStorage.Free[I.LowHalf[key]];
    END;

  CreateIndexKey: PUBLIC PROC [s: ROPE] RETURNS [IndexKey] =
    BEGIN
    sLength: CARDINAL _ I.LowHalf[s.Size[]];
    ret: IndexKey _ DBHeapStorage.Node[(sLength+3)/2];
    keyCount_ keyCount+1;
    ret.length _ sLength;
    IF sLength>CoreIndexSize THEN ERROR KeyTooBig;
    FOR i: CARDINAL IN [0..sLength) DO
      ret.text[i]_ s.Fetch[i] ENDLOOP;
    IF (sLength MOD 2) = 1 THEN ret.text[sLength] _ 0C;
    RETURN[ret]
    END;

  Mask: PUBLIC PROC [p: LONG POINTER] =
    -- Turns the right most byte of p^ to 0
    BEGIN p^ _ I.BITAND[p^, 177400B]; END;

  -- Key comparison functions.

  GreaterEq: PUBLIC PROC [left, right: IndexKey] RETURNS [BOOLEAN] =
    -- Returns TRUE iff left>=right
    BEGIN
    leftC: LONG POINTER TO ARRAY OF CARDINAL _ LOOPHOLE[@(left.text), LONG POINTER TO
      ARRAY OF CARDINAL];
    rightC: LONG POINTER TO ARRAY OF CARDINAL _ LOOPHOLE[@(right.text), LONG POINTER TO
      ARRAY OF CARDINAL];
    rightChar: CARDINAL;
    i: CARDINAL;
    FOR i IN [0..MIN[(left.length + 1)/2, (right.length + 1)/2]) DO
      rightChar _ rightC[i];
      SELECT leftC[i] FROM
	> rightChar => RETURN[TRUE];
	< rightChar => RETURN[FALSE];
	ENDCASE;
      REPEAT
      FINISHED => IF left.length >= right.length THEN RETURN[TRUE] ELSE RETURN[FALSE];
      ENDLOOP;
    END;

  LessEq: PUBLIC PROC [left, right: IndexKey] RETURNS [BOOLEAN] =
    -- Returns TRUE iff left<right
    BEGIN
    leftC: LONG POINTER TO ARRAY OF CARDINAL _ LOOPHOLE[@(left.text), LONG POINTER TO
      ARRAY OF CARDINAL];
    rightChar: CARDINAL;
    rightC: LONG POINTER TO ARRAY OF CARDINAL _ LOOPHOLE[@(right.text), LONG POINTER TO
      ARRAY OF CARDINAL];
    i: CARDINAL;
    FOR i IN [0..MIN[(left.length + 1)/2, (right.length + 1)/2]) DO
      rightChar _ rightC[i];
      SELECT leftC[i] FROM
	> rightChar => RETURN[FALSE];
	< rightChar => RETURN[TRUE];
	ENDCASE;
      ENDLOOP;
    IF left.length <= right.length THEN RETURN[TRUE] ELSE RETURN[FALSE]
    END;

  Less: PUBLIC PROC [left, right: IndexKey] RETURNS [BOOLEAN] =
    BEGIN RETURN[NOT GreaterEq[left, right]] END;

  Greater: PUBLIC PROC [left, right: IndexKey] RETURNS [BOOLEAN] =
    BEGIN RETURN[NOT LessEq[left, right]] END;

  -- Basic utilities

  -- Key search functions.

  FindTheFirstLeafKey: PUBLIC PROC [p: Page, key: IndexKey] RETURNS [ret:CARDINAL] =
    -- Returns i such that i=0&key<=a[i] OR 0<i<max[a]&a[i-1]<key<=a[i] OR i=max[a]&a[i-1]<key
    BEGIN
    m: CARDINAL;
    low: CARDINAL _ 0;
    high, sizePMinusOne: CARDINAL _ p.pointer.size-1;
    m _ (low + high)/2;
    IF p.pointer.size = 0 THEN  -- ouch!  try to push on anyway...
      {SIGNAL WhatDoYouThinkOfThis; RETURN[0]};
    UNTIL m = low DO
      IF LessEq[key, Key[p, m]] THEN high _ m ELSE low _ m;
      -- Invariant: (low=0 | Key[p,low]<key)&(high=Size[p]-1 | key<=Key[p,high])
      m _ (low + high)/2;
      ENDLOOP;
    IF low=0 THEN 
      IF LessEq[key, Key[p, 0]] THEN ret _ 0 
      ELSE IF high=sizePMinusOne AND Greater[key, Key[p, high]] 
        THEN ret _ high+1
        ELSE ret _ high
    ELSE IF high=sizePMinusOne AND Less[Key[p, high], key] THEN ret _ high+1 
        ELSE ret _ high; 
    RETURN[ret]
    END;

  FindTheLastLeafKey: PUBLIC PROC [p: Page, key: IndexKey] RETURNS [ret: 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
    BEGIN
    pSize: CARDINAL _ p.pointer.size;
    low: CARDINAL _ 0;
    high: CARDINAL _ pSize - 1;
    m: CARDINAL;
    m _ (low + high)/2;
    UNTIL m = low DO
      IF GreaterEq[key, Key[p, m]] THEN low _ m ELSE high _ m;
      -- Invariant: (low=0 | Key[p, low]<=key)&(high=Size[p]-1 | key<Key[p, high])
      m _ (low + high)/2;
      ENDLOOP;
    IF low=0 THEN 
      IF Less[key, Key[p,0]] THEN ret _ 0 
      ELSE IF high=pSize-1 AND GreaterEq[key, Key[p, high]] 
        THEN ret _ high+1
      ELSE ret _ high
    ELSE IF high=pSize-1 AND GreaterEq[key, Key[p,high]] 
        THEN ret _ high+1 
    ELSE ret _ high
    END;

  FindTheInternalKey: PUBLIC PROC [
    page: Page, key: IndexKey,
    Upper, Lower: PROC [IndexKey, IndexKey] RETURNS [BOOLEAN]] RETURNS [ret:CARDINAL] =
    -- i=0&key(Lower)a[1] OR 0<i<max[a]&a[i](Upper)key(Lower)a[i+1] OR i=max[a]&a[i](Upper)key
    BEGIN
    pageSize: CARDINAL _ page.pointer.size;
    max: CARDINAL _ pageSize - 1;
    min: CARDINAL _ 1;
    m: CARDINAL;
    IF min>max THEN RETURN[0];
    DO
      m _ (max + min)/2;
      IF m = min THEN EXIT;
      IF Upper[key, Key[page, m]] THEN min _ m ELSE max _ m;
      -- Invariant: (min=1 | Key[page, min](Upper)key)&(max=Size[page]-1|key(Lower)Key[page,max])
      ENDLOOP;
    IF min=1 THEN 
      IF Lower[key,Key[page,min]] 
        THEN ret _ 0 
      ELSE IF min#max AND max=pageSize - 1 AND Upper[key, Key[page,max]] 
            THEN ret _ max 
          ELSE ret _ min
    ELSE IF max=pageSize-1 AND Upper[key, Key[page,max]] THEN ret _ max
    ELSE ret _ min
    END;

  JustOver: PUBLIC PROC [p: Page, size: CARDINAL] RETURNS [CARDINAL] =
    -- Find index i such that entries from 0 to i and OverHead and
    -- index arrays (=i+1) is greater than size, but not for i-1
    BEGIN
    i: CARDINAL;
    pSize: CARDINAL _ p.pointer.size;
    FOR i IN [0..pSize) DO
      IF p.pointer.index[i]+size < FullPage + (i + 1) THEN GOTO Over;
      REPEAT Over => RETURN[i]; FINISHED => RETURN[pSize - 1];
      ENDLOOP;
    END;



END.


Change Log

Changed the meaning of FindTheLastLeafKey
	by Suzuki: November 24, 1980  1:09 PM 

Changed JustOver to match the meaning
	by Suzuki: December 2, 1980  9:46 AM 

Changed FindTheInternalKey to assign min to ret in the most general case
	by Suzuki: December 3, 1980  9:28 AM 

Changed FindTheInternalKey so that it can handle 1 entry page
	by Suzuki: December 3, 1980  1:11 PM 

Allocate storage from DBHeapStorage.
	by MBrown: February 27, 1981  6:34 PM

Added checks on key lengths, index passed to CoreAddr, and FreeSize returned value.
	by Cattell: June 19, 1982 3:51 pm

Changed name of CopyIndexKey to CreateIndexKey.  Added check on key length too big, and signal KeyTooBig.
	by Cattell: June 20, 1982 6:32 pm

Changed FindTheFirstLeafKey to try to signal and attempt to push on if it encounters a zero-size page ('cause my personal database is in a rubble of bits otherwise...)
	by Cattell: August 11, 1982 10:15 am
 
Removed some procs to DBIndexModImpl.  Moved some procs here.
	by Cattell: September 21, 1982 8:37 pm

Fixed B-tree bug #19: this one took 4 man-hours, because it took so long to reproduce and involved a fairly complicated call stack.  The symptom was a garbage key in the root node after a deletion.  If re-arranging two sons of a node causes a new larger key to be stored in the node, which in turn is over threshold to cause the node to split, then in certain cases the pointer that SplitPage creates as the splitKey, the last key on the node, gets overwritten before it gets used by the grandparent.  The solution is that SplitPage should copy the key.  This ripples through several procedures in other modules which change their assumptions about allocation/deallocation of keys: DBIndexImpl.SplitInternal, etc.