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.