-- VMMgr>STreeImpl.mesa (last edited by Knutsen on July 30, 1980 4:05 PM)

-- Things to consider:

-- 1) Use LongMove for root insert/delete

-- 2) Collapse merge/balance logic

-- 3) For multi-mds, remove variables from global frame

-- 4) Move cDesc from leaves to root; improve merge/balance logic

-- 5) Some calls to LongMove could be LongCOPY

DIRECTORY

CachedSpace USING [handleVM, Level],

Environment USING [Base, first64K],

Inline USING [LongCOPY, LowHalf],

ResidentHeap USING [FreeNode, MakeNode],

Space USING [defaultWindow],

STLeaf,

STree,

Transaction USING [nullHandle],

Utilities USING [LongMove],

VM USING [PageCount],

Zone USING [Status];

STreeImpl: PROGRAM [countVM: VM.PageCount, kind: STLeaf.Kind] -- logically, this program should be a monitor, but each instance of it has only one client (HierarchyImpl or ProjectionImpl) and is protected by their monitor locks.

IMPORTS Inline, ResidentHeap, STLeaf, Transaction, Utilities

EXPORTS STree =

BEGIN OPEN STLeaf, STree;

sizeDesc: CARDINAL; -- SIZE[kind Desc]

cDesc: INTEGER; -- total number of descriptors in the STree (for measurements only)

--
-- Keys

keyTop: Key; -- upper bound for kind Key

KeyFromPDesc: PROCEDURE [pDesc: PDesc] RETURNS [Key] =

BEGIN

WITH pDesc SELECT kind FROM

hierarchy => RETURN[[hierarchy[[level: descH.level, page: descH.interval.page]]]];

ENDCASE -- projection -- => RETURN[[projection[pDesc.page]]]

END;

--
-- The root

-- If cKey=0, then mpIILeafKey has no entries; rgILeaf[0] specifies the only leaf page.
-- If cKey>0, then the values mpIILeafKey[i], for i IN [1..cKey], are ascending:
-- leaf rgILeaf[0] contains descriptors matching keys<mpIILeafKey[1];
-- leaf rgILeaf[i] contains descriptors matching keys IN [mpIILeafKey[i]..mpIILeafKey[i+1]), i IN [1..cKey);
-- leaf rgILeaf[cKey] contains descriptors matching keys>=mpIILeafKey[cKey].

-- The two arrays making up the root are stored in a single ResidentHeap (really only needs to be "ResidentDescriptorHeap") node, with mpIILeafKey preceding rgILeaf.

IILeaf: TYPE = CARDINAL; -- Index of ILeaf entry in root

MpIILeafKey: TYPE = LONG POINTER TO ARRAY IILeaf(0..0] OF Key; -- maxlength is cKeyMax

RgILeaf: TYPE = LONG POINTER TO ARRAY IILeaf[0..0] OF ILeaf; -- maxlength is cKeyMax+1

cKeyMax: CARDINAL;

cKey: CARDINAL;

mpIILeafKey: MpIILeafKey;

rgILeaf: RgILeaf;

rootGrowthTenths: CARDINAL ← 5; -- see ExpandRoot

Bug: PRIVATE --PROGRAMMING-- ERROR [type: BugType] = CODE;

BugType: TYPE = {bug0, bug1};

AllocateRoot: PROCEDURE [cKeyMax: CARDINAL] RETURNS [mpIILeafKey: MpIILeafKey, rgILeaf: RgILeaf] =

BEGIN
sizeMpIILeafKey: CARDINAL = cKeyMax*SIZE[Key];
node: Environment.Base RELATIVE POINTER;
s: Zone.Status;
[node, s] ← ResidentHeap.MakeNode[sizeMpIILeafKey+(cKeyMax+1)*SIZE[ILeaf]];
IF s~=okay THEN ERROR Bug[bug0];
mpIILeafKey ← @Environment.first64K[node];
rgILeaf ← @Environment.first64K[node+sizeMpIILeafKey];
END;

