]> gerrit.simantics Code Review - simantics/platform.git/blobdiff - bundles/org.simantics.databoard/cpp/DataBoardTest/libantlr3c-3.2/include/antlr3collections.h
Migrated source code from Simantics SVN
[simantics/platform.git] / bundles / org.simantics.databoard / cpp / DataBoardTest / libantlr3c-3.2 / include / antlr3collections.h
diff --git a/bundles/org.simantics.databoard/cpp/DataBoardTest/libantlr3c-3.2/include/antlr3collections.h b/bundles/org.simantics.databoard/cpp/DataBoardTest/libantlr3c-3.2/include/antlr3collections.h
new file mode 100644 (file)
index 0000000..ef49605
--- /dev/null
@@ -0,0 +1,513 @@
+#ifndef        ANTLR3COLLECTIONS_H\r
+#define        ANTLR3COLLECTIONS_H\r
+\r
+// [The "BSD licence"]\r
+// Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC\r
+// http://www.temporal-wave.com\r
+// http://www.linkedin.com/in/jimidle\r
+//\r
+// All rights reserved.\r
+//\r
+// Redistribution and use in source and binary forms, with or without\r
+// modification, are permitted provided that the following conditions\r
+// are met:\r
+// 1. Redistributions of source code must retain the above copyright\r
+//    notice, this list of conditions and the following disclaimer.\r
+// 2. Redistributions in binary form must reproduce the above copyright\r
+//    notice, this list of conditions and the following disclaimer in the\r
+//    documentation and/or other materials provided with the distribution.\r
+// 3. The name of the author may not be used to endorse or promote products\r
+//    derived from this software without specific prior written permission.\r
+//\r
+// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR\r
+// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\r
+// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.\r
+// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,\r
+// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\r
+// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,\r
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY\r
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT\r
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF\r
+// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\r
+\r
+#include    <antlr3defs.h>\r
+#include    <antlr3bitset.h>\r
+\r
+#define        ANTLR3_HASH_TYPE_INT    0   /**< Indicates the hashed file has integer keys */\r
+#define        ANTLR3_HASH_TYPE_STR    1   /**< Indicates the hashed file has numeric keys */\r
+\r
+#ifdef __cplusplus\r
+extern "C" {\r
+#endif\r
+\r
+typedef struct ANTLR3_HASH_KEY_struct\r
+{\r
+       ANTLR3_UINT8    type;   /**< One of ##ANTLR3_HASH_TYPE_INT or ##ANTLR3_HASH_TYPE_STR    */\r
+\r
+       union\r
+       {\r
+               pANTLR3_UINT8   sKey;   /**< Used if type is ANTLR3_HASH_TYPE_STR                       */\r
+               ANTLR3_INTKEY   iKey;   /**< used if type is ANTLR3_HASH_TYPE_INT                       */\r
+       }\r
+       key;\r
+\r
+} ANTLR3_HASH_KEY, *pANTLR3_HASH_KEY;\r
+\r
+/** Internal structure representing an element in a hash bucket.\r
+ *  Stores the original key so that duplicate keys can be rejected\r
+ *  if necessary, and contains function can be supported. If the hash key\r
+ *  could be unique I would have invented the perfect compression algorithm ;-)\r
+ */\r
+typedef        struct  ANTLR3_HASH_ENTRY_struct\r
+{\r
+    /** Key that created this particular entry\r
+     */\r
+    ANTLR3_HASH_KEY    keybase;\r
+\r
+    /** Pointer to the data for this particular entry\r
+     */\r
+    void           * data;\r
+\r
+    /** Pointer to routine that knows how to release the memory\r
+     *  structure pointed at by data. If this is NULL then we assume\r
+     *  that the data pointer does not need to be freed when the entry\r
+     *  is deleted from the table.\r
+     */\r
+    void           (ANTLR3_CDECL *free)(void * data);\r
+\r
+    /** Pointer to the next entry in this bucket if there\r
+     *  is one. Sometimes different keys will hash to the same bucket (especially\r
+     *  if the number of buckets is small). We could implement dual hashing algorithms\r
+     *  to minimize this, but that seems over the top for what this is needed for.\r
+     */\r
+    struct     ANTLR3_HASH_ENTRY_struct * nextEntry;\r
+}\r
+    ANTLR3_HASH_ENTRY;\r
+\r
+/** Internal structure of a hash table bucket, which tracks\r
+ *  all keys that hash to the same bucket.\r
+ */\r
+typedef struct ANTLR3_HASH_BUCKET_struct\r
+{\r
+    /** Pointer to the first entry in the bucket (if any, it\r
+     *  may be NULL). Duplicate entries are chained from\r
+     * here.\r
+     */\r
+    pANTLR3_HASH_ENTRY entries;\r
+    \r
+}\r
+    ANTLR3_HASH_BUCKET;\r
+\r
+/** Structure that tracks a hash table\r
+ */\r
+typedef        struct  ANTLR3_HASH_TABLE_struct\r
+{\r
+    /** Indicates whether the table allows duplicate keys\r
+     */\r
+    int                                        allowDups;\r
+\r
+    /** Number of buckets available in this table\r
+     */\r
+    ANTLR3_UINT32              modulo;\r
+\r
+    /** Points to the memory where the array of buckets\r
+     * starts.\r
+     */\r
+    pANTLR3_HASH_BUCKET        buckets;\r
+\r
+    /** How many elements currently exist in the table.\r
+     */\r
+    ANTLR3_UINT32              count;\r
+\r
+    /** Whether the hash table should strdup the keys it is given or not.\r
+     */\r
+    ANTLR3_BOOLEAN              doStrdup;\r
+\r
+    /** Pointer to function to completely delete this table\r
+     */\r
+    void                               (*free)     (struct ANTLR3_HASH_TABLE_struct * table);\r
+    \r
+    /* String keyed hashtable functions */\r
+    void                               (*del)      (struct ANTLR3_HASH_TABLE_struct * table, void * key);\r
+    pANTLR3_HASH_ENTRY (*remove)   (struct ANTLR3_HASH_TABLE_struct * table, void * key);\r
+    void *                             (*get)      (struct ANTLR3_HASH_TABLE_struct * table, void * key);\r
+    ANTLR3_INT32               (*put)      (struct ANTLR3_HASH_TABLE_struct * table, void * key, void * element, void (ANTLR3_CDECL *freeptr)(void *));\r
+\r
+    /* Integer based hash functions */\r
+    void                               (*delI)     (struct ANTLR3_HASH_TABLE_struct * table, ANTLR3_INTKEY key);\r
+    pANTLR3_HASH_ENTRY (*removeI)  (struct ANTLR3_HASH_TABLE_struct * table, ANTLR3_INTKEY key);\r
+    void *                             (*getI)     (struct ANTLR3_HASH_TABLE_struct * table, ANTLR3_INTKEY key);\r
+    ANTLR3_INT32               (*putI)     (struct ANTLR3_HASH_TABLE_struct * table, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *));\r
+\r
+    ANTLR3_UINT32              (*size)     (struct ANTLR3_HASH_TABLE_struct * table);\r
+}\r
+    ANTLR3_HASH_TABLE;\r
+\r
+\r
+/** Internal structure representing an enumeration of a table.\r
+ *  This is returned by antlr3Enumeration()\r
+ *  Allows the programmer to traverse the table in hash order without \r
+ *  knowing what is in the actual table.\r
+ *\r
+ *  Note that it is up to the caller to ensure that the table\r
+ *  structure does not change in the hash bucket that is currently being\r
+ *  enumerated as this structure just tracks the next pointers in the\r
+ *  bucket series.\r
+ */\r
+typedef struct ANTLR3_HASH_ENUM_struct\r
+{\r
+    /* Pointer to the table we are enumerating\r
+     */\r
+    pANTLR3_HASH_TABLE table;\r
+\r
+    /* Bucket we are currently enumerating (if NULL then we are done)\r
+     */\r
+    ANTLR3_UINT32      bucket;\r
+\r
+    /* Next entry to return, if NULL, then move to next bucket if any\r
+     */\r
+    pANTLR3_HASH_ENTRY entry;\r
+\r
+    /* Interface\r
+     */\r
+    int                (*next)     (struct ANTLR3_HASH_ENUM_struct * en, pANTLR3_HASH_KEY *key, void ** data);\r
+    void       (*free)     (struct ANTLR3_HASH_ENUM_struct * table);\r
+}\r
+    ANTLR3_HASH_ENUM;\r
+\r
+/** Structure that represents a LIST collection\r
+ */\r
+typedef        struct  ANTLR3_LIST_struct\r
+{\r
+    /** Hash table that is storing the list elements\r
+     */\r
+    pANTLR3_HASH_TABLE table;\r
+\r
+    void                       (*free)         (struct ANTLR3_LIST_struct * list);\r
+    void                       (*del)          (struct ANTLR3_LIST_struct * list, ANTLR3_INTKEY key);\r
+    void *                     (*get)          (struct ANTLR3_LIST_struct * list, ANTLR3_INTKEY key);\r
+    void *                     (*remove)       (struct ANTLR3_LIST_struct * list, ANTLR3_INTKEY key);\r
+    ANTLR3_INT32    (*add)             (struct ANTLR3_LIST_struct * list, void * element, void (ANTLR3_CDECL *freeptr)(void *));\r
+    ANTLR3_INT32    (*put)             (struct ANTLR3_LIST_struct * list, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *));\r
+    ANTLR3_UINT32   (*size)            (struct ANTLR3_LIST_struct * list);\r
+    \r
+}\r
+    ANTLR3_LIST;\r
+\r
+/** Structure that represents a Stack collection\r
+ */\r
+typedef        struct  ANTLR3_STACK_struct\r
+{\r
+    /** List that supports the stack structure\r
+     */\r
+    pANTLR3_VECTOR  vector;\r
+\r
+    /** Used for quick access to the top of the stack\r
+     */\r
+    void *         top;\r
+    void                       (*free) (struct ANTLR3_STACK_struct * stack);\r
+    void *                     (*pop)  (struct ANTLR3_STACK_struct * stack);\r
+    void *                     (*get)  (struct ANTLR3_STACK_struct * stack, ANTLR3_INTKEY key);\r
+    ANTLR3_BOOLEAN  (*push)    (struct ANTLR3_STACK_struct * stack, void * element, void (ANTLR3_CDECL *freeptr)(void *));\r
+    ANTLR3_UINT32   (*size)    (struct ANTLR3_STACK_struct * stack);\r
+    void *                     (*peek) (struct ANTLR3_STACK_struct * stack);\r
+\r
+}\r
+    ANTLR3_STACK;\r
+\r
+/* Structure that represents a vector element\r
+ */\r
+typedef struct ANTLR3_VECTOR_ELEMENT_struct\r
+{\r
+    void    * element;\r
+    void (ANTLR3_CDECL *freeptr)(void *);\r
+}\r
+    ANTLR3_VECTOR_ELEMENT, *pANTLR3_VECTOR_ELEMENT;\r
+\r
+#define ANTLR3_VECTOR_INTERNAL_SIZE     16\r
+/* Structure that represents a vector collection. A vector is a simple list\r
+ * that contains a pointer to the element and a pointer to a function that\r
+ * that can free the element if it is removed. It auto resizes but does not\r
+ * use hash techniques as it is referenced by a simple numeric index. It is not a \r
+ * sparse list, so if any element is deleted, then the ones following are moved\r
+ * down in memory and the count is adjusted.\r
+ */\r
+typedef struct ANTLR3_VECTOR_struct\r
+{\r
+    /** Array of pointers to vector elements\r
+     */\r
+    pANTLR3_VECTOR_ELEMENT  elements;\r
+\r
+    /** Number of entries currently in the list;\r
+     */\r
+    ANTLR3_UINT32   count;\r
+\r
+    /** Many times, a vector holds just a few nodes in an AST and it\r
+     * is too much overhead to malloc the space for elements so\r
+     * at the expense of a few bytes of memory, we hold the first\r
+     * few elements internally. It means we must copy them when\r
+     * we grow beyond this initial size, but that is less overhead than\r
+     * the malloc/free callas we would otherwise require.\r
+     */\r
+    ANTLR3_VECTOR_ELEMENT   internal[ANTLR3_VECTOR_INTERNAL_SIZE];\r
+\r
+    /** Indicates if the structure was made by a factory, in which\r
+     *  case only the factory can free the memory for the actual vector,\r
+     *  though the vector free function is called and will recurse through its\r
+     *  entries calling any free pointers for each entry.\r
+     */\r
+    ANTLR3_BOOLEAN  factoryMade;\r
+\r
+    /** Total number of entries in elements at any point in time\r
+     */\r
+    ANTLR3_UINT32   elementsSize;\r
+\r
+    void                       (ANTLR3_CDECL *free)    (struct ANTLR3_VECTOR_struct * vector);\r
+    void                       (*del)                                  (struct ANTLR3_VECTOR_struct * vector, ANTLR3_UINT32 entry);\r
+    void *                     (*get)                                  (struct ANTLR3_VECTOR_struct * vector, ANTLR3_UINT32 entry);\r
+    void *                     (*remove)                               (struct ANTLR3_VECTOR_struct * vector, ANTLR3_UINT32 entry);\r
+    void                       (*clear)                                (struct ANTLR3_VECTOR_struct * vector);\r
+    ANTLR3_BOOLEAN              (*swap)                 (struct ANTLR3_VECTOR_struct *, ANTLR3_UINT32 entry1, ANTLR3_UINT32 entry2);\r
+    ANTLR3_UINT32   (*add)                                     (struct ANTLR3_VECTOR_struct * vector, void * element, void (ANTLR3_CDECL *freeptr)(void *));\r
+    ANTLR3_UINT32   (*set)                                     (struct ANTLR3_VECTOR_struct * vector, ANTLR3_UINT32 entry, void * element, void (ANTLR3_CDECL *freeptr)(void *), ANTLR3_BOOLEAN freeExisting);\r
+    ANTLR3_UINT32   (*size)                                    (struct ANTLR3_VECTOR_struct * vector);\r
+}\r
+    ANTLR3_VECTOR;\r
+\r
+/** Default vector pool size if otherwise unspecified\r
+ */\r
+#define ANTLR3_FACTORY_VPOOL_SIZE 256\r
+\r
+/** Structure that tracks vectors in a vector and auto deletes the vectors\r
+ *  in the vector factory when closed.\r
+ */\r
+typedef struct ANTLR3_VECTOR_FACTORY_struct\r
+{\r
+\r
+        /** List of all vector pools allocated so far\r
+         */\r
+        pANTLR3_VECTOR      *pools;\r
+\r
+        /** Count of the vector pools allocated so far (current active pool)\r
+         */\r
+        ANTLR3_INT32         thisPool;\r
+\r
+        /** The next vector available in the pool\r
+         */\r
+        ANTLR3_UINT32        nextVector;\r
+\r
+        /** Trick to quickly initialize a new vector via memcpy and not a function call\r
+         */\r
+        ANTLR3_VECTOR        unTruc;\r
+\r
+               /** Consumers from the factory can release a factory produced vector \r
+                * back to the factory so that it may be reused (and thus conserve memory)\r
+                * by another caller. The available vectors are stored here. Note that\r
+                * the only vectors avaible in the free chain are produced by this factory, so they\r
+                * need not be explicitly freed when the factory is closed.\r
+                */\r
+               pANTLR3_STACK            freeStack;\r
+\r
+               /** Function to close the vector factory\r
+        */\r
+       void                (*close)        (struct ANTLR3_VECTOR_FACTORY_struct * factory);\r
+\r
+       /** Function to supply a new vector\r
+        */\r
+       pANTLR3_VECTOR      (*newVector)    (struct ANTLR3_VECTOR_FACTORY_struct * factory);\r
+\r
+       /// Function to return a vector to the factory for reuse\r
+       ///\r
+       void                            (*returnVector) (struct ANTLR3_VECTOR_FACTORY_struct * factory, pANTLR3_VECTOR vector);\r
+\r
+}\r
+ANTLR3_VECTOR_FACTORY; \r
+    \r
+    \r
+/* -------------- TRIE Interfaces ---------------- */\r
+\r
+\r
+/** Structure that holds the payload entry in an ANTLR3_INT_TRIE or ANTLR3_STRING_TRIE\r
+ */\r
+typedef struct ANTLR3_TRIE_ENTRY_struct\r
+{\r
+       ANTLR3_UINT32   type;\r
+       void (ANTLR3_CDECL *freeptr)(void *);\r
+       union\r
+       {\r
+               ANTLR3_INTKEY     intVal;\r
+               void            * ptr;\r
+       } data;\r
+\r
+       struct ANTLR3_TRIE_ENTRY_struct * next;     /* Allows duplicate entries for same key in insertion order */\r
+}\r
+ANTLR3_TRIE_ENTRY, * pANTLR3_TRIE_ENTRY;\r
+\r
+\r
+/** Structure that defines an element/node in an ANTLR3_INT_TRIE\r
+ */\r
+typedef struct ANTLR3_INT_TRIE_NODE_struct\r
+{\r
+    ANTLR3_UINT32                                                        bitNum;       /**< This is the left/right bit index for traversal along the nodes                             */\r
+    ANTLR3_INTKEY                                                        key;          /**< This is the actual key that the entry represents if it is a terminal node  */\r
+    pANTLR3_TRIE_ENTRY                                           buckets;      /**< This is the data bucket(s) that the key indexes, which may be NULL                 */\r
+    struct ANTLR3_INT_TRIE_NODE_struct     * leftN;    /**< Pointer to the left node from here when sKey & bitNum = 0                                  */\r
+    struct ANTLR3_INT_TRIE_NODE_struct     * rightN;   /**< Pointer to the right node from here when sKey & bitNum, = 1                                */\r
+}\r
+    ANTLR3_INT_TRIE_NODE, * pANTLR3_INT_TRIE_NODE;\r
+\r
+/** Structure that defines an ANTLR3_INT_TRIE. For this particular implementation,\r
+ *  as you might expect, the key is turned into a "string" by looking at bit(key, depth)\r
+ *  of the integer key. Using 64 bit keys gives us a depth limit of 64 (or bit 0..63)\r
+ *  and potentially a huge trie. This is the algorithm for a Patricia Trie.\r
+ *  Note also that this trie [can] accept multiple entries for the same key and is\r
+ *  therefore a kind of elastic bucket patricia trie.\r
+ *\r
+ *  If you find this code useful, please feel free to 'steal' it for any purpose\r
+ *  as covered by the BSD license under which ANTLR is issued. You can cut the code\r
+ *  but as the ANTLR library is only about 50K (Windows Vista), you might find it \r
+ *  easier to just link the library. Please keep all comments and licenses and so on\r
+ *  in any version of this you create of course.\r
+ *\r
+ *  Jim Idle.\r
+ *  \r
+ */\r
+typedef struct ANTLR3_INT_TRIE_struct\r
+{\r
+    pANTLR3_INT_TRIE_NODE   root;                      /* Root node of this integer trie                                       */\r
+    pANTLR3_INT_TRIE_NODE   current;           /* Used to traverse the TRIE with the next() method     */\r
+    ANTLR3_UINT32                      count;                  /* Current entry count                                                          */\r
+    ANTLR3_BOOLEAN                     allowDups;              /* Whether this trie accepts duplicate keys                     */\r
+\r
+    \r
+    pANTLR3_TRIE_ENTRY (*get)  (struct ANTLR3_INT_TRIE_struct * trie, ANTLR3_INTKEY key);\r
+    ANTLR3_BOOLEAN             (*del)  (struct ANTLR3_INT_TRIE_struct * trie, ANTLR3_INTKEY key);\r
+    ANTLR3_BOOLEAN             (*add)  (struct ANTLR3_INT_TRIE_struct * trie, ANTLR3_INTKEY key, ANTLR3_UINT32 type, ANTLR3_INTKEY intVal, void * data, void (ANTLR3_CDECL *freeptr)(void *));\r
+    void                               (*free) (struct ANTLR3_INT_TRIE_struct * trie);\r
+\r
+}\r
+    ANTLR3_INT_TRIE;\r
+\r
+/**\r
+ * A topological sort system that given a set of dependencies of a node m on node n,\r
+ * can sort them in dependency order. This is a generally useful utility object\r
+ * that does not care what the things are it is sorting. Generally the set\r
+ * to be sorted will be numeric indexes into some other structure such as an ANTLR3_VECTOR.\r
+ * I have provided a sort method that given ANTLR3_VECTOR as an input will sort\r
+ * the vector entries in place, as well as a sort method that just returns an\r
+ * array of the sorted noded indexes, in case you are not sorting ANTLR3_VECTORS but\r
+ * some set of your own device.\r
+ *\r
+ * Of the two main algorithms that could be used, I chose to use the depth first\r
+ * search for unvisited nodes as a) This runs in linear time, and b) it is what\r
+ * we used in the ANTLR Tool to perform a topological sort of the input grammar files\r
+ * based on their dependencies.\r
+ */\r
+typedef struct ANTLR3_TOPO_struct\r
+{\r
+    /**\r
+     * A vector of vectors of edges, built by calling the addEdge method()\r
+     * to indicate that node number n depends on node number m. Each entry in the vector\r
+     * contains a bitset, which has a bit index set for each node upon which the\r
+     * entry node depends.\r
+     */\r
+    pANTLR3_BITSET  * edges;\r
+\r
+    /**\r
+     * A vector used to build up the sorted output order. Note that\r
+     * as the vector contains UINT32 then the maximum node index is\r
+     * 'limited' to 2^32, as nodes should be zero based.\r
+     */\r
+    pANTLR3_UINT32    sorted;\r
+\r
+    /**\r
+     * A vector used to detect cycles in the edge dependecies. It is used\r
+     * as a stack and each time we descend a node to one of its edges we\r
+     * add the node into this stack. If we find a node that we have already\r
+     * visited in the stack, then it means there wasa cycle such as 9->8->1->9\r
+     * as the only way a node can be on the stack is if we are currently\r
+     * descnding from it as we remove it from the stack as we exit from\r
+     * descending its dependencies\r
+     */\r
+    pANTLR3_UINT32    cycle;\r
+\r
+    /**\r
+     * A flag that indicates the algorithm found a cycle in the edges\r
+     * such as 9->8->1->9\r
+     * If this flag is set after you have called one of the sort routines\r
+     * then the detected cycle will be contained in the cycle array and\r
+     * cycleLimit will point to the one after the last entry in the cycle.\r
+     */\r
+    ANTLR3_BOOLEAN    hasCycle;\r
+\r
+    /**\r
+     * A watermark used to accumulate potential cycles in the cycle array.\r
+     * This should be zero when we are done. Check hasCycle after calling one\r
+     * of the sort methods and if it is ANTLR3_TRUE then you can find the cycle\r
+     * in cycle[0]...cycle[cycleMark-1]\r
+     */\r
+    ANTLR3_UINT32     cycleMark;\r
+    \r
+    /**\r
+     * One more than the largest node index that is contained in edges/sorted.\r
+     */\r
+    ANTLR3_UINT32     limit;\r
+\r
+    /**\r
+     * The set of visited nodes as determined by a set entry in\r
+     * the bitmap.\r
+     */\r
+    pANTLR3_BITSET    visited;\r
+\r
+    /**\r
+     * A method that adds an edge from one node to another. An edge\r
+     * of n -> m indicates that node n is dependent on node m. Note that\r
+     * while building these edges, it is perfectly OK to add nodes out of\r
+     * sequence. So, if you have edges:\r
+     *\r
+     * 3 -> 0\r
+     * 2 -> 1\r
+     * 1 -> 3\r
+     *\r
+     * The you can add them in that order and so add node 3 before nodes 2 and 1\r
+     *\r
+     */\r
+    void            (*addEdge)          (struct ANTLR3_TOPO_struct * topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency);\r
+\r
+\r
+    /**\r
+     * A method that returns a pointer to an array of sorted node indexes.\r
+     * The array is sorted in topological sorted order. Note that the array\r
+     * is only as large as the largest node index you created an edge for. This means\r
+     * that if you had an input of 32 nodes, but that largest node with an edge\r
+     * was 16, then the returned array will be the sorted order of the first 16\r
+     * nodes and the last 16 nodes of your array are basically fine as they are\r
+     * as they had no dependencies and do not need any particular sort order.\r
+     *\r
+     * NB: If the structure that contains the array is freed, then the sorted\r
+     * array will be freed too so you should use the value of limit to\r
+     * make a long term copy of this array if you do not want to keep the topo\r
+     * structure around as well.\r
+     */\r
+    pANTLR3_UINT32  (*sortToArray)      (struct ANTLR3_TOPO_struct * topo);\r
+\r
+    /** \r
+     * A method that sorts the supplied ANTLR3_VECTOR in place based\r
+     * on the previously supplied edge data.\r
+     */\r
+    void            (*sortVector)       (struct ANTLR3_TOPO_struct * topo, pANTLR3_VECTOR v);\r
+\r
+    /**\r
+     *  A method to free this structure and any associated memory.\r
+     */\r
+    void            (*free)             (struct ANTLR3_TOPO_struct * topo);\r
+}\r
+    ANTLR3_TOPO;\r
+    \r
+#ifdef __cplusplus\r
+}\r
+#endif\r
+\r
+#endif\r
+\r
+\r