Graphs0Impl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Created by: Christian Jacobi, September 15, 1986 11:07:56 am PDT
Last edited by: Christian Jacobi, September 29, 1986 11:39:08 am PDT
DIRECTORY Graphs0, Process, PropertyLists, Random, RefTab, SafeStorage;
Graphs0Impl: CEDAR MONITOR
IMPORTS Process, Random, RefTab, SafeStorage
EXPORTS Graphs0 =
BEGIN OPEN Graphs0;
GraphPrivateRep: PUBLIC TYPE = RECORD [nodes: RefTab.Ref];
Create: PUBLIC PROC [graphInfo: REF ← NIL] RETURNS [graph: Graph] = {
graph ← NEW[Graphs0.GraphRec←[
graphInfo: graphInfo,
graphPrivate: NEW[GraphPrivateRep←[nodes: RefTab.Create[]]]
]];
SafeStorage.EnableFinalization[graph];
};
CreateNode: PUBLIC PROC [nodeInfo: REF ← NIL] RETURNS [node: Node] = {
node ← NEW[NodeRec←[nodeInfo: nodeInfo]]
};
IncludeNode: PUBLIC PROC [graph: Graph, node: Node] = {
IF node.incl THEN ERROR;
node.incl ← TRUE;
IF ~RefTab.Insert[graph.graphPrivate.nodes, node, $TRUE] THEN ERROR
};
InternalRemArc: PROC [node: Node, arc: Arc] = {
--removes arc from a nodes list of arcs
IF node.arcs=NIL THEN ERROR;
IF node.arcs.first=arc THEN node.arcs ← node.arcs.rest
ELSE {
FOR list: ArcList ← node.arcs, list.rest WHILE list.rest#NIL DO
IF list.rest.first=arc THEN {list.rest ← list.rest.rest; RETURN};
ENDLOOP;
ERROR --arc was not member of nodes arc list
}
};
RemoveNode: PUBLIC PROC [graph: Graph, node: Node] RETURNS [removedArcs: ArcList] = {
IF ~node.incl THEN ERROR;
node.incl ← FALSE;
IF ~RefTab.Delete[graph.graphPrivate.nodes, node] THEN ERROR;
removedArcs ← node.arcs;
FOR list: ArcList ← node.arcs, list.rest WHILE list#NIL DO
IF list.first.node1#node THEN InternalRemArc[list.first.node1, list.first];
IF list.first.node2#node THEN InternalRemArc[list.first.node2, list.first];
ENDLOOP;
};
AddNewNode: PUBLIC PROC [graph: Graph, nodeInfo: REF ← NIL] RETURNS [node: Node] = {
node ← CreateNode[nodeInfo];
IncludeNode[graph, node]
};
CreateArc: PUBLIC PROC [arcInfo: REF ← NIL] RETURNS [arc: Arc] = {
arc ← NEW[ArcRec←[arcInfo: arcInfo]]
};
IncludeArc: PUBLIC PROC [graph: Graph, arc: Arc, node1, node2: Node] = {
IF arc.incl OR ~node1.incl OR ~node2.incl THEN ERROR; --implicite nil test for nodes
arc.incl ← TRUE;
arc.node1 ← node1;
arc.node2 ← node2; 
node1.arcs ← CONS[arc, node1.arcs];
node2.arcs ← CONS[arc, node2.arcs];
};
RemoveArc: PUBLIC PROC [graph: Graph, arc: Arc] = {
IF ~arc.incl OR ~arc.node1.incl OR ~arc.node2.incl THEN ERROR;
arc.incl ← FALSE;
InternalRemArc[arc.node1, arc];
InternalRemArc[arc.node2, arc];
};
AddNewArc: PUBLIC PROC [graph: Graph, arcInfo: REF ← NIL, node1, node2: Node] RETURNS [arc: Arc] = {
arc ← CreateArc[arcInfo];
IncludeArc[graph, arc, node1, node2];
};
EnumNodes: PUBLIC PROC [graph: Graph, enumNode: EnumNodeProc, data: REF←NIL] RETURNS [quit: BOOL ← FALSE] = {
Each: RefTab.EachPairAction = {quit ← enumNode[graph, NARROW[key], data]};
quit ← RefTab.Pairs[graph.graphPrivate.nodes, Each]
};
EnumArcs: PUBLIC PROC [graph: Graph, enumArc: EnumArcProc, data: REF←NIL] RETURNS [quit: BOOL ← FALSE] = {
checkTab: RefTab.Ref ← RefTab.Create[RefTab.GetSize[graph.graphPrivate.nodes]];
EachNode: EnumNodeProc = {
FOR list: ArcList ← node.arcs, list.rest WHILE list#NIL DO
IF RefTab.Insert[checkTab, list.first, $TRUE] THEN
IF enumArc[graph, list.first, data].quit THEN RETURN [quit←TRUE]
ENDLOOP
};
quit ← EnumNodes[graph, EachNode, data];
};
HasNode: PUBLIC PROC [graph: Graph, node: Node] RETURNS [BOOL] = {
IF ~node.incl THEN RETURN [graph=NIL];
RETURN [RefTab.Fetch[graph.graphPrivate.nodes, node].found]
};
HasArc: PUBLIC PROC [graph: Graph, arc: Arc] RETURNS [yes: BOOL] = {
IF ~arc.incl THEN RETURN [graph=NIL];
yes ← HasNode[graph, arc.node1];
IF yes#HasNode[graph, arc.node2] THEN ERROR;
};
Check: PUBLIC PROC [graph: Graph] = {
EachNode: EnumNodeProc = {
IF ~node.incl THEN ERROR;
FOR list: ArcList ← node.arcs, list.rest WHILE list#NIL DO
IF ~HasArc[graph, list.first] THEN ERROR;
IF ~(list.first.node1=node OR list.first.node2=node) THEN ERROR;
IF ~HasNode[graph, list.first.node1] THEN ERROR;
IF ~HasNode[graph, list.first.node2] THEN ERROR;
ENDLOOP
};
[] ← EnumNodes[graph, EachNode, NIL]
};
NodesInGraph: PUBLIC PROC [graph: Graph] RETURNS [INT] = {
RETURN [RefTab.GetSize[graph.graphPrivate.nodes]]
};
ArcListLength: PROC [al: ArcList] RETURNS [i: INT𡤀] = {
WHILE al#NIL DO al𡤊l.rest; i←i+1 ENDLOOP
};
ArcsInGraph: PUBLIC PROC [graph: Graph] RETURNS [n: INT𡤀] = {
EachNode: EnumNodeProc = {
n ← n+ArcListLength[node.arcs];
};
[] ← EnumNodes[graph, EachNode, NIL];
n ← n/2
};
RandomShuffle: PUBLIC PROC [graph: Graph, randomStream: REF] = {
rs: Random.RandomStream ← NARROW[randomStream];
EachNode: EnumNodeProc = {
--goal: O(Num(arcs)), but don't care about optimal shuffling
--in global routing typical node has 4 or less arcs
num: INT = 6;
a: ARRAY [0..num) OF ArcList ← ALL[NIL];
--split list randomly into num lists
FOR l: ArcList ← node.arcs, l.rest WHILE l#NIL DO
n: INT ← Random.ChooseInt[rs, 0, num-1];
a[n] ← CONS[l.first, a[n]];
ENDLOOP;
--merge the num lists
FOR i: INT DECREASING IN [1..num) DO
n: INT ← Random.ChooseInt[rs, 1, i];
FOR l: ArcList ← a[n], l.rest WHILE l#NIL DO
a[0] ← CONS[l.first, a[0]];
ENDLOOP;
a[n] ← a[i]
ENDLOOP;
node.arcs ← a[0];
};
[] ← EnumNodes[graph, EachNode, NIL]
};
Destroy: PUBLIC PROC [graph: Graph] = {
EachNode: EnumNodeProc = {
node.nodeInfo ← $DELETED;
node.props ← NIL;
FOR list: ArcList ← node.arcs, list.rest WHILE list#NIL DO
list.first.arcInfo ← $DELETED;
list.first.props ← NIL;
list.first.node1 ← list.first.node2 ← NIL;
ENDLOOP;
node.arcs ← NIL;
};
[] ← EnumNodes[graph, EachNode];
graph.graphInfo ← $DELETED;
graph.props ← NIL;
graph.graphPrivate ← NIL;
};
FinalizerProcess: PROC[fooFQ: SafeStorage.FinalizationQueue] = {
DO
Destroy[NARROW[SafeStorage.FQNext[fooFQ]]];
ENDLOOP
};
fooFQ: SafeStorage.FinalizationQueue = SafeStorage.NewFQ[];
SafeStorage.EstablishFinalization[CODE[Graphs0.GraphRec], 0, fooFQ];
TRUSTED {Process.Detach[FORK FinalizerProcess[fooFQ]]};
END.