<> <> <> <> <<>> DIRECTORY IO, Rope, Core; DrotBool: CEDAR DEFINITIONS ~ BEGIN <> <> Vtype: TYPE = {prim,not,and,nand,or,nor,buf}; <> 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 <> PlaceAtEnd: PROC [tree: Dag, vertex: Node]; PlaceAtBeg: PROC [tree: Dag, vertex: Node]; PrimitivesToEnd: PROC [tree: Dag]; OrphansToFront: PROC [tree: Dag]; <> PlaceBefore: PROC [tree: Dag, before, after: Node] RETURNS[Node]; <> PlaceAfter: PROC [tree: Dag, before, after: Node] RETURNS[Node]; <> OrderNodesByPrims: PROC [tree: Dag]; <> OrderNodesByOrphans: PROC [tree: Dag]; <> <> RemoveNode: PROC [tree: Dag, vertex: Node]; <> 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]; <> 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]; <> MakeBrother: PROC [tree: Dag, vertex: Node]; KillCLink: PROC [link: Kidptr] RETURNS [Kidptr]; <> KillPLink: PROC [plink: Kidptr] RETURNS [Kidptr]; <> <<>> MakeLink: PROC [par,gyerek: Node]; <> <<>> MakeLinkE: PROC [szulo, gyerek: Node]; <> <<>> RemoveLink: PROC [szulo, gyerek: Node]; <> <> EstablishLevels: PROC [tree: Dag]; <> CLogarythm: PROC [base, num: INT] RETURNS [INT]; <> ClearScratch: PROC [tree: Dag]; <> <> NegNodeType: PROC [intype: Vtype] RETURNS [Vtype]; NegateVarName: PROC [name: ROPE] RETURNS [ROPE]; <> MergeListOfRopes: PROC [lista, listb: LIST OF ROPE] RETURNS [LIST OF ROPE]; NotAbove: PROC [pariter: Kidptr] RETURNS [Node]; <> <<>> NegativeOf: PROC [vertex: Node] RETURNS [negVertex: Node _ NIL]; <> ConnectionBetween: PROC [szulo, gyerek: Node] RETURNS [link: Kidptr _ 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]; <> ForwardSimilar: PROC [nodea, nodeb: Node] RETURNS [a: BOOL _ FALSE]; <> KidptrToEnd: PROC [kid: Kidptr, par: Node]; <> <<>> Negate: PROC [tree: Dag, vertex: Node] RETURNS [csucs: Node]; <> IntersectionSize: PROC [nagy, kicsi: Node] RETURNS [size: INT _ 0]; <> NegateConnection: PROC [tree: Dag, link: Kidptr]; KillHangingNodes: PROC [tree: Dag, primsToo: BOOL]; END.