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