ExpandRoot: PROCEDURE =

BEGIN
s: Zone.Status;
cKeyMaxNew: CARDINAL = cKeyMax+(cKeyMax*rootGrowthTenths+9--round up--)/10;
mpIILeafKeyNew: MpIILeafKey;
rgILeafNew: RgILeaf;
[mpIILeafKeyNew, rgILeafNew] ← AllocateRoot[cKeyMaxNew];
Inline.LongCOPY[from: mpIILeafKey, nwords: cKeyMax*SIZE[Key], to: mpIILeafKeyNew];
Inline.LongCOPY[from: rgILeaf, nwords: (cKeyMax+1)*SIZE[ILeaf], to: rgILeafNew];
s ← ResidentHeap.FreeNode[Inline.LowHalf[mpIILeafKey]];
IF s~=okay THEN ERROR;
mpIILeafKey ← mpIILeafKeyNew; rgILeaf ← rgILeafNew; cKeyMax ← cKeyMaxNew
END;

SearchRoot: PROCEDURE [key: Key] RETURNS [iILeaf: IILeaf] =

BEGIN

FOR iILeaf ← 0, iILeaf+1 DO

IF iILeaf=cKey OR (WITH mpIILeafKey[iILeaf+1] SELECT kind FROM

hierarchy => key.handleH.level<handleH.level OR
key.handleH.level=handleH.level AND key.handleH.page<handleH.page,

ENDCASE -- projection -- => key.pageP<pageP) THEN EXIT

ENDLOOP

END;

UpdateRoot: PROCEDURE [iILeaf: IILeaf, pLeaf: PLeaf] =

BEGIN

IF iILeaf~=0 AND pLeaf.cDesc~=0 THEN mpIILeafKey[iILeaf] ← KeyFromPDesc[@pLeaf.descFirst]

END;

--
-- Leaves

cDescMax: CDesc; -- maximum number of descriptors per leaf

cDescMin: CDesc; -- threshold for balancing

SearchLeaf: PROCEDURE [key: Key, pLeaf: PLeaf] RETURNS [found: BOOLEAN, pDesc: PDesc, last: BOOLEAN] =

-- Returns last=TRUE if the descriptor coming after given key is not on this leaf

BEGIN

iDesc: CARDINAL;

pDescNext: PDesc;

--assert--IF pLeaf.cDesc=0 THEN ERROR;

found ← TRUE; last ← FALSE;

pDesc ← @pLeaf.descFirst;

FOR iDesc IN [0..pLeaf.cDesc-(IF kind=projection THEN 1 ELSE 0)) DO

pDescNext ← pDesc+sizeDesc;

WITH pDesc SELECT kind FROM

hierarchy =>

BEGIN OPEN descH;

IF key.handleH.level=level AND key.handleH.page<interval.page+interval.count OR key.handleH.level<level THEN

BEGIN

IF key.handleH.level~=level OR key.handleH.page<interval.page THEN found ← FALSE

ELSE IF iDesc+1=pLeaf.cDesc THEN last ← TRUE;

EXIT

END

END;

projection => IF key.pageP<pDescNext.page THEN EXIT;

ENDCASE;

pDesc ← pDescNext

REPEAT FINISHED => BEGIN last ← TRUE; IF kind=hierarchy THEN found ← FALSE END

ENDLOOP

END;

--
-- STree’s

Delete: PUBLIC PROCEDURE [key: Key] =

BEGIN

iILeaf: IILeaf = SearchRoot[key];

pLeaf: PLeaf = STLeaf.Open[rgILeaf[iILeaf]];

matching: BOOLEAN;

pDesc: PDesc;

[matching, pDesc] ← SearchLeaf[key, pLeaf];

--assert--IF ~matching THEN ERROR;

-- Move descriptors following pDesc up one place

pLeaf.cDesc ← pLeaf.cDesc-1;

