-- File: DBIndexModImpl.mesa
-- Contents: All DBIndex package database modifications go through this module
-- Created from: pieces of former DBIndexFilePageImpl, DBIndexOpImpl, DBIndexImpl,
--   and DBIndexInternalImpl
-- Invariant: All public procedures should set dirty bit for B-Tree page; no internal ones
--   should do so.  No other module should set dirty bit or modify B-Tree pages.
-- Created by Cattell on September 21, 1982 8:28 pm
-- Last edited by
  -- Cattell: September 23, 1982 10:37 am 

  DIRECTORY
    DBCache,
    DBCommon,
    DBSegment,
    DBStoragePagetags,
    DBIndexFilePage,
    DBIndex,
    DBIndexMod,
    Inline USING[LongCOPY, LowHalf],
    DBIndexOp,
    DBIndexPage;

DBIndexModImpl: PROGRAM
  IMPORTS
    DBSegment,
    DBIndexFilePage,
    I: Inline,
    DBIndexOp,
    DBIndexPage
  EXPORTS
    DBIndexMod
  = 

BEGIN OPEN DBIndexFilePage;


Page: TYPE = DBIndex.Page;
Core: TYPE = DBIndex.Core;
IndexKey: TYPE = DBIndex.IndexKey;
ItemHandle: TYPE = DBIndex.ItemHandle;
State: TYPE = DBIndex.State;
  
OverHead: CARDINAL = DBIndex.OverHead;
FullPage: CARDINAL = DBIndex.FullPage;
CoreIndexSize: CARDINAL = DBIndex.CoreIndexSize;
HalfPage: CARDINAL = DBIndex.HalfPage; 

KeyTooLarge: SIGNAL = CODE;
BadBTree: SIGNAL = CODE;
OutOfBound: SIGNAL = CODE;
ThisLooksSuspicious: SIGNAL = CODE;
PageOverflow: ERROR = CODE; 
  

