Add a parser for linear equations

(Also add the antlr jar and C runtime)

1 files changed, 2741 insertions, 0 deletions

diff --git a/impl/antlr/libantlr3c-3.4/src/antlr3collections.c b/impl/antlr/libantlr3c-3.4/src/antlr3collections.c
new file mode 100644
index 0000000..d9e22e9
--- /dev/null
+++ b/impl/antlr/libantlr3c-3.4/src/antlr3collections.c
@@ -0,0 +1,2741 @@
+/// \file
+/// Provides a number of useful functions that are roughly equivalent
+/// to java HashTable and List for the purposes of Antlr 3 C runtime.
+/// Also useable by the C programmer for things like symbol tables pointers
+/// and so on.
+///
+///
+
+// [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    <antlr3.h>
+
+#include "antlr3collections.h"
+
+// Interface functions for hash table
+//
+
+// String based keys
+//
+static void					antlr3HashDelete    (pANTLR3_HASH_TABLE table, void * key);
+static void *				antlr3HashGet	(pANTLR3_HASH_TABLE table, void * key);
+static pANTLR3_HASH_ENTRY   antlr3HashRemove    (pANTLR3_HASH_TABLE table, void * key);
+static ANTLR3_INT32			antlr3HashPut	(pANTLR3_HASH_TABLE table, void * key, void * element, void (ANTLR3_CDECL *freeptr)(void *));
+
+// Integer based keys (Lists and so on)
+//
+static void					antlr3HashDeleteI   (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key);
+static void *				antlr3HashGetI	(pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key);
+static pANTLR3_HASH_ENTRY   antlr3HashRemoveI   (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key);
+static ANTLR3_INT32			antlr3HashPutI	(pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *));
+
+static void					antlr3HashFree	(pANTLR3_HASH_TABLE table);
+static ANTLR3_UINT32	    antlr3HashSize	(pANTLR3_HASH_TABLE table);
+
+// -----------
+
+// Interface functions for enumeration
+//
+static int	    antlr3EnumNext	    (pANTLR3_HASH_ENUM en, pANTLR3_HASH_KEY * key, void ** data);
+static void	    antlr3EnumFree	    (pANTLR3_HASH_ENUM en);
+
+// Interface functions for List
+//
+static void				antlr3ListFree	(pANTLR3_LIST list);
+static void				antlr3ListDelete(pANTLR3_LIST list, ANTLR3_INTKEY key);
+static void *			antlr3ListGet	(pANTLR3_LIST list, ANTLR3_INTKEY key);
+static ANTLR3_INT32		antlr3ListPut	(pANTLR3_LIST list, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *));
+static ANTLR3_INT32		antlr3ListAdd   (pANTLR3_LIST list, void * element, void (ANTLR3_CDECL *freeptr)(void *));
+static void *			antlr3ListRemove(pANTLR3_LIST list, ANTLR3_INTKEY key);
+static ANTLR3_UINT32	antlr3ListSize	(pANTLR3_LIST list);
+
+// Interface functions for Stack
+//
+static void				antlr3StackFree	(pANTLR3_STACK  stack);
+static void *			antlr3StackPop	(pANTLR3_STACK	stack);
+static void *			antlr3StackGet	(pANTLR3_STACK	stack, ANTLR3_INTKEY key);
+static ANTLR3_BOOLEAN	antlr3StackPush	(pANTLR3_STACK	stack, void * element, void (ANTLR3_CDECL *freeptr)(void *));
+static ANTLR3_UINT32	antlr3StackSize	(pANTLR3_STACK	stack);
+static void *			antlr3StackPeek	(pANTLR3_STACK	stack);
+
+// Interface functions for vectors
+//
+static	void ANTLR3_CDECL	antlr3VectorFree	(pANTLR3_VECTOR vector);
+static	void				antlr3VectorDel		(pANTLR3_VECTOR vector, ANTLR3_UINT32 entry);
+static	void *				antlr3VectorGet		(pANTLR3_VECTOR vector, ANTLR3_UINT32 entry);
+static	void *				antrl3VectorRemove	(pANTLR3_VECTOR vector, ANTLR3_UINT32 entry);
+static	void				antlr3VectorClear	(pANTLR3_VECTOR vector);
+static	ANTLR3_UINT32		antlr3VectorAdd		(pANTLR3_VECTOR vector, void * element, void (ANTLR3_CDECL *freeptr)(void *));
+static	ANTLR3_UINT32		antlr3VectorSet		(pANTLR3_VECTOR vector, ANTLR3_UINT32 entry, void * element, void (ANTLR3_CDECL *freeptr)(void *), ANTLR3_BOOLEAN freeExisting);
+static	ANTLR3_UINT32		antlr3VectorSize    (pANTLR3_VECTOR vector);
+static	ANTLR3_BOOLEAN      antlr3VectorSwap	(pANTLR3_VECTOR vector, ANTLR3_UINT32 entry1, ANTLR3_UINT32 entry2);
+
+static  void                newPool             (pANTLR3_VECTOR_FACTORY factory);
+static  void				closeVectorFactory  (pANTLR3_VECTOR_FACTORY factory);
+static	pANTLR3_VECTOR		newVector			(pANTLR3_VECTOR_FACTORY factory);
+static	void				returnVector		(pANTLR3_VECTOR_FACTORY factory, pANTLR3_VECTOR vector);
+
+
+// Interface functions for int TRIE
+//
+static	pANTLR3_TRIE_ENTRY	intTrieGet		(pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key);
+static	ANTLR3_BOOLEAN		intTrieDel		(pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key);
+static	ANTLR3_BOOLEAN		intTrieAdd		(pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key, ANTLR3_UINT32 type, ANTLR3_INTKEY intType, void * data, void (ANTLR3_CDECL *freeptr)(void *));
+static	void				intTrieFree		(pANTLR3_INT_TRIE trie);
+
+
+// Interface functions for topological sorter
+//
+static  void            addEdge          (pANTLR3_TOPO topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency);
+static  pANTLR3_UINT32  sortToArray      (pANTLR3_TOPO topo);
+static  void            sortVector       (pANTLR3_TOPO topo, pANTLR3_VECTOR v);
+static  void            freeTopo         (pANTLR3_TOPO topo);
+
+// Local function to advance enumeration structure pointers
+//
+static void antlr3EnumNextEntry(pANTLR3_HASH_ENUM en);
+
+pANTLR3_HASH_TABLE
+antlr3HashTableNew(ANTLR3_UINT32 sizeHint)
+{
+	// All we have to do is create the hashtable tracking structure
+	// and allocate memory for the requested number of buckets.
+	//
+	pANTLR3_HASH_TABLE	table;
+
+	ANTLR3_UINT32	bucket;	// Used to traverse the buckets
+
+	table   = ANTLR3_MALLOC(sizeof(ANTLR3_HASH_TABLE));
+
+	// Error out if no memory left
+	if	(table	== NULL)
+	{
+		return	NULL;
+	}
+
+	// Allocate memory for the buckets
+	//
+	table->buckets = (pANTLR3_HASH_BUCKET) ANTLR3_MALLOC((size_t) (sizeof(ANTLR3_HASH_BUCKET) * sizeHint)); 
+
+	if	(table->buckets == NULL)
+	{
+		ANTLR3_FREE((void *)table);
+		return	NULL;
+	}
+
+	// Modulo of the table, (bucket count).
+	//
+	table->modulo   = sizeHint;
+
+	table->count    = 0;	    /* Nothing in there yet ( I hope)	*/
+
+	/* Initialize the buckets to empty
+	*/
+	for	(bucket = 0; bucket < sizeHint; bucket++)
+	{
+		table->buckets[bucket].entries = NULL;
+	}
+
+	/* Exclude duplicate entries by default
+	*/
+	table->allowDups	= ANTLR3_FALSE;
+
+    /* Assume that keys should by strduped before they are
+     * entered in the table.
+     */
+    table->doStrdup     = ANTLR3_TRUE;
+
+	/* Install the interface
+	*/
+
+	table->get		=  antlr3HashGet;
+	table->put		=  antlr3HashPut;
+	table->del		=  antlr3HashDelete;
+	table->remove	=  antlr3HashRemove;
+
+	table->getI		=  antlr3HashGetI;
+	table->putI		=  antlr3HashPutI;
+	table->delI		=  antlr3HashDeleteI;
+	table->removeI	=  antlr3HashRemoveI;
+
+	table->size		=  antlr3HashSize;
+	table->free		=  antlr3HashFree;
+
+	return  table;
+}
+
+static void
+antlr3HashFree(pANTLR3_HASH_TABLE table)
+{
+    ANTLR3_UINT32	bucket;	/* Used to traverse the buckets	*/
+
+    pANTLR3_HASH_BUCKET	thisBucket;
+    pANTLR3_HASH_ENTRY	entry;
+    pANTLR3_HASH_ENTRY	nextEntry;
+
+    /* Free the table, all buckets and all entries, and all the
+     * keys and data (if the table exists)
+     */
+    if	(table	!= NULL)
+    {
+	for	(bucket = 0; bucket < table->modulo; bucket++)
+	{
+	    thisBucket	= &(table->buckets[bucket]);
+
+	    /* Allow sparse tables, though we don't create them as such at present
+	     */
+	    if	( thisBucket != NULL)
+	    {
+		entry	= thisBucket->entries;
+
+		/* Search all entries in the bucket and free them up
+		 */
+		while	(entry != NULL)
+		{
+		    /* Save next entry - we do not want to access memory in entry after we
+		     * have freed it.
+		     */
+		    nextEntry	= entry->nextEntry;
+
+		    /* Free any data pointer, this only happens if the user supplied
+		     * a pointer to a routine that knwos how to free the structure they
+		     * added to the table.
+		     */
+		    if	(entry->free != NULL)
+		    {
+			entry->free(entry->data);
+		    }
+
+		    /* Free the key memory - we know that we allocated this
+		     */
+		    if	(entry->keybase.type == ANTLR3_HASH_TYPE_STR && entry->keybase.key.sKey != NULL)
+		    {
+			ANTLR3_FREE(entry->keybase.key.sKey);
+		    }
+
+		    /* Free this entry
+		     */
+		    ANTLR3_FREE(entry);
+		    entry   = nextEntry;    /* Load next pointer to see if we shoud free it */
+		}
+		/* Invalidate the current pointer
+		 */
+		thisBucket->entries = NULL;
+	    }
+	}
+
+	/* Now we can free the bucket memory
+	 */
+	ANTLR3_FREE(table->buckets);
+    }
+
+    /* Now we free teh memory for the table itself
+     */
+    ANTLR3_FREE(table);
+}
+
+/** return the current size of the hash table
+ */
+static ANTLR3_UINT32	antlr3HashSize	    (pANTLR3_HASH_TABLE table)
+{
+    return  table->count;
+}
+
+/** Remove a numeric keyed entry from a hash table if it exists,
+ *  no error if it does not exist.
+ */
+static pANTLR3_HASH_ENTRY   antlr3HashRemoveI   (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key)
+{
+    ANTLR3_UINT32	    hash;
+    pANTLR3_HASH_BUCKET	    bucket;
+    pANTLR3_HASH_ENTRY	    entry;
+    pANTLR3_HASH_ENTRY	    * nextPointer;
+
+    /* First we need to know the hash of the provided key
+     */
+    hash    = (ANTLR3_UINT32)(key % (ANTLR3_INTKEY)(table->modulo));
+
+    /* Knowing the hash, we can find the bucket
+     */
+    bucket  = table->buckets + hash;
+
+    /* Now, we traverse the entries in the bucket until
+     * we find the key or the end of the entries in the bucket. 
+     * We track the element prior to the one we are examining
+     * as we need to set its next pointer to the next pointer
+     * of the entry we are deleting (if we find it).
+     */
+    entry	    =   bucket->entries;    /* Entry to examine					    */
+    nextPointer	    = & bucket->entries;    /* Where to put the next pointer of the deleted entry   */
+
+    while   (entry != NULL)
+    {
+	/* See if this is the entry we wish to delete
+	 */
+	if  (entry->keybase.key.iKey == key)
+	{
+	    /* It was the correct entry, so we set the next pointer
+	     * of the previous entry to the next pointer of this
+	     * located one, which takes it out of the chain.
+	     */
+	    (*nextPointer)		= entry->nextEntry;
+
+	    table->count--;
+
+	    return entry;
+	}
+	else
+	{
+	    /* We found an entry but it wasn't the one that was wanted, so
+	     * move to the next one, if any.
+	     */
+	    nextPointer	= & (entry->nextEntry);	    /* Address of the next pointer in the current entry	    */
+	    entry	= entry->nextEntry;	    /* Address of the next element in the bucket (if any)   */
+	}
+    }
+
+    return NULL;  /* Not found */
+}
+
+/** Remove the element in the hash table for a particular
+ *  key value, if it exists - no error if it does not.
+ */
+static pANTLR3_HASH_ENTRY
+antlr3HashRemove(pANTLR3_HASH_TABLE table, void * key)
+{
+    ANTLR3_UINT32	    hash;
+    pANTLR3_HASH_BUCKET	    bucket;
+    pANTLR3_HASH_ENTRY	    entry;
+    pANTLR3_HASH_ENTRY	    * nextPointer;
+
+    /* First we need to know the hash of the provided key
+     */
+    hash    = antlr3Hash(key, (ANTLR3_UINT32)strlen((const char *)key));
+
+    /* Knowing the hash, we can find the bucket
+     */
+    bucket  = table->buckets + (hash % table->modulo);
+
+    /* Now, we traverse the entries in the bucket until
+     * we find the key or the end of the entires in the bucket. 
+     * We track the element prior to the one we are exmaining
+     * as we need to set its next pointer to the next pointer
+     * of the entry we are deleting (if we find it).
+     */
+    entry	    =   bucket->entries;    /* Entry to examine					    */
+    nextPointer	    = & bucket->entries;    /* Where to put the next pointer of the deleted entry   */
+
+    while   (entry != NULL)
+    {
+	/* See if this is the entry we wish to delete
+	 */
+	if  (strcmp((const char *)key, (const char *)entry->keybase.key.sKey) == 0)
+	{
+	    /* It was the correct entry, so we set the next pointer
+	     * of the previous entry to the next pointer of this
+	     * located one, which takes it out of the chain.
+	     */
+	    (*nextPointer)		= entry->nextEntry;
+
+	    /* Release the key - if we allocated that
+	     */
+        if (table->doStrdup == ANTLR3_TRUE)
+        {
+            ANTLR3_FREE(entry->keybase.key.sKey);
+        }
+	    entry->keybase.key.sKey	= NULL;
+
+	    table->count--;
+
+	    return entry;
+	}
+	else
+	{
+	    /* We found an entry but it wasn't the one that was wanted, so
+	     * move to the next one, if any.
+	     */
+	    nextPointer	= & (entry->nextEntry);	    /* Address of the next pointer in the current entry	    */
+	    entry	= entry->nextEntry;	    /* Address of the next element in the bucket (if any)   */
+	}
+    }
+
+    return NULL;  /* Not found */
+}
+
+/** Takes the element with the supplied key out of the list, and deletes the data
+ *  calling the supplied free() routine if any. 
+ */
+static void
+antlr3HashDeleteI    (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key)
+{
+    pANTLR3_HASH_ENTRY	entry;
+
+    entry = antlr3HashRemoveI(table, key);
+	
+    /* Now we can free the elements and the entry in order
+     */
+    if	(entry != NULL && entry->free != NULL)
+    {
+	/* Call programmer supplied function to release this entry data
+	 */
+	entry->free(entry->data);
+	entry->data = NULL;
+    }
+    /* Finally release the space for this entry block.
+     */
+    ANTLR3_FREE(entry);
+}
+
+/** Takes the element with the supplied key out of the list, and deletes the data
+ *  calling the supplied free() routine if any. 
+ */
+static void
+antlr3HashDelete    (pANTLR3_HASH_TABLE table, void * key)
+{
+    pANTLR3_HASH_ENTRY	entry;
+
+    entry = antlr3HashRemove(table, key);
+	
+    /* Now we can free the elements and the entry in order
+     */
+    if	(entry != NULL && entry->free != NULL)
+    {
+	/* Call programmer supplied function to release this entry data
+	 */
+	entry->free(entry->data);
+	entry->data = NULL;
+    }
+    /* Finally release the space for this entry block.
+     */
+    ANTLR3_FREE(entry);
+}
+
+/** Return the element pointer in the hash table for a particular
+ *  key value, or NULL if it don't exist (or was itself NULL).
+ */
+static void *
+antlr3HashGetI(pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key)
+{
+    ANTLR3_UINT32	    hash;
+    pANTLR3_HASH_BUCKET	    bucket;
+    pANTLR3_HASH_ENTRY	    entry;
+
+    /* First we need to know the hash of the provided key
+     */
+    hash    = (ANTLR3_UINT32)(key % (ANTLR3_INTKEY)(table->modulo));
+
+    /* Knowing the hash, we can find the bucket
+     */
+    bucket  = table->buckets + hash;
+
+    /* Now we can inspect the key at each entry in the bucket
+     * and see if we have a match.
+     */
+    entry   = bucket->entries;
+
+    while   (entry != NULL)
+    {
+	if  (entry->keybase.key.iKey == key)
+	{
+	    /* Match was found, return the data pointer for this entry
+	     */
+	    return  entry->data;
+	}
+	entry = entry->nextEntry;
+    }
+
+    /* If we got here, then we did not find the key
+     */
+    return  NULL;
+}
+
+/** Return the element pointer in the hash table for a particular
+ *  key value, or NULL if it don't exist (or was itself NULL).
+ */
+static void *
+antlr3HashGet(pANTLR3_HASH_TABLE table, void * key)
+{
+    ANTLR3_UINT32	    hash;
+    pANTLR3_HASH_BUCKET	    bucket;
+    pANTLR3_HASH_ENTRY	    entry;
+
+
+    /* First we need to know the hash of the provided key
+     */
+    hash    = antlr3Hash(key, (ANTLR3_UINT32)strlen((const char *)key));
+
+    /* Knowing the hash, we can find the bucket
+     */
+    bucket  = table->buckets + (hash % table->modulo);
+
+    /* Now we can inspect the key at each entry in the bucket
+     * and see if we have a match.
+     */
+    entry   = bucket->entries;
+
+    while   (entry != NULL)
+    {
+	if  (strcmp((const char *)key, (const char *)entry->keybase.key.sKey) == 0)
+	{
+	    /* Match was found, return the data pointer for this entry
+	     */
+	    return  entry->data;
+	}
+	entry = entry->nextEntry;
+    }
+
+    /* If we got here, then we did not find the key
+     */
+    return  NULL;
+}
+
+/** Add the element pointer in to the table, based upon the 
+ *  hash of the provided key.
+ */
+static	ANTLR3_INT32
+antlr3HashPutI(pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *))
+{
+	ANTLR3_UINT32	    hash;
+	pANTLR3_HASH_BUCKET	    bucket;
+	pANTLR3_HASH_ENTRY	    entry;
+	pANTLR3_HASH_ENTRY	    * newPointer;
+
+	/* First we need to know the hash of the provided key
+	*/
+	hash    = (ANTLR3_UINT32)(key % (ANTLR3_INTKEY)(table->modulo));
+
+	/* Knowing the hash, we can find the bucket
+	*/
+	bucket  = table->buckets + hash;
+
+	/* Knowing the bucket, we can traverse the entries until we
+	* we find a NULL pointer or we find that this is already 
+	* in the table and duplicates were not allowed.
+	*/
+	newPointer	= &bucket->entries;
+
+	while   (*newPointer !=  NULL)
+	{
+		/* The value at new pointer is pointing to an existing entry.
+		* If duplicates are allowed then we don't care what it is, but
+		* must reject this add if the key is the same as the one we are
+		* supplied with.
+		*/
+		if  (table->allowDups == ANTLR3_FALSE)
+		{
+			if	((*newPointer)->keybase.key.iKey == key)
+			{
+				return	ANTLR3_ERR_HASHDUP;
+			}
+		}
+
+		/* Point to the next entry pointer of the current entry we
+		* are traversing, if it is NULL we will create our new
+		* structure and point this to it.
+		*/
+		newPointer = &((*newPointer)->nextEntry);
+	}
+
+	/* newPointer is now pointing at the pointer where we need to
+	* add our new entry, so let's crate the entry and add it in.
+	*/
+	entry   = (pANTLR3_HASH_ENTRY)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_HASH_ENTRY));
+
+	if	(entry == NULL)
+	{
+		return	ANTLR3_ERR_NOMEM;
+	}
+
+	entry->data			= element;		/* Install the data element supplied			*/
+	entry->free			= freeptr;		/* Function that knows how to release the entry		*/
+	entry->keybase.type		= ANTLR3_HASH_TYPE_INT;	/* Indicate the key type stored here for when we free	*/
+	entry->keybase.key.iKey	= key;			/* Record the key value					*/
+	entry->nextEntry		= NULL;			/* Ensure that the forward pointer ends the chain	*/
+
+	*newPointer	= entry;    /* Install the next entry in this bucket	*/
+
+	table->count++;
+
+	return  ANTLR3_SUCCESS;
+}
+
+
+/** Add the element pointer in to the table, based upon the 
+ *  hash of the provided key.
+ */
+static	ANTLR3_INT32
+antlr3HashPut(pANTLR3_HASH_TABLE table, void * key, void * element, void (ANTLR3_CDECL *freeptr)(void *))
+{
+	ANTLR3_UINT32	    hash;
+	pANTLR3_HASH_BUCKET	    bucket;
+	pANTLR3_HASH_ENTRY	    entry;
+	pANTLR3_HASH_ENTRY	    * newPointer;
+
+	/* First we need to know the hash of the provided key
+	*/
+	hash    = antlr3Hash(key, (ANTLR3_UINT32)strlen((const char *)key));
+
+	/* Knowing the hash, we can find the bucket
+	*/
+	bucket  = table->buckets + (hash % table->modulo);
+
+	/* Knowign the bucket, we can traverse the entries until we
+	* we find a NULL pointer ofr we find that this is already 
+	* in the table and duplicates were not allowed.
+	*/
+	newPointer	= &bucket->entries;
+
+	while   (*newPointer !=  NULL)
+	{
+		/* The value at new pointer is pointing to an existing entry.
+		* If duplicates are allowed then we don't care what it is, but
+		* must reject this add if the key is the same as the one we are
+		* supplied with.
+		*/
+		if  (table->allowDups == ANTLR3_FALSE)
+		{
+			if	(strcmp((const char*) key, (const char *)(*newPointer)->keybase.key.sKey) == 0)
+			{
+				return	ANTLR3_ERR_HASHDUP;
+			}
+		}
+
+		/* Point to the next entry pointer of the current entry we
+		* are traversing, if it is NULL we will create our new
+		* structure and point this to it.
+		*/
+		newPointer = &((*newPointer)->nextEntry);
+	}
+
+	/* newPointer is now poiting at the pointer where we need to
+	* add our new entry, so let's crate the entry and add it in.
+	*/
+	entry   = (pANTLR3_HASH_ENTRY)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_HASH_ENTRY));
+
+	if	(entry == NULL)
+	{
+		return	ANTLR3_ERR_NOMEM;
+	}
+
+	entry->data			= element;					/* Install the data element supplied				*/
+	entry->free			= freeptr;					/* Function that knows how to release the entry	    */
+	entry->keybase.type	= ANTLR3_HASH_TYPE_STR;     /* Indicate the key type stored here for free()	    */
+    if  (table->doStrdup == ANTLR3_TRUE)
+    {
+        entry->keybase.key.sKey	= ANTLR3_STRDUP(key);	/* Record the key value								*/
+    }
+    else
+    {
+        entry->keybase.key.sKey	= key;                  /* Record the key value								*/
+    }
+	entry->nextEntry		= NULL;					/* Ensure that the forward pointer ends the chain   */
+
+	*newPointer	= entry;    /* Install the next entry in this bucket	*/
+
+	table->count++;
+
+	return  ANTLR3_SUCCESS;
+}
+
+/** \brief Creates an enumeration structure to traverse the hash table.
+ *
+ * \param table Table to enumerate
+ * \return Pointer to enumeration structure.
+ */
+pANTLR3_HASH_ENUM
+antlr3EnumNew	(pANTLR3_HASH_TABLE table)
+{
+    pANTLR3_HASH_ENUM	en;
+
+    /* Allocate structure memory
+     */
+    en    = (pANTLR3_HASH_ENUM) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_HASH_ENUM));
+
+    /* Check that the allocation was good 
+     */
+    if	(en == NULL)
+    {
+	return	(pANTLR3_HASH_ENUM) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
+    }
+    
+    /* Initialize the start pointers
+    */
+    en->table	= table;
+    en->bucket	= 0;				/* First bucket		    */
+    en->entry	= en->table->buckets->entries;	/* First entry to return    */
+
+    /* Special case in that the first bucket may not have anything in it
+     * but the antlr3EnumNext() function expects that the en->entry is
+     * set to the next valid pointer. Hence if it is not a valid element
+     * pointer, attempt to find the next one that is, (table may be empty
+     * of course.
+     */
+    if	(en->entry == NULL)
+    {
+	antlr3EnumNextEntry(en);
+    }
+
+    /* Install the interface
+     */
+    en->free	=  antlr3EnumFree;
+    en->next	=  antlr3EnumNext;
+
+    /* All is good
+     */
+    return  en;
+}
+
+/** \brief Return the next entry in the hashtable being traversed by the supplied
+ *         enumeration.
+ *
+ * \param[in] en Pointer to the enumeration tracking structure
+ * \param key	 Pointer to void pointer, where the key pointer is returned.
+ * \param data	 Pointer to void pointer where the data pointer is returned.
+ * \return 
+ *	- ANTLR3_SUCCESS if there was a next key
+ *	- ANTLR3_FAIL	 if there were no more keys
+ *
+ * \remark
+ *  No checking of input structure is performed!
+ */
+static int
+antlr3EnumNext	(pANTLR3_HASH_ENUM en, pANTLR3_HASH_KEY * key, void ** data)
+{
+    /* If the current entry is valid, then use it
+     */
+    if  (en->bucket >= en->table->modulo)
+    {
+        /* Already exhausted the table
+         */
+        return	ANTLR3_FAIL;
+    }
+
+    /* Pointers are already set to the current entry to return, or
+     * we would not be at this point in the logic flow.
+     */
+    *key	= &(en->entry->keybase);
+    *data	= en->entry->data;
+
+    /* Return pointers are set up, so now we move the element
+     * pointer to the next in the table (if any).
+     */
+    antlr3EnumNextEntry(en);
+
+    return	ANTLR3_SUCCESS;
+}
+
+/** \brief Local function to advance the entry pointer of an enumeration 
+ * structure to the next valid entry (if there is one).
+ *
+ * \param[in] enum Pointer to ANTLR3 enumeration structure returned by antlr3EnumNew()
+ *
+ * \remark
+ *   - The function always leaves the pointers pointing at a valid entry if there
+ *     is one, so if the entry pointer is NULL when this function exits, there were
+ *     no more entries in the table.
+ */
+static void
+antlr3EnumNextEntry(pANTLR3_HASH_ENUM en)
+{
+    pANTLR3_HASH_BUCKET	bucket;
+
+    /* See if the current entry pointer is valid first of all
+     */
+    if	(en->entry != NULL)
+    {
+	/* Current entry was a valid point, see if there is another
+	 * one in the chain.
+	 */
+	if  (en->entry->nextEntry != NULL)
+	{
+	    /* Next entry in the enumeration is just the next entry
+	     * in the chain.
+	     */
+	    en->entry = en->entry->nextEntry;
+	    return;
+	}
+    }
+
+    /* There were no more entries in the current bucket, if there are
+     * more buckets then chase them until we find an entry.
+     */
+    en->bucket++;
+
+    while   (en->bucket < en->table->modulo)
+    {
+	/* There was one more bucket, see if it has any elements in it
+	 */
+	bucket	= en->table->buckets + en->bucket;
+
+	if  (bucket->entries != NULL)
+	{
+	    /* There was an entry in this bucket, so we can use it
+	     * for the next entry in the enumeration.
+	     */
+	    en->entry	= bucket->entries;
+	    return;
+	}
+
+	/* There was nothing in the bucket we just examined, move to the
+	 * next one.
+	 */
+	en->bucket++;
+    }
+
+    /* Here we have exhausted all buckets and the enumeration pointer will 
+     * have its bucket count = table->modulo which signifies that we are done.
+     */
+}
+
+/** \brief Frees up the memory structures that represent a hash table
+ *  enumeration.
+ * \param[in] enum Pointer to ANTLR3 enumeration structure returned by antlr3EnumNew()
+ */
+static void
+antlr3EnumFree	(pANTLR3_HASH_ENUM en)
+{
+    /* Nothing to check, we just free it.
+     */
+    ANTLR3_FREE(en);
+}
+
+/** Given an input key of arbitrary length, return a hash value of
+ *  it. This can then be used (with suitable modulo) to index other
+ *  structures.
+ */
+ANTLR3_API ANTLR3_UINT32
+antlr3Hash(void * key, ANTLR3_UINT32 keylen)
+{
+    /* Accumulate the hash value of the key
+     */
+    ANTLR3_UINT32   hash;
+    pANTLR3_UINT8   keyPtr;
+    ANTLR3_UINT32   i1;
+
+    hash    = 0;
+    keyPtr  = (pANTLR3_UINT8) key;
+
+    /* Iterate the key and accumulate the hash
+     */
+    while(keylen > 0)
+    {
+	hash = (hash << 4) + (*(keyPtr++));
+
+	if ((i1=hash&0xf0000000) != 0)
+	{
+		hash = hash ^ (i1 >> 24);
+		hash = hash ^ i1;
+	}
+	keylen--;
+    }
+
+    return  hash;
+}
+
+ANTLR3_API  pANTLR3_LIST
+antlr3ListNew	(ANTLR3_UINT32 sizeHint)
+{
+    pANTLR3_LIST    list;
+
+    /* Allocate memory
+     */
+    list    = (pANTLR3_LIST)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_LIST));
+
+    if	(list == NULL)
+    {
+	return	(pANTLR3_LIST)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
+    }
+
+    /* Now we need to add a new table
+     */
+    list->table	= antlr3HashTableNew(sizeHint);
+
+    if	(list->table == (pANTLR3_HASH_TABLE)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM))
+    {
+	return	(pANTLR3_LIST)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
+    }
+
+    /* Allocation was good, install interface
+     */
+    list->free	    =  antlr3ListFree;
+    list->del	    =  antlr3ListDelete;
+    list->get	    =  antlr3ListGet;
+    list->add	    =  antlr3ListAdd;
+    list->remove    =  antlr3ListRemove;
+    list->put	    =  antlr3ListPut;
+    list->size	    =  antlr3ListSize;
+
+    return  list;
+}
+
+static ANTLR3_UINT32	antlr3ListSize	    (pANTLR3_LIST list)
+{
+    return  list->table->size(list->table);
+}
+
+static void
+antlr3ListFree	(pANTLR3_LIST list)
+{
+    /* Free the hashtable that stores the list
+     */
+    list->table->free(list->table);
+
+    /* Free the allocation for the list itself
+     */
+    ANTLR3_FREE(list);
+}
+
+static void
+antlr3ListDelete    (pANTLR3_LIST list, ANTLR3_INTKEY key)
+{
+    list->table->delI(list->table, key);
+}
+
+static void *
+antlr3ListGet	    (pANTLR3_LIST list, ANTLR3_INTKEY key)
+{
+    return list->table->getI(list->table, key);
+}
+
+/** Add the supplied element to the list, at the next available key
+ */
+static ANTLR3_INT32	antlr3ListAdd   (pANTLR3_LIST list, void * element, void (ANTLR3_CDECL *freeptr)(void *))
+{
+    ANTLR3_INTKEY   key;
+
+    key	    = list->table->size(list->table) + 1;
+    return list->put(list, key, element, freeptr);
+}
+
+/** Remove from the list, but don't free the element, just send it back to the
+ *  caller.
+ */
+static	void *
+antlr3ListRemove	    (pANTLR3_LIST list, ANTLR3_INTKEY key)
+{
+    pANTLR3_HASH_ENTRY	    entry;
+
+    entry = list->table->removeI(list->table, key);
+
+    if	(entry != NULL)
+    {
+        return  entry->data;
+    }
+    else
+    {
+	return	NULL;
+    }
+}
+
+static	ANTLR3_INT32
+antlr3ListPut	    (pANTLR3_LIST list, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *))
+{
+    return  list->table->putI(list->table, key, element, freeptr);
+}
+
+ANTLR3_API  pANTLR3_STACK
+antlr3StackNew	(ANTLR3_UINT32 sizeHint)
+{
+    pANTLR3_STACK   stack;
+
+    /* Allocate memory
+     */
+    stack    = (pANTLR3_STACK)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_STACK));
+
+    if	(stack == NULL)
+    {
+	return	(pANTLR3_STACK)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
+    }
+
+    /* Now we need to add a new table
+     */
+    stack->vector   = antlr3VectorNew(sizeHint);
+    stack->top	    = NULL;
+
+    if	(stack->vector == (pANTLR3_VECTOR)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM))
+    {
+	return	(pANTLR3_STACK)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
+    }
+
+    /* Looks good, now add the interface
+     */
+    stack->get	=  antlr3StackGet;
+    stack->free	=  antlr3StackFree;
+    stack->pop	=  antlr3StackPop;
+    stack->push	=  antlr3StackPush;
+    stack->size	=  antlr3StackSize;
+    stack->peek	=  antlr3StackPeek;
+
+    return  stack;
+}
+
+static ANTLR3_UINT32	antlr3StackSize	    (pANTLR3_STACK stack)
+{
+    return  stack->vector->count;
+}
+
+
+static void
+antlr3StackFree	(pANTLR3_STACK  stack)
+{
+    /* Free the list that supports the stack
+     */
+    stack->vector->free(stack->vector);
+    stack->vector   = NULL;
+    stack->top	    = NULL;
+
+    ANTLR3_FREE(stack);
+}
+
+static void *
+antlr3StackPop	(pANTLR3_STACK	stack)
+{
+    // Delete the element that is currently at the top of the stack
+    //
+    stack->vector->del(stack->vector, stack->vector->count - 1);
+
+    // And get the element that is the now the top of the stack (if anything)
+    // NOTE! This is not quite like a 'real' stack, which would normally return you
+    // the current top of the stack, then remove it from the stack.
+    // TODO: Review this, it is correct for follow sets which is what this was done for
+    //       but is not as obvious when using it as a 'real'stack.
+    //
+    stack->top = stack->vector->get(stack->vector, stack->vector->count - 1);
+    return stack->top;
+}
+
+static void *
+antlr3StackGet	(pANTLR3_STACK stack, ANTLR3_INTKEY key)
+{
+    return  stack->vector->get(stack->vector, (ANTLR3_UINT32)key);
+}
+
+static void *
+antlr3StackPeek	(pANTLR3_STACK	stack)
+{
+    return  stack->top;
+}
+
+static ANTLR3_BOOLEAN 
+antlr3StackPush	(pANTLR3_STACK stack, void * element, void (ANTLR3_CDECL *freeptr)(void *))
+{
+    stack->top	= element;
+    return (ANTLR3_BOOLEAN)(stack->vector->add(stack->vector, element, freeptr));
+}
+
+ANTLR3_API  pANTLR3_VECTOR
+antlr3VectorNew	(ANTLR3_UINT32 sizeHint)
+{
+	pANTLR3_VECTOR  vector;
+
+
+	// Allocate memory for the vector structure itself
+	//
+	vector  = (pANTLR3_VECTOR) ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR)));
+
+	if	(vector == NULL)
+	{
+		return	(pANTLR3_VECTOR)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
+	}
+
+	// Now fill in the defaults
+	//
+    antlr3SetVectorApi(vector, sizeHint);
+
+	// And everything is hunky dory
+	//
+	return  vector;
+}
+
+ANTLR3_API void
+antlr3SetVectorApi  (pANTLR3_VECTOR vector, ANTLR3_UINT32 sizeHint)
+{
+    ANTLR3_UINT32   initialSize;
+
+    // Allow vectors to be guessed by ourselves, so input size can be zero
+    //
+    if	(sizeHint > ANTLR3_VECTOR_INTERNAL_SIZE)
+    {
+        initialSize = sizeHint;
+    }
+    else
+    {
+        initialSize = ANTLR3_VECTOR_INTERNAL_SIZE;
+    }
+
+    if  (sizeHint > ANTLR3_VECTOR_INTERNAL_SIZE)
+    {
+        vector->elements	= (pANTLR3_VECTOR_ELEMENT)ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR_ELEMENT) * initialSize));
+    }
+    else
+    {
+        vector->elements    = vector->internal;
+    }
+
+    if	(vector->elements == NULL)
+    {
+        ANTLR3_FREE(vector);
+        return;
+    }
+
+    // Memory allocated successfully
+    //
+    vector->count			= 0;			// No entries yet of course
+    vector->elementsSize    = initialSize;  // Available entries
+
+    // Now we can install the API
+    //
+    vector->add	    = antlr3VectorAdd;
+    vector->del	    = antlr3VectorDel;
+    vector->get	    = antlr3VectorGet;
+    vector->free    = antlr3VectorFree;
+    vector->set	    = antlr3VectorSet;
+    vector->remove  = antrl3VectorRemove;
+    vector->clear   = antlr3VectorClear;
+    vector->size    = antlr3VectorSize;
+    vector->swap    = antlr3VectorSwap;
+
+    // Assume that this is not a factory made vector
+    //
+    vector->factoryMade	= ANTLR3_FALSE;
+}
+
+// Clear the entries in a vector.
+// Clearing the vector leaves its capacity the same but
+// it walks the entries first to see if any of them
+// have a free routine that must be called.
+//
+static	void				
+antlr3VectorClear	(pANTLR3_VECTOR vector)
+{
+	ANTLR3_UINT32   entry;
+
+	// We must traverse every entry in the vector and if it has
+	// a pointer to a free function then we call it with the
+	// the entry pointer
+	//
+	for	(entry = 0; entry < vector->count; entry++)
+	{
+		if  (vector->elements[entry].freeptr != NULL)
+		{
+			vector->elements[entry].freeptr(vector->elements[entry].element);
+		}
+		vector->elements[entry].freeptr    = NULL;
+		vector->elements[entry].element    = NULL;
+	}
+
+	// Having called any free pointers, we just reset the entry count
+	// back to zero.
+	//
+	vector->count	= 0;
+}
+
+static	
+void	ANTLR3_CDECL	antlr3VectorFree    (pANTLR3_VECTOR vector)
+{
+	ANTLR3_UINT32   entry;
+
+	// We must traverse every entry in the vector and if it has
+	// a pointer to a free function then we call it with the
+	// the entry pointer
+	//
+	for	(entry = 0; entry < vector->count; entry++)
+	{
+		if  (vector->elements[entry].freeptr != NULL)
+		{
+			vector->elements[entry].freeptr(vector->elements[entry].element);
+		}
+		vector->elements[entry].freeptr    = NULL;
+		vector->elements[entry].element    = NULL;
+	}
+
+	if	(vector->factoryMade == ANTLR3_FALSE)
+	{
+		// The entries are freed, so free the element allocation
+		//
+        if  (vector->elementsSize > ANTLR3_VECTOR_INTERNAL_SIZE)
+        {
+            ANTLR3_FREE(vector->elements);
+        }
+		vector->elements = NULL;
+
+		// Finally, free the allocation for the vector itself
+		//
+		ANTLR3_FREE(vector);
+	}
+}
+
+static	void		antlr3VectorDel	    (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry)
+{
+	// Check this is a valid request first
+	//
+	if	(entry >= vector->count)
+	{
+		return;
+	}
+
+	// Valid request, check for free pointer and call it if present
+	//
+	if	(vector->elements[entry].freeptr != NULL)
+	{
+		vector->elements[entry].freeptr(vector->elements[entry].element);
+		vector->elements[entry].freeptr    = NULL;
+	}
+
+	if	(entry == vector->count - 1)
+	{
+		// Ensure the pointer is never reused by accident, but otherwise just 
+		// decrement the pointer.
+		//
+		vector->elements[entry].element    = NULL;
+	}
+	else
+	{
+		// Need to shuffle trailing pointers back over the deleted entry
+		//
+		ANTLR3_MEMMOVE(vector->elements + entry, vector->elements + entry + 1, sizeof(ANTLR3_VECTOR_ELEMENT) * (vector->count - entry - 1));
+	}
+
+	// One less entry in the vector now
+	//
+	vector->count--;
+}
+
+static	void *		antlr3VectorGet     (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry)
+{
+	// Ensure this is a valid request
+	//
+	if	(entry < vector->count)
+	{
+		return	vector->elements[entry].element;
+	}
+	else
+	{
+		// I know nothing, Mr. Fawlty!
+		//
+		return	NULL;
+	}
+}
+
+/// Remove the entry from the vector, but do not free any entry, even if it has
+/// a free pointer.
+///
+static	void *		antrl3VectorRemove  (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry)
+{
+	void * element;
+
+	// Check this is a valid request first 
+	//
+	if	(entry >= vector->count)
+	{
+		return NULL;
+	}
+
+	// Valid request, return the sorted pointer
+	//
+
+	element				    = vector->elements[entry].element;
+
+	if	(entry == vector->count - 1)
+	{
+		// Ensure the pointer is never reused by accident, but otherwise just 
+		// decrement the pointer.
+		///
+		vector->elements[entry].element    = NULL;
+		vector->elements[entry].freeptr    = NULL;
+	}
+	else
+	{
+		// Need to shuffle trailing pointers back over the deleted entry
+		//
+		ANTLR3_MEMMOVE(vector->elements + entry, vector->elements + entry + 1, sizeof(ANTLR3_VECTOR_ELEMENT) * (vector->count - entry - 1));
+	}
+
+	// One less entry in the vector now
+	//
+	vector->count--;
+
+	return  element;
+}
+
+static  void
+antlr3VectorResize  (pANTLR3_VECTOR vector, ANTLR3_UINT32 hint)
+{
+	ANTLR3_UINT32	newSize;
+
+	// Need to resize the element pointers. We double the allocation
+	// we already have unless asked for a specific increase.
+    //
+    if (hint == 0 || hint < vector->elementsSize)
+    {
+        newSize = vector->elementsSize * 2;
+    }
+    else
+    {
+        newSize = hint * 2;
+    }
+
+    // Now we know how many we need, so we see if we have just expanded
+    // past the built in vector elements or were already past that
+    //
+    if  (vector->elementsSize > ANTLR3_VECTOR_INTERNAL_SIZE)
+    {
+        // We were already larger than the internal size, so we just
+        // use realloc so that the pointers are copied for us
+        //
+        vector->elements	= (pANTLR3_VECTOR_ELEMENT)ANTLR3_REALLOC(vector->elements, (sizeof(ANTLR3_VECTOR_ELEMENT)* newSize));
+    }
+    else
+    {
+        // The current size was less than or equal to the internal array size and as we always start
+        // with a size that is at least the maximum internal size, then we must need to allocate new memory
+        // for external pointers. We don't want to take the time to calculate if a requested element
+        // is part of the internal or external entries, so we copy the internal ones to the new space
+        //
+        vector->elements	= (pANTLR3_VECTOR_ELEMENT)ANTLR3_MALLOC((sizeof(ANTLR3_VECTOR_ELEMENT)* newSize));
+        ANTLR3_MEMCPY(vector->elements, vector->internal, ANTLR3_VECTOR_INTERNAL_SIZE * sizeof(ANTLR3_VECTOR_ELEMENT));
+    }
+
+	vector->elementsSize	= newSize;
+}
+
+/// Add the supplied pointer and freeing function pointer to the list,
+/// expanding the vector if needed.
+///
+static	ANTLR3_UINT32    antlr3VectorAdd	    (pANTLR3_VECTOR vector, void * element, void (ANTLR3_CDECL *freeptr)(void *))
+{
+	// Do we need to resize the vector table?
+	//
+	if	(vector->count == vector->elementsSize)
+	{
+		antlr3VectorResize(vector, 0);	    // Give no hint, we let it add 1024 or double it
+	}
+
+	// Insert the new entry
+	//
+	vector->elements[vector->count].element	= element;
+	vector->elements[vector->count].freeptr	= freeptr;
+
+	vector->count++;	    // One more element counted
+
+	return  (ANTLR3_UINT32)(vector->count);
+
+}
+
+/// Replace the element at the specified entry point with the supplied
+/// entry.
+///
+static	ANTLR3_UINT32    
+antlr3VectorSet	    (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry, void * element, void (ANTLR3_CDECL *freeptr)(void *), ANTLR3_BOOLEAN freeExisting)
+{
+
+	// If the vector is currently not big enough, then we expand it
+	//
+	if (entry >= vector->elementsSize)
+	{
+		antlr3VectorResize(vector, entry);	// We will get at least this many 
+	}
+
+	// Valid request, replace the current one, freeing any prior entry if told to
+	//
+	if	(		entry < vector->count						// If actually replacing an element
+			&&	freeExisting								// And told to free any existing element
+			&&	vector->elements[entry].freeptr != NULL		// And the existing element has a free pointer
+		)
+	{
+		vector->elements[entry].freeptr(vector->elements[entry].element);
+	}
+
+	// Install the new pointers
+	//
+	vector->elements[entry].freeptr	= freeptr;
+	vector->elements[entry].element	= element;
+
+	if (entry >= vector->count)
+	{
+		vector->count = entry + 1;
+	}
+	return  (ANTLR3_UINT32)(entry);	    // Indicates the replacement was successful
+
+}
+
+/// Replace the element at the specified entry point with the supplied
+/// entry.
+///
+static	ANTLR3_BOOLEAN
+antlr3VectorSwap	    (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry1, ANTLR3_UINT32 entry2)
+{
+
+    void               * tempEntry;
+    void (ANTLR3_CDECL *freeptr)(void *);
+
+	// If the vector is currently not big enough, then we do nothing
+	//
+	if (entry1 >= vector->elementsSize || entry2 >= vector->elementsSize)
+	{
+        return ANTLR3_FALSE;
+	}
+
+	// Valid request, swap them
+	//
+    tempEntry   = vector->elements[entry1].element;
+    freeptr     = vector->elements[entry1].freeptr;
+
+	// Install the new pointers
+	//
+    vector->elements[entry1].freeptr	= vector->elements[entry2].freeptr;
+	vector->elements[entry1].element	= vector->elements[entry2].element;
+
+	vector->elements[entry2].freeptr	= freeptr;
+	vector->elements[entry2].element	= tempEntry;
+
+	return  ANTLR3_TRUE;
+
+}
+
+static	ANTLR3_UINT32   antlr3VectorSize    (pANTLR3_VECTOR vector)
+{
+    return  vector->count;
+}
+
+#ifdef ANTLR3_WINDOWS
+#pragma warning	(push)
+#pragma warning (disable : 4100)
+#endif
+/// Vector factory creation
+///
+ANTLR3_API pANTLR3_VECTOR_FACTORY
+antlr3VectorFactoryNew	    (ANTLR3_UINT32 sizeHint)
+{
+	pANTLR3_VECTOR_FACTORY  factory;
+
+	// Allocate memory for the factory
+	//
+	factory = (pANTLR3_VECTOR_FACTORY)ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR_FACTORY)));
+
+	if	(factory == NULL)
+	{
+		return	NULL;
+	}
+
+	// Factory memory is good, so create a new vector pool
+	//
+    factory->pools      = NULL;
+    factory->thisPool   = -1;
+
+    newPool(factory);
+
+    // Initialize the API, ignore the hint as this algorithm does
+    // a better job really.
+    //
+    antlr3SetVectorApi(&(factory->unTruc), ANTLR3_VECTOR_INTERNAL_SIZE);
+    
+    factory->unTruc.factoryMade = ANTLR3_TRUE;
+
+	// Install the factory API
+	//
+	factory->close			= closeVectorFactory;
+	factory->newVector		= newVector;
+	factory->returnVector	= returnVector;
+
+	// Create a stack to accumulate reusable vectors
+	//
+	factory->freeStack		= antlr3StackNew(16);
+	return  factory;
+}
+#ifdef ANTLR3_WINDOWS
+#pragma warning	(pop)
+#endif
+
+static	void				
+returnVector		(pANTLR3_VECTOR_FACTORY factory, pANTLR3_VECTOR vector)
+{
+	// First we need to clear out anything that is still in the vector
+	//
+	vector->clear(vector);
+
+	// We have a free stack available so we can add the vector we were
+	// given into the free chain. The vector has to have come from this
+	// factory, so we already know how to release its memory when it
+	// dies by virtue of the factory being closed.
+	//
+	factory->freeStack->push(factory->freeStack, vector, NULL);
+
+	// TODO: remove this line once happy printf("Returned vector %08X to the pool, stack size is %d\n", vector, factory->freeStack->size(factory->freeStack));
+}
+
+static void
+newPool(pANTLR3_VECTOR_FACTORY factory)
+{
+    /* Increment factory count
+     */
+    factory->thisPool++;
+
+    /* Ensure we have enough pointers allocated
+     */
+    factory->pools = (pANTLR3_VECTOR *)
+		     ANTLR3_REALLOC(	(void *)factory->pools,	    /* Current pools pointer (starts at NULL)	*/
+					(ANTLR3_UINT32)((factory->thisPool + 1) * sizeof(pANTLR3_VECTOR *))	/* Memory for new pool pointers */
+					);
+
+    /* Allocate a new pool for the factory
+     */
+    factory->pools[factory->thisPool]	=
+			    (pANTLR3_VECTOR)
+				ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR) * ANTLR3_FACTORY_VPOOL_SIZE));
+
+
+    /* Reset the counters
+     */
+    factory->nextVector	= 0;
+
+    /* Done
+     */
+    return;
+}
+
+static  void		
+closeVectorFactory  (pANTLR3_VECTOR_FACTORY factory)
+{
+    pANTLR3_VECTOR      pool;
+    ANTLR3_INT32        poolCount;
+    ANTLR3_UINT32       limit;
+    ANTLR3_UINT32       vector;
+    pANTLR3_VECTOR      check;
+
+	// First see if we have a free chain stack to release?
+	//
+	if	(factory->freeStack != NULL)
+	{
+		factory->freeStack->free(factory->freeStack);
+	}
+
+    /* We iterate the vector pools one at a time
+     */
+    for (poolCount = 0; poolCount <= factory->thisPool; poolCount++)
+    {
+        /* Pointer to current pool
+         */
+        pool = factory->pools[poolCount];
+
+        /* Work out how many tokens we need to check in this pool.
+         */
+        limit = (poolCount == factory->thisPool ? factory->nextVector : ANTLR3_FACTORY_VPOOL_SIZE);
+
+        /* Marginal condition, we might be at the start of a brand new pool
+         * where the nextToken is 0 and nothing has been allocated.
+         */
+        if (limit > 0)
+        {
+            /* We have some vectors allocated from this pool
+             */
+            for (vector = 0; vector < limit; vector++)
+            {
+                /* Next one in the chain
+                 */
+                check = pool + vector;
+
+                // Call the free function on each of the vectors in the pool,
+                // which in turn will cause any elements it holds that also have a free
+                // pointer to be freed. However, because any vector may be in any other
+                // vector, we don't free the element allocations yet. We do that in a
+                // a specific pass, coming up next. The vector free function knows that
+                // this is a factory allocated pool vector and so it won't free things it
+                // should not.
+                //
+                check->free(check);
+            }
+        }
+    }
+
+    /* We iterate the vector pools one at a time once again, but this time
+     * we are going to free up any allocated element pointers. Note that we are doing this
+     * so that we do not try to release vectors twice. When building ASTs we just copy
+     * the vectors all over the place and they may be embedded in this vector pool
+     * numerous times.
+     */
+    for (poolCount = 0; poolCount <= factory->thisPool; poolCount++)
+    {
+        /* Pointer to current pool
+         */
+        pool = factory->pools[poolCount];
+
+        /* Work out how many tokens we need to check in this pool.
+         */
+        limit = (poolCount == factory->thisPool ? factory->nextVector : ANTLR3_FACTORY_VPOOL_SIZE);
+
+        /* Marginal condition, we might be at the start of a brand new pool
+         * where the nextToken is 0 and nothing has been allocated.
+         */
+        if (limit > 0)
+        {
+            /* We have some vectors allocated from this pool
+             */
+            for (vector = 0; vector < limit; vector++)
+            {
+                /* Next one in the chain
+                 */
+                check = pool + vector;
+
+                // Anything in here should be factory made, but we do this just
+                // to triple check. We just free up the elements if they were
+                // allocated beyond the internal size.
+                //
+                if (check->factoryMade == ANTLR3_TRUE && check->elementsSize > ANTLR3_VECTOR_INTERNAL_SIZE)
+                {
+                    ANTLR3_FREE(check->elements);
+                    check->elements = NULL;
+                }
+            }
+        }
+
+        // We can now free this pool allocation as we have called free on every element in every vector
+        // and freed any memory for pointers the grew beyond the internal size limit.
+        //
+        ANTLR3_FREE(factory->pools[poolCount]);
+        factory->pools[poolCount] = NULL;
+    }
+
+    /* All the pools are deallocated we can free the pointers to the pools
+     * now.
+     */
+    ANTLR3_FREE(factory->pools);
+
+    /* Finally, we can free the space for the factory itself
+     */
+    ANTLR3_FREE(factory);
+
+}
+
+static pANTLR3_VECTOR
+newVector(pANTLR3_VECTOR_FACTORY factory)
+{
+    pANTLR3_VECTOR vector;
+
+	// If we have anything on the re claim stack, reuse it
+	//
+	vector = factory->freeStack->peek(factory->freeStack);
+
+	if  (vector != NULL)
+	{
+		// Cool we got something we could reuse
+		//
+		factory->freeStack->pop(factory->freeStack);
+
+		// TODO: remove this line once happy printf("Reused vector %08X from stack, size is now %d\n", vector, factory->freeStack->size(factory->freeStack));
+		return vector;
+
+	}
+
+	// See if we need a new vector pool before allocating a new
+    // one
+    //
+    if (factory->nextVector >= ANTLR3_FACTORY_VPOOL_SIZE)
+    {
+        // We ran out of vectors in the current pool, so we need a new pool
+        //
+        newPool(factory);
+    }
+
+    // Assuming everything went well (we are trying for performance here so doing minimal
+    // error checking. Then we can work out what the pointer is to the next vector.
+    //
+    vector = factory->pools[factory->thisPool] + factory->nextVector;
+    factory->nextVector++;
+
+    // We have our token pointer now, so we can initialize it to the predefined model.
+    //
+    antlr3SetVectorApi(vector, ANTLR3_VECTOR_INTERNAL_SIZE);
+    vector->factoryMade = ANTLR3_TRUE;
+
+    // We know that the pool vectors are created at the default size, which means they
+    // will start off using their internal entry pointers. We must intialize our pool vector
+    // to point to its own internal entry table and not the pre-made one.
+    //
+    vector->elements = vector->internal;
+
+		// TODO: remove this line once happy printf("Used a new vector at %08X from the pools as nothing on the reusue stack\n", vector);
+
+    // And we are done
+    //
+    return vector;
+}
+
+/** Array of left most significant bit positions for an 8 bit
+ *  element provides an efficient way to find the highest bit
+ *  that is set in an n byte value (n>0). Assuming the values will all hit the data cache,
+ *  coding without conditional elements should allow branch
+ *  prediction to work well and of course a parallel instruction cache
+ *  will whip through this. Otherwise we must loop shifting a one
+ *  bit and masking. The values we tend to be placing in out integer
+ *  patricia trie are usually a lot lower than the 64 bits we
+ *  allow for the key allows. Hence there is a lot of redundant looping and
+ *  shifting in a while loop. Whereas, the lookup table is just
+ *  a few ands and indirect lookups, while testing for 0. This
+ *  is likely to be done in parallel on many processors available
+ *  when I wrote this. If this code survives as long as yacc, then
+ *  I may already be dead by the time you read this and maybe there is
+ *  a single machine instruction to perform the operation. What
+ *  else are you going to do with all those transistors? Jim 2007
+ *
+ * The table is probably obvious but it is just the number 0..7
+ * of the MSB in each integer value 0..256
+ */
+static ANTLR3_UINT8 bitIndex[256] = 
+{ 
+    0,													// 0 - Just for padding
+    0,													// 1
+    1, 1,												// 2..3
+    2, 2, 2, 2,											// 4..7
+    3, 3, 3, 3, 3, 3, 3, 3,								// 8+
+    4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,	    // 16+
+    5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,	    // 32+
+	5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,	    
+    6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,	    // 64+
+	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 
+    7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,	    // 128+
+	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
+	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
+};
+
+/** Rather than use the bit index of a trie node to shift
+ *  0x01 left that many times, then & with the result, it is
+ *  faster to use the bit index as an index into this table
+ *  which holds precomputed masks for any of the 64 bits
+ *  we need to mask off singly. The data values will stay in
+ *  cache while ever a trie is in heavy use, such as in
+ *  memoization. It is also pretty enough to be ASCII art.
+ */
+static ANTLR3_UINT64 bitMask[64] = 
+{
+    0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000004ULL, 0x0000000000000008ULL,
+    0x0000000000000010ULL, 0x0000000000000020ULL, 0x0000000000000040ULL, 0x0000000000000080ULL,
+    0x0000000000000100ULL, 0x0000000000000200ULL, 0x0000000000000400ULL, 0x0000000000000800ULL,
+    0x0000000000001000ULL, 0x0000000000002000ULL, 0x0000000000004000ULL, 0x0000000000008000ULL,
+    0x0000000000010000ULL, 0x0000000000020000ULL, 0x0000000000040000ULL, 0x0000000000080000ULL,
+    0x0000000000100000ULL, 0x0000000000200000ULL, 0x0000000000400000ULL, 0x0000000000800000ULL,
+    0x0000000001000000ULL, 0x0000000002000000ULL, 0x0000000004000000ULL, 0x0000000008000000ULL,
+    0x0000000010000000ULL, 0x0000000020000000ULL, 0x0000000040000000ULL, 0x0000000080000000ULL,
+    0x0000000100000000ULL, 0x0000000200000000ULL, 0x0000000400000000ULL, 0x0000000800000000ULL,
+    0x0000001000000000ULL, 0x0000002000000000ULL, 0x0000004000000000ULL, 0x0000008000000000ULL,
+    0x0000010000000000ULL, 0x0000020000000000ULL, 0x0000040000000000ULL, 0x0000080000000000ULL,
+    0x0000100000000000ULL, 0x0000200000000000ULL, 0x0000400000000000ULL, 0x0000800000000000ULL,
+    0x0001000000000000ULL, 0x0002000000000000ULL, 0x0004000000000000ULL, 0x0008000000000000ULL,
+    0x0010000000000000ULL, 0x0020000000000000ULL, 0x0040000000000000ULL, 0x0080000000000000ULL,
+    0x0100000000000000ULL, 0x0200000000000000ULL, 0x0400000000000000ULL, 0x0800000000000000ULL,
+    0x1000000000000000ULL, 0x2000000000000000ULL, 0x4000000000000000ULL, 0x8000000000000000ULL
+};
+
+/* INT TRIE Implementation of depth 64 bits, being the number of bits
+ * in a 64 bit integer. 
+ */
+
+pANTLR3_INT_TRIE
+antlr3IntTrieNew(ANTLR3_UINT32 depth)
+{
+	pANTLR3_INT_TRIE	trie;
+
+	trie    = (pANTLR3_INT_TRIE) ANTLR3_CALLOC(1, sizeof(ANTLR3_INT_TRIE));	/* Base memory required	*/
+
+	if (trie == NULL)
+	{
+		return	(pANTLR3_INT_TRIE) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
+	}
+
+	/* Now we need to allocate the root node. This makes it easier
+	 * to use the tree as we don't have to do anything special 
+	 * for the root node.
+	 */
+	trie->root	= (pANTLR3_INT_TRIE_NODE) ANTLR3_CALLOC(1, sizeof(ANTLR3_INT_TRIE));
+
+	if (trie->root == NULL)
+	{
+		ANTLR3_FREE(trie);
+		return	(pANTLR3_INT_TRIE) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
+	}
+
+	trie->add	= intTrieAdd;
+	trie->del	= intTrieDel;
+	trie->free	= intTrieFree;
+	trie->get	= intTrieGet;
+
+	/* Now we seed the root node with the index being the
+	 * highest left most bit we want to test, which limits the
+	 * keys in the trie. This is the trie 'depth'. The limit for
+	 * this implementation is 63 (bits 0..63).
+	 */
+	trie->root->bitNum = depth;
+
+	/* And as we have nothing in here yet, we set both child pointers
+	 * of the root node to point back to itself.
+	 */
+	trie->root->leftN	= trie->root;
+	trie->root->rightN	= trie->root;
+	trie->count			= 0;
+
+	/* Finally, note that the key for this root node is 0 because
+	 * we use calloc() to initialise it.
+	 */
+
+	return trie;
+}
+
+/** Search the int Trie and return a pointer to the first bucket indexed
+ *  by the key if it is contained in the trie, otherwise NULL.
+ */
+static	pANTLR3_TRIE_ENTRY   
+intTrieGet	(pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key)
+{
+	pANTLR3_INT_TRIE_NODE    thisNode; 
+	pANTLR3_INT_TRIE_NODE    nextNode; 
+
+	if (trie->count == 0)
+	{
+		return NULL;	    /* Nothing in this trie yet	*/
+	}
+	/* Starting at the root node in the trie, compare the bit index
+	 * of the current node with its next child node (starts left from root).
+	 * When the bit index of the child node is greater than the bit index of the current node
+	 * then by definition (as the bit index decreases as we descent the trie)
+	 * we have reached a 'backward' pointer. A backward pointer means we
+	 * have reached the only node that can be reached by the bits given us so far
+	 * and it must either be the key we are looking for, or if not then it
+	 * means the entry was not in the trie, and we return NULL. A backward pointer
+	 * points back in to the tree structure rather than down (deeper) within the
+	 * tree branches.
+	 */
+	thisNode	= trie->root;		/* Start at the root node		*/
+	nextNode	= thisNode->leftN;	/* Examine the left node from the root	*/
+
+	/* While we are descending the tree nodes...
+	 */
+	while (thisNode->bitNum > nextNode->bitNum)
+	{
+		/* Next node now becomes the new 'current' node
+		 */
+		thisNode    = nextNode;
+
+		/* We now test the bit indicated by the bitmap in the next node
+		 * in the key we are searching for. The new next node is the
+		 * right node if that bit is set and the left node it is not.
+		 */
+		if (key & bitMask[nextNode->bitNum])
+		{
+			nextNode = nextNode->rightN;	/* 1 is right	*/
+		}
+		else
+		{
+			nextNode = nextNode->leftN;		/* 0 is left	*/
+		}
+	}
+
+	/* Here we have reached a node where the bitMap index is lower than
+	 * its parent. This means it is pointing backward in the tree and
+	 * must therefore be a terminal node, being the only point than can
+	 * be reached with the bits seen so far. It is either the actual key
+	 * we wanted, or if that key is not in the trie it is another key
+	 * that is currently the only one that can be reached by those bits.
+	 * That situation would obviously change if the key was to be added
+	 * to the trie.
+	 *
+	 * Hence it only remains to test whether this is actually the key or not.
+	 */
+	if (nextNode->key == key)
+	{
+		/* This was the key, so return the entry pointer
+		 */
+		return	nextNode->buckets;
+	}
+	else
+	{
+		return	NULL;	/* That key is not in the trie (note that we set the pointer to -1 if no payload) */
+	}
+}
+
+
+static	ANTLR3_BOOLEAN		
+intTrieDel	(pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key)
+{
+    pANTLR3_INT_TRIE_NODE   p;
+
+    p=trie->root;
+    key = key;
+
+    return ANTLR3_FALSE;
+}
+
+/** Add an entry into the INT trie.
+ *  Basically we descend the trie as we do when searching it, which will
+ *  locate the only node in the trie that can be reached by the bit pattern of the
+ *  key. If the key is actually at that node, then if the trie accepts duplicates
+ *  we add the supplied data in a new chained bucket to that data node. If it does
+ *  not accept duplicates then we merely return FALSE in case the caller wants to know
+ *  whether the key was already in the trie.
+ *  If the node we locate is not the key we are looking to add, then we insert a new node
+ *  into the trie with a bit index of the leftmost differing bit and the left or right 
+ *  node pointing to itself or the data node we are inserting 'before'. 
+ */
+static	ANTLR3_BOOLEAN		
+intTrieAdd	(pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key, ANTLR3_UINT32 type, ANTLR3_INTKEY intVal, void * data, void (ANTLR3_CDECL *freeptr)(void *))
+{
+	pANTLR3_INT_TRIE_NODE   thisNode;
+	pANTLR3_INT_TRIE_NODE   nextNode;
+	pANTLR3_INT_TRIE_NODE   entNode;
+	ANTLR3_UINT32			depth;
+	pANTLR3_TRIE_ENTRY	    newEnt;
+	pANTLR3_TRIE_ENTRY	    nextEnt;
+	ANTLR3_INTKEY		    xorKey;
+
+	/* Cache the bit depth of this trie, which is always the highest index, 
+	 * which is in the root node
+	 */
+	depth   = trie->root->bitNum;
+
+	thisNode	= trie->root;		/* Start with the root node	    */
+	nextNode	= trie->root->leftN;	/* And assume we start to the left  */
+
+	/* Now find the only node that can be currently reached by the bits in the
+	 * key we are being asked to insert.
+	 */
+	while (thisNode->bitNum  > nextNode->bitNum)
+	{
+		/* Still descending the structure, next node becomes current.
+		 */
+		thisNode = nextNode;
+
+		if (key & bitMask[nextNode->bitNum])
+		{
+			/* Bit at the required index was 1, so travers the right node from here
+			 */
+			nextNode = nextNode->rightN;
+		}
+		else
+		{
+			/* Bit at the required index was 0, so we traverse to the left
+			 */
+			nextNode = nextNode->leftN;
+		}
+	}
+	/* Here we have located the only node that can be reached by the
+	 * bits in the requested key. It could in fact be that key or the node
+	 * we need to use to insert the new key.
+	 */
+	if (nextNode->key == key)
+	{
+		/* We have located an exact match, but we will only append to the bucket chain
+		 * if this trie accepts duplicate keys.
+		 */
+		if (trie->allowDups ==ANTLR3_TRUE)
+		{
+			/* Yes, we are accepting duplicates
+			 */
+			newEnt = (pANTLR3_TRIE_ENTRY)ANTLR3_CALLOC(1, sizeof(ANTLR3_TRIE_ENTRY));
+
+			if (newEnt == NULL)
+			{
+				/* Out of memory, all we can do is return the fact that the insert failed.
+				 */
+				return	ANTLR3_FALSE;
+			}
+
+			/* Otherwise insert this in the chain
+			*/
+			newEnt->type	= type;
+			newEnt->freeptr	= freeptr;
+			if (type == ANTLR3_HASH_TYPE_STR)
+			{
+				newEnt->data.ptr = data;
+			}
+			else
+			{
+				newEnt->data.intVal = intVal;
+			}
+
+			/* We want to be able to traverse the stored elements in the order that they were
+			 * added as duplicate keys. We might need to revise this opinion if we end up having many duplicate keys
+			 * as perhaps reverse order is just as good, so long as it is ordered.
+			 */
+			nextEnt = nextNode->buckets;
+			while (nextEnt->next != NULL)
+			{
+				nextEnt = nextEnt->next;    
+			}
+			nextEnt->next = newEnt;
+
+			trie->count++;
+			return  ANTLR3_TRUE;
+		}
+		else
+		{
+			/* We found the key is already there and we are not allowed duplicates in this
+			 * trie.
+			 */
+			return  ANTLR3_FALSE;
+		}
+	}
+
+	/* Here we have discovered the only node that can be reached by the bits in the key
+	 * but we have found that this node is not the key we need to insert. We must find the
+	 * the leftmost bit by which the current key for that node and the new key we are going 
+	 * to insert, differ. While this nested series of ifs may look a bit strange, experimentation
+	 * showed that it allows a machine code path that works well with predicated execution
+	 */
+	xorKey = (key ^ nextNode->key);   /* Gives 1 bits only where they differ then we find the left most 1 bit*/
+
+	/* Most common case is a 32 bit key really
+	 */
+#ifdef	ANTLR3_USE_64BIT
+	if	(xorKey & 0xFFFFFFFF00000000)
+	{
+		if  (xorKey & 0xFFFF000000000000)
+		{
+			if	(xorKey & 0xFF00000000000000)
+			{
+				depth = 56 + bitIndex[((xorKey & 0xFF00000000000000)>>56)];
+			}
+			else
+			{
+				depth = 48 + bitIndex[((xorKey & 0x00FF000000000000)>>48)];
+			}
+		}
+		else
+		{
+			if	(xorKey & 0x0000FF0000000000)
+			{
+				depth = 40 + bitIndex[((xorKey & 0x0000FF0000000000)>>40)];
+			}
+			else
+			{
+				depth = 32 + bitIndex[((xorKey & 0x000000FF00000000)>>32)];
+			}
+		}
+	}
+	else
+#endif
+	{
+		if  (xorKey & 0x00000000FFFF0000)
+		{
+			if	(xorKey & 0x00000000FF000000)
+			{
+				depth = 24 + bitIndex[((xorKey & 0x00000000FF000000)>>24)];
+			}
+			else
+			{
+				depth = 16 + bitIndex[((xorKey & 0x0000000000FF0000)>>16)];
+			}
+		}
+		else
+		{
+			if	(xorKey & 0x000000000000FF00)
+			{
+				depth = 8 + bitIndex[((xorKey & 0x0000000000000FF00)>>8)];
+			}
+			else
+			{
+				depth = bitIndex[xorKey & 0x00000000000000FF];
+			}
+		}
+	}
+
+    /* We have located the leftmost differing bit, indicated by the depth variable. So, we know what
+     * bit index we are to insert the new entry at. There are two cases, being where the two keys
+     * differ at a bit position that is not currently part of the bit testing, where they differ on a bit
+     * that is currently being skipped in the indexed comparisons, and where they differ on a bit
+     * that is merely lower down in the current bit search. If the bit index went bit 4, bit 2 and they differ
+     * at bit 3, then we have the "skipped" bit case. But if that chain was Bit 4, Bit 2 and they differ at bit 1
+     * then we have the easy bit <pun>.
+     *
+     * So, set up to descend the tree again, but this time looking for the insert point
+     * according to whether we skip the bit that differs or not.
+     */
+    thisNode	= trie->root;
+    entNode	= trie->root->leftN;
+
+    /* Note the slight difference in the checks here to cover both cases
+     */
+    while (thisNode->bitNum > entNode->bitNum && entNode->bitNum > depth)
+    {
+	/* Still descending the structure, next node becomes current.
+	 */
+	thisNode = entNode;
+
+	if (key & bitMask[entNode->bitNum])
+	{
+	    /* Bit at the required index was 1, so traverse the right node from here
+	     */
+	    entNode = entNode->rightN;
+	}
+	else
+	{
+	    /* Bit at the required index was 0, so we traverse to the left
+	     */
+	    entNode = entNode->leftN;
+	}
+    }
+
+    /* We have located the correct insert point for this new key, so we need
+     * to allocate our entry and insert it etc.
+     */
+    nextNode	= (pANTLR3_INT_TRIE_NODE)ANTLR3_CALLOC(1, sizeof(ANTLR3_INT_TRIE_NODE));
+    if (nextNode == NULL)
+    {
+	/* All that work and no memory - bummer.
+	 */
+	return	ANTLR3_FALSE;
+    }
+
+    /* Build a new entry block for the new node
+     */
+    newEnt = (pANTLR3_TRIE_ENTRY)ANTLR3_CALLOC(1, sizeof(ANTLR3_TRIE_ENTRY));
+
+    if (newEnt == NULL)
+    {
+	/* Out of memory, all we can do is return the fact that the insert failed.
+	 */
+	return	ANTLR3_FALSE;
+    }
+
+    /* Otherwise enter this in our new node
+    */
+    newEnt->type	= type;
+    newEnt->freeptr	= freeptr;
+    if (type == ANTLR3_HASH_TYPE_STR)
+    {
+	newEnt->data.ptr = data;
+    }
+    else
+    {
+	newEnt->data.intVal = intVal;
+    }
+    /* Install it
+     */
+    nextNode->buckets	= newEnt;
+    nextNode->key	= key;
+    nextNode->bitNum	= depth;
+
+    /* Work out the right and left pointers for this new node, which involve
+     * terminating with the current found node either right or left according
+     * to whether the current index bit is 1 or 0
+     */
+    if (key & bitMask[depth])
+    {
+	nextNode->leftN	    = entNode;	    /* Terminates at previous position	*/
+	nextNode->rightN    = nextNode;	    /* Terminates with itself		*/
+    }
+    else
+    {
+	nextNode->rightN   = entNode;	    /* Terminates at previous position	*/
+	nextNode->leftN    = nextNode;	    /* Terminates with itself		*/		
+    }
+
+    /* Finally, we need to change the pointers at the node we located
+     * for inserting. If the key bit at its index is set then the right
+     * pointer for that node becomes the newly created node, otherwise the left 
+     * pointer does.
+     */
+    if (key & bitMask[thisNode->bitNum] )
+    {
+	thisNode->rightN    = nextNode;
+    }
+    else
+    {
+	thisNode->leftN	    = nextNode;
+    }
+
+    /* Et voila
+     */
+    trie->count++;
+    return  ANTLR3_TRUE;
+
+}
+/** Release memory allocated to this tree.
+ *  Basic algorithm is that we do a depth first left descent and free
+ *  up any nodes that are not backward pointers.
+ */
+static void
+freeIntNode(pANTLR3_INT_TRIE_NODE node)
+{
+    pANTLR3_TRIE_ENTRY	thisEntry;
+    pANTLR3_TRIE_ENTRY	nextEntry;
+
+    /* If this node has a left pointer that is not a back pointer
+     * then recursively call to free this
+     */
+    if (node->bitNum > node->leftN->bitNum)
+    {
+	/* We have a left node that needs descending, so do it.
+	 */
+	freeIntNode(node->leftN);
+    }
+
+    /* The left nodes from here should now be dealt with, so 
+     * we need to descend any right nodes that are not back pointers
+     */
+    if (node->bitNum > node->rightN->bitNum)
+    {
+	/* There are some right nodes to descend and deal with.
+	 */
+	freeIntNode(node->rightN);
+    }
+
+    /* Now all the children are dealt with, we can destroy
+     * this node too
+     */
+    thisEntry	= node->buckets;
+
+    while (thisEntry != NULL)
+    {
+	nextEntry   = thisEntry->next;
+
+	/* Do we need to call a custom free pointer for this string entry?
+	 */
+	if (thisEntry->type == ANTLR3_HASH_TYPE_STR && thisEntry->freeptr != NULL)
+	{
+	    thisEntry->freeptr(thisEntry->data.ptr);
+	}
+
+	/* Now free the data for this bucket entry
+	 */
+	ANTLR3_FREE(thisEntry);
+	thisEntry = nextEntry;	    /* See if there are any more to free    */
+    }
+
+    /* The bucket entry is now gone, so we can free the memory for
+     * the entry itself.
+     */
+    ANTLR3_FREE(node);
+
+    /* And that should be it for everything under this node and itself
+     */
+}
+
+/** Called to free all nodes and the structure itself.
+ */
+static	void			
+intTrieFree	(pANTLR3_INT_TRIE trie)
+{
+    /* Descend from the root and free all the nodes
+     */
+    freeIntNode(trie->root);
+
+    /* the nodes are all gone now, so we need only free the memory
+     * for the structure itself
+     */
+    ANTLR3_FREE(trie);
+}
+
+
+/**
+ * Allocate and initialize a new ANTLR3 topological sorter, which can be
+ * used to define edges that identify numerical node indexes that depend on other
+ * numerical node indexes, which can then be sorted topologically such that
+ * any node is sorted after all its dependent nodes.
+ *
+ * Use:
+ *
+ * /verbatim
+
+  pANTLR3_TOPO topo;
+  topo = antlr3NewTopo();
+
+  if (topo == NULL) { out of memory }
+
+  topo->addEdge(topo, 3, 0); // Node 3 depends on node 0
+  topo->addEdge(topo, 0, 1); // Node - depends on node 1
+  topo->sortVector(topo, myVector); // Sort the vector in place (node numbers are the vector entry numbers)
+
+ * /verbatim
+ */
+ANTLR3_API pANTLR3_TOPO
+antlr3TopoNew()
+{
+    pANTLR3_TOPO topo = (pANTLR3_TOPO)ANTLR3_MALLOC(sizeof(ANTLR3_TOPO));
+
+    if  (topo == NULL)
+    {
+        return NULL;
+    }
+
+    // Initialize variables
+    //
+
+    topo->visited   = NULL;                 // Don't know how big it is yet
+    topo->limit     = 1;                    // No edges added yet
+    topo->edges     = NULL;                 // No edges added yet
+    topo->sorted    = NULL;                 // Nothing sorted at the start
+    topo->cycle     = NULL;                 // No cycles at the start
+    topo->cycleMark = 0;                    // No cycles at the start
+    topo->hasCycle  = ANTLR3_FALSE;         // No cycle at the start
+    
+    // API
+    //
+    topo->addEdge       = addEdge;
+    topo->sortToArray   = sortToArray;
+    topo->sortVector    = sortVector;
+    topo->free          = freeTopo;
+
+    return topo;
+}
+// Topological sorter
+//
+static  void
+addEdge          (pANTLR3_TOPO topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency)
+{
+    ANTLR3_UINT32   i;
+    ANTLR3_UINT32   maxEdge;
+    pANTLR3_BITSET  edgeDeps;
+
+    if (edge>dependency)
+    {
+        maxEdge = edge;
+    }
+    else
+    {
+        maxEdge = dependency;
+    }
+    // We need to add an edge to says that the node indexed by 'edge' is
+    // dependent on the node indexed by 'dependency'
+    //
+
+    // First see if we have enough room in the edges array to add the edge?
+    //
+    if (topo->edges == NULL)
+    {
+        // We don't have any edges yet, so create an array to hold them
+        //
+        topo->edges = ANTLR3_CALLOC(sizeof(pANTLR3_BITSET) * (maxEdge + 1), 1);
+        if (topo->edges == NULL)
+        {
+            return;
+        }
+
+        // Set the limit to what we have now
+        //
+        topo->limit = maxEdge + 1;
+    }
+    else if (topo->limit <= maxEdge)
+    {
+        // WE have some edges but not enough
+        //
+        topo->edges = ANTLR3_REALLOC(topo->edges, sizeof(pANTLR3_BITSET) * (maxEdge + 1));
+        if (topo->edges == NULL)
+        {
+            return;
+        }
+
+        // Initialize the new bitmaps to ;indicate we have no edges defined yet
+        //
+        for (i = topo->limit; i <= maxEdge; i++)
+        {
+            *((topo->edges) + i) = NULL;
+        }
+
+        // Set the limit to what we have now
+        //
+        topo->limit = maxEdge + 1;
+    }
+
+    // If the edge was flagged as depending on itself, then we just
+    // do nothing as it means this routine was just called to add it
+    // in to the list of nodes.
+    //
+    if  (edge == dependency)
+    {
+        return;
+    }
+
+    // Pick up the bit map for the requested edge
+    //
+    edgeDeps = *((topo->edges) + edge);
+
+    if  (edgeDeps == NULL)
+    {
+        // No edges are defined yet for this node
+        //
+        edgeDeps                = antlr3BitsetNew(0);
+        *((topo->edges) + edge) = edgeDeps;
+        if (edgeDeps == NULL )
+        {
+            return;  // Out of memory
+        }
+    }
+
+    // Set the bit in the bitmap that corresponds to the requested
+    // dependency.
+    //
+    edgeDeps->add(edgeDeps, dependency);
+
+    // And we are all set
+    //
+    return;
+}
+
+
+/**
+ * Given a starting node, descend its dependent nodes (ones that it has edges
+ * to) until we find one without edges. Having found a node without edges, we have
+ * discovered the bottom of a depth first search, which we can then ascend, adding
+ * the nodes in order from the bottom, which gives us the dependency order.
+ */
+static void
+DFS(pANTLR3_TOPO topo, ANTLR3_UINT32 node)
+{
+    pANTLR3_BITSET edges;
+
+    // Guard against a revisit and check for cycles
+    //
+    if  (topo->hasCycle == ANTLR3_TRUE)
+    {
+        return; // We don't do anything else if we found a cycle
+    }
+
+    if  (topo->visited->isMember(topo->visited, node))
+    {
+        // Check to see if we found a cycle. To do this we search the
+        // current cycle stack and see if we find this node already in the stack.
+        //
+        ANTLR3_UINT32   i;
+
+        for (i=0; i<topo->cycleMark; i++)
+        {
+            if  (topo->cycle[i] == node)
+            {
+                // Stop! We found a cycle in the input, so rejig the cycle
+                // stack so that it only contains the cycle and set the cycle flag
+                // which will tell the caller what happened
+                //
+                ANTLR3_UINT32 l;
+
+                for (l = i; l < topo->cycleMark; l++)
+                {
+                    topo->cycle[l - i] = topo->cycle[l];    // Move to zero base in the cycle list
+                }
+
+                // Recalculate the limit
+                //
+                topo->cycleMark -= i;
+
+                // Signal disaster
+                //
+                topo->hasCycle = ANTLR3_TRUE;
+            }
+        }
+        return;
+    }
+
+    // So far, no cycles have been found and we have not visited this node yet,
+    // so this node needs to go into the cycle stack before we continue
+    // then we will take it out of the stack once we have descended all its
+    // dependencies.
+    //
+    topo->cycle[topo->cycleMark++] = node;
+
+    // First flag that we have visited this node
+    //
+    topo->visited->add(topo->visited, node);
+
+    // Now, if this node has edges, then we want to ensure we visit
+    // them all before we drop through and add this node into the sorted
+    // list.
+    //
+    edges = *((topo->edges) + node);
+    if  (edges != NULL)
+    {
+        // We have some edges, so visit each of the edge nodes
+        // that have not already been visited.
+        //
+        ANTLR3_UINT32   numBits;	    // How many bits are in the set
+        ANTLR3_UINT32   i;
+        ANTLR3_UINT32   range;
+
+        numBits = edges->numBits(edges);
+        range   = edges->size(edges);   // Number of set bits
+
+        // Stop if we exahust the bit list or have checked the
+        // number of edges that this node refers to (so we don't
+        // check bits at the end that cannot possibly be set).
+        //
+        for (i=0; i<= numBits && range > 0; i++)
+        {
+            if  (edges->isMember(edges, i))
+            {
+                range--;        // About to check another one
+
+                // Found an edge, make sure we visit and descend it
+                //
+                DFS(topo, i);
+            }
+        }
+    }
+
+    // At this point we will have visited all the dependencies
+    // of this node and they will be ordered (even if there are cycles)
+    // So we just add the node into the sorted list at the
+    // current index position.
+    //
+    topo->sorted[topo->limit++] = node;
+
+    // Remove this node from the cycle list if we have not detected a cycle
+    //
+    if  (topo->hasCycle == ANTLR3_FALSE)
+    {
+        topo->cycleMark--;
+    }
+
+    return;
+}
+
+static  pANTLR3_UINT32
+sortToArray      (pANTLR3_TOPO topo)
+{
+    ANTLR3_UINT32 v;
+    ANTLR3_UINT32 oldLimit;
+
+    // Guard against being called with no edges defined
+    //
+    if  (topo->edges == NULL)
+    {
+        return 0;
+    }
+    // First we need a vector to populate with enough
+    // entries to accomodate the sorted list and another to accomodate
+    // the maximum cycle we could detect which is all nodes such as 0->1->2->3->0
+    //
+    topo->sorted    = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32));
+    topo->cycle     = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32));
+
+    // Next we need an empty bitset to show whether we have visited a node
+    // or not. This is the bit that gives us linear time of course as we are essentially
+    // dropping through the nodes in depth first order and when we get to a node that
+    // has no edges, we pop back up the stack adding the nodes we traversed in reverse
+    // order.
+    //
+    topo->visited   = antlr3BitsetNew(0);
+
+    // Now traverse the nodes as if we were just going left to right, but
+    // then descend each node unless it has already been visited.
+    //
+    oldLimit    = topo->limit;     // Number of nodes to traverse linearly
+    topo->limit = 0;               // Next entry in the sorted table
+
+    for (v = 0; v < oldLimit; v++)
+    {
+        // If we did not already visit this node, then descend it until we
+        // get a node without edges or arrive at a node we have already visited.
+        //
+        if  (topo->visited->isMember(topo->visited, v) == ANTLR3_FALSE)
+        {
+            // We have not visited this one so descend it
+            //
+            DFS(topo, v);
+        }
+
+        // Break the loop if we detect a cycle as we have no need to go any
+        // further
+        //
+        if  (topo->hasCycle == ANTLR3_TRUE)
+        {
+            break;
+        }
+    }
+
+    // Reset the limit to the number we recorded as if we hit a
+    // cycle, then limit will have stopped at the node where we
+    // discovered the cycle, but in order to free the edge bitmaps
+    // we need to know how many we may have allocated and traverse them all.
+    //
+    topo->limit = oldLimit;
+
+    // Having traversed all the nodes we were given, we
+    // are guaranteed to have ordered all the nodes or detected a
+    // cycle.
+    //
+    return topo->sorted;
+}
+
+static  void
+sortVector       (pANTLR3_TOPO topo, pANTLR3_VECTOR v)
+{
+    // To sort a vector, we first perform the
+    // sort to an array, then use the results to reorder the vector
+    // we are given. This is just a convenience routine that allows you to
+    // sort the children of a tree node into topological order before or
+    // during an AST walk. This can be useful for optimizations that require
+    // dag reorders and also when the input stream defines thigns that are
+    // interdependent and you want to walk the list of the generated trees
+    // for those things in topological order so you can ignore the interdependencies
+    // at that point.
+    //
+    ANTLR3_UINT32 i;
+
+    // Used as a lookup index to find the current location in the vector of
+    // the vector entry that was originally at position [0], [1], [2] etc
+    //
+    pANTLR3_UINT32  vIndex;
+
+    // Sort into an array, then we can use the array that is
+    // stored in the topo
+    //
+    if  (topo->sortToArray(topo) == 0)
+    {
+        return;     // There were no edges
+    }
+
+    if  (topo->hasCycle == ANTLR3_TRUE)
+    {
+        return;  // Do nothing if we detected a cycle
+    }
+
+    // Ensure that the vector we are sorting is at least as big as the
+    // the input sequence we were adsked to sort. It does not matter if it is
+    // bigger as thaat probably just means that nodes numbered higher than the
+    // limit had no dependencies and so can be left alone.
+    //
+    if  (topo->limit > v->count)
+    {
+        // We can only sort the entries that we have dude! The caller is
+        // responsible for ensuring the vector is the correct one and is the
+        // correct size etc.
+        //
+        topo->limit = v->count;
+    }
+    // We need to know the locations of each of the entries
+    // in the vector as we don't want to duplicate them in a new vector. We
+    // just use an indirection table to get the vector entry for a particular sequence
+    // acording to where we moved it last. Then we can just swap vector entries until
+    // we are done :-)
+    //
+    vIndex = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32));
+
+    // Start index, each vector entry is located where you think it is
+    //
+    for (i = 0; i < topo->limit; i++)
+    {
+        vIndex[i] = i;
+    }
+
+    // Now we traverse the sorted array and moved the entries of
+    // the vector around according to the sort order and the indirection
+    // table we just created. The index telsl us where in the vector the
+    // original element entry n is now located via vIndex[n].
+    //
+    for (i=0; i < topo->limit; i++)
+    {
+        ANTLR3_UINT32   ind;
+
+        // If the vector entry at i is already the one that it
+        // should be, then we skip moving it of course.
+        //
+        if  (vIndex[topo->sorted[i]] == i)
+        {
+            continue;
+        }
+
+        // The vector entry at i, should be replaced with the
+        // vector entry indicated by topo->sorted[i]. The vector entry
+        // at topo->sorted[i] may have already been swapped out though, so we
+        // find where it is now and move it from there to i.
+        //
+        ind     = vIndex[topo->sorted[i]];
+        v->swap(v, i, ind);
+
+        // Update our index. The element at i is now the one we wanted
+        // to be sorted here and the element we swapped out is now the
+        // element that was at i just before we swapped it. If you are lost now
+        // don't worry about it, we are just reindexing on the fly is all.
+        //
+        vIndex[topo->sorted[i]] = i;
+        vIndex[i] = ind;
+    }
+
+    // Having traversed all the entries, we have sorted the vector in place.
+    //
+    ANTLR3_FREE(vIndex);
+    return;
+}
+
+static  void
+freeTopo             (pANTLR3_TOPO topo)
+{
+    ANTLR3_UINT32   i;
+
+    // Free the result vector
+    //
+    if  (topo->sorted != NULL)
+    {
+        ANTLR3_FREE(topo->sorted);
+        topo->sorted = NULL;
+    }
+
+    // Free the visited map
+    //
+    if  (topo->visited != NULL)
+    {
+
+        topo->visited->free(topo->visited);
+        topo->visited = NULL;
+    }
+
+    // Free any edgemaps
+    //
+    if  (topo->edges != NULL)
+    {
+        pANTLR3_BITSET edgeList;
+
+        
+        for (i=0; i<topo->limit; i++)
+        {
+            edgeList = *((topo->edges) + i);
+            if  (edgeList != NULL)
+            {
+                edgeList->free(edgeList);
+            }
+        }
+
+        ANTLR3_FREE(topo->edges);
+    }
+    topo->edges = NULL;
+    
+    // Free any cycle map
+    //
+    if  (topo->cycle != NULL)
+    {
+        ANTLR3_FREE(topo->cycle);
+    }
+
+    ANTLR3_FREE(topo);
+}