Bug Summary

File:OMCompiler/Parser/../3rdParty/antlr/3.2/libantlr3c-3.2/src/antlr3collections.c
Warning:line 1925, column 2
Value stored to 'depth' is never read

Annotated Source Code

[?] Use j/k keys for keyboard navigation

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//
47static void antlr3HashDelete (pANTLR3_HASH_TABLE table, void * key);
48static void * antlr3HashGet (pANTLR3_HASH_TABLE table, void * key);
49static pANTLR3_HASH_ENTRY antlr3HashRemove (pANTLR3_HASH_TABLE table, void * key);
50static 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//
54static void antlr3HashDeleteI (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key);
55static void * antlr3HashGetI (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key);
56static pANTLR3_HASH_ENTRY antlr3HashRemoveI (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key);
57static ANTLR3_INT32 antlr3HashPutI (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *));
58
59static void antlr3HashFree (pANTLR3_HASH_TABLE table);
60static ANTLR3_UINT32 antlr3HashSize (pANTLR3_HASH_TABLE table);
61
62// -----------
63
64// Interface functions for enumeration
65//
66static int antlr3EnumNext (pANTLR3_HASH_ENUM en, pANTLR3_HASH_KEY * key, void ** data);
67static void antlr3EnumFree (pANTLR3_HASH_ENUM en);
68
69// Interface functions for List
70//
71static void antlr3ListFree (pANTLR3_LIST list);
72static void antlr3ListDelete(pANTLR3_LIST list, ANTLR3_INTKEY key);
73static void * antlr3ListGet (pANTLR3_LIST list, ANTLR3_INTKEY key);
74static ANTLR3_INT32 antlr3ListPut (pANTLR3_LIST list, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *));
75static ANTLR3_INT32 antlr3ListAdd (pANTLR3_LIST list, void * element, void (ANTLR3_CDECL *freeptr)(void *));
76static void * antlr3ListRemove(pANTLR3_LIST list, ANTLR3_INTKEY key);
77static ANTLR3_UINT32 antlr3ListSize (pANTLR3_LIST list);
78
79// Interface functions for Stack
80//
81static void antlr3StackFree (pANTLR3_STACK stack);
82static void * antlr3StackPop (pANTLR3_STACK stack);
83static void * antlr3StackGet (pANTLR3_STACK stack, ANTLR3_INTKEY key);
84static ANTLR3_BOOLEAN antlr3StackPush (pANTLR3_STACK stack, void * element, void (ANTLR3_CDECL *freeptr)(void *));
85static ANTLR3_UINT32 antlr3StackSize (pANTLR3_STACK stack);
86static void * antlr3StackPeek (pANTLR3_STACK stack);
87
88// Interface functions for vectors
89//
90static void ANTLR3_CDECL antlr3VectorFree (pANTLR3_VECTOR vector);
91static void antlr3VectorDel (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry);
92static void * antlr3VectorGet (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry);
93static void * antrl3VectorRemove (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry);
94static void antlr3VectorClear (pANTLR3_VECTOR vector);
95static ANTLR3_UINT32 antlr3VectorAdd (pANTLR3_VECTOR vector, void * element, void (ANTLR3_CDECL *freeptr)(void *));
96static ANTLR3_UINT32 antlr3VectorSet (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry, void * element, void (ANTLR3_CDECL *freeptr)(void *), ANTLR3_BOOLEAN freeExisting);
97static ANTLR3_UINT32 antlr3VectorSize (pANTLR3_VECTOR vector);
98static ANTLR3_BOOLEAN antlr3VectorSwap (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry1, ANTLR3_UINT32 entry2);
99
100static void newPool (pANTLR3_VECTOR_FACTORY factory);
101static void closeVectorFactory (pANTLR3_VECTOR_FACTORY factory);
102static pANTLR3_VECTOR newVector (pANTLR3_VECTOR_FACTORY factory);
103static void returnVector (pANTLR3_VECTOR_FACTORY factory, pANTLR3_VECTOR vector);
104
105
106// Interface functions for int TRIE
107//
108static pANTLR3_TRIE_ENTRY intTrieGet (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key);
109static ANTLR3_BOOLEAN intTrieDel (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key);
110static ANTLR3_BOOLEAN intTrieAdd (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key, ANTLR3_UINT32 type, ANTLR3_INTKEY intType, void * data, void (ANTLR3_CDECL *freeptr)(void *));
111static void intTrieFree (pANTLR3_INT_TRIE trie);
112
113
114// Interface functions for topological sorter
115//
116static void addEdge (pANTLR3_TOPO topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency);
117static pANTLR3_UINT32 sortToArray (pANTLR3_TOPO topo);
118static void sortVector (pANTLR3_TOPO topo, pANTLR3_VECTOR v);
119static void freeTopo (pANTLR3_TOPO topo);
120
121// Local function to advance enumeration structure pointers
122//
123static void antlr3EnumNextEntry(pANTLR3_HASH_ENUM en);
124
125pANTLR3_HASH_TABLE
126antlr3HashTableNew(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))malloc ((size_t)(sizeof(ANTLR3_HASH_TABLE)));;
136
137 // Error out if no memory left
138 if (table == NULL((void*)0))
139 {
140 return NULL((void*)0);
141 }
142
143 // Allocate memory for the buckets
144 //
145 table->buckets = (pANTLR3_HASH_BUCKET) ANTLR3_MALLOC((size_t) (sizeof(ANTLR3_HASH_BUCKET) * sizeHint))malloc ((size_t)((size_t) (sizeof(ANTLR3_HASH_BUCKET) * sizeHint
)));
;
146
147 if (table->buckets == NULL((void*)0))
148 {
149 ANTLR3_FREE((void *)table)free ((void *)((void *)table));
150 return NULL((void*)0);
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((void*)0);
164 }
165
166 /* Exclude duplicate entries by default
167 */
168 table->allowDups = ANTLR3_FALSE0;
169
170 /* Assume that keys should by strduped before they are
171 * entered in the table.
172 */
173 table->doStrdup = ANTLR3_TRUE1;
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
194static void
195antlr3HashFree(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((void*)0))
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((void*)0))
215 {
216 entry = thisBucket->entries;
217
218 /* Search all entries in the bucket and free them up
219 */
220 while (entry != NULL((void*)0))
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((void*)0))
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_STR1 && entry->keybase.key.sKey != NULL((void*)0))
239 {
240 ANTLR3_FREE(entry->keybase.key.sKey)free ((void *)(entry->keybase.key.sKey));
241 }
242
243 /* Free this entry
244 */
245 ANTLR3_FREE(entry)free ((void *)(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((void*)0);
251 }
252 }
253
254 /* Now we can free the bucket memory
255 */
256 ANTLR3_FREE(table->buckets)free ((void *)(table->buckets));
257 }
258
259 /* Now we free teh memory for the table itself
260 */
261 ANTLR3_FREE(table)free ((void *)(table));
262}
263
264/** return the current size of the hash table
265 */
266static 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 */
274static 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((void*)0))
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((void*)0); /* 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 */
330static pANTLR3_HASH_ENTRY
331antlr3HashRemove(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((void*)0))
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_TRUE1)
370 {
371 ANTLR3_FREE(entry->keybase.key.sKey)free ((void *)(entry->keybase.key.sKey));
372 }
373 entry->keybase.key.sKey = NULL((void*)0);
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((void*)0); /* 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 */
395static void
396antlr3HashDeleteI (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((void*)0) && entry->free != NULL((void*)0))
405 {
406 /* Call programmer supplied function to release this entry data
407 */
408 entry->free(entry->data);
409 entry->data = NULL((void*)0);
410 }
411 /* Finally release the space for this entry block.
412 */
413 ANTLR3_FREE(entry)free ((void *)(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 */
419static void
420antlr3HashDelete (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((void*)0) && entry->free != NULL((void*)0))
429 {
430 /* Call programmer supplied function to release this entry data
431 */
432 entry->free(entry->data);
433 entry->data = NULL((void*)0);
434 }
435 /* Finally release the space for this entry block.
436 */
437 ANTLR3_FREE(entry)free ((void *)(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 */
443static void *
444antlr3HashGetI(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((void*)0))
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((void*)0);
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 */
482static void *
483antlr3HashGet(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((void*)0))
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((void*)0);
517}
518
519/** Add the element pointer in to the table, based upon the
520 * hash of the provided key.
521 */
522static ANTLR3_INT32
523antlr3HashPutI(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((void*)0))
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_FALSE0)
552 {
553 if ((*newPointer)->keybase.key.iKey == key)
554 {
555 return ANTLR3_ERR_HASHDUP(0 + 3);
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))malloc ((size_t)((size_t)sizeof(ANTLR3_HASH_ENTRY)));;
570
571 if (entry == NULL((void*)0))
572 {
573 return ANTLR3_ERR_NOMEM(0 + 1);
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_INT0; /* Indicate the key type stored here for when we free */
579 entry->keybase.key.iKey = key; /* Record the key value */
580 entry->nextEntry = NULL((void*)0); /* 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_SUCCESS0;
587}
588
589
590/** Add the element pointer in to the table, based upon the
591 * hash of the provided key.
592 */
593static ANTLR3_INT32
594antlr3HashPut(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((void*)0))
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_FALSE0)
623 {
624 if (strcmp((const char*) key, (const char *)(*newPointer)->keybase.key.sKey) == 0)
625 {
626 return ANTLR3_ERR_HASHDUP(0 + 3);
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))malloc ((size_t)((size_t)sizeof(ANTLR3_HASH_ENTRY)));;
641
642 if (entry == NULL((void*)0))
643 {
644 return ANTLR3_ERR_NOMEM(0 + 1);
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_STR1; /* Indicate the key type stored here for free() */
650 if (table->doStrdup == ANTLR3_TRUE1)
651 {
652 entry->keybase.key.sKey = ANTLR3_STRDUP(key)(pANTLR3_UINT8)(strdup ((const char *)(key))); /* Record the key value */
653 }
654 else
655 {
656 entry->keybase.key.sKey = key; /* Record the key value */
657 }
658 entry->nextEntry = NULL((void*)0); /* 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_SUCCESS0;
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 */
672pANTLR3_HASH_ENUM
673antlr3EnumNew (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))malloc ((size_t)((size_t)sizeof(ANTLR3_HASH_ENUM)));;
680
681 /* Check that the allocation was good
682 */
683 if (en == NULL((void*)0))
684 {
685 return (pANTLR3_HASH_ENUM) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM)(void *)((ANTLR3_UINT64)((0 + 1)));
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((void*)0))
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 */
728static int
729antlr3EnumNext (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_FAIL1;
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_SUCCESS0;
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 */
764static void
765antlr3EnumNextEntry(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((void*)0))
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((void*)0))
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((void*)0))
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 */
821static void
822antlr3EnumFree (pANTLR3_HASH_ENUM en)
823{
824 /* Nothing to check, we just free it.
825 */
826 ANTLR3_FREE(en)free ((void *)(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 */
833ANTLR3_API ANTLR3_UINT32
834antlr3Hash(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
862ANTLR3_API pANTLR3_LIST
863antlr3ListNew (ANTLR3_UINT32 sizeHint)
864{
865 pANTLR3_LIST list;
866
867 /* Allocate memory
868 */
869 list = (pANTLR3_LIST)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_LIST))malloc ((size_t)((size_t)sizeof(ANTLR3_LIST)));;
870
871 if (list == NULL((void*)0))
872 {
873 return (pANTLR3_LIST)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM)(void *)((ANTLR3_UINT64)((0 + 1)));
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)(void *)((ANTLR3_UINT64)((0 + 1))))
881 {
882 return (pANTLR3_LIST)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM)(void *)((ANTLR3_UINT64)((0 + 1)));
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
898static ANTLR3_UINT32 antlr3ListSize (pANTLR3_LIST list)
899{
900 return list->table->size(list->table);
901}
902
903static void
904antlr3ListFree (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)free ((void *)(list));
913}
914
915static void
916antlr3ListDelete (pANTLR3_LIST list, ANTLR3_INTKEY key)
917{
918 list->table->delI(list->table, key);
919}
920
921static void *
922antlr3ListGet (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 */
929static 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 */
940static void *
941antlr3ListRemove (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((void*)0))
948 {
949 return entry->data;
950 }
951 else
952 {
953 return NULL((void*)0);
954 }
955}
956
957static ANTLR3_INT32
958antlr3ListPut (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
963ANTLR3_API pANTLR3_STACK
964antlr3StackNew (ANTLR3_UINT32 sizeHint)
965{
966 pANTLR3_STACK stack;
967
968 /* Allocate memory
969 */
970 stack = (pANTLR3_STACK)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_STACK))malloc ((size_t)((size_t)sizeof(ANTLR3_STACK)));;
971
972 if (stack == NULL((void*)0))
973 {
974 return (pANTLR3_STACK)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM)(void *)((ANTLR3_UINT64)((0 + 1)));
975 }
976
977 /* Now we need to add a new table
978 */
979 stack->vector = antlr3VectorNew(sizeHint);
980 stack->top = NULL((void*)0);
981
982 if (stack->vector == (pANTLR3_VECTOR)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM)(void *)((ANTLR3_UINT64)((0 + 1))))
983 {
984 return (pANTLR3_STACK)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM)(void *)((ANTLR3_UINT64)((0 + 1)));
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
999static ANTLR3_UINT32 antlr3StackSize (pANTLR3_STACK stack)
1000{
1001 return stack->vector->count;
1002}
1003
1004
1005static void
1006antlr3StackFree (pANTLR3_STACK stack)
1007{
1008 /* Free the list that supports the stack
1009 */
1010 stack->vector->free(stack->vector);
1011 stack->vector = NULL((void*)0);
1012 stack->top = NULL((void*)0);
1013
1014 ANTLR3_FREE(stack)free ((void *)(stack));
1015}
1016
1017static void *
1018antlr3StackPop (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
1034static void *
1035antlr3StackGet (pANTLR3_STACK stack, ANTLR3_INTKEY key)
1036{
1037 return stack->vector->get(stack->vector, (ANTLR3_UINT32)key);
1038}
1039
1040static void *
1041antlr3StackPeek (pANTLR3_STACK stack)
1042{
1043 return stack->top;
1044}
1045
1046static ANTLR3_BOOLEAN
1047antlr3StackPush (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
1053ANTLR3_API pANTLR3_VECTOR
1054antlr3VectorNew (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)))malloc ((size_t)((size_t)(sizeof(ANTLR3_VECTOR))));;
1062
1063 if (vector == NULL((void*)0))
1064 {
1065 return (pANTLR3_VECTOR)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM)(void *)((ANTLR3_UINT64)((0 + 1)));
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
1077ANTLR3_API void
1078antlr3SetVectorApi (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_SIZE16)
1085 {
1086 initialSize = sizeHint;
1087 }
1088 else
1089 {
1090 initialSize = ANTLR3_VECTOR_INTERNAL_SIZE16;
1091 }
1092
1093 if (sizeHint > ANTLR3_VECTOR_INTERNAL_SIZE16)
1094 {
1095 vector->elements = (pANTLR3_VECTOR_ELEMENT)ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR_ELEMENT) * initialSize))malloc ((size_t)((size_t)(sizeof(ANTLR3_VECTOR_ELEMENT) * initialSize
)));
;
1096 }
1097 else
1098 {
1099 vector->elements = vector->internal;
1100 }
1101
1102 if (vector->elements == NULL((void*)0))
1103 {
1104 ANTLR3_FREE(vector)free ((void *)(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_FALSE0;
1128}
1129// Clear the entries in a vector.
1130// Clearing the vector leaves its capacity the same but
1131// it walks the entries first to see if any of them
1132// have a free routine that must be called.
1133//
1134static void
1135antlr3VectorClear (pANTLR3_VECTOR vector)
1136{
1137 ANTLR3_UINT32 entry;
1138
1139 // We must traverse every entry in the vector and if it has
1140 // a pointer to a free function then we call it with the
1141 // the entry pointer
1142 //
1143 for (entry = 0; entry < vector->count; entry++)
1144 {
1145 if (vector->elements[entry].freeptr != NULL((void*)0))
1146 {
1147 vector->elements[entry].freeptr(vector->elements[entry].element);
1148 }
1149 vector->elements[entry].freeptr = NULL((void*)0);
1150 vector->elements[entry].element = NULL((void*)0);
1151 }
1152
1153 // Having called any free pointers, we just reset the entry count
1154 // back to zero.
1155 //
1156 vector->count = 0;
1157}
1158
1159static
1160void ANTLR3_CDECL antlr3VectorFree (pANTLR3_VECTOR vector)
1161{
1162 ANTLR3_UINT32 entry;
1163
1164 // We must traverse every entry in the vector and if it has
1165 // a pointer to a free function then we call it with the
1166 // the entry pointer
1167 //
1168 for (entry = 0; entry < vector->count; entry++)
1169 {
1170 if (vector->elements[entry].freeptr != NULL((void*)0))
1171 {
1172 vector->elements[entry].freeptr(vector->elements[entry].element);
1173 }
1174 vector->elements[entry].freeptr = NULL((void*)0);
1175 vector->elements[entry].element = NULL((void*)0);
1176 }
1177
1178 if (vector->factoryMade == ANTLR3_FALSE0)
1179 {
1180 // The entries are freed, so free the element allocation
1181 //
1182 if (vector->elementsSize > ANTLR3_VECTOR_INTERNAL_SIZE16)
1183 {
1184 ANTLR3_FREE(vector->elements)free ((void *)(vector->elements));
1185 }
1186 vector->elements = NULL((void*)0);
1187
1188 // Finally, free the allocation for the vector itself
1189 //
1190 ANTLR3_FREE(vector)free ((void *)(vector));
1191 }
1192}
1193
1194static void antlr3VectorDel (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry)
1195{
1196 // Check this is a valid request first
1197 //
1198 if (entry >= vector->count)
1199 {
1200 return;
1201 }
1202
1203 // Valid request, check for free pointer and call it if present
1204 //
1205 if (vector->elements[entry].freeptr != NULL((void*)0))
1206 {
1207 vector->elements[entry].freeptr(vector->elements[entry].element);
1208 vector->elements[entry].freeptr = NULL((void*)0);
1209 }
1210
1211 if (entry == vector->count - 1)
1212 {
1213 // Ensure the pointer is never reused by accident, but otherwise just
1214 // decrement the pointer.
1215 //
1216 vector->elements[entry].element = NULL((void*)0);
1217 }
1218 else
1219 {
1220 // Need to shuffle trailing pointers back over the deleted entry
1221 //
1222 ANTLR3_MEMMOVE(vector->elements + entry, vector->elements + entry + 1, sizeof(ANTLR3_VECTOR_ELEMENT) * (vector->count - entry - 1))memmove((void *)(vector->elements + entry), (const void *)
(vector->elements + entry + 1), (size_t)(sizeof(ANTLR3_VECTOR_ELEMENT
) * (vector->count - entry - 1)))
;
1223 }
1224
1225 // One less entry in the vector now
1226 //
1227 vector->count--;
1228}
1229
1230static void * antlr3VectorGet (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry)
1231{
1232 // Ensure this is a valid request
1233 //
1234 if (entry < vector->count)
1235 {
1236 return vector->elements[entry].element;
1237 }
1238 else
1239 {
1240 // I know nothing, Mr. Fawlty!
1241 //
1242 return NULL((void*)0);
1243 }
1244}
1245
1246/// Remove the entry from the vector, but do not free any entry, even if it has
1247/// a free pointer.
1248///
1249static void * antrl3VectorRemove (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry)
1250{
1251 void * element;
1252
1253 // Check this is a valid request first
1254 //
1255 if (entry >= vector->count)
1256 {
1257 return NULL((void*)0);
1258 }
1259
1260 // Valid request, return the sorted pointer
1261 //
1262
1263 element = vector->elements[entry].element;
1264
1265 if (entry == vector->count - 1)
1266 {
1267 // Ensure the pointer is never reused by accident, but otherwise just
1268 // decrement the pointer.
1269 ///
1270 vector->elements[entry].element = NULL((void*)0);
1271 vector->elements[entry].freeptr = NULL((void*)0);
1272 }
1273 else
1274 {
1275 // Need to shuffle trailing pointers back over the deleted entry
1276 //
1277 ANTLR3_MEMMOVE(vector->elements + entry, vector->elements + entry + 1, sizeof(ANTLR3_VECTOR_ELEMENT) * (vector->count - entry - 1))memmove((void *)(vector->elements + entry), (const void *)
(vector->elements + entry + 1), (size_t)(sizeof(ANTLR3_VECTOR_ELEMENT
) * (vector->count - entry - 1)))
;
1278 }
1279
1280 // One less entry in the vector now
1281 //
1282 vector->count--;
1283
1284 return element;
1285}
1286
1287static void
1288antlr3VectorResize (pANTLR3_VECTOR vector, ANTLR3_UINT32 hint)
1289{
1290 ANTLR3_UINT32 newSize;
1291
1292 // Need to resize the element pointers. We double the allocation
1293 // we already have unless asked for a specific increase.
1294 //
1295 if (hint == 0 || hint < vector->elementsSize)
1296 {
1297 newSize = vector->elementsSize * 2;
1298 }
1299 else
1300 {
1301 newSize = hint * 2;
1302 }
1303
1304 // Now we know how many we need, so we see if we have just expanded
1305 // past the built in vector elements or were already past that
1306 //
1307 if (vector->elementsSize > ANTLR3_VECTOR_INTERNAL_SIZE16)
1308 {
1309 // We were already larger than the internal size, so we just
1310 // use realloc so that the pointers are copied for us
1311 //
1312 vector->elements = (pANTLR3_VECTOR_ELEMENT)ANTLR3_REALLOC(vector->elements, (sizeof(ANTLR3_VECTOR_ELEMENT)* newSize))realloc ((void *)(vector->elements), (size_t)((sizeof(ANTLR3_VECTOR_ELEMENT
)* newSize)));
;
1313 }
1314 else
1315 {
1316 // The current size was less than or equal to the internal array size and as we always start
1317 // with a size that is at least the maximum internal size, then we must need to allocate new memory
1318 // for external pointers. We don't want to take the time to calculate if a requested element
1319 // is part of the internal or external entries, so we copy the internal ones to the new space
1320 //
1321 vector->elements = (pANTLR3_VECTOR_ELEMENT)ANTLR3_MALLOC((sizeof(ANTLR3_VECTOR_ELEMENT)* newSize))malloc ((size_t)((sizeof(ANTLR3_VECTOR_ELEMENT)* newSize)));;
1322 ANTLR3_MEMCPY(vector->elements, vector->internal, ANTLR3_VECTOR_INTERNAL_SIZE * sizeof(ANTLR3_VECTOR_ELEMENT))memcpy((void *)(vector->elements), (const void *)(vector->
internal), (size_t)(16 * sizeof(ANTLR3_VECTOR_ELEMENT)))
;
1323 }
1324
1325 vector->elementsSize = newSize;
1326}
1327
1328/// Add the supplied pointer and freeing function pointer to the list,
1329/// expanding the vector if needed.
1330///
1331static ANTLR3_UINT32 antlr3VectorAdd (pANTLR3_VECTOR vector, void * element, void (ANTLR3_CDECL *freeptr)(void *))
1332{
1333 // Do we need to resize the vector table?
1334 //
1335 if (vector->count == vector->elementsSize)
1336 {
1337 antlr3VectorResize(vector, 0); // Give no hint, we let it add 1024 or double it
1338 }
1339
1340 // Insert the new entry
1341 //
1342 vector->elements[vector->count].element = element;
1343 vector->elements[vector->count].freeptr = freeptr;
1344
1345 vector->count++; // One more element counted
1346
1347 return (ANTLR3_UINT32)(vector->count);
1348
1349}
1350
1351/// Replace the element at the specified entry point with the supplied
1352/// entry.
1353///
1354static ANTLR3_UINT32
1355antlr3VectorSet (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry, void * element, void (ANTLR3_CDECL *freeptr)(void *), ANTLR3_BOOLEAN freeExisting)
1356{
1357
1358 // If the vector is currently not big enough, then we expand it
1359 //
1360 if (entry >= vector->elementsSize)
1361 {
1362 antlr3VectorResize(vector, entry); // We will get at least this many
1363 }
1364
1365 // Valid request, replace the current one, freeing any prior entry if told to
1366 //
1367 if ( entry < vector->count // If actually replacing an element
1368 && freeExisting // And told to free any existing element
1369 && vector->elements[entry].freeptr != NULL((void*)0) // And the existing element has a free pointer
1370 )
1371 {
1372 vector->elements[entry].freeptr(vector->elements[entry].element);
1373 }
1374
1375 // Install the new pointers
1376 //
1377 vector->elements[entry].freeptr = freeptr;
1378 vector->elements[entry].element = element;
1379
1380 if (entry >= vector->count)
1381 {
1382 vector->count = entry + 1;
1383 }
1384 return (ANTLR3_UINT32)(entry); // Indicates the replacement was successful
1385
1386}
1387
1388/// Replace the element at the specified entry point with the supplied
1389/// entry.
1390///
1391static ANTLR3_BOOLEAN
1392antlr3VectorSwap (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry1, ANTLR3_UINT32 entry2)
1393{
1394
1395 void * tempEntry;
1396 void (ANTLR3_CDECL *freeptr)(void *);
1397
1398 // If the vector is currently not big enough, then we do nothing
1399 //
1400 if (entry1 >= vector->elementsSize || entry2 >= vector->elementsSize)
1401 {
1402 return ANTLR3_FALSE0;
1403 }
1404
1405 // Valid request, swap them
1406 //
1407 tempEntry = vector->elements[entry1].element;
1408 freeptr = vector->elements[entry1].freeptr;
1409
1410 // Install the new pointers
1411 //
1412 vector->elements[entry1].freeptr = vector->elements[entry2].freeptr;
1413 vector->elements[entry1].element = vector->elements[entry2].element;
1414
1415 vector->elements[entry2].freeptr = freeptr;
1416 vector->elements[entry2].element = tempEntry;
1417
1418 return ANTLR3_TRUE1;
1419
1420}
1421
1422static ANTLR3_UINT32 antlr3VectorSize (pANTLR3_VECTOR vector)
1423{
1424 return vector->count;
1425}
1426
1427#ifdef ANTLR3_WINDOWS
1428#pragma warning (push)
1429#pragma warning (disable : 4100)
1430#endif
1431/// Vector factory creation
1432///
1433ANTLR3_API pANTLR3_VECTOR_FACTORY
1434antlr3VectorFactoryNew (ANTLR3_UINT32 sizeHint)
1435{
1436 pANTLR3_VECTOR_FACTORY factory;
1437
1438 // Allocate memory for the factory
1439 //
1440 factory = (pANTLR3_VECTOR_FACTORY)ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR_FACTORY)))malloc ((size_t)((size_t)(sizeof(ANTLR3_VECTOR_FACTORY))));;
1441
1442 if (factory == NULL((void*)0))
1443 {
1444 return NULL((void*)0);
1445 }
1446
1447 // Factory memory is good, so create a new vector pool
1448 //
1449 factory->pools = NULL((void*)0);
1450 factory->thisPool = -1;
1451
1452 newPool(factory);
1453
1454 // Initialize the API, ignore the hint as this algorithm does
1455 // a better job really.
1456 //
1457 antlr3SetVectorApi(&(factory->unTruc), ANTLR3_VECTOR_INTERNAL_SIZE16);
1458
1459 factory->unTruc.factoryMade = ANTLR3_TRUE1;
1460
1461 // Install the factory API
1462 //
1463 factory->close = closeVectorFactory;
1464 factory->newVector = newVector;
1465 factory->returnVector = returnVector;
1466
1467 // Create a stack to accumulate reusable vectors
1468 //
1469 factory->freeStack = antlr3StackNew(16);
1470 return factory;
1471}
1472#ifdef ANTLR3_WINDOWS
1473#pragma warning (pop)
1474#endif
1475
1476static void
1477returnVector (pANTLR3_VECTOR_FACTORY factory, pANTLR3_VECTOR vector)
1478{
1479 // First we need to clear out anything that is still in the vector
1480 //
1481 vector->clear(vector);
1482
1483 // We have a free stack available so we can add the vector we were
1484 // given into the free chain. The vector has to have come from this
1485 // factory, so we already know how to release its memory when it
1486 // dies by virtue of the factory being closed.
1487 //
1488 factory->freeStack->push(factory->freeStack, vector, NULL((void*)0));
1489
1490 // TODO: remove this line once happy printf("Returned vector %08X to the pool, stack size is %d\n", vector, factory->freeStack->size(factory->freeStack));
1491}
1492
1493static void
1494newPool(pANTLR3_VECTOR_FACTORY factory)
1495{
1496 /* Increment factory count
1497 */
1498 factory->thisPool++;
1499
1500 /* Ensure we have enough pointers allocated
1501 */
1502 factory->pools = (pANTLR3_VECTOR *)
1503 ANTLR3_REALLOC( (void *)factory->pools, /* Current pools pointer (starts at NULL) */realloc ((void *)((void *)factory->pools), (size_t)((ANTLR3_UINT32
)((factory->thisPool + 1) * sizeof(pANTLR3_VECTOR *))));
1504 (ANTLR3_UINT32)((factory->thisPool + 1) * sizeof(pANTLR3_VECTOR *)) /* Memory for new pool pointers */realloc ((void *)((void *)factory->pools), (size_t)((ANTLR3_UINT32
)((factory->thisPool + 1) * sizeof(pANTLR3_VECTOR *))));
1505 )realloc ((void *)((void *)factory->pools), (size_t)((ANTLR3_UINT32
)((factory->thisPool + 1) * sizeof(pANTLR3_VECTOR *))));
;
1506
1507 /* Allocate a new pool for the factory
1508 */
1509 factory->pools[factory->thisPool] =
1510 (pANTLR3_VECTOR)
1511 ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR) * ANTLR3_FACTORY_VPOOL_SIZE))malloc ((size_t)((size_t)(sizeof(ANTLR3_VECTOR) * 256)));;
1512
1513
1514 /* Reset the counters
1515 */
1516 factory->nextVector = 0;
1517
1518 /* Done
1519 */
1520 return;
1521}
1522
1523static void
1524closeVectorFactory (pANTLR3_VECTOR_FACTORY factory)
1525{
1526 pANTLR3_VECTOR pool;
1527 ANTLR3_INT32 poolCount;
1528 ANTLR3_UINT32 limit;
1529 ANTLR3_UINT32 vector;
1530 pANTLR3_VECTOR check;
1531
1532 // First see if we have a free chain stack to release?
1533 //
1534 if (factory->freeStack != NULL((void*)0))
1535 {
1536 factory->freeStack->free(factory->freeStack);
1537 }
1538
1539 /* We iterate the vector pools one at a time
1540 */
1541 for (poolCount = 0; poolCount <= factory->thisPool; poolCount++)
1542 {
1543 /* Pointer to current pool
1544 */
1545 pool = factory->pools[poolCount];
1546
1547 /* Work out how many tokens we need to check in this pool.
1548 */
1549 limit = (poolCount == factory->thisPool ? factory->nextVector : ANTLR3_FACTORY_VPOOL_SIZE256);
1550
1551 /* Marginal condition, we might be at the start of a brand new pool
1552 * where the nextToken is 0 and nothing has been allocated.
1553 */
1554 if (limit > 0)
1555 {
1556 /* We have some vectors allocated from this pool
1557 */
1558 for (vector = 0; vector < limit; vector++)
1559 {
1560 /* Next one in the chain
1561 */
1562 check = pool + vector;
1563
1564 // Call the free function on each of the vectors in the pool,
1565 // which in turn will cause any elements it holds that also have a free
1566 // pointer to be freed. However, because any vector may be in any other
1567 // vector, we don't free the element allocations yet. We do that in a
1568 // a specific pass, coming up next. The vector free function knows that
1569 // this is a factory allocated pool vector and so it won't free things it
1570 // should not.
1571 //
1572 check->free(check);
1573 }
1574 }
1575 }
1576
1577 /* We iterate the vector pools one at a time once again, but this time
1578 * we are going to free up any allocated element pointers. Note that we are doing this
1579 * so that we do not try to release vectors twice. When building ASTs we just copy
1580 * the vectors all over the place and they may be embedded in this vector pool
1581 * numerous times.
1582 */
1583 for (poolCount = 0; poolCount <= factory->thisPool; poolCount++)
1584 {
1585 /* Pointer to current pool
1586 */
1587 pool = factory->pools[poolCount];
1588
1589 /* Work out how many tokens we need to check in this pool.
1590 */
1591 limit = (poolCount == factory->thisPool ? factory->nextVector : ANTLR3_FACTORY_VPOOL_SIZE256);
1592
1593 /* Marginal condition, we might be at the start of a brand new pool
1594 * where the nextToken is 0 and nothing has been allocated.
1595 */
1596 if (limit > 0)
1597 {
1598 /* We have some vectors allocated from this pool
1599 */
1600 for (vector = 0; vector < limit; vector++)
1601 {
1602 /* Next one in the chain
1603 */
1604 check = pool + vector;
1605
1606 // Anything in here should be factory made, but we do this just
1607 // to triple check. We just free up the elements if they were
1608 // allocated beyond the internal size.
1609 //
1610 if (check->factoryMade == ANTLR3_TRUE1 && check->elementsSize > ANTLR3_VECTOR_INTERNAL_SIZE16)
1611 {
1612 ANTLR3_FREE(check->elements)free ((void *)(check->elements));
1613 check->elements = NULL((void*)0);
1614 }
1615 }
1616 }
1617
1618 // We can now free this pool allocation as we have called free on every element in every vector
1619 // and freed any memory for pointers the grew beyond the internal size limit.
1620 //
1621 ANTLR3_FREE(factory->pools[poolCount])free ((void *)(factory->pools[poolCount]));
1622 factory->pools[poolCount] = NULL((void*)0);
1623 }
1624
1625 /* All the pools are deallocated we can free the pointers to the pools
1626 * now.
1627 */
1628 ANTLR3_FREE(factory->pools)free ((void *)(factory->pools));
1629
1630 /* Finally, we can free the space for the factory itself
1631 */
1632 ANTLR3_FREE(factory)free ((void *)(factory));
1633
1634}
1635
1636static pANTLR3_VECTOR
1637newVector(pANTLR3_VECTOR_FACTORY factory)
1638{
1639 pANTLR3_VECTOR vector;
1640
1641 // If we have anything on the re claim stack, reuse it
1642 //
1643 vector = factory->freeStack->peek(factory->freeStack);
1644
1645 if (vector != NULL((void*)0))
1646 {
1647 // Cool we got something we could reuse
1648 //
1649 factory->freeStack->pop(factory->freeStack);
1650
1651 // TODO: remove this line once happy printf("Reused vector %08X from stack, size is now %d\n", vector, factory->freeStack->size(factory->freeStack));
1652 return vector;
1653
1654 }
1655
1656 // See if we need a new vector pool before allocating a new
1657 // one
1658 //
1659 if (factory->nextVector >= ANTLR3_FACTORY_VPOOL_SIZE256)
1660 {
1661 // We ran out of vectors in the current pool, so we need a new pool
1662 //
1663 newPool(factory);
1664 }
1665
1666 // Assuming everything went well (we are trying for performance here so doing minimal
1667 // error checking. Then we can work out what the pointer is to the next vector.
1668 //
1669 vector = factory->pools[factory->thisPool] + factory->nextVector;
1670 factory->nextVector++;
1671
1672 // We have our token pointer now, so we can initialize it to the predefined model.
1673 //
1674 antlr3SetVectorApi(vector, ANTLR3_VECTOR_INTERNAL_SIZE16);
1675 vector->factoryMade = ANTLR3_TRUE1;
1676
1677 // We know that the pool vectors are created at the default size, which means they
1678 // will start off using their internal entry pointers. We must intialize our pool vector
1679 // to point to its own internal entry table and not the pre-made one.
1680 //
1681 vector->elements = vector->internal;
1682
1683 // TODO: remove this line once happy printf("Used a new vector at %08X from the pools as nothing on the reusue stack\n", vector);
1684
1685 // And we are done
1686 //
1687 return vector;
1688}
1689
1690/** Array of left most significant bit positions for an 8 bit
1691 * element provides an efficient way to find the highest bit
1692 * that is set in an n byte value (n>0). Assuming the values will all hit the data cache,
1693 * coding without conditional elements should allow branch
1694 * prediction to work well and of course a parallel instruction cache
1695 * will whip through this. Otherwise we must loop shifting a one
1696 * bit and masking. The values we tend to be placing in out integer
1697 * patricia trie are usually a lot lower than the 64 bits we
1698 * allow for the key allows. Hence there is a lot of redundant looping and
1699 * shifting in a while loop. Whereas, the lookup table is just
1700 * a few ands and indirect lookups, while testing for 0. This
1701 * is likely to be done in parallel on many processors available
1702 * when I wrote this. If this code survives as long as yacc, then
1703 * I may already be dead by the time you read this and maybe there is
1704 * a single machine instruction to perform the operation. What
1705 * else are you going to do with all those transistors? Jim 2007
1706 *
1707 * The table is probably obvious but it is just the number 0..7
1708 * of the MSB in each integer value 0..256
1709 */
1710static ANTLR3_UINT8 bitIndex[256] =
1711{
1712 0, // 0 - Just for padding
1713 0, // 1
1714 1, 1, // 2..3
1715 2, 2, 2, 2, // 4..7
1716 3, 3, 3, 3, 3, 3, 3, 3, // 8+
1717 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, // 16+
1718 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, // 32+
1719 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1720 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, // 64+
1721 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
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 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 128+
1725 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
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};
1733
1734/** Rather than use the bit index of a trie node to shift
1735 * 0x01 left that many times, then & with the result, it is
1736 * faster to use the bit index as an index into this table
1737 * which holds precomputed masks for any of the 64 bits
1738 * we need to mask off singly. The data values will stay in
1739 * cache while ever a trie is in heavy use, such as in
1740 * memoization. It is also pretty enough to be ASCII art.
1741 */
1742static ANTLR3_UINT64 bitMask[64] =
1743{
1744 0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000004ULL, 0x0000000000000008ULL,
1745 0x0000000000000010ULL, 0x0000000000000020ULL, 0x0000000000000040ULL, 0x0000000000000080ULL,
1746 0x0000000000000100ULL, 0x0000000000000200ULL, 0x0000000000000400ULL, 0x0000000000000800ULL,
1747 0x0000000000001000ULL, 0x0000000000002000ULL, 0x0000000000004000ULL, 0x0000000000008000ULL,
1748 0x0000000000010000ULL, 0x0000000000020000ULL, 0x0000000000040000ULL, 0x0000000000080000ULL,
1749 0x0000000000100000ULL, 0x0000000000200000ULL, 0x0000000000400000ULL, 0x0000000000800000ULL,
1750 0x0000000001000000ULL, 0x0000000002000000ULL, 0x0000000004000000ULL, 0x0000000008000000ULL,
1751 0x0000000010000000ULL, 0x0000000020000000ULL, 0x0000000040000000ULL, 0x0000000080000000ULL,
1752 0x0000000100000000ULL, 0x0000000200000000ULL, 0x0000000400000000ULL, 0x0000000800000000ULL,
1753 0x0000001000000000ULL, 0x0000002000000000ULL, 0x0000004000000000ULL, 0x0000008000000000ULL,
1754 0x0000010000000000ULL, 0x0000020000000000ULL, 0x0000040000000000ULL, 0x0000080000000000ULL,
1755 0x0000100000000000ULL, 0x0000200000000000ULL, 0x0000400000000000ULL, 0x0000800000000000ULL,
1756 0x0001000000000000ULL, 0x0002000000000000ULL, 0x0004000000000000ULL, 0x0008000000000000ULL,
1757 0x0010000000000000ULL, 0x0020000000000000ULL, 0x0040000000000000ULL, 0x0080000000000000ULL,
1758 0x0100000000000000ULL, 0x0200000000000000ULL, 0x0400000000000000ULL, 0x0800000000000000ULL,
1759 0x1000000000000000ULL, 0x2000000000000000ULL, 0x4000000000000000ULL, 0x8000000000000000ULL
1760};
1761
1762/* INT TRIE Implementation of depth 64 bits, being the number of bits
1763 * in a 64 bit integer.
1764 */
1765
1766pANTLR3_INT_TRIE
1767antlr3IntTrieNew(ANTLR3_UINT32 depth)
1768{
1769 pANTLR3_INT_TRIE trie;
1770
1771 trie = (pANTLR3_INT_TRIE) ANTLR3_CALLOC(1, sizeof(ANTLR3_INT_TRIE))calloc (1, (size_t)(sizeof(ANTLR3_INT_TRIE)));; /* Base memory required */
1772
1773 if (trie == NULL((void*)0))
1774 {
1775 return (pANTLR3_INT_TRIE) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM)(void *)((ANTLR3_UINT64)((0 + 1)));
1776 }
1777
1778 /* Now we need to allocate the root node. This makes it easier
1779 * to use the tree as we don't have to do anything special
1780 * for the root node.
1781 */
1782 trie->root = (pANTLR3_INT_TRIE_NODE) ANTLR3_CALLOC(1, sizeof(ANTLR3_INT_TRIE))calloc (1, (size_t)(sizeof(ANTLR3_INT_TRIE)));;
1783
1784 if (trie->root == NULL((void*)0))
1785 {
1786 ANTLR3_FREE(trie)free ((void *)(trie));
1787 return (pANTLR3_INT_TRIE) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM)(void *)((ANTLR3_UINT64)((0 + 1)));
1788 }
1789
1790 trie->add = intTrieAdd;
1791 trie->del = intTrieDel;
1792 trie->free = intTrieFree;
1793 trie->get = intTrieGet;
1794
1795 /* Now we seed the root node with the index being the
1796 * highest left most bit we want to test, which limits the
1797 * keys in the trie. This is the trie 'depth'. The limit for
1798 * this implementation is 63 (bits 0..63).
1799 */
1800 trie->root->bitNum = depth;
1801
1802 /* And as we have nothing in here yet, we set both child pointers
1803 * of the root node to point back to itself.
1804 */
1805 trie->root->leftN = trie->root;
1806 trie->root->rightN = trie->root;
1807 trie->count = 0;
1808
1809 /* Finally, note that the key for this root node is 0 because
1810 * we use calloc() to initialise it.
1811 */
1812
1813 return trie;
1814}
1815
1816/** Search the int Trie and return a pointer to the first bucket indexed
1817 * by the key if it is contained in the trie, otherwise NULL.
1818 */
1819static pANTLR3_TRIE_ENTRY
1820intTrieGet (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key)
1821{
1822 pANTLR3_INT_TRIE_NODE thisNode;
1823 pANTLR3_INT_TRIE_NODE nextNode;
1824
1825 if (trie->count == 0)
1826 {
1827 return NULL((void*)0); /* Nothing in this trie yet */
1828 }
1829 /* Starting at the root node in the trie, compare the bit index
1830 * of the current node with its next child node (starts left from root).
1831 * When the bit index of the child node is greater than the bit index of the current node
1832 * then by definition (as the bit index decreases as we descent the trie)
1833 * we have reached a 'backward' pointer. A backward pointer means we
1834 * have reached the only node that can be reached by the bits given us so far
1835 * and it must either be the key we are looking for, or if not then it
1836 * means the entry was not in the trie, and we return NULL. A backward pointer
1837 * points back in to the tree structure rather than down (deeper) within the
1838 * tree branches.
1839 */
1840 thisNode = trie->root; /* Start at the root node */
1841 nextNode = thisNode->leftN; /* Examine the left node from the root */
1842
1843 /* While we are descending the tree nodes...
1844 */
1845 while (thisNode->bitNum > nextNode->bitNum)
1846 {
1847 /* Next node now becomes the new 'current' node
1848 */
1849 thisNode = nextNode;
1850
1851 /* We now test the bit indicated by the bitmap in the next node
1852 * in the key we are searching for. The new next node is the
1853 * right node if that bit is set and the left node it is not.
1854 */
1855 if (key & bitMask[nextNode->bitNum])
1856 {
1857 nextNode = nextNode->rightN; /* 1 is right */
1858 }
1859 else
1860 {
1861 nextNode = nextNode->leftN; /* 0 is left */
1862 }
1863 }
1864
1865 /* Here we have reached a node where the bitMap index is lower than
1866 * its parent. This means it is pointing backward in the tree and
1867 * must therefore be a terminal node, being the only point than can
1868 * be reached with the bits seen so far. It is either the actual key
1869 * we wanted, or if that key is not in the trie it is another key
1870 * that is currently the only one that can be reached by those bits.
1871 * That situation would obviously change if the key was to be added
1872 * to the trie.
1873 *
1874 * Hence it only remains to test whether this is actually the key or not.
1875 */
1876 if (nextNode->key == key)
1877 {
1878 /* This was the key, so return the entry pointer
1879 */
1880 return nextNode->buckets;
1881 }
1882 else
1883 {
1884 return NULL((void*)0); /* That key is not in the trie (note that we set the pointer to -1 if no payload) */
1885 }
1886}
1887
1888
1889static ANTLR3_BOOLEAN
1890intTrieDel (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key)
1891{
1892 pANTLR3_INT_TRIE_NODE p;
1893
1894 p=trie->root;
1895 key = key;
1896
1897 return ANTLR3_FALSE0;
1898}
1899
1900/** Add an entry into the INT trie.
1901 * Basically we descend the trie as we do when searching it, which will
1902 * locate the only node in the trie that can be reached by the bit pattern of the
1903 * key. If the key is actually at that node, then if the trie accepts duplicates
1904 * we add the supplied data in a new chained bucket to that data node. If it does
1905 * not accept duplicates then we merely return FALSE in case the caller wants to know
1906 * whether the key was already in the trie.
1907 * If the node we locate is not the key we are looking to add, then we insert a new node
1908 * into the trie with a bit index of the leftmost differing bit and the left or right
1909 * node pointing to itself or the data node we are inserting 'before'.
1910 */
1911static ANTLR3_BOOLEAN
1912intTrieAdd (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key, ANTLR3_UINT32 type, ANTLR3_INTKEY intVal, void * data, void (ANTLR3_CDECL *freeptr)(void *))
1913{
1914 pANTLR3_INT_TRIE_NODE thisNode;
1915 pANTLR3_INT_TRIE_NODE nextNode;
1916 pANTLR3_INT_TRIE_NODE entNode;
1917 ANTLR3_UINT32 depth;
1918 pANTLR3_TRIE_ENTRY newEnt;
1919 pANTLR3_TRIE_ENTRY nextEnt;
1920 ANTLR3_INTKEY xorKey;
1921
1922 /* Cache the bit depth of this trie, which is always the highest index,
1923 * which is in the root node
1924 */
1925 depth = trie->root->bitNum;
Value stored to 'depth' is never read
1926
1927 thisNode = trie->root; /* Start with the root node */
1928 nextNode = trie->root->leftN; /* And assume we start to the left */
1929
1930 /* Now find the only node that can be currently reached by the bits in the
1931 * key we are being asked to insert.
1932 */
1933 while (thisNode->bitNum > nextNode->bitNum)
1934 {
1935 /* Still descending the structure, next node becomes current.
1936 */
1937 thisNode = nextNode;
1938
1939 if (key & bitMask[nextNode->bitNum])
1940 {
1941 /* Bit at the required index was 1, so travers the right node from here
1942 */
1943 nextNode = nextNode->rightN;
1944 }
1945 else
1946 {
1947 /* Bit at the required index was 0, so we traverse to the left
1948 */
1949 nextNode = nextNode->leftN;
1950 }
1951 }
1952 /* Here we have located the only node that can be reached by the
1953 * bits in the requested key. It could in fact be that key or the node
1954 * we need to use to insert the new key.
1955 */
1956 if (nextNode->key == key)
1957 {
1958 /* We have located an exact match, but we will only append to the bucket chain
1959 * if this trie accepts duplicate keys.
1960 */
1961 if (trie->allowDups ==ANTLR3_TRUE1)
1962 {
1963 /* Yes, we are accepting duplicates
1964 */
1965 newEnt = (pANTLR3_TRIE_ENTRY)ANTLR3_CALLOC(1, sizeof(ANTLR3_TRIE_ENTRY))calloc (1, (size_t)(sizeof(ANTLR3_TRIE_ENTRY)));;
1966
1967 if (newEnt == NULL((void*)0))
1968 {
1969 /* Out of memory, all we can do is return the fact that the insert failed.
1970 */
1971 return ANTLR3_FALSE0;
1972 }
1973
1974 /* Otherwise insert this in the chain
1975 */
1976 newEnt->type = type;
1977 newEnt->freeptr = freeptr;
1978 if (type == ANTLR3_HASH_TYPE_STR1)
1979 {
1980 newEnt->data.ptr = data;
1981 }
1982 else
1983 {
1984 newEnt->data.intVal = intVal;
1985 }
1986
1987 /* We want to be able to traverse the stored elements in the order that they were
1988 * added as duplicate keys. We might need to revise this opinion if we end up having many duplicate keys
1989 * as perhaps reverse order is just as good, so long as it is ordered.
1990 */
1991 nextEnt = nextNode->buckets;
1992 while (nextEnt->next != NULL((void*)0))
1993 {
1994 nextEnt = nextEnt->next;
1995 }
1996 nextEnt->next = newEnt;
1997
1998 trie->count++;
1999 return ANTLR3_TRUE1;
2000 }
2001 else
2002 {
2003 /* We found the key is already there and we are not allowed duplicates in this
2004 * trie.
2005 */
2006 return ANTLR3_FALSE0;
2007 }
2008 }
2009
2010 /* Here we have discovered the only node that can be reached by the bits in the key
2011 * but we have found that this node is not the key we need to insert. We must find the
2012 * the leftmost bit by which the current key for that node and the new key we are going
2013 * to insert, differ. While this nested series of ifs may look a bit strange, experimentation
2014 * showed that it allows a machine code path that works well with predicated execution
2015 */
2016 xorKey = (key ^ nextNode->key); /* Gives 1 bits only where they differ then we find the left most 1 bit*/
2017
2018 /* Most common case is a 32 bit key really
2019 */
2020#ifdef ANTLR3_USE_64BIT1
2021 if (xorKey & 0xFFFFFFFF00000000)
2022 {
2023 if (xorKey & 0xFFFF000000000000)
2024 {
2025 if (xorKey & 0xFF00000000000000)
2026 {
2027 depth = 56 + bitIndex[((xorKey & 0xFF00000000000000)>>56)];
2028 }
2029 else
2030 {
2031 depth = 48 + bitIndex[((xorKey & 0x00FF000000000000)>>48)];
2032 }
2033 }
2034 else
2035 {
2036 if (xorKey & 0x0000FF0000000000)
2037 {
2038 depth = 40 + bitIndex[((xorKey & 0x0000FF0000000000)>>40)];
2039 }
2040 else
2041 {
2042 depth = 32 + bitIndex[((xorKey & 0x000000FF00000000)>>32)];
2043 }
2044 }
2045 }
2046 else
2047#endif
2048 {
2049 if (xorKey & 0x00000000FFFF0000)
2050 {
2051 if (xorKey & 0x00000000FF000000)
2052 {
2053 depth = 24 + bitIndex[((xorKey & 0x00000000FF000000)>>24)];
2054 }
2055 else
2056 {
2057 depth = 16 + bitIndex[((xorKey & 0x0000000000FF0000)>>16)];
2058 }
2059 }
2060 else
2061 {
2062 if (xorKey & 0x000000000000FF00)
2063 {
2064 depth = 8 + bitIndex[((xorKey & 0x0000000000000FF00)>>8)];
2065 }
2066 else
2067 {
2068 depth = bitIndex[xorKey & 0x00000000000000FF];
2069 }
2070 }
2071 }
2072
2073 /* We have located the leftmost differing bit, indicated by the depth variable. So, we know what
2074 * bit index we are to insert the new entry at. There are two cases, being where the two keys
2075 * differ at a bit position that is not currently part of the bit testing, where they differ on a bit
2076 * that is currently being skipped in the indexed comparisons, and where they differ on a bit
2077 * that is merely lower down in the current bit search. If the bit index went bit 4, bit 2 and they differ
2078 * at bit 3, then we have the "skipped" bit case. But if that chain was Bit 4, Bit 2 and they differ at bit 1
2079 * then we have the easy bit <pun>.
2080 *
2081 * So, set up to descend the tree again, but this time looking for the insert point
2082 * according to whether we skip the bit that differs or not.
2083 */
2084 thisNode = trie->root;
2085 entNode = trie->root->leftN;
2086
2087 /* Note the slight difference in the checks here to cover both cases
2088 */
2089 while (thisNode->bitNum > entNode->bitNum && entNode->bitNum > depth)
2090 {
2091 /* Still descending the structure, next node becomes current.
2092 */
2093 thisNode = entNode;
2094
2095 if (key & bitMask[entNode->bitNum])
2096 {
2097 /* Bit at the required index was 1, so traverse the right node from here
2098 */
2099 entNode = entNode->rightN;
2100 }
2101 else
2102 {
2103 /* Bit at the required index was 0, so we traverse to the left
2104 */
2105 entNode = entNode->leftN;
2106 }
2107 }
2108
2109 /* We have located the correct insert point for this new key, so we need
2110 * to allocate our entry and insert it etc.
2111 */
2112 nextNode = (pANTLR3_INT_TRIE_NODE)ANTLR3_CALLOC(1, sizeof(ANTLR3_INT_TRIE_NODE))calloc (1, (size_t)(sizeof(ANTLR3_INT_TRIE_NODE)));;
2113 if (nextNode == NULL((void*)0))
2114 {
2115 /* All that work and no memory - bummer.
2116 */
2117 return ANTLR3_FALSE0;
2118 }
2119
2120 /* Build a new entry block for the new node
2121 */
2122 newEnt = (pANTLR3_TRIE_ENTRY)ANTLR3_CALLOC(1, sizeof(ANTLR3_TRIE_ENTRY))calloc (1, (size_t)(sizeof(ANTLR3_TRIE_ENTRY)));;
2123
2124 if (newEnt == NULL((void*)0))
2125 {
2126 /* Out of memory, all we can do is return the fact that the insert failed.
2127 */
2128 return ANTLR3_FALSE0;
2129 }
2130
2131 /* Otherwise enter this in our new node
2132 */
2133 newEnt->type = type;
2134 newEnt->freeptr = freeptr;
2135 if (type == ANTLR3_HASH_TYPE_STR1)
2136 {
2137 newEnt->data.ptr = data;
2138 }
2139 else
2140 {
2141 newEnt->data.intVal = intVal;
2142 }
2143 /* Install it
2144 */
2145 nextNode->buckets = newEnt;
2146 nextNode->key = key;
2147 nextNode->bitNum = depth;
2148
2149 /* Work out the right and left pointers for this new node, which involve
2150 * terminating with the current found node either right or left according
2151 * to whether the current index bit is 1 or 0
2152 */
2153 if (key & bitMask[depth])
2154 {
2155 nextNode->leftN = entNode; /* Terminates at previous position */
2156 nextNode->rightN = nextNode; /* Terminates with itself */
2157 }
2158 else
2159 {
2160 nextNode->rightN = entNode; /* Terminates at previous position */
2161 nextNode->leftN = nextNode; /* Terminates with itself */
2162 }
2163
2164 /* Finally, we need to change the pointers at the node we located
2165 * for inserting. If the key bit at its index is set then the right
2166 * pointer for that node becomes the newly created node, otherwise the left
2167 * pointer does.
2168 */
2169 if (key & bitMask[thisNode->bitNum] )
2170 {
2171 thisNode->rightN = nextNode;
2172 }
2173 else
2174 {
2175 thisNode->leftN = nextNode;
2176 }
2177
2178 /* Et voila
2179 */
2180 trie->count++;
2181 return ANTLR3_TRUE1;
2182
2183}
2184/** Release memory allocated to this tree.
2185 * Basic algorithm is that we do a depth first left descent and free
2186 * up any nodes that are not backward pointers.
2187 */
2188static void
2189freeIntNode(pANTLR3_INT_TRIE_NODE node)
2190{
2191 pANTLR3_TRIE_ENTRY thisEntry;
2192 pANTLR3_TRIE_ENTRY nextEntry;
2193
2194 /* If this node has a left pointer that is not a back pointer
2195 * then recursively call to free this
2196 */
2197 if (node->bitNum > node->leftN->bitNum)
2198 {
2199 /* We have a left node that needs descending, so do it.
2200 */
2201 freeIntNode(node->leftN);
2202 }
2203
2204 /* The left nodes from here should now be dealt with, so
2205 * we need to descend any right nodes that are not back pointers
2206 */
2207 if (node->bitNum > node->rightN->bitNum)
2208 {
2209 /* There are some right nodes to descend and deal with.
2210 */
2211 freeIntNode(node->rightN);
2212 }
2213
2214 /* Now all the children are dealt with, we can destroy
2215 * this node too
2216 */
2217 thisEntry = node->buckets;
2218
2219 while (thisEntry != NULL((void*)0))
2220 {
2221 nextEntry = thisEntry->next;
2222
2223 /* Do we need to call a custom free pointer for this string entry?
2224 */
2225 if (thisEntry->type == ANTLR3_HASH_TYPE_STR1 && thisEntry->freeptr != NULL((void*)0))
2226 {
2227 thisEntry->freeptr(thisEntry->data.ptr);
2228 }
2229
2230 /* Now free the data for this bucket entry
2231 */
2232 ANTLR3_FREE(thisEntry)free ((void *)(thisEntry));
2233 thisEntry = nextEntry; /* See if there are any more to free */
2234 }
2235
2236 /* The bucket entry is now gone, so we can free the memory for
2237 * the entry itself.
2238 */
2239 ANTLR3_FREE(node)free ((void *)(node));
2240
2241 /* And that should be it for everything under this node and itself
2242 */
2243}
2244
2245/** Called to free all nodes and the structure itself.
2246 */
2247static void
2248intTrieFree (pANTLR3_INT_TRIE trie)
2249{
2250 /* Descend from the root and free all the nodes
2251 */
2252 freeIntNode(trie->root);
2253
2254 /* the nodes are all gone now, so we need only free the memory
2255 * for the structure itself
2256 */
2257 ANTLR3_FREE(trie)free ((void *)(trie));
2258}
2259
2260
2261/**
2262 * Allocate and initialize a new ANTLR3 topological sorter, which can be
2263 * used to define edges that identify numerical node indexes that depend on other
2264 * numerical node indexes, which can then be sorted topologically such that
2265 * any node is sorted after all its dependent nodes.
2266 *
2267 * Use:
2268 *
2269 * /verbatim
2270
2271 pANTLR3_TOPO topo;
2272 topo = antlr3NewTopo();
2273
2274 if (topo == NULL) { out of memory }
2275
2276 topo->addEdge(topo, 3, 0); // Node 3 depends on node 0
2277 topo->addEdge(topo, 0, 1); // Node - depends on node 1
2278 topo->sortVector(topo, myVector); // Sort the vector in place (node numbers are the vector entry numbers)
2279
2280 * /verbatim
2281 */
2282ANTLR3_API pANTLR3_TOPO
2283antlr3TopoNew()
2284{
2285 pANTLR3_TOPO topo = (pANTLR3_TOPO)ANTLR3_MALLOC(sizeof(ANTLR3_TOPO))malloc ((size_t)(sizeof(ANTLR3_TOPO)));;
2286
2287 if (topo == NULL((void*)0))
2288 {
2289 return NULL((void*)0);
2290 }
2291
2292 // Initialize variables
2293 //
2294
2295 topo->visited = NULL((void*)0); // Don't know how big it is yet
2296 topo->limit = 1; // No edges added yet
2297 topo->edges = NULL((void*)0); // No edges added yet
2298 topo->sorted = NULL((void*)0); // Nothing sorted at the start
2299 topo->cycle = NULL((void*)0); // No cycles at the start
2300 topo->cycleMark = 0; // No cycles at the start
2301 topo->hasCycle = ANTLR3_FALSE0; // No cycle at the start
2302
2303 // API
2304 //
2305 topo->addEdge = addEdge;
2306 topo->sortToArray = sortToArray;
2307 topo->sortVector = sortVector;
2308 topo->free = freeTopo;
2309
2310 return topo;
2311}
2312// Topological sorter
2313//
2314static void
2315addEdge (pANTLR3_TOPO topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency)
2316{
2317 ANTLR3_UINT32 i;
2318 ANTLR3_UINT32 maxEdge;
2319 pANTLR3_BITSET edgeDeps;
2320
2321 if (edge>dependency)
2322 {
2323 maxEdge = edge;
2324 }
2325 else
2326 {
2327 maxEdge = dependency;
2328 }
2329 // We need to add an edge to says that the node indexed by 'edge' is
2330 // dependent on the node indexed by 'dependency'
2331 //
2332
2333 // First see if we have enough room in the edges array to add the edge?
2334 //
2335 if (topo->edges == NULL((void*)0))
2336 {
2337 // We don't have any edges yet, so create an array to hold them
2338 //
2339 topo->edges = ANTLR3_CALLOC(sizeof(pANTLR3_BITSET) * (maxEdge + 1), 1)calloc (sizeof(pANTLR3_BITSET) * (maxEdge + 1), (size_t)(1));;
2340 if (topo->edges == NULL((void*)0))
2341 {
2342 return;
2343 }
2344
2345 // Set the limit to what we have now
2346 //
2347 topo->limit = maxEdge + 1;
2348 }
2349 else if (topo->limit <= maxEdge)
2350 {
2351 // WE have some edges but not enough
2352 //
2353 topo->edges = ANTLR3_REALLOC(topo->edges, sizeof(pANTLR3_BITSET) * (maxEdge + 1))realloc ((void *)(topo->edges), (size_t)(sizeof(pANTLR3_BITSET
) * (maxEdge + 1)));
;
2354 if (topo->edges == NULL((void*)0))
2355 {
2356 return;
2357 }
2358
2359 // Initialize the new bitmaps to ;indicate we have no edges defined yet
2360 //
2361 for (i = topo->limit; i <= maxEdge; i++)
2362 {
2363 *((topo->edges) + i) = NULL((void*)0);
2364 }
2365
2366 // Set the limit to what we have now
2367 //
2368 topo->limit = maxEdge + 1;
2369 }
2370
2371 // If the edge was flagged as depending on itself, then we just
2372 // do nothing as it means this routine was just called to add it
2373 // in to the list of nodes.
2374 //
2375 if (edge == dependency)
2376 {
2377 return;
2378 }
2379
2380 // Pick up the bit map for the requested edge
2381 //
2382 edgeDeps = *((topo->edges) + edge);
2383
2384 if (edgeDeps == NULL((void*)0))
2385 {
2386 // No edges are defined yet for this node
2387 //
2388 edgeDeps = antlr3BitsetNew(0);
2389 *((topo->edges) + edge) = edgeDeps;
2390 if (edgeDeps == NULL((void*)0) )
2391 {
2392 return; // Out of memory
2393 }
2394 }
2395
2396 // Set the bit in the bitmap that corresponds to the requested
2397 // dependency.
2398 //
2399 edgeDeps->add(edgeDeps, dependency);
2400
2401 // And we are all set
2402 //
2403 return;
2404}
2405
2406
2407/**
2408 * Given a starting node, descend its dependent nodes (ones that it has edges
2409 * to) until we find one without edges. Having found a node without edges, we have
2410 * discovered the bottom of a depth first search, which we can then ascend, adding
2411 * the nodes in order from the bottom, which gives us the dependency order.
2412 */
2413static void
2414DFS(pANTLR3_TOPO topo, ANTLR3_UINT32 node)
2415{
2416 pANTLR3_BITSET edges;
2417
2418 // Guard against a revisit and check for cycles
2419 //
2420 if (topo->hasCycle == ANTLR3_TRUE1)
2421 {
2422 return; // We don't do anything else if we found a cycle
2423 }
2424
2425 if (topo->visited->isMember(topo->visited, node))
2426 {
2427 // Check to see if we found a cycle. To do this we search the
2428 // current cycle stack and see if we find this node already in the stack.
2429 //
2430 ANTLR3_UINT32 i;
2431
2432 for (i=0; i<topo->cycleMark; i++)
2433 {
2434 if (topo->cycle[i] == node)
2435 {
2436 // Stop! We found a cycle in the input, so rejig the cycle
2437 // stack so that it only contains the cycle and set the cycle flag
2438 // which will tell the caller what happened
2439 //
2440 ANTLR3_UINT32 l;
2441
2442 for (l = i; l < topo->cycleMark; l++)
2443 {
2444 topo->cycle[l - i] = topo->cycle[l]; // Move to zero base in the cycle list
2445 }
2446
2447 // Recalculate the limit
2448 //
2449 topo->cycleMark -= i;
2450
2451 // Signal disaster
2452 //
2453 topo->hasCycle = ANTLR3_TRUE1;
2454 }
2455 }
2456 return;
2457 }
2458
2459 // So far, no cycles have been found and we have not visited this node yet,
2460 // so this node needs to go into the cycle stack before we continue
2461 // then we will take it out of the stack once we have descended all its
2462 // dependencies.
2463 //
2464 topo->cycle[topo->cycleMark++] = node;
2465
2466 // First flag that we have visited this node
2467 //
2468 topo->visited->add(topo->visited, node);
2469
2470 // Now, if this node has edges, then we want to ensure we visit
2471 // them all before we drop through and add this node into the sorted
2472 // list.
2473 //
2474 edges = *((topo->edges) + node);
2475 if (edges != NULL((void*)0))
2476 {
2477 // We have some edges, so visit each of the edge nodes
2478 // that have not already been visited.
2479 //
2480 ANTLR3_UINT32 numBits; // How many bits are in the set
2481 ANTLR3_UINT32 i;
2482 ANTLR3_UINT32 range;
2483
2484 numBits = edges->numBits(edges);
2485 range = edges->size(edges); // Number of set bits
2486
2487 // Stop if we exahust the bit list or have checked the
2488 // number of edges that this node refers to (so we don't
2489 // check bits at the end that cannot possibly be set).
2490 //
2491 for (i=0; i<= numBits && range > 0; i++)
2492 {
2493 if (edges->isMember(edges, i))
2494 {
2495 range--; // About to check another one
2496
2497 // Found an edge, make sure we visit and descend it
2498 //
2499 DFS(topo, i);
2500 }
2501 }
2502 }
2503
2504 // At this point we will have visited all the dependencies
2505 // of this node and they will be ordered (even if there are cycles)
2506 // So we just add the node into the sorted list at the
2507 // current index position.
2508 //
2509 topo->sorted[topo->limit++] = node;
2510
2511 // Remove this node from the cycle list if we have not detected a cycle
2512 //
2513 if (topo->hasCycle == ANTLR3_FALSE0)
2514 {
2515 topo->cycleMark--;
2516 }
2517
2518 return;
2519}
2520
2521static pANTLR3_UINT32
2522sortToArray (pANTLR3_TOPO topo)
2523{
2524 ANTLR3_UINT32 v;
2525 ANTLR3_UINT32 oldLimit;
2526
2527 // Guard against being called with no edges defined
2528 //
2529 if (topo->edges == NULL((void*)0))
2530 {
2531 return 0;
2532 }
2533 // First we need a vector to populate with enough
2534 // entries to accomodate the sorted list and another to accomodate
2535 // the maximum cycle we could detect which is all nodes such as 0->1->2->3->0
2536 //
2537 topo->sorted = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32))malloc ((size_t)(topo->limit * sizeof(ANTLR3_UINT32)));;
2538 topo->cycle = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32))malloc ((size_t)(topo->limit * sizeof(ANTLR3_UINT32)));;
2539
2540 // Next we need an empty bitset to show whether we have visited a node
2541 // or not. This is the bit that gives us linear time of course as we are essentially
2542 // dropping through the nodes in depth first order and when we get to a node that
2543 // has no edges, we pop back up the stack adding the nodes we traversed in reverse
2544 // order.
2545 //
2546 topo->visited = antlr3BitsetNew(0);
2547
2548 // Now traverse the nodes as if we were just going left to right, but
2549 // then descend each node unless it has already been visited.
2550 //
2551 oldLimit = topo->limit; // Number of nodes to traverse linearly
2552 topo->limit = 0; // Next entry in the sorted table
2553
2554 for (v = 0; v < oldLimit; v++)
2555 {
2556 // If we did not already visit this node, then descend it until we
2557 // get a node without edges or arrive at a node we have already visited.
2558 //
2559 if (topo->visited->isMember(topo->visited, v) == ANTLR3_FALSE0)
2560 {
2561 // We have not visited this one so descend it
2562 //
2563 DFS(topo, v);
2564 }
2565
2566 // Break the loop if we detect a cycle as we have no need to go any
2567 // further
2568 //
2569 if (topo->hasCycle == ANTLR3_TRUE1)
2570 {
2571 break;
2572 }
2573 }
2574
2575 // Reset the limit to the number we recorded as if we hit a
2576 // cycle, then limit will have stopped at the node where we
2577 // discovered the cycle, but in order to free the edge bitmaps
2578 // we need to know how many we may have allocated and traverse them all.
2579 //
2580 topo->limit = oldLimit;
2581
2582 // Having traversed all the nodes we were given, we
2583 // are guaranteed to have ordered all the nodes or detected a
2584 // cycle.
2585 //
2586 return topo->sorted;
2587}
2588
2589static void
2590sortVector (pANTLR3_TOPO topo, pANTLR3_VECTOR v)
2591{
2592 // To sort a vector, we first perform the
2593 // sort to an array, then use the results to reorder the vector
2594 // we are given. This is just a convenience routine that allows you to
2595 // sort the children of a tree node into topological order before or
2596 // during an AST walk. This can be useful for optimizations that require
2597 // dag reorders and also when the input stream defines thigns that are
2598 // interdependent and you want to walk the list of the generated trees
2599 // for those things in topological order so you can ignore the interdependencies
2600 // at that point.
2601 //
2602 ANTLR3_UINT32 i;
2603
2604 // Used as a lookup index to find the current location in the vector of
2605 // the vector entry that was originally at position [0], [1], [2] etc
2606 //
2607 pANTLR3_UINT32 vIndex;
2608
2609 // Sort into an array, then we can use the array that is
2610 // stored in the topo
2611 //
2612 if (topo->sortToArray(topo) == 0)
2613 {
2614 return; // There were no edges
2615 }
2616
2617 if (topo->hasCycle == ANTLR3_TRUE1)
2618 {
2619 return; // Do nothing if we detected a cycle
2620 }
2621
2622 // Ensure that the vector we are sorting is at least as big as the
2623 // the input sequence we were adsked to sort. It does not matter if it is
2624 // bigger as thaat probably just means that nodes numbered higher than the
2625 // limit had no dependencies and so can be left alone.
2626 //
2627 if (topo->limit > v->count)
2628 {
2629 // We can only sort the entries that we have dude! The caller is
2630 // responsible for ensuring the vector is the correct one and is the
2631 // correct size etc.
2632 //
2633 topo->limit = v->count;
2634 }
2635 // We need to know the locations of each of the entries
2636 // in the vector as we don't want to duplicate them in a new vector. We
2637 // just use an indirection table to get the vector entry for a particular sequence
2638 // acording to where we moved it last. Then we can just swap vector entries until
2639 // we are done :-)
2640 //
2641 vIndex = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32))malloc ((size_t)(topo->limit * sizeof(ANTLR3_UINT32)));;
2642
2643 // Start index, each vector entry is located where you think it is
2644 //
2645 for (i = 0; i < topo->limit; i++)
2646 {
2647 vIndex[i] = i;
2648 }
2649
2650 // Now we traverse the sorted array and moved the entries of
2651 // the vector around according to the sort order and the indirection
2652 // table we just created. The index telsl us where in the vector the
2653 // original element entry n is now located via vIndex[n].
2654 //
2655 for (i=0; i < topo->limit; i++)
2656 {
2657 ANTLR3_UINT32 ind;
2658
2659 // If the vector entry at i is already the one that it
2660 // should be, then we skip moving it of course.
2661 //
2662 if (vIndex[topo->sorted[i]] == i)
2663 {
2664 continue;
2665 }
2666
2667 // The vector entry at i, should be replaced with the
2668 // vector entry indicated by topo->sorted[i]. The vector entry
2669 // at topo->sorted[i] may have already been swapped out though, so we
2670 // find where it is now and move it from there to i.
2671 //
2672 ind = vIndex[topo->sorted[i]];
2673 v->swap(v, i, ind);
2674
2675 // Update our index. The element at i is now the one we wanted
2676 // to be sorted here and the element we swapped out is now the
2677 // element that was at i just before we swapped it. If you are lost now
2678 // don't worry about it, we are just reindexing on the fly is all.
2679 //
2680 vIndex[topo->sorted[i]] = i;
2681 vIndex[i] = ind;
2682 }
2683
2684 // Having traversed all the entries, we have sorted the vector in place.
2685 //
2686 ANTLR3_FREE(vIndex)free ((void *)(vIndex));
2687 return;
2688}
2689
2690static void
2691freeTopo (pANTLR3_TOPO topo)
2692{
2693 ANTLR3_UINT32 i;
2694
2695 // Free the result vector
2696 //
2697 if (topo->sorted != NULL((void*)0))
2698 {
2699 ANTLR3_FREE(topo->sorted)free ((void *)(topo->sorted));
2700 topo->sorted = NULL((void*)0);
2701 }
2702
2703 // Free the visited map
2704 //
2705 if (topo->visited != NULL((void*)0))
2706 {
2707
2708 topo->visited->free(topo->visited);
2709 topo->visited = NULL((void*)0);
2710 }
2711
2712 // Free any edgemaps
2713 //
2714 if (topo->edges != NULL((void*)0))
2715 {
2716 pANTLR3_BITSET edgeList;
2717
2718
2719 for (i=0; i<topo->limit; i++)
2720 {
2721 edgeList = *((topo->edges) + i);
2722 if (edgeList != NULL((void*)0))
2723 {
2724 edgeList->free(edgeList);
2725 }
2726 }
2727
2728 ANTLR3_FREE(topo->edges)free ((void *)(topo->edges));
2729 }
2730 topo->edges = NULL((void*)0);
2731
2732 // Free any cycle map
2733 //
2734 if (topo->cycle != NULL((void*)0))
2735 {
2736 ANTLR3_FREE(topo->cycle)free ((void *)(topo->cycle));
2737 }
2738
2739 ANTLR3_FREE(topo)free ((void *)(topo));
2740}