Utilities.LongMove[

pSource: pDesc+sizeDesc,

size: Inline.LowHalf[@pLeaf.descFirst+sizeDesc*pLeaf.cDesc-pDesc],

pSink: pDesc];

-- Update root entry in case deleted descriptor was first on leaf

UpdateRoot[iILeaf, pLeaf];

-- If number of descriptors remaining on leaf is small enough, perform merge or balance

IF pLeaf.cDesc=0 AND iILeaf=cKey THEN

BEGIN

-- Delete last leaf

STLeaf.Close[rgILeaf[iILeaf]];

STLeaf.Delete[rgILeaf[iILeaf]];

cKey ← cKey-1;

RETURN

END;

IF pLeaf.cDesc<cDescMin AND iILeaf<cKey THEN

BEGIN

iILeafNext: IILeaf = iILeaf+1;

pLeafNext: PLeaf = STLeaf.Open[rgILeaf[iILeafNext]];

IF pLeaf.cDesc+pLeafNext.cDesc<=cDescMax THEN

-- Merge higher neighbor into this leaf

BEGIN

iILeafAfter: IILeaf;

-- Append contents of merged leaf

Utilities.LongMove[

pSource: @pLeafNext.descFirst,

size: sizeDesc*pLeafNext.cDesc,

pSink: @pLeaf.descFirst+sizeDesc*pLeaf.cDesc];

pLeaf.cDesc ← pLeaf.cDesc+pLeafNext.cDesc;

-- Delete merged leaf

STLeaf.Close[rgILeaf[iILeafNext]];

STLeaf.Delete[rgILeaf[iILeafNext]];

-- Delete its root entry

cKey ← cKey-1;

FOR iILeafAfter IN [iILeafNext..cKey] DO

mpIILeafKey[iILeafAfter] ← mpIILeafKey[iILeafAfter+1];

rgILeaf[iILeafAfter] ← rgILeaf[iILeafAfter+1]

ENDLOOP

END

ELSE

-- Balance with next leaf

BEGIN

cDescDelta: CDesc = (pLeafNext.cDesc-pLeaf.cDesc)/2; -- >0, or we would have merged

-- Append first cDescDelta descriptors from next leaf to this one

Utilities.LongMove[

pSource: @pLeafNext.descFirst,

size: sizeDesc*cDescDelta,

pSink: @pLeaf.descFirst+sizeDesc*pLeaf.cDesc];

pLeaf.cDesc ← pLeaf.cDesc+cDescDelta;

-- Delete first cDescDelta descriptors of next leaf

pLeafNext.cDesc ← pLeafNext.cDesc-cDescDelta;

Utilities.LongMove[

pSource: @pLeafNext.descFirst+sizeDesc*cDescDelta,

size: sizeDesc*pLeafNext.cDesc,

pSink: @pLeafNext.descFirst];

-- Update root entry since identity of first descriptor changed

UpdateRoot[iILeafNext, pLeafNext];

STLeaf.Close[rgILeaf[iILeafNext]]

END

END;

STLeaf.Close[rgILeaf[iILeaf]];

cDesc ← cDesc-1

END;

Get: PUBLIC PROCEDURE [pDescResult: PDesc, key: Key] RETURNS [keyNext: Key] =

BEGIN

iILeaf: IILeaf = SearchRoot[key];

pLeaf: PLeaf = STLeaf.Open[rgILeaf[iILeaf]];

found, last: BOOLEAN;

pDesc: PDesc;

[found, pDesc, last] ← SearchLeaf[key, pLeaf];

IF ~found THEN WITH pDescResult SELECT kind FROM

hierarchy => descH.state ← missing;

projection => ERROR;

ENDCASE

ELSE Utilities.LongMove[pSource: pDesc, size: sizeDesc, pSink: pDescResult];

SELECT TRUE FROM

~last => keyNext ← KeyFromPDesc[pDesc+(IF found THEN sizeDesc ELSE 0)];

