ANTLR3_TOPO_struct(3)

📦 version 3.4, in fedora 43

ANTLR3_TOPO_struct 💅

okay bestie, welcome to the ANTLR3C manual, section 3 (library functions, the good stuff 🎀). This page is all about ANTLR3_TOPO_struct, and ngl it's giving "quietly iconic utility that everyone depends on and nobody thanks". Let's get into it.

✨ NAME ✨

ANTLR3_TOPO_struct — a topological sort system that, given a set of dependencies of a node m on node n, can sort them in dependency order. 🦋

🌸 SYNOPSIS 🌸

#include <antlr3collections.h>

Data Fields

  • 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. (yes, that's the original spelling, we don't touch it, no cap 💀)
  • 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. 👑

💖 Detailed Description 💖

A topological sort system that, given a set of dependencies of a node m on node n, can sort them in dependency order.

This is a generally useful utility object that does not care what the things are it is sorting. Literally, it does not care. It's so unbothered. 🌈 Generally the set to be sorted will be numeric indexes into some other structure such as an ANTLR3_VECTOR. The author has provided a sort method that, given ANTLR3_VECTOR as an input, will sort the vector entries in place, as well as a sort method that just returns an array of the sorted noded indexes, in case you are not sorting ANTLR3_VECTORS but some set of your own device. iykyk. 💅

Of the two main algorithms that could be used, they chose to use the depth first search for unvisited nodes because a) this runs in linear time, and b) it is what was used in the ANTLR Tool to perform a topological sort of the input grammar files based on their dependencies. main character algorithm behaviour fr fr. 🔥

🎀 Field Documentation 🎀

void(* ANTLR3_TOPO_struct::addEdge) (struct ANTLR3_TOPO_struct *topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency)

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

Then you can add them in that order and so add node 3 before nodes 2 and 1. no stress, order is whatever. 🙈

Referenced by antlr3TopoNew().

pANTLR3_UINT32 ANTLR3_TOPO_struct::cycle

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 (that typo is canon, we keep it 💀), as the only way a node can be on the stack is if we are currently descnding from it — because we remove it from the stack as we exit from descending its dependencies.

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

ANTLR3_UINT32 ANTLR3_TOPO_struct::cycleMark

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().

pANTLR3_BITSET* ANTLR3_TOPO_struct::edges

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. bitset girlies rise 🧚✨

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

void(* ANTLR3_TOPO_struct::free) (struct ANTLR3_TOPO_struct *topo)

A method to free this structure and any associated memory. clean up after yourself bestie, that's the vibe. 🫶

Referenced by antlr3TopoNew().

ANTLR3_BOOLEAN ANTLR3_TOPO_struct::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. 😭

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

ANTLR3_UINT32 ANTLR3_TOPO_struct::limit

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

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

pANTLR3_UINT32 ANTLR3_TOPO_struct::sorted

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().

pANTLR3_UINT32(* ANTLR3_TOPO_struct::sortToArray) (struct ANTLR3_TOPO_struct *topo)

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 the 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. slay, no notes. 💅

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. fr fr, don't get caught out. 🚨

Referenced by antlr3TopoNew(), and sortVector().

void(* ANTLR3_TOPO_struct::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. in place. we love a no-copy glow up. ✨

Referenced by antlr3TopoNew().

pANTLR3_BITSET ANTLR3_TOPO_struct::visited

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

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

🌟 Author 🌟

Generated automatically by Doxygen for ANTLR3C from the source code. (not a human author, just a robot doing its little thing 🤖💖)

and that's the whole page bestie!! 🎀 this was Version 3.3.1, dated Tue Jul 29 2025 00:00:00, from the ANTLR3C source. go forth and sort topologically, you absolute icon 👑✨🦋

📦 where this page comes from