-- From former DBIndexImpl

  InsertTwoEntriesToEmptyPage: PUBLIC PROC
       [page: Page, first: LONG CARDINAL, key: IndexKey, second: LONG CARDINAL] = {
    -- "page" is empty and an internal node.
    -- Inserts two entries "first" and "second" with the separator "key"
    index: CARDINAL; 
    core: LONG POINTER TO Core ← page.pointer;
    DBIndexPage.WritePage[page];
    IF key.length > CoreIndexSize - 7 THEN ERROR KeyTooLarge; 
    core.index[0] ← CoreIndexSize - 2; 
    LOOPHOLE[@core.index[CoreIndexSize - 2], ItemHandle].value ← first; 
    index ← core.index[1] ← CoreIndexSize - (key.length + 11) / 2; 
    core.size ← 2; 
    StoreEntryInPage[core, index, key, second]
    }; 
  
  MoveEntriesToRightInternal: PUBLIC PROC
       [from, to: Page, key: IndexKey, nentries: CARDINAL] = {
    -- "from" is to the left of "to"
    -- "key" is the dividing key between from and to
    -- "nentries" are moved (returns if 0)
    length: CARDINAL ← (key.length + 3) / 2; 
    fromSize: CARDINAL ← from.pointer.size; 
    toSize: CARDINAL ← to.pointer.size; 
    at: CARDINAL ← fromSize - nentries; 
    moveSize: CARDINAL; 
    i, offset: CARDINAL; 
    fromcore: LONG POINTER TO Core ← from.pointer; 
    tocore: LONG POINTER TO Core ← to.pointer;
    DBIndexPage.WritePage[from]; 
    DBIndexPage.WritePage[to]; 
    IF nentries = 0 THEN RETURN;
    IF nentries>1000 OR fromSize=0 THEN SIGNAL BadBTree; 
    moveSize← SizeOfEntries[from, at + 1, fromSize - 1] + 2;
    -- Shifts entries in "to"
    ShiftLeft
      [addr: CoreAddr[to, toSize - 1], nwords: SizeOfEntries[to, 0, toSize - 1], 
       by: moveSize + length]; 
    -- store key
    StoreKey[tocore, CoreIndexSize - moveSize - length, key]; 
    -- move entries from "from" to "to"
    I.LongCOPY
      [from: CoreAddr[from, fromSize - 1], to: EndAddr[to] - moveSize, 
       nwords: moveSize]; 
    -- shifts indexes in "to"
    FOR i DECREASING IN [0..toSize) DO 
        tocore.index[i + nentries] ← tocore.index[i] - moveSize - length
        ENDLOOP; 
    -- move indexes from "from" to "to"
    offset ← IF at = 0 THEN 0 ELSE CoreIndexSize - from.pointer.index[at] - 2; 
    FOR i IN [at..fromSize) DO 
        tocore.index[i - at] ← fromcore.index[i] + offset
        ENDLOOP; 
    -- set sizes
    SetSize[to, toSize + nentries]; 
    SetSize[from, at]
    }; 
  
  MoveEntriesToLeftInternal: PUBLIC PROC
       [from, to: Page, key: IndexKey, nentries: CARDINAL] = {
    -- "from" is to the right of "to"
    -- key is the dividing key between from and to
    -- "nentries" are moved (0 => no-op)
    fromSize: CARDINAL ← from.pointer.size; 
    fromShiftSize: CARDINAL ← 
      IF nentries >= fromSize THEN 0 ELSE SizeOfEntries[from, 1, nentries]; 
    toSize: CARDINAL ← to.pointer.size; 
    length: CARDINAL ← (key.length + 3) / 2; 
    moveSize: CARDINAL; 
    i, offset: CARDINAL; 
    fromcore: LONG POINTER TO Core ← from.pointer; 
    tocore: LONG POINTER TO Core ← to.pointer;
    DBIndexPage.WritePage[from]; 
    DBIndexPage.WritePage[to]; 
    IF nentries = 0 THEN RETURN; 
    IF nentries>1000 OR fromSize=0 THEN SIGNAL BadBTree;
    moveSize← SizeOfEntries[from, 0, nentries - 1];
    StoreKey[tocore, tocore.index[toSize - 1] - length, key]; 
    -- move entries in "from" to "to"
    I.LongCOPY
      [from: CoreAddr[from, nentries - 1], 
       to: CoreAddr[to, toSize - 1] - length - moveSize, 
       nwords: moveSize]; 
    -- shifts entries in "from" to the right
    ShiftRight [addr: CoreAddr[from, fromSize - 1], 
       nwords: SizeOfEntries[from, nentries + 1, fromSize - 1] + 2, 
       by: fromShiftSize]; 
    -- move indexes from "from" to "to"
    offset ← SizeOfEntries[to, 0, toSize - 1] + length; 
    FOR i IN [toSize..toSize + nentries) DO 
        tocore.index[i] ← fromcore.index[i - toSize] - offset
        ENDLOOP; 
    -- shift indexes in "from"
    FOR i IN [nentries..fromSize) DO 
        fromcore.index[i - nentries] ← fromcore.index[i] + fromShiftSize
        ENDLOOP; 
    -- set size
    SetSize[to, toSize + nentries]; 
    SetSize[from, fromSize - nentries]
    };