-- last AND -- iILeaf<cKey => keyNext ← mpIILeafKey[iILeaf+1];

-- last AND iILeaf=cKey -- ENDCASE => keyNext ← keyTop;

STLeaf.Close[rgILeaf[iILeaf]]

END;

Insert: PUBLIC PROCEDURE [pDesc: PDesc] =

BEGIN

key: Key = KeyFromPDesc[pDesc];

iILeaf: IILeaf;

pLeaf: PLeaf;

inserted: BOOLEAN;

DO

iILeaf ← SearchRoot[key];

pLeaf ← STLeaf.Open[rgILeaf[iILeaf]];

IF pLeaf.cDesc=cDescMax THEN

-- Leaf is full; split it and try again

BEGIN

iILeafNew: IILeaf = iILeaf+1;

iILeafAfter: IILeaf;

-- Create new leaf to follow current one

iLeafNew: ILeaf = STLeaf.Create[];

pLeafNew: PLeaf = STLeaf.Open[iLeafNew];

cDescNew: CDesc = pLeaf.cDesc/2;

-- Move last cDescNew descriptors of this leaf to new one

pLeaf.cDesc ← pLeaf.cDesc-cDescNew;

pLeafNew.cDesc ← cDescNew;

Utilities.LongMove[

pSource: @pLeaf.descFirst+sizeDesc*pLeaf.cDesc,

size: sizeDesc*cDescNew,

pSink: @pLeafNew.descFirst];

-- Insert new root entry

IF cKey=cKeyMax THEN ExpandRoot[];

FOR iILeafAfter DECREASING IN [iILeafNew..cKey] DO

mpIILeafKey[iILeafAfter+1] ← mpIILeafKey[iILeafAfter];

rgILeaf[iILeafAfter+1] ← rgILeaf[iILeafAfter]

ENDLOOP;

cKey ← cKey+1;

rgILeaf[iILeafNew] ← iLeafNew;

UpdateRoot[iILeafNew, pLeafNew];

STLeaf.Close[iLeafNew];

-- Restart

inserted ← FALSE

END

ELSE

-- Leaf is not full; perform insert and exit

BEGIN

matching: BOOLEAN;

pDescTarget: PDesc;

[matching, pDescTarget] ← SearchLeaf[key, pLeaf];

SELECT kind FROM

hierarchy => IF matching THEN ERROR;

projection => pDescTarget ← pDescTarget+sizeDesc; -- insert after current matching entry

ENDCASE;

-- Move all descriptors not before pDescTarget down one place

Utilities.LongMove[

pSource: pDescTarget,

size: Inline.LowHalf[@pLeaf.descFirst+sizeDesc*pLeaf.cDesc-pDescTarget],

pSink: pDescTarget+sizeDesc];

-- Insert descriptor

Utilities.LongMove[pSource: pDesc, size: sizeDesc, pSink: pDescTarget];

pLeaf.cDesc ← pLeaf.cDesc+1;

-- Update root entry in case inserted descriptor is first on leaf

UpdateRoot[iILeaf, pLeaf];

-- Indicate finished

inserted ← TRUE

END;

STLeaf.Close[rgILeaf[iILeaf]];

IF inserted THEN EXIT

ENDLOOP;

cDesc ← cDesc+1

END;

Update: PUBLIC PROCEDURE [pDesc: PDesc] =

BEGIN

key: Key = KeyFromPDesc[pDesc];

iILeaf: IILeaf = SearchRoot[key];

pLeaf: PLeaf = STLeaf.Open[rgILeaf[iILeaf]];

matching: BOOLEAN;

pDescTarget: PDesc;

[matching, pDescTarget] ← SearchLeaf[key, pLeaf];

--assert--IF ~matching THEN ERROR;

-- Update descriptor

Utilities.LongMove[pSource: pDesc, size: sizeDesc, pSink: pDescTarget];

-- Update root entry in case updated descriptor is first on leaf

