| /// \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 ANTLR3_BOOLEAN 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 = (pANTLR3_HASH_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 = (pANTLR3_UINT8)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 ANTLR3_BOOLEAN |
| 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 |
| // |
| pANTLR3_VECTOR_ELEMENT newElements = (pANTLR3_VECTOR_ELEMENT)ANTLR3_REALLOC(vector->elements, (sizeof(ANTLR3_VECTOR_ELEMENT)* newSize)); |
| if (newElements == NULL) |
| { |
| // realloc failed, but the old allocation is still there |
| return ANTLR3_FALSE; |
| } |
| vector->elements = newElements; |
| } |
| 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)); |
| if (vector->elements == NULL) |
| { |
| // malloc failed |
| return ANTLR3_FALSE; |
| } |
| ANTLR3_MEMCPY(vector->elements, vector->internal, ANTLR3_VECTOR_INTERNAL_SIZE * sizeof(ANTLR3_VECTOR_ELEMENT)); |
| } |
| |
| vector->elementsSize = newSize; |
| return ANTLR3_TRUE; |
| } |
| |
| /// 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) |
| { |
| // Give no hint, we let it add 1024 or double it |
| if (!antlr3VectorResize(vector, 0)) |
| { |
| // Resize failed |
| return 0; |
| } |
| } |
| |
| // 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) |
| { |
| // We will get at least this many |
| if (!antlr3VectorResize(vector, entry)) |
| { |
| // Resize failed |
| return 0; |
| } |
| } |
| |
| // 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 ANTLR3_BOOLEAN |
| newPool(pANTLR3_VECTOR_FACTORY factory) |
| { |
| pANTLR3_VECTOR *newPools; |
| |
| /* Increment factory count |
| */ |
| ++factory->thisPool; |
| |
| /* Ensure we have enough pointers allocated |
| */ |
| newPools = (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 */ |
| ); |
| if (newPools == NULL) |
| { |
| // realloc failed, but we still have the old allocation |
| --factory->thisPool; |
| return ANTLR3_FALSE; |
| } |
| factory->pools = newPools; |
| |
| /* Allocate a new pool for the factory |
| */ |
| factory->pools[factory->thisPool] = |
| (pANTLR3_VECTOR) |
| ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR) * ANTLR3_FACTORY_VPOOL_SIZE)); |
| if (factory->pools[factory->thisPool] == NULL) |
| { |
| // malloc failed |
| --factory->thisPool; |
| return ANTLR3_FALSE; |
| } |
| |
| |
| /* Reset the counters |
| */ |
| factory->nextVector = 0; |
| |
| /* Done |
| */ |
| return ANTLR3_TRUE; |
| } |
| |
| 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 = (pANTLR3_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 |
| // |
| if (!newPool(factory)) |
| { |
| // new pool creation failed |
| return NULL; |
| } |
| } |
| |
| // 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 initialize 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; |
| |
| 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 = (pANTLR3_BITSET*)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 = (pANTLR3_BITSET*)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 NULL; |
| } |
| // First we need a vector to populate with enough |
| // entries to accommodate the sorted list and another to accommodate |
| // the maximum cycle we could detect which is all nodes such as 0->1->2->3->0 |
| // |
| topo->sorted = (pANTLR3_UINT32)ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32)); |
| if (topo->sorted == NULL) |
| { |
| return NULL; |
| } |
| topo->cycle = (pANTLR3_UINT32)ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32)); |
| if (topo->cycle == NULL) |
| { |
| return NULL; |
| } |
| |
| // 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 things 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 asked to sort. It does not matter if it is |
| // bigger as that 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 |
| // according to where we moved it last. Then we can just swap vector entries until |
| // we are done :-) |
| // |
| vIndex = (pANTLR3_UINT32)ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32)); |
| if (vIndex == NULL) |
| { |
| // malloc failed |
| return; |
| } |
| |
| // 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); |
| } |