-- From former DBIndexInternalImpl

  RemoveFromInternal: PUBLIC PROC [page: Page, deleting: CARDINAL] RETURNS [State] =
    -- This works only for an internal node
    -- Takes out the deleting-th entry and compresses
    BEGIN
    core: LONG POINTER TO Core ← page.pointer;
    pageSize: CARDINAL ← page.pointer.size;
    size: CARDINAL;
    shiftSize: CARDINAL;
    DBIndexPage.WritePage[page];
    IF deleting#pageSize-1 THEN {
      at: ItemHandle ← CoreAddr[page, pageSize - 1];
      size ← DBIndexOp.EntrySize[page, deleting+1];
      IF deleting=pageSize-2 THEN
        shiftSize ← 2
      ELSE shiftSize ← SizeOfEntries[page, deleting+2, pageSize-1]+2;
      -- Compress data
      LongCOPY[from: at, to: at + size, nwords: shiftSize];
      -- Compress index array
      ShiftIndex[page: page, from: deleting + 1, to: pageSize - 1, offset: size, by: -1]};
    page.pointer.size ← page.pointer.size-1;
    IF FreeSpace[page] >= HalfPage THEN RETURN[merge] ELSE RETURN[normal]
    END;

  SplitEntriesToRightPage: PUBLIC PROC [from, to: Page, at: CARDINAL] RETURNS [IndexKey] =
    -- Both from & to are internal page.
    -- "From" is to the left of "to", and "to" is empty.
    -- Move entries [at..size) in "from" to "to".
    -- Caller must free IndexKey returned.
    BEGIN
    fromSize: CARDINAL ← from.pointer.size;
    moveSize: CARDINAL ← SizeOfEntries[from, at + 1, fromSize - 1] + 2;
    splitKey: IndexKey;
    -- only the value of the entry is moved.
    i, offset: CARDINAL;
    fromcore: LONG POINTER TO Core ← from.pointer;
    tocore: LONG POINTER TO Core ← to.pointer;
    DBIndexPage.WritePage[from];
    DBIndexPage.WritePage[to];
    -- creates splitKey
    splitKey ← CopyKey[Key[from, at]]; -- copy because later split can re-arrange from page!
    -- move entries from "from" to "to"
    I.LongCOPY[
      from: CoreAddr[from, fromSize - 1], to: EndAddr[to] - moveSize,
      nwords: moveSize];
    -- move indexes from "from" to "to"
    offset ← FrontSize[from, at] - 2;
    FOR i IN [at..fromSize) DO
      tocore.index[i - at] ← fromcore.index[i] + offset ENDLOOP;
    -- set size
    SetSize[to, fromSize - at];
    SetSize[from, at];
    -- mark pages dirty
    RETURN[splitKey];
    END;
 

-- From former DBIndexFilePageImpl

  StoreEntryInPage:  PROC [
    core: LONG POINTER TO Core, insertIndex: CARDINAL, key: IndexKey,
    value: LONG CARDINAL] =
    -- stores the value, key to the page.
    BEGIN
    StoreEntry[LOOPHOLE[@core.index[insertIndex],ItemHandle], key, value];
    END;

  StoreEntry:  PROC [at: ItemHandle, key: IndexKey, value: LONG CARDINAL] =
    -- Store the <key, value> at at, and make it the index
    BEGIN
    copyLength: CARDINAL;
    IF key.length>CoreIndexSize THEN ERROR;
    at.value ← value;
    at.length ← key.length;
    I.LongCOPY[
      from: @key.text, to: @at.text,
      nwords: (copyLength ← (key.length + 1)/2)];
    IF key.length MOD 2 = 1 THEN Mask[@at.text + copyLength - 1];
    END;

  StoreKey:  PROC [core: LONG POINTER TO Core, index: CARDINAL, key: IndexKey] =
    -- Stores the key in core.index starting at index
    BEGIN
    IF key.length>CoreIndexSize THEN ERROR;
    core.index[index] ← key.length;
    I.LongCOPY[
      from: @key.text, to: @core.index[index + 1], nwords: (key.length + 1)/2];
    IF key.length MOD 2 = 1 THEN Mask[@core.index[index + (key.length + 1)/2]];
    END;


