antlr3-addEdge (3) - Linux Manuals
NAME
src/antlr3collections.c -
Provides a number of useful functions that are roughly equivalent to java HashTable and List for the purposes of Antlr 3 C runtime.
SYNOPSIS
#include <antlr3.h>
#include 'antlr3collections.h'
Functions
static void addEdge (pANTLR3_TOPO topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency)
static void antlr3EnumFree (pANTLR3_HASH_ENUM en)
Frees up the memory structures that represent a hash table enumeration.
pANTLR3_HASH_ENUM antlr3EnumNew (pANTLR3_HASH_TABLE table)
Creates an enumeration structure to traverse the hash table.
static int antlr3EnumNext (pANTLR3_HASH_ENUM en, pANTLR3_HASH_KEY *key, void **data)
Return the next entry in the hashtable being traversed by the supplied enumeration.
static void antlr3EnumNextEntry (pANTLR3_HASH_ENUM en)
Local function to advance the entry pointer of an enumeration structure to the next valid entry (if there is one).
ANTLR3_API ANTLR3_UINT32 antlr3Hash (void *key, ANTLR3_UINT32 keylen)
Given an input key of arbitrary length, return a hash value of it.
static void antlr3HashDelete (pANTLR3_HASH_TABLE table, void *key)
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)
Takes the element with the supplied key out of the list, and deletes the data calling the supplied free() routine if any.
static void antlr3HashFree (pANTLR3_HASH_TABLE table)
static void * antlr3HashGet (pANTLR3_HASH_TABLE table, void *key)
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)
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 ANTLR3_INT32 antlr3HashPut (pANTLR3_HASH_TABLE table, void *key, void *element, void(ANTLR3_CDECL *freeptr)(void *))
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 *))
Add the element pointer in to the table, based upon the hash of the provided key.
static pANTLR3_HASH_ENTRY antlr3HashRemove (pANTLR3_HASH_TABLE table, void *key)
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 antlr3HashRemoveI (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key)
Remove a numeric keyed entry from a hash table if it exists, no error if it does not exist.
static ANTLR3_UINT32 antlr3HashSize (pANTLR3_HASH_TABLE table)
return the current size of the hash table
pANTLR3_HASH_TABLE antlr3HashTableNew (ANTLR3_UINT32 sizeHint)
pANTLR3_INT_TRIE antlr3IntTrieNew (ANTLR3_UINT32 depth)
static ANTLR3_INT32 antlr3ListAdd (pANTLR3_LIST list, void *element, void(ANTLR3_CDECL *freeptr)(void *))
Add the supplied element to the list, at the next available key.
static void antlr3ListDelete (pANTLR3_LIST list, ANTLR3_INTKEY key)
static void antlr3ListFree (pANTLR3_LIST list)
static void * antlr3ListGet (pANTLR3_LIST list, ANTLR3_INTKEY key)
ANTLR3_API pANTLR3_LIST antlr3ListNew (ANTLR3_UINT32 sizeHint)
static ANTLR3_INT32 antlr3ListPut (pANTLR3_LIST list, ANTLR3_INTKEY key, void *element, void(ANTLR3_CDECL *freeptr)(void *))
static void * antlr3ListRemove (pANTLR3_LIST list, ANTLR3_INTKEY key)
Remove from the list, but don't free the element, just send it back to the caller.
static ANTLR3_UINT32 antlr3ListSize (pANTLR3_LIST list)
ANTLR3_API void antlr3SetVectorApi (pANTLR3_VECTOR vector, ANTLR3_UINT32 sizeHint)
static void antlr3StackFree (pANTLR3_STACK stack)
static void * antlr3StackGet (pANTLR3_STACK stack, ANTLR3_INTKEY key)
ANTLR3_API pANTLR3_STACK antlr3StackNew (ANTLR3_UINT32 sizeHint)
static void * antlr3StackPeek (pANTLR3_STACK stack)
static void * antlr3StackPop (pANTLR3_STACK stack)
static ANTLR3_BOOLEAN antlr3StackPush (pANTLR3_STACK stack, void *element, void(ANTLR3_CDECL *freeptr)(void *))
static ANTLR3_UINT32 antlr3StackSize (pANTLR3_STACK stack)
ANTLR3_API pANTLR3_TOPO antlr3TopoNew ()
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.
static ANTLR3_UINT32 antlr3VectorAdd (pANTLR3_VECTOR vector, void *element, void(ANTLR3_CDECL *freeptr)(void *))
Add the supplied pointer and freeing function pointer to the list, expanding the vector if needed.
static void antlr3VectorClear (pANTLR3_VECTOR vector)
static void antlr3VectorDel (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry)
ANTLR3_API pANTLR3_VECTOR_FACTORY antlr3VectorFactoryNew (ANTLR3_UINT32 sizeHint)
Vector factory creation.
static void ANTLR3_CDECL antlr3VectorFree (pANTLR3_VECTOR vector)
static void * antlr3VectorGet (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry)
ANTLR3_API pANTLR3_VECTOR antlr3VectorNew (ANTLR3_UINT32 sizeHint)
static void antlr3VectorResize (pANTLR3_VECTOR vector, ANTLR3_UINT32 hint)
static ANTLR3_UINT32 antlr3VectorSet (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry, void *element, void(ANTLR3_CDECL *freeptr)(void *), ANTLR3_BOOLEAN freeExisting)
Replace the element at the specified entry point with the supplied entry.
static ANTLR3_UINT32 antlr3VectorSize (pANTLR3_VECTOR vector)
static ANTLR3_BOOLEAN antlr3VectorSwap (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry1, ANTLR3_UINT32 entry2)
Replace the element at the specified entry point with the supplied entry.
static void * antrl3VectorRemove (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry)
Remove the entry from the vector, but do not free any entry, even if it has a free pointer.
static void closeVectorFactory (pANTLR3_VECTOR_FACTORY factory)
static void DFS (pANTLR3_TOPO topo, ANTLR3_UINT32 node)
Given a starting node, descend its dependent nodes (ones that it has edges to) until we find one without edges.
static void freeIntNode (pANTLR3_INT_TRIE_NODE node)
Release memory allocated to this tree.
static void freeTopo (pANTLR3_TOPO topo)
static ANTLR3_BOOLEAN intTrieAdd (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key, ANTLR3_UINT32 type, ANTLR3_INTKEY intVal, void *data, void(ANTLR3_CDECL *freeptr)(void *))
Add an entry into the INT trie.
static ANTLR3_BOOLEAN intTrieDel (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key)
static void intTrieFree (pANTLR3_INT_TRIE trie)
Called to free all nodes and the structure itself.
static pANTLR3_TRIE_ENTRY intTrieGet (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key)
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 void newPool (pANTLR3_VECTOR_FACTORY factory)
static pANTLR3_VECTOR newVector (pANTLR3_VECTOR_FACTORY factory)
static void returnVector (pANTLR3_VECTOR_FACTORY factory, pANTLR3_VECTOR vector)
static pANTLR3_UINT32 sortToArray (pANTLR3_TOPO topo)
static void sortVector (pANTLR3_TOPO topo, pANTLR3_VECTOR v)
Variables
static ANTLR3_UINT8 bitIndex [256]
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).
static ANTLR3_UINT64 bitMask [64]
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.
Detailed Description
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.
Function Documentation
static void addEdge (pANTLR3_TOPO topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency) [static]
References ANTLR3_BITSET_struct::add, ANTLR3_CALLOC, ANTLR3_REALLOC, antlr3BitsetNew(), ANTLR3_TOPO_struct::edges, and ANTLR3_TOPO_struct::limit.
Referenced by antlr3TopoNew().
static void antlr3EnumFree (pANTLR3_HASH_ENUM en) [static]
Frees up the memory structures that represent a hash table enumeration. Parameters:
- enum Pointer to ANTLR3 enumeration structure returned by antlr3EnumNew()
References ANTLR3_FREE.
Referenced by antlr3EnumNew().
pANTLR3_HASH_ENUM antlr3EnumNew (pANTLR3_HASH_TABLE table)
Creates an enumeration structure to traverse the hash table. Parameters:
- table Table to enumerate
Returns:
- Pointer to enumeration structure.
References ANTLR3_ERR_NOMEM, ANTLR3_FUNC_PTR, ANTLR3_MALLOC, antlr3EnumFree(), antlr3EnumNext(), antlr3EnumNextEntry(), ANTLR3_HASH_ENUM_struct::bucket, ANTLR3_HASH_TABLE_struct::buckets, ANTLR3_HASH_BUCKET_struct::entries, ANTLR3_HASH_ENUM_struct::entry, ANTLR3_HASH_ENUM_struct::free, ANTLR3_HASH_ENUM_struct::next, and ANTLR3_HASH_ENUM_struct::table.
Referenced by antlr3BitsetList().
static int antlr3EnumNext (pANTLR3_HASH_ENUM en, pANTLR3_HASH_KEY * key, void ** data) [static]
Return the next entry in the hashtable being traversed by the supplied enumeration. Parameters:
-
en Pointer to the enumeration tracking structure
key Pointer to void pointer, where the key pointer is returned.
data Pointer to void pointer where the data pointer is returned.
Returns:
-
- *
- ANTLR3_SUCCESS if there was a next key
- *
- ANTLR3_FAIL if there were no more keys
Remarks:
- No checking of input structure is performed!
References ANTLR3_FAIL, ANTLR3_SUCCESS, antlr3EnumNextEntry(), ANTLR3_HASH_ENUM_struct::bucket, ANTLR3_HASH_ENTRY_struct::data, ANTLR3_HASH_ENUM_struct::entry, ANTLR3_HASH_ENTRY_struct::keybase, ANTLR3_HASH_TABLE_struct::modulo, and ANTLR3_HASH_ENUM_struct::table.
Referenced by antlr3EnumNew().
static void antlr3EnumNextEntry (pANTLR3_HASH_ENUM en) [static]
Local function to advance the entry pointer of an enumeration structure to the next valid entry (if there is one). Parameters:
- enum Pointer to ANTLR3 enumeration structure returned by antlr3EnumNew()
Remarks:
-
- *
- 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.
References ANTLR3_HASH_ENUM_struct::bucket, ANTLR3_HASH_TABLE_struct::buckets, ANTLR3_HASH_BUCKET_struct::entries, ANTLR3_HASH_ENUM_struct::entry, ANTLR3_HASH_TABLE_struct::modulo, ANTLR3_HASH_ENTRY_struct::nextEntry, and ANTLR3_HASH_ENUM_struct::table.
Referenced by antlr3EnumNew(), and antlr3EnumNext().
ANTLR3_API ANTLR3_UINT32 antlr3Hash (void * key, ANTLR3_UINT32 keylen)
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.
Referenced by antlr3HashGet(), antlr3HashPut(), and antlr3HashRemove().
static void antlr3HashDelete (pANTLR3_HASH_TABLE table, void * key) [static]
Takes the element with the supplied key out of the list, and deletes the data calling the supplied free() routine if any.
References ANTLR3_FREE, antlr3HashRemove(), and ANTLR3_HASH_ENTRY_struct::data.
Referenced by antlr3HashTableNew().
static void antlr3HashDeleteI (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key) [static]
Takes the element with the supplied key out of the list, and deletes the data calling the supplied free() routine if any.
References ANTLR3_FREE, antlr3HashRemoveI(), and ANTLR3_HASH_ENTRY_struct::data.
Referenced by antlr3HashTableNew().
static void antlr3HashFree (pANTLR3_HASH_TABLE table) [static]
References ANTLR3_FREE, ANTLR3_HASH_TYPE_STR, ANTLR3_HASH_TABLE_struct::buckets, ANTLR3_HASH_ENTRY_struct::data, ANTLR3_HASH_BUCKET_struct::entries, ANTLR3_HASH_KEY_struct::key, ANTLR3_HASH_ENTRY_struct::keybase, ANTLR3_HASH_TABLE_struct::modulo, ANTLR3_HASH_ENTRY_struct::nextEntry, ANTLR3_HASH_KEY_struct::sKey, and ANTLR3_HASH_KEY_struct::type.
Referenced by antlr3HashTableNew().
static void * antlr3HashGet (pANTLR3_HASH_TABLE table, void * key) [static]
Return the element pointer in the hash table for a particular key value, or NULL if it don't exist (or was itself NULL).
References antlr3Hash(), ANTLR3_HASH_TABLE_struct::buckets, ANTLR3_HASH_ENTRY_struct::data, ANTLR3_HASH_BUCKET_struct::entries, ANTLR3_HASH_KEY_struct::key, ANTLR3_HASH_ENTRY_struct::keybase, ANTLR3_HASH_TABLE_struct::modulo, ANTLR3_HASH_ENTRY_struct::nextEntry, and ANTLR3_HASH_KEY_struct::sKey.
Referenced by antlr3HashTableNew().
static void * antlr3HashGetI (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key) [static]
Return the element pointer in the hash table for a particular key value, or NULL if it don't exist (or was itself NULL).
References ANTLR3_HASH_TABLE_struct::buckets, ANTLR3_HASH_ENTRY_struct::data, ANTLR3_HASH_BUCKET_struct::entries, ANTLR3_HASH_KEY_struct::iKey, ANTLR3_HASH_KEY_struct::key, ANTLR3_HASH_ENTRY_struct::keybase, ANTLR3_HASH_TABLE_struct::modulo, and ANTLR3_HASH_ENTRY_struct::nextEntry.
Referenced by antlr3HashTableNew().
static ANTLR3_INT32 antlr3HashPut (pANTLR3_HASH_TABLE table, void * key, void * element, void(ANTLR3_CDECL *freeptr)(void *)) [static]
Add the element pointer in to the table, based upon the hash of the provided key.
References ANTLR3_HASH_TABLE_struct::allowDups, ANTLR3_ERR_HASHDUP, ANTLR3_ERR_NOMEM, ANTLR3_FALSE, ANTLR3_HASH_TYPE_STR, ANTLR3_MALLOC, ANTLR3_STRDUP, ANTLR3_SUCCESS, ANTLR3_TRUE, antlr3Hash(), ANTLR3_HASH_TABLE_struct::buckets, ANTLR3_HASH_TABLE_struct::count, ANTLR3_HASH_ENTRY_struct::data, ANTLR3_HASH_TABLE_struct::doStrdup, ANTLR3_HASH_BUCKET_struct::entries, ANTLR3_HASH_KEY_struct::key, ANTLR3_HASH_ENTRY_struct::keybase, ANTLR3_HASH_TABLE_struct::modulo, ANTLR3_HASH_ENTRY_struct::nextEntry, ANTLR3_HASH_KEY_struct::sKey, and ANTLR3_HASH_KEY_struct::type.
Referenced by antlr3HashTableNew().
static ANTLR3_INT32 antlr3HashPutI (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key, void * element, void(ANTLR3_CDECL *freeptr)(void *)) [static]
Add the element pointer in to the table, based upon the hash of the provided key.
References ANTLR3_HASH_TABLE_struct::allowDups, ANTLR3_ERR_HASHDUP, ANTLR3_ERR_NOMEM, ANTLR3_FALSE, ANTLR3_HASH_TYPE_INT, ANTLR3_MALLOC, ANTLR3_SUCCESS, ANTLR3_HASH_TABLE_struct::buckets, ANTLR3_HASH_TABLE_struct::count, ANTLR3_HASH_ENTRY_struct::data, ANTLR3_HASH_BUCKET_struct::entries, ANTLR3_HASH_KEY_struct::iKey, ANTLR3_HASH_KEY_struct::key, ANTLR3_HASH_ENTRY_struct::keybase, ANTLR3_HASH_TABLE_struct::modulo, ANTLR3_HASH_ENTRY_struct::nextEntry, and ANTLR3_HASH_KEY_struct::type.
Referenced by antlr3HashTableNew().
static pANTLR3_HASH_ENTRY antlr3HashRemove (pANTLR3_HASH_TABLE table, void * key) [static]
Remove the element in the hash table for a particular key value, if it exists - no error if it does not.
References ANTLR3_FREE, ANTLR3_TRUE, antlr3Hash(), ANTLR3_HASH_TABLE_struct::buckets, ANTLR3_HASH_TABLE_struct::count, ANTLR3_HASH_TABLE_struct::doStrdup, ANTLR3_HASH_BUCKET_struct::entries, ANTLR3_HASH_KEY_struct::key, ANTLR3_HASH_ENTRY_struct::keybase, ANTLR3_HASH_TABLE_struct::modulo, ANTLR3_HASH_ENTRY_struct::nextEntry, and ANTLR3_HASH_KEY_struct::sKey.
Referenced by antlr3HashDelete(), and antlr3HashTableNew().
static pANTLR3_HASH_ENTRY antlr3HashRemoveI (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key) [static]
Remove a numeric keyed entry from a hash table if it exists, no error if it does not exist.
References ANTLR3_HASH_TABLE_struct::buckets, ANTLR3_HASH_TABLE_struct::count, ANTLR3_HASH_BUCKET_struct::entries, ANTLR3_HASH_KEY_struct::iKey, ANTLR3_HASH_KEY_struct::key, ANTLR3_HASH_ENTRY_struct::keybase, ANTLR3_HASH_TABLE_struct::modulo, and ANTLR3_HASH_ENTRY_struct::nextEntry.
Referenced by antlr3HashDeleteI(), and antlr3HashTableNew().
static ANTLR3_UINT32 antlr3HashSize (pANTLR3_HASH_TABLE table) [static]
return the current size of the hash table
References ANTLR3_HASH_TABLE_struct::count.
Referenced by antlr3HashTableNew().
pANTLR3_HASH_TABLE antlr3HashTableNew (ANTLR3_UINT32 sizeHint)
References ANTLR3_HASH_TABLE_struct::allowDups, ANTLR3_FALSE, ANTLR3_FREE, ANTLR3_MALLOC, ANTLR3_TRUE, antlr3HashDelete(), antlr3HashDeleteI(), antlr3HashFree(), antlr3HashGet(), antlr3HashGetI(), antlr3HashPut(), antlr3HashPutI(), antlr3HashRemove(), antlr3HashRemoveI(), antlr3HashSize(), ANTLR3_HASH_TABLE_struct::buckets, ANTLR3_HASH_TABLE_struct::count, ANTLR3_HASH_TABLE_struct::del, ANTLR3_HASH_TABLE_struct::delI, ANTLR3_HASH_TABLE_struct::doStrdup, ANTLR3_HASH_BUCKET_struct::entries, ANTLR3_HASH_TABLE_struct::free, ANTLR3_HASH_TABLE_struct::get, ANTLR3_HASH_TABLE_struct::getI, ANTLR3_HASH_TABLE_struct::modulo, ANTLR3_HASH_TABLE_struct::put, ANTLR3_HASH_TABLE_struct::putI, ANTLR3_HASH_TABLE_struct::remove, ANTLR3_HASH_TABLE_struct::removeI, and ANTLR3_HASH_TABLE_struct::size.
Referenced by antlr3ListNew().
pANTLR3_INT_TRIE antlr3IntTrieNew (ANTLR3_UINT32 depth)
References ANTLR3_INT_TRIE_struct::add, ANTLR3_CALLOC, ANTLR3_ERR_NOMEM, ANTLR3_FREE, ANTLR3_FUNC_PTR, ANTLR3_INT_TRIE_NODE_struct::bitNum, ANTLR3_INT_TRIE_struct::count, ANTLR3_INT_TRIE_struct::del, ANTLR3_INT_TRIE_struct::free, ANTLR3_INT_TRIE_struct::get, intTrieAdd(), intTrieDel(), intTrieFree(), intTrieGet(), ANTLR3_INT_TRIE_NODE_struct::leftN, ANTLR3_INT_TRIE_NODE_struct::rightN, and ANTLR3_INT_TRIE_struct::root.
Referenced by getRuleMemoization(), and reset().
static ANTLR3_INT32 antlr3ListAdd (pANTLR3_LIST list, void * element, void(ANTLR3_CDECL *freeptr)(void *)) [static]
Add the supplied element to the list, at the next available key.
References ANTLR3_LIST_struct::put, ANTLR3_HASH_TABLE_struct::size, and ANTLR3_LIST_struct::table.
Referenced by antlr3ListNew().
static void antlr3ListDelete (pANTLR3_LIST list, ANTLR3_INTKEY key) [static]
References ANTLR3_HASH_TABLE_struct::delI, and ANTLR3_LIST_struct::table.
Referenced by antlr3ListNew().
static void antlr3ListFree (pANTLR3_LIST list) [static]
References ANTLR3_FREE, ANTLR3_HASH_TABLE_struct::free, and ANTLR3_LIST_struct::table.
Referenced by antlr3ListNew().
static void * antlr3ListGet (pANTLR3_LIST list, ANTLR3_INTKEY key) [static]
References ANTLR3_HASH_TABLE_struct::getI, and ANTLR3_LIST_struct::table.
Referenced by antlr3ListNew().
ANTLR3_API pANTLR3_LIST antlr3ListNew (ANTLR3_UINT32 sizeHint)
References ANTLR3_LIST_struct::add, ANTLR3_ERR_NOMEM, ANTLR3_FUNC_PTR, ANTLR3_MALLOC, antlr3HashTableNew(), antlr3ListAdd(), antlr3ListDelete(), antlr3ListFree(), antlr3ListGet(), antlr3ListPut(), antlr3ListRemove(), antlr3ListSize(), ANTLR3_LIST_struct::del, ANTLR3_LIST_struct::free, ANTLR3_LIST_struct::get, ANTLR3_LIST_struct::put, ANTLR3_LIST_struct::remove, ANTLR3_LIST_struct::size, and ANTLR3_LIST_struct::table.
Referenced by discardTokenType(), getTokensSet(), and setTokenTypeChannel().
static ANTLR3_INT32 antlr3ListPut (pANTLR3_LIST list, ANTLR3_INTKEY key, void * element, void(ANTLR3_CDECL *freeptr)(void *)) [static]
References ANTLR3_HASH_TABLE_struct::putI, and ANTLR3_LIST_struct::table.
Referenced by antlr3ListNew().
static void * antlr3ListRemove (pANTLR3_LIST list, ANTLR3_INTKEY key) [static]
Remove from the list, but don't free the element, just send it back to the caller.
References ANTLR3_HASH_ENTRY_struct::data, ANTLR3_HASH_TABLE_struct::removeI, and ANTLR3_LIST_struct::table.
Referenced by antlr3ListNew().
static ANTLR3_UINT32 antlr3ListSize (pANTLR3_LIST list) [static]
References ANTLR3_HASH_TABLE_struct::size, and ANTLR3_LIST_struct::table.
Referenced by antlr3ListNew().
ANTLR3_API void antlr3SetVectorApi (pANTLR3_VECTOR vector, ANTLR3_UINT32 sizeHint)
References ANTLR3_VECTOR_struct::add, ANTLR3_FALSE, ANTLR3_FREE, ANTLR3_MALLOC, ANTLR3_VECTOR_INTERNAL_SIZE, antlr3VectorAdd(), antlr3VectorClear(), antlr3VectorDel(), antlr3VectorFree(), antlr3VectorGet(), antlr3VectorSet(), antlr3VectorSize(), antlr3VectorSwap(), antrl3VectorRemove(), ANTLR3_VECTOR_struct::clear, ANTLR3_VECTOR_struct::count, ANTLR3_VECTOR_struct::del, ANTLR3_VECTOR_struct::elements, ANTLR3_VECTOR_struct::elementsSize, ANTLR3_VECTOR_struct::factoryMade, ANTLR3_VECTOR_struct::get, ANTLR3_VECTOR_struct::internal, ANTLR3_VECTOR_struct::remove, ANTLR3_VECTOR_struct::set, ANTLR3_VECTOR_struct::size, and ANTLR3_VECTOR_struct::swap.
Referenced by antlr3VectorFactoryNew(), antlr3VectorNew(), and newVector().
static void antlr3StackFree (pANTLR3_STACK stack) [static]
References ANTLR3_FREE, ANTLR3_STACK_struct::top, and ANTLR3_STACK_struct::vector.
Referenced by antlr3StackNew().
static void * antlr3StackGet (pANTLR3_STACK stack, ANTLR3_INTKEY key) [static]
References ANTLR3_VECTOR_struct::get, and ANTLR3_STACK_struct::vector.
Referenced by antlr3StackNew().
ANTLR3_API pANTLR3_STACK antlr3StackNew (ANTLR3_UINT32 sizeHint)
References ANTLR3_ERR_NOMEM, ANTLR3_FUNC_PTR, ANTLR3_MALLOC, antlr3StackFree(), antlr3StackGet(), antlr3StackPeek(), antlr3StackPop(), antlr3StackPush(), antlr3StackSize(), antlr3VectorNew(), ANTLR3_STACK_struct::free, ANTLR3_STACK_struct::get, ANTLR3_STACK_struct::peek, ANTLR3_STACK_struct::pop, ANTLR3_STACK_struct::push, ANTLR3_STACK_struct::size, ANTLR3_STACK_struct::top, and ANTLR3_STACK_struct::vector.
Referenced by antlr3ArboretumNew(), antlr3CommonTreeNodeStreamNew(), antlr3VectorFactoryNew(), pushCharStream(), and reset().
static void * antlr3StackPeek (pANTLR3_STACK stack) [static]
References ANTLR3_STACK_struct::top.
Referenced by antlr3StackNew().
static void * antlr3StackPop (pANTLR3_STACK stack) [static]
References ANTLR3_VECTOR_struct::count, ANTLR3_VECTOR_struct::del, ANTLR3_VECTOR_struct::get, ANTLR3_STACK_struct::top, and ANTLR3_STACK_struct::vector.
Referenced by antlr3StackNew().
static ANTLR3_BOOLEAN antlr3StackPush (pANTLR3_STACK stack, void * element, void(ANTLR3_CDECL *freeptr)(void *)) [static]
References ANTLR3_VECTOR_struct::add, ANTLR3_STACK_struct::top, and ANTLR3_STACK_struct::vector.
Referenced by antlr3StackNew().
static ANTLR3_UINT32 antlr3StackSize (pANTLR3_STACK stack) [static]
References ANTLR3_VECTOR_struct::count, and ANTLR3_STACK_struct::vector.
Referenced by antlr3StackNew().
ANTLR3_API pANTLR3_TOPO antlr3TopoNew ()
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
References addEdge(), ANTLR3_TOPO_struct::addEdge, ANTLR3_FALSE, ANTLR3_MALLOC, ANTLR3_TOPO_struct::cycle, ANTLR3_TOPO_struct::cycleMark, ANTLR3_TOPO_struct::edges, ANTLR3_TOPO_struct::free, freeTopo(), ANTLR3_TOPO_struct::hasCycle, ANTLR3_TOPO_struct::limit, ANTLR3_TOPO_struct::sorted, sortToArray(), ANTLR3_TOPO_struct::sortToArray, sortVector(), ANTLR3_TOPO_struct::sortVector, and ANTLR3_TOPO_struct::visited.
static ANTLR3_UINT32 antlr3VectorAdd (pANTLR3_VECTOR vector, void * element, void(ANTLR3_CDECL *freeptr)(void *)) [static]
Add the supplied pointer and freeing function pointer to the list, expanding the vector if needed.
References antlr3VectorResize(), ANTLR3_VECTOR_struct::count, ANTLR3_VECTOR_ELEMENT_struct::element, ANTLR3_VECTOR_struct::elements, and ANTLR3_VECTOR_struct::elementsSize.
Referenced by antlr3SetVectorApi().
static void antlr3VectorClear (pANTLR3_VECTOR vector) [static]
References ANTLR3_VECTOR_struct::count, ANTLR3_VECTOR_ELEMENT_struct::element, and ANTLR3_VECTOR_struct::elements.
Referenced by antlr3SetVectorApi().
static void antlr3VectorDel (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry) [static]
References ANTLR3_MEMMOVE, ANTLR3_VECTOR_struct::count, ANTLR3_VECTOR_ELEMENT_struct::element, and ANTLR3_VECTOR_struct::elements.
Referenced by antlr3SetVectorApi().
ANTLR3_API pANTLR3_VECTOR_FACTORY antlr3VectorFactoryNew (ANTLR3_UINT32 sizeHint)
Vector factory creation.
References ANTLR3_MALLOC, ANTLR3_TRUE, ANTLR3_VECTOR_INTERNAL_SIZE, antlr3SetVectorApi(), antlr3StackNew(), ANTLR3_VECTOR_FACTORY_struct::close, closeVectorFactory(), ANTLR3_VECTOR_struct::factoryMade, ANTLR3_VECTOR_FACTORY_struct::freeStack, newPool(), newVector(), ANTLR3_VECTOR_FACTORY_struct::newVector, ANTLR3_VECTOR_FACTORY_struct::pools, returnVector(), ANTLR3_VECTOR_FACTORY_struct::returnVector, ANTLR3_VECTOR_FACTORY_struct::thisPool, and ANTLR3_VECTOR_FACTORY_struct::unTruc.
Referenced by antlr3ArboretumNew().
static void ANTLR3_CDECL antlr3VectorFree (pANTLR3_VECTOR vector) [static]
References ANTLR3_FALSE, ANTLR3_FREE, ANTLR3_VECTOR_INTERNAL_SIZE, ANTLR3_VECTOR_struct::count, ANTLR3_VECTOR_ELEMENT_struct::element, ANTLR3_VECTOR_struct::elements, ANTLR3_VECTOR_struct::elementsSize, and ANTLR3_VECTOR_struct::factoryMade.
Referenced by antlr3SetVectorApi().
static void * antlr3VectorGet (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry) [static]
References ANTLR3_VECTOR_ELEMENT_struct::element, and ANTLR3_VECTOR_struct::elements.
Referenced by antlr3SetVectorApi().
ANTLR3_API pANTLR3_VECTOR antlr3VectorNew (ANTLR3_UINT32 sizeHint)
References ANTLR3_ERR_NOMEM, ANTLR3_FUNC_PTR, ANTLR3_MALLOC, and antlr3SetVectorApi().
Referenced by antlr3BaseRecognizerNew(), antlr3CommonTokenStreamNew(), antlr3CommonTreeNodeStreamNew(), antlr3CommonTreeNodeStreamNewStream(), antlr3InputReset(), antlr3StackNew(), antlr3StringFactoryNew(), and replaceChildren().
static void antlr3VectorResize (pANTLR3_VECTOR vector, ANTLR3_UINT32 hint) [static]
References ANTLR3_MALLOC, ANTLR3_MEMCPY, ANTLR3_REALLOC, ANTLR3_VECTOR_INTERNAL_SIZE, ANTLR3_VECTOR_struct::elements, ANTLR3_VECTOR_struct::elementsSize, and ANTLR3_VECTOR_struct::internal.
Referenced by antlr3VectorAdd(), and antlr3VectorSet().
static ANTLR3_UINT32 antlr3VectorSet (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry, void * element, void(ANTLR3_CDECL *freeptr)(void *), ANTLR3_BOOLEAN freeExisting) [static]
Replace the element at the specified entry point with the supplied entry.
References antlr3VectorResize(), ANTLR3_VECTOR_struct::count, ANTLR3_VECTOR_ELEMENT_struct::element, ANTLR3_VECTOR_struct::elements, and ANTLR3_VECTOR_struct::elementsSize.
Referenced by antlr3SetVectorApi().
static ANTLR3_UINT32 antlr3VectorSize (pANTLR3_VECTOR vector) [static]
References ANTLR3_VECTOR_struct::count.
Referenced by antlr3SetVectorApi().
static ANTLR3_BOOLEAN antlr3VectorSwap (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry1, ANTLR3_UINT32 entry2) [static]
Replace the element at the specified entry point with the supplied entry.
References ANTLR3_CDECL, ANTLR3_FALSE, ANTLR3_TRUE, ANTLR3_VECTOR_ELEMENT_struct::element, ANTLR3_VECTOR_struct::elements, and ANTLR3_VECTOR_struct::elementsSize.
Referenced by antlr3SetVectorApi().
static void * antrl3VectorRemove (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry) [static]
Remove the entry from the vector, but do not free any entry, even if it has a free pointer.
References ANTLR3_MEMMOVE, ANTLR3_VECTOR_struct::count, ANTLR3_VECTOR_ELEMENT_struct::element, and ANTLR3_VECTOR_struct::elements.
Referenced by antlr3SetVectorApi().
static void closeVectorFactory (pANTLR3_VECTOR_FACTORY factory) [static]
References ANTLR3_FACTORY_VPOOL_SIZE, ANTLR3_FREE, ANTLR3_TRUE, ANTLR3_VECTOR_INTERNAL_SIZE, ANTLR3_VECTOR_struct::elements, ANTLR3_VECTOR_struct::elementsSize, ANTLR3_VECTOR_struct::factoryMade, ANTLR3_STACK_struct::free, ANTLR3_VECTOR_FACTORY_struct::freeStack, ANTLR3_VECTOR_FACTORY_struct::nextVector, ANTLR3_VECTOR_FACTORY_struct::pools, and ANTLR3_VECTOR_FACTORY_struct::thisPool.
Referenced by antlr3VectorFactoryNew().
static void DFS (pANTLR3_TOPO topo, ANTLR3_UINT32 node) [static]
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.
References ANTLR3_BITSET_struct::add, ANTLR3_FALSE, ANTLR3_TRUE, ANTLR3_TOPO_struct::cycle, ANTLR3_TOPO_struct::cycleMark, ANTLR3_TOPO_struct::edges, ANTLR3_TOPO_struct::hasCycle, ANTLR3_BITSET_struct::isMember, ANTLR3_TOPO_struct::limit, ANTLR3_BITSET_struct::numBits, ANTLR3_BITSET_struct::size, ANTLR3_TOPO_struct::sorted, and ANTLR3_TOPO_struct::visited.
static void freeIntNode (pANTLR3_INT_TRIE_NODE node) [static]
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.
References ANTLR3_FREE, ANTLR3_HASH_TYPE_STR, ANTLR3_INT_TRIE_NODE_struct::bitNum, ANTLR3_INT_TRIE_NODE_struct::buckets, ANTLR3_TRIE_ENTRY_struct::data, ANTLR3_INT_TRIE_NODE_struct::leftN, ANTLR3_TRIE_ENTRY_struct::next, ANTLR3_TRIE_ENTRY_struct::ptr, ANTLR3_INT_TRIE_NODE_struct::rightN, and ANTLR3_TRIE_ENTRY_struct::type.
static void freeTopo (pANTLR3_TOPO topo) [static]
References ANTLR3_FREE, ANTLR3_TOPO_struct::cycle, ANTLR3_TOPO_struct::edges, ANTLR3_BITSET_struct::free, ANTLR3_TOPO_struct::limit, ANTLR3_TOPO_struct::sorted, and ANTLR3_TOPO_struct::visited.
Referenced by antlr3TopoNew().
static ANTLR3_BOOLEAN intTrieAdd (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key, ANTLR3_UINT32 type, ANTLR3_INTKEY intVal, void * data, void(ANTLR3_CDECL *freeptr)(void *)) [static]
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'.
References ANTLR3_INT_TRIE_struct::allowDups, ANTLR3_CALLOC, ANTLR3_FALSE, ANTLR3_HASH_TYPE_STR, ANTLR3_TRUE, ANTLR3_INT_TRIE_NODE_struct::bitNum, ANTLR3_INT_TRIE_NODE_struct::buckets, ANTLR3_INT_TRIE_struct::count, ANTLR3_TRIE_ENTRY_struct::data, ANTLR3_TRIE_ENTRY_struct::intVal, ANTLR3_INT_TRIE_NODE_struct::key, ANTLR3_INT_TRIE_NODE_struct::leftN, ANTLR3_TRIE_ENTRY_struct::next, nextNode(), ANTLR3_TRIE_ENTRY_struct::ptr, ANTLR3_INT_TRIE_NODE_struct::rightN, ANTLR3_INT_TRIE_struct::root, and ANTLR3_TRIE_ENTRY_struct::type.
Referenced by antlr3IntTrieNew().
static ANTLR3_BOOLEAN intTrieDel (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key) [static]
References ANTLR3_FALSE, and ANTLR3_INT_TRIE_struct::root.
Referenced by antlr3IntTrieNew().
static void intTrieFree (pANTLR3_INT_TRIE trie) [static]
Called to free all nodes and the structure itself.
References ANTLR3_FREE, freeIntNode(), and ANTLR3_INT_TRIE_struct::root.
Referenced by antlr3IntTrieNew().
static pANTLR3_TRIE_ENTRY intTrieGet (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key) [static]
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.
References ANTLR3_INT_TRIE_NODE_struct::bitNum, ANTLR3_INT_TRIE_NODE_struct::buckets, ANTLR3_INT_TRIE_struct::count, ANTLR3_INT_TRIE_NODE_struct::key, ANTLR3_INT_TRIE_NODE_struct::leftN, nextNode(), ANTLR3_INT_TRIE_NODE_struct::rightN, and ANTLR3_INT_TRIE_struct::root.
Referenced by antlr3IntTrieNew().
static void newPool (pANTLR3_VECTOR_FACTORY factory) [static]
References ANTLR3_FACTORY_VPOOL_SIZE, ANTLR3_MALLOC, ANTLR3_REALLOC, ANTLR3_VECTOR_FACTORY_struct::nextVector, ANTLR3_VECTOR_FACTORY_struct::pools, and ANTLR3_VECTOR_FACTORY_struct::thisPool.
Referenced by antlr3VectorFactoryNew(), and newVector().
static pANTLR3_VECTOR newVector (pANTLR3_VECTOR_FACTORY factory) [static]
References ANTLR3_FACTORY_VPOOL_SIZE, ANTLR3_TRUE, ANTLR3_VECTOR_INTERNAL_SIZE, antlr3SetVectorApi(), ANTLR3_VECTOR_struct::elements, ANTLR3_VECTOR_struct::factoryMade, ANTLR3_VECTOR_FACTORY_struct::freeStack, ANTLR3_VECTOR_struct::internal, newPool(), ANTLR3_VECTOR_FACTORY_struct::nextVector, ANTLR3_STACK_struct::peek, ANTLR3_VECTOR_FACTORY_struct::pools, ANTLR3_STACK_struct::pop, and ANTLR3_VECTOR_FACTORY_struct::thisPool.
Referenced by antlr3VectorFactoryNew().
static void returnVector (pANTLR3_VECTOR_FACTORY factory, pANTLR3_VECTOR vector) [static]
References ANTLR3_VECTOR_struct::clear, ANTLR3_VECTOR_FACTORY_struct::freeStack, and ANTLR3_STACK_struct::push.
Referenced by antlr3VectorFactoryNew().
static pANTLR3_UINT32 sortToArray (pANTLR3_TOPO topo) [static]
References ANTLR3_FALSE, ANTLR3_MALLOC, ANTLR3_TRUE, antlr3BitsetNew(), ANTLR3_TOPO_struct::cycle, DFS(), ANTLR3_TOPO_struct::edges, ANTLR3_TOPO_struct::hasCycle, ANTLR3_BITSET_struct::isMember, ANTLR3_TOPO_struct::limit, ANTLR3_TOPO_struct::sorted, and ANTLR3_TOPO_struct::visited.
Referenced by antlr3TopoNew().
static void sortVector (pANTLR3_TOPO topo, pANTLR3_VECTOR v) [static]
References ANTLR3_FREE, ANTLR3_MALLOC, ANTLR3_TRUE, ANTLR3_VECTOR_struct::count, ANTLR3_TOPO_struct::hasCycle, ANTLR3_TOPO_struct::limit, ANTLR3_TOPO_struct::sorted, ANTLR3_TOPO_struct::sortToArray, and ANTLR3_VECTOR_struct::swap.
Referenced by antlr3TopoNew().
Variable Documentation
ANTLR3_UINT8 bitIndex[256] [static]Initial value:
{
0,
0,
1, 1,
2, 2, 2, 2,
3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
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,
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,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
}
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
ANTLR3_UINT64 bitMask[64] [static]Initial value:
{
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
}
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.
Author
Generated automatically by Doxygen for ANTLR3C from the source code.