antlr3collections.c

antlr最新版本V3源代码

    /* Allow vectors to be guessed by ourselves, so input size can be zero
     */
    if	(sizeHint > 0)
    {
	initialSize = sizeHint;
    }
    else
    {
	initialSize = 8;
    }

    /* Allocate memory for the vector structure itself
     */
    vector  = (pANTLR3_VECTOR) ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR)));

    if	(vector == NULL)
    {
	return	(pANTLR3_VECTOR)ANTLR3_ERR_NOMEM;
    }

    /* Now fill in the defaults
     */
    vector->elements	= (pANTLR3_VECTOR_ELEMENT)ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR_ELEMENT) * initialSize));

    if	(vector->elements == NULL)
    {
	ANTLR3_FREE(vector);
	return	(pANTLR3_VECTOR)ANTLR3_ERR_NOMEM;
    }

    /* Memory allocated succesfully
     */
    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->get	    = antlr3VectorGet;
    vector->put	    = antlr3VectorPut;
    vector->remove  = antrl3VectorRemove;
    vector->size    = antlr3VectorSize;

    /** Assume that this is not a factory made vector
     */
    vector->factoryMade	= ANTLR3_FALSE;

    /* And everything is hunky dory
     */
    return  vector;
}

static	
void	ANTLR3_CDECL	antlr3VectorFree    (pANTLR3_VECTOR vector)
{
    ANTLR3_UINT64   entry;

    /* We must traverse every entry in the vector and if it has
     * a pointer to a free fucntion 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
	 */
	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_UINT64 entry)
{
    /* Check this is a valid request first (index is 1 based!!)
     */
    if	(entry == 0 || entry > vector->count)
    {
	return;
    }

    /* Valid request, check for free pointer and call it if present
     */
    
    if	(vector->elements[entry-1].freeptr != NULL)
    {
	vector->elements[entry-1].freeptr(vector->elements[entry-1].element);
	vector->elements[entry-1].freeptr    = NULL;
    }

    if	(entry == vector->count)
    {
	/* Ensure the pointer is never reused by accident, but othewise just 
	 * decrement the pointer.
	 */
	vector->elements[entry-1].element    = NULL;
    }
    else
    {
	/* Need to shuffle trailing pointers back over the deleted entry
	 */
	ANTLR3_MEMMOVE(vector->elements + entry - 1, vector->elements + entry, sizeof(ANTLR3_VECTOR_ELEMENT) * (vector->count - entry));
    }

    /* One less entry in the vector now
     */
    vector->count--;
}

static	void *		antlr3VectorGet     (pANTLR3_VECTOR vector, ANTLR3_UINT64 entry)
{
    /* Ensure this is a valid request
     */
    if	(entry <= vector->count && entry > 0)
    {
	return	vector->elements[entry - 1].element;	/* Index is 1 based, storage is 0 based */
    }
    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_UINT64 entry)
{
    void * element;

    /* Check this is a valid request first (index is 1 based!!)
     */
    if	(entry == 0 || entry > vector->count)
    {
	return NULL;
    }

    /* Valid request, return the sorted pointer
     */

    element				    = vector->elements[entry-1].element;

    if	(entry == vector->count)
    {
	/* Ensure the pointer is never reused by accident, but otherwise just 
	 * decrement the pointer.
	 */
	vector->elements[entry-1].element    = NULL;
	vector->elements[entry-1].freeptr    = NULL;
    }
    else
    {
	/* Need to shuffle trailing pointers back over the deleted entry
	 */
	ANTLR3_MEMMOVE(vector->elements + entry - 1, vector->elements + entry, sizeof(ANTLR3_VECTOR_ELEMENT) * (vector->count - entry));
    }

    /* One less entry in the vector now
     */
    vector->count--;

    return  element;
}

static  void
antlr3VectorResize  (pANTLR3_VECTOR vector, ANTLR3_UINT64 hint)
{
    	ANTLR3_UINT64	newSize;

	/* Need to resize the element pointers. We double the allocation
	 * unless we have reached 1024 elements, in which case we just
	 * add another 1024. I may tune this or make it tunable later.
	 */
	if  (vector->elementsSize > 1024)
	{
	    if (hint == 0)
	    {
		newSize = vector->elementsSize + 1024;
	    }
	    else
	    {
		newSize = hint + 1024;
	    }
	}
	else
	{
	    if (hint == 0)
	    {
		newSize = vector->elementsSize * 2;
	    }
	    else
	    {
		newSize = hint * 2;	// Add twice what we were asked for
	    }
	}

	/* Use realloc so that the pointers are copied for us
	 */
	vector->elements	= (pANTLR3_VECTOR_ELEMENT)ANTLR3_REALLOC(vector->elements, (sizeof(ANTLR3_VECTOR_ELEMENT)* newSize));
	/* Reset new pointers etc to 0
	 */
	ANTLR3_MEMSET(vector->elements + vector->elementsSize, 0x00, (newSize - vector->elementsSize) * sizeof(ANTLR3_VECTOR_ELEMENT));
	vector->elementsSize	= newSize;
}

/* Add the supplied pointer and freeing function pointer to the list,
 * explanding the vector if needed.
 */
