ANTLR3_TOPO_struct - Man Page

void(* addEdge )(struct ANTLR3_TOPO_struct *topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency)
A method that adds an edge from one node to another.
pANTLR3_UINT32 cycle
A vector used to detect cycles in the edge dependecies.
ANTLR3_UINT32 cycleMark
A watermark used to accumulate potential cycles in the cycle array.
pANTLR3_BITSET * edges
A vector of vectors of edges, built by calling the addEdge method() to indicate that node number n depends on node number m.
void(* free )(struct ANTLR3_TOPO_struct *topo)
A method to free this structure and any associated memory.
ANTLR3_BOOLEAN hasCycle
A flag that indicates the algorithm found a cycle in the edges such as 9->8->1->9 If this flag is set after you have called one of the sort routines then the detected cycle will be contained in the cycle array and cycleLimit will point to the one after the last entry in the cycle.
ANTLR3_UINT32 limit
One more than the largest node index that is contained in edges/sorted.
pANTLR3_UINT32 sorted
A vector used to build up the sorted output order.
pANTLR3_UINT32(* sortToArray )(struct ANTLR3_TOPO_struct *topo)
A method that returns a pointer to an array of sorted node indexes.
void(* sortVector )(struct ANTLR3_TOPO_struct *topo, pANTLR3_VECTOR v)
A method that sorts the supplied ANTLR3_VECTOR in place based on the previously supplied edge data.
pANTLR3_BITSET visited
The set of visited nodes as determined by a set entry in the bitmap.

A method that adds an edge from one node to another. An edge of n -> m indicates that node n is dependent on node m. Note that while building these edges, it is perfectly OK to add nodes out of sequence. So, if you have edges:

3 -> 0 2 -> 1 1 -> 3

The you can add them in that order and so add node 3 before nodes 2 and 1

Referenced by antlr3TopoNew().

A vector used to detect cycles in the edge dependecies. It is used as a stack and each time we descend a node to one of its edges we add the node into this stack. If we find a node that we have already visited in the stack, then it means there wasa cycle such as 9->8->1->9 as the only way a node can be on the stack is if we are currently descnding from it as we remove it from the stack as we exit from descending its dependencies

Referenced by antlr3TopoNew(), DFS(), freeTopo(), and sortToArray().

A watermark used to accumulate potential cycles in the cycle array. This should be zero when we are done. Check hasCycle after calling one of the sort methods and if it is ANTLR3_TRUE then you can find the cycle in cycle[0]...cycle[cycleMark-1]

Referenced by antlr3TopoNew(), and DFS().

A vector of vectors of edges, built by calling the addEdge method() to indicate that node number n depends on node number m. Each entry in the vector contains a bitset, which has a bit index set for each node upon which the entry node depends.

Referenced by addEdge(), antlr3TopoNew(), DFS(), freeTopo(), and sortToArray().

A method to free this structure and any associated memory.

Referenced by antlr3TopoNew().

A flag that indicates the algorithm found a cycle in the edges such as 9->8->1->9 If this flag is set after you have called one of the sort routines then the detected cycle will be contained in the cycle array and cycleLimit will point to the one after the last entry in the cycle.

Referenced by antlr3TopoNew(), DFS(), sortToArray(), and sortVector().

One more than the largest node index that is contained in edges/sorted.

Referenced by addEdge(), antlr3TopoNew(), DFS(), freeTopo(), sortToArray(), and sortVector().

A vector used to build up the sorted output order. Note that as the vector contains UINT32 then the maximum node index is 'limited' to 2^32, as nodes should be zero based.

Referenced by antlr3TopoNew(), DFS(), freeTopo(), sortToArray(), and sortVector().

A method that returns a pointer to an array of sorted node indexes. The array is sorted in topological sorted order. Note that the array is only as large as the largest node index you created an edge for. This means that if you had an input of 32 nodes, but that largest node with an edge was 16, then the returned array will be the sorted order of the first 16 nodes and the last 16 nodes of your array are basically fine as they are as they had no dependencies and do not need any particular sort order.

NB: If the structure that contains the array is freed, then the sorted array will be freed too so you should use the value of limit to make a long term copy of this array if you do not want to keep the topo structure around as well.

Referenced by antlr3TopoNew(), and sortVector().

A method that sorts the supplied ANTLR3_VECTOR in place based on the previously supplied edge data.

Referenced by antlr3TopoNew().

The set of visited nodes as determined by a set entry in the bitmap.

Referenced by antlr3TopoNew(), DFS(), freeTopo(), and sortToArray().