antlr3collections.c

antlr最新版本V3源代码

/** \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.
 *
 */
#include    <antlr3.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_UINT64 key);
static void *		    antlr3HashGetI	(pANTLR3_HASH_TABLE table, ANTLR3_UINT64 key);
static pANTLR3_HASH_ENTRY   antlr3HashRemoveI   (pANTLR3_HASH_TABLE table, ANTLR3_UINT64 key);
static ANTLR3_INT32	    antlr3HashPutI	(pANTLR3_HASH_TABLE table, ANTLR3_UINT64 key, void * element, void (ANTLR3_CDECL *freeptr)(void *));

static void		    antlr3HashFree	(pANTLR3_HASH_TABLE table);
static ANTLR3_UINT64	    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_UINT64 key);
static void *		antlr3ListGet	(pANTLR3_LIST list, ANTLR3_UINT64 key);
static ANTLR3_INT32	antlr3ListPut	(pANTLR3_LIST list, ANTLR3_UINT64 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_UINT64 key);
static ANTLR3_UINT64	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_UINT64 key);
static ANTLR3_BOOLEAN	antlr3StackPush	(pANTLR3_STACK	stack, void * element, void (ANTLR3_CDECL *freeptr)(void *));
static ANTLR3_UINT64	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_UINT64 entry);
static	void *		antlr3VectorGet     (pANTLR3_VECTOR vector, ANTLR3_UINT64 entry);
static	void *		antrl3VectorRemove  (pANTLR3_VECTOR vector, ANTLR3_UINT64 entry);
static	ANTLR3_INT32    antlr3VectorAdd	    (pANTLR3_VECTOR vector, void * element, void (ANTLR3_CDECL *freeptr)(void *));
static	ANTLR3_INT32    antlr3VectorPut	    (pANTLR3_VECTOR vector, ANTLR3_UINT64 entry, void * element, void (ANTLR3_CDECL *freeptr)(void *), ANTLR3_BOOLEAN freeExisting);
static	ANTLR3_UINT64   antlr3VectorSize    (pANTLR3_VECTOR vector);

static  void		closeVectorFactory  (pANTLR3_VECTOR_FACTORY factory);
static	pANTLR3_VECTOR  newVector	    (pANTLR3_VECTOR_FACTORY factory);


/* Interface functions for int TRIE
 */
static	pANTLR3_TRIE_ENTRY	intTrieGet	(pANTLR3_INT_TRIE trie, ANTLR3_UINT64 key);
static	ANTLR3_BOOLEAN		intTrieDel	(pANTLR3_INT_TRIE trie, ANTLR3_UINT64 key);
static	ANTLR3_BOOLEAN		intTrieAdd	(pANTLR3_INT_TRIE trie, ANTLR3_UINT64 key, ANTLR3_UINT32 type, ANTLR3_UINT64 intType, void * data, void (ANTLR3_CDECL *freeptr)(void *));
static	void			intTrieFree	(pANTLR3_INT_TRIE trie);

/* 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	(pANTLR3_HASH_TABLE) ANTLR3_ERR_NOMEM;
    }

    /* 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	(pANTLR3_HASH_TABLE) ANTLR3_ERR_NOMEM;
    }

    /* 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;

    /* 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_UINT64	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_UINT64 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_UINT64)(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 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  (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 - we allocated that
	     */
	    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_UINT64 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_UINT64 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_UINT64)(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_UINT64 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_UINT64)(table->modulo));

    /* Knowing the hash, we can find the bucket
     */
    bucket  = table->buckets + hash;

    /* 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