-- From former DBIndexOpImpl

  
  IncrementSize: PROC [p: Page] = {
    -- Increment the size of entries in p
    core: LONG POINTER TO Core ← p.pointer;
    IF core.size>100 THEN SIGNAL ThisLooksSuspicious;
    core.size ← core.size + 1
    }; 
  
  DecrementSize: PROC [p: Page] = {
    -- Decrement the size of entries in p
    core: LONG POINTER TO Core ← p.pointer;
    IF core.size>100 THEN SIGNAL ThisLooksSuspicious;
    core.size ← core.size - 1
    };

  SetLinks: PUBLIC PROC [left, new: Page] = {
    -- Inserts "new" between "left" and its right sibling
    cache: DBCache.CacheHandle; 
    newcore: LONG POINTER TO Core ← new.pointer; 
    leftcore: LONG POINTER TO Core ← left.pointer; 
    rightcore: LONG POINTER TO Core; 
    right: DBCommon.DBPage;
    right ← newcore.right ← leftcore.right; 
    leftcore.right ← new.db; 
    newcore.left ← left.db; 
    IF right # DBCommon.NullDBPage THEN 
       {[cache, rightcore] ← DBSegment.ReadPage[right, NIL]; 
        IF rightcore.tag.pageTag # DBStoragePagetags.BTree THEN ERROR; 
        rightcore.left ← new.db; 
        DBSegment.WriteLockedPage[cache]; 
        DBSegment.UnlockPage[cache]}
    }; 
  
  InsertTheFirstLeafEntry: PUBLIC PROC
       [page: Page, key: IndexKey, value: LONG CARDINAL] = {
    -- Insert the first entry in an empty page
    insertSize: CARDINAL ← (key.length + 7) / 2; 
    core: LONG POINTER TO Core ← page.pointer;
    DBIndexPage.WritePage[page];
    IF insertSize >= CoreIndexSize THEN ERROR; 
    core.size ← 1; 
    core.index[0] ← CheckLength[CoreIndexSize - insertSize]; 
    StoreEntryInPage[core, CoreIndexSize - insertSize, key, value]
    }; 

  MoveEntriesToRightLeaf: PUBLIC PROC [from, to: Page, nentries: CARDINAL] = {
    -- Both from & to are internal pages.
    -- from is to the left of to.
    -- Move entries [size-nentries..size) in from page to to page.
    fromSize: CARDINAL ← from.pointer.size; 
    toSize: CARDINAL ← to.pointer.size; 
    at: CARDINAL ← fromSize - nentries; 
    moveSize: CARDINAL; 
    i, offset: CARDINAL; 
    fromcore: LONG POINTER TO Core ← from.pointer; 
    tocore: LONG POINTER TO Core ← to.pointer;
    DBIndexPage.WritePage[from]; 
    DBIndexPage.WritePage[to]; 
    DBIndexPage.CheckTag[from.pointer]; 
    DBIndexPage.CheckTag[to.pointer]; 
    IF nentries = 0 THEN RETURN; 
    IF nentries > 40 OR fromSize = 0 THEN SIGNAL BadBTree;
    moveSize← SizeOfEntries[from, at, fromSize - 1]; -- fromSize>0 if nentries>0! 
    -- Shifts entries in "to"
    IF toSize # 0 THEN 
       ShiftLeft[addr: CoreAddr[to, toSize - 1], 
          nwords: SizeOfEntries[to, 0, toSize - 1], by: moveSize]; 
    -- Move entries from "from" to "to"
    I.LongCOPY
      [from: CoreAddr[from, fromSize - 1], to: EndAddr[to] - moveSize, 
       nwords: moveSize]; 
    -- Shifts indexes in "to"
    FOR i DECREASING IN [0..toSize) DO 
        tocore.index[i + nentries] ← tocore.index[i] - moveSize
        ENDLOOP; 
    -- Move indexes from "from" to "to"
    offset ← IF at = 0 THEN 0 ELSE CoreIndexSize - from.pointer.index[at - 1]; 
    FOR i IN [at..fromSize) DO 
        tocore.index[i - at] ← fromcore.index[i] + offset
        ENDLOOP; 
    -- Set sizes
    SetSize[to, toSize + nentries]; 
    SetSize[from, at]; 
    DBIndexOp.MoveScanIndexRight[from: from, to: to, after: fromSize - nentries - 1]; 
    DBIndexPage.CheckTag[from.pointer]; 
    DBIndexPage.CheckTag[to.pointer]
    }; 
  
  MoveEntriesToLeftLeaf: PUBLIC PROC [from, to: Page, nentries: CARDINAL] = {
    -- Both from & to are internal pages.
    -- from is to the right of to.
    -- Move entries [0-nentries) in from page to to page.
    fromSize: CARDINAL ← from.pointer.size; 
    toSize: CARDINAL ← to.pointer.size; 
    moveSize: CARDINAL; 
    i, offset: CARDINAL; 
    fromcore: LONG POINTER TO Core ← from.pointer; 
    tocore: LONG POINTER TO Core ← to.pointer;
    DBIndexPage.WritePage[from]; 
    DBIndexPage.WritePage[to]; 
    DBIndexPage.CheckTag[from.pointer]; 
    DBIndexPage.CheckTag[to.pointer]; 
    IF nentries = 0 THEN RETURN; 
    IF nentries > 40 OR fromSize = 0 THEN SIGNAL BadBTree;
    moveSize← SizeOfEntries[from, 0, nentries - 1]; 
    -- Move entries from "from" to "to"
    IF toSize # 0 THEN 
       I.LongCOPY
         [from: CoreAddr[from, nentries - 1], 
          to: CoreAddr[to, toSize - 1] - moveSize, nwords: moveSize]; 
    -- Shifts entries in "from" to the right
    ShiftRight
      [addr: CoreAddr[from, fromSize - 1], 
       nwords: SizeOfEntries[from, nentries, fromSize - 1], by: moveSize]; 
    -- Move indexes from "from" to "to"
    offset ← SizeOfEntries[to, 0, toSize - 1]; 
    FOR i IN [toSize..toSize + nentries) DO 
        tocore.index[i] ← fromcore.index[i - toSize] - offset
        ENDLOOP; 
    -- Shifts indexes in "from"
    FOR i IN [nentries..fromSize) DO 
        fromcore.index[i - nentries] ← fromcore.index[i] + moveSize
        ENDLOOP; 
    -- Set sizes
    SetSize[to, toSize + nentries]; 
    SetSize[from, fromSize - nentries]; 
    DBIndexOp.MoveScanIndexLeft[from: from, to: to, nentries: nentries]; 
    DBIndexPage.CheckTag[from.pointer]; 
    DBIndexPage.CheckTag[to.pointer]
    }; 

  
  RemoveFromLeaf: PUBLIC PROC [page: Page, deleting: CARDINAL] RETURNS [State] = {
    -- This works only for a leaf.  Takes out the deleting-th entry and compresses.
    core: LONG POINTER TO Core ← page.pointer; 
    pageSizeMinusOne: CARDINAL ← core.size - 1;
    DBIndexPage.WritePage[page]; 
    IF deleting # pageSizeMinusOne THEN 
       {base: LONG POINTER ← @core.index; 
        deletingAt: CARDINAL ← (base + deleting)↑; 
        size: CARDINAL ← 
          (IF deleting = 0 THEN CoreIndexSize ELSE (base + deleting - 1)↑) - 
            deletingAt; 
        offset: CARDINAL ← (base + pageSizeMinusOne)↑; 
        at: LONG POINTER ← base + offset; 
        -- Compress data
        ShiftRight[addr: at, by: size, nwords: deletingAt - offset]; 
        -- Compress index array
        ShiftIndex
          [page: page, from: deleting, to: pageSizeMinusOne, offset: size, 
           by: -1]}; 
    -- Decrement size of the page
    core.size ← pageSizeMinusOne; 
    DBIndexOp.DecrementScanIndex[page: page, after: deleting]; 
    IF FreeSpace[page] >= HalfPage 
       THEN RETURN [merge] ELSE RETURN [normal]
    }; 
  
RemoveLinks: PUBLIC PROC [page: Page] = {
    left, right: DBCommon.DBPage; 
    leftPage, rightPage: Page;
    DBIndexPage.WritePage[page];
    left ← page.pointer.left; 
    right ← page.pointer.right;
    page.pointer.left← page.pointer.right← DBCommon.NullDBPage;  -- to be sure 
    -- remove left links
    IF left # DBCommon.NullDBPage THEN 
       {leftPage ← DBIndexPage.GetPage[page.tree, left, page.depth]; 
        leftPage.pointer.right ← right; 
        DBIndexPage.WriteAndUnlockPage[leftPage]}; 
    -- remove right links
    IF right # DBCommon.NullDBPage THEN 
       {rightPage ← DBIndexPage.GetPage[page.tree, right, page.depth]; 
        rightPage.pointer.left ← left; 
        DBIndexPage.WriteAndUnlockPage[rightPage]}
    }; 
  
  ShiftLeft:  PROC[addr: LONG POINTER, nwords: CARDINAL, by: CARDINAL] = {
    -- Shifts words of size nwords starting at addr to the left
    I.LongCOPY[from: addr, to: addr - by, nwords: nwords]
    }; 
  
  ShiftRight:  PROC[addr: LONG POINTER, nwords: CARDINAL, by: CARDINAL] = {
    -- Shifts words of size nwords starting at addr to the left
    IF by = 0 THEN RETURN;			-- special case, never finishes if by=0
    WHILE NOT (by >= nwords) DO 
      I.LongCOPY[from: addr + nwords - by, to: addr + nwords, nwords: by]; 
      nwords ← nwords - by
      ENDLOOP; 
    I.LongCOPY[from: addr, to: addr + by, nwords: nwords]
    }; 

  ReplaceKey: PUBLIC PROC [p: Page, key: IndexKey, at: CARDINAL] = {
    -- Replaces the key at "at" by "key" on leaf page
    pSize: CARDINAL ← p.pointer.size; 
    start: ItemHandle ← CoreAddr[p, pSize - 1]; 
    oldSize: CARDINAL ← DBIndexOp.EntrySize[p, at] - 3; 
    newSize: CARDINAL ← (key.length + 1) / 2; 
    moveSize: CARDINAL ← 
      SizeOfEntries[page: p, from: at + 1, to: pSize - 1] + 2;
    -- value is moved
    []← CheckLength[at];
    []← CheckLength[moveSize];
    []← CheckLength[oldSize];
    []← CheckLength[key.length];
    DBSegment.WriteLockedPage[p.cache]; 
    IF p.depth = 1 AND at = 0 THEN ERROR OutOfBound; 
    IF oldSize <= newSize 
       THEN 
         I.LongCOPY
           [from: start, to: start - newSize + oldSize, nwords: moveSize] 
       ELSE 
         ShiftRight[addr: start, nwords: moveSize, by: oldSize - newSize]; 
    IF newSize > oldSize 
       THEN 
         DecrementIndexArray
           [page: p, from: at, to: pSize - 1, by: newSize - oldSize] 
       ELSE 
         IncrementIndexArray
           [page: p, from: at, to: pSize - 1, by: oldSize - newSize]; 
    StoreKey[p.pointer, p.pointer.index[at] + 2, key]
    }; 

  
  IncrementIndexArray: PROC [page: Page, from, to, by: CARDINAL] = {
    -- Increments the contents of index array from "from" to "to"
    core: LONG POINTER TO Core ← page.pointer; 
    i: CARDINAL;
    []← CheckLength[by]; []← CheckLength[to]; []← CheckLength[from];
    FOR i IN [from..to] DO 
        core.index[i] ← core.index[i] + by
        ENDLOOP
    }; 
  
  DecrementIndexArray: PROC [page: Page, from, to, by: CARDINAL] = {
    -- Decrements the contents of index array from "from" to "to"
    core: LONG POINTER TO Core ← page.pointer; 
    i: CARDINAL;
    []← CheckLength[by]; []← CheckLength[to]; []← CheckLength[from];
    FOR i IN [from..to] DO 
        core.index[i] ← core.index[i] - by
        ENDLOOP
    }; 
  
  SetIndex: PROC
       [page: Page, index: CARDINAL, address: LONG POINTER] = {
    offset: CARDINAL ← I.LowHalf[address - page.pointer - OverHead];
    page.pointer.index[index] ← offset
    }; 
  
  SlideLeafEntries: PROC[in: Page, from: CARDINAL, to: CARDINAL, by: CARDINAL]
    RETURNS [LONG POINTER] = {
    -- Slide entries in[from..to] to left, by "by" words, and make a 
    --room for one entry.  Returns the address of empty slot
    start: ItemHandle ← CoreAddr[in, to]; 
    dest: LONG POINTER ← start - by; 
    size: CARDINAL;
    IF from > to + 1 THEN ERROR; 
    IF from > to THEN RETURN [dest]; 
    size ← SizeOfEntries[page: in, from: from, to: to]; 
    I.LongCOPY[from: start, to: dest, nwords: size]; 
    ShiftIndex[page: in, from: from, to: to, offset: by, by: 1]; 
    RETURN [dest + size]
    }; 
  
  ShiftIndex: PROC[page: Page, from, to: CARDINAL, offset: CARDINAL, by: INTEGER] = {
    -- Shifts right index array index[from..to] by size "by" and adds or subtracts offset
    core: LONG POINTER ← @page.pointer.index; 
    dest: LONG POINTER ← core + by; 
    i: CARDINAL ← from + by;
    IF by > 0 
       THEN 
         FOR i DECREASING IN [from..to] DO 
             (dest + i)↑ ← (core + i)↑ - offset
             ENDLOOP 
       ELSE 
         FOR i IN [from..to] DO 
             (dest + i)↑ ← (core + i)↑ + offset
             ENDLOOP
    }; 

  MoveRightAndInsert: PUBLIC PROC[
    from: Page, to: Page, after: CARDINAL, at: CARDINAL,
    key: IndexKey, value: LONG CARDINAL]
    RETURNS [CARDINAL] = {
    -- Assert after<at
    -- We are trying to insert <key, value> between from[at] and 
    --from[at+1].  Since from will overflow, we move 
    --from[after+1..fromEnd] to the page to, and insert <key,value>
    -- Returns the index where insertion occurred
    i, j: CARDINAL; 
    start: ItemHandle ← CoreAddr[from, at]; 
    newSize, size: CARDINAL ← 
      SizeOfEntries[page: from, from: after + 1, to: at]; 
    toCore: LONG POINTER TO Core ← to.pointer; 
    fromCore: LONG POINTER TO Core ← from.pointer; 
    fromEnd: CARDINAL ← from.pointer.size - 1; 
    insertSize: CARDINAL ← (key.length + 1) / 2 + 3; 
    offset: CARDINAL ← CoreIndexSize - from.pointer.index[after]; 
    temp: CARDINAL;
    
    DBIndexPage.WritePage[from];
    DBIndexPage.WritePage[to];
    IF size + insertSize + (fromEnd + 1 - after) + OverHead > FullPage THEN 
       ERROR PageOverflow; 
    -- first move from[after+1..at]
    temp ← CoreIndexSize - size; 
    I.LongCOPY[from: start, to: @toCore.index[temp], nwords: size]; 
    j ← 0; 
    FOR i IN [after + 1..at] DO 
        toCore.index[j] ← fromCore.index[i] + offset; 
        j ← j + 1
        ENDLOOP; 
    toCore.index[j] ← 
      (IF j = 0 THEN CoreIndexSize ELSE toCore.index[j - 1]) - insertSize; 
    -- then insert <key,value>
    StoreEntry[at: CoreAddr[to, j], key: key, value: value]; 
    j ← j + 1; 
    -- then move from[at+1..fromEnd]
    start ← CoreAddr[from, fromEnd]; 
    newSize ← SizeOfEntries[page: from, from: at + 1, to: fromEnd]; 
    temp ← temp - insertSize - newSize; 
    I.LongCOPY[from: start, to: @toCore.index[temp], nwords: newSize]; 
    FOR i IN [at + 1..fromEnd] DO 
        toCore.index[j] ← fromCore.index[i] + offset - insertSize; 
        j ← j + 1
        ENDLOOP; 
    -- fix size
    SetSize[from, after + 1]; 
    SetSize[to, fromEnd - after + 1]; 
    RETURN [at - after - 1]
    }; 
  
  MoveEntriesToRightLeafAfter: PUBLIC PROC [from, to: Page, nentries: CARDINAL] = {
    -- Just like MoveEntriesToRightLeaf, except entries moved from "from"
    -- are placed after entries of "to"
    fromSize: CARDINAL ← from.pointer.size; 
    toSize: CARDINAL ← to.pointer.size; 
    oldToSize: CARDINAL ← SizeOfEntries[to, 0, toSize - 1]; 
    at: CARDINAL ← fromSize - nentries; 
    moveSize: CARDINAL ← SizeOfEntries[from, at, fromSize - 1]; 
    i, offset: CARDINAL; 
    fromcore: LONG POINTER TO Core ← from.pointer; 
    tocore: LONG POINTER TO Core ← to.pointer;
    IF oldToSize + moveSize + OverHead + (toSize + fromSize - at) > FullPage THEN 
       ERROR PageOverflow; 
    DBIndexPage.WritePage[from];
    DBIndexPage.WritePage[to];
    DBIndexPage.CheckTag[from.pointer]; 
    DBIndexPage.CheckTag[to.pointer]; 
    IF nentries = 0 THEN RETURN; 
    IF nentries > 40 THEN ERROR; 
    -- Move entries from "from" to "to"
    I.LongCOPY
      [from: CoreAddr[from, fromSize - 1], 
       to: CoreAddr[to, toSize - 1] - moveSize, nwords: moveSize]; 
    -- Move indexes from "from" to "to"
    offset ← 
      IF at = 0 
         THEN 0 ELSE CoreIndexSize - from.pointer.index[at - 1] - oldToSize; 
    FOR i IN [at..fromSize) DO 
        tocore.index[i - at + 1] ← fromcore.index[i] + offset
        ENDLOOP; 
    -- Set sizes
    SetSize[to, toSize + nentries]; 
    SetSize[from, at]; 
    DBIndexOp.MoveScanIndexRight[from: from, to: to, after: fromSize - nentries - 1]; 
    DBIndexPage.CheckTag[from.pointer]; 
    DBIndexPage.CheckTag[to.pointer]
    };
  
  SlideLeafAt: PUBLIC PROC
       [p: Page, index: CARDINAL, key: IndexKey, value: LONG CARDINAL] = {
    -- Shifts part of entries in p including and after the index and inserts <key, value>
    -- It is guaranted that there won't be any overflow.
    insertSize: CARDINAL ← (key.length + 7) / 2; 
    at: LONG POINTER ← 
      SlideLeafEntries[in: p, from: index, to: p.pointer.size - 1, by: insertSize];
    DBIndexPage.WritePage[p];
    StoreEntry[at: at, key: key, value: value]; 
    SetIndex[page: p, index: index, address: at]; 
    IncrementSize[p]; 
    DBIndexOp.IncrementScanIndex[p, index - 1]
    }; 

  CheckLength: PROC[c: CARDINAL] RETURNS[CARDINAL] =
    -- Use to check that cardinals are reasonable in key lengths and indexes into core.
    {IF c>250 THEN SIGNAL ThisLooksSuspicious; RETURN[c]}; 
  
END.

Change Log

By Cattell September 22, 1982 3:05 pm: Created module.

By Cattell May 27, 1983 2:11 pm:  Added more comments.