static	ANTLR3_INT32    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_INT32    
antlr3VectorPut	    (pANTLR3_VECTOR vector, ANTLR3_UINT64 entry, void * element, void (ANTLR3_CDECL *freeptr)(void *), ANTLR3_BOOLEAN freeExisting)
{
    /* Validate first
     */
    if	(entry == 0)
    {
	return	-1;
    }

    /* 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 preior entry if told to
     */
    if	(freeExisting && vector->elements[entry-1].freeptr != NULL)
    {
	vector->elements[entry-1].freeptr(vector->elements[entry-1].element);
    }

    /* Install the new pointers
     */
    vector->elements[entry-1].freeptr    = freeptr;
    vector->elements[entry-1].element	= element;

    if (entry > vector->count)
    {
	vector->count = entry;
    }
    return  (ANTLR3_UINT32)(entry);	    /* Indicates the replacement was successful	*/

}

static	ANTLR3_UINT64   antlr3VectorSize    (pANTLR3_VECTOR vector)
{
    return  vector->count;
}

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

    /* Factory memory is good, so create a new vector
     */
    if	(sizeHint == 0)
    {
	sizeHint = 64;
    }

    /* Create the vector if possible
     */
    factory->vectors	= antlr3VectorNew(sizeHint);

    if	(factory->vectors == (pANTLR3_VECTOR)ANTLR3_ERR_NOMEM)
    {
	ANTLR3_FREE(factory);
	return	(pANTLR3_VECTOR_FACTORY)ANTLR3_ERR_NOMEM;
    }

    /* Install the API
     */
    factory->close	= closeVectorFactory;
    factory->newVector	= newVector;

    return  factory;
}

static  void		
closeVectorFactory  (pANTLR3_VECTOR_FACTORY factory)
{
    ANTLR3_UINT64   entry;
    pANTLR3_VECTOR  vector;
    pANTLR3_VECTOR  freeVector;

    /** First we iterate the vectors in the factory and call
     *  free on each of them. Because they are factory made only
     *  any installed free pointers for the entries will be called
     *  and we will be left with just those vectors that were factory made
     *  to delete the memory allocations for. These are the elment list
     *  itself.
     */
    vector  = factory->vectors;

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

    /* Having called free on each of the vectors in the vector factory,
     * anything that was somewhere buried in the vectors in the factory that
     * was not factory made, is now deallocated. So, we now need only
     * traverse each vector in the factory and free its elements, then free this
     * factory vector.
     */
    for	(entry = 0; entry < vector->count; entry++)
    {
	freeVector  = (pANTLR3_VECTOR)(vector->elements[entry].element);

	/* Anything in here should be factory made, but we do this just
	 * to triple check.
	 */
	if  (freeVector->factoryMade == ANTLR3_TRUE)
	{
	    ANTLR3_FREE(freeVector->elements);
	    ANTLR3_FREE(freeVector);
	}
    }

    /* Free the memory for the factory vector elements, then the factory vector
     */
    ANTLR3_FREE(vector->elements);
    ANTLR3_FREE(vector);

    /* Now free the memory for the factory itself
     */
    ANTLR3_FREE(factory);
}

static	pANTLR3_VECTOR  
newVector	    (pANTLR3_VECTOR_FACTORY factory)
{
    pANTLR3_VECTOR  vector;

    /* Attempt to create a new vector of default size
     */
    vector  = antlr3VectorNew(0);

    if	(vector == (pANTLR3_VECTOR)(ANTLR3_ERR_NOMEM))
    {
	return vector;
    }

    /* Now add this vector to the factory vector, which will
     * track it and release any entries in it when we close the factory.
     */
    vector->factoryMade	= ANTLR3_TRUE;
    factory->vectors->add(factory->vectors, (void *)vector, (void (ANTLR3_CDECL *)(void *))(vector->free));

    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 a reasonable
 *  amount of CPU cache, 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 transitors? 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 bitindex 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] = 
{
    0x0000000000000001, 0x0000000000000002, 0x0000000000000004, 0x0000000000000008,
    0x0000000000000010, 0x0000000000000020, 0x0000000000000040, 0x0000000000000080,
    0x0000000000000100, 0x0000000000000200, 0x0000000000000400, 0x0000000000000800,
    0x0000000000001000, 0x0000000000002000, 0x0000000000004000, 0x0000000000008000,
    0x0000000000010000, 0x0000000000020000, 0x0000000000040000, 0x0000000000080000,
    0x0000000000100000, 0x0000000000200000, 0x0000000000400000, 0x0000000000800000,
    0x0000000001000000, 0x0000000002000000, 0x0000000004000000, 0x0000000008000000,
    0x0000000010000000, 0x0000000020000000, 0x0000000040000000, 0x0000000080000000
#ifdef ANTLR3_USE_64BIT
    ,
    0x0000000100000000, 0x0000000200000000, 0x0000000400000000, 0x0000000800000000,
    0x0000001000000000, 0x0000002000000000, 0x0000004000000000, 0x0000008000000000,
    0x0000010000000000, 0x0000020000000000, 0x0000040000000000, 0x0000080000000000,
    0x0000100000000000, 0x0000200000000000, 0x0000400000000000, 0x0000800000000000,
    0x0001000000000000, 0x0002000000000000, 0x0004000000000000, 0x0008000000000000,
    0x0010000000000000, 0x0020000000000000, 0x0040000000000000, 0x0080000000000000,
    0x0100000000000000, 0x0200000000000000, 0x0400000000000000, 0x0800000000000000,
    0x1000000000000000, 0x2000000000000000, 0x4000000000000000, 0x8000000000000000
#endif
};

/* INT TRIE Implementation of depth 64 bits, being the number of bits
 * in a 64 bit integer. 
 */

pANTLR3_INT_TRIE