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