• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /// \file
2 /// Provides a number of useful functions that are roughly equivalent
3 /// to java HashTable and List for the purposes of Antlr 3 C runtime.
4 /// Also useable by the C programmer for things like symbol tables pointers
5 /// and so on.
6 ///
7 ///
8 
9 // [The "BSD licence"]
10 // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
11 // http://www.temporal-wave.com
12 // http://www.linkedin.com/in/jimidle
13 //
14 // All rights reserved.
15 //
16 // Redistribution and use in source and binary forms, with or without
17 // modification, are permitted provided that the following conditions
18 // are met:
19 // 1. Redistributions of source code must retain the above copyright
20 //    notice, this list of conditions and the following disclaimer.
21 // 2. Redistributions in binary form must reproduce the above copyright
22 //    notice, this list of conditions and the following disclaimer in the
23 //    documentation and/or other materials provided with the distribution.
24 // 3. The name of the author may not be used to endorse or promote products
25 //    derived from this software without specific prior written permission.
26 //
27 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
28 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
29 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
30 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
31 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
32 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
33 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
34 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
35 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
36 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 
38 #include    <antlr3.h>
39 
40 #include "antlr3collections.h"
41 
42 // Interface functions for hash table
43 //
44 
45 // String based keys
46 //
47 static void					antlr3HashDelete    (pANTLR3_HASH_TABLE table, void * key);
48 static void *				antlr3HashGet	(pANTLR3_HASH_TABLE table, void * key);
49 static pANTLR3_HASH_ENTRY   antlr3HashRemove    (pANTLR3_HASH_TABLE table, void * key);
50 static ANTLR3_INT32			antlr3HashPut	(pANTLR3_HASH_TABLE table, void * key, void * element, void (ANTLR3_CDECL *freeptr)(void *));
51 
52 // Integer based keys (Lists and so on)
53 //
54 static void					antlr3HashDeleteI   (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key);
55 static void *				antlr3HashGetI	(pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key);
56 static pANTLR3_HASH_ENTRY   antlr3HashRemoveI   (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key);
57 static ANTLR3_INT32			antlr3HashPutI	(pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *));
58 
59 static void					antlr3HashFree	(pANTLR3_HASH_TABLE table);
60 static ANTLR3_UINT32	    antlr3HashSize	(pANTLR3_HASH_TABLE table);
61 
62 // -----------
63 
64 // Interface functions for enumeration
65 //
66 static int	    antlr3EnumNext	    (pANTLR3_HASH_ENUM en, pANTLR3_HASH_KEY * key, void ** data);
67 static void	    antlr3EnumFree	    (pANTLR3_HASH_ENUM en);
68 
69 // Interface functions for List
70 //
71 static void				antlr3ListFree	(pANTLR3_LIST list);
72 static void				antlr3ListDelete(pANTLR3_LIST list, ANTLR3_INTKEY key);
73 static void *			antlr3ListGet	(pANTLR3_LIST list, ANTLR3_INTKEY key);
74 static ANTLR3_INT32		antlr3ListPut	(pANTLR3_LIST list, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *));
75 static ANTLR3_INT32		antlr3ListAdd   (pANTLR3_LIST list, void * element, void (ANTLR3_CDECL *freeptr)(void *));
76 static void *			antlr3ListRemove(pANTLR3_LIST list, ANTLR3_INTKEY key);
77 static ANTLR3_UINT32	antlr3ListSize	(pANTLR3_LIST list);
78 
79 // Interface functions for Stack
80 //
81 static void				antlr3StackFree	(pANTLR3_STACK  stack);
82 static void *			antlr3StackPop	(pANTLR3_STACK	stack);
83 static void *			antlr3StackGet	(pANTLR3_STACK	stack, ANTLR3_INTKEY key);
84 static ANTLR3_BOOLEAN	antlr3StackPush	(pANTLR3_STACK	stack, void * element, void (ANTLR3_CDECL *freeptr)(void *));
85 static ANTLR3_UINT32	antlr3StackSize	(pANTLR3_STACK	stack);
86 static void *			antlr3StackPeek	(pANTLR3_STACK	stack);
87 
88 // Interface functions for vectors
89 //
90 static	void ANTLR3_CDECL	antlr3VectorFree	(pANTLR3_VECTOR vector);
91 static	void				antlr3VectorDel		(pANTLR3_VECTOR vector, ANTLR3_UINT32 entry);
92 static	void *				antlr3VectorGet		(pANTLR3_VECTOR vector, ANTLR3_UINT32 entry);
93 static	void *				antrl3VectorRemove	(pANTLR3_VECTOR vector, ANTLR3_UINT32 entry);
94 static	void				antlr3VectorClear	(pANTLR3_VECTOR vector);
95 static	ANTLR3_UINT32		antlr3VectorAdd		(pANTLR3_VECTOR vector, void * element, void (ANTLR3_CDECL *freeptr)(void *));
96 static	ANTLR3_UINT32		antlr3VectorSet		(pANTLR3_VECTOR vector, ANTLR3_UINT32 entry, void * element, void (ANTLR3_CDECL *freeptr)(void *), ANTLR3_BOOLEAN freeExisting);
97 static	ANTLR3_UINT32		antlr3VectorSize    (pANTLR3_VECTOR vector);
98 static	ANTLR3_BOOLEAN      antlr3VectorSwap	(pANTLR3_VECTOR vector, ANTLR3_UINT32 entry1, ANTLR3_UINT32 entry2);
99 
100 static  void                newPool             (pANTLR3_VECTOR_FACTORY factory);
101 static  void				closeVectorFactory  (pANTLR3_VECTOR_FACTORY factory);
102 static	pANTLR3_VECTOR		newVector			(pANTLR3_VECTOR_FACTORY factory);
103 static	void				returnVector		(pANTLR3_VECTOR_FACTORY factory, pANTLR3_VECTOR vector);
104 
105 
106 // Interface functions for int TRIE
107 //
108 static	pANTLR3_TRIE_ENTRY	intTrieGet		(pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key);
109 static	ANTLR3_BOOLEAN		intTrieDel		(pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key);
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 *));
111 static	void				intTrieFree		(pANTLR3_INT_TRIE trie);
112 
113 
114 // Interface functions for topological sorter
115 //
116 static  void            addEdge          (pANTLR3_TOPO topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency);
117 static  pANTLR3_UINT32  sortToArray      (pANTLR3_TOPO topo);
118 static  void            sortVector       (pANTLR3_TOPO topo, pANTLR3_VECTOR v);
119 static  void            freeTopo         (pANTLR3_TOPO topo);
120 
121 // Local function to advance enumeration structure pointers
122 //
123 static void antlr3EnumNextEntry(pANTLR3_HASH_ENUM en);
124 
125 pANTLR3_HASH_TABLE
antlr3HashTableNew(ANTLR3_UINT32 sizeHint)126 antlr3HashTableNew(ANTLR3_UINT32 sizeHint)
127 {
128 	// All we have to do is create the hashtable tracking structure
129 	// and allocate memory for the requested number of buckets.
130 	//
131 	pANTLR3_HASH_TABLE	table;
132 
133 	ANTLR3_UINT32	bucket;	// Used to traverse the buckets
134 
135 	table   = ANTLR3_MALLOC(sizeof(ANTLR3_HASH_TABLE));
136 
137 	// Error out if no memory left
138 	if	(table	== NULL)
139 	{
140 		return	NULL;
141 	}
142 
143 	// Allocate memory for the buckets
144 	//
145 	table->buckets = (pANTLR3_HASH_BUCKET) ANTLR3_MALLOC((size_t) (sizeof(ANTLR3_HASH_BUCKET) * sizeHint));
146 
147 	if	(table->buckets == NULL)
148 	{
149 		ANTLR3_FREE((void *)table);
150 		return	NULL;
151 	}
152 
153 	// Modulo of the table, (bucket count).
154 	//
155 	table->modulo   = sizeHint;
156 
157 	table->count    = 0;	    /* Nothing in there yet ( I hope)	*/
158 
159 	/* Initialize the buckets to empty
160 	*/
161 	for	(bucket = 0; bucket < sizeHint; bucket++)
162 	{
163 		table->buckets[bucket].entries = NULL;
164 	}
165 
166 	/* Exclude duplicate entries by default
167 	*/
168 	table->allowDups	= ANTLR3_FALSE;
169 
170     /* Assume that keys should by strduped before they are
171      * entered in the table.
172      */
173     table->doStrdup     = ANTLR3_TRUE;
174 
175 	/* Install the interface
176 	*/
177 
178 	table->get		=  antlr3HashGet;
179 	table->put		=  antlr3HashPut;
180 	table->del		=  antlr3HashDelete;
181 	table->remove	=  antlr3HashRemove;
182 
183 	table->getI		=  antlr3HashGetI;
184 	table->putI		=  antlr3HashPutI;
185 	table->delI		=  antlr3HashDeleteI;
186 	table->removeI	=  antlr3HashRemoveI;
187 
188 	table->size		=  antlr3HashSize;
189 	table->free		=  antlr3HashFree;
190 
191 	return  table;
192 }
193 
194 static void
antlr3HashFree(pANTLR3_HASH_TABLE table)195 antlr3HashFree(pANTLR3_HASH_TABLE table)
196 {
197     ANTLR3_UINT32	bucket;	/* Used to traverse the buckets	*/
198 
199     pANTLR3_HASH_BUCKET	thisBucket;
200     pANTLR3_HASH_ENTRY	entry;
201     pANTLR3_HASH_ENTRY	nextEntry;
202 
203     /* Free the table, all buckets and all entries, and all the
204      * keys and data (if the table exists)
205      */
206     if	(table	!= NULL)
207     {
208 	for	(bucket = 0; bucket < table->modulo; bucket++)
209 	{
210 	    thisBucket	= &(table->buckets[bucket]);
211 
212 	    /* Allow sparse tables, though we don't create them as such at present
213 	     */
214 	    if	( thisBucket != NULL)
215 	    {
216 		entry	= thisBucket->entries;
217 
218 		/* Search all entries in the bucket and free them up
219 		 */
220 		while	(entry != NULL)
221 		{
222 		    /* Save next entry - we do not want to access memory in entry after we
223 		     * have freed it.
224 		     */
225 		    nextEntry	= entry->nextEntry;
226 
227 		    /* Free any data pointer, this only happens if the user supplied
228 		     * a pointer to a routine that knwos how to free the structure they
229 		     * added to the table.
230 		     */
231 		    if	(entry->free != NULL)
232 		    {
233 			entry->free(entry->data);
234 		    }
235 
236 		    /* Free the key memory - we know that we allocated this
237 		     */
238 		    if	(entry->keybase.type == ANTLR3_HASH_TYPE_STR && entry->keybase.key.sKey != NULL)
239 		    {
240 			ANTLR3_FREE(entry->keybase.key.sKey);
241 		    }
242 
243 		    /* Free this entry
244 		     */
245 		    ANTLR3_FREE(entry);
246 		    entry   = nextEntry;    /* Load next pointer to see if we shoud free it */
247 		}
248 		/* Invalidate the current pointer
249 		 */
250 		thisBucket->entries = NULL;
251 	    }
252 	}
253 
254 	/* Now we can free the bucket memory
255 	 */
256 	ANTLR3_FREE(table->buckets);
257     }
258 
259     /* Now we free teh memory for the table itself
260      */
261     ANTLR3_FREE(table);
262 }
263 
264 /** return the current size of the hash table
265  */
antlr3HashSize(pANTLR3_HASH_TABLE table)266 static ANTLR3_UINT32	antlr3HashSize	    (pANTLR3_HASH_TABLE table)
267 {
268     return  table->count;
269 }
270 
271 /** Remove a numeric keyed entry from a hash table if it exists,
272  *  no error if it does not exist.
273  */
antlr3HashRemoveI(pANTLR3_HASH_TABLE table,ANTLR3_INTKEY key)274 static pANTLR3_HASH_ENTRY   antlr3HashRemoveI   (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key)
275 {
276     ANTLR3_UINT32	    hash;
277     pANTLR3_HASH_BUCKET	    bucket;
278     pANTLR3_HASH_ENTRY	    entry;
279     pANTLR3_HASH_ENTRY	    * nextPointer;
280 
281     /* First we need to know the hash of the provided key
282      */
283     hash    = (ANTLR3_UINT32)(key % (ANTLR3_INTKEY)(table->modulo));
284 
285     /* Knowing the hash, we can find the bucket
286      */
287     bucket  = table->buckets + hash;
288 
289     /* Now, we traverse the entries in the bucket until
290      * we find the key or the end of the entries in the bucket.
291      * We track the element prior to the one we are examining
292      * as we need to set its next pointer to the next pointer
293      * of the entry we are deleting (if we find it).
294      */
295     entry	    =   bucket->entries;    /* Entry to examine					    */
296     nextPointer	    = & bucket->entries;    /* Where to put the next pointer of the deleted entry   */
297 
298     while   (entry != NULL)
299     {
300 	/* See if this is the entry we wish to delete
301 	 */
302 	if  (entry->keybase.key.iKey == key)
303 	{
304 	    /* It was the correct entry, so we set the next pointer
305 	     * of the previous entry to the next pointer of this
306 	     * located one, which takes it out of the chain.
307 	     */
308 	    (*nextPointer)		= entry->nextEntry;
309 
310 	    table->count--;
311 
312 	    return entry;
313 	}
314 	else
315 	{
316 	    /* We found an entry but it wasn't the one that was wanted, so
317 	     * move to the next one, if any.
318 	     */
319 	    nextPointer	= & (entry->nextEntry);	    /* Address of the next pointer in the current entry	    */
320 	    entry	= entry->nextEntry;	    /* Address of the next element in the bucket (if any)   */
321 	}
322     }
323 
324     return NULL;  /* Not found */
325 }
326 
327 /** Remove the element in the hash table for a particular
328  *  key value, if it exists - no error if it does not.
329  */
330 static pANTLR3_HASH_ENTRY
antlr3HashRemove(pANTLR3_HASH_TABLE table,void * key)331 antlr3HashRemove(pANTLR3_HASH_TABLE table, void * key)
332 {
333     ANTLR3_UINT32	    hash;
334     pANTLR3_HASH_BUCKET	    bucket;
335     pANTLR3_HASH_ENTRY	    entry;
336     pANTLR3_HASH_ENTRY	    * nextPointer;
337 
338     /* First we need to know the hash of the provided key
339      */
340     hash    = antlr3Hash(key, (ANTLR3_UINT32)strlen((const char *)key));
341 
342     /* Knowing the hash, we can find the bucket
343      */
344     bucket  = table->buckets + (hash % table->modulo);
345 
346     /* Now, we traverse the entries in the bucket until
347      * we find the key or the end of the entires in the bucket.
348      * We track the element prior to the one we are exmaining
349      * as we need to set its next pointer to the next pointer
350      * of the entry we are deleting (if we find it).
351      */
352     entry	    =   bucket->entries;    /* Entry to examine					    */
353     nextPointer	    = & bucket->entries;    /* Where to put the next pointer of the deleted entry   */
354 
355     while   (entry != NULL)
356     {
357 	/* See if this is the entry we wish to delete
358 	 */
359 	if  (strcmp((const char *)key, (const char *)entry->keybase.key.sKey) == 0)
360 	{
361 	    /* It was the correct entry, so we set the next pointer
362 	     * of the previous entry to the next pointer of this
363 	     * located one, which takes it out of the chain.
364 	     */
365 	    (*nextPointer)		= entry->nextEntry;
366 
367 	    /* Release the key - if we allocated that
368 	     */
369         if (table->doStrdup == ANTLR3_TRUE)
370         {
371             ANTLR3_FREE(entry->keybase.key.sKey);
372         }
373 	    entry->keybase.key.sKey	= NULL;
374 
375 	    table->count--;
376 
377 	    return entry;
378 	}
379 	else
380 	{
381 	    /* We found an entry but it wasn't the one that was wanted, so
382 	     * move to the next one, if any.
383 	     */
384 	    nextPointer	= & (entry->nextEntry);	    /* Address of the next pointer in the current entry	    */
385 	    entry	= entry->nextEntry;	    /* Address of the next element in the bucket (if any)   */
386 	}
387     }
388 
389     return NULL;  /* Not found */
390 }
391 
392 /** Takes the element with the supplied key out of the list, and deletes the data
393  *  calling the supplied free() routine if any.
394  */
395 static void
antlr3HashDeleteI(pANTLR3_HASH_TABLE table,ANTLR3_INTKEY key)396 antlr3HashDeleteI    (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key)
397 {
398     pANTLR3_HASH_ENTRY	entry;
399 
400     entry = antlr3HashRemoveI(table, key);
401 
402     /* Now we can free the elements and the entry in order
403      */
404     if	(entry != NULL && entry->free != NULL)
405     {
406 	/* Call programmer supplied function to release this entry data
407 	 */
408 	entry->free(entry->data);
409 	entry->data = NULL;
410     }
411     /* Finally release the space for this entry block.
412      */
413     ANTLR3_FREE(entry);
414 }
415 
416 /** Takes the element with the supplied key out of the list, and deletes the data
417  *  calling the supplied free() routine if any.
418  */
419 static void
antlr3HashDelete(pANTLR3_HASH_TABLE table,void * key)420 antlr3HashDelete    (pANTLR3_HASH_TABLE table, void * key)
421 {
422     pANTLR3_HASH_ENTRY	entry;
423 
424     entry = antlr3HashRemove(table, key);
425 
426     /* Now we can free the elements and the entry in order
427      */
428     if	(entry != NULL && entry->free != NULL)
429     {
430 	/* Call programmer supplied function to release this entry data
431 	 */
432 	entry->free(entry->data);
433 	entry->data = NULL;
434     }
435     /* Finally release the space for this entry block.
436      */
437     ANTLR3_FREE(entry);
438 }
439 
440 /** Return the element pointer in the hash table for a particular
441  *  key value, or NULL if it don't exist (or was itself NULL).
442  */
443 static void *
antlr3HashGetI(pANTLR3_HASH_TABLE table,ANTLR3_INTKEY key)444 antlr3HashGetI(pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key)
445 {
446     ANTLR3_UINT32	    hash;
447     pANTLR3_HASH_BUCKET	    bucket;
448     pANTLR3_HASH_ENTRY	    entry;
449 
450     /* First we need to know the hash of the provided key
451      */
452     hash    = (ANTLR3_UINT32)(key % (ANTLR3_INTKEY)(table->modulo));
453 
454     /* Knowing the hash, we can find the bucket
455      */
456     bucket  = table->buckets + hash;
457 
458     /* Now we can inspect the key at each entry in the bucket
459      * and see if we have a match.
460      */
461     entry   = bucket->entries;
462 
463     while   (entry != NULL)
464     {
465 	if  (entry->keybase.key.iKey == key)
466 	{
467 	    /* Match was found, return the data pointer for this entry
468 	     */
469 	    return  entry->data;
470 	}
471 	entry = entry->nextEntry;
472     }
473 
474     /* If we got here, then we did not find the key
475      */
476     return  NULL;
477 }
478 
479 /** Return the element pointer in the hash table for a particular
480  *  key value, or NULL if it don't exist (or was itself NULL).
481  */
482 static void *
antlr3HashGet(pANTLR3_HASH_TABLE table,void * key)483 antlr3HashGet(pANTLR3_HASH_TABLE table, void * key)
484 {
485     ANTLR3_UINT32	    hash;
486     pANTLR3_HASH_BUCKET	    bucket;
487     pANTLR3_HASH_ENTRY	    entry;
488 
489 
490     /* First we need to know the hash of the provided key
491      */
492     hash    = antlr3Hash(key, (ANTLR3_UINT32)strlen((const char *)key));
493 
494     /* Knowing the hash, we can find the bucket
495      */
496     bucket  = table->buckets + (hash % table->modulo);
497 
498     /* Now we can inspect the key at each entry in the bucket
499      * and see if we have a match.
500      */
501     entry   = bucket->entries;
502 
503     while   (entry != NULL)
504     {
505 	if  (strcmp((const char *)key, (const char *)entry->keybase.key.sKey) == 0)
506 	{
507 	    /* Match was found, return the data pointer for this entry
508 	     */
509 	    return  entry->data;
510 	}
511 	entry = entry->nextEntry;
512     }
513 
514     /* If we got here, then we did not find the key
515      */
516     return  NULL;
517 }
518 
519 /** Add the element pointer in to the table, based upon the
520  *  hash of the provided key.
521  */
522 static	ANTLR3_INT32
antlr3HashPutI(pANTLR3_HASH_TABLE table,ANTLR3_INTKEY key,void * element,void (ANTLR3_CDECL * freeptr)(void *))523 antlr3HashPutI(pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *))
524 {
525 	ANTLR3_UINT32	    hash;
526 	pANTLR3_HASH_BUCKET	    bucket;
527 	pANTLR3_HASH_ENTRY	    entry;
528 	pANTLR3_HASH_ENTRY	    * newPointer;
529 
530 	/* First we need to know the hash of the provided key
531 	*/
532 	hash    = (ANTLR3_UINT32)(key % (ANTLR3_INTKEY)(table->modulo));
533 
534 	/* Knowing the hash, we can find the bucket
535 	*/
536 	bucket  = table->buckets + hash;
537 
538 	/* Knowing the bucket, we can traverse the entries until we
539 	* we find a NULL pointer or we find that this is already
540 	* in the table and duplicates were not allowed.
541 	*/
542 	newPointer	= &bucket->entries;
543 
544 	while   (*newPointer !=  NULL)
545 	{
546 		/* The value at new pointer is pointing to an existing entry.
547 		* If duplicates are allowed then we don't care what it is, but
548 		* must reject this add if the key is the same as the one we are
549 		* supplied with.
550 		*/
551 		if  (table->allowDups == ANTLR3_FALSE)
552 		{
553 			if	((*newPointer)->keybase.key.iKey == key)
554 			{
555 				return	ANTLR3_ERR_HASHDUP;
556 			}
557 		}
558 
559 		/* Point to the next entry pointer of the current entry we
560 		* are traversing, if it is NULL we will create our new
561 		* structure and point this to it.
562 		*/
563 		newPointer = &((*newPointer)->nextEntry);
564 	}
565 
566 	/* newPointer is now pointing at the pointer where we need to
567 	* add our new entry, so let's crate the entry and add it in.
568 	*/
569 	entry   = (pANTLR3_HASH_ENTRY)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_HASH_ENTRY));
570 
571 	if	(entry == NULL)
572 	{
573 		return	ANTLR3_ERR_NOMEM;
574 	}
575 
576 	entry->data			= element;		/* Install the data element supplied			*/
577 	entry->free			= freeptr;		/* Function that knows how to release the entry		*/
578 	entry->keybase.type		= ANTLR3_HASH_TYPE_INT;	/* Indicate the key type stored here for when we free	*/
579 	entry->keybase.key.iKey	= key;			/* Record the key value					*/
580 	entry->nextEntry		= NULL;			/* Ensure that the forward pointer ends the chain	*/
581 
582 	*newPointer	= entry;    /* Install the next entry in this bucket	*/
583 
584 	table->count++;
585 
586 	return  ANTLR3_SUCCESS;
587 }
588 
589 
590 /** Add the element pointer in to the table, based upon the
591  *  hash of the provided key.
592  */
593 static	ANTLR3_INT32
antlr3HashPut(pANTLR3_HASH_TABLE table,void * key,void * element,void (ANTLR3_CDECL * freeptr)(void *))594 antlr3HashPut(pANTLR3_HASH_TABLE table, void * key, void * element, void (ANTLR3_CDECL *freeptr)(void *))
595 {
596 	ANTLR3_UINT32	    hash;
597 	pANTLR3_HASH_BUCKET	    bucket;
598 	pANTLR3_HASH_ENTRY	    entry;
599 	pANTLR3_HASH_ENTRY	    * newPointer;
600 
601 	/* First we need to know the hash of the provided key
602 	*/
603 	hash    = antlr3Hash(key, (ANTLR3_UINT32)strlen((const char *)key));
604 
605 	/* Knowing the hash, we can find the bucket
606 	*/
607 	bucket  = table->buckets + (hash % table->modulo);
608 
609 	/* Knowign the bucket, we can traverse the entries until we
610 	* we find a NULL pointer ofr we find that this is already
611 	* in the table and duplicates were not allowed.
612 	*/
613 	newPointer	= &bucket->entries;
614 
615 	while   (*newPointer !=  NULL)
616 	{
617 		/* The value at new pointer is pointing to an existing entry.
618 		* If duplicates are allowed then we don't care what it is, but
619 		* must reject this add if the key is the same as the one we are
620 		* supplied with.
621 		*/
622 		if  (table->allowDups == ANTLR3_FALSE)
623 		{
624 			if	(strcmp((const char*) key, (const char *)(*newPointer)->keybase.key.sKey) == 0)
625 			{
626 				return	ANTLR3_ERR_HASHDUP;
627 			}
628 		}
629 
630 		/* Point to the next entry pointer of the current entry we
631 		* are traversing, if it is NULL we will create our new
632 		* structure and point this to it.
633 		*/
634 		newPointer = &((*newPointer)->nextEntry);
635 	}
636 
637 	/* newPointer is now poiting at the pointer where we need to
638 	* add our new entry, so let's crate the entry and add it in.
639 	*/
640 	entry   = (pANTLR3_HASH_ENTRY)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_HASH_ENTRY));
641 
642 	if	(entry == NULL)
643 	{
644 		return	ANTLR3_ERR_NOMEM;
645 	}
646 
647 	entry->data			= element;					/* Install the data element supplied				*/
648 	entry->free			= freeptr;					/* Function that knows how to release the entry	    */
649 	entry->keybase.type	= ANTLR3_HASH_TYPE_STR;     /* Indicate the key type stored here for free()	    */
650     if  (table->doStrdup == ANTLR3_TRUE)
651     {
652         entry->keybase.key.sKey	= ANTLR3_STRDUP(key);	/* Record the key value								*/
653     }
654     else
655     {
656         entry->keybase.key.sKey	= key;                  /* Record the key value								*/
657     }
658 	entry->nextEntry		= NULL;					/* Ensure that the forward pointer ends the chain   */
659 
660 	*newPointer	= entry;    /* Install the next entry in this bucket	*/
661 
662 	table->count++;
663 
664 	return  ANTLR3_SUCCESS;
665 }
666 
667 /** \brief Creates an enumeration structure to traverse the hash table.
668  *
669  * \param table Table to enumerate
670  * \return Pointer to enumeration structure.
671  */
672 pANTLR3_HASH_ENUM
antlr3EnumNew(pANTLR3_HASH_TABLE table)673 antlr3EnumNew	(pANTLR3_HASH_TABLE table)
674 {
675     pANTLR3_HASH_ENUM	en;
676 
677     /* Allocate structure memory
678      */
679     en    = (pANTLR3_HASH_ENUM) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_HASH_ENUM));
680 
681     /* Check that the allocation was good
682      */
683     if	(en == NULL)
684     {
685 	return	(pANTLR3_HASH_ENUM) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
686     }
687 
688     /* Initialize the start pointers
689     */
690     en->table	= table;
691     en->bucket	= 0;				/* First bucket		    */
692     en->entry	= en->table->buckets->entries;	/* First entry to return    */
693 
694     /* Special case in that the first bucket may not have anything in it
695      * but the antlr3EnumNext() function expects that the en->entry is
696      * set to the next valid pointer. Hence if it is not a valid element
697      * pointer, attempt to find the next one that is, (table may be empty
698      * of course.
699      */
700     if	(en->entry == NULL)
701     {
702 	antlr3EnumNextEntry(en);
703     }
704 
705     /* Install the interface
706      */
707     en->free	=  antlr3EnumFree;
708     en->next	=  antlr3EnumNext;
709 
710     /* All is good
711      */
712     return  en;
713 }
714 
715 /** \brief Return the next entry in the hashtable being traversed by the supplied
716  *         enumeration.
717  *
718  * \param[in] en Pointer to the enumeration tracking structure
719  * \param key	 Pointer to void pointer, where the key pointer is returned.
720  * \param data	 Pointer to void pointer where the data pointer is returned.
721  * \return
722  *	- ANTLR3_SUCCESS if there was a next key
723  *	- ANTLR3_FAIL	 if there were no more keys
724  *
725  * \remark
726  *  No checking of input structure is performed!
727  */
728 static int
antlr3EnumNext(pANTLR3_HASH_ENUM en,pANTLR3_HASH_KEY * key,void ** data)729 antlr3EnumNext	(pANTLR3_HASH_ENUM en, pANTLR3_HASH_KEY * key, void ** data)
730 {
731     /* If the current entry is valid, then use it
732      */
733     if  (en->bucket >= en->table->modulo)
734     {
735         /* Already exhausted the table
736          */
737         return	ANTLR3_FAIL;
738     }
739 
740     /* Pointers are already set to the current entry to return, or
741      * we would not be at this point in the logic flow.
742      */
743     *key	= &(en->entry->keybase);
744     *data	= en->entry->data;
745 
746     /* Return pointers are set up, so now we move the element
747      * pointer to the next in the table (if any).
748      */
749     antlr3EnumNextEntry(en);
750 
751     return	ANTLR3_SUCCESS;
752 }
753 
754 /** \brief Local function to advance the entry pointer of an enumeration
755  * structure to the next valid entry (if there is one).
756  *
757  * \param[in] enum Pointer to ANTLR3 enumeration structure returned by antlr3EnumNew()
758  *
759  * \remark
760  *   - The function always leaves the pointers pointing at a valid entry if there
761  *     is one, so if the entry pointer is NULL when this function exits, there were
762  *     no more entries in the table.
763  */
764 static void
antlr3EnumNextEntry(pANTLR3_HASH_ENUM en)765 antlr3EnumNextEntry(pANTLR3_HASH_ENUM en)
766 {
767     pANTLR3_HASH_BUCKET	bucket;
768 
769     /* See if the current entry pointer is valid first of all
770      */
771     if	(en->entry != NULL)
772     {
773 	/* Current entry was a valid point, see if there is another
774 	 * one in the chain.
775 	 */
776 	if  (en->entry->nextEntry != NULL)
777 	{
778 	    /* Next entry in the enumeration is just the next entry
779 	     * in the chain.
780 	     */
781 	    en->entry = en->entry->nextEntry;
782 	    return;
783 	}
784     }
785 
786     /* There were no more entries in the current bucket, if there are
787      * more buckets then chase them until we find an entry.
788      */
789     en->bucket++;
790 
791     while   (en->bucket < en->table->modulo)
792     {
793 	/* There was one more bucket, see if it has any elements in it
794 	 */
795 	bucket	= en->table->buckets + en->bucket;
796 
797 	if  (bucket->entries != NULL)
798 	{
799 	    /* There was an entry in this bucket, so we can use it
800 	     * for the next entry in the enumeration.
801 	     */
802 	    en->entry	= bucket->entries;
803 	    return;
804 	}
805 
806 	/* There was nothing in the bucket we just examined, move to the
807 	 * next one.
808 	 */
809 	en->bucket++;
810     }
811 
812     /* Here we have exhausted all buckets and the enumeration pointer will
813      * have its bucket count = table->modulo which signifies that we are done.
814      */
815 }
816 
817 /** \brief Frees up the memory structures that represent a hash table
818  *  enumeration.
819  * \param[in] enum Pointer to ANTLR3 enumeration structure returned by antlr3EnumNew()
820  */
821 static void
antlr3EnumFree(pANTLR3_HASH_ENUM en)822 antlr3EnumFree	(pANTLR3_HASH_ENUM en)
823 {
824     /* Nothing to check, we just free it.
825      */
826     ANTLR3_FREE(en);
827 }
828 
829 /** Given an input key of arbitrary length, return a hash value of
830  *  it. This can then be used (with suitable modulo) to index other
831  *  structures.
832  */
833 ANTLR3_API ANTLR3_UINT32
antlr3Hash(void * key,ANTLR3_UINT32 keylen)834 antlr3Hash(void * key, ANTLR3_UINT32 keylen)
835 {
836     /* Accumulate the hash value of the key
837      */
838     ANTLR3_UINT32   hash;
839     pANTLR3_UINT8   keyPtr;
840     ANTLR3_UINT32   i1;
841 
842     hash    = 0;
843     keyPtr  = (pANTLR3_UINT8) key;
844 
845     /* Iterate the key and accumulate the hash
846      */
847     while(keylen > 0)
848     {
849 	hash = (hash << 4) + (*(keyPtr++));
850 
851 	if ((i1=hash&0xf0000000) != 0)
852 	{
853 		hash = hash ^ (i1 >> 24);
854 		hash = hash ^ i1;
855 	}
856 	keylen--;
857     }
858 
859     return  hash;
860 }
861 
862 ANTLR3_API  pANTLR3_LIST
antlr3ListNew(ANTLR3_UINT32 sizeHint)863 antlr3ListNew	(ANTLR3_UINT32 sizeHint)
864 {
865     pANTLR3_LIST    list;
866 
867     /* Allocate memory
868      */
869     list    = (pANTLR3_LIST)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_LIST));
870 
871     if	(list == NULL)
872     {
873 	return	(pANTLR3_LIST)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
874     }
875 
876     /* Now we need to add a new table
877      */
878     list->table	= antlr3HashTableNew(sizeHint);
879 
880     if	(list->table == (pANTLR3_HASH_TABLE)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM))
881     {
882 	return	(pANTLR3_LIST)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
883     }
884 
885     /* Allocation was good, install interface
886      */
887     list->free	    =  antlr3ListFree;
888     list->del	    =  antlr3ListDelete;
889     list->get	    =  antlr3ListGet;
890     list->add	    =  antlr3ListAdd;
891     list->remove    =  antlr3ListRemove;
892     list->put	    =  antlr3ListPut;
893     list->size	    =  antlr3ListSize;
894 
895     return  list;
896 }
897 
antlr3ListSize(pANTLR3_LIST list)898 static ANTLR3_UINT32	antlr3ListSize	    (pANTLR3_LIST list)
899 {
900     return  list->table->size(list->table);
901 }
902 
903 static void
antlr3ListFree(pANTLR3_LIST list)904 antlr3ListFree	(pANTLR3_LIST list)
905 {
906     /* Free the hashtable that stores the list
907      */
908     list->table->free(list->table);
909 
910     /* Free the allocation for the list itself
911      */
912     ANTLR3_FREE(list);
913 }
914 
915 static void
antlr3ListDelete(pANTLR3_LIST list,ANTLR3_INTKEY key)916 antlr3ListDelete    (pANTLR3_LIST list, ANTLR3_INTKEY key)
917 {
918     list->table->delI(list->table, key);
919 }
920 
921 static void *
antlr3ListGet(pANTLR3_LIST list,ANTLR3_INTKEY key)922 antlr3ListGet	    (pANTLR3_LIST list, ANTLR3_INTKEY key)
923 {
924     return list->table->getI(list->table, key);
925 }
926 
927 /** Add the supplied element to the list, at the next available key
928  */
antlr3ListAdd(pANTLR3_LIST list,void * element,void (ANTLR3_CDECL * freeptr)(void *))929 static ANTLR3_INT32	antlr3ListAdd   (pANTLR3_LIST list, void * element, void (ANTLR3_CDECL *freeptr)(void *))
930 {
931     ANTLR3_INTKEY   key;
932 
933     key	    = list->table->size(list->table) + 1;
934     return list->put(list, key, element, freeptr);
935 }
936 
937 /** Remove from the list, but don't free the element, just send it back to the
938  *  caller.
939  */
940 static	void *
antlr3ListRemove(pANTLR3_LIST list,ANTLR3_INTKEY key)941 antlr3ListRemove	    (pANTLR3_LIST list, ANTLR3_INTKEY key)
942 {
943     pANTLR3_HASH_ENTRY	    entry;
944 
945     entry = list->table->removeI(list->table, key);
946 
947     if	(entry != NULL)
948     {
949         return  entry->data;
950     }
951     else
952     {
953 	return	NULL;
954     }
955 }
956 
957 static	ANTLR3_INT32
antlr3ListPut(pANTLR3_LIST list,ANTLR3_INTKEY key,void * element,void (ANTLR3_CDECL * freeptr)(void *))958 antlr3ListPut	    (pANTLR3_LIST list, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *))
959 {
960     return  list->table->putI(list->table, key, element, freeptr);
961 }
962 
963 ANTLR3_API  pANTLR3_STACK
antlr3StackNew(ANTLR3_UINT32 sizeHint)964 antlr3StackNew	(ANTLR3_UINT32 sizeHint)
965 {
966     pANTLR3_STACK   stack;
967 
968     /* Allocate memory
969      */
970     stack    = (pANTLR3_STACK)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_STACK));
971 
972     if	(stack == NULL)
973     {
974 	return	(pANTLR3_STACK)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
975     }
976 
977     /* Now we need to add a new table
978      */
979     stack->vector   = antlr3VectorNew(sizeHint);
980     stack->top	    = NULL;
981 
982     if	(stack->vector == (pANTLR3_VECTOR)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM))
983     {
984 	return	(pANTLR3_STACK)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
985     }
986 
987     /* Looks good, now add the interface
988      */
989     stack->get	=  antlr3StackGet;
990     stack->free	=  antlr3StackFree;
991     stack->pop	=  antlr3StackPop;
992     stack->push	=  antlr3StackPush;
993     stack->size	=  antlr3StackSize;
994     stack->peek	=  antlr3StackPeek;
995 
996     return  stack;
997 }
998 
antlr3StackSize(pANTLR3_STACK stack)999 static ANTLR3_UINT32	antlr3StackSize	    (pANTLR3_STACK stack)
1000 {
1001     return  stack->vector->count;
1002 }
1003 
1004 
1005 static void
antlr3StackFree(pANTLR3_STACK stack)1006 antlr3StackFree	(pANTLR3_STACK  stack)
1007 {
1008     /* Free the list that supports the stack
1009      */
1010     stack->vector->free(stack->vector);
1011     stack->vector   = NULL;
1012     stack->top	    = NULL;
1013 
1014     ANTLR3_FREE(stack);
1015 }
1016 
1017 static void *
antlr3StackPop(pANTLR3_STACK stack)1018 antlr3StackPop	(pANTLR3_STACK	stack)
1019 {
1020     // Delete the element that is currently at the top of the stack
1021     //
1022     stack->vector->del(stack->vector, stack->vector->count - 1);
1023 
1024     // And get the element that is the now the top of the stack (if anything)
1025     // NOTE! This is not quite like a 'real' stack, which would normally return you
1026     // the current top of the stack, then remove it from the stack.
1027     // TODO: Review this, it is correct for follow sets which is what this was done for
1028     //       but is not as obvious when using it as a 'real'stack.
1029     //
1030     stack->top = stack->vector->get(stack->vector, stack->vector->count - 1);
1031     return stack->top;
1032 }
1033 
1034 static void *
antlr3StackGet(pANTLR3_STACK stack,ANTLR3_INTKEY key)1035 antlr3StackGet	(pANTLR3_STACK stack, ANTLR3_INTKEY key)
1036 {
1037     return  stack->vector->get(stack->vector, (ANTLR3_UINT32)key);
1038 }
1039 
1040 static void *
antlr3StackPeek(pANTLR3_STACK stack)1041 antlr3StackPeek	(pANTLR3_STACK	stack)
1042 {
1043     return  stack->top;
1044 }
1045 
1046 static ANTLR3_BOOLEAN
antlr3StackPush(pANTLR3_STACK stack,void * element,void (ANTLR3_CDECL * freeptr)(void *))1047 antlr3StackPush	(pANTLR3_STACK stack, void * element, void (ANTLR3_CDECL *freeptr)(void *))
1048 {
1049     stack->top	= element;
1050     return (ANTLR3_BOOLEAN)(stack->vector->add(stack->vector, element, freeptr));
1051 }
1052 
1053 ANTLR3_API  pANTLR3_VECTOR
antlr3VectorNew(ANTLR3_UINT32 sizeHint)1054 antlr3VectorNew	(ANTLR3_UINT32 sizeHint)
1055 {
1056 	pANTLR3_VECTOR  vector;
1057 
1058 
1059 	// Allocate memory for the vector structure itself
1060 	//
1061 	vector  = (pANTLR3_VECTOR) ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR)));
1062 
1063 	if	(vector == NULL)
1064 	{
1065 		return	(pANTLR3_VECTOR)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
1066 	}
1067 
1068 	// Now fill in the defaults
1069 	//
1070     antlr3SetVectorApi(vector, sizeHint);
1071 
1072 	// And everything is hunky dory
1073 	//
1074 	return  vector;
1075 }
1076 
1077 ANTLR3_API void
antlr3SetVectorApi(pANTLR3_VECTOR vector,ANTLR3_UINT32 sizeHint)1078 antlr3SetVectorApi  (pANTLR3_VECTOR vector, ANTLR3_UINT32 sizeHint)
1079 {
1080     ANTLR3_UINT32   initialSize;
1081 
1082     // Allow vectors to be guessed by ourselves, so input size can be zero
1083     //
1084     if	(sizeHint > ANTLR3_VECTOR_INTERNAL_SIZE)
1085     {
1086         initialSize = sizeHint;
1087     }
1088     else
1089     {
1090         initialSize = ANTLR3_VECTOR_INTERNAL_SIZE;
1091     }
1092 
1093     if  (sizeHint > ANTLR3_VECTOR_INTERNAL_SIZE)
1094     {
1095         vector->elements	= (pANTLR3_VECTOR_ELEMENT)ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR_ELEMENT) * initialSize));
1096     }
1097     else
1098     {
1099         vector->elements    = vector->internal;
1100     }
1101 
1102     if	(vector->elements == NULL)
1103     {
1104         ANTLR3_FREE(vector);
1105         return;
1106     }
1107 
1108     // Memory allocated successfully
1109     //
1110     vector->count			= 0;			// No entries yet of course
1111     vector->elementsSize    = initialSize;  // Available entries
1112 
1113     // Now we can install the API
1114     //
1115     vector->add	    = antlr3VectorAdd;
1116     vector->del	    = antlr3VectorDel;
1117     vector->get	    = antlr3VectorGet;
1118     vector->free    = antlr3VectorFree;
1119     vector->set	    = antlr3VectorSet;
1120     vector->remove  = antrl3VectorRemove;
1121     vector->clear   = antlr3VectorClear;
1122     vector->size    = antlr3VectorSize;
1123     vector->swap    = antlr3VectorSwap;
1124 
1125     // Assume that this is not a factory made vector
1126     //
1127     vector->factoryMade	= ANTLR3_FALSE;
1128 }
1129 
1130 // Clear the entries in a vector.
1131 // Clearing the vector leaves its capacity the same but
1132 // it walks the entries first to see if any of them
1133 // have a free routine that must be called.
1134 //
1135 static	void
antlr3VectorClear(pANTLR3_VECTOR vector)1136 antlr3VectorClear	(pANTLR3_VECTOR vector)
1137 {
1138 	ANTLR3_UINT32   entry;
1139 
1140 	// We must traverse every entry in the vector and if it has
1141 	// a pointer to a free function then we call it with the
1142 	// the entry pointer
1143 	//
1144 	for	(entry = 0; entry < vector->count; entry++)
1145 	{
1146 		if  (vector->elements[entry].freeptr != NULL)
1147 		{
1148 			vector->elements[entry].freeptr(vector->elements[entry].element);
1149 		}
1150 		vector->elements[entry].freeptr    = NULL;
1151 		vector->elements[entry].element    = NULL;
1152 	}
1153 
1154 	// Having called any free pointers, we just reset the entry count
1155 	// back to zero.
1156 	//
1157 	vector->count	= 0;
1158 }
1159 
1160 static
antlr3VectorFree(pANTLR3_VECTOR vector)1161 void	ANTLR3_CDECL	antlr3VectorFree    (pANTLR3_VECTOR vector)
1162 {
1163 	ANTLR3_UINT32   entry;
1164 
1165 	// We must traverse every entry in the vector and if it has
1166 	// a pointer to a free function then we call it with the
1167 	// the entry pointer
1168 	//
1169 	for	(entry = 0; entry < vector->count; entry++)
1170 	{
1171 		if  (vector->elements[entry].freeptr != NULL)
1172 		{
1173 			vector->elements[entry].freeptr(vector->elements[entry].element);
1174 		}
1175 		vector->elements[entry].freeptr    = NULL;
1176 		vector->elements[entry].element    = NULL;
1177 	}
1178 
1179 	if	(vector->factoryMade == ANTLR3_FALSE)
1180 	{
1181 		// The entries are freed, so free the element allocation
1182 		//
1183         if  (vector->elementsSize > ANTLR3_VECTOR_INTERNAL_SIZE)
1184         {
1185             ANTLR3_FREE(vector->elements);
1186         }
1187 		vector->elements = NULL;
1188 
1189 		// Finally, free the allocation for the vector itself
1190 		//
1191 		ANTLR3_FREE(vector);
1192 	}
1193 }
1194 
antlr3VectorDel(pANTLR3_VECTOR vector,ANTLR3_UINT32 entry)1195 static	void		antlr3VectorDel	    (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry)
1196 {
1197 	// Check this is a valid request first
1198 	//
1199 	if	(entry >= vector->count)
1200 	{
1201 		return;
1202 	}
1203 
1204 	// Valid request, check for free pointer and call it if present
1205 	//
1206 	if	(vector->elements[entry].freeptr != NULL)
1207 	{
1208 		vector->elements[entry].freeptr(vector->elements[entry].element);
1209 		vector->elements[entry].freeptr    = NULL;
1210 	}
1211 
1212 	if	(entry == vector->count - 1)
1213 	{
1214 		// Ensure the pointer is never reused by accident, but otherwise just
1215 		// decrement the pointer.
1216 		//
1217 		vector->elements[entry].element    = NULL;
1218 	}
1219 	else
1220 	{
1221 		// Need to shuffle trailing pointers back over the deleted entry
1222 		//
1223 		ANTLR3_MEMMOVE(vector->elements + entry, vector->elements + entry + 1, sizeof(ANTLR3_VECTOR_ELEMENT) * (vector->count - entry - 1));
1224 	}
1225 
1226 	// One less entry in the vector now
1227 	//
1228 	vector->count--;
1229 }
1230 
antlr3VectorGet(pANTLR3_VECTOR vector,ANTLR3_UINT32 entry)1231 static	void *		antlr3VectorGet     (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry)
1232 {
1233 	// Ensure this is a valid request
1234 	//
1235 	if	(entry < vector->count)
1236 	{
1237 		return	vector->elements[entry].element;
1238 	}
1239 	else
1240 	{
1241 		// I know nothing, Mr. Fawlty!
1242 		//
1243 		return	NULL;
1244 	}
1245 }
1246 
1247 /// Remove the entry from the vector, but do not free any entry, even if it has
1248 /// a free pointer.
1249 ///
antrl3VectorRemove(pANTLR3_VECTOR vector,ANTLR3_UINT32 entry)1250 static	void *		antrl3VectorRemove  (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry)
1251 {
1252 	void * element;
1253 
1254 	// Check this is a valid request first
1255 	//
1256 	if	(entry >= vector->count)
1257 	{
1258 		return NULL;
1259 	}
1260 
1261 	// Valid request, return the sorted pointer
1262 	//
1263 
1264 	element				    = vector->elements[entry].element;
1265 
1266 	if	(entry == vector->count - 1)
1267 	{
1268 		// Ensure the pointer is never reused by accident, but otherwise just
1269 		// decrement the pointer.
1270 		///
1271 		vector->elements[entry].element    = NULL;
1272 		vector->elements[entry].freeptr    = NULL;
1273 	}
1274 	else
1275 	{
1276 		// Need to shuffle trailing pointers back over the deleted entry
1277 		//
1278 		ANTLR3_MEMMOVE(vector->elements + entry, vector->elements + entry + 1, sizeof(ANTLR3_VECTOR_ELEMENT) * (vector->count - entry - 1));
1279 	}
1280 
1281 	// One less entry in the vector now
1282 	//
1283 	vector->count--;
1284 
1285 	return  element;
1286 }
1287 
1288 static  void
antlr3VectorResize(pANTLR3_VECTOR vector,ANTLR3_UINT32 hint)1289 antlr3VectorResize  (pANTLR3_VECTOR vector, ANTLR3_UINT32 hint)
1290 {
1291 	ANTLR3_UINT32	newSize;
1292 
1293 	// Need to resize the element pointers. We double the allocation
1294 	// we already have unless asked for a specific increase.
1295     //
1296     if (hint == 0 || hint < vector->elementsSize)
1297     {
1298         newSize = vector->elementsSize * 2;
1299     }
1300     else
1301     {
1302         newSize = hint * 2;
1303     }
1304 
1305     // Now we know how many we need, so we see if we have just expanded
1306     // past the built in vector elements or were already past that
1307     //
1308     if  (vector->elementsSize > ANTLR3_VECTOR_INTERNAL_SIZE)
1309     {
1310         // We were already larger than the internal size, so we just
1311         // use realloc so that the pointers are copied for us
1312         //
1313         vector->elements	= (pANTLR3_VECTOR_ELEMENT)ANTLR3_REALLOC(vector->elements, (sizeof(ANTLR3_VECTOR_ELEMENT)* newSize));
1314     }
1315     else
1316     {
1317         // The current size was less than or equal to the internal array size and as we always start
1318         // with a size that is at least the maximum internal size, then we must need to allocate new memory
1319         // for external pointers. We don't want to take the time to calculate if a requested element
1320         // is part of the internal or external entries, so we copy the internal ones to the new space
1321         //
1322         vector->elements	= (pANTLR3_VECTOR_ELEMENT)ANTLR3_MALLOC((sizeof(ANTLR3_VECTOR_ELEMENT)* newSize));
1323         ANTLR3_MEMCPY(vector->elements, vector->internal, ANTLR3_VECTOR_INTERNAL_SIZE * sizeof(ANTLR3_VECTOR_ELEMENT));
1324     }
1325 
1326 	vector->elementsSize	= newSize;
1327 }
1328 
1329 /// Add the supplied pointer and freeing function pointer to the list,
1330 /// expanding the vector if needed.
1331 ///
antlr3VectorAdd(pANTLR3_VECTOR vector,void * element,void (ANTLR3_CDECL * freeptr)(void *))1332 static	ANTLR3_UINT32    antlr3VectorAdd	    (pANTLR3_VECTOR vector, void * element, void (ANTLR3_CDECL *freeptr)(void *))
1333 {
1334 	// Do we need to resize the vector table?
1335 	//
1336 	if	(vector->count == vector->elementsSize)
1337 	{
1338 		antlr3VectorResize(vector, 0);	    // Give no hint, we let it add 1024 or double it
1339 	}
1340 
1341 	// Insert the new entry
1342 	//
1343 	vector->elements[vector->count].element	= element;
1344 	vector->elements[vector->count].freeptr	= freeptr;
1345 
1346 	vector->count++;	    // One more element counted
1347 
1348 	return  (ANTLR3_UINT32)(vector->count);
1349 
1350 }
1351 
1352 /// Replace the element at the specified entry point with the supplied
1353 /// entry.
1354 ///
1355 static	ANTLR3_UINT32
antlr3VectorSet(pANTLR3_VECTOR vector,ANTLR3_UINT32 entry,void * element,void (ANTLR3_CDECL * freeptr)(void *),ANTLR3_BOOLEAN freeExisting)1356 antlr3VectorSet	    (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry, void * element, void (ANTLR3_CDECL *freeptr)(void *), ANTLR3_BOOLEAN freeExisting)
1357 {
1358 
1359 	// If the vector is currently not big enough, then we expand it
1360 	//
1361 	if (entry >= vector->elementsSize)
1362 	{
1363 		antlr3VectorResize(vector, entry);	// We will get at least this many
1364 	}
1365 
1366 	// Valid request, replace the current one, freeing any prior entry if told to
1367 	//
1368 	if	(		entry < vector->count						// If actually replacing an element
1369 			&&	freeExisting								// And told to free any existing element
1370 			&&	vector->elements[entry].freeptr != NULL		// And the existing element has a free pointer
1371 		)
1372 	{
1373 		vector->elements[entry].freeptr(vector->elements[entry].element);
1374 	}
1375 
1376 	// Install the new pointers
1377 	//
1378 	vector->elements[entry].freeptr	= freeptr;
1379 	vector->elements[entry].element	= element;
1380 
1381 	if (entry >= vector->count)
1382 	{
1383 		vector->count = entry + 1;
1384 	}
1385 	return  (ANTLR3_UINT32)(entry);	    // Indicates the replacement was successful
1386 
1387 }
1388 
1389 /// Replace the element at the specified entry point with the supplied
1390 /// entry.
1391 ///
1392 static	ANTLR3_BOOLEAN
antlr3VectorSwap(pANTLR3_VECTOR vector,ANTLR3_UINT32 entry1,ANTLR3_UINT32 entry2)1393 antlr3VectorSwap	    (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry1, ANTLR3_UINT32 entry2)
1394 {
1395 
1396     void               * tempEntry;
1397     void (ANTLR3_CDECL *freeptr)(void *);
1398 
1399 	// If the vector is currently not big enough, then we do nothing
1400 	//
1401 	if (entry1 >= vector->elementsSize || entry2 >= vector->elementsSize)
1402 	{
1403         return ANTLR3_FALSE;
1404 	}
1405 
1406 	// Valid request, swap them
1407 	//
1408     tempEntry   = vector->elements[entry1].element;
1409     freeptr     = vector->elements[entry1].freeptr;
1410 
1411 	// Install the new pointers
1412 	//
1413     vector->elements[entry1].freeptr	= vector->elements[entry2].freeptr;
1414 	vector->elements[entry1].element	= vector->elements[entry2].element;
1415 
1416 	vector->elements[entry2].freeptr	= freeptr;
1417 	vector->elements[entry2].element	= tempEntry;
1418 
1419 	return  ANTLR3_TRUE;
1420 
1421 }
1422 
antlr3VectorSize(pANTLR3_VECTOR vector)1423 static	ANTLR3_UINT32   antlr3VectorSize    (pANTLR3_VECTOR vector)
1424 {
1425     return  vector->count;
1426 }
1427 
1428 #ifdef ANTLR3_WINDOWS
1429 #pragma warning	(push)
1430 #pragma warning (disable : 4100)
1431 #endif
1432 /// Vector factory creation
1433 ///
1434 ANTLR3_API pANTLR3_VECTOR_FACTORY
antlr3VectorFactoryNew(ANTLR3_UINT32 sizeHint)1435 antlr3VectorFactoryNew	    (ANTLR3_UINT32 sizeHint)
1436 {
1437 	pANTLR3_VECTOR_FACTORY  factory;
1438 
1439 	// Allocate memory for the factory
1440 	//
1441 	factory = (pANTLR3_VECTOR_FACTORY)ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR_FACTORY)));
1442 
1443 	if	(factory == NULL)
1444 	{
1445 		return	NULL;
1446 	}
1447 
1448 	// Factory memory is good, so create a new vector pool
1449 	//
1450     factory->pools      = NULL;
1451     factory->thisPool   = -1;
1452 
1453     newPool(factory);
1454 
1455     // Initialize the API, ignore the hint as this algorithm does
1456     // a better job really.
1457     //
1458     antlr3SetVectorApi(&(factory->unTruc), ANTLR3_VECTOR_INTERNAL_SIZE);
1459 
1460     factory->unTruc.factoryMade = ANTLR3_TRUE;
1461 
1462 	// Install the factory API
1463 	//
1464 	factory->close			= closeVectorFactory;
1465 	factory->newVector		= newVector;
1466 	factory->returnVector	= returnVector;
1467 
1468 	// Create a stack to accumulate reusable vectors
1469 	//
1470 	factory->freeStack		= antlr3StackNew(16);
1471 	return  factory;
1472 }
1473 #ifdef ANTLR3_WINDOWS
1474 #pragma warning	(pop)
1475 #endif
1476 
1477 static	void
returnVector(pANTLR3_VECTOR_FACTORY factory,pANTLR3_VECTOR vector)1478 returnVector		(pANTLR3_VECTOR_FACTORY factory, pANTLR3_VECTOR vector)
1479 {
1480 	// First we need to clear out anything that is still in the vector
1481 	//
1482 	vector->clear(vector);
1483 
1484 	// We have a free stack available so we can add the vector we were
1485 	// given into the free chain. The vector has to have come from this
1486 	// factory, so we already know how to release its memory when it
1487 	// dies by virtue of the factory being closed.
1488 	//
1489 	factory->freeStack->push(factory->freeStack, vector, NULL);
1490 
1491 	// TODO: remove this line once happy printf("Returned vector %08X to the pool, stack size is %d\n", vector, factory->freeStack->size(factory->freeStack));
1492 }
1493 
1494 static void
newPool(pANTLR3_VECTOR_FACTORY factory)1495 newPool(pANTLR3_VECTOR_FACTORY factory)
1496 {
1497     /* Increment factory count
1498      */
1499     factory->thisPool++;
1500 
1501     /* Ensure we have enough pointers allocated
1502      */
1503     factory->pools = (pANTLR3_VECTOR *)
1504 		     ANTLR3_REALLOC(	(void *)factory->pools,	    /* Current pools pointer (starts at NULL)	*/
1505 					(ANTLR3_UINT32)((factory->thisPool + 1) * sizeof(pANTLR3_VECTOR *))	/* Memory for new pool pointers */
1506 					);
1507 
1508     /* Allocate a new pool for the factory
1509      */
1510     factory->pools[factory->thisPool]	=
1511 			    (pANTLR3_VECTOR)
1512 				ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR) * ANTLR3_FACTORY_VPOOL_SIZE));
1513 
1514 
1515     /* Reset the counters
1516      */
1517     factory->nextVector	= 0;
1518 
1519     /* Done
1520      */
1521     return;
1522 }
1523 
1524 static  void
closeVectorFactory(pANTLR3_VECTOR_FACTORY factory)1525 closeVectorFactory  (pANTLR3_VECTOR_FACTORY factory)
1526 {
1527     pANTLR3_VECTOR      pool;
1528     ANTLR3_INT32        poolCount;
1529     ANTLR3_UINT32       limit;
1530     ANTLR3_UINT32       vector;
1531     pANTLR3_VECTOR      check;
1532 
1533 	// First see if we have a free chain stack to release?
1534 	//
1535 	if	(factory->freeStack != NULL)
1536 	{
1537 		factory->freeStack->free(factory->freeStack);
1538 	}
1539 
1540     /* We iterate the vector pools one at a time
1541      */
1542     for (poolCount = 0; poolCount <= factory->thisPool; poolCount++)
1543     {
1544         /* Pointer to current pool
1545          */
1546         pool = factory->pools[poolCount];
1547 
1548         /* Work out how many tokens we need to check in this pool.
1549          */
1550         limit = (poolCount == factory->thisPool ? factory->nextVector : ANTLR3_FACTORY_VPOOL_SIZE);
1551 
1552         /* Marginal condition, we might be at the start of a brand new pool
1553          * where the nextToken is 0 and nothing has been allocated.
1554          */
1555         if (limit > 0)
1556         {
1557             /* We have some vectors allocated from this pool
1558              */
1559             for (vector = 0; vector < limit; vector++)
1560             {
1561                 /* Next one in the chain
1562                  */
1563                 check = pool + vector;
1564 
1565                 // Call the free function on each of the vectors in the pool,
1566                 // which in turn will cause any elements it holds that also have a free
1567                 // pointer to be freed. However, because any vector may be in any other
1568                 // vector, we don't free the element allocations yet. We do that in a
1569                 // a specific pass, coming up next. The vector free function knows that
1570                 // this is a factory allocated pool vector and so it won't free things it
1571                 // should not.
1572                 //
1573                 check->free(check);
1574             }
1575         }
1576     }
1577 
1578     /* We iterate the vector pools one at a time once again, but this time
1579      * we are going to free up any allocated element pointers. Note that we are doing this
1580      * so that we do not try to release vectors twice. When building ASTs we just copy
1581      * the vectors all over the place and they may be embedded in this vector pool
1582      * numerous times.
1583      */
1584     for (poolCount = 0; poolCount <= factory->thisPool; poolCount++)
1585     {
1586         /* Pointer to current pool
1587          */
1588         pool = factory->pools[poolCount];
1589 
1590         /* Work out how many tokens we need to check in this pool.
1591          */
1592         limit = (poolCount == factory->thisPool ? factory->nextVector : ANTLR3_FACTORY_VPOOL_SIZE);
1593 
1594         /* Marginal condition, we might be at the start of a brand new pool
1595          * where the nextToken is 0 and nothing has been allocated.
1596          */
1597         if (limit > 0)
1598         {
1599             /* We have some vectors allocated from this pool
1600              */
1601             for (vector = 0; vector < limit; vector++)
1602             {
1603                 /* Next one in the chain
1604                  */
1605                 check = pool + vector;
1606 
1607                 // Anything in here should be factory made, but we do this just
1608                 // to triple check. We just free up the elements if they were
1609                 // allocated beyond the internal size.
1610                 //
1611                 if (check->factoryMade == ANTLR3_TRUE && check->elementsSize > ANTLR3_VECTOR_INTERNAL_SIZE)
1612                 {
1613                     ANTLR3_FREE(check->elements);
1614                     check->elements = NULL;
1615                 }
1616             }
1617         }
1618 
1619         // We can now free this pool allocation as we have called free on every element in every vector
1620         // and freed any memory for pointers the grew beyond the internal size limit.
1621         //
1622         ANTLR3_FREE(factory->pools[poolCount]);
1623         factory->pools[poolCount] = NULL;
1624     }
1625 
1626     /* All the pools are deallocated we can free the pointers to the pools
1627      * now.
1628      */
1629     ANTLR3_FREE(factory->pools);
1630 
1631     /* Finally, we can free the space for the factory itself
1632      */
1633     ANTLR3_FREE(factory);
1634 
1635 }
1636 
1637 static pANTLR3_VECTOR
newVector(pANTLR3_VECTOR_FACTORY factory)1638 newVector(pANTLR3_VECTOR_FACTORY factory)
1639 {
1640     pANTLR3_VECTOR vector;
1641 
1642 	// If we have anything on the re claim stack, reuse it
1643 	//
1644 	vector = factory->freeStack->peek(factory->freeStack);
1645 
1646 	if  (vector != NULL)
1647 	{
1648 		// Cool we got something we could reuse
1649 		//
1650 		factory->freeStack->pop(factory->freeStack);
1651 
1652 		// TODO: remove this line once happy printf("Reused vector %08X from stack, size is now %d\n", vector, factory->freeStack->size(factory->freeStack));
1653 		return vector;
1654 
1655 	}
1656 
1657 	// See if we need a new vector pool before allocating a new
1658     // one
1659     //
1660     if (factory->nextVector >= ANTLR3_FACTORY_VPOOL_SIZE)
1661     {
1662         // We ran out of vectors in the current pool, so we need a new pool
1663         //
1664         newPool(factory);
1665     }
1666 
1667     // Assuming everything went well (we are trying for performance here so doing minimal
1668     // error checking. Then we can work out what the pointer is to the next vector.
1669     //
1670     vector = factory->pools[factory->thisPool] + factory->nextVector;
1671     factory->nextVector++;
1672 
1673     // We have our token pointer now, so we can initialize it to the predefined model.
1674     //
1675     antlr3SetVectorApi(vector, ANTLR3_VECTOR_INTERNAL_SIZE);
1676     vector->factoryMade = ANTLR3_TRUE;
1677 
1678     // We know that the pool vectors are created at the default size, which means they
1679     // will start off using their internal entry pointers. We must intialize our pool vector
1680     // to point to its own internal entry table and not the pre-made one.
1681     //
1682     vector->elements = vector->internal;
1683 
1684 		// TODO: remove this line once happy printf("Used a new vector at %08X from the pools as nothing on the reusue stack\n", vector);
1685 
1686     // And we are done
1687     //
1688     return vector;
1689 }
1690 
1691 /** Array of left most significant bit positions for an 8 bit
1692  *  element provides an efficient way to find the highest bit
1693  *  that is set in an n byte value (n>0). Assuming the values will all hit the data cache,
1694  *  coding without conditional elements should allow branch
1695  *  prediction to work well and of course a parallel instruction cache
1696  *  will whip through this. Otherwise we must loop shifting a one
1697  *  bit and masking. The values we tend to be placing in out integer
1698  *  patricia trie are usually a lot lower than the 64 bits we
1699  *  allow for the key allows. Hence there is a lot of redundant looping and
1700  *  shifting in a while loop. Whereas, the lookup table is just
1701  *  a few ands and indirect lookups, while testing for 0. This
1702  *  is likely to be done in parallel on many processors available
1703  *  when I wrote this. If this code survives as long as yacc, then
1704  *  I may already be dead by the time you read this and maybe there is
1705  *  a single machine instruction to perform the operation. What
1706  *  else are you going to do with all those transistors? Jim 2007
1707  *
1708  * The table is probably obvious but it is just the number 0..7
1709  * of the MSB in each integer value 0..256
1710  */
1711 static ANTLR3_UINT8 bitIndex[256] =
1712 {
1713     0,													// 0 - Just for padding
1714     0,													// 1
1715     1, 1,												// 2..3
1716     2, 2, 2, 2,											// 4..7
1717     3, 3, 3, 3, 3, 3, 3, 3,								// 8+
1718     4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,	    // 16+
1719     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,	    // 32+
1720 	5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1721     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,	    // 64+
1722 	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
1723 	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
1724 	6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
1725     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,	    // 128+
1726 	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1727 	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1728 	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1729 	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1730 	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1731 	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
1732 	7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
1733 };
1734 
1735 /** Rather than use the bit index of a trie node to shift
1736  *  0x01 left that many times, then & with the result, it is
1737  *  faster to use the bit index as an index into this table
1738  *  which holds precomputed masks for any of the 64 bits
1739  *  we need to mask off singly. The data values will stay in
1740  *  cache while ever a trie is in heavy use, such as in
1741  *  memoization. It is also pretty enough to be ASCII art.
1742  */
1743 static ANTLR3_UINT64 bitMask[64] =
1744 {
1745     0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000004ULL, 0x0000000000000008ULL,
1746     0x0000000000000010ULL, 0x0000000000000020ULL, 0x0000000000000040ULL, 0x0000000000000080ULL,
1747     0x0000000000000100ULL, 0x0000000000000200ULL, 0x0000000000000400ULL, 0x0000000000000800ULL,
1748     0x0000000000001000ULL, 0x0000000000002000ULL, 0x0000000000004000ULL, 0x0000000000008000ULL,
1749     0x0000000000010000ULL, 0x0000000000020000ULL, 0x0000000000040000ULL, 0x0000000000080000ULL,
1750     0x0000000000100000ULL, 0x0000000000200000ULL, 0x0000000000400000ULL, 0x0000000000800000ULL,
1751     0x0000000001000000ULL, 0x0000000002000000ULL, 0x0000000004000000ULL, 0x0000000008000000ULL,
1752     0x0000000010000000ULL, 0x0000000020000000ULL, 0x0000000040000000ULL, 0x0000000080000000ULL,
1753     0x0000000100000000ULL, 0x0000000200000000ULL, 0x0000000400000000ULL, 0x0000000800000000ULL,
1754     0x0000001000000000ULL, 0x0000002000000000ULL, 0x0000004000000000ULL, 0x0000008000000000ULL,
1755     0x0000010000000000ULL, 0x0000020000000000ULL, 0x0000040000000000ULL, 0x0000080000000000ULL,
1756     0x0000100000000000ULL, 0x0000200000000000ULL, 0x0000400000000000ULL, 0x0000800000000000ULL,
1757     0x0001000000000000ULL, 0x0002000000000000ULL, 0x0004000000000000ULL, 0x0008000000000000ULL,
1758     0x0010000000000000ULL, 0x0020000000000000ULL, 0x0040000000000000ULL, 0x0080000000000000ULL,
1759     0x0100000000000000ULL, 0x0200000000000000ULL, 0x0400000000000000ULL, 0x0800000000000000ULL,
1760     0x1000000000000000ULL, 0x2000000000000000ULL, 0x4000000000000000ULL, 0x8000000000000000ULL
1761 };
1762 
1763 /* INT TRIE Implementation of depth 64 bits, being the number of bits
1764  * in a 64 bit integer.
1765  */
1766 
1767 pANTLR3_INT_TRIE
antlr3IntTrieNew(ANTLR3_UINT32 depth)1768 antlr3IntTrieNew(ANTLR3_UINT32 depth)
1769 {
1770 	pANTLR3_INT_TRIE	trie;
1771 
1772 	trie    = (pANTLR3_INT_TRIE) ANTLR3_CALLOC(1, sizeof(ANTLR3_INT_TRIE));	/* Base memory required	*/
1773 
1774 	if (trie == NULL)
1775 	{
1776 		return	(pANTLR3_INT_TRIE) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
1777 	}
1778 
1779 	/* Now we need to allocate the root node. This makes it easier
1780 	 * to use the tree as we don't have to do anything special
1781 	 * for the root node.
1782 	 */
1783 	trie->root	= (pANTLR3_INT_TRIE_NODE) ANTLR3_CALLOC(1, sizeof(ANTLR3_INT_TRIE));
1784 
1785 	if (trie->root == NULL)
1786 	{
1787 		ANTLR3_FREE(trie);
1788 		return	(pANTLR3_INT_TRIE) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
1789 	}
1790 
1791 	trie->add	= intTrieAdd;
1792 	trie->del	= intTrieDel;
1793 	trie->free	= intTrieFree;
1794 	trie->get	= intTrieGet;
1795 
1796 	/* Now we seed the root node with the index being the
1797 	 * highest left most bit we want to test, which limits the
1798 	 * keys in the trie. This is the trie 'depth'. The limit for
1799 	 * this implementation is 63 (bits 0..63).
1800 	 */
1801 	trie->root->bitNum = depth;
1802 
1803 	/* And as we have nothing in here yet, we set both child pointers
1804 	 * of the root node to point back to itself.
1805 	 */
1806 	trie->root->leftN	= trie->root;
1807 	trie->root->rightN	= trie->root;
1808 	trie->count			= 0;
1809 
1810 	/* Finally, note that the key for this root node is 0 because
1811 	 * we use calloc() to initialise it.
1812 	 */
1813 
1814 	return trie;
1815 }
1816 
1817 /** Search the int Trie and return a pointer to the first bucket indexed
1818  *  by the key if it is contained in the trie, otherwise NULL.
1819  */
1820 static	pANTLR3_TRIE_ENTRY
intTrieGet(pANTLR3_INT_TRIE trie,ANTLR3_INTKEY key)1821 intTrieGet	(pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key)
1822 {
1823 	pANTLR3_INT_TRIE_NODE    thisNode;
1824 	pANTLR3_INT_TRIE_NODE    nextNode;
1825 
1826 	if (trie->count == 0)
1827 	{
1828 		return NULL;	    /* Nothing in this trie yet	*/
1829 	}
1830 	/* Starting at the root node in the trie, compare the bit index
1831 	 * of the current node with its next child node (starts left from root).
1832 	 * When the bit index of the child node is greater than the bit index of the current node
1833 	 * then by definition (as the bit index decreases as we descent the trie)
1834 	 * we have reached a 'backward' pointer. A backward pointer means we
1835 	 * have reached the only node that can be reached by the bits given us so far
1836 	 * and it must either be the key we are looking for, or if not then it
1837 	 * means the entry was not in the trie, and we return NULL. A backward pointer
1838 	 * points back in to the tree structure rather than down (deeper) within the
1839 	 * tree branches.
1840 	 */
1841 	thisNode	= trie->root;		/* Start at the root node		*/
1842 	nextNode	= thisNode->leftN;	/* Examine the left node from the root	*/
1843 
1844 	/* While we are descending the tree nodes...
1845 	 */
1846 	while (thisNode->bitNum > nextNode->bitNum)
1847 	{
1848 		/* Next node now becomes the new 'current' node
1849 		 */
1850 		thisNode    = nextNode;
1851 
1852 		/* We now test the bit indicated by the bitmap in the next node
1853 		 * in the key we are searching for. The new next node is the
1854 		 * right node if that bit is set and the left node it is not.
1855 		 */
1856 		if (key & bitMask[nextNode->bitNum])
1857 		{
1858 			nextNode = nextNode->rightN;	/* 1 is right	*/
1859 		}
1860 		else
1861 		{
1862 			nextNode = nextNode->leftN;		/* 0 is left	*/
1863 		}
1864 	}
1865 
1866 	/* Here we have reached a node where the bitMap index is lower than
1867 	 * its parent. This means it is pointing backward in the tree and
1868 	 * must therefore be a terminal node, being the only point than can
1869 	 * be reached with the bits seen so far. It is either the actual key
1870 	 * we wanted, or if that key is not in the trie it is another key
1871 	 * that is currently the only one that can be reached by those bits.
1872 	 * That situation would obviously change if the key was to be added
1873 	 * to the trie.
1874 	 *
1875 	 * Hence it only remains to test whether this is actually the key or not.
1876 	 */
1877 	if (nextNode->key == key)
1878 	{
1879 		/* This was the key, so return the entry pointer
1880 		 */
1881 		return	nextNode->buckets;
1882 	}
1883 	else
1884 	{
1885 		return	NULL;	/* That key is not in the trie (note that we set the pointer to -1 if no payload) */
1886 	}
1887 }
1888 
1889 
1890 static	ANTLR3_BOOLEAN
intTrieDel(pANTLR3_INT_TRIE trie,ANTLR3_INTKEY key)1891 intTrieDel	(pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key)
1892 {
1893     pANTLR3_INT_TRIE_NODE   p;
1894 
1895     p=trie->root;
1896     key = key;
1897 
1898     return ANTLR3_FALSE;
1899 }
1900 
1901 /** Add an entry into the INT trie.
1902  *  Basically we descend the trie as we do when searching it, which will
1903  *  locate the only node in the trie that can be reached by the bit pattern of the
1904  *  key. If the key is actually at that node, then if the trie accepts duplicates
1905  *  we add the supplied data in a new chained bucket to that data node. If it does
1906  *  not accept duplicates then we merely return FALSE in case the caller wants to know
1907  *  whether the key was already in the trie.
1908  *  If the node we locate is not the key we are looking to add, then we insert a new node
1909  *  into the trie with a bit index of the leftmost differing bit and the left or right
1910  *  node pointing to itself or the data node we are inserting 'before'.
1911  */
1912 static	ANTLR3_BOOLEAN
intTrieAdd(pANTLR3_INT_TRIE trie,ANTLR3_INTKEY key,ANTLR3_UINT32 type,ANTLR3_INTKEY intVal,void * data,void (ANTLR3_CDECL * freeptr)(void *))1913 intTrieAdd	(pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key, ANTLR3_UINT32 type, ANTLR3_INTKEY intVal, void * data, void (ANTLR3_CDECL *freeptr)(void *))
1914 {
1915 	pANTLR3_INT_TRIE_NODE   thisNode;
1916 	pANTLR3_INT_TRIE_NODE   nextNode;
1917 	pANTLR3_INT_TRIE_NODE   entNode;
1918 	ANTLR3_UINT32			depth;
1919 	pANTLR3_TRIE_ENTRY	    newEnt;
1920 	pANTLR3_TRIE_ENTRY	    nextEnt;
1921 	ANTLR3_INTKEY		    xorKey;
1922 
1923 	/* Cache the bit depth of this trie, which is always the highest index,
1924 	 * which is in the root node
1925 	 */
1926 	depth   = trie->root->bitNum;
1927 
1928 	thisNode	= trie->root;		/* Start with the root node	    */
1929 	nextNode	= trie->root->leftN;	/* And assume we start to the left  */
1930 
1931 	/* Now find the only node that can be currently reached by the bits in the
1932 	 * key we are being asked to insert.
1933 	 */
1934 	while (thisNode->bitNum  > nextNode->bitNum)
1935 	{
1936 		/* Still descending the structure, next node becomes current.
1937 		 */
1938 		thisNode = nextNode;
1939 
1940 		if (key & bitMask[nextNode->bitNum])
1941 		{
1942 			/* Bit at the required index was 1, so travers the right node from here
1943 			 */
1944 			nextNode = nextNode->rightN;
1945 		}
1946 		else
1947 		{
1948 			/* Bit at the required index was 0, so we traverse to the left
1949 			 */
1950 			nextNode = nextNode->leftN;
1951 		}
1952 	}
1953 	/* Here we have located the only node that can be reached by the
1954 	 * bits in the requested key. It could in fact be that key or the node
1955 	 * we need to use to insert the new key.
1956 	 */
1957 	if (nextNode->key == key)
1958 	{
1959 		/* We have located an exact match, but we will only append to the bucket chain
1960 		 * if this trie accepts duplicate keys.
1961 		 */
1962 		if (trie->allowDups ==ANTLR3_TRUE)
1963 		{
1964 			/* Yes, we are accepting duplicates
1965 			 */
1966 			newEnt = (pANTLR3_TRIE_ENTRY)ANTLR3_CALLOC(1, sizeof(ANTLR3_TRIE_ENTRY));
1967 
1968 			if (newEnt == NULL)
1969 			{
1970 				/* Out of memory, all we can do is return the fact that the insert failed.
1971 				 */
1972 				return	ANTLR3_FALSE;
1973 			}
1974 
1975 			/* Otherwise insert this in the chain
1976 			*/
1977 			newEnt->type	= type;
1978 			newEnt->freeptr	= freeptr;
1979 			if (type == ANTLR3_HASH_TYPE_STR)
1980 			{
1981 				newEnt->data.ptr = data;
1982 			}
1983 			else
1984 			{
1985 				newEnt->data.intVal = intVal;
1986 			}
1987 
1988 			/* We want to be able to traverse the stored elements in the order that they were
1989 			 * added as duplicate keys. We might need to revise this opinion if we end up having many duplicate keys
1990 			 * as perhaps reverse order is just as good, so long as it is ordered.
1991 			 */
1992 			nextEnt = nextNode->buckets;
1993 			while (nextEnt->next != NULL)
1994 			{
1995 				nextEnt = nextEnt->next;
1996 			}
1997 			nextEnt->next = newEnt;
1998 
1999 			trie->count++;
2000 			return  ANTLR3_TRUE;
2001 		}
2002 		else
2003 		{
2004 			/* We found the key is already there and we are not allowed duplicates in this
2005 			 * trie.
2006 			 */
2007 			return  ANTLR3_FALSE;
2008 		}
2009 	}
2010 
2011 	/* Here we have discovered the only node that can be reached by the bits in the key
2012 	 * but we have found that this node is not the key we need to insert. We must find the
2013 	 * the leftmost bit by which the current key for that node and the new key we are going
2014 	 * to insert, differ. While this nested series of ifs may look a bit strange, experimentation
2015 	 * showed that it allows a machine code path that works well with predicated execution
2016 	 */
2017 	xorKey = (key ^ nextNode->key);   /* Gives 1 bits only where they differ then we find the left most 1 bit*/
2018 
2019 	/* Most common case is a 32 bit key really
2020 	 */
2021 #ifdef	ANTLR3_USE_64BIT
2022 	if	(xorKey & 0xFFFFFFFF00000000)
2023 	{
2024 		if  (xorKey & 0xFFFF000000000000)
2025 		{
2026 			if	(xorKey & 0xFF00000000000000)
2027 			{
2028 				depth = 56 + bitIndex[((xorKey & 0xFF00000000000000)>>56)];
2029 			}
2030 			else
2031 			{
2032 				depth = 48 + bitIndex[((xorKey & 0x00FF000000000000)>>48)];
2033 			}
2034 		}
2035 		else
2036 		{
2037 			if	(xorKey & 0x0000FF0000000000)
2038 			{
2039 				depth = 40 + bitIndex[((xorKey & 0x0000FF0000000000)>>40)];
2040 			}
2041 			else
2042 			{
2043 				depth = 32 + bitIndex[((xorKey & 0x000000FF00000000)>>32)];
2044 			}
2045 		}
2046 	}
2047 	else
2048 #endif
2049 	{
2050 		if  (xorKey & 0x00000000FFFF0000)
2051 		{
2052 			if	(xorKey & 0x00000000FF000000)
2053 			{
2054 				depth = 24 + bitIndex[((xorKey & 0x00000000FF000000)>>24)];
2055 			}
2056 			else
2057 			{
2058 				depth = 16 + bitIndex[((xorKey & 0x0000000000FF0000)>>16)];
2059 			}
2060 		}
2061 		else
2062 		{
2063 			if	(xorKey & 0x000000000000FF00)
2064 			{
2065 				depth = 8 + bitIndex[((xorKey & 0x0000000000000FF00)>>8)];
2066 			}
2067 			else
2068 			{
2069 				depth = bitIndex[xorKey & 0x00000000000000FF];
2070 			}
2071 		}
2072 	}
2073 
2074     /* We have located the leftmost differing bit, indicated by the depth variable. So, we know what
2075      * bit index we are to insert the new entry at. There are two cases, being where the two keys
2076      * differ at a bit position that is not currently part of the bit testing, where they differ on a bit
2077      * that is currently being skipped in the indexed comparisons, and where they differ on a bit
2078      * that is merely lower down in the current bit search. If the bit index went bit 4, bit 2 and they differ
2079      * 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
2080      * then we have the easy bit <pun>.
2081      *
2082      * So, set up to descend the tree again, but this time looking for the insert point
2083      * according to whether we skip the bit that differs or not.
2084      */
2085     thisNode	= trie->root;
2086     entNode	= trie->root->leftN;
2087 
2088     /* Note the slight difference in the checks here to cover both cases
2089      */
2090     while (thisNode->bitNum > entNode->bitNum && entNode->bitNum > depth)
2091     {
2092 	/* Still descending the structure, next node becomes current.
2093 	 */
2094 	thisNode = entNode;
2095 
2096 	if (key & bitMask[entNode->bitNum])
2097 	{
2098 	    /* Bit at the required index was 1, so traverse the right node from here
2099 	     */
2100 	    entNode = entNode->rightN;
2101 	}
2102 	else
2103 	{
2104 	    /* Bit at the required index was 0, so we traverse to the left
2105 	     */
2106 	    entNode = entNode->leftN;
2107 	}
2108     }
2109 
2110     /* We have located the correct insert point for this new key, so we need
2111      * to allocate our entry and insert it etc.
2112      */
2113     nextNode	= (pANTLR3_INT_TRIE_NODE)ANTLR3_CALLOC(1, sizeof(ANTLR3_INT_TRIE_NODE));
2114     if (nextNode == NULL)
2115     {
2116 	/* All that work and no memory - bummer.
2117 	 */
2118 	return	ANTLR3_FALSE;
2119     }
2120 
2121     /* Build a new entry block for the new node
2122      */
2123     newEnt = (pANTLR3_TRIE_ENTRY)ANTLR3_CALLOC(1, sizeof(ANTLR3_TRIE_ENTRY));
2124 
2125     if (newEnt == NULL)
2126     {
2127 	/* Out of memory, all we can do is return the fact that the insert failed.
2128 	 */
2129 	return	ANTLR3_FALSE;
2130     }
2131 
2132     /* Otherwise enter this in our new node
2133     */
2134     newEnt->type	= type;
2135     newEnt->freeptr	= freeptr;
2136     if (type == ANTLR3_HASH_TYPE_STR)
2137     {
2138 	newEnt->data.ptr = data;
2139     }
2140     else
2141     {
2142 	newEnt->data.intVal = intVal;
2143     }
2144     /* Install it
2145      */
2146     nextNode->buckets	= newEnt;
2147     nextNode->key	= key;
2148     nextNode->bitNum	= depth;
2149 
2150     /* Work out the right and left pointers for this new node, which involve
2151      * terminating with the current found node either right or left according
2152      * to whether the current index bit is 1 or 0
2153      */
2154     if (key & bitMask[depth])
2155     {
2156 	nextNode->leftN	    = entNode;	    /* Terminates at previous position	*/
2157 	nextNode->rightN    = nextNode;	    /* Terminates with itself		*/
2158     }
2159     else
2160     {
2161 	nextNode->rightN   = entNode;	    /* Terminates at previous position	*/
2162 	nextNode->leftN    = nextNode;	    /* Terminates with itself		*/
2163     }
2164 
2165     /* Finally, we need to change the pointers at the node we located
2166      * for inserting. If the key bit at its index is set then the right
2167      * pointer for that node becomes the newly created node, otherwise the left
2168      * pointer does.
2169      */
2170     if (key & bitMask[thisNode->bitNum] )
2171     {
2172 	thisNode->rightN    = nextNode;
2173     }
2174     else
2175     {
2176 	thisNode->leftN	    = nextNode;
2177     }
2178 
2179     /* Et voila
2180      */
2181     trie->count++;
2182     return  ANTLR3_TRUE;
2183 
2184 }
2185 /** Release memory allocated to this tree.
2186  *  Basic algorithm is that we do a depth first left descent and free
2187  *  up any nodes that are not backward pointers.
2188  */
2189 static void
freeIntNode(pANTLR3_INT_TRIE_NODE node)2190 freeIntNode(pANTLR3_INT_TRIE_NODE node)
2191 {
2192     pANTLR3_TRIE_ENTRY	thisEntry;
2193     pANTLR3_TRIE_ENTRY	nextEntry;
2194 
2195     /* If this node has a left pointer that is not a back pointer
2196      * then recursively call to free this
2197      */
2198     if (node->bitNum > node->leftN->bitNum)
2199     {
2200 	/* We have a left node that needs descending, so do it.
2201 	 */
2202 	freeIntNode(node->leftN);
2203     }
2204 
2205     /* The left nodes from here should now be dealt with, so
2206      * we need to descend any right nodes that are not back pointers
2207      */
2208     if (node->bitNum > node->rightN->bitNum)
2209     {
2210 	/* There are some right nodes to descend and deal with.
2211 	 */
2212 	freeIntNode(node->rightN);
2213     }
2214 
2215     /* Now all the children are dealt with, we can destroy
2216      * this node too
2217      */
2218     thisEntry	= node->buckets;
2219 
2220     while (thisEntry != NULL)
2221     {
2222 	nextEntry   = thisEntry->next;
2223 
2224 	/* Do we need to call a custom free pointer for this string entry?
2225 	 */
2226 	if (thisEntry->type == ANTLR3_HASH_TYPE_STR && thisEntry->freeptr != NULL)
2227 	{
2228 	    thisEntry->freeptr(thisEntry->data.ptr);
2229 	}
2230 
2231 	/* Now free the data for this bucket entry
2232 	 */
2233 	ANTLR3_FREE(thisEntry);
2234 	thisEntry = nextEntry;	    /* See if there are any more to free    */
2235     }
2236 
2237     /* The bucket entry is now gone, so we can free the memory for
2238      * the entry itself.
2239      */
2240     ANTLR3_FREE(node);
2241 
2242     /* And that should be it for everything under this node and itself
2243      */
2244 }
2245 
2246 /** Called to free all nodes and the structure itself.
2247  */
2248 static	void
intTrieFree(pANTLR3_INT_TRIE trie)2249 intTrieFree	(pANTLR3_INT_TRIE trie)
2250 {
2251     /* Descend from the root and free all the nodes
2252      */
2253     freeIntNode(trie->root);
2254 
2255     /* the nodes are all gone now, so we need only free the memory
2256      * for the structure itself
2257      */
2258     ANTLR3_FREE(trie);
2259 }
2260 
2261 
2262 /**
2263  * Allocate and initialize a new ANTLR3 topological sorter, which can be
2264  * used to define edges that identify numerical node indexes that depend on other
2265  * numerical node indexes, which can then be sorted topologically such that
2266  * any node is sorted after all its dependent nodes.
2267  *
2268  * Use:
2269  *
2270  * /verbatim
2271 
2272   pANTLR3_TOPO topo;
2273   topo = antlr3NewTopo();
2274 
2275   if (topo == NULL) { out of memory }
2276 
2277   topo->addEdge(topo, 3, 0); // Node 3 depends on node 0
2278   topo->addEdge(topo, 0, 1); // Node - depends on node 1
2279   topo->sortVector(topo, myVector); // Sort the vector in place (node numbers are the vector entry numbers)
2280 
2281  * /verbatim
2282  */
2283 ANTLR3_API pANTLR3_TOPO
antlr3TopoNew()2284 antlr3TopoNew()
2285 {
2286     pANTLR3_TOPO topo = (pANTLR3_TOPO)ANTLR3_MALLOC(sizeof(ANTLR3_TOPO));
2287 
2288     if  (topo == NULL)
2289     {
2290         return NULL;
2291     }
2292 
2293     // Initialize variables
2294     //
2295 
2296     topo->visited   = NULL;                 // Don't know how big it is yet
2297     topo->limit     = 1;                    // No edges added yet
2298     topo->edges     = NULL;                 // No edges added yet
2299     topo->sorted    = NULL;                 // Nothing sorted at the start
2300     topo->cycle     = NULL;                 // No cycles at the start
2301     topo->cycleMark = 0;                    // No cycles at the start
2302     topo->hasCycle  = ANTLR3_FALSE;         // No cycle at the start
2303 
2304     // API
2305     //
2306     topo->addEdge       = addEdge;
2307     topo->sortToArray   = sortToArray;
2308     topo->sortVector    = sortVector;
2309     topo->free          = freeTopo;
2310 
2311     return topo;
2312 }
2313 // Topological sorter
2314 //
2315 static  void
addEdge(pANTLR3_TOPO topo,ANTLR3_UINT32 edge,ANTLR3_UINT32 dependency)2316 addEdge          (pANTLR3_TOPO topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency)
2317 {
2318     ANTLR3_UINT32   i;
2319     ANTLR3_UINT32   maxEdge;
2320     pANTLR3_BITSET  edgeDeps;
2321 
2322     if (edge>dependency)
2323     {
2324         maxEdge = edge;
2325     }
2326     else
2327     {
2328         maxEdge = dependency;
2329     }
2330     // We need to add an edge to says that the node indexed by 'edge' is
2331     // dependent on the node indexed by 'dependency'
2332     //
2333 
2334     // First see if we have enough room in the edges array to add the edge?
2335     //
2336     if (topo->edges == NULL)
2337     {
2338         // We don't have any edges yet, so create an array to hold them
2339         //
2340         topo->edges = ANTLR3_CALLOC(sizeof(pANTLR3_BITSET) * (maxEdge + 1), 1);
2341         if (topo->edges == NULL)
2342         {
2343             return;
2344         }
2345 
2346         // Set the limit to what we have now
2347         //
2348         topo->limit = maxEdge + 1;
2349     }
2350     else if (topo->limit <= maxEdge)
2351     {
2352         // WE have some edges but not enough
2353         //
2354         topo->edges = ANTLR3_REALLOC(topo->edges, sizeof(pANTLR3_BITSET) * (maxEdge + 1));
2355         if (topo->edges == NULL)
2356         {
2357             return;
2358         }
2359 
2360         // Initialize the new bitmaps to ;indicate we have no edges defined yet
2361         //
2362         for (i = topo->limit; i <= maxEdge; i++)
2363         {
2364             *((topo->edges) + i) = NULL;
2365         }
2366 
2367         // Set the limit to what we have now
2368         //
2369         topo->limit = maxEdge + 1;
2370     }
2371 
2372     // If the edge was flagged as depending on itself, then we just
2373     // do nothing as it means this routine was just called to add it
2374     // in to the list of nodes.
2375     //
2376     if  (edge == dependency)
2377     {
2378         return;
2379     }
2380 
2381     // Pick up the bit map for the requested edge
2382     //
2383     edgeDeps = *((topo->edges) + edge);
2384 
2385     if  (edgeDeps == NULL)
2386     {
2387         // No edges are defined yet for this node
2388         //
2389         edgeDeps                = antlr3BitsetNew(0);
2390         *((topo->edges) + edge) = edgeDeps;
2391         if (edgeDeps == NULL )
2392         {
2393             return;  // Out of memory
2394         }
2395     }
2396 
2397     // Set the bit in the bitmap that corresponds to the requested
2398     // dependency.
2399     //
2400     edgeDeps->add(edgeDeps, dependency);
2401 
2402     // And we are all set
2403     //
2404     return;
2405 }
2406 
2407 
2408 /**
2409  * Given a starting node, descend its dependent nodes (ones that it has edges
2410  * to) until we find one without edges. Having found a node without edges, we have
2411  * discovered the bottom of a depth first search, which we can then ascend, adding
2412  * the nodes in order from the bottom, which gives us the dependency order.
2413  */
2414 static void
DFS(pANTLR3_TOPO topo,ANTLR3_UINT32 node)2415 DFS(pANTLR3_TOPO topo, ANTLR3_UINT32 node)
2416 {
2417     pANTLR3_BITSET edges;
2418 
2419     // Guard against a revisit and check for cycles
2420     //
2421     if  (topo->hasCycle == ANTLR3_TRUE)
2422     {
2423         return; // We don't do anything else if we found a cycle
2424     }
2425 
2426     if  (topo->visited->isMember(topo->visited, node))
2427     {
2428         // Check to see if we found a cycle. To do this we search the
2429         // current cycle stack and see if we find this node already in the stack.
2430         //
2431         ANTLR3_UINT32   i;
2432 
2433         for (i=0; i<topo->cycleMark; i++)
2434         {
2435             if  (topo->cycle[i] == node)
2436             {
2437                 // Stop! We found a cycle in the input, so rejig the cycle
2438                 // stack so that it only contains the cycle and set the cycle flag
2439                 // which will tell the caller what happened
2440                 //
2441                 ANTLR3_UINT32 l;
2442 
2443                 for (l = i; l < topo->cycleMark; l++)
2444                 {
2445                     topo->cycle[l - i] = topo->cycle[l];    // Move to zero base in the cycle list
2446                 }
2447 
2448                 // Recalculate the limit
2449                 //
2450                 topo->cycleMark -= i;
2451 
2452                 // Signal disaster
2453                 //
2454                 topo->hasCycle = ANTLR3_TRUE;
2455             }
2456         }
2457         return;
2458     }
2459 
2460     // So far, no cycles have been found and we have not visited this node yet,
2461     // so this node needs to go into the cycle stack before we continue
2462     // then we will take it out of the stack once we have descended all its
2463     // dependencies.
2464     //
2465     topo->cycle[topo->cycleMark++] = node;
2466 
2467     // First flag that we have visited this node
2468     //
2469     topo->visited->add(topo->visited, node);
2470 
2471     // Now, if this node has edges, then we want to ensure we visit
2472     // them all before we drop through and add this node into the sorted
2473     // list.
2474     //
2475     edges = *((topo->edges) + node);
2476     if  (edges != NULL)
2477     {
2478         // We have some edges, so visit each of the edge nodes
2479         // that have not already been visited.
2480         //
2481         ANTLR3_UINT32   numBits;	    // How many bits are in the set
2482         ANTLR3_UINT32   i;
2483         ANTLR3_UINT32   range;
2484 
2485         numBits = edges->numBits(edges);
2486         range   = edges->size(edges);   // Number of set bits
2487 
2488         // Stop if we exahust the bit list or have checked the
2489         // number of edges that this node refers to (so we don't
2490         // check bits at the end that cannot possibly be set).
2491         //
2492         for (i=0; i<= numBits && range > 0; i++)
2493         {
2494             if  (edges->isMember(edges, i))
2495             {
2496                 range--;        // About to check another one
2497 
2498                 // Found an edge, make sure we visit and descend it
2499                 //
2500                 DFS(topo, i);
2501             }
2502         }
2503     }
2504 
2505     // At this point we will have visited all the dependencies
2506     // of this node and they will be ordered (even if there are cycles)
2507     // So we just add the node into the sorted list at the
2508     // current index position.
2509     //
2510     topo->sorted[topo->limit++] = node;
2511 
2512     // Remove this node from the cycle list if we have not detected a cycle
2513     //
2514     if  (topo->hasCycle == ANTLR3_FALSE)
2515     {
2516         topo->cycleMark--;
2517     }
2518 
2519     return;
2520 }
2521 
2522 static  pANTLR3_UINT32
sortToArray(pANTLR3_TOPO topo)2523 sortToArray      (pANTLR3_TOPO topo)
2524 {
2525     ANTLR3_UINT32 v;
2526     ANTLR3_UINT32 oldLimit;
2527 
2528     // Guard against being called with no edges defined
2529     //
2530     if  (topo->edges == NULL)
2531     {
2532         return 0;
2533     }
2534     // First we need a vector to populate with enough
2535     // entries to accomodate the sorted list and another to accomodate
2536     // the maximum cycle we could detect which is all nodes such as 0->1->2->3->0
2537     //
2538     topo->sorted    = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32));
2539     topo->cycle     = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32));
2540 
2541     // Next we need an empty bitset to show whether we have visited a node
2542     // or not. This is the bit that gives us linear time of course as we are essentially
2543     // dropping through the nodes in depth first order and when we get to a node that
2544     // has no edges, we pop back up the stack adding the nodes we traversed in reverse
2545     // order.
2546     //
2547     topo->visited   = antlr3BitsetNew(0);
2548 
2549     // Now traverse the nodes as if we were just going left to right, but
2550     // then descend each node unless it has already been visited.
2551     //
2552     oldLimit    = topo->limit;     // Number of nodes to traverse linearly
2553     topo->limit = 0;               // Next entry in the sorted table
2554 
2555     for (v = 0; v < oldLimit; v++)
2556     {
2557         // If we did not already visit this node, then descend it until we
2558         // get a node without edges or arrive at a node we have already visited.
2559         //
2560         if  (topo->visited->isMember(topo->visited, v) == ANTLR3_FALSE)
2561         {
2562             // We have not visited this one so descend it
2563             //
2564             DFS(topo, v);
2565         }
2566 
2567         // Break the loop if we detect a cycle as we have no need to go any
2568         // further
2569         //
2570         if  (topo->hasCycle == ANTLR3_TRUE)
2571         {
2572             break;
2573         }
2574     }
2575 
2576     // Reset the limit to the number we recorded as if we hit a
2577     // cycle, then limit will have stopped at the node where we
2578     // discovered the cycle, but in order to free the edge bitmaps
2579     // we need to know how many we may have allocated and traverse them all.
2580     //
2581     topo->limit = oldLimit;
2582 
2583     // Having traversed all the nodes we were given, we
2584     // are guaranteed to have ordered all the nodes or detected a
2585     // cycle.
2586     //
2587     return topo->sorted;
2588 }
2589 
2590 static  void
sortVector(pANTLR3_TOPO topo,pANTLR3_VECTOR v)2591 sortVector       (pANTLR3_TOPO topo, pANTLR3_VECTOR v)
2592 {
2593     // To sort a vector, we first perform the
2594     // sort to an array, then use the results to reorder the vector
2595     // we are given. This is just a convenience routine that allows you to
2596     // sort the children of a tree node into topological order before or
2597     // during an AST walk. This can be useful for optimizations that require
2598     // dag reorders and also when the input stream defines thigns that are
2599     // interdependent and you want to walk the list of the generated trees
2600     // for those things in topological order so you can ignore the interdependencies
2601     // at that point.
2602     //
2603     ANTLR3_UINT32 i;
2604 
2605     // Used as a lookup index to find the current location in the vector of
2606     // the vector entry that was originally at position [0], [1], [2] etc
2607     //
2608     pANTLR3_UINT32  vIndex;
2609 
2610     // Sort into an array, then we can use the array that is
2611     // stored in the topo
2612     //
2613     if  (topo->sortToArray(topo) == 0)
2614     {
2615         return;     // There were no edges
2616     }
2617 
2618     if  (topo->hasCycle == ANTLR3_TRUE)
2619     {
2620         return;  // Do nothing if we detected a cycle
2621     }
2622 
2623     // Ensure that the vector we are sorting is at least as big as the
2624     // the input sequence we were adsked to sort. It does not matter if it is
2625     // bigger as thaat probably just means that nodes numbered higher than the
2626     // limit had no dependencies and so can be left alone.
2627     //
2628     if  (topo->limit > v->count)
2629     {
2630         // We can only sort the entries that we have dude! The caller is
2631         // responsible for ensuring the vector is the correct one and is the
2632         // correct size etc.
2633         //
2634         topo->limit = v->count;
2635     }
2636     // We need to know the locations of each of the entries
2637     // in the vector as we don't want to duplicate them in a new vector. We
2638     // just use an indirection table to get the vector entry for a particular sequence
2639     // acording to where we moved it last. Then we can just swap vector entries until
2640     // we are done :-)
2641     //
2642     vIndex = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32));
2643 
2644     // Start index, each vector entry is located where you think it is
2645     //
2646     for (i = 0; i < topo->limit; i++)
2647     {
2648         vIndex[i] = i;
2649     }
2650 
2651     // Now we traverse the sorted array and moved the entries of
2652     // the vector around according to the sort order and the indirection
2653     // table we just created. The index telsl us where in the vector the
2654     // original element entry n is now located via vIndex[n].
2655     //
2656     for (i=0; i < topo->limit; i++)
2657     {
2658         ANTLR3_UINT32   ind;
2659 
2660         // If the vector entry at i is already the one that it
2661         // should be, then we skip moving it of course.
2662         //
2663         if  (vIndex[topo->sorted[i]] == i)
2664         {
2665             continue;
2666         }
2667 
2668         // The vector entry at i, should be replaced with the
2669         // vector entry indicated by topo->sorted[i]. The vector entry
2670         // at topo->sorted[i] may have already been swapped out though, so we
2671         // find where it is now and move it from there to i.
2672         //
2673         ind     = vIndex[topo->sorted[i]];
2674         v->swap(v, i, ind);
2675 
2676         // Update our index. The element at i is now the one we wanted
2677         // to be sorted here and the element we swapped out is now the
2678         // element that was at i just before we swapped it. If you are lost now
2679         // don't worry about it, we are just reindexing on the fly is all.
2680         //
2681         vIndex[topo->sorted[i]] = i;
2682         vIndex[i] = ind;
2683     }
2684 
2685     // Having traversed all the entries, we have sorted the vector in place.
2686     //
2687     ANTLR3_FREE(vIndex);
2688     return;
2689 }
2690 
2691 static  void
freeTopo(pANTLR3_TOPO topo)2692 freeTopo             (pANTLR3_TOPO topo)
2693 {
2694     ANTLR3_UINT32   i;
2695 
2696     // Free the result vector
2697     //
2698     if  (topo->sorted != NULL)
2699     {
2700         ANTLR3_FREE(topo->sorted);
2701         topo->sorted = NULL;
2702     }
2703 
2704     // Free the visited map
2705     //
2706     if  (topo->visited != NULL)
2707     {
2708 
2709         topo->visited->free(topo->visited);
2710         topo->visited = NULL;
2711     }
2712 
2713     // Free any edgemaps
2714     //
2715     if  (topo->edges != NULL)
2716     {
2717         pANTLR3_BITSET edgeList;
2718 
2719 
2720         for (i=0; i<topo->limit; i++)
2721         {
2722             edgeList = *((topo->edges) + i);
2723             if  (edgeList != NULL)
2724             {
2725                 edgeList->free(edgeList);
2726             }
2727         }
2728 
2729         ANTLR3_FREE(topo->edges);
2730     }
2731     topo->edges = NULL;
2732 
2733     // Free any cycle map
2734     //
2735     if  (topo->cycle != NULL)
2736     {
2737         ANTLR3_FREE(topo->cycle);
2738     }
2739 
2740     ANTLR3_FREE(topo);
2741 }
2742