typedefstruct char char struct

Innlesning

readbench.ld

##addtop

#include^<stdio.h^>

#include^<stdlib.h^>

#include^<string.h^>

#include"datastruct.h"

= Datastructuretokeepthetransistorsforeachcelluntilwemakeinstancesindomains. ⁼

typedefstruct char char struct

name[STRLEN];placed;^terminalterminal^next;f

gTerminal;

typedefstruct char

NodeEdgeTerminal

struct

name[STRLEN];startedge;cellstartnode;startterminal;cellnext;^f

gCell;

Cellstartcell=NULL;⁼ Startoflistofallcells.⁼

Cellcurrentcell=NULL;⁼Themostrecentlyreadcell⁼

Nodecurrentnode=NULL;⁼Themostrecentlyreadtransistor ⁼

Edgecurrentedge=NULL;⁼ Themostrecentlyreadnet⁼

Terminalcurrentterminal=NULL;⁼ Themostrecentlyreadterminal⁼

char

auxname1[STRLEN],auxname2[STRLEN],auxname3[STRLEN],instance[STRLEN];

= Auxilliaryvariables ⁼

= Somefunctionsforoperationsonthecelldatastructure ⁼

VedleggA:Cluster

CellCell

if

(!c)perror(exit(1);InitializeCell(^fc=(Cell"malloc")malloc(

char

);name)

sizeof

^f(Cell));

gstrcpy(c^!name,name);

c^!startnode=NULL;

c^!startedge=NULL;

c^!startterminal=NULL;

c^!next=NULL;

return

^c;

g

void

InsertCell(Cellc)^f

=INVARIANT:chasNULLpointerfornext.Thecellisinsertedatthestartofthelist⁼

if

(startcell)cstartcell=c;^!next=startcell;^f

g

else

startcell=c;

g

CellCell

int while

if else

found=0;FindCell((strcmp(c(c&&!found)c=start;^c=c!next;

char

^!name,name)==0)found=1;^fname,Cellstart)^f

g

return

c;

g

TerminalTerminal

if

(!t)perror(exit(1);^fInitializeTerminal("malloc"t=(Terminal); )malloc(

char

name)

sizeof

(Terminal));^f

gstrcpy(t^!name,name);

t^!placed='E';⁼ Eforempty ⁼

t^!next=NULL;

return

t;

g

readbench.ld

void

InsertTerminal(Terminalt,Terminal start)^f

=INVARIANT:thasNULLpointerfornext.Theterminalisinsertedatthestartofthelistinacelloradomain.⁼

if

(t^!start)next=^fstart;

start=t;

g

else

start=t;

g

void

TerminalCopyTerminals(Terminalt1,t2; old,Terminal new)^f

new=NULL;

t1=old;

while

t2=InitializeTerminal(t1InsertTerminal(t2,new);t1=t1(t1)^!fnext; ^!name);

g

g

void

Terminal

while

strcat(tstrcat(tt=tAddNamesForTerminals(^!(t)next;^f!!t=start;name,name,ext);^"");

char

ext,Terminalstart)^f

g

g

void if

(t)DeleteTerminals(tDeleteTerminals(Terminal^!next);t)^f

elsereturn

^;

free(t);

g

void if

(c)DeleteNodes(cDeleteEdges(cDeleteTerminals(cDeleteCells(cDeleteCells(Cell^{f !!!}next);startedge);startnode);^!c)startterminal);^f

g

else

VedleggA:Cluster

return

^;

free(c);

g

= Datastructurefordomains. ⁼

typedefstruct char

NodeEdgeTerminalTerminal

struct

name[STRLEN];startedge;domainstartnode;startterminal;startinnerterminal;domainnext;^f

gDomain;

Domainstartdomain=NULL;⁼ Startoflistofalldomains.⁼

Domaincurrentdomain=NULL;⁼Themostrecentlyreaddomain⁼

Domaininnerdomain=NULL;⁼ Themostrecentlyreadinnerdomain⁼

Domainworkingdomain=NULL;⁼ Domainunderconstruction⁼

Cellworkingcell=NULL;⁼ Cellunderconstruction⁼

int

domain;⁼Indicatesifwereadadomainoracell ⁼

Terminalauxterm1,auxterm2;⁼Auxilliaries⁼

= Thesewillbeusedwheninstantiatingcells/innerdomains.⁼

= Somefunctionsforoperationsonthedomaindatastructure⁼

Domain_DomainInitializeDomain(

char

^name)f

d=(Domain)malloc(

sizeof

(Domain));

if

(!d)perror(exit(1);^f "malloc");

gstrcpy(d^!name,name);

d^!startnode=NULL;

d^!startedge=NULL;

d^!startterminal=NULL;

d^!startinnerterminal=NULL;

d^!next=NULL;

return

^d;

g

void

InsertDomain(Domaind)^f

=INVARIANT:dhasNULLpointerfornext.

readbench.ld Thedomainisinsertedatthestartofthelist⁼

if

(startdomain)dstartdomain=d;^!next=startdomain;^f

g

else

startdomain=d;

g

DomainDomain

int while if else

found=0;(strcmp(d(d&&!found)d=dFindDomain(d=start;^!next;^!name,name)==0)found=1;^f

char

name,Domainstart)^f

g

return

d;

g

void if

(d)DeleteNodes(dDeleteEdges(dDeleteTerminals(dDeleteTerminals(dDeleteDomains(dDeleteDomains(Domain^{f !!}startedge);startnode);^!!!next);startterminal);startinnerterminal);d)^f

g

elsereturn

; free(d);

g

char if elseif

