Underlying Data Types
Most of the underlying data structures are doubly linked, circular lists. There are next and prev fields with the property that y^.next^.prev = y (unless y is the last element in the list) and y^.prev^.next = y (unless y is the first element of the list) and the exceptions arise because the next field of the last element points to NIL. Generally pointers to the lists are passed so that the lists may be easily modified (which is also the reason for the doubly linkedness). The reason for the circularity is so that insertion is easy, and the reason for the last pointer being nil is so that iteration around the list is made easy. Treesets are composed of a list of Dags and dags in turn are composed of a list of Nodes.
Vtype: TYPE = {prim,not,and,nand,or,nor,buf};
These are the types that a node may have. prim means input. buf is like NULL, currently unused
ROPE : TYPE = Rope.ROPE;
Dag: TYPE ~ REF Degree; --this is a tree
Degree:
TYPE ~
RECORD[
prev, next: Dag ← NIL,
csucs: Node ← NIL, --this is the head of the tree. In cover trees (ctrees) it is typically a source (Ie. output or orphan)
size: INT ← 0, --the number of nodes this tree contains
number: INT ← 0, --the identification number of this node within the treeset (not essential to functioning of these routines).
done: BOOL ← FALSE, --a scratch variable which indicates whether this ctree has been completely processed (used in TwoifyAllWays (I think))
cell: Core.CellType, --this is the cell type associated with this particular ctree
unmap: Dag, --If a ctree has a node with more than one parent, it must be unmapped and this points to the unmapped version if it exists or is NIL to indicate that no such unmmapping was necessary
val, netval: INT ← 0]; --val is the area assosciated with this particular ctree. Once a match has been found and instanciated, netval countains the area associated with the subtree headed by the node this ctree covers. Note that the final covers have had their netval information invalidated, so there should probably be a fuction which computes the sum of the areas of the final set of covers.
Node: TYPE ~ REF Noderec; --This is a node
Noderec:
TYPE ~
RECORD[
prev,next: Node ← NIL,
brother: Node ← NIL, --Brother should point to the negation of the node, if it exists, but currently this is not really being done. If this is implemented, care should be taken so that when node types are changed, the brother field is updated, too. This field is really bastardized in TwoifyAllWays where it is used for a completely different purpose; for that matter, the nodes mean different things too, in one part.
parlist,kidlist: Kidptr ← NIL, --this is the list of parents and children of a node respectively. The children are the inputs, the parents are where the output goes to.
parnum,kidnum: INT ← 0, --the number of parents and children respectively
scratch: INT ← 0, --this is a scratch field. VERY heavily used.
level: INT ← 1, --This is the level that this node is at.
inname: ROPE ← NIL, --If this node is an input, this is its input name.
varname: ROPE ← NIL, --If this node is an internal variable name, this is what it is. This could be a LIST OF ROPE like the outname field, but currently only one variable name per expression is allowed.
outname: LIST OF ROPE ← NIL, --these are the different names that this node, as an output, is called. outname had better be NIL is the output field is FALSE
number: INT, --this is the identification number of this node. Used to generate a unique name for each node if it doesn't have one.
type: Vtype, --the type of this node
mate: Node ← NIL, --If this node is in a ctree, mate point at the node in the tree to be covered which this maps onto
sim: BOOL ← FALSE, --If this node is a nand, says whether the left and right subtrees are similar. Currently, only computed for ctrees where no node has more than one parent.
output: BOOL ← FALSE, --is this node an output?
wire: Core.Wire ← NIL, --the wire associated with this node (could be internal).
cover: Dag ← NIL, --the cover associated with this node as the head of a subtree. Points to a the root (head) of a ctree.
map: Node --If a ctree has had to be unmapped, then this is where the unmapped nodes map to (so this field is only active in unmapped ctrees now
];
Kidptr: TYPE ~ REF Kidrec; --this is a list of pointer either acting as parents or as children
Kidrec:
TYPE ~
RECORD[
child: Node ← NIL, --If this is from a kidlist, it really does mean child, otherwise (if it is part of a parlist, then it means parent)
prev, next: Kidptr ← NIL,
parlink: Kidptr ← NIL, --For each link from parent to child, there is a link from child to parent (and vise versa). This field points to that corresponding link. It is useful for finding where a link came from because you just say link^.parlink^.child
req: INT ← 0];
Links: TYPE ~ REF Linksrec; --This is basically a set of Links. Only used in Twoify, I think
Linksrec:
TYPE ~
RECORD[
size: INT ← 0,
top: Kidptr];
Treeset: TYPE ~ REF Treesetrec; --A set of trees (ctrees)
Treesetrec:
TYPE ~
RECORD[
top: Dag ← NIL, --the first ctree
size: INT ← 0]; --how many ctrees in the set
Linear Ordering Of Trees
PlaceAtEnd: PROC [tree: Dag, vertex: Node];
PlaceAtBeg: PROC [tree: Dag, vertex: Node];
PrimitivesToEnd: PROC [tree: Dag];
OrphansToFront:
PROC [tree: Dag];
This takes all nodes which represent outputs and places them at the beginning (in linear order) of the tree --
PlaceBefore:
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[before,tree] is invoked. This will fail if before = NIL. Returns before^.next --
PlaceAfter:
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[after,tree] is invoked. Will fail if after = NIL. Returns after^.prev (or NIL if after = tree^.csucs). --
OrderNodesByPrims:
PROC [tree: Dag];
Arranges tree so that considering linear order, each node's parents are greater than it. --
OrderNodesByOrphans:
PROC [tree: Dag];
Arranges a tree so that if linear order is considered, each nodes forward pointers point only to vertices less than it. --
Creating And Deleting Tree Parts
RemoveNode:
PROC [tree: Dag, vertex: Node];
Completely removes a node from the tree, including any links it has --
MakeNewNodeA:
PROC [tree: Dag, vertex: Node, type: Vtype ← prim, inname:
ROPE ←
NIL, varname:
ROPE ←
NIL, outname:
LIST
OF
ROPE ←
NIL, output:
BOOL ←
FALSE]
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. Returns the created node.--
MakeNewNodeB:
PROC [tree: Dag, vertex: Node, type: Vtype ← prim, inname:
ROPE ←
NIL, varname:
ROPE ←
NIL, outname:
LIST
OF
ROPE ←
NIL, output:
BOOL ←
FALSE]
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. --
MakeBrother: PROC [tree: Dag, vertex: Node];
KillCLink:
PROC [link: Kidptr]
RETURNS [Kidptr];
This removes the link from a parent to a child. link must be an element of a kidlist --
KillPLink:
PROC [plink: Kidptr]
RETURNS [Kidptr];
This removes the link from a child to a parent. link must be an element of a parlist --
MakeLink:
PROC [par,gyerek: Node];
Makes a link from par (parent) to gyerek (child) in the tree containing them --
MakeLinkE:
PROC [szulo, gyerek: Node];
Makes a link from szulo to gyerek in the tree containing them, placing it at the end of these lists in linear order.
RemoveLink:
PROC [szulo, gyerek: Node];
Given two nodes, this finds the parent (szulo) - child (gyerek) link between them, if it exists, and removes it
Non Modifying Functions
NegNodeType: PROC [intype: Vtype] RETURNS [Vtype];
NegateVarName:
PROC [name:
ROPE]
RETURNS [
ROPE];
Puts a ~ in front of name unless name already has one in which case it removes the ~ --
MergeListOfRopes: PROC [lista, listb: LIST OF ROPE] RETURNS [LIST OF ROPE];
NotAbove:
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
NegativeOf:
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.
ConnectionBetween:
PROC [szulo, gyerek: Node]
RETURNS [link: Kidptr ←
NIL];
If szulo has gyerek as a child then the link between them is returned, otherwise NIL
FindExpressionByName: PROC [tree: Dag, name: ROPE] RETURNS [vertex: Node ← NIL];
FindInputByName: PROC [tree: Dag, name: ROPE] RETURNS [vertex: Node ← NIL];
FindNodeByName: PROC [tree: Dag, name: ROPE] RETURNS [vertex: Node];
Tree Modifying Functions
ForwardSimilar:
PROC [nodea, nodeb: Node]
RETURNS [a:
BOOL ←
FALSE];
Compares whether the children of two nodes (inputs) are the same. Assumes order on the links. See Compactdag) --
KidptrToEnd:
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 --
Negate:
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 --
IntersectionSize:
PROC [nagy, kicsi: Node]
RETURNS [size:
INT ← 0];
Children of the two nodes have a 2 in their scratch fields, if a child of both, 1 otherwise. Non children may have anything in their scratch fields.
NegateConnection: PROC [tree: Dag, link: Kidptr];
KillHangingNodes: PROC [tree: Dag, primsToo: BOOL];