UpdateRoot[iILeaf, pLeaf];

STLeaf.Close[rgILeaf[iILeaf]];

END;

Initialize: PROCEDURE =

BEGIN

iLeaf: ILeaf = STLeaf.Create[];

pLeaf: PLeaf = STLeaf.Open[iLeaf];

cDesc ← 1;

pLeaf.cDesc ← 1;

SELECT kind FROM

hierarchy =>

BEGIN

sizeDesc ← SIZE[hierarchy Desc];

keyTop ← [hierarchy[[level: LAST[CachedSpace.Level], page: CachedSpace.handleVM.page+countVM]]];

cKeyMax ← 25;

pLeaf.descFirst ← [ hierarchy[ [

level: CachedSpace.handleVM.level,

interval: [CachedSpace.handleVM.page, countVM],

dPinned: FALSE, -- don’t care

dDirty: FALSE, -- don’t care

pinned: FALSE,

state: unmapped,

writeProtected: , -- don’t care

hasSwapUnits: FALSE,

sizeSwapUnit: 1, -- don’t care

dataOrFile: , -- don’t care

pageRover: CachedSpace.handleVM.page,

vp: long[

window: Space.defaultWindow, -- don’t care

countMapped: 0, -- don’t care

transaction: Transaction.nullHandle ] ] ] ]; -- not part of a transaction yet.

END;

projection =>

BEGIN

sizeDesc ← SIZE[projection Desc];

keyTop ← [projection[CachedSpace.handleVM.page+countVM]];

cKeyMax ← 2;

pLeaf.descFirst ← [ projection[

page: CachedSpace.handleVM.page,

level: CachedSpace.handleVM.level,

levelMapped: FIRST[CachedSpace.Level], -- don’t care

hasSwapUnits: FALSE,

state: unmapped,

writeProtected: FALSE, -- don’t care

needsLogging: FALSE ]] -- don’t care

END;

ENDCASE => ERROR Bug[bug1];

STLeaf.Close[iLeaf];

[mpIILeafKey, rgILeaf] ← AllocateRoot[cKeyMax];

cKey ← 0;

rgILeaf[0] ← iLeaf;

cDescMax ← sizeLeafBody/sizeDesc;

cDescMin ← cDescMax/3; -- must be < cDescMax/2 for merge/balance logic

END;

Initialize[];

END.

LOG

Time: May 5, 1978 2:55 PMBy: McJonesAction: Create file

Time: June 22, 1978 4:06 PMBy: McJonesAction: keyTop.page was one too large (both kinds)

Time: June 26, 1978 1:06 PMBy: McJonesAction: projection Insert put new entry before old matching entry

Time: July 17, 1978 12:06 PMBy: McJonesAction: Upper bound for split root update loop was ) instead of ]; Delete allowed last page to become empty; Delete wouldn’t merge second-to-last page; Upper bound for merge root update loop was ) instead of ];

Balance updated wrong root entry

Time: August 31, 1978 11:59 AMBy: McJonesAction: Bugs in Get’s keyNext computation

Time: September 9, 1978 5:02 PMBy: McJonesAction: Added pinned to CachedSpace constructor

Time: September 22, 1978 6:33 PMBy: McJonesAction: SearchLeaf didn’t set last when found=TRUE

Time: February 1, 1979 2:24 PMBy: McJonesAction: pageRover in CachedSpace.Desc

Time: September 6, 1979 11:10 AMBy: McJonesAction: Dynamic root expansion

Time: October 1, 1979 9:56 AMBy: KnutsenAction: Made compatible with new CachedRegion.Desc and CachedSpace.Desc.

Time: July 7, 1980 4:32 PMBy: GobbelAction: Made compatible with new CachedRegion.Desc and CachedSpace.Desc.

Time: July 30, 1980 4:05 PMBy: GobbelAction: Made compatible with new CachedRegion.Desc. Initial Hierarchy entry for VM must have Transaction.nullHandle.