(strcmp(name,strcpy(name,strcat(name,strcat(name,blockname);MakeName((strcmp(name,^"""vgnd""vss"

char

);"vdd")==0);name,)^{j j6=}strcmp(name,

char

0&&strcmp(name,blockname)"gnd"^f"vgnd")==0) )⁶⁼0)^f

g

return

name;

g

= Hereisthestartofreadingacell ⁼

##begincell

VedleggA:Cluster

InsertCell(currentcell=InitializeCell(zzs));⁼ Initializewiththecellnamewehavejustread⁼

##termlistcellname

= Thisisthecellsinterfacetotheothercells/domains,sothesenameswillpossiblychange.Westoretheminalistkeptwitheachcell.Thecellnameisaddedtothename,tokeeptrackofwhichcellitsfrom. ⁼

strcpy(auxname1,zzs);

MakeName(auxname1,currentcell^!name);

InsertTerminal(InitializeTerminal(auxname1),&(currentcell^!startterminal));

= Aterminalisalsoasignal,sowehavetomakeone.Thenameofthissignalmaychangecompletelylater. ⁼

InsertEdge(InitializeEdge(auxname1),&(currentcell^!startedge));

##siglistname

= Asignalisonlyanedge.Thenameissignamecellname.Thismaybeextendedasthecellisencapsulatedfurtherinto(possiblyseveral)layersofdomains.Someofthebenchmarksputthesamenamebothintermlistandinsiglist,sowehavetocheckthatthenamedoesnotexistintheedgelist.⁼

strcpy(auxname1,zzs);

MakeName(auxname1,currentcell^!name);

if

(!FindEdge(auxname1,currentcellInsertEdge(InitializeEdge(auxname1),&(currentcell^!startedge)) ^!startedge));

##translistname

= Atransistorisanodewithlotsofattributes,butwewillreadthislater.Thenameistreatedsimiliarasforsignals. ⁼

strcpy(auxname1,zzs);

MakeName(auxname1,currentcell^!name);

RInsertNode(currentnode=InitializeNode(auxname1,'E'),&(currentcell^!startnode));

##translistsource

strcpy(auxname1,zzs);

MakeName(auxname1,currentcell^!name);

if

((currentedge=FindEdge(auxname1,currentcellcurrentnode^!source=currentedge; ^!startedge)))^f

readbench.ld

MakePointerToNode(currentedge,currentnode);

g

else

printf("Readingtranslistfromfile:Node");

printf("%scouldnotfindnet%sfor source.ⁿn",currentnode^!name,zzs);

##translistgate

strcpy(auxname1,zzs);

MakeName(auxname1,currentcell^!name);

if

((currentedge=FindEdge(auxname1,currentcellcurrentnodeMakePointerToNode(currentedge,currentnode);^!gate=currentedge; ^!startedge)))^f

g

else

printf("Readfromfile:Node%scouldnotfindnet%sfor gate.ⁿn"currentnode, ^!name,zzs);

##translistdrain

strcpy(auxname1,zzs);

MakeName(auxname1,currentcell^!name);

if

((currentedge=FindEdge(auxname1,currentcellcurrentnodeMakePointerToNode(currentedge,currentnode);^!drain=currentedge; ^!startedge)))^f

g

else

printf("Readfromfile:Node%scouldnotfindnet%sfor drain.currentnodeⁿn", ^!name,zzs);

##attributetranslistinteger

= Integerattributeofatransistorhasbeenread. ⁼

if

(strcmp(zzw,currentnode"width"^!width=()==0)

double

)zzn;

elseif

currentnode(strcmp(zzw,^!"length"length=(

double

)==0)^)zzn;

##attributetranslistdecimal

= Decimalattributeofatransistorhasbeenread.⁼

VedleggA:Cluster

if

(strcmp(zzw,currentnode"width"^!width=zzn;)==0)

elseif

currentnode(strcmp(zzw,^!"length"length=zzn;)==0)

##attributetransliststring

= Stringattributehasbeenread⁼

if

(strcmp(zzw,SetType(currentnode,zzs[0]);"type")==0)

##endcell

if

(strcmp(zzs,currentcellprintf("Inconsistencyindata:cellbegin%sendedwith^!name)⁶⁼0)

cellend%s.currentcellⁿn", ^!name,zzs);

= Wehavenishedreadingacell⁼

= Hereweareabouttostartreadadomain ⁼

##begindomain

InsertDomain(currentdomain=InitializeDomain(zzs));

= Initializewiththedomainnamewehavejustread⁼

workingdomain=NULL;⁼ThesehavetobeNULL,becausewedothe⁼

workingcell=NULL;⁼ insertion"oneroundlater".⁼

##iolistsignal

= Thisisthedomainsinterfacetotheotherdomains,sothesenameswillpossiblychange.Westoretheminalistkeptwitheachdomain.Thedomainnameisaddedtothename,tokeeptrackofwhichdomainitsfrom. ⁼

strcpy(auxname1,zzs);

MakeName(auxname1,currentdomain^!name);

InsertTerminal(currentterminal=InitializeTerminal(auxname1),&(currentdomain^!startterminal));

= Aterminalisalsoasignal,sowehavetomakeone.Thenameofthissignalmaychangecompletelylater. ⁼

InsertEdge(InitializeEdge(auxname1),&(currentdomain^!startedge));

readbench.ld

##iolisttop

currentterminal^!placed='T';

##iolistbottom

currentterminal^!placed='B';

##rowgate

= Wehavereadaninstanceofacelloradomain. ⁼

= Firstwemergethestructurewemadefromlastgateintherow,withtherestofthestructureinthedomain.IfitisthersttimeworkingdomainandworkingcellwillbeNULLpointers,sowedonothing.Thetestondomainistoensurethatwemergethecorrectstructures. ⁼

if

(domain&&workingdomain)MergeStructures(workingdomain&(currentdomain^!startnode,workingdomain^!startnode),&(currentdomain^!startedge,^!startedge));

elseif

MergeStructures(workingcell(workingcell) &(currentdomain^!startnode,workingcell^!startnode),&(currentdomain^!startedge, ^!startedge));

if

((innerdomain=FindDomain(zzs1,startdomain)))^f

= domain=1;strcpy(auxname1,zzs1);strcpy(instance,zzs2);MakeName(auxname1,zzs2);workingdomain=InitializeDomain(auxname1);CopyStructure(innerdomainCopyTerminals(innerdomainAddNamesForNodes(zzs2,workingdomainAddNamesForEdges(zzs2,workingdomainAddNamesForTerminals(zzs2,workingdomainCopyTerminals(innerdomainIfitisadomain,wecopyit,instantiateandgettheiolistofthedomainsincethesenamesareknowntousnow.&(workingdomain^!!!startnode,innerdomainstartterminal,&(workingdomainstartterminal,&auxterm1);^!startnode),&(workingdomain^!!startedge);startnode);^!startterminal); ^=!startedge,^!startterminal));^!startedge));

=

if

Wehavetoinsertawholelistofinnerterminals((currentdomainauxterm2=auxterm1;

while

auxterm2currentdomainauxterm2=auxterm2(auxterm2^!next=currentdomain^!!!startinnerterminal=auxterm1;startinnerterminal&&auxterm1))next)^!next; ^!startinnerterminal;^{= f}

g

else

VedleggA:Cluster

currentdomain^!startinnerterminal=auxterm1;

g

elseif

((currentcell=FindCell(zzs1,startcell)))^f

=Ifitisacellwedoonlythecopyingandinstantiatingpart.⁼

domain=0;

strcpy(auxname1,zzs1);

MakeName(auxname1,zzs2);

workingcell=InitializeCell(auxname1);

CopyStructure(currentcell&(workingcell^!startnode,currentcell^!startnode),&(workingcell^!startedge,^!startedge));

CopyTerminals(currentcell^!startterminal,&(workingcell^!startterminal));

AddNamesForNodes(zzs2,workingcell^!startnode);

AddNamesForEdges(zzs2,workingcell^!startedge);

AddNamesForTerminals(zzs2,workingcell^!startterminal);

auxterm1=workingcell^!startterminal;

g

else

printf("Domain%siscalling%s,whichdoesnot exist.ⁿn",currentdomain^!name,zzs1);

##rowsignal

= Wehavereadoneofthesignalsinthisinstanceandweshallinstantiateitbychangingthecorrespondingnameinthestructurewehavepreviouslycopied. ⁼

if

^(domain)strcpy(auxname2,zzs);MakeName(auxname2,currentdomainstrcpy(auxname3,auxterm1MakeName(auxname3,instance);

if else

(ChangeEdgeNames(auxname3,auxname2,workingdomainstrcpy(auxterm1_printf(^f"Failedtosubstitute%sfor%sindomaininstance%s^!name,auxname2);^!name);^!name); ^!startedge))

in%s.ⁿn",auxname2,auxterm1^!name,auxname1,currentdomain^!name);

g

else

strcpy(auxname2,zzs);MakeName(auxname2,currentdomain^{f !}name);

=strcpy(auxname3,auxterm1-MakeName(auxname3,instance);^>name);⁼

if

(ChangeEdgeNames(auxterm1strcpy(auxterm1^!name,auxname2);^!name,auxname2,workingcell^!startedge))

else

_printf("Failedtosubstitute%sfor%sincellinstance%s

readbench.ld

in%s.ⁿn",auxname2,auxterm1^!name,auxname1,currentdomain^!name);

g

if

(auxterm1)auxterm1=auxterm1^!next;

else

printf("Moreactualthanformalparametersin%s.ⁿn",auxname1);

##rowtail

= Wehavetoinsertthelastelementaswell.⁼

if

(domain&&workingdomain)MergeStructures(workingdomain&(currentdomain^!startnode,workingdomain^!startnode),&(currentdomain^!startedge,^!startedge));

elseif

(workingcell)

MergeStructures(workingcell&(currentdomain^!startnode,workingcell^!startnode),&(currentdomain^!startedge, ^!startedge));

##enddomain

if

(strcmp(zzs,currentdomainprintf("Inconsistency:domainbegin%sendedwithdomain^!name)⁶⁼0)

end%s.ⁿn",currentdomain^!name,zzs);

##addend

void

NodeTerminalEdgeCleanUp()e;n;t;^f

=Allcellstructuresmaybethrownaway,... ⁼

DeleteCells(startcell);

=andnearlyalldomainstructures.⁼

if

(startdomain==currentdomain)DeleteDomains(startdomain^!next);

else

_printf("Internalerror:Nodomainsdeletedduetochangesin program.ⁿn");

=Theglobalterminalsmustbeconvertedtonodes⁼

t=currentdomain^!startterminal;

while

RInsertNode(n=InitializeNode(t(t)^{f !}name,'T'),&(currentdomain^!startnode));

VedleggA:Cluster

e=FindEdge(t^!name,currentdomain^!startedge);

n^!source=e;

MakePointerToNode(e,n);

n^!placed=t^!placed;

t=t^!next;

g

=Weinitializetheglobalvariables,... ⁼

startnode=currentdomain^!startnode;

startedge=currentdomain^!startedge;

=anddeletethelastparts ⁼

DeleteTerminals(currentdomain^!startterminal);

DeleteTerminals(currentdomain^!startinnerterminal);

free(currentdomain);

=Edgesconnectedtononodesarefeedthroughsthatwedidntneed,sowegiveawarninganddeletethem. ⁼

e=startedge;

while if

(!eprintf((e)^!fsize)"WARNING:Deletedfeedthroughedge%s,connectedto0^f nodes.RemoveEdge(e,&startedge);ⁿn",e^!name);

ge=e^!next;

g

=Somemoreglobalvariablesweshouldinitialize. ⁼

numberofnodes=CountNodes(startnode);

numberofedges=CountEdges(startedge);

g

main.c

Partisjonering

main.c

#include"datastruct.h"

#include"partition.h"

#include"^cluster.h"

#include^<stdio.h^>

#include^<stdlib.h^>

#include^<unistd.h^>

externvoid

CleanUp();

externint

CutValue();

externint

MakeFirstPartition();

externint

KernighanLin();

#defineNEIGHTRUE

#defineNONEIGHFALSE

void

MakeClusters(Nodestartn,Edgestarte,Clusterstartc)

f FindDirectlyConnectedNodes(startn,starte,startc,&DiffTest,NONEIGH);FindDirectlyConnectedNodes(startn,starte,startc,&PolyTest,NONEIGH);ConnectClusters(startn,starte,startc,NONEIGH);GrowClusters(startn,starte,startc);ConnectTerminals(startn,starte,startc);PrintClusterStatistics(printf(^"nnNumberofP-Ntwinpairs:%dstartc); ⁿnⁿn",numberoftwins);

g

void

MakeClustersWithNeighbours(NodeClusterstartn,Edgestartc)starte,

f FindPNTwins(startn,starte,startc);FindDirectlyConnectedNodes(startn,starte,startc,&DiffTest,NEIGH);FindDirectlyConnectedNodes(startn,starte,startc,&PolyTest,NEIGH);ConnectClusters(startn,starte,startc,NEIGH);GrowClusters(startn,starte,startc);ConnectTerminals(startn,starte,startc);PrintClusterStatistics(printf(^"nnNumberofP-Ntwinpairs:%dstartc); ⁿnⁿn",numberoftwins);

g

void

ClearStructures(Nodestartn,Cluster startc)

f DeleteClusters(startc);

startc=NULL;

VedleggA:Cluster

while

_startn^(startn)f

!cluster=NULL;

startn^!partition=-1;

startn^!traversed=0;

startn^!change=0;

startn=startn^!next;

g

g

void

main()

f ClusterNodeEdge

int

srand((yyparse();CleanUp();PrintStatistics(startnode,startedge);MakeClustersWithNeighbours(startnode,startedge,&startcluster);ClearStructures(startnode,&startcluster);MakeClusters(startnode,startedge,&startcluster);ClearStructures(startnode,&startcluster);cut=MakeFirstPartition();printf(cut=KernighanLin();printf(cut,i;"Theinitialcutvaluefortwopartitionsis%d"ThecutvalueafterrunningKernighan-Linis%dnewstartedge=NULL;

unsignedint

newstartnode=NULL;startcluster=NULL;)getpid());⁼ Initializerand()values ^{= n}n"ⁿn,cut);ⁿn",

cut);

g

datastruct.h

datastruct.h

#ifndefDATASTRUCTH

#defineDATASTRUCTH

#defineTRUE1

#defineFALSE0

#defineSTRLEN60

= Declarationsofnodesandedgesinthisparticularkindofgraphs.

=

= Anodehasexactlythreeedges,becauseitissupposedtomimickatransistor.

=

= Inadditionweneedtorepresentterminalsfortheedgeofthechipasaspecialkindofnodewithonlyoneedge.NotethattheattributesaresimilartotherstattributesofTransistor,sowecanusethesamestruct.Onlythepointersourcewillbeused,sinceaterminalisonlyattachedtoonenet.

=

typedefstruct char char struct int double int char int struct struct

^xpos,ypos;partition;traversed,change;name[STRLEN];PNTtype;placed;clusterwidth,length;edgenodenodesource,next,cluster;^f previous;gate,drain;

gNode;

= Anedgeisconnectedtoanotknownnumberofnodessincewearedealingwithhypergraphs.Werepresentthisasalistofedgeelems.

=

typedefstruct

Node

struct

nodeinlist;edgeelemedgeelemnextelem;^f

gEdgeElem;

typedefstruct char

EdgeElemname[STRLEN];edgerstelem;^f

VedleggA:Cluster

int

^size;

struct

edgenext,previous;

gEdge;

= Actualdenitionaftheglobalvariables.ThestartpointsforthedoublylinkedlistsofNodesandEdges.

=

Nodestartnode;

Edgestartedge;

int

numberofnodes,numberofedges;

= Someusefulfuntionsforinitialization,insertion,updatingandsearching. ⁼

extern

NodeInitializeNode(

char

name,

char

PNTtype);

externvoid

RInsertNode(Noden,Node start);

extern

EdgeInitializeEdge(

char

name);

externvoid

InsertEdge(Edgee,Edge start);

externvoid

MakePointerToNode(Edgee,Noden);

extern

NodeGetEdgeNode(Edgee,

int

num);

externvoid

SetType(Noden,

char

t);

extern

^{NodeFindNode(}

char

^{name,Nodestart);}

extern

EdgeFindEdge(

char

name,Edgestart);

externint

CountNodes(Nodestart);

externint

CountEdges(Edgestart);

externvoid

PrintAllNodes(Nodestart);

externvoid

PrintAllEdges(Edgestart);

externvoid

PrintStatistics(Nodestartnode,Edgestartedge);

externvoid

CopyStructure(NodeEdgeoldnode,Edgenewedge);oldedge,Node newnode,

externvoid

MergeStructures(NodeNodesourcenode,Edgedestnode,Edgesourceedge,destedge);

externvoid

AddNamesForNodes(

char

ext,Nodestart);

externvoid

AddNamesForEdges(

char

ext,Edgestart);

externint

ChangeEdgeNames(

char

old,

char

new,Edgestart);

externvoid

DeleteNodes(Noden);

externvoid

RemoveEdge(Edgee,Edge start);

externvoid

DeleteEdges(Edgee);

externvoid

DeleteStructure(Noden,Edgee);

= Weneedseveralwaystorememberwhichnodeswewanttoassociatewithwhichothernodes,sowemakeageneralnodeliststructure.⁼

typedefstruct

Node

struct

nodepointer;nodelistnodelistnext;^f

gNodeList;

datastruct.h

extern

NodeListInitializeNodeList(Noden);

externvoid

InsertNodeList(NodeListnl,NodeList start);

extern

NodeListFindNodeList(Noden,NodeListstart);

externvoid

DeleteNodeList(NodeListnl);

#endif

VedleggA:Cluster

datastruct.c

#include"datastruct.h"

#include^<stdlib.h^>

#include^<stdio.h^>

#include^<ctype.h^>

#include^<string.h^>

NodeInitializeNode(

char

name,

char

PNTtype)

f Node

if

(!n)perror(exit(1);^fn=(Node"malloc")malloc();

sizeof

(Node));

gstrcpy(n^!name,name);

n^!PNTtype=PNTtype;

n^!cluster=NULL;

n^!xpos=-10000;

n^!ypos=-10000;

n^!width=0;

n^!length=0;

n^!partition=-1;

n^!placed='E';

n^!traversed=0;

n^!change=0;

n^!source=NULL;

n^!gate=NULL;

n^!drain=NULL;

n^!next=NULL;

n^!previous=NULL;

return

^n;

g

void

RInsertNode(Noden,Node start)

f

=ThenodeisinsertedatarandompositioninthelistINVARIANT:nhasNULLpointerforpreviousandnext.⁼

Nodenp;

int

i,num=0,pos;

if

(!start)

start=n;

else

^f

for

i=RANDMAXi

while

^=(np=num++;num;((pos=rand())start;np;np=np⁼num;i) ^!next)

datastruct.c

continue

^;

pos%=num;

if

(pos==0)n(^!start)next=^!fprevious=n;start;

start=n;

g

else

_np=^f

start;

for

(i=0;inp=np^<!pos-1;i++)next;

n^!next=np^!next;

n^!previous=np;

np^!next=n;

g

g

g

EdgeInitializeEdge(

char

name)

f Edge

if

(!e)perror(exit(1);^fe=(Edge"malloc")malloc();

sizeof

(Edge));

gstrcpy(e^!name,name);

e^!rstelem=NULL;

e^!size=0;

e^!next=NULL;

e^!previous=NULL;

return

e;

g

void

InsertEdge(Edgee,Edge start)

f

= TheedgeisinsertedatthestartofthelistINVARIANT:ehasNULLpointerforpreviousandnext. ⁼

if

(start)e(^!start)next=^{f !}previous=e;start;

start=e;

g

else

start=e;

g

void

MakePointerToNode(Edgee,Noden)

f

= INVARIANT:thelastedgeeleminalistpointstoNULLinsertanewedgeeleminthelist ⁼

VedleggA:Cluster

EdgeElemee=(EdgeElem)malloc(

sizeof

(EdgeElem));

if

(!ee)perror(exit(1);^f "malloc");

gee^!nodeinlist=n;

ee^!nextelem=e^!rstelem;

e^!rstelem=ee;

e^!size+=1;

g

NodeGetEdgeNode(Edgee,

int

num)

f

=num⁼0willreturntherstelementinthelist. ⁼

EdgeElemel=e^!rstelem;

while

el=el(num--)^!nextelem;

return

el^!nodeinlist;

g

void

SetType(Noden,

char

t)

f n^!PNTtype=(islower(t)?t+'A'-'a':t);

g

NodeFindNode(

char

name,Nodestart)

f Node

int while

found=0;

if else

(n&&!found)n=start;(strcmp(nfound=1;_n=n^!name,name)==0)^f

!next;

g

return

n;

g

EdgeFindEdge(

char

name,Edgestart)

f Edge

int while

found=0;

if else

(e&&!found)e=start;^(strcmp(efound=1;_e=e^!name,name)==0)^f

!next;

g

datastruct.c

return

^e;

g

int

CountNodes(Nodestart)

f Node

int while

^num=0;num++;n=n(n)n=start;^f!next;

g

return

num;

g

int

CountEdges(Edgestart)

f Edge

int while

num=0;num++;e=e(e)e=start;^f!next;

g

return

^num;

g

void

PrintAllNodes(Nodestart)

f Node

while

printf((n)n=start;^f"Node%shastype:%c.ⁿnSize:width:%glength:

%gandpositionx⁼%dy⁼%d.ⁿnItbelongstopartition%d.ⁿn", n^!name,n

if if if

printf(n=n^!(n(n(nPNTtype,n^!!!printf(printf(printf(^!"source)gate)drain)next;ⁿⁿⁿ"Sourceis%s.""Gateis%s.""Drainis%s."^n");^!width,n^!length,n,n,n^!!,ndrain^!gate^!xpos,nsource^!!name);name);^!!ypos,nname);^!partition);

g

g

void

PrintAllEdges(Edgestart)

f EdgeEdgeElem

while

(e)e=start;^fel;

VedleggA:Cluster

printf("Edge%sisconnectedtothese%dnodes:",e^!name, e^!size);el=e

while

printf(el=el^!(el)rstelem;^f!"%s"nextelem;,el^!nodeinlist^!name);

gprintf(^".nn");

e=e^!next;

g

g

void

PrintStatistics(Nodestartnode,Edgestartedge)

f NodeEdgeEdgeElem

int int int int int int int for for

PandNn=0;total=0,num=0,i,numT=0,numP=0,numN=0;hist[numberofnodes],onlyPnet[numberofnodes];onlyNnet[numberofnodes],onlyTnet[numberofnodes];PandTnet[numberofnodes],NandTnet[numberofnodes];PandNnet[numberofnodes],PandNandTnet[numberofnodes];histn=0,onlyPn=0,onlyNn=0,onlyTn=0,PandTn=0,NandTn=0,PandNandTn=0;(i=0;i(e=startedge;e;e=ehist[i]=onlyPnet[i]=onlyNnet[i]=onlyTnet[i]=PandTnet[i]=

if if

total+=enum++;hist[enumP=numN=numT=0;

for

e;n=startnode;(strcmp(e^(strcmp(eNandTnet[i]=PandNnet[i]=PandNandTnet[i]=0;^(el=eprintf(printf(

if if if

^!<(el(el(elel;size]++;numberofnodes;i++)^!!!!numP++;numN++;numT++;^!"vdd:%dnoder"vgnd:%dnoder^!!size;nodeinlistnodeinlistnodeinlistrstelem;el;el=elname,^name,"vdd""vgnd"^!!!!next)PNTtype=='P'&&!numP)PNTtype=='N'&&!numN)PNTtype=='T'&&!numT))==0)^f)==0)^!nn"ⁿnextelem)n",e,e^!!size);size);^f

g

if

(numP)

if

(numN)

if

(numT)

datastruct.c

PandNandTnet[e^!size]++;

else

_PandNnet[e

!size]++;

elseif

PandTnet[e(numT) ^!size]++;

else

_onlyPnet[e

!size]++;

elseif if

(numN)(numT)NandTnet[e^{f !}size]++;

g

else

_onlyNnet[e

!size]++;

elseif

_onlyTnet[e^(numT)

!size]++;

else

_printf("Error:Netwithnonodes:%sⁿn",e^!name);

g

if

(numprintf(⁶⁼numberofedges)"Internalerror:numberofedges⁼%dandactual numbeis%d.ⁿnumberofedges,num);n",

printf("NET-STATISTICSⁿnⁿn");

printf("SizeonlyPonlyNonlyTPandTNandTPandNP,NandT TOTAL

for

ⁿn"(i=0;i

if

);(hist[i])printf(PandNandTn+=PandNandTnet[i];PandNn+=PandNnet[i];NandTn+=NandTnet[i];PandTn+=PandTnet[i];onlyTn+=onlyTnet[i];onlyNn+=onlyNnet[i];onlyPn+=onlyPnet[i];histn+=hist[i];^<numberofnodes;i++)^f"%8d%8d%8d%8d%8d%8d%8d%8d%8donlyNnet[i],onlyTnet[i],PandTnet[i],NandTnet[i],PandNnet[i],PandNandTnet[i],hist[i]);ⁿn",i,onlyPnet[i],

printf(g"--- ---printf("SUMMARY:%8d%8d%8d%8d%8d%8d%8d%8dⁿn"); ⁿnⁿn",onlyPn,onlyNn, onlyTn, PandTn,NandTn,PandNn,PandNandTn,histn);

printf("Averagesizeofanetis%g.ⁿnⁿn",(

double

)total⁼(

double

) num);numP=numN=numT=0;

VedleggA:Cluster

while if elseif elseif else

⁽ⁿ⁾(n^!fnumT++;numP++;numN++;_printf(PNTtype=='T')(n(n^!!PNTtype=='P')PNTtype=='N')"Internalerror:PrintStatistics:unknownnode

type.ⁿn");n=n^!next;

g

if

((numT+numP+numN)printf("Internalerror:numberofnodes⁶⁼numberofnodes) ⁼%dandactual numberis%d.printf("%dterminalsnumberofnodes,num);ⁿn", ⁺ %dPtransistors⁺ %dNtransistor⁼

%dnodes.ⁿnumT,numP,numN,numberofnodes);nⁿn",

g

void

CopyStructure(NodeEdgeoldnode,Edgenewedge)oldedge,Node newnode,

f NodeEdgee1;n1,n2;

newnode=NULL;

newedge=NULL;

=Copythenodesrst ⁼

n1=oldnode;

while

n2=InitializeNode(n1n2n2n2n2n2n2n2n2n2RInsertNode(n2,newnode);n1=n1(n1)^!!!!!!!!!cluster=n1xpos=n1ypos=n1width=n1length=n1partition=n1placed=n1traversed=n1change=n1^f!next;^!!!!!!!xpos;ypos;width;^!length;placed;cluster;^!change;partition;traversed;^!name,n1^!PNTtype);

g

=Thencopytheedges⁼

e1=oldedge;

while

InsertEdge(InitializeEdge(e1(e1)^{f !}name),newedge);

datastruct.c

e1=e1^!next;

g

= Andlastwecopytheconnectionsbetweennodesandedges⁼

n2=newnode;

while if

(n2)((n1=FindNode(n2

if

^f((e1=FindEdge(n1n2MakePointerToNode(e1,n2);^!source=e1;^!name,oldnode)))^!source^!name,^f newedge)))^f

g

else

_printf("Node%scouldnotfindnet%sfor source.ⁿn",

if

((e1=FindEdge(n1n2MakePointerToNode(e1,n2);^!gate=e1;n1^!name,n1^!gate^!!sourcename,^!newedge)))name); ^f

g

else

_printf("Node%scouldnotfindnet%sforgate.n1^!name,n1^!gate^!name); ⁿn",

if

((e1=FindEdge(n1n2MakePointerToNode(e1,n2);^!drain=e1;^!drain^!name,newedge)))^f

g

else

_printf("Node%scouldnotfindnet%sfor drain.ⁿn", n1^!name,n1^!drain^!name);

g

else

_printf("Internalerror,cannotfindnode%sinold structure.n2=n2ⁿn"^!, n2next;^!name);

g

g

void

MergeStructures(NodeNodesourcenode,Edgedestnode,Edgesourceedge,destedge)

f NodeEdgeEdgeEleme1,n1=sourcenode,e2;el1; n2;

= randomlyintodestnode.Putsallnodesintoonebiglist.Wemergenodesfromsourcenode⁼

if

(!destnode)

destnode=sourcenode;

elsewhile

_n2=n1;^(n1)f

n1=n1^!next;

VedleggA:Cluster

n2^!next=NULL;

n2^!previous=NULL;

RInsertNode(n2,destnode);

g

=oneofthemandresolvesallpointerstoandfromnodes.Thenonebiglistiscreated,andwethrowawaytheoldedge.Checksifanedgeispresentinbothstructures,andifitisremoves⁼

e1=sourceedge;

while if

(e1)((e2=FindEdge(e1el1=e1

while

^f _n1=el1^(el1)!rstelem;^{f !}name,destedge)))^f

!nodeinlist;

MakePointerToNode(e2,n1);

if

(n1n1^!!source==e1)source=e2;

elseif

n1(n1^!!gate=e2;gate==e1)

elseif

n1(n1^!!drain=e2;drain==e1)

else

_printf("Internalerrorindatastructure.ⁿn");

el1=el1^!nextelem;

ge2=e1;

e1=e1^!next;

free(e2);

g

else

_e2=e1;^f

e1=e1^!next;

e2^!next=NULL;

e2^!previous=NULL;

InsertEdge(e2,destedge);

g

g

g

void

AddNamesForNodes(

char

ext,Nodestart)

f Node

while

strcat(nstrcat(nn=n(n)n=start;^f!!!next;name,name,ext);^"");

g

g

datastruct.c

void

AddNamesForEdges(

char

^{ext,Edgestart)}

f

= thesearespecialglobalnames.ThesetestsaredoneinMakeNamewhenwedothereading,butwedothemjusttobesureNOTE:Ifthenameis'vdd'or'vgnd'itisnotchanged,because ⁼

Edgee=start;

while if

^(e)(strcmp(e^fstrcpy(e^!!name,name,"vss""vgnd")==0); ^{j j}strcmp(e^!name,"gnd")==0)^f

g

elseif

strcat(estrcat(e(strcmp(e^!!strcmp(ename,name,ext);^!name,^""!name,);"vdd""vgnd")⁶⁼0&&)⁶⁼0)^f

ge=e^!next;

g

g

int

ChangeEdgeNames(

char

old,

char

new,Edgestart)

f Edge

int

changed=0;e=start;

while if

(e&&!changed)(strcmp(old,estrcpy(echanged=1;^!name,new);^!name)==0)^{f f}

ge=e^!next;

g

return

changed;

g

void

DeleteNodes(Noden)

f

if

(n)DeleteNodes(n^!next);

elsereturn

^;

free(n);

g

void

DeleteEdgeElems(EdgeElemel)

f

if

(el)DeleteEdgeElems(el^!nextelem);

elsereturn

;

VedleggA:Cluster

free(el);

g

void

RemoveEdge(Edgee,Edge start)

f

if

(e==start)^f

start=e^!next;

(start)^!previous=NULL;

g

else

_e^f

!next^!previous=e^!previous;

e^!previous^!next=e^!next;

gfree(e);

g

void

DeleteEdges(Edgee)

f

if

(e)DeleteEdgeElems(eDeleteEdges(e^{f !}next);^!rstelem);

g

elsereturn

^;

free(e);

g

void

DeleteStructure(Noden,Edgee)

f DeleteNodes(n);DeleteEdges(e);

g

= Functionstooperateonnodelists.⁼

NodeListInitializeNodeList(Noden)

f NodeList

if

(!nl)perror(exit(1);^f nl=(NodeList"malloc");)malloc(

sizeof

(NodeList));

gnl^!nodepointer=n;

nl^!next=NULL;

return

nl;

g

void

InsertNodeList(NodeListnl,NodeListstart)

f

if

(start)^f

datastruct.c

nl^!next=start;

start=nl;

g

else

start=nl;

g

NodeListFindNodeList(Noden,NodeListstart)

f NodeList

int while

found=0;

if else

(nl&&!found)(nl^!found=1;_nl=nlnl=start;nodepointer==n)^f

!next;

g

return

nl;

g

void

DeleteNodeList(NodeListnl)

f

if

(nl)DeleteNodeList(nl^!next);

elsereturn

; free(nl);

g

VedleggA:Cluster

datastruct.h

#ifndefCLUSTERH

#defineCLUSTERH

#include"datastruct.h"

= Datastructuretokeepalistof"clusters"{nodesthatttogether.⁼

#defineMAXCLUSTERSIZE5

#defineNCLUSTERS32

#definePCLUSTERS32

typedefstruct

NodeList

int char struct int struct

^size;traversed;type;cluster^clusternodes;clustersameneigh,^next;f otherneigh;

gCluster;

extern

ClusterInitializeCluster();

externvoid

InsertCluster(Clusterc,Clusterstart);

extern

ClusterFindClusterForNode(Noden,Clusterstart);

externvoid

MergeClusters(Clusterc1,Clusterc2,Clusterc);

externint

ExternalNets(Clusterc);

externvoid

PrintAllClusters(Clusterc);

externvoid

PrintClusterStatistics(Clusterc);

externvoid

DeleteClusters(Clusterc);

#endif

datastruct.c

datastruct.c

#include"^cluster.h"

#include"datastruct.h"

#include^<stdlib.h^>

#include^<stdio.h^>

= Somefunctionsforoperationsonaclusterstructure.⁼

ClusterInitializeCluster()

f Cluster

if

^(!c)_perror(exit(1);^fc=(Cluster"malloc")malloc();

sizeof

(Cluster));

gc^!nodes=NULL;

c^!size=0;

c^!type='E';

c^!sameneigh=NULL;

c^!otherneigh=NULL;

c^!traversed=FALSE;

c^!next=NULL;

return

c;

g

void

InsertCluster(Clusterc,Cluster start)

f

if

(start)c^!next=^f start;

start=c;

g

else

start=c;

g

ClusterFindClusterForNode(Noden,Clusterstart)

f ClusterNodeList

int while

found=0;nl=c

while

(c&&!found)c=start;

if else

^!nl;(nl&&!found)^(nlnodes;^!found=1;_nl=nlnodepointer==n)^{f f}

!next;

g

VedleggA:Cluster

if

^(!found)_c=c

!next;

g

return

c;

g

void

MergeClusters(Clusterc1,Clusterc2,Clusterc)

f NodeListnl=c1

while

nlnl=nl(nl^!!!nodepointernodes;nl;next)^!next;^{f !}cluster=c2;

gnl^!nodepointer^!cluster=c2;

nl^!next=c2^!nodes;

c2^!nodes=c1^!nodes;

c2^!size+=c1^!size;

if

(c2c2^!!type=='T')type=c1^!type;

if

((c)==c1)(c)=c1^!next;

else

^f_c2=(

c);

while

c2=c2(c2^!next^!next;⁶⁼c1) c2^!next=c1^!next;

gfree(c1);

g

int

ExternalNets(Clusterc)

f Edge

int

NodeListNode

int for

edges[numberofedges];nedges=0,i,external=0;(i=0;ie[i]=NULL;edges[i]=0;e[numberofedges];np;nlt;^<numberofedges;i++)^f

g

for

^(nlt=cnp=nlt

for

(i=0;i

if

^!(np^!nodes;nlt;nlt=nlt

break

nodepointer;^!<source==e[i])nedges;i++); ^!next)^f

datastruct.c

if

(i==nedges)e[nedges++]=np^!source;

edges[i]++;

if

(np

for if

edges[i]++;

for if

edges[i]++;^!(i==nedges)(i==nedges)PNTtype(i=0;i(i=0;i

if

e[nedges++]=np

if

e[nedges++]=np(np(np

break break

^!!<<6=gate==e[i])drain==e[i])nedges;i++)nedges;i++)'T')^{;; f !!}gate;drain;

g

g

for

(i=0;i

if

(edges[i]external++;^<nedges;i++)^<e[i]^!size)

return

external;

g

void

PrintAllClusters(Clusterc)

f ClusterNodeList

while

nlt=cltprintf(

while

(clt)clt=c;printf(nlt=nltnlt;^f"Clusterconsistsof"(nlt)^!nodes;^f"%s"^!next;,nlt^!nodepointer^!);name);

gprintf(^"nn");

clt=clt^!next;

g

g

void

PrintClusterStatistics(Clusterc)

f ClusterNodeListNode

int int

total=0,num=0,i=0,numT=0,numP=0,numN=0;hist[numberofnodes],onlyPnet[numberofnodes],onlyNnet[numberofnodes];n;clt;nlt;

VedleggA:Cluster

int

PandTnet[numberofnodes],NandTnet[numberofnodes];

int

sameneighbourhist[3]=

f0,0,0^g;

int

otherneighbourhist[3]=

f0,0,0^g;

int

histn=0,onlyPn=0,onlyNn=0,PandTn=0,NandTn=0;

Edgee[numberofedges];

int

edges[numberofedges],edgehist[numberofedges];

int

nedges,numedges,totaledges=0;

for

(i=0;ihist[i]=onlyPnet[i]=onlyNnet[i]=PandTnet[i]=NandTnet[i]=0;^<numberofnodes;i++)

for

^(i=0;iedgehist[i]=0;^<numberofedges;i++)

for

(clt=c;clt;clt=cltnum=numT=numP=numN=numedges=0;

for

(i=0;ie[i]=NULL;edges[i]=0;^<numberofedges;i++)^!next)^{f f}

gnedges=0;

for

(nlt=cltnum++;n=nlt

if if if for if

edges[i]++;

if

(n(n(n(i==nedges)(n(i=0;i^!!!!numP++;numN++;numT++;

if

e[nedges++]=n

for if

edges[i]++;

for

^!PNTtype=='P'&&!numP)PNTtype=='N'&&!numN)PNTtype=='T'&&!numT)PNTtype(n(i==nedges)^!(i=0;i(i=0;inodepointer;^!nodes;nlt;nlt=nlt

break if

e[nedges++]=n

if

source==e[i])^<(n(n^!!nedges;i++)

break break

;⁶⁼gate==e[i])drain==e[i])^<<'T')nedges;i++)nedges;i++);;^!fsource;^!!gate;next)^f