/// \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 #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 . * * 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; icycleMark; 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; ilimit; 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); }