DrotBoolImpl.mesa
Copyright Ó 1987 by Xerox Corporation. All rights reserved.
Csaba Gabor August 19, 1987 10:32:35 pm PDT
Bertrand Serlet August 21, 1987 4:15:29 pm PDT
DIRECTORY
Rope, DrotBool;
DrotBoolImpl: CEDAR MONITOR
IMPORTS Rope
EXPORTS DrotBool
~ BEGIN OPEN DrotBool;
Linear Ordering Of Trees
--Dags have two types of ordering here. The first is the conventional one where each node may have children and parents. However, to make the data structure more manageable the nodes are kept on a circularly linked list and in this sense have a 'linear order.' To visit each node for example one may percolate around the nodes in a depth first search (after finding the sources, of course) or one may just go from one to the next in linear order.
PlaceAtEnd: PUBLIC PROC [tree: Dag, vertex: Node] ~ {
Takes a vertex in tree and causes that vertex to be the last in linear order in the tree --
IF vertex.next # NIL THEN --No action in an empty tree
IF tree.csucs = vertex --If vertex is the first element
THEN {
vertex.prev.next ← vertex;
tree.csucs ← vertex.next;
vertex.next ← NIL
}
ELSE {
tree.csucs.prev.next ← vertex;
vertex.next.prev ← vertex.prev;
vertex.prev.next ← vertex.next;
vertex.prev ← tree.csucs.prev;
tree.csucs.prev ← vertex;
vertex.next ← NIL
};
};
PlaceAtBeg: PUBLIC PROC [tree: Dag, vertex: Node] ~ {
This takes vertex in tree and causes it to be the first in linear order in the tree --
IF vertex # tree.csucs THEN {
IF vertex.next = NIL --If vertex is the last element
THEN {
vertex.prev.next ← NIL
}
ELSE {
vertex.prev.next ← vertex.next;
vertex.next.prev ← vertex.prev;
vertex.prev ← tree.csucs.prev;
tree.csucs.prev ← vertex
};
vertex.next ← tree.csucs;
tree.csucs ← vertex}
};
PrimitivesToEnd: PUBLIC PROC [tree: Dag] ~ {
This takes all nodes which represent inputs (prims) and places them at the end (in linear order) of the tree.
IF tree # NIL AND tree.csucs # NIL THEN { --If the tree is not NIL
nonPrimEncountered : BOOLFALSE;
vertex : Node ← tree.csucs.prev;
WHILE vertex # tree.csucs DO
IF vertex.type = prim AND nonPrimEncountered
THEN {
temp: Node ← vertex.prev; --So we don't lose our place
PlaceAtEnd[tree, vertex];
vertex ← temp}
ELSE {
nonPrimEncountered ← (vertex.type # prim);
vertex ← vertex.prev}
ENDLOOP;
Now we have to take care of the last node
IF vertex.type = prim AND nonPrimEncountered THEN PlaceAtEnd[tree, vertex]}
};
OrphansToFront: PUBLIC PROC [tree: Dag] ~ {
This takes all nodes which have no parents and places them at the beginning (in linear order) of the tree --
IF tree # NIL AND tree.csucs # NIL THEN {
nonOrphanEncountered : BOOLFALSE;
iter: Node ← tree.csucs;
WHILE iter # NIL DO
IF iter.parnum = 0 AND nonOrphanEncountered
THEN {
temp: Node ← iter.next; --So we don't lose our place
PlaceAtBeg[tree, iter];
iter ← temp
}
ELSE {
nonOrphanEncountered ← (iter.parnum > 0);
iter ← iter.next}
ENDLOOP};
};
PlaceBefore: PUBLIC PROC [tree: Dag, before, after: Node] RETURNS[Node] ~ {
after stays fixed here. This procedure takes before and after in tree and causes before to be placed before after in linear order. If after = NIL then PlaceAtEnd[tree, before] is invoked. It really is consistent. This will fail if before = NIL. Returns before.next. Thus, unless before = after it will return after. --
IF after = NIL
THEN PlaceAtEnd[tree, before]
ELSE IF before # after AND (before.next # after) THEN
Think about it. That first line makes sense after all --
IF after = tree.csucs --if after is first in the tree
THEN {
tree.csucs ← before; --then before becomes the new first element
IF before.next = NIL --if before was at the end
THEN {
before.next ← after;
before.prev.next ← NIL
}
ELSE {
before.prev.next ← before.next;
before.next.prev ← before.prev;
before.prev ← after.prev;
before.next ← after;
after.prev ← before
};
}
ELSE {
IF before = tree.csucs --if before was at the front of the tree
THEN tree.csucs ← before.next
ELSE before.prev.next ← before.next;
IF before.next = NIL --if before was at the end of the tree
THEN tree.csucs.prev ← before.prev
ELSE before.next.prev ← before.prev;
before.next ← after;
before.prev ← after.prev;
after.prev.next ← before;
after.prev ← before
};
RETURN[before.next]
};
PlaceAfter: PUBLIC PROC[tree: Dag, before, after: Node] RETURNS[Node] ~ {
before stays fixed here. This procedure takes before and after in tree and causes after to be placed after before in linear order. If before = NIL then PlaceAtBeg[tree, after] is invoked. Will fail if after = NIL. Returns after.prev (or NIL if after = tree.csucs). --
IF before = NIL
THEN PlaceAtBeg[tree, after]
ELSE IF before # after AND (before.next # after) THEN
IF before.next = NIL --If before is at the end of the tree
THEN {
before.next ← after;
IF after = tree.csucs --If after is first in the tree
THEN {
tree.csucs ← after.next;
after.next ← NIL}
ELSE {
after.prev.next ← after.next;
after.next.prev ← after.prev;
tree.csucs.prev ← after;
after.next ← NIL;
after.prev ← before}}
ELSE {
IF after.next = NIL --If after is at the end of the tree
THEN tree.csucs.prev ← after.prev
ELSE after.next.prev ← after.prev;
IF after = tree.csucs --If after is at the head of the tree
THEN tree.csucs ← after.next
ELSE after.prev.next ← after.next;
after.prev ← before;
after.next ← before.next;
before.next.prev ← after;
before.next ← after};
IF after = tree.csucs
THEN RETURN[NIL]
ELSE RETURN[after.prev];
};
OrderNodesByPrims: PUBLIC PROC [tree: Dag] ~ {
Arranges tree so that considering linear order, each node's parents are greater than it. --
IF tree.csucs # NIL THEN {
PrimitivesToEnd[tree];
ClearScratch[tree];
We use the scratch field for counting the number of children already accessed
IF (tree.csucs.type # prim) AND (tree.csucs.prev.type = prim) THEN {
rear: Node ← tree.csucs.prev;
front: Node ← rear;
WHILE front.type = prim DO
front ← front.prev;
ENDLOOP;
We put a placeholder, front, at the head of all the processed nodes
front ← front.next;
WHILE front # tree.csucs DO --Main routine
pariter: Kidptr ← rear.parlist;
WHILE pariter # NIL DO --For each parent
pariter.child.scratch ← pariter.child.scratch + 1;
IF pariter.child.scratch = pariter.child.kidnum THEN {
KidptrToEnd[pariter.parlink, pariter.child];
I believe that the above line should go, but I haven't double checked yet. Should probably be redone to be like OrderNodesByOrphans
[] ← PlaceBefore[tree, pariter.child, front];
front ← pariter.child};
pariter ← pariter.next;
ENDLOOP;
rear ← rear.prev;
ENDLOOP}}
};
OrderNodesByOrphans: PUBLIC PROC [tree: Dag] ~ {
Arranges a tree so that if linear order is considered, each node's forward pointers point only to vertices less than it. --
IF tree.csucs # NIL THEN {
OrphansToFront[tree];
ClearScratch[tree];
We use the scratch field for counting the number of parents already accessed
IF (tree.csucs.parnum = 0) AND (tree.csucs.prev.parnum # 0) THEN {
front: Node ← tree.csucs;
rear: Node ← front;
WHILE rear.parnum = 0 DO
rear ← rear.next;
ENDLOOP;
We put a placeholder, rear, at the end of all the processed nodes
WHILE rear # NIL DO
kiditer: Kidptr ← front.kidlist;
WHILE kiditer # NIL DO
kiditer.child.scratch ← kiditer.child.scratch + 1;
IF kiditer.child.scratch = kiditer.child.parnum
THEN rear ← PlaceBefore[tree, kiditer.child, rear];
kiditer ← kiditer.next;
ENDLOOP;
front ← front.next;
ENDLOOP}}
};
Creating And Deleting Tree Parts
RemoveNode: PUBLIC PROC [tree: Dag, vertex: Node] ~ {
Completely removes a node from the tree, including any links it has --
kiter: Kidptr ← vertex.kidlist;
piter: Kidptr ← vertex.parlist;
WHILE kiter # NIL DO --Gets rid of the links with the Children
kiter ← KillCLink[kiter];
ENDLOOP;
WHILE piter # NIL DO --Gets rid of the links with the Parents
piter ← KillPLink[piter];
ENDLOOP;
IF vertex.brother # NIL THEN vertex.brother.brother ← NIL;
The next two statements remove the node from the circular list of the tree.
IF vertex.next = NIL
THEN tree.csucs.prev ← vertex.prev
ELSE vertex.next.prev ← vertex.prev;
IF vertex = tree.csucs
THEN tree.csucs ← vertex.next
ELSE vertex.prev.next ← vertex.next;
We want the tree to be numbered from 1 to tree.size
IF vertex.number < tree.size THEN {
iter: Node ← tree.csucs;
WHILE iter.number # tree.size DO
iter ← iter.next
ENDLOOP;
iter.number ← vertex.number};
tree.size ← tree.size - 1
};
MakeNewNodeA: PUBLIC PROC [tree: Dag, vertex: Node, type: Vtype ← prim, inname: ROPENIL, varname: ROPENIL, outname: LIST OF ROPENIL, output: BOOLFALSE] RETURNS[temp: Node] ~ {
This creates a new node placing it after vertex in linear order unless vertex = NIL in which case the created node becomes the head of the tree. tree must not be NIL. --
temp ← NEW[Noderec ← [type: type, inname: inname, varname: varname, outname: outname, output: output, number: tree.size + 1]];
IF tree.csucs = NIL THEN { --If the tree was empty
temp.prev ← temp;
tree.csucs ← temp}
ELSE IF vertex = NIL THEN { --If the new node is to be first in the tree
temp.prev ← tree.csucs.prev;
temp.next ← tree.csucs;
temp.next.prev ← temp;
tree.csucs ← temp}
ELSE {
temp.prev ← vertex;
temp.next ← vertex.next;
IF vertex.next = NIL
THEN tree.csucs.prev ← temp
ELSE vertex.next.prev ← temp;
vertex.next ← temp};
tree.size ← tree.size + 1
};
MakeNewNodeB: PUBLIC PROC [tree: Dag, vertex: Node, type: Vtype ← prim, inname: ROPENIL, varname: ROPENIL, outname: LIST OF ROPENIL, output: BOOLFALSE] RETURNS[temp: Node] ~ {
This creates a new node placing it before vertex in linear order unless vertex = NIL in which case the created node becomes the tail of the tree. tree must not be NIL. --
temp ← NEW[Noderec ← [type: type, inname: inname, varname: varname, outname: outname, output: output, number: tree.size + 1]];
IF tree.csucs = NIL THEN { --If the tree is empty
temp.prev ← temp;
tree.csucs ← temp}
ELSE IF vertex = NIL THEN { --If the new node is to be last in the tree (in linear order)
temp.prev ← tree.csucs.prev;
tree.csucs.prev ← temp;
temp.prev.next ← temp}
ELSE {
temp.next ← vertex;
temp.prev ← vertex.prev;
IF vertex = tree.csucs
THEN tree.csucs ← temp
ELSE vertex.prev.next ← temp;
vertex.prev ← temp};
tree.size ← tree.size + 1
};
MakeBrother: PUBLIC PROC [tree: Dag, vertex: Node] ~ {
Finds the negation of a node and creates it if it does not exist, in either case linking the two through the brother field. Currently not used.
IF vertex.brother = NIL THEN {
[] ← MakeNewNodeA[tree, vertex, NegNodeType[vertex.type], NegateVarName[vertex.inname]];
vertex.brother ← vertex.next;
vertex.brother.brother ← vertex}
};
KillCLink: PUBLIC PROC [link: Kidptr] RETURNS [Kidptr] ~ {
This expects as input some link to a child which it will delete.
kid: Node ← link.child; --This is the child
plink: Kidptr ← link.parlink; --This is the link from the child to the parent
par: Node ← plink.child; --The parent
par.kidnum ← par.kidnum - 1;
kid.parnum ← kid.parnum - 1;
IF link.next = NIL
THEN par.kidlist.prev ← link.prev
ELSE link.next.prev ← link.prev;
IF plink.next = NIL
THEN kid.parlist.prev ← plink.prev
ELSE plink.next.prev ← plink.prev;
IF link = par.kidlist
THEN par.kidlist ← link.next
ELSE link.prev.next ← link.next;
IF plink = kid.parlist
THEN kid.parlist ← plink.next
ELSE plink.prev.next ← plink.next;
RETURN[link.next]
};
KillPLink: PUBLIC PROC [plink: Kidptr] RETURNS [Kidptr] ~ {
This expects as input some link to a parent which link it will delete.
[] ← KillCLink[plink.parlink];
RETURN [plink.next]
};
MakeLink: PUBLIC PROC [par,gyerek: Node] ~ {
Makes a link from par (parent) to gyerek (child) (and the reciprocal link from gyerek to parent) in the tree containing them. Both links will be first in linear order --
temp: Kidptr;
par.kidlist ← NEW[Kidrec ← [child: gyerek, next: par.kidlist]];
gyerek.parlist ← NEW[Kidrec ← [child: par, next: gyerek.parlist, parlink: par.kidlist]];
par.kidlist.parlink ← gyerek.parlist;
temp ← par.kidlist;
IF temp.next = NIL
THEN
temp.prev ← temp
ELSE {
temp.prev ← temp.next.prev;
temp.next.prev ← temp};
temp ← gyerek.parlist;
IF temp.next = NIL
THEN
temp.prev ← temp
ELSE {
temp.prev ← temp.next.prev;
temp.next.prev ← temp};
par.kidnum ← par.kidnum + 1;
gyerek.parnum ← gyerek.parnum + 1
};
MakeLinkE: PUBLIC PROC [szulo, gyerek: Node] ~ {
This places the newly created link between szulo and gyerek at the end of their respective lists. Unfortunately, this is used in a few places where we are iterating through a list of links, creating some as we go along and then having to process the newly created links. See, for example, ProcessGndAndVdd.
tempk: Kidptr ← NEW[Kidrec ← [child: gyerek]];
tempp: Kidptr ← NEW[Kidrec ← [child: szulo, parlink: tempk]];
tempk.parlink ← tempp;
IF szulo.kidlist = NIL
THEN szulo.kidlist ← tempk
ELSE {
szulo.kidlist.prev.next ← tempk;
tempk.prev ← szulo.kidlist.prev};
szulo.kidlist.prev ← tempk;
IF gyerek.parlist = NIL
THEN gyerek.parlist ← tempp
ELSE {
gyerek.parlist.prev.next ← tempp;
tempp.prev ← gyerek.parlist.prev};
gyerek.parlist.prev ← tempp;
szulo.kidnum ← szulo.kidnum + 1;
gyerek.parnum ← gyerek.parnum + 1
};
RemoveLink: PUBLIC PROC [szulo, gyerek: Node] ~ {
Given two nodes, this finds the parent (szulo) - child (gyerek) link between them, if it exists, and removes it
temp: Kidptr ← ConnectionBetween[szulo,gyerek];
WHILE temp # NIL DO
[] ← KillCLink[temp];
temp ← ConnectionBetween[szulo,gyerek];
ENDLOOP;
};
Setting Values On All Nodes
EstablishLevels: PUBLIC PROC [tree: Dag] ~ {
This finds the real level of all nodes in a tree. Gates with large amounts of inputs will cause their children to have correspondingly higher levels. Ex. A 4-input and is really at least a 2-input and of two 2-input ands. Unfortunately, I have not fixed it up yet to ignore nots, but that should not be too difficult. On the bright side, this level information is not really being used currently, though eventually it should be.
ResetLevels[tree];
FOR iter: Node ← tree.csucs, iter.next UNTIL iter = NIL DO
IF iter.parnum = 0 THEN REstablishLevels[iter,1];
ENDLOOP;
};
ResetLevels: PROC [tree: Dag] ~ {
The the levelnumber of each node in the tree to 0
FOR iter: Node ← tree.csucs, iter.next UNTIL iter = NIL DO
iter.level ← 0;
ENDLOOP;
};
REstablishLevels: PROC [iter: Node, levelnum: INT] ~ {
This recursively establishes the level of all nodes in the subtree headed by iter. levelnum is the level at which this particular node (iter) is starting out.
IF iter # NIL AND levelnum > iter.level THEN {
IF iter.kidnum = 1
THEN REstablishLevels[iter.kidlist.child, levelnum + 1]
ELSE FOR kiditer: Kidptr ← iter.kidlist, kiditer.next UNTIL kiditer = NIL DO
REstablishLevels[kiditer.child, levelnum + CLogarythm[2,iter.kidnum]];
ENDLOOP;
iter.level ← levelnum}
};
CLogarythm: PUBLIC PROC [base, num: INT] RETURNS [INT] ~ {
Computes the ceiling function of log base base of num. This is a cute function; that's why it is public. Everyone should be encouraged to use cute functions. --
IF num = 1
THEN RETURN[0]
ELSE RETURN[1 + CLogarythm[base, (num + base -1)/base]]
};
ClearScratch: PUBLIC PROC [tree: Dag] ~ {
This sets the scratch field of every node in tree to 0. Used prior to tree searches for initialization --
FOR iter: Node ← tree.csucs, iter.next UNTIL iter = NIL DO
iter.scratch ← 0;
ENDLOOP;
};
Non Modifying Functions
NegNodeType: PUBLIC PROC [intype: Vtype] RETURNS [Vtype] ~ {
Returns the negative of any Vtype (the type of any node)
SELECT intype FROM
nand => RETURN[and];
and => RETURN[nand];
or => RETURN[nor];
nor => RETURN[or];
not => RETURN[buf];
buf => RETURN[not];
ENDCASE => RETURN[prim]; --Prims are not gates
};
NegateVarName: PUBLIC PROC [name: ROPE] RETURNS [ROPE] ~ {
Generates a name for the negation of a variable. This could be removed since it only affects internal names.
IF Rope.IsEmpty[name]
THEN RETURN[NIL]
ELSE IF Rope.Fetch[name,0] = '~
THEN RETURN[Rope.Substr[name,1,Rope.Length[name] - 1]]
ELSE RETURN[Rope.Concat["~", name]];
};
MergeListOfRopes: PUBLIC PROC [lista, listb: LIST OF ROPE] RETURNS [LIST OF ROPE] ~ {
Appends one list of ROPES to another. listb should be shorter, if possible.
IF listb = NIL THEN RETURN[lista]
ELSE RETURN[MergeListOfRopes[CONS[listb.first, lista], listb.rest]]
};
NotAbove: PUBLIC PROC [pariter: Kidptr] RETURNS [Node] ~ {
Given the parlist of a vertex this determines whether at least one of its parents is of type not. For practical purposes (fanout) it should eventually find that not parent with the least number of parents.
IF pariter = NIL
THEN RETURN[NIL]
ELSE IF pariter.child.type = not
THEN RETURN[pariter.child]
ELSE RETURN[NotAbove[pariter.next]]
};
NegativeOf: PUBLIC PROC [vertex: Node] RETURNS [negVertex: Node ← NIL] ~ {
Returns the negation of vertex, if it exists, else NIL. Currently, there is no check for the negations of XORs.
IF vertex # NIL THEN
IF vertex.brother # NIL THEN RETURN[vertex.brother]
ELSE IF vertex.type = not THEN RETURN[vertex.kidlist.child]
ELSE RETURN[NotAbove[vertex.parlist]];
};
ConnectionBetween: PUBLIC PROC [szulo, gyerek: Node] RETURNS [link: Kidptr ← NIL] ~ {
If szulo has gyerek as a child then the link between them is returned, otherwise NIL
FOR iter: Kidptr ← szulo.kidlist, iter.next UNTIL iter = NIL DO
IF iter.child = gyerek THEN RETURN[iter];
ENDLOOP;
};
FindExpressionByName: PUBLIC PROC [tree: Dag, name: ROPE] RETURNS [vertex: Node ← NIL] ~ {
Finds a node (if it exists) with the given name (searches the varname and outname fields)
FOR iter: Node ← tree.csucs, iter.next UNTIL iter = NIL DO
IF Rope.Equal[iter.varname,name] THEN RETURN[iter];
FOR nameiter: LIST OF ROPE ← iter.outname, nameiter.rest UNTIL nameiter = NIL DO
IF Rope.Equal[nameiter.first,name] THEN RETURN[iter];
ENDLOOP;
ENDLOOP;
};
FindInputByName: PUBLIC PROC [tree: Dag, name: ROPE] RETURNS [vertex: Node ← NIL] ~ {
Finds an input (prim) with the given name, if it exists
FOR iter: Node ← tree.csucs, iter.next UNTIL iter = NIL DO
IF iter.type = prim AND Rope.Equal[iter.inname,name] THEN RETURN[iter];
ENDLOOP;
};
FindNodeByName: PUBLIC PROC [tree: Dag, name: ROPE] RETURNS [vertex: Node] ~ {
Finds a node with the given name giving preference to inname, varname, outname in that order.
vertex ← FindInputByName[tree, name];
IF vertex # NIL
THEN RETURN[vertex]
ELSE RETURN[FindExpressionByName[tree, name]]
};
Tree Modifying Functions
ForwardSimilar: PUBLIC PROC [nodea, nodeb: Node] RETURNS [a: BOOLFALSE] ~ {
Compares whether the children of two nodes (inputs) are the same. Assumes order on the links. See RemoveDuplicateNodes. I think this code is archaic. It should be scrapped and IntersectionSize should be used in RemoveDuplicateNodes and elsewhere. --
IF nodea.kidnum = nodeb.kidnum
THEN RETURN[KidlistEqual[nodea.kidlist, nodeb.kidlist]]
};
KidlistEqual: PROC [kidlista, kidlistb: Kidptr] RETURNS [a: BOOL] ~ {
Assumes kidlista, kidlistb have the same number of elements. See ForwardSimilar --
iterb: Kidptr ← kidlistb;
FOR itera: Kidptr ← kidlista, itera.next DO
IF itera = NIL
THEN RETURN[TRUE]
ELSE IF itera.child # iterb.child
THEN RETURN[FALSE]
ELSE iterb ← iterb.next
ENDLOOP;
};
KidptrToEnd: PUBLIC PROC [kid: Kidptr, par: Node] ~ {
This places the specified link to the end of par's kidlist. kid must be in the kidlist of par. I'm unsure whether this is needed or even useful. --
IF kid.next # NIL THEN
IF par.kidlist = kid
THEN {
kid.prev.next ← kid;
par.kidlist ← kid.next;
kid.next ← NIL
}
ELSE {
par.kidlist.prev.next ← kid;
kid.next.prev ← kid.prev;
kid.prev.next ← kid.next;
kid.prev ← par.kidlist.prev;
par.kidlist.prev ← kid;
kid.next ← NIL
};
};
Negate: PUBLIC PROC [tree: Dag, vertex: Node] RETURNS [csucs: Node] ~ {
Given vertex in tree, this finds that node's complement, creating it if necessary. If the node has no parents then it will change the type of vertex appropriately. Thus, USE WITH CARE!
IF vertex.brother # NIL
THEN RETURN[vertex.brother]
ELSE IF vertex.type = not
THEN IF (vertex.parnum > 0) OR vertex.output
THEN RETURN[vertex.kidlist.child]
ELSE {
temp: Node ← vertex.kidlist.child;
RemoveNode[tree, vertex];
RETURN[temp]}
ELSE {
IF NotAbove[vertex.parlist] # NIL THEN RETURN[NotAbove[vertex.parlist]];
IF vertex.type # prim AND vertex.parnum = 0 AND NOT vertex.output THEN {
vertex.type ← NegNodeType[vertex.type];
RETURN[vertex]};
MakeLink[MakeNewNodeB[tree, vertex, not], vertex];
RETURN[vertex.prev]}
};
IntersectionSize: PUBLIC PROC [nagy, kicsi: Node] RETURNS [size: INT ← 0] ~ {
This determines the size of the intersection of the children of nagy and kicsi. Those nodes (their scratch fields) in the intersection are marked with 2, the children of only one with a 1, and the scratch fields of the rest may be anything. This has made many other procedures obsolete.
FOR iter: Kidptr ← kicsi.kidlist, iter.next UNTIL iter = NIL DO
iter.child.scratch ← 0;
ENDLOOP;
FOR iter: Kidptr ← nagy.kidlist, iter.next UNTIL iter = NIL DO
iter.child.scratch ← 1;
ENDLOOP;
FOR iter: Kidptr ← kicsi.kidlist, iter.next UNTIL iter = NIL DO
size ← size + iter.child.scratch;
iter.child.scratch ← iter.child.scratch + 1;
ENDLOOP;
};
NegateConnection: PUBLIC PROC [tree: Dag, link: Kidptr] ~ {
This takes a link from some parent to a child and changes that link (and its reciprocal link) to point from the parent to the negation of the child, creating that negation if necessary.
ide: Node ← link.child;
innen: Node ← link.parlink.child;
IF ide.type = not
THEN {
MakeLink[innen, ide.kidlist.child];
[] ← KillCLink[link];
IF ide.parnum = 0 AND NOT ide.output THEN RemoveNode[tree, ide]}
ELSE IF ide.brother # NIL
THEN {
MakeLink[innen, ide.brother];
[] ← KillCLink [link]}
ELSE IF NotAbove[ide.parlist] # NIL
THEN {
MakeLink[innen, NotAbove[ide.parlist]];
[] ← KillCLink [link]}
ELSE IF ide.parnum > 1 OR ide.type = prim OR ide.output
THEN {
MakeLink[MakeNewNodeB[tree, ide, not, NegateVarName[ide.inname]], ide];
MakeLink[innen, ide.prev];
[] ← KillCLink[link]}
ELSE ide.type ← NegNodeType[ide.type]
};
KillHangingNodes: PUBLIC PROC [tree: Dag, primsToo: BOOL] ~ {
Any nodes which do not contribute to the output are annihilated (with the possible exception of inputs if primsToo is FALSE)
ClearScratch[tree];
FOR iter: Node ← tree.csucs, iter.next UNTIL iter = NIL DO
IF iter.output THEN MarkThisSubtree[iter];
ENDLOOP;
FOR iter: Node ← tree.csucs, iter.next UNTIL iter = NIL DO
IF (primsToo OR iter.type # prim) AND iter.scratch # 1 THEN RemoveNode[tree, iter];
ENDLOOP;
};
MarkThisSubtree: PROC [vertex: Node] ~ {
This puts a 1 on each scratch field of the subtree headed by vertex (since this is only used by KillHangingNodes, the recursive process terminates if a 1 is encountered on some scratch field)
IF vertex.scratch # 1 THEN {
vertex.scratch ← 1;
SELECT vertex.type FROM
prim => NULL;
not, buf => MarkThisSubtree[vertex.kidlist.child];
ENDCASE => FOR kiditer: Kidptr ← vertex.kidlist, kiditer.next UNTIL kiditer = NIL DO
MarkThisSubtree[kiditer.child];
ENDLOOP};
};
END.