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