<<>>
    <<VersionMap2Variable.mesa>>
        <<Last tweaked by Mike Spreitzer on March 27, 1992 9:04 pm PST>>

    DIRECTORY Card2Tab, Card4Tab, PFSNames, RefTab, Rope, RopeHash, SymTab, VersionMap2, VersionMap2Implr;

    VersionMap2Variable: CEDAR PROGRAM
        IMPORTS Card2Tab, Card4Tab, PFSNames, RefTab, Rope, RopeHash, SymTab, VersionMap2, VersionMap2Implr
        EXPORTS VersionMap2
        =

    BEGIN OPEN VM2i:VersionMap2Implr, VersionMap2;

    VarMap: TYPE ~ REF VarMapPrivate;
    VarMapPrivate: TYPE ~ RECORD [
        size: INT _ 0,
        byName: RefTab.Ref--Name->TupleList--,
        byShort: SymTab.Ref-->TupleList--,
        byCreated: Card4Tab.Ref-->TupleList--,
        byStamp: Card2Tab.Ref-->TupleList--
        ];

    TupleList: TYPE ~ REF TupleCons;
    TupleCons: TYPE ~ RECORD [
        first: VersionTuple,
        rest: ARRAY ListId OF TupleList _ ALL[NIL]];

    ListId: TYPE ~ {short, created, stamp};

    vapMapClass: MapClass ~ VM2i.FillinDefaults[TRUE, writable, [
        Has: VarMapHas,
        Scan: VarMapScan,
        Size: VarMapSize,
        AddTuple: VarMapAddTuple,
        AddMap: VM2i.AddMapByTuples,
        RemTuple: VarMapRemTuple,
        RemMap: VM2i.RemMapByTuples,
        data: NIL]];

    CreateVariableMap: PUBLIC PROC RETURNS [Map] ~ {
        varm: VarMap ~ NEW [VarMapPrivate _ [
            size: 0,
            byName: RefTab.Create[equal: EqualName, hash: HashName],
            byShort: SymTab.Create[case: FALSE],
            byCreated: Card4Tab.Create[],
            byStamp: Card2Tab.Create[]
            ]];
        RETURN [[class: vapMapClass, data: varm]]};

    VarMapHas: PROC [map: Map, elt: VersionTuple] RETURNS [BOOL] ~ {
        varm: VarMap ~ NARROW[map.data];
        tl: TupleList ~ NARROW[varm.byName.Fetch[elt.name].val];
        RETURN [tl#NIL AND elt.created=tl.first.created AND elt.stamp=tl.first.stamp]};

    VarMapScan: PROC [map: Map, Consume: TupleConsumer, inOrder: BOOL, pfml: PatternFactoredMapList] RETURNS [MaybeTuple] ~ {
        IF inOrder THEN RETURN VM2i.SortScan[map, map.class.Scan, Consume, pfml];
        {varm: VarMap ~ NARROW[map.data];
        lp: ListAndPattern ~ PickListAndPattern[varm, pfml.pattern];
        IF TEqual[lp.p, pfml.pattern] THEN pfml.pattern _ nullTuple;
        IF lp.l = alluvem
        THEN {
            mt: MaybeTuple _ noMaybe;
            ScanPerStamp: PROC [key: VersionStamp, val: REF ANY] RETURNS [quit: BOOL _ FALSE] --Card2Tab.EachPairAction-- ~ {
                FOR tl: TupleList _ NARROW[val], tl.rest[stamp] WHILE tl#NIL DO
                    IF PfmlHas[pfml, tl.first] AND Consume[tl.first]
                        THEN {mt.it _ tl.first; RETURN [TRUE]};
                    ENDLOOP;
                RETURN [FALSE]};
            mt.found _ varm.byStamp.Pairs[ScanPerStamp];
            RETURN [mt]}
        ELSE {
            FOR tl: TupleList _ lp.l, tl.rest[lp.lid] WHILE tl#NIL DO
                IF PfmlHas[pfml, tl.first] AND Consume[tl.first] THEN RETURN [[TRUE, tl.first]];
                ENDLOOP;
            RETURN [noMaybe]};
        }};

    ListAndPattern: TYPE ~ RECORD [l: TupleList, lid: ListId, p: VersionTuple];
    alluvem: TupleList ~ NEW [TupleCons _ [nullTuple]];
    allrest: ARRAY ListId OF TupleList ~ alluvem.rest _ ALL[alluvem];
        <<Nobody should ever cdr down alluvem!>>

    PickListAndPattern: PROC [varm: VarMap, pat: VersionTuple] RETURNS [ListAndPattern] ~ {
        short: ROPE ~ IF pat.name # nullName THEN ShortName[pat.name] ELSE NIL;
        shortL: TupleList ~ IF short # NIL AND short.Find["*"] < 0 THEN NARROW[varm.byShort.Fetch[short].val] ELSE alluvem;
        createdL: TupleList ~ IF pat.created # nullCreated THEN NARROW[varm.byCreated.Fetch[CreatedTo4[pat.created]].val] ELSE alluvem;
        stampL: TupleList ~ IF pat.stamp # nullStamp THEN NARROW[varm.byStamp.Fetch[pat.stamp].val] ELSE alluvem;
        ans12: ListAndPattern ~ SELECT TRUE FROM
            shortL=NIL => [shortL, short, ShortNameToPattern[short]],
            createdL=NIL => [createdL, created, [created: pat.created]],
            shortL=alluvem => [createdL, created, [created: pat.created]],
            createdL=alluvem => [shortL, short, ShortNameToPattern[short]],
            createdL.rest[created]=NIL => [createdL, created, [created: pat.created]],
            shortL.rest[short]=NIL => [shortL, short, ShortNameToPattern[short]],
            ENDCASE => [createdL, created, [created: pat.created]];
        ans123: ListAndPattern ~ SELECT TRUE FROM
            stampL=NIL => [stampL, stamp, [stamp: pat.stamp]],
            ans12.l=NIL => ans12,
            ans12.l=alluvem => [stampL, stamp, [stamp: pat.stamp]],
            stampL=alluvem => ans12,
            ans12.l.rest[ans12.lid]=NIL => ans12,
            stampL.rest[stamp]=NIL => [stampL, stamp, [stamp: pat.stamp]],
            ENDCASE => ans12;
        RETURN [ans123]};

    VarMapSize: PROC [map: Map, limit: INT] RETURNS [INT] ~ {
        varm: VarMap ~ NARROW[map.data];
        RETURN [varm.size]};

    VarMapAddTuple: PROC [map: Map, t: VersionTuple, if: IfHads] RETURNS [had: Hads] ~ {
        varm: VarMap ~ NARROW[map.data];
        nl: TupleList ~ NARROW[varm.byName.Fetch[t.name].val];
        IF nl=NIL THEN had _ ALL[none]
        ELSE had _ [IF t.created=nl.first.created THEN same ELSE different, IF t.stamp=nl.first.stamp THEN same ELSE different];
        IF had=ALL[same] THEN RETURN;
        IF if[VM2i.OcFromHad[had]] THEN {
            short: ROPE ~ ShortName[t.name];
            it: TupleList _ nl;
            IF nl#NIL THEN {
                had2: Hads ~ VarMapRemTuple[map, [t.name, nl.first.created, nl.first.stamp]];
                IF had2 # [same, same] THEN ERROR;
                it.first _ t}
            ELSE it _ NEW [TupleCons _ [t]];
            IF NOT varm.byName.Insert[t.name, it] THEN ERROR;
            it.rest[short] _ NARROW[varm.byShort.Fetch[short].val];
            it.rest[created] _ NARROW[varm.byCreated.Fetch[CreatedTo4[t.created]].val];
            it.rest[stamp] _ NARROW[varm.byStamp.Fetch[t.stamp].val];
            [] _ varm.byShort.Store[short, it];
            [] _ varm.byCreated.Store[CreatedTo4[t.created], it];
            [] _ varm.byStamp.Store[t.stamp, it];
            varm.size _ varm.size+1};
        RETURN};

    ListDel: PROC [list, elt: TupleList, lid: ListId] RETURNS [TupleList] ~ {
        IF list=elt THEN RETURN [list.rest[lid]];
        {cur: TupleList _ list.rest[lid];
        prev: TupleList _ list;
        DO
            IF cur = elt THEN {prev.rest[lid] _ cur.rest[lid]; RETURN [list]};
            prev _ cur; cur _ cur.rest[lid];
            ENDLOOP}};

    VarMapRemTuple: PROC [map: Map, t: VersionTuple] RETURNS [had: Hads] ~ {
        varm: VarMap ~ NARROW[map.data];
        nl: TupleList ~ NARROW[varm.byName.Fetch[t.name].val];
        IF nl=NIL THEN had _ ALL[none]
        ELSE had _ [IF t.created=nl.first.created THEN same ELSE different, IF t.stamp=nl.first.stamp THEN same ELSE different];
        IF had # ALL[same] THEN RETURN;
        IF NOT varm.byName.Delete[t.name] THEN ERROR;
        {short: ROPE ~ ShortName[t.name];
        [] _ varm.byShort.Store[short, ListDel[NARROW[varm.byShort.Fetch[short].val], nl, short]];
        [] _ varm.byCreated.Store[CreatedTo4[t.created], ListDel[NARROW[varm.byCreated.Fetch[CreatedTo4[t.created]].val], nl, created]];
        [] _ varm.byStamp.Store[t.stamp, ListDel[NARROW[varm.byStamp.Fetch[t.stamp].val], nl, stamp]];
        varm.size _ varm.size - 1;
        RETURN}};

    EqualName: PROC [key1, key2: REF ANY] RETURNS [BOOL] ~ {
        n1: Name ~ NARROW[key1];
        n2: Name ~ NARROW[key2];
        RETURN n1.Equal[n2]};

    HashName: PROC [key: REF ANY] RETURNS [hash: CARDINAL _ 0] ~ {
        name: Name ~ NARROW[key];
        FOR i: NAT IN [0 .. name.ComponentCount[]) DO
            c: PFSNames.Component ~ name.Fetch[i];
            cr: ROPE ~ c.ComponentRope[--don't care whether version is included--];
            hash _ hash + RopeHash.FromRope[cr, FALSE];
            ENDLOOP;
        RETURN};

    ShortName: PROC [n: Name] RETURNS [ROPE] ~ {
        RETURN n.ShortName[].ComponentRope[--must not and does not include version--]};

    CreatedTo4: PROC [c: Created] RETURNS [Card4Tab.Key]
        ~ TRUSTED INLINE {RETURN [LOOPHOLE[c]]};

    END.