/// \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);
}