-- BTree2.mesa	Last edit: Andrew Birrell	15-Jan-82 11:37:15

DIRECTORY
  BTree2Defs: FROM "BTree2Defs" USING [Entry, EntryR, Index, VArray];

-- A Varray consists of:
-- 1) the number of items (n) stored in the array.
-- 2) a mumble, described below. 
-- 3) n packed descriptors for the items, each consisting of a pointer to the starting place and a length for the key.
-- 4) some empty space perhaps
-- 5) the items themselves, stored backward from the end of array

-- The length of the value part of the item can be deduced from the start of the preceeding item. The mumble is a start for a phony item so it all works without special end tests.

-- The Copy routines make the code smaller by 10%
-- The use of Entry makes the code smaller by 10%

-- A Copy is A[i] ¬B[i] + x for all i

-- A Slip moves entries startIndex and beyond from this array to newIndex and newData in array other, copying both index and data.

-- A Move appends entries startIndex and beyond from this array to the other array. move updates the entry count, slip doesn't.


BTree2: PROGRAM EXPORTS BTree2Defs = PUBLIC
  BEGIN

  NN: TYPE = CARDINAL;
  Desc: TYPE = DESCRIPTOR FOR ARRAY OF WORD;
  RealJob: TYPE = {insert, replace, delete};
  w, FixedOverhead: CARDINAL = 2;
  OverheadPerItem: CARDINAL = 1;
  nullER: BTree2Defs.EntryR ¬ [DESCRIPTOR[NIL, 0], DESCRIPTOR[NIL, 0]];

  debug: BOOLEAN ¬ TRUE;

  maxKeyLength: CARDINAL = 63;

  Form: TYPE = MACHINE DEPENDENT RECORD [k: [0..1024), v: [0..maxKeyLength]];
  Foo: TYPE = POINTER TO ARRAY [0..3) OF Form;

  IndexOutOfBounds: SIGNAL = CODE;
  GetAnother: SIGNAL RETURNS [BTree2Defs.VArray] = CODE;
  Merger: SIGNAL RETURNS [BTree2Defs.VArray, BOOLEAN] = CODE;
  DeletePage: SIGNAL = CODE;

  Initialize: PROCEDURE [v: BTree2Defs.VArray] =
    BEGIN
    i: CARDINAL;
    FOR i IN [0..LENGTH[v­]) DO v[i] ¬ 0; ENDLOOP;
    v[1] ¬ LOOPHOLE[Form[LENGTH[v­], 0]];
    END;

  Items: PROCEDURE [v: BTree2Defs.VArray] RETURNS [NN] = BEGIN RETURN[v[0]]; END;

  Lookup: PROCEDURE [this: BTree2Defs.VArray, item: BTree2Defs.Index]
    RETURNS [BTree2Defs.EntryR] =
    BEGIN
    foo: Foo;
    startK, endK, startV, lengthK: NN;
    [foo, , , startK, endK] ¬ Unpack[this, item];
    IF item >= this[0] THEN SIGNAL IndexOutOfBounds;
    startV ¬ startK + (lengthK ¬ foo[item].v);
    RETURN[
      [
        DESCRIPTOR[@this[startK], lengthK], DESCRIPTOR[
        @this[startV], endK - startV]]];
    END;

  Insert: PROCEDURE [
    this: BTree2Defs.VArray, item: BTree2Defs.Index, e: BTree2Defs.Entry] =
    BEGIN
    IF ((LENGTH[e.k] > maxKeyLength) OR (LENGTH[e.k] + LENGTH[e.v] > 80)) THEN
      ERROR;
    ReplaceX[this, item, e, insert];
    END;

  Delete: PROCEDURE [this: BTree2Defs.VArray, item: BTree2Defs.Index] =
    BEGIN ReplaceX[this, item, @nullER, delete]; END;

  Replace: PROCEDURE [
    this: BTree2Defs.VArray, item: BTree2Defs.Index, e: BTree2Defs.Entry] =
    BEGIN ReplaceX[this, item, e, replace]; END;

  ReplaceX: PROCEDURE [
    this: BTree2Defs.VArray, item: BTree2Defs.Index, e: BTree2Defs.Entry,
    r: RealJob] =
    BEGIN
    diddle: INTEGER = SELECT r FROM replace => 0, insert => 1, ENDCASE => -1;
    foo: Foo;
    other: BTree2Defs.VArray;
    shrinkage: INTEGER;
    nextIndex, startLast, startItem, page, halfPage, sizeKey, sizeVal: NN;
    sizeNew, sizeOld, start, used, endItem, i: NN;
    [foo, nextIndex, startLast, startItem, endItem] ¬ Unpack[this, item];
    page ¬ (foo - 1)[0].k;
    halfPage ¬ page / 2;
    sizeNew ¬ (sizeKey ¬ LENGTH[e.k]) + (sizeVal ¬ LENGTH[e.v]);
    sizeOld ¬ IF r = insert THEN 0 ELSE endItem - startItem;
    shrinkage ¬ sizeOld - sizeNew;
    start ¬ startItem + shrinkage;
    used ¬ (page - startLast) - shrinkage + (nextIndex - 1) + OverheadPerItem + w;
    IF debug THEN Check[this];
    IF nextIndex < item + 1 THEN ERROR IndexOutOfBounds;
    IF used + 4 > page THEN
      BEGIN
      withoutItem: NN ¬ halfPage + w;
      withItem: NN ¬ halfPage + w - shrinkage + diddle;
      other ¬ SIGNAL GetAnother;
      FOR i IN [0..nextIndex) DO  -- test is split result to be at >= halfPage.
        IF foo[i].k <
          ((IF i >= item THEN withItem ELSE withoutItem) +
             (i + 1) * OverheadPerItem) THEN
          BEGIN  -- and it better be <= Page.
          IF foo[i].k <=
            ((IF i >= item THEN withItem - halfPage ELSE w) +
               (i + 1) * OverheadPerItem) THEN
            BEGIN IF i = 0 THEN ERROR; i ¬ i - 1; END;
          Move[this, i + 1, other];
          IF i >= item THEN
            ReplaceX[this, item, e, r ! Merger, GetAnother => ERROR]
          ELSE ReplaceX[other, item - i - 1, e, r ! Merger, GetAnother => ERROR];
          RETURN;
          END;
        ENDLOOP;
      ERROR;  -- oops
      END;
    IF shrinkage # 0 THEN
      Slip[this, this, item + 1, item + 1 + diddle, startLast + shrinkage];
    IF r # delete THEN
      BEGIN
      foo[item + diddle] ¬ [start, sizeKey];
      Copy[@e.k[0], @this[start], sizeKey, 0];
      Copy[@e.v[0], @this[start + sizeKey], sizeVal, 0];
      END;
    this[0] ¬ nextIndex + diddle;
    IF ((used < halfPage) AND (shrinkage > 0)) THEN Balance[this, used];
    IF debug THEN Check[this];
    END;


  Balance: PROCEDURE [this: BTree2Defs.VArray, used: NN] =
    BEGIN
    oFoo: Foo;
    other: BTree2Defs.VArray;
    onRight: BOOLEAN;
    page, halfPage, nextIndex, thisEnd: NN;
    l, here, nextOther, otherEnd, i, carry: NN;
    page ¬ LOOPHOLE[this[1], Form].k;
    halfPage ¬ page / 2;
    [other, onRight] ¬ SIGNAL Merger;
    IF other = NIL THEN RETURN;
    [, nextIndex, thisEnd, , ] ¬ Unpack[this, 0];
    [oFoo, nextOther, otherEnd, , ] ¬ Unpack[other, 0];
    IF used + nextOther < otherEnd THEN
      BEGIN
      IF onRight THEN Move[other, 0, this] ELSE Move[this, 0, other];
      SIGNAL DeletePage;
      RETURN;
      END;
    carry ¬ halfPage + w + (IF onRight THEN used ELSE 0);
    -- magic to leave the page on the left just over half full
    i ¬ 0;
    UNTIL carry + i > (here ¬ oFoo[i - 1].k) DO
      IF i >= nextOther THEN EXIT; i ¬ i + 1; ENDLOOP;
    IF carry + i <= here THEN ERROR;
    IF onRight THEN
      BEGIN
      other[0] ¬ i;
      Move[other, 0, this];
      other[0] ¬ nextOther;
      Slip[other, other, i, 0, otherEnd + page - here];
      other[0] ¬ nextOther - i;
      END
    ELSE
      BEGIN
      l ¬ nextOther - i;
      Slip[this, this, 0, l, otherEnd + thisEnd - here];
      this[0] ¬ 0;
      Move[other, i, this];
      this[0] ¬ l + nextIndex;
      END;
    END;

  --I think this returns the array of pntrs to items, the count of items, and the offsets: of start of first item on the page, of end of requested item, of start of requested item.
  Unpack: PROCEDURE [v: BTree2Defs.VArray, item: BTree2Defs.Index]
    RETURNS [Foo, BTree2Defs.Index, NN, NN, NN] =
    BEGIN
    next: NN = v[0];
    foo: Foo = LOOPHOLE[@v[w]];
    RETURN[foo, next, foo[next - 1].k, foo[item].k, foo[item - 1].k];
    END;

  Move: PROCEDURE [
    from: BTree2Defs.VArray, at: BTree2Defs.Index, to: BTree2Defs.VArray] =
    BEGIN
    toNext, fromNext, fromEnd, atEnd, toEnd: NN;
    [, fromNext, fromEnd, , atEnd] ¬ Unpack[from, at];
    [, toNext, toEnd, , ] ¬ Unpack[to, 0];
    Slip[from, to, at, toNext, toEnd - atEnd + fromEnd];
    to[0] ¬ toNext + fromNext - at;
    from[0] ¬ at;
    END;

  Slip: PROCEDURE [
    this, other: BTree2Defs.VArray,
    startIndex, newIndex, newData: BTree2Defs.Index] =
    BEGIN
    foo, toFoo: Foo;
    endIndex, endData, startData, q: NN;
    [foo, endIndex, endData, , startData] ¬ Unpack[this, startIndex];
    toFoo ¬ LOOPHOLE[@other[w]];
    q ¬ LOOPHOLE[Form[newData - endData, 0]];
    Copy[@foo[startIndex], @toFoo[newIndex], endIndex - startIndex, q];
    Copy[@this[endData], @other[newData], startData - endData, 0];
    END;

  Copy: PROCEDURE [from, to: POINTER, len, a: NN] =
    BEGIN
    i: NN;
    IF len > 256 THEN ERROR;
    IF LOOPHOLE[to, CARDINAL] > LOOPHOLE[from, CARDINAL] THEN
      FOR i DECREASING IN [0..len) DO (to + i)­ ¬ (from + i)­ + a; ENDLOOP
    ELSE FOR i IN [0..len) DO (to + i)­ ¬ (from + i)­ + a; ENDLOOP;
    END;

  Check: PROCEDURE [v: BTree2Defs.VArray] =
    BEGIN
    foo: Foo = LOOPHOLE[@v[w]];
    i: NN;
    IF v[0] >= LENGTH[v­] THEN ERROR;
    IF (foo - 1)[0].k # LENGTH[v­] THEN ERROR;
    FOR i IN [0..v[0]) DO
      IF ((foo[i].k >= foo[i - 1].k) OR (foo[i].v > foo[i - 1].k - foo[i].k)) THEN
        ERROR;
      ENDLOOP;
    END;

  END.

Edit Log

RTE: March 28, 1980  2:47 PM: KK: changed format of program so I could read it.
RTE: April 28, 1980  12:18 PM: KK: bug in replacex, could cause page to overflow after split.
RTE: September 9, 1980  3:44 PM: KK: Nori found loop index in Balance that was depended upon but could be undefined.
RTE: 15-Jan-82 11:36:59: Andrew Birrell: allowed keys up to 63 words long.