2 /// Provides a number of useful functions that are roughly equivalent
\r
3 /// to java HashTable and List for the purposes of Antlr 3 C runtime.
\r
4 /// Also useable by the C programmer for things like symbol tables pointers
\r
9 // [The "BSD licence"]
\r
10 // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
\r
11 // http://www.temporal-wave.com
\r
12 // http://www.linkedin.com/in/jimidle
\r
14 // All rights reserved.
\r
16 // Redistribution and use in source and binary forms, with or without
\r
17 // modification, are permitted provided that the following conditions
\r
19 // 1. Redistributions of source code must retain the above copyright
\r
20 // notice, this list of conditions and the following disclaimer.
\r
21 // 2. Redistributions in binary form must reproduce the above copyright
\r
22 // notice, this list of conditions and the following disclaimer in the
\r
23 // documentation and/or other materials provided with the distribution.
\r
24 // 3. The name of the author may not be used to endorse or promote products
\r
25 // derived from this software without specific prior written permission.
\r
27 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
\r
28 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
\r
29 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
\r
30 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
\r
31 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
\r
32 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
\r
33 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
\r
34 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
\r
35 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
\r
36 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
\r
40 #include "antlr3collections.h"
\r
42 // Interface functions for hash table
\r
45 // String based keys
\r
47 static void antlr3HashDelete (pANTLR3_HASH_TABLE table, void * key);
\r
48 static void * antlr3HashGet (pANTLR3_HASH_TABLE table, void * key);
\r
49 static pANTLR3_HASH_ENTRY antlr3HashRemove (pANTLR3_HASH_TABLE table, void * key);
\r
50 static ANTLR3_INT32 antlr3HashPut (pANTLR3_HASH_TABLE table, void * key, void * element, void (ANTLR3_CDECL *freeptr)(void *));
\r
52 // Integer based keys (Lists and so on)
\r
54 static void antlr3HashDeleteI (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key);
\r
55 static void * antlr3HashGetI (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key);
\r
56 static pANTLR3_HASH_ENTRY antlr3HashRemoveI (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key);
\r
57 static ANTLR3_INT32 antlr3HashPutI (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *));
\r
59 static void antlr3HashFree (pANTLR3_HASH_TABLE table);
\r
60 static ANTLR3_UINT32 antlr3HashSize (pANTLR3_HASH_TABLE table);
\r
64 // Interface functions for enumeration
\r
66 static int antlr3EnumNext (pANTLR3_HASH_ENUM en, pANTLR3_HASH_KEY * key, void ** data);
\r
67 static void antlr3EnumFree (pANTLR3_HASH_ENUM en);
\r
69 // Interface functions for List
\r
71 static void antlr3ListFree (pANTLR3_LIST list);
\r
72 static void antlr3ListDelete(pANTLR3_LIST list, ANTLR3_INTKEY key);
\r
73 static void * antlr3ListGet (pANTLR3_LIST list, ANTLR3_INTKEY key);
\r
74 static ANTLR3_INT32 antlr3ListPut (pANTLR3_LIST list, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *));
\r
75 static ANTLR3_INT32 antlr3ListAdd (pANTLR3_LIST list, void * element, void (ANTLR3_CDECL *freeptr)(void *));
\r
76 static void * antlr3ListRemove(pANTLR3_LIST list, ANTLR3_INTKEY key);
\r
77 static ANTLR3_UINT32 antlr3ListSize (pANTLR3_LIST list);
\r
79 // Interface functions for Stack
\r
81 static void antlr3StackFree (pANTLR3_STACK stack);
\r
82 static void * antlr3StackPop (pANTLR3_STACK stack);
\r
83 static void * antlr3StackGet (pANTLR3_STACK stack, ANTLR3_INTKEY key);
\r
84 static ANTLR3_BOOLEAN antlr3StackPush (pANTLR3_STACK stack, void * element, void (ANTLR3_CDECL *freeptr)(void *));
\r
85 static ANTLR3_UINT32 antlr3StackSize (pANTLR3_STACK stack);
\r
86 static void * antlr3StackPeek (pANTLR3_STACK stack);
\r
88 // Interface functions for vectors
\r
90 static void ANTLR3_CDECL antlr3VectorFree (pANTLR3_VECTOR vector);
\r
91 static void antlr3VectorDel (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry);
\r
92 static void * antlr3VectorGet (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry);
\r
93 static void * antrl3VectorRemove (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry);
\r
94 static void antlr3VectorClear (pANTLR3_VECTOR vector);
\r
95 static ANTLR3_UINT32 antlr3VectorAdd (pANTLR3_VECTOR vector, void * element, void (ANTLR3_CDECL *freeptr)(void *));
\r
96 static ANTLR3_UINT32 antlr3VectorSet (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry, void * element, void (ANTLR3_CDECL *freeptr)(void *), ANTLR3_BOOLEAN freeExisting);
\r
97 static ANTLR3_UINT32 antlr3VectorSize (pANTLR3_VECTOR vector);
\r
98 static ANTLR3_BOOLEAN antlr3VectorSwap (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry1, ANTLR3_UINT32 entry2);
\r
100 static void newPool (pANTLR3_VECTOR_FACTORY factory);
\r
101 static void closeVectorFactory (pANTLR3_VECTOR_FACTORY factory);
\r
102 static pANTLR3_VECTOR newVector (pANTLR3_VECTOR_FACTORY factory);
\r
103 static void returnVector (pANTLR3_VECTOR_FACTORY factory, pANTLR3_VECTOR vector);
\r
106 // Interface functions for int TRIE
\r
108 static pANTLR3_TRIE_ENTRY intTrieGet (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key);
\r
109 static ANTLR3_BOOLEAN intTrieDel (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key);
\r
110 static ANTLR3_BOOLEAN intTrieAdd (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key, ANTLR3_UINT32 type, ANTLR3_INTKEY intType, void * data, void (ANTLR3_CDECL *freeptr)(void *));
\r
111 static void intTrieFree (pANTLR3_INT_TRIE trie);
\r
114 // Interface functions for topological sorter
\r
116 static void addEdge (pANTLR3_TOPO topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency);
\r
117 static pANTLR3_UINT32 sortToArray (pANTLR3_TOPO topo);
\r
118 static void sortVector (pANTLR3_TOPO topo, pANTLR3_VECTOR v);
\r
119 static void freeTopo (pANTLR3_TOPO topo);
\r
121 // Local function to advance enumeration structure pointers
\r
123 static void antlr3EnumNextEntry(pANTLR3_HASH_ENUM en);
\r
126 antlr3HashTableNew(ANTLR3_UINT32 sizeHint)
\r
128 // All we have to do is create the hashtable tracking structure
\r
129 // and allocate memory for the requested number of buckets.
\r
131 pANTLR3_HASH_TABLE table;
\r
133 ANTLR3_UINT32 bucket; // Used to traverse the buckets
\r
135 table = ANTLR3_MALLOC(sizeof(ANTLR3_HASH_TABLE));
\r
137 // Error out if no memory left
\r
143 // Allocate memory for the buckets
\r
145 table->buckets = (pANTLR3_HASH_BUCKET) ANTLR3_MALLOC((size_t) (sizeof(ANTLR3_HASH_BUCKET) * sizeHint));
\r
147 if (table->buckets == NULL)
\r
149 ANTLR3_FREE((void *)table);
\r
153 // Modulo of the table, (bucket count).
\r
155 table->modulo = sizeHint;
\r
157 table->count = 0; /* Nothing in there yet ( I hope) */
\r
159 /* Initialize the buckets to empty
\r
161 for (bucket = 0; bucket < sizeHint; bucket++)
\r
163 table->buckets[bucket].entries = NULL;
\r
166 /* Exclude duplicate entries by default
\r
168 table->allowDups = ANTLR3_FALSE;
\r
170 /* Assume that keys should by strduped before they are
\r
171 * entered in the table.
\r
173 table->doStrdup = ANTLR3_TRUE;
\r
175 /* Install the interface
\r
178 table->get = antlr3HashGet;
\r
179 table->put = antlr3HashPut;
\r
180 table->del = antlr3HashDelete;
\r
181 table->remove = antlr3HashRemove;
\r
183 table->getI = antlr3HashGetI;
\r
184 table->putI = antlr3HashPutI;
\r
185 table->delI = antlr3HashDeleteI;
\r
186 table->removeI = antlr3HashRemoveI;
\r
188 table->size = antlr3HashSize;
\r
189 table->free = antlr3HashFree;
\r
195 antlr3HashFree(pANTLR3_HASH_TABLE table)
\r
197 ANTLR3_UINT32 bucket; /* Used to traverse the buckets */
\r
199 pANTLR3_HASH_BUCKET thisBucket;
\r
200 pANTLR3_HASH_ENTRY entry;
\r
201 pANTLR3_HASH_ENTRY nextEntry;
\r
203 /* Free the table, all buckets and all entries, and all the
\r
204 * keys and data (if the table exists)
\r
208 for (bucket = 0; bucket < table->modulo; bucket++)
\r
210 thisBucket = &(table->buckets[bucket]);
\r
212 /* Allow sparse tables, though we don't create them as such at present
\r
214 if ( thisBucket != NULL)
\r
216 entry = thisBucket->entries;
\r
218 /* Search all entries in the bucket and free them up
\r
220 while (entry != NULL)
\r
222 /* Save next entry - we do not want to access memory in entry after we
\r
225 nextEntry = entry->nextEntry;
\r
227 /* Free any data pointer, this only happens if the user supplied
\r
228 * a pointer to a routine that knwos how to free the structure they
\r
229 * added to the table.
\r
231 if (entry->free != NULL)
\r
233 entry->free(entry->data);
\r
236 /* Free the key memory - we know that we allocated this
\r
238 if (entry->keybase.type == ANTLR3_HASH_TYPE_STR && entry->keybase.key.sKey != NULL)
\r
240 ANTLR3_FREE(entry->keybase.key.sKey);
\r
245 ANTLR3_FREE(entry);
\r
246 entry = nextEntry; /* Load next pointer to see if we shoud free it */
\r
248 /* Invalidate the current pointer
\r
250 thisBucket->entries = NULL;
\r
254 /* Now we can free the bucket memory
\r
256 ANTLR3_FREE(table->buckets);
\r
259 /* Now we free teh memory for the table itself
\r
261 ANTLR3_FREE(table);
\r
264 /** return the current size of the hash table
\r
266 static ANTLR3_UINT32 antlr3HashSize (pANTLR3_HASH_TABLE table)
\r
268 return table->count;
\r
271 /** Remove a numeric keyed entry from a hash table if it exists,
\r
272 * no error if it does not exist.
\r
274 static pANTLR3_HASH_ENTRY antlr3HashRemoveI (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key)
\r
276 ANTLR3_UINT32 hash;
\r
277 pANTLR3_HASH_BUCKET bucket;
\r
278 pANTLR3_HASH_ENTRY entry;
\r
279 pANTLR3_HASH_ENTRY * nextPointer;
\r
281 /* First we need to know the hash of the provided key
\r
283 hash = (ANTLR3_UINT32)(key % (ANTLR3_INTKEY)(table->modulo));
\r
285 /* Knowing the hash, we can find the bucket
\r
287 bucket = table->buckets + hash;
\r
289 /* Now, we traverse the entries in the bucket until
\r
290 * we find the key or the end of the entries in the bucket.
\r
291 * We track the element prior to the one we are examining
\r
292 * as we need to set its next pointer to the next pointer
\r
293 * of the entry we are deleting (if we find it).
\r
295 entry = bucket->entries; /* Entry to examine */
\r
296 nextPointer = & bucket->entries; /* Where to put the next pointer of the deleted entry */
\r
298 while (entry != NULL)
\r
300 /* See if this is the entry we wish to delete
\r
302 if (entry->keybase.key.iKey == key)
\r
304 /* It was the correct entry, so we set the next pointer
\r
305 * of the previous entry to the next pointer of this
\r
306 * located one, which takes it out of the chain.
\r
308 (*nextPointer) = entry->nextEntry;
\r
316 /* We found an entry but it wasn't the one that was wanted, so
\r
317 * move to the next one, if any.
\r
319 nextPointer = & (entry->nextEntry); /* Address of the next pointer in the current entry */
\r
320 entry = entry->nextEntry; /* Address of the next element in the bucket (if any) */
\r
324 return NULL; /* Not found */
\r
327 /** Remove the element in the hash table for a particular
\r
328 * key value, if it exists - no error if it does not.
\r
330 static pANTLR3_HASH_ENTRY
\r
331 antlr3HashRemove(pANTLR3_HASH_TABLE table, void * key)
\r
333 ANTLR3_UINT32 hash;
\r
334 pANTLR3_HASH_BUCKET bucket;
\r
335 pANTLR3_HASH_ENTRY entry;
\r
336 pANTLR3_HASH_ENTRY * nextPointer;
\r
338 /* First we need to know the hash of the provided key
\r
340 hash = antlr3Hash(key, (ANTLR3_UINT32)strlen((const char *)key));
\r
342 /* Knowing the hash, we can find the bucket
\r
344 bucket = table->buckets + (hash % table->modulo);
\r
346 /* Now, we traverse the entries in the bucket until
\r
347 * we find the key or the end of the entires in the bucket.
\r
348 * We track the element prior to the one we are exmaining
\r
349 * as we need to set its next pointer to the next pointer
\r
350 * of the entry we are deleting (if we find it).
\r
352 entry = bucket->entries; /* Entry to examine */
\r
353 nextPointer = & bucket->entries; /* Where to put the next pointer of the deleted entry */
\r
355 while (entry != NULL)
\r
357 /* See if this is the entry we wish to delete
\r
359 if (strcmp((const char *)key, (const char *)entry->keybase.key.sKey) == 0)
\r
361 /* It was the correct entry, so we set the next pointer
\r
362 * of the previous entry to the next pointer of this
\r
363 * located one, which takes it out of the chain.
\r
365 (*nextPointer) = entry->nextEntry;
\r
367 /* Release the key - if we allocated that
\r
369 if (table->doStrdup == ANTLR3_TRUE)
\r
371 ANTLR3_FREE(entry->keybase.key.sKey);
\r
373 entry->keybase.key.sKey = NULL;
\r
381 /* We found an entry but it wasn't the one that was wanted, so
\r
382 * move to the next one, if any.
\r
384 nextPointer = & (entry->nextEntry); /* Address of the next pointer in the current entry */
\r
385 entry = entry->nextEntry; /* Address of the next element in the bucket (if any) */
\r
389 return NULL; /* Not found */
\r
392 /** Takes the element with the supplied key out of the list, and deletes the data
\r
393 * calling the supplied free() routine if any.
\r
396 antlr3HashDeleteI (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key)
\r
398 pANTLR3_HASH_ENTRY entry;
\r
400 entry = antlr3HashRemoveI(table, key);
\r
402 /* Now we can free the elements and the entry in order
\r
404 if (entry != NULL && entry->free != NULL)
\r
406 /* Call programmer supplied function to release this entry data
\r
408 entry->free(entry->data);
\r
409 entry->data = NULL;
\r
411 /* Finally release the space for this entry block.
\r
413 ANTLR3_FREE(entry);
\r
416 /** Takes the element with the supplied key out of the list, and deletes the data
\r
417 * calling the supplied free() routine if any.
\r
420 antlr3HashDelete (pANTLR3_HASH_TABLE table, void * key)
\r
422 pANTLR3_HASH_ENTRY entry;
\r
424 entry = antlr3HashRemove(table, key);
\r
426 /* Now we can free the elements and the entry in order
\r
428 if (entry != NULL && entry->free != NULL)
\r
430 /* Call programmer supplied function to release this entry data
\r
432 entry->free(entry->data);
\r
433 entry->data = NULL;
\r
435 /* Finally release the space for this entry block.
\r
437 ANTLR3_FREE(entry);
\r
440 /** Return the element pointer in the hash table for a particular
\r
441 * key value, or NULL if it don't exist (or was itself NULL).
\r
444 antlr3HashGetI(pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key)
\r
446 ANTLR3_UINT32 hash;
\r
447 pANTLR3_HASH_BUCKET bucket;
\r
448 pANTLR3_HASH_ENTRY entry;
\r
450 /* First we need to know the hash of the provided key
\r
452 hash = (ANTLR3_UINT32)(key % (ANTLR3_INTKEY)(table->modulo));
\r
454 /* Knowing the hash, we can find the bucket
\r
456 bucket = table->buckets + hash;
\r
458 /* Now we can inspect the key at each entry in the bucket
\r
459 * and see if we have a match.
\r
461 entry = bucket->entries;
\r
463 while (entry != NULL)
\r
465 if (entry->keybase.key.iKey == key)
\r
467 /* Match was found, return the data pointer for this entry
\r
469 return entry->data;
\r
471 entry = entry->nextEntry;
\r
474 /* If we got here, then we did not find the key
\r
479 /** Return the element pointer in the hash table for a particular
\r
480 * key value, or NULL if it don't exist (or was itself NULL).
\r
483 antlr3HashGet(pANTLR3_HASH_TABLE table, void * key)
\r
485 ANTLR3_UINT32 hash;
\r
486 pANTLR3_HASH_BUCKET bucket;
\r
487 pANTLR3_HASH_ENTRY entry;
\r
490 /* First we need to know the hash of the provided key
\r
492 hash = antlr3Hash(key, (ANTLR3_UINT32)strlen((const char *)key));
\r
494 /* Knowing the hash, we can find the bucket
\r
496 bucket = table->buckets + (hash % table->modulo);
\r
498 /* Now we can inspect the key at each entry in the bucket
\r
499 * and see if we have a match.
\r
501 entry = bucket->entries;
\r
503 while (entry != NULL)
\r
505 if (strcmp((const char *)key, (const char *)entry->keybase.key.sKey) == 0)
\r
507 /* Match was found, return the data pointer for this entry
\r
509 return entry->data;
\r
511 entry = entry->nextEntry;
\r
514 /* If we got here, then we did not find the key
\r
519 /** Add the element pointer in to the table, based upon the
\r
520 * hash of the provided key.
\r
522 static ANTLR3_INT32
\r
523 antlr3HashPutI(pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *))
\r
525 ANTLR3_UINT32 hash;
\r
526 pANTLR3_HASH_BUCKET bucket;
\r
527 pANTLR3_HASH_ENTRY entry;
\r
528 pANTLR3_HASH_ENTRY * newPointer;
\r
530 /* First we need to know the hash of the provided key
\r
532 hash = (ANTLR3_UINT32)(key % (ANTLR3_INTKEY)(table->modulo));
\r
534 /* Knowing the hash, we can find the bucket
\r
536 bucket = table->buckets + hash;
\r
538 /* Knowing the bucket, we can traverse the entries until we
\r
539 * we find a NULL pointer or we find that this is already
\r
540 * in the table and duplicates were not allowed.
\r
542 newPointer = &bucket->entries;
\r
544 while (*newPointer != NULL)
\r
546 /* The value at new pointer is pointing to an existing entry.
\r
547 * If duplicates are allowed then we don't care what it is, but
\r
548 * must reject this add if the key is the same as the one we are
\r
551 if (table->allowDups == ANTLR3_FALSE)
\r
553 if ((*newPointer)->keybase.key.iKey == key)
\r
555 return ANTLR3_ERR_HASHDUP;
\r
559 /* Point to the next entry pointer of the current entry we
\r
560 * are traversing, if it is NULL we will create our new
\r
561 * structure and point this to it.
\r
563 newPointer = &((*newPointer)->nextEntry);
\r
566 /* newPointer is now pointing at the pointer where we need to
\r
567 * add our new entry, so let's crate the entry and add it in.
\r
569 entry = (pANTLR3_HASH_ENTRY)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_HASH_ENTRY));
\r
573 return ANTLR3_ERR_NOMEM;
\r
576 entry->data = element; /* Install the data element supplied */
\r
577 entry->free = freeptr; /* Function that knows how to release the entry */
\r
578 entry->keybase.type = ANTLR3_HASH_TYPE_INT; /* Indicate the key type stored here for when we free */
\r
579 entry->keybase.key.iKey = key; /* Record the key value */
\r
580 entry->nextEntry = NULL; /* Ensure that the forward pointer ends the chain */
\r
582 *newPointer = entry; /* Install the next entry in this bucket */
\r
586 return ANTLR3_SUCCESS;
\r
590 /** Add the element pointer in to the table, based upon the
\r
591 * hash of the provided key.
\r
593 static ANTLR3_INT32
\r
594 antlr3HashPut(pANTLR3_HASH_TABLE table, void * key, void * element, void (ANTLR3_CDECL *freeptr)(void *))
\r
596 ANTLR3_UINT32 hash;
\r
597 pANTLR3_HASH_BUCKET bucket;
\r
598 pANTLR3_HASH_ENTRY entry;
\r
599 pANTLR3_HASH_ENTRY * newPointer;
\r
601 /* First we need to know the hash of the provided key
\r
603 hash = antlr3Hash(key, (ANTLR3_UINT32)strlen((const char *)key));
\r
605 /* Knowing the hash, we can find the bucket
\r
607 bucket = table->buckets + (hash % table->modulo);
\r
609 /* Knowign the bucket, we can traverse the entries until we
\r
610 * we find a NULL pointer ofr we find that this is already
\r
611 * in the table and duplicates were not allowed.
\r
613 newPointer = &bucket->entries;
\r
615 while (*newPointer != NULL)
\r
617 /* The value at new pointer is pointing to an existing entry.
\r
618 * If duplicates are allowed then we don't care what it is, but
\r
619 * must reject this add if the key is the same as the one we are
\r
622 if (table->allowDups == ANTLR3_FALSE)
\r
624 if (strcmp((const char*) key, (const char *)(*newPointer)->keybase.key.sKey) == 0)
\r
626 return ANTLR3_ERR_HASHDUP;
\r
630 /* Point to the next entry pointer of the current entry we
\r
631 * are traversing, if it is NULL we will create our new
\r
632 * structure and point this to it.
\r
634 newPointer = &((*newPointer)->nextEntry);
\r
637 /* newPointer is now poiting at the pointer where we need to
\r
638 * add our new entry, so let's crate the entry and add it in.
\r
640 entry = (pANTLR3_HASH_ENTRY)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_HASH_ENTRY));
\r
644 return ANTLR3_ERR_NOMEM;
\r
647 entry->data = element; /* Install the data element supplied */
\r
648 entry->free = freeptr; /* Function that knows how to release the entry */
\r
649 entry->keybase.type = ANTLR3_HASH_TYPE_STR; /* Indicate the key type stored here for free() */
\r
650 if (table->doStrdup == ANTLR3_TRUE)
\r
652 entry->keybase.key.sKey = ANTLR3_STRDUP(key); /* Record the key value */
\r
656 entry->keybase.key.sKey = key; /* Record the key value */
\r
658 entry->nextEntry = NULL; /* Ensure that the forward pointer ends the chain */
\r
660 *newPointer = entry; /* Install the next entry in this bucket */
\r
664 return ANTLR3_SUCCESS;
\r
667 /** \brief Creates an enumeration structure to traverse the hash table.
\r
669 * \param table Table to enumerate
\r
670 * \return Pointer to enumeration structure.
\r
673 antlr3EnumNew (pANTLR3_HASH_TABLE table)
\r
675 pANTLR3_HASH_ENUM en;
\r
677 /* Allocate structure memory
\r
679 en = (pANTLR3_HASH_ENUM) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_HASH_ENUM));
\r
681 /* Check that the allocation was good
\r
685 return (pANTLR3_HASH_ENUM) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
\r
688 /* Initialize the start pointers
\r
691 en->bucket = 0; /* First bucket */
\r
692 en->entry = en->table->buckets->entries; /* First entry to return */
\r
694 /* Special case in that the first bucket may not have anything in it
\r
695 * but the antlr3EnumNext() function expects that the en->entry is
\r
696 * set to the next valid pointer. Hence if it is not a valid element
\r
697 * pointer, attempt to find the next one that is, (table may be empty
\r
700 if (en->entry == NULL)
\r
702 antlr3EnumNextEntry(en);
\r
705 /* Install the interface
\r
707 en->free = antlr3EnumFree;
\r
708 en->next = antlr3EnumNext;
\r
715 /** \brief Return the next entry in the hashtable being traversed by the supplied
\r
718 * \param[in] en Pointer to the enumeration tracking structure
\r
719 * \param key Pointer to void pointer, where the key pointer is returned.
\r
720 * \param data Pointer to void pointer where the data pointer is returned.
\r
722 * - ANTLR3_SUCCESS if there was a next key
\r
723 * - ANTLR3_FAIL if there were no more keys
\r
726 * No checking of input structure is performed!
\r
729 antlr3EnumNext (pANTLR3_HASH_ENUM en, pANTLR3_HASH_KEY * key, void ** data)
\r
731 /* If the current entry is valid, then use it
\r
733 if (en->bucket >= en->table->modulo)
\r
735 /* Already exhausted the table
\r
737 return ANTLR3_FAIL;
\r
740 /* Pointers are already set to the current entry to return, or
\r
741 * we would not be at this point in the logic flow.
\r
743 *key = &(en->entry->keybase);
\r
744 *data = en->entry->data;
\r
746 /* Return pointers are set up, so now we move the element
\r
747 * pointer to the next in the table (if any).
\r
749 antlr3EnumNextEntry(en);
\r
751 return ANTLR3_SUCCESS;
\r
754 /** \brief Local function to advance the entry pointer of an enumeration
\r
755 * structure to the next valid entry (if there is one).
\r
757 * \param[in] enum Pointer to ANTLR3 enumeration structure returned by antlr3EnumNew()
\r
760 * - The function always leaves the pointers pointing at a valid entry if there
\r
761 * is one, so if the entry pointer is NULL when this function exits, there were
\r
762 * no more entries in the table.
\r
765 antlr3EnumNextEntry(pANTLR3_HASH_ENUM en)
\r
767 pANTLR3_HASH_BUCKET bucket;
\r
769 /* See if the current entry pointer is valid first of all
\r
771 if (en->entry != NULL)
\r
773 /* Current entry was a valid point, see if there is another
\r
774 * one in the chain.
\r
776 if (en->entry->nextEntry != NULL)
\r
778 /* Next entry in the enumeration is just the next entry
\r
781 en->entry = en->entry->nextEntry;
\r
786 /* There were no more entries in the current bucket, if there are
\r
787 * more buckets then chase them until we find an entry.
\r
791 while (en->bucket < en->table->modulo)
\r
793 /* There was one more bucket, see if it has any elements in it
\r
795 bucket = en->table->buckets + en->bucket;
\r
797 if (bucket->entries != NULL)
\r
799 /* There was an entry in this bucket, so we can use it
\r
800 * for the next entry in the enumeration.
\r
802 en->entry = bucket->entries;
\r
806 /* There was nothing in the bucket we just examined, move to the
\r
812 /* Here we have exhausted all buckets and the enumeration pointer will
\r
813 * have its bucket count = table->modulo which signifies that we are done.
\r
817 /** \brief Frees up the memory structures that represent a hash table
\r
819 * \param[in] enum Pointer to ANTLR3 enumeration structure returned by antlr3EnumNew()
\r
822 antlr3EnumFree (pANTLR3_HASH_ENUM en)
\r
824 /* Nothing to check, we just free it.
\r
829 /** Given an input key of arbitrary length, return a hash value of
\r
830 * it. This can then be used (with suitable modulo) to index other
\r
833 ANTLR3_API ANTLR3_UINT32
\r
834 antlr3Hash(void * key, ANTLR3_UINT32 keylen)
\r
836 /* Accumulate the hash value of the key
\r
838 ANTLR3_UINT32 hash;
\r
839 pANTLR3_UINT8 keyPtr;
\r
843 keyPtr = (pANTLR3_UINT8) key;
\r
845 /* Iterate the key and accumulate the hash
\r
849 hash = (hash << 4) + (*(keyPtr++));
\r
851 if ((i1=hash&0xf0000000) != 0)
\r
853 hash = hash ^ (i1 >> 24);
\r
862 ANTLR3_API pANTLR3_LIST
\r
863 antlr3ListNew (ANTLR3_UINT32 sizeHint)
\r
869 list = (pANTLR3_LIST)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_LIST));
\r
873 return (pANTLR3_LIST)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
\r
876 /* Now we need to add a new table
\r
878 list->table = antlr3HashTableNew(sizeHint);
\r
880 if (list->table == (pANTLR3_HASH_TABLE)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM))
\r
882 return (pANTLR3_LIST)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
\r
885 /* Allocation was good, install interface
\r
887 list->free = antlr3ListFree;
\r
888 list->del = antlr3ListDelete;
\r
889 list->get = antlr3ListGet;
\r
890 list->add = antlr3ListAdd;
\r
891 list->remove = antlr3ListRemove;
\r
892 list->put = antlr3ListPut;
\r
893 list->size = antlr3ListSize;
\r
898 static ANTLR3_UINT32 antlr3ListSize (pANTLR3_LIST list)
\r
900 return list->table->size(list->table);
\r
904 antlr3ListFree (pANTLR3_LIST list)
\r
906 /* Free the hashtable that stores the list
\r
908 list->table->free(list->table);
\r
910 /* Free the allocation for the list itself
\r
916 antlr3ListDelete (pANTLR3_LIST list, ANTLR3_INTKEY key)
\r
918 list->table->delI(list->table, key);
\r
922 antlr3ListGet (pANTLR3_LIST list, ANTLR3_INTKEY key)
\r
924 return list->table->getI(list->table, key);
\r
927 /** Add the supplied element to the list, at the next available key
\r
929 static ANTLR3_INT32 antlr3ListAdd (pANTLR3_LIST list, void * element, void (ANTLR3_CDECL *freeptr)(void *))
\r
933 key = list->table->size(list->table) + 1;
\r
934 return list->put(list, key, element, freeptr);
\r
937 /** Remove from the list, but don't free the element, just send it back to the
\r
941 antlr3ListRemove (pANTLR3_LIST list, ANTLR3_INTKEY key)
\r
943 pANTLR3_HASH_ENTRY entry;
\r
945 entry = list->table->removeI(list->table, key);
\r
949 return entry->data;
\r
957 static ANTLR3_INT32
\r
958 antlr3ListPut (pANTLR3_LIST list, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *))
\r
960 return list->table->putI(list->table, key, element, freeptr);
\r
963 ANTLR3_API pANTLR3_STACK
\r
964 antlr3StackNew (ANTLR3_UINT32 sizeHint)
\r
966 pANTLR3_STACK stack;
\r
970 stack = (pANTLR3_STACK)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_STACK));
\r
974 return (pANTLR3_STACK)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
\r
977 /* Now we need to add a new table
\r
979 stack->vector = antlr3VectorNew(sizeHint);
\r
982 if (stack->vector == (pANTLR3_VECTOR)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM))
\r
984 return (pANTLR3_STACK)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
\r
987 /* Looks good, now add the interface
\r
989 stack->get = antlr3StackGet;
\r
990 stack->free = antlr3StackFree;
\r
991 stack->pop = antlr3StackPop;
\r
992 stack->push = antlr3StackPush;
\r
993 stack->size = antlr3StackSize;
\r
994 stack->peek = antlr3StackPeek;
\r
999 static ANTLR3_UINT32 antlr3StackSize (pANTLR3_STACK stack)
\r
1001 return stack->vector->count;
\r
1006 antlr3StackFree (pANTLR3_STACK stack)
\r
1008 /* Free the list that supports the stack
\r
1010 stack->vector->free(stack->vector);
\r
1011 stack->vector = NULL;
\r
1012 stack->top = NULL;
\r
1014 ANTLR3_FREE(stack);
\r
1018 antlr3StackPop (pANTLR3_STACK stack)
\r
1020 // Delete the element that is currently at the top of the stack
\r
1022 stack->vector->del(stack->vector, stack->vector->count - 1);
\r
1024 // And get the element that is the now the top of the stack (if anything)
\r
1025 // NOTE! This is not quite like a 'real' stack, which would normally return you
\r
1026 // the current top of the stack, then remove it from the stack.
\r
1027 // TODO: Review this, it is correct for follow sets which is what this was done for
\r
1028 // but is not as obvious when using it as a 'real'stack.
\r
1030 stack->top = stack->vector->get(stack->vector, stack->vector->count - 1);
\r
1031 return stack->top;
\r
1035 antlr3StackGet (pANTLR3_STACK stack, ANTLR3_INTKEY key)
\r
1037 return stack->vector->get(stack->vector, (ANTLR3_UINT32)key);
\r
1041 antlr3StackPeek (pANTLR3_STACK stack)
\r
1043 return stack->top;
\r
1046 static ANTLR3_BOOLEAN
\r
1047 antlr3StackPush (pANTLR3_STACK stack, void * element, void (ANTLR3_CDECL *freeptr)(void *))
\r
1049 stack->top = element;
\r
1050 return (ANTLR3_BOOLEAN)(stack->vector->add(stack->vector, element, freeptr));
\r
1053 ANTLR3_API pANTLR3_VECTOR
\r
1054 antlr3VectorNew (ANTLR3_UINT32 sizeHint)
\r
1056 pANTLR3_VECTOR vector;
\r
1059 // Allocate memory for the vector structure itself
\r
1061 vector = (pANTLR3_VECTOR) ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR)));
\r
1063 if (vector == NULL)
\r
1065 return (pANTLR3_VECTOR)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
\r
1068 // Now fill in the defaults
\r
1070 antlr3SetVectorApi(vector, sizeHint);
\r
1072 // And everything is hunky dory
\r
1078 antlr3SetVectorApi (pANTLR3_VECTOR vector, ANTLR3_UINT32 sizeHint)
\r
1080 ANTLR3_UINT32 initialSize;
\r
1082 // Allow vectors to be guessed by ourselves, so input size can be zero
\r
1084 if (sizeHint > ANTLR3_VECTOR_INTERNAL_SIZE)
\r
1086 initialSize = sizeHint;
\r
1090 initialSize = ANTLR3_VECTOR_INTERNAL_SIZE;
\r
1093 if (sizeHint > ANTLR3_VECTOR_INTERNAL_SIZE)
\r
1095 vector->elements = (pANTLR3_VECTOR_ELEMENT)ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR_ELEMENT) * initialSize));
\r
1099 vector->elements = vector->internal;
\r
1102 if (vector->elements == NULL)
\r
1104 ANTLR3_FREE(vector);
\r
1108 // Memory allocated successfully
\r
1110 vector->count = 0; // No entries yet of course
\r
1111 vector->elementsSize = initialSize; // Available entries
\r
1113 // Now we can install the API
\r
1115 vector->add = antlr3VectorAdd;
\r
1116 vector->del = antlr3VectorDel;
\r
1117 vector->get = antlr3VectorGet;
\r
1118 vector->free = antlr3VectorFree;
\r
1119 vector->set = antlr3VectorSet;
\r
1120 vector->remove = antrl3VectorRemove;
\r
1121 vector->clear = antlr3VectorClear;
\r
1122 vector->size = antlr3VectorSize;
\r
1123 vector->swap = antlr3VectorSwap;
\r
1125 // Assume that this is not a factory made vector
\r
1127 vector->factoryMade = ANTLR3_FALSE;
\r
1129 // Clear the entries in a vector.
\r
1130 // Clearing the vector leaves its capacity the same but
\r
1131 // it walks the entries first to see if any of them
\r
1132 // have a free routine that must be called.
\r
1135 antlr3VectorClear (pANTLR3_VECTOR vector)
\r
1137 ANTLR3_UINT32 entry;
\r
1139 // We must traverse every entry in the vector and if it has
\r
1140 // a pointer to a free function then we call it with the
\r
1141 // the entry pointer
\r
1143 for (entry = 0; entry < vector->count; entry++)
\r
1145 if (vector->elements[entry].freeptr != NULL)
\r
1147 vector->elements[entry].freeptr(vector->elements[entry].element);
\r
1149 vector->elements[entry].freeptr = NULL;
\r
1150 vector->elements[entry].element = NULL;
\r
1153 // Having called any free pointers, we just reset the entry count
\r
1156 vector->count = 0;
\r
1160 void ANTLR3_CDECL antlr3VectorFree (pANTLR3_VECTOR vector)
\r
1162 ANTLR3_UINT32 entry;
\r
1164 // We must traverse every entry in the vector and if it has
\r
1165 // a pointer to a free function then we call it with the
\r
1166 // the entry pointer
\r
1168 for (entry = 0; entry < vector->count; entry++)
\r
1170 if (vector->elements[entry].freeptr != NULL)
\r
1172 vector->elements[entry].freeptr(vector->elements[entry].element);
\r
1174 vector->elements[entry].freeptr = NULL;
\r
1175 vector->elements[entry].element = NULL;
\r
1178 if (vector->factoryMade == ANTLR3_FALSE)
\r
1180 // The entries are freed, so free the element allocation
\r
1182 if (vector->elementsSize > ANTLR3_VECTOR_INTERNAL_SIZE)
\r
1184 ANTLR3_FREE(vector->elements);
\r
1186 vector->elements = NULL;
\r
1188 // Finally, free the allocation for the vector itself
\r
1190 ANTLR3_FREE(vector);
\r
1194 static void antlr3VectorDel (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry)
\r
1196 // Check this is a valid request first
\r
1198 if (entry >= vector->count)
\r
1203 // Valid request, check for free pointer and call it if present
\r
1205 if (vector->elements[entry].freeptr != NULL)
\r
1207 vector->elements[entry].freeptr(vector->elements[entry].element);
\r
1208 vector->elements[entry].freeptr = NULL;
\r
1211 if (entry == vector->count - 1)
\r
1213 // Ensure the pointer is never reused by accident, but otherwise just
\r
1214 // decrement the pointer.
\r
1216 vector->elements[entry].element = NULL;
\r
1220 // Need to shuffle trailing pointers back over the deleted entry
\r
1222 ANTLR3_MEMMOVE(vector->elements + entry, vector->elements + entry + 1, sizeof(ANTLR3_VECTOR_ELEMENT) * (vector->count - entry - 1));
\r
1225 // One less entry in the vector now
\r
1230 static void * antlr3VectorGet (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry)
\r
1232 // Ensure this is a valid request
\r
1234 if (entry < vector->count)
\r
1236 return vector->elements[entry].element;
\r
1240 // I know nothing, Mr. Fawlty!
\r
1246 /// Remove the entry from the vector, but do not free any entry, even if it has
\r
1247 /// a free pointer.
\r
1249 static void * antrl3VectorRemove (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry)
\r
1253 // Check this is a valid request first
\r
1255 if (entry >= vector->count)
\r
1260 // Valid request, return the sorted pointer
\r
1263 element = vector->elements[entry].element;
\r
1265 if (entry == vector->count - 1)
\r
1267 // Ensure the pointer is never reused by accident, but otherwise just
\r
1268 // decrement the pointer.
\r
1270 vector->elements[entry].element = NULL;
\r
1271 vector->elements[entry].freeptr = NULL;
\r
1275 // Need to shuffle trailing pointers back over the deleted entry
\r
1277 ANTLR3_MEMMOVE(vector->elements + entry, vector->elements + entry + 1, sizeof(ANTLR3_VECTOR_ELEMENT) * (vector->count - entry - 1));
\r
1280 // One less entry in the vector now
\r
1288 antlr3VectorResize (pANTLR3_VECTOR vector, ANTLR3_UINT32 hint)
\r
1290 ANTLR3_UINT32 newSize;
\r
1292 // Need to resize the element pointers. We double the allocation
\r
1293 // we already have unless asked for a specific increase.
\r
1295 if (hint == 0 || hint < vector->elementsSize)
\r
1297 newSize = vector->elementsSize * 2;
\r
1301 newSize = hint * 2;
\r
1304 // Now we know how many we need, so we see if we have just expanded
\r
1305 // past the built in vector elements or were already past that
\r
1307 if (vector->elementsSize > ANTLR3_VECTOR_INTERNAL_SIZE)
\r
1309 // We were already larger than the internal size, so we just
\r
1310 // use realloc so that the pointers are copied for us
\r
1312 vector->elements = (pANTLR3_VECTOR_ELEMENT)ANTLR3_REALLOC(vector->elements, (sizeof(ANTLR3_VECTOR_ELEMENT)* newSize));
\r
1316 // The current size was less than or equal to the internal array size and as we always start
\r
1317 // with a size that is at least the maximum internal size, then we must need to allocate new memory
\r
1318 // for external pointers. We don't want to take the time to calculate if a requested element
\r
1319 // is part of the internal or external entries, so we copy the internal ones to the new space
\r
1321 vector->elements = (pANTLR3_VECTOR_ELEMENT)ANTLR3_MALLOC((sizeof(ANTLR3_VECTOR_ELEMENT)* newSize));
\r
1322 ANTLR3_MEMCPY(vector->elements, vector->internal, ANTLR3_VECTOR_INTERNAL_SIZE * sizeof(ANTLR3_VECTOR_ELEMENT));
\r
1325 vector->elementsSize = newSize;
\r
1328 /// Add the supplied pointer and freeing function pointer to the list,
\r
1329 /// expanding the vector if needed.
\r
1331 static ANTLR3_UINT32 antlr3VectorAdd (pANTLR3_VECTOR vector, void * element, void (ANTLR3_CDECL *freeptr)(void *))
\r
1333 // Do we need to resize the vector table?
\r
1335 if (vector->count == vector->elementsSize)
\r
1337 antlr3VectorResize(vector, 0); // Give no hint, we let it add 1024 or double it
\r
1340 // Insert the new entry
\r
1342 vector->elements[vector->count].element = element;
\r
1343 vector->elements[vector->count].freeptr = freeptr;
\r
1345 vector->count++; // One more element counted
\r
1347 return (ANTLR3_UINT32)(vector->count);
\r
1351 /// Replace the element at the specified entry point with the supplied
\r
1354 static ANTLR3_UINT32
\r
1355 antlr3VectorSet (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry, void * element, void (ANTLR3_CDECL *freeptr)(void *), ANTLR3_BOOLEAN freeExisting)
\r
1358 // If the vector is currently not big enough, then we expand it
\r
1360 if (entry >= vector->elementsSize)
\r
1362 antlr3VectorResize(vector, entry); // We will get at least this many
\r
1365 // Valid request, replace the current one, freeing any prior entry if told to
\r
1367 if ( entry < vector->count // If actually replacing an element
\r
1368 && freeExisting // And told to free any existing element
\r
1369 && vector->elements[entry].freeptr != NULL // And the existing element has a free pointer
\r
1372 vector->elements[entry].freeptr(vector->elements[entry].element);
\r
1375 // Install the new pointers
\r
1377 vector->elements[entry].freeptr = freeptr;
\r
1378 vector->elements[entry].element = element;
\r
1380 if (entry >= vector->count)
\r
1382 vector->count = entry + 1;
\r
1384 return (ANTLR3_UINT32)(entry); // Indicates the replacement was successful
\r
1388 /// Replace the element at the specified entry point with the supplied
\r
1391 static ANTLR3_BOOLEAN
\r
1392 antlr3VectorSwap (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry1, ANTLR3_UINT32 entry2)
\r
1396 void (ANTLR3_CDECL *freeptr)(void *);
\r
1398 // If the vector is currently not big enough, then we do nothing
\r
1400 if (entry1 >= vector->elementsSize || entry2 >= vector->elementsSize)
\r
1402 return ANTLR3_FALSE;
\r
1405 // Valid request, swap them
\r
1407 tempEntry = vector->elements[entry1].element;
\r
1408 freeptr = vector->elements[entry1].freeptr;
\r
1410 // Install the new pointers
\r
1412 vector->elements[entry1].freeptr = vector->elements[entry2].freeptr;
\r
1413 vector->elements[entry1].element = vector->elements[entry2].element;
\r
1415 vector->elements[entry2].freeptr = freeptr;
\r
1416 vector->elements[entry2].element = tempEntry;
\r
1418 return ANTLR3_TRUE;
\r
1422 static ANTLR3_UINT32 antlr3VectorSize (pANTLR3_VECTOR vector)
\r
1424 return vector->count;
\r
1427 #ifdef ANTLR3_WINDOWS
\r
1428 #pragma warning (push)
\r
1429 #pragma warning (disable : 4100)
\r
1431 /// Vector factory creation
\r
1433 ANTLR3_API pANTLR3_VECTOR_FACTORY
\r
1434 antlr3VectorFactoryNew (ANTLR3_UINT32 sizeHint)
\r
1436 pANTLR3_VECTOR_FACTORY factory;
\r
1438 // Allocate memory for the factory
\r
1440 factory = (pANTLR3_VECTOR_FACTORY)ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR_FACTORY)));
\r
1442 if (factory == NULL)
\r
1447 // Factory memory is good, so create a new vector pool
\r
1449 factory->pools = NULL;
\r
1450 factory->thisPool = -1;
\r
1454 // Initialize the API, ignore the hint as this algorithm does
\r
1455 // a better job really.
\r
1457 antlr3SetVectorApi(&(factory->unTruc), ANTLR3_VECTOR_INTERNAL_SIZE);
\r
1459 factory->unTruc.factoryMade = ANTLR3_TRUE;
\r
1461 // Install the factory API
\r
1463 factory->close = closeVectorFactory;
\r
1464 factory->newVector = newVector;
\r
1465 factory->returnVector = returnVector;
\r
1467 // Create a stack to accumulate reusable vectors
\r
1469 factory->freeStack = antlr3StackNew(16);
\r
1472 #ifdef ANTLR3_WINDOWS
\r
1473 #pragma warning (pop)
\r
1477 returnVector (pANTLR3_VECTOR_FACTORY factory, pANTLR3_VECTOR vector)
\r
1479 // First we need to clear out anything that is still in the vector
\r
1481 vector->clear(vector);
\r
1483 // We have a free stack available so we can add the vector we were
\r
1484 // given into the free chain. The vector has to have come from this
\r
1485 // factory, so we already know how to release its memory when it
\r
1486 // dies by virtue of the factory being closed.
\r
1488 factory->freeStack->push(factory->freeStack, vector, NULL);
\r
1490 // TODO: remove this line once happy printf("Returned vector %08X to the pool, stack size is %d\n", vector, factory->freeStack->size(factory->freeStack));
\r
1494 newPool(pANTLR3_VECTOR_FACTORY factory)
\r
1496 /* Increment factory count
\r
1498 factory->thisPool++;
\r
1500 /* Ensure we have enough pointers allocated
\r
1502 factory->pools = (pANTLR3_VECTOR *)
\r
1503 ANTLR3_REALLOC( (void *)factory->pools, /* Current pools pointer (starts at NULL) */
\r
1504 (ANTLR3_UINT32)((factory->thisPool + 1) * sizeof(pANTLR3_VECTOR *)) /* Memory for new pool pointers */
\r
1507 /* Allocate a new pool for the factory
\r
1509 factory->pools[factory->thisPool] =
\r
1511 ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR) * ANTLR3_FACTORY_VPOOL_SIZE));
\r
1514 /* Reset the counters
\r
1516 factory->nextVector = 0;
\r
1524 closeVectorFactory (pANTLR3_VECTOR_FACTORY factory)
\r
1526 pANTLR3_VECTOR pool;
\r
1527 ANTLR3_INT32 poolCount;
\r
1528 ANTLR3_UINT32 limit;
\r
1529 ANTLR3_UINT32 vector;
\r
1530 pANTLR3_VECTOR check;
\r
1532 // First see if we have a free chain stack to release?
\r
1534 if (factory->freeStack != NULL)
\r
1536 factory->freeStack->free(factory->freeStack);
\r
1539 /* We iterate the vector pools one at a time
\r
1541 for (poolCount = 0; poolCount <= factory->thisPool; poolCount++)
\r
1543 /* Pointer to current pool
\r
1545 pool = factory->pools[poolCount];
\r
1547 /* Work out how many tokens we need to check in this pool.
\r
1549 limit = (poolCount == factory->thisPool ? factory->nextVector : ANTLR3_FACTORY_VPOOL_SIZE);
\r
1551 /* Marginal condition, we might be at the start of a brand new pool
\r
1552 * where the nextToken is 0 and nothing has been allocated.
\r
1556 /* We have some vectors allocated from this pool
\r
1558 for (vector = 0; vector < limit; vector++)
\r
1560 /* Next one in the chain
\r
1562 check = pool + vector;
\r
1564 // Call the free function on each of the vectors in the pool,
\r
1565 // which in turn will cause any elements it holds that also have a free
\r
1566 // pointer to be freed. However, because any vector may be in any other
\r
1567 // vector, we don't free the element allocations yet. We do that in a
\r
1568 // a specific pass, coming up next. The vector free function knows that
\r
1569 // this is a factory allocated pool vector and so it won't free things it
\r
1572 check->free(check);
\r
1577 /* We iterate the vector pools one at a time once again, but this time
\r
1578 * we are going to free up any allocated element pointers. Note that we are doing this
\r
1579 * so that we do not try to release vectors twice. When building ASTs we just copy
\r
1580 * the vectors all over the place and they may be embedded in this vector pool
\r
1583 for (poolCount = 0; poolCount <= factory->thisPool; poolCount++)
\r
1585 /* Pointer to current pool
\r
1587 pool = factory->pools[poolCount];
\r
1589 /* Work out how many tokens we need to check in this pool.
\r
1591 limit = (poolCount == factory->thisPool ? factory->nextVector : ANTLR3_FACTORY_VPOOL_SIZE);
\r
1593 /* Marginal condition, we might be at the start of a brand new pool
\r
1594 * where the nextToken is 0 and nothing has been allocated.
\r
1598 /* We have some vectors allocated from this pool
\r
1600 for (vector = 0; vector < limit; vector++)
\r
1602 /* Next one in the chain
\r
1604 check = pool + vector;
\r
1606 // Anything in here should be factory made, but we do this just
\r
1607 // to triple check. We just free up the elements if they were
\r
1608 // allocated beyond the internal size.
\r
1610 if (check->factoryMade == ANTLR3_TRUE && check->elementsSize > ANTLR3_VECTOR_INTERNAL_SIZE)
\r
1612 ANTLR3_FREE(check->elements);
\r
1613 check->elements = NULL;
\r
1618 // We can now free this pool allocation as we have called free on every element in every vector
\r
1619 // and freed any memory for pointers the grew beyond the internal size limit.
\r
1621 ANTLR3_FREE(factory->pools[poolCount]);
\r
1622 factory->pools[poolCount] = NULL;
\r
1625 /* All the pools are deallocated we can free the pointers to the pools
\r
1628 ANTLR3_FREE(factory->pools);
\r
1630 /* Finally, we can free the space for the factory itself
\r
1632 ANTLR3_FREE(factory);
\r
1636 static pANTLR3_VECTOR
\r
1637 newVector(pANTLR3_VECTOR_FACTORY factory)
\r
1639 pANTLR3_VECTOR vector;
\r
1641 // If we have anything on the re claim stack, reuse it
\r
1643 vector = factory->freeStack->peek(factory->freeStack);
\r
1645 if (vector != NULL)
\r
1647 // Cool we got something we could reuse
\r
1649 factory->freeStack->pop(factory->freeStack);
\r
1651 // TODO: remove this line once happy printf("Reused vector %08X from stack, size is now %d\n", vector, factory->freeStack->size(factory->freeStack));
\r
1656 // See if we need a new vector pool before allocating a new
\r
1659 if (factory->nextVector >= ANTLR3_FACTORY_VPOOL_SIZE)
\r
1661 // We ran out of vectors in the current pool, so we need a new pool
\r
1666 // Assuming everything went well (we are trying for performance here so doing minimal
\r
1667 // error checking. Then we can work out what the pointer is to the next vector.
\r
1669 vector = factory->pools[factory->thisPool] + factory->nextVector;
\r
1670 factory->nextVector++;
\r
1672 // We have our token pointer now, so we can initialize it to the predefined model.
\r
1674 antlr3SetVectorApi(vector, ANTLR3_VECTOR_INTERNAL_SIZE);
\r
1675 vector->factoryMade = ANTLR3_TRUE;
\r
1677 // We know that the pool vectors are created at the default size, which means they
\r
1678 // will start off using their internal entry pointers. We must intialize our pool vector
\r
1679 // to point to its own internal entry table and not the pre-made one.
\r
1681 vector->elements = vector->internal;
\r
1683 // TODO: remove this line once happy printf("Used a new vector at %08X from the pools as nothing on the reusue stack\n", vector);
\r
1685 // And we are done
\r
1690 /** Array of left most significant bit positions for an 8 bit
\r
1691 * element provides an efficient way to find the highest bit
\r
1692 * that is set in an n byte value (n>0). Assuming the values will all hit the data cache,
\r
1693 * coding without conditional elements should allow branch
\r
1694 * prediction to work well and of course a parallel instruction cache
\r
1695 * will whip through this. Otherwise we must loop shifting a one
\r
1696 * bit and masking. The values we tend to be placing in out integer
\r
1697 * patricia trie are usually a lot lower than the 64 bits we
\r
1698 * allow for the key allows. Hence there is a lot of redundant looping and
\r
1699 * shifting in a while loop. Whereas, the lookup table is just
\r
1700 * a few ands and indirect lookups, while testing for 0. This
\r
1701 * is likely to be done in parallel on many processors available
\r
1702 * when I wrote this. If this code survives as long as yacc, then
\r
1703 * I may already be dead by the time you read this and maybe there is
\r
1704 * a single machine instruction to perform the operation. What
\r
1705 * else are you going to do with all those transistors? Jim 2007
\r
1707 * The table is probably obvious but it is just the number 0..7
\r
1708 * of the MSB in each integer value 0..256
\r
1710 static ANTLR3_UINT8 bitIndex[256] =
\r
1712 0, // 0 - Just for padding
\r
1715 2, 2, 2, 2, // 4..7
\r
1716 3, 3, 3, 3, 3, 3, 3, 3, // 8+
\r
1717 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, // 16+
\r
1718 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, // 32+
\r
1719 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
\r
1720 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, // 64+
\r
1721 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
\r
1722 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
\r
1723 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
\r
1724 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 128+
\r
1725 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
\r
1726 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
\r
1727 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
\r
1728 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
\r
1729 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
\r
1730 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
\r
1731 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
\r
1734 /** Rather than use the bit index of a trie node to shift
\r
1735 * 0x01 left that many times, then & with the result, it is
\r
1736 * faster to use the bit index as an index into this table
\r
1737 * which holds precomputed masks for any of the 64 bits
\r
1738 * we need to mask off singly. The data values will stay in
\r
1739 * cache while ever a trie is in heavy use, such as in
\r
1740 * memoization. It is also pretty enough to be ASCII art.
\r
1742 static ANTLR3_UINT64 bitMask[64] =
\r
1744 0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000004ULL, 0x0000000000000008ULL,
\r
1745 0x0000000000000010ULL, 0x0000000000000020ULL, 0x0000000000000040ULL, 0x0000000000000080ULL,
\r
1746 0x0000000000000100ULL, 0x0000000000000200ULL, 0x0000000000000400ULL, 0x0000000000000800ULL,
\r
1747 0x0000000000001000ULL, 0x0000000000002000ULL, 0x0000000000004000ULL, 0x0000000000008000ULL,
\r
1748 0x0000000000010000ULL, 0x0000000000020000ULL, 0x0000000000040000ULL, 0x0000000000080000ULL,
\r
1749 0x0000000000100000ULL, 0x0000000000200000ULL, 0x0000000000400000ULL, 0x0000000000800000ULL,
\r
1750 0x0000000001000000ULL, 0x0000000002000000ULL, 0x0000000004000000ULL, 0x0000000008000000ULL,
\r
1751 0x0000000010000000ULL, 0x0000000020000000ULL, 0x0000000040000000ULL, 0x0000000080000000ULL,
\r
1752 0x0000000100000000ULL, 0x0000000200000000ULL, 0x0000000400000000ULL, 0x0000000800000000ULL,
\r
1753 0x0000001000000000ULL, 0x0000002000000000ULL, 0x0000004000000000ULL, 0x0000008000000000ULL,
\r
1754 0x0000010000000000ULL, 0x0000020000000000ULL, 0x0000040000000000ULL, 0x0000080000000000ULL,
\r
1755 0x0000100000000000ULL, 0x0000200000000000ULL, 0x0000400000000000ULL, 0x0000800000000000ULL,
\r
1756 0x0001000000000000ULL, 0x0002000000000000ULL, 0x0004000000000000ULL, 0x0008000000000000ULL,
\r
1757 0x0010000000000000ULL, 0x0020000000000000ULL, 0x0040000000000000ULL, 0x0080000000000000ULL,
\r
1758 0x0100000000000000ULL, 0x0200000000000000ULL, 0x0400000000000000ULL, 0x0800000000000000ULL,
\r
1759 0x1000000000000000ULL, 0x2000000000000000ULL, 0x4000000000000000ULL, 0x8000000000000000ULL
\r
1762 /* INT TRIE Implementation of depth 64 bits, being the number of bits
\r
1763 * in a 64 bit integer.
\r
1767 antlr3IntTrieNew(ANTLR3_UINT32 depth)
\r
1769 pANTLR3_INT_TRIE trie;
\r
1771 trie = (pANTLR3_INT_TRIE) ANTLR3_CALLOC(1, sizeof(ANTLR3_INT_TRIE)); /* Base memory required */
\r
1775 return (pANTLR3_INT_TRIE) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
\r
1778 /* Now we need to allocate the root node. This makes it easier
\r
1779 * to use the tree as we don't have to do anything special
\r
1780 * for the root node.
\r
1782 trie->root = (pANTLR3_INT_TRIE_NODE) ANTLR3_CALLOC(1, sizeof(ANTLR3_INT_TRIE));
\r
1784 if (trie->root == NULL)
\r
1786 ANTLR3_FREE(trie);
\r
1787 return (pANTLR3_INT_TRIE) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
\r
1790 trie->add = intTrieAdd;
\r
1791 trie->del = intTrieDel;
\r
1792 trie->free = intTrieFree;
\r
1793 trie->get = intTrieGet;
\r
1795 /* Now we seed the root node with the index being the
\r
1796 * highest left most bit we want to test, which limits the
\r
1797 * keys in the trie. This is the trie 'depth'. The limit for
\r
1798 * this implementation is 63 (bits 0..63).
\r
1800 trie->root->bitNum = depth;
\r
1802 /* And as we have nothing in here yet, we set both child pointers
\r
1803 * of the root node to point back to itself.
\r
1805 trie->root->leftN = trie->root;
\r
1806 trie->root->rightN = trie->root;
\r
1809 /* Finally, note that the key for this root node is 0 because
\r
1810 * we use calloc() to initialise it.
\r
1816 /** Search the int Trie and return a pointer to the first bucket indexed
\r
1817 * by the key if it is contained in the trie, otherwise NULL.
\r
1819 static pANTLR3_TRIE_ENTRY
\r
1820 intTrieGet (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key)
\r
1822 pANTLR3_INT_TRIE_NODE thisNode;
\r
1823 pANTLR3_INT_TRIE_NODE nextNode;
\r
1825 if (trie->count == 0)
\r
1827 return NULL; /* Nothing in this trie yet */
\r
1829 /* Starting at the root node in the trie, compare the bit index
\r
1830 * of the current node with its next child node (starts left from root).
\r
1831 * When the bit index of the child node is greater than the bit index of the current node
\r
1832 * then by definition (as the bit index decreases as we descent the trie)
\r
1833 * we have reached a 'backward' pointer. A backward pointer means we
\r
1834 * have reached the only node that can be reached by the bits given us so far
\r
1835 * and it must either be the key we are looking for, or if not then it
\r
1836 * means the entry was not in the trie, and we return NULL. A backward pointer
\r
1837 * points back in to the tree structure rather than down (deeper) within the
\r
1840 thisNode = trie->root; /* Start at the root node */
\r
1841 nextNode = thisNode->leftN; /* Examine the left node from the root */
\r
1843 /* While we are descending the tree nodes...
\r
1845 while (thisNode->bitNum > nextNode->bitNum)
\r
1847 /* Next node now becomes the new 'current' node
\r
1849 thisNode = nextNode;
\r
1851 /* We now test the bit indicated by the bitmap in the next node
\r
1852 * in the key we are searching for. The new next node is the
\r
1853 * right node if that bit is set and the left node it is not.
\r
1855 if (key & bitMask[nextNode->bitNum])
\r
1857 nextNode = nextNode->rightN; /* 1 is right */
\r
1861 nextNode = nextNode->leftN; /* 0 is left */
\r
1865 /* Here we have reached a node where the bitMap index is lower than
\r
1866 * its parent. This means it is pointing backward in the tree and
\r
1867 * must therefore be a terminal node, being the only point than can
\r
1868 * be reached with the bits seen so far. It is either the actual key
\r
1869 * we wanted, or if that key is not in the trie it is another key
\r
1870 * that is currently the only one that can be reached by those bits.
\r
1871 * That situation would obviously change if the key was to be added
\r
1874 * Hence it only remains to test whether this is actually the key or not.
\r
1876 if (nextNode->key == key)
\r
1878 /* This was the key, so return the entry pointer
\r
1880 return nextNode->buckets;
\r
1884 return NULL; /* That key is not in the trie (note that we set the pointer to -1 if no payload) */
\r
1889 static ANTLR3_BOOLEAN
\r
1890 intTrieDel (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key)
\r
1892 pANTLR3_INT_TRIE_NODE p;
\r
1897 return ANTLR3_FALSE;
\r
1900 /** Add an entry into the INT trie.
\r
1901 * Basically we descend the trie as we do when searching it, which will
\r
1902 * locate the only node in the trie that can be reached by the bit pattern of the
\r
1903 * key. If the key is actually at that node, then if the trie accepts duplicates
\r
1904 * we add the supplied data in a new chained bucket to that data node. If it does
\r
1905 * not accept duplicates then we merely return FALSE in case the caller wants to know
\r
1906 * whether the key was already in the trie.
\r
1907 * If the node we locate is not the key we are looking to add, then we insert a new node
\r
1908 * into the trie with a bit index of the leftmost differing bit and the left or right
\r
1909 * node pointing to itself or the data node we are inserting 'before'.
\r
1911 static ANTLR3_BOOLEAN
\r
1912 intTrieAdd (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key, ANTLR3_UINT32 type, ANTLR3_INTKEY intVal, void * data, void (ANTLR3_CDECL *freeptr)(void *))
\r
1914 pANTLR3_INT_TRIE_NODE thisNode;
\r
1915 pANTLR3_INT_TRIE_NODE nextNode;
\r
1916 pANTLR3_INT_TRIE_NODE entNode;
\r
1917 ANTLR3_UINT32 depth;
\r
1918 pANTLR3_TRIE_ENTRY newEnt;
\r
1919 pANTLR3_TRIE_ENTRY nextEnt;
\r
1920 ANTLR3_INTKEY xorKey;
\r
1922 /* Cache the bit depth of this trie, which is always the highest index,
\r
1923 * which is in the root node
\r
1925 depth = trie->root->bitNum;
\r
1927 thisNode = trie->root; /* Start with the root node */
\r
1928 nextNode = trie->root->leftN; /* And assume we start to the left */
\r
1930 /* Now find the only node that can be currently reached by the bits in the
\r
1931 * key we are being asked to insert.
\r
1933 while (thisNode->bitNum > nextNode->bitNum)
\r
1935 /* Still descending the structure, next node becomes current.
\r
1937 thisNode = nextNode;
\r
1939 if (key & bitMask[nextNode->bitNum])
\r
1941 /* Bit at the required index was 1, so travers the right node from here
\r
1943 nextNode = nextNode->rightN;
\r
1947 /* Bit at the required index was 0, so we traverse to the left
\r
1949 nextNode = nextNode->leftN;
\r
1952 /* Here we have located the only node that can be reached by the
\r
1953 * bits in the requested key. It could in fact be that key or the node
\r
1954 * we need to use to insert the new key.
\r
1956 if (nextNode->key == key)
\r
1958 /* We have located an exact match, but we will only append to the bucket chain
\r
1959 * if this trie accepts duplicate keys.
\r
1961 if (trie->allowDups ==ANTLR3_TRUE)
\r
1963 /* Yes, we are accepting duplicates
\r
1965 newEnt = (pANTLR3_TRIE_ENTRY)ANTLR3_CALLOC(1, sizeof(ANTLR3_TRIE_ENTRY));
\r
1967 if (newEnt == NULL)
\r
1969 /* Out of memory, all we can do is return the fact that the insert failed.
\r
1971 return ANTLR3_FALSE;
\r
1974 /* Otherwise insert this in the chain
\r
1976 newEnt->type = type;
\r
1977 newEnt->freeptr = freeptr;
\r
1978 if (type == ANTLR3_HASH_TYPE_STR)
\r
1980 newEnt->data.ptr = data;
\r
1984 newEnt->data.intVal = intVal;
\r
1987 /* We want to be able to traverse the stored elements in the order that they were
\r
1988 * added as duplicate keys. We might need to revise this opinion if we end up having many duplicate keys
\r
1989 * as perhaps reverse order is just as good, so long as it is ordered.
\r
1991 nextEnt = nextNode->buckets;
\r
1992 while (nextEnt->next != NULL)
\r
1994 nextEnt = nextEnt->next;
\r
1996 nextEnt->next = newEnt;
\r
1999 return ANTLR3_TRUE;
\r
2003 /* We found the key is already there and we are not allowed duplicates in this
\r
2006 return ANTLR3_FALSE;
\r
2010 /* Here we have discovered the only node that can be reached by the bits in the key
\r
2011 * but we have found that this node is not the key we need to insert. We must find the
\r
2012 * the leftmost bit by which the current key for that node and the new key we are going
\r
2013 * to insert, differ. While this nested series of ifs may look a bit strange, experimentation
\r
2014 * showed that it allows a machine code path that works well with predicated execution
\r
2016 xorKey = (key ^ nextNode->key); /* Gives 1 bits only where they differ then we find the left most 1 bit*/
\r
2018 /* Most common case is a 32 bit key really
\r
2020 #ifdef ANTLR3_USE_64BIT
\r
2021 if (xorKey & 0xFFFFFFFF00000000)
\r
2023 if (xorKey & 0xFFFF000000000000)
\r
2025 if (xorKey & 0xFF00000000000000)
\r
2027 depth = 56 + bitIndex[((xorKey & 0xFF00000000000000)>>56)];
\r
2031 depth = 48 + bitIndex[((xorKey & 0x00FF000000000000)>>48)];
\r
2036 if (xorKey & 0x0000FF0000000000)
\r
2038 depth = 40 + bitIndex[((xorKey & 0x0000FF0000000000)>>40)];
\r
2042 depth = 32 + bitIndex[((xorKey & 0x000000FF00000000)>>32)];
\r
2049 if (xorKey & 0x00000000FFFF0000)
\r
2051 if (xorKey & 0x00000000FF000000)
\r
2053 depth = 24 + bitIndex[((xorKey & 0x00000000FF000000)>>24)];
\r
2057 depth = 16 + bitIndex[((xorKey & 0x0000000000FF0000)>>16)];
\r
2062 if (xorKey & 0x000000000000FF00)
\r
2064 depth = 8 + bitIndex[((xorKey & 0x0000000000000FF00)>>8)];
\r
2068 depth = bitIndex[xorKey & 0x00000000000000FF];
\r
2073 /* We have located the leftmost differing bit, indicated by the depth variable. So, we know what
\r
2074 * bit index we are to insert the new entry at. There are two cases, being where the two keys
\r
2075 * differ at a bit position that is not currently part of the bit testing, where they differ on a bit
\r
2076 * that is currently being skipped in the indexed comparisons, and where they differ on a bit
\r
2077 * that is merely lower down in the current bit search. If the bit index went bit 4, bit 2 and they differ
\r
2078 * 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
\r
2079 * then we have the easy bit <pun>.
\r
2081 * So, set up to descend the tree again, but this time looking for the insert point
\r
2082 * according to whether we skip the bit that differs or not.
\r
2084 thisNode = trie->root;
\r
2085 entNode = trie->root->leftN;
\r
2087 /* Note the slight difference in the checks here to cover both cases
\r
2089 while (thisNode->bitNum > entNode->bitNum && entNode->bitNum > depth)
\r
2091 /* Still descending the structure, next node becomes current.
\r
2093 thisNode = entNode;
\r
2095 if (key & bitMask[entNode->bitNum])
\r
2097 /* Bit at the required index was 1, so traverse the right node from here
\r
2099 entNode = entNode->rightN;
\r
2103 /* Bit at the required index was 0, so we traverse to the left
\r
2105 entNode = entNode->leftN;
\r
2109 /* We have located the correct insert point for this new key, so we need
\r
2110 * to allocate our entry and insert it etc.
\r
2112 nextNode = (pANTLR3_INT_TRIE_NODE)ANTLR3_CALLOC(1, sizeof(ANTLR3_INT_TRIE_NODE));
\r
2113 if (nextNode == NULL)
\r
2115 /* All that work and no memory - bummer.
\r
2117 return ANTLR3_FALSE;
\r
2120 /* Build a new entry block for the new node
\r
2122 newEnt = (pANTLR3_TRIE_ENTRY)ANTLR3_CALLOC(1, sizeof(ANTLR3_TRIE_ENTRY));
\r
2124 if (newEnt == NULL)
\r
2126 /* Out of memory, all we can do is return the fact that the insert failed.
\r
2128 return ANTLR3_FALSE;
\r
2131 /* Otherwise enter this in our new node
\r
2133 newEnt->type = type;
\r
2134 newEnt->freeptr = freeptr;
\r
2135 if (type == ANTLR3_HASH_TYPE_STR)
\r
2137 newEnt->data.ptr = data;
\r
2141 newEnt->data.intVal = intVal;
\r
2145 nextNode->buckets = newEnt;
\r
2146 nextNode->key = key;
\r
2147 nextNode->bitNum = depth;
\r
2149 /* Work out the right and left pointers for this new node, which involve
\r
2150 * terminating with the current found node either right or left according
\r
2151 * to whether the current index bit is 1 or 0
\r
2153 if (key & bitMask[depth])
\r
2155 nextNode->leftN = entNode; /* Terminates at previous position */
\r
2156 nextNode->rightN = nextNode; /* Terminates with itself */
\r
2160 nextNode->rightN = entNode; /* Terminates at previous position */
\r
2161 nextNode->leftN = nextNode; /* Terminates with itself */
\r
2164 /* Finally, we need to change the pointers at the node we located
\r
2165 * for inserting. If the key bit at its index is set then the right
\r
2166 * pointer for that node becomes the newly created node, otherwise the left
\r
2169 if (key & bitMask[thisNode->bitNum] )
\r
2171 thisNode->rightN = nextNode;
\r
2175 thisNode->leftN = nextNode;
\r
2181 return ANTLR3_TRUE;
\r
2184 /** Release memory allocated to this tree.
\r
2185 * Basic algorithm is that we do a depth first left descent and free
\r
2186 * up any nodes that are not backward pointers.
\r
2189 freeIntNode(pANTLR3_INT_TRIE_NODE node)
\r
2191 pANTLR3_TRIE_ENTRY thisEntry;
\r
2192 pANTLR3_TRIE_ENTRY nextEntry;
\r
2194 /* If this node has a left pointer that is not a back pointer
\r
2195 * then recursively call to free this
\r
2197 if (node->bitNum > node->leftN->bitNum)
\r
2199 /* We have a left node that needs descending, so do it.
\r
2201 freeIntNode(node->leftN);
\r
2204 /* The left nodes from here should now be dealt with, so
\r
2205 * we need to descend any right nodes that are not back pointers
\r
2207 if (node->bitNum > node->rightN->bitNum)
\r
2209 /* There are some right nodes to descend and deal with.
\r
2211 freeIntNode(node->rightN);
\r
2214 /* Now all the children are dealt with, we can destroy
\r
2217 thisEntry = node->buckets;
\r
2219 while (thisEntry != NULL)
\r
2221 nextEntry = thisEntry->next;
\r
2223 /* Do we need to call a custom free pointer for this string entry?
\r
2225 if (thisEntry->type == ANTLR3_HASH_TYPE_STR && thisEntry->freeptr != NULL)
\r
2227 thisEntry->freeptr(thisEntry->data.ptr);
\r
2230 /* Now free the data for this bucket entry
\r
2232 ANTLR3_FREE(thisEntry);
\r
2233 thisEntry = nextEntry; /* See if there are any more to free */
\r
2236 /* The bucket entry is now gone, so we can free the memory for
\r
2237 * the entry itself.
\r
2239 ANTLR3_FREE(node);
\r
2241 /* And that should be it for everything under this node and itself
\r
2245 /** Called to free all nodes and the structure itself.
\r
2248 intTrieFree (pANTLR3_INT_TRIE trie)
\r
2250 /* Descend from the root and free all the nodes
\r
2252 freeIntNode(trie->root);
\r
2254 /* the nodes are all gone now, so we need only free the memory
\r
2255 * for the structure itself
\r
2257 ANTLR3_FREE(trie);
\r
2262 * Allocate and initialize a new ANTLR3 topological sorter, which can be
\r
2263 * used to define edges that identify numerical node indexes that depend on other
\r
2264 * numerical node indexes, which can then be sorted topologically such that
\r
2265 * any node is sorted after all its dependent nodes.
\r
2271 pANTLR3_TOPO topo;
\r
2272 topo = antlr3NewTopo();
\r
2274 if (topo == NULL) { out of memory }
\r
2276 topo->addEdge(topo, 3, 0); // Node 3 depends on node 0
\r
2277 topo->addEdge(topo, 0, 1); // Node - depends on node 1
\r
2278 topo->sortVector(topo, myVector); // Sort the vector in place (node numbers are the vector entry numbers)
\r
2282 ANTLR3_API pANTLR3_TOPO
\r
2285 pANTLR3_TOPO topo = (pANTLR3_TOPO)ANTLR3_MALLOC(sizeof(ANTLR3_TOPO));
\r
2292 // Initialize variables
\r
2295 topo->visited = NULL; // Don't know how big it is yet
\r
2296 topo->limit = 1; // No edges added yet
\r
2297 topo->edges = NULL; // No edges added yet
\r
2298 topo->sorted = NULL; // Nothing sorted at the start
\r
2299 topo->cycle = NULL; // No cycles at the start
\r
2300 topo->cycleMark = 0; // No cycles at the start
\r
2301 topo->hasCycle = ANTLR3_FALSE; // No cycle at the start
\r
2305 topo->addEdge = addEdge;
\r
2306 topo->sortToArray = sortToArray;
\r
2307 topo->sortVector = sortVector;
\r
2308 topo->free = freeTopo;
\r
2312 // Topological sorter
\r
2315 addEdge (pANTLR3_TOPO topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency)
\r
2318 ANTLR3_UINT32 maxEdge;
\r
2319 pANTLR3_BITSET edgeDeps;
\r
2321 if (edge>dependency)
\r
2327 maxEdge = dependency;
\r
2329 // We need to add an edge to says that the node indexed by 'edge' is
\r
2330 // dependent on the node indexed by 'dependency'
\r
2333 // First see if we have enough room in the edges array to add the edge?
\r
2335 if (topo->edges == NULL)
\r
2337 // We don't have any edges yet, so create an array to hold them
\r
2339 topo->edges = ANTLR3_CALLOC(sizeof(pANTLR3_BITSET) * (maxEdge + 1), 1);
\r
2340 if (topo->edges == NULL)
\r
2345 // Set the limit to what we have now
\r
2347 topo->limit = maxEdge + 1;
\r
2349 else if (topo->limit <= maxEdge)
\r
2351 // WE have some edges but not enough
\r
2353 topo->edges = ANTLR3_REALLOC(topo->edges, sizeof(pANTLR3_BITSET) * (maxEdge + 1));
\r
2354 if (topo->edges == NULL)
\r
2359 // Initialize the new bitmaps to ;indicate we have no edges defined yet
\r
2361 for (i = topo->limit; i <= maxEdge; i++)
\r
2363 *((topo->edges) + i) = NULL;
\r
2366 // Set the limit to what we have now
\r
2368 topo->limit = maxEdge + 1;
\r
2371 // If the edge was flagged as depending on itself, then we just
\r
2372 // do nothing as it means this routine was just called to add it
\r
2373 // in to the list of nodes.
\r
2375 if (edge == dependency)
\r
2380 // Pick up the bit map for the requested edge
\r
2382 edgeDeps = *((topo->edges) + edge);
\r
2384 if (edgeDeps == NULL)
\r
2386 // No edges are defined yet for this node
\r
2388 edgeDeps = antlr3BitsetNew(0);
\r
2389 *((topo->edges) + edge) = edgeDeps;
\r
2390 if (edgeDeps == NULL )
\r
2392 return; // Out of memory
\r
2396 // Set the bit in the bitmap that corresponds to the requested
\r
2399 edgeDeps->add(edgeDeps, dependency);
\r
2401 // And we are all set
\r
2408 * Given a starting node, descend its dependent nodes (ones that it has edges
\r
2409 * to) until we find one without edges. Having found a node without edges, we have
\r
2410 * discovered the bottom of a depth first search, which we can then ascend, adding
\r
2411 * the nodes in order from the bottom, which gives us the dependency order.
\r
2414 DFS(pANTLR3_TOPO topo, ANTLR3_UINT32 node)
\r
2416 pANTLR3_BITSET edges;
\r
2418 // Guard against a revisit and check for cycles
\r
2420 if (topo->hasCycle == ANTLR3_TRUE)
\r
2422 return; // We don't do anything else if we found a cycle
\r
2425 if (topo->visited->isMember(topo->visited, node))
\r
2427 // Check to see if we found a cycle. To do this we search the
\r
2428 // current cycle stack and see if we find this node already in the stack.
\r
2432 for (i=0; i<topo->cycleMark; i++)
\r
2434 if (topo->cycle[i] == node)
\r
2436 // Stop! We found a cycle in the input, so rejig the cycle
\r
2437 // stack so that it only contains the cycle and set the cycle flag
\r
2438 // which will tell the caller what happened
\r
2442 for (l = i; l < topo->cycleMark; l++)
\r
2444 topo->cycle[l - i] = topo->cycle[l]; // Move to zero base in the cycle list
\r
2447 // Recalculate the limit
\r
2449 topo->cycleMark -= i;
\r
2451 // Signal disaster
\r
2453 topo->hasCycle = ANTLR3_TRUE;
\r
2459 // So far, no cycles have been found and we have not visited this node yet,
\r
2460 // so this node needs to go into the cycle stack before we continue
\r
2461 // then we will take it out of the stack once we have descended all its
\r
2464 topo->cycle[topo->cycleMark++] = node;
\r
2466 // First flag that we have visited this node
\r
2468 topo->visited->add(topo->visited, node);
\r
2470 // Now, if this node has edges, then we want to ensure we visit
\r
2471 // them all before we drop through and add this node into the sorted
\r
2474 edges = *((topo->edges) + node);
\r
2475 if (edges != NULL)
\r
2477 // We have some edges, so visit each of the edge nodes
\r
2478 // that have not already been visited.
\r
2480 ANTLR3_UINT32 numBits; // How many bits are in the set
\r
2482 ANTLR3_UINT32 range;
\r
2484 numBits = edges->numBits(edges);
\r
2485 range = edges->size(edges); // Number of set bits
\r
2487 // Stop if we exahust the bit list or have checked the
\r
2488 // number of edges that this node refers to (so we don't
\r
2489 // check bits at the end that cannot possibly be set).
\r
2491 for (i=0; i<= numBits && range > 0; i++)
\r
2493 if (edges->isMember(edges, i))
\r
2495 range--; // About to check another one
\r
2497 // Found an edge, make sure we visit and descend it
\r
2504 // At this point we will have visited all the dependencies
\r
2505 // of this node and they will be ordered (even if there are cycles)
\r
2506 // So we just add the node into the sorted list at the
\r
2507 // current index position.
\r
2509 topo->sorted[topo->limit++] = node;
\r
2511 // Remove this node from the cycle list if we have not detected a cycle
\r
2513 if (topo->hasCycle == ANTLR3_FALSE)
\r
2515 topo->cycleMark--;
\r
2521 static pANTLR3_UINT32
\r
2522 sortToArray (pANTLR3_TOPO topo)
\r
2525 ANTLR3_UINT32 oldLimit;
\r
2527 // Guard against being called with no edges defined
\r
2529 if (topo->edges == NULL)
\r
2533 // First we need a vector to populate with enough
\r
2534 // entries to accomodate the sorted list and another to accomodate
\r
2535 // the maximum cycle we could detect which is all nodes such as 0->1->2->3->0
\r
2537 topo->sorted = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32));
\r
2538 topo->cycle = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32));
\r
2540 // Next we need an empty bitset to show whether we have visited a node
\r
2541 // or not. This is the bit that gives us linear time of course as we are essentially
\r
2542 // dropping through the nodes in depth first order and when we get to a node that
\r
2543 // has no edges, we pop back up the stack adding the nodes we traversed in reverse
\r
2546 topo->visited = antlr3BitsetNew(0);
\r
2548 // Now traverse the nodes as if we were just going left to right, but
\r
2549 // then descend each node unless it has already been visited.
\r
2551 oldLimit = topo->limit; // Number of nodes to traverse linearly
\r
2552 topo->limit = 0; // Next entry in the sorted table
\r
2554 for (v = 0; v < oldLimit; v++)
\r
2556 // If we did not already visit this node, then descend it until we
\r
2557 // get a node without edges or arrive at a node we have already visited.
\r
2559 if (topo->visited->isMember(topo->visited, v) == ANTLR3_FALSE)
\r
2561 // We have not visited this one so descend it
\r
2566 // Break the loop if we detect a cycle as we have no need to go any
\r
2569 if (topo->hasCycle == ANTLR3_TRUE)
\r
2575 // Reset the limit to the number we recorded as if we hit a
\r
2576 // cycle, then limit will have stopped at the node where we
\r
2577 // discovered the cycle, but in order to free the edge bitmaps
\r
2578 // we need to know how many we may have allocated and traverse them all.
\r
2580 topo->limit = oldLimit;
\r
2582 // Having traversed all the nodes we were given, we
\r
2583 // are guaranteed to have ordered all the nodes or detected a
\r
2586 return topo->sorted;
\r
2590 sortVector (pANTLR3_TOPO topo, pANTLR3_VECTOR v)
\r
2592 // To sort a vector, we first perform the
\r
2593 // sort to an array, then use the results to reorder the vector
\r
2594 // we are given. This is just a convenience routine that allows you to
\r
2595 // sort the children of a tree node into topological order before or
\r
2596 // during an AST walk. This can be useful for optimizations that require
\r
2597 // dag reorders and also when the input stream defines thigns that are
\r
2598 // interdependent and you want to walk the list of the generated trees
\r
2599 // for those things in topological order so you can ignore the interdependencies
\r
2604 // Used as a lookup index to find the current location in the vector of
\r
2605 // the vector entry that was originally at position [0], [1], [2] etc
\r
2607 pANTLR3_UINT32 vIndex;
\r
2609 // Sort into an array, then we can use the array that is
\r
2610 // stored in the topo
\r
2612 if (topo->sortToArray(topo) == 0)
\r
2614 return; // There were no edges
\r
2617 if (topo->hasCycle == ANTLR3_TRUE)
\r
2619 return; // Do nothing if we detected a cycle
\r
2622 // Ensure that the vector we are sorting is at least as big as the
\r
2623 // the input sequence we were adsked to sort. It does not matter if it is
\r
2624 // bigger as thaat probably just means that nodes numbered higher than the
\r
2625 // limit had no dependencies and so can be left alone.
\r
2627 if (topo->limit > v->count)
\r
2629 // We can only sort the entries that we have dude! The caller is
\r
2630 // responsible for ensuring the vector is the correct one and is the
\r
2631 // correct size etc.
\r
2633 topo->limit = v->count;
\r
2635 // We need to know the locations of each of the entries
\r
2636 // in the vector as we don't want to duplicate them in a new vector. We
\r
2637 // just use an indirection table to get the vector entry for a particular sequence
\r
2638 // acording to where we moved it last. Then we can just swap vector entries until
\r
2639 // we are done :-)
\r
2641 vIndex = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32));
\r
2643 // Start index, each vector entry is located where you think it is
\r
2645 for (i = 0; i < topo->limit; i++)
\r
2650 // Now we traverse the sorted array and moved the entries of
\r
2651 // the vector around according to the sort order and the indirection
\r
2652 // table we just created. The index telsl us where in the vector the
\r
2653 // original element entry n is now located via vIndex[n].
\r
2655 for (i=0; i < topo->limit; i++)
\r
2657 ANTLR3_UINT32 ind;
\r
2659 // If the vector entry at i is already the one that it
\r
2660 // should be, then we skip moving it of course.
\r
2662 if (vIndex[topo->sorted[i]] == i)
\r
2667 // The vector entry at i, should be replaced with the
\r
2668 // vector entry indicated by topo->sorted[i]. The vector entry
\r
2669 // at topo->sorted[i] may have already been swapped out though, so we
\r
2670 // find where it is now and move it from there to i.
\r
2672 ind = vIndex[topo->sorted[i]];
\r
2673 v->swap(v, i, ind);
\r
2675 // Update our index. The element at i is now the one we wanted
\r
2676 // to be sorted here and the element we swapped out is now the
\r
2677 // element that was at i just before we swapped it. If you are lost now
\r
2678 // don't worry about it, we are just reindexing on the fly is all.
\r
2680 vIndex[topo->sorted[i]] = i;
\r
2684 // Having traversed all the entries, we have sorted the vector in place.
\r
2686 ANTLR3_FREE(vIndex);
\r
2691 freeTopo (pANTLR3_TOPO topo)
\r
2695 // Free the result vector
\r
2697 if (topo->sorted != NULL)
\r
2699 ANTLR3_FREE(topo->sorted);
\r
2700 topo->sorted = NULL;
\r
2703 // Free the visited map
\r
2705 if (topo->visited != NULL)
\r
2708 topo->visited->free(topo->visited);
\r
2709 topo->visited = NULL;
\r
2712 // Free any edgemaps
\r
2714 if (topo->edges != NULL)
\r
2716 pANTLR3_BITSET edgeList;
\r
2719 for (i=0; i<topo->limit; i++)
\r
2721 edgeList = *((topo->edges) + i);
\r
2722 if (edgeList != NULL)
\r
2724 edgeList->free(edgeList);
\r
2728 ANTLR3_FREE(topo->edges);
\r
2730 topo->edges = NULL;
\r
2732 // Free any cycle map
\r
2734 if (topo->cycle != NULL)
\r
2736 ANTLR3_FREE(topo->cycle);
\r
2739 ANTLR3_FREE(topo);
\r
Code Review / simantics / platform.git / blob