-- ChipNetImpl.mesa

-- A package of routines that maintains net interconnect
-- structures.

-- last modified by E. McCreight, October 1, 1984  3:35 PM
-- written by E. McCreight, November 5, 1981  10:24 AM

DIRECTORY
  ChipDRC,
  ChipExpand,
  ChipNetDefs,
  ChipUserInt,
  CWF,
  InlineDefs,
  ppdefs;

ChipNetImpl: PROGRAM
  IMPORTS ChipDRC, ChipExpand, ChipNetDefs, ChipUserInt, CWF
  EXPORTS ChipNetDefs =
  BEGIN OPEN ppdefs, ChipUserInt, ChipNetDefs;


  freeNets: LONG POINTER TO link Net _ NIL;
  freeIds: FreeNetIdPtr _ NIL;

  allNets: PUBLIC NetIdPtr _ NIL;

  NewNet: PUBLIC PROCEDURE[initRefs: CARDINAL _ 1]
    RETURNS[CanonNetPtr] =
    BEGIN
    cn: CanonNetPtr;
    IF freeNets=NIL THEN
      cn _ LOOPHOLE[netZ.NEW[net _
        [refs: initRefs, rest: canon[id: NewNetId[]]]]]
    ELSE
      BEGIN
      cn _ LOOPHOLE[freeNets];
      freeNets _ LOOPHOLE[freeNets.nxt];
      cn^ _ [refs: initRefs, rest: canon[id: NewNetId[]]];
      END;
    RETURN[cn];
    END;


  NewNetId: PROCEDURE[]
    RETURNS[id: NetIdPtr] =
    BEGIN
    call: CellCallPtr _ NIL;
    IF freeIds=NIL THEN
      BEGIN
      id _ netIdZ.NEW[NetId _ [next: allNets, details: normal[
        name: anonymous[]]]];
      allNets _ id;
      END
    ELSE
      BEGIN
      id _ freeIds; freeIds _ freeIds.nextFree;
      id^ _ [next: id.next, details: normal[
        name: anonymous[]]];
      END
    END;


  RefCanonNet: PUBLIC PROCEDURE[n: netPtr,
    newRefs: INTEGER _ 1] RETURNS[CanonNetPtr] =
    BEGIN
    nInt: netIntPtr _ n;
    canonNet: CanonNetPtr;
    skipWeight: CARDINAL;
    IF nInt=NIL THEN RETURN[NewNet[newRefs+1]];
    DO
      WITH dn: nInt SELECT FROM
        link => nInt _ dn.nxt;
        canon => {canonNet _ @dn; EXIT};
        ENDCASE;
      ENDLOOP;
    nInt _ n;
    skipWeight _ 1;
    DO
      np: netIntPtr _ nInt;
      WITH dn: np SELECT FROM
        link =>
          BEGIN
          newSkipWeight: CARDINAL _ dn.refs;
          nInt _ dn.nxt;
          IF (dn.refs _ dn.refs-skipWeight)=0 THEN
            {dn.nxt _ freeNets; freeNets _ @dn}
          ELSE dn.nxt _ canonNet;
            -- the original incoming reference will now skip over
            -- this link.
          skipWeight _ newSkipWeight;
          END;
        canon =>
          BEGIN
          IF (dn.refs _ dn.refs+newRefs)=0 THEN
            BEGIN
            np.rest _ link[nxt: freeNets];
            freeNets _ LOOPHOLE[np];
            canonNet _ NIL;
            END;
          RETURN[canonNet];
          END;
        ENDCASE;
      ENDLOOP;
    END; -- of RefCanonNet


  GetNormalNetId: PUBLIC PROCEDURE[n: LONG POINTER TO netPtr]
    RETURNS[NormalNetIdPtr] =
    BEGIN
    cn: CanonNetPtr;
    IF n=NIL THEN GOTO Malformed;
    cn _ n^ _ CanonNet[n^];
    WITH nid: cn.id SELECT FROM
      normal => RETURN[@nid];
      ENDCASE => GOTO Malformed;
    EXITS
      Malformed =>
        BEGIN
        Explain["GetNormalNetId called with improper arguments"];
        RETURN[NIL]
        END;
    END;  -- of GetNormalNetId


  MergeNets: PUBLIC PROCEDURE[n1, n2: netPtr]
    RETURNS[CanonNetPtr] =
    BEGIN
    cn1: CanonNetPtr _ CanonNet[n1];
    cn2: CanonNetPtr _ CanonNet[n2];
    IF cn1#cn2 THEN
      BEGIN -- merging two canonical nets
      nInt2: netIntPtr;
      id: NetIdPtr _ JoinNetIds[cn1, cn2];
      IF cn1.refs<cn2.refs THEN -- reverse cn1 and cn2
        {cnTemp: CanonNetPtr _ cn1; cn1 _ cn2; cn2 _ cnTemp};
      cn1.refs _ cn1.refs+cn2.refs;
      cn1.id _ id;
      nInt2 _ cn2; -- decommit cn2's variant
      nInt2.rest _ link[nxt: cn1];
      cn2 _ CanonNet[nInt2];
        -- adjusts reference count of nInt2
      IF id.violations#NIL THEN
        ChipDRC.PurgeDRCViolations[cn1];
      END;
    RETURN[cn1];
    END; -- of MergeNets


  JoinNetIds: PROCEDURE[cn1, cn2: CanonNetPtr] RETURNS[n: NetIdPtr] =
    BEGIN
    n1: NetIdPtr = cn1.id;
    n2: NetIdPtr = cn2.id;
    IF n1=n2 THEN RETURN[n1];
    WITH nid1: n1 SELECT FROM
      well =>
        WITH nid2: n2 SELECT FROM
          well =>
            SELECT TRUE FROM
              nid1.attachedTo=NIL =>
                BEGIN
                n _ @nid2;
                n1.details _ free[nextFree: freeIds];
                freeIds _ LOOPHOLE[n1];
                END;
              ENDCASE =>
                BEGIN
                IF nid2.attachedTo#NIL THEN
                  BEGIN
                  cn: CanonNetPtr _ CanonNet[nid2.attachedTo];
                  AttachNetToWell[normal: cn, well: cn1];
                  cn _ DeRefNet[cn];
                  END;
                n _ @nid1;
                n2.details _ free[nextFree: freeIds];
                freeIds _ LOOPHOLE[n2];
                END;
          ENDCASE => ERROR;
      normal =>
        WITH nid2: n2 SELECT FROM
          normal => n _ JoinNormalNetIds[@nid1, @nid2];
          ENDCASE => ERROR;
      ENDCASE => ERROR;
    END; -- of JoinNetIds


  AttachNetToWell: PROC [normal: CanonNetPtr, well: CanonNetPtr] =
    BEGIN
    WITH w: well.id SELECT FROM
      well =>
        SELECT w.attachedTo FROM
          NIL => w.attachedTo _ RefCanonNet[normal];
          ENDCASE => -- not NIL
            SELECT (w.attachedTo _ CanonNet[w.attachedTo]) FROM
              normal => NULL; -- attaching to same net twice is NOP
              ENDCASE =>
                WITH n: normal.id SELECT FROM
                  normal =>
                    n.violations _ uz.NEW[ViolationList _ [
                      next: n.violations,
                      v: [
                        place: RefCoordPt[w.final.r],
                        info: differentNetsToWell[lev: w.final.lev,
                          wellNode: RefCanonNet[well],
                          n: RefCanonNet[normal]]]]];
                  ENDCASE => ERROR; -- normal doesn't point to normal NetId
      ENDCASE => ERROR; -- well doesn't point to well NetId
    END;


  JoinNormalNetIds: PROCEDURE[n1, n2: NormalNetIdPtr]
    RETURNS[n: NormalNetIdPtr] =
    BEGIN
    id: NetIdPtr;
    caps: ARRAY Conductors OF LayerCap;
    UpdateAreas[n1];
    UpdateAreas[n2];
    FOR cond: Conductors IN Conductors DO
      caps[cond].cutSides _ n1.caps[cond].cutSides+
        n2.caps[cond].cutSides;
      caps[cond].cutWidth _ n1.caps[cond].cutWidth+
        n2.caps[cond].cutWidth;
      caps[cond].perimeter _ n1.caps[cond].perimeter+
        n2.caps[cond].perimeter;
      caps[cond].area _ n1.caps[cond].area+
        n2.caps[cond].area;
      ENDLOOP;
    WITH dn1: n1 SELECT FROM
      anonymous => n _ n2;
      numeric =>
        WITH dn2: n2 SELECT FROM
          anonymous, numeric => n _ n1;
          ENDCASE => n _ n2;
      qualified =>
        WITH dn2: n2 SELECT FROM
          anonymous, numeric => n _ n1;
          qualified =>
            n _ IF CallDepth[n1.source]<=CallDepth[n2.source]
              THEN n1 ELSE n2; -- less qualified is better
          ENDCASE => n _ n2;
       ENDCASE => n _ n1;
    n.caps _ caps;
    n.final _
      (IF n1.final.r.x2<n2.final.r.x2 THEN n2.final ELSE n1.final);

    n.hasPathToGnd _ n1.hasPathToGnd OR n2.hasPathToGnd;
    n.hasPathToVdd _ n1.hasPathToVdd OR n2.hasPathToVdd;
    n.hasDepletionPullup _ n1.hasDepletionPullup OR
      n2.hasDepletionPullup;
    n.couldBeLogo _ n1.couldBeLogo AND n2.couldBeLogo;

    IF n2.violations#NIL THEN
      BEGIN
      FOR v: ViolationListPtr _ n2.violations, v.next DO
        IF v.next=NIL THEN {v.next _ n1.violations; EXIT};
        ENDLOOP;
      n.violations _ n2.violations;
      END
    ELSE n.violations _ n1.violations;
    IF n=n1 THEN n1 _ n2;
    id _ n1;
    id.details _ free[nextFree: freeIds];
    freeIds _ LOOPHOLE[id];
    END; -- of JoinNormalNetIds


  UpdateAreas: PUBLIC PROCEDURE[n: NormalNetIdPtr] =
    BEGIN
    IF n.lastX<currentX THEN
     FOR cond: Conductors IN Conductors DO
      n.caps[cond].perimeter _ n.caps[cond].perimeter+
        n.caps[cond].cutSides*ScaleToChipmonk[currentX-n.lastX];
      n.caps[cond].area _ n.caps[cond].area+
        n.caps[cond].cutWidth*
          LONG[ScaleToChipmonk[currentX-n.lastX]];
      ENDLOOP;
    n.lastX _ currentX;
    END; -- of UpdateAreas


  CallDepth: PROCEDURE[c: InstancePtr]
    RETURNS[d: CARDINAL] =
    BEGIN
    d _ 0;
    FOR ancest: InstancePtr _ c, ancest.caller.head
      WHILE ancest#NIL DO
      d _ d+1;
      ENDLOOP;
    END;


  FeatureNet: PUBLIC PROC [f: FeaturePtr] RETURNS [CanonNetPtr] =
    BEGIN
    cn: CanonNetPtr;
    IF f.net=NIL THEN
      BEGIN
      cn _ f.net _ NewNet[1];
      cn.id.final _ [lev: f.lev, r: f.cover];
      SELECT f.lev FROM
        nwel, pwel => cn.id.details _ well[attachedTo: NIL];
        ENDCASE => cn.id.details _ 
          normal[source: ChipExpand.NearestCellInstance[f.caller.head],
            name: anonymous[]];
      END
    ELSE cn _ f.net _ CanonNet[f.net];
    cn.id.final _ [lev: f.lev, r: f.cover];
    RETURN[cn];
    END;


  MergeFeatureNets: PUBLIC PROC [f1, f2: FeaturePtr] =
    BEGIN
    -- Merge them unless they are of different types (e.g., node vs well).
    -- In that case, relate them.
    id: NetIdPtr;
    IF f1.lev=f2.lev THEN
      BEGIN
      cn: CanonNetPtr;
      SELECT f1.net FROM
        #NIL =>
          SELECT f2.net FROM
            #NIL => cn _ MergeNets[f1.net, f2.net];
            ENDCASE => cn _ RefCanonNet[f1.net];
        ENDCASE => cn _ RefCanonNet[FeatureNet[f2]];
      id _ (f1.net _ f2.net _ cn).id;
      END
    ELSE
      BEGIN
      cn1: CanonNetPtr _ FeatureNet[f1];
      cn2: CanonNetPtr _ FeatureNet[f2];
      IF cn1.id.type=cn2.id.type THEN
        id _ (f1.net _ f2.net _ MergeNets[f1.net, f2.net]).id
      ELSE
        BEGIN
        IF cn1.id.type#normal THEN -- exchange nets
          {t: CanonNetPtr _ cn1; cn1 _ cn2; cn2 _ t};
        IF NOT(cn1.id.type=normal AND cn2.id.type=well) THEN ERROR;
        AttachNetToWell[normal: cn1, well: cn2];
        RETURN;
        END;
      END;
    IF id.final.r.x2<f1.cover.x2 THEN
      id.final _ [lev: f1.lev, r: f1.cover];
    IF id.final.r.x2<f2.cover.x2 THEN
      id.final _ [lev: f2.lev, r: f2.cover];
    END; -- of MergeFeatureNets


  CountNetIds: PROCEDURE [examine: BOOLEAN _ FALSE] RETURNS
    [ids, frees, wells, anonymi, numerics, qualifieds, zeroAreas: LONG INTEGER _ 0] =
    BEGIN
    FOR n: NetIdPtr _ allNets, n.next WHILE n#NIL DO
      ids _ ids+1;
      WITH dn: n SELECT FROM
        free => frees _ frees+1;
        well => wells _ wells+1;
        normal =>
          BEGIN
          FOR c: Conductors IN Conductors DO
            IF dn.caps[c] # [0,0,0,0] THEN EXIT;
            REPEAT
              FINISHED =>
                IF dn.final.r.x2<currentX THEN
                  BEGIN
                  zeroAreas _ zeroAreas+1;
                  IF examine THEN
                    BEGIN
                    s: STRING _ [100];
                    CWF.SWF1[sto: s, s: "Zero-area node in %s here...", a: levelNames[dn.final.lev]];
                    RemarkAtPoint[RefCoordPt[dn.final.r], s];
                    END;
                  END;
            ENDLOOP;
          WITH ddn: dn SELECT FROM
            anonymous => anonymi _ anonymi+1;
            numeric => numerics _ numerics+1;
            qualified => qualifieds _ qualifieds+1;
            ENDCASE => ERROR;
          END;
        ENDCASE => ERROR;
      ENDLOOP;
    END;


  END. -- of ChipNetImpl