| blob | 48ffe184ce331f9e11c1503a4fdc1b452ec6b481 |
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 ///
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.
38 #include <antlr3.h>
40 #include "antlr3collections.h"
42 // Interface functions for hash table
43 //
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 *));
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 *));
59 static void antlr3HashFree (pANTLR3_HASH_TABLE table);
60 static ANTLR3_UINT32 antlr3HashSize (pANTLR3_HASH_TABLE table);
62 // -----------
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);
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);
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);
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);
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);
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);
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);
121 // Local function to advance enumeration structure pointers
122 //
123 static void antlr3EnumNextEntry(pANTLR3_HASH_ENUM en);
125 pANTLR3_HASH_TABLE
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;
133 ANTLR3_UINT32 bucket; // Used to traverse the buckets
135 table = ANTLR3_MALLOC(sizeof(ANTLR3_HASH_TABLE));
137 // Error out if no memory left
138 if (table == NULL)
139 {
140 return NULL;
141 }
143 // Allocate memory for the buckets
144 //
145 table->buckets = (pANTLR3_HASH_BUCKET) ANTLR3_MALLOC((size_t) (sizeof(ANTLR3_HASH_BUCKET) * sizeHint));
147 if (table->buckets == NULL)
148 {
149 ANTLR3_FREE((void *)table);
150 return NULL;
151 }
153 // Modulo of the table, (bucket count).
154 //
155 table->modulo = sizeHint;
157 table->count = 0; /* Nothing in there yet ( I hope) */
159 /* Initialize the buckets to empty
160 */
161 for (bucket = 0; bucket < sizeHint; bucket++)
162 {
163 table->buckets[bucket].entries = NULL;
164 }
166 /* Exclude duplicate entries by default
167 */
168 table->allowDups = ANTLR3_FALSE;
170 /* Assume that keys should by strduped before they are
171 * entered in the table.
172 */
173 table->doStrdup = ANTLR3_TRUE;
175 /* Install the interface
176 */
178 table->get = antlr3HashGet;
179 table->put = antlr3HashPut;
180 table->del = antlr3HashDelete;
181 table->remove = antlr3HashRemove;
183 table->getI = antlr3HashGetI;
184 table->putI = antlr3HashPutI;
185 table->delI = antlr3HashDeleteI;
186 table->removeI = antlr3HashRemoveI;
188 table->size = antlr3HashSize;
189 table->free = antlr3HashFree;
191 return table;
192 }
194 static void
195 antlr3HashFree(pANTLR3_HASH_TABLE table)
196 {
197 ANTLR3_UINT32 bucket; /* Used to traverse the buckets */
199 pANTLR3_HASH_BUCKET thisBucket;
200 pANTLR3_HASH_ENTRY entry;
201 pANTLR3_HASH_ENTRY nextEntry;
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]);
212 /* Allow sparse tables, though we don't create them as such at present
213 */
214 if ( thisBucket != NULL)
215 {
216 entry = thisBucket->entries;
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;
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 }
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 }
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 }
254 /* Now we can free the bucket memory
255 */
256 ANTLR3_FREE(table->buckets);
257 }
259 /* Now we free teh memory for the table itself
260 */
261 ANTLR3_FREE(table);
262 }
264 /** return the current size of the hash table
265 */
266 static ANTLR3_UINT32 antlr3HashSize (pANTLR3_HASH_TABLE table)
267 {
268 return table->count;
269 }
271 /** Remove a numeric keyed entry from a hash table if it exists,
272 * no error if it does not exist.
273 */
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;
281 /* First we need to know the hash of the provided key
282 */
283 hash = (ANTLR3_UINT32)(key % (ANTLR3_INTKEY)(table->modulo));
285 /* Knowing the hash, we can find the bucket
286 */
287 bucket = table->buckets + hash;
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 */
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;
310 table->count--;
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 }
324 return NULL; /* Not found */
325 }
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
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;
338 /* First we need to know the hash of the provided key
339 */
340 hash = antlr3Hash(key, (ANTLR3_UINT32)strlen((const char *)key));
342 /* Knowing the hash, we can find the bucket
343 */
344 bucket = table->buckets + (hash % table->modulo);
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 */
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;
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;
375 table->count--;
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 }
389 return NULL; /* Not found */
390 }
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
396 antlr3HashDeleteI (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key)
397 {
398 pANTLR3_HASH_ENTRY entry;
400 entry = antlr3HashRemoveI(table, key);
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 }
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
420 antlr3HashDelete (pANTLR3_HASH_TABLE table, void * key)
421 {
422 pANTLR3_HASH_ENTRY entry;
424 entry = antlr3HashRemove(table, key);
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 }
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 *
444 antlr3HashGetI(pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key)
445 {
446 ANTLR3_UINT32 hash;
447 pANTLR3_HASH_BUCKET bucket;
448 pANTLR3_HASH_ENTRY entry;
450 /* First we need to know the hash of the provided key
451 */
452 hash = (ANTLR3_UINT32)(key % (ANTLR3_INTKEY)(table->modulo));
454 /* Knowing the hash, we can find the bucket
455 */
456 bucket = table->buckets + hash;
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;
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 }
474 /* If we got here, then we did not find the key
475 */
476 return NULL;
477 }
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 *
483 antlr3HashGet(pANTLR3_HASH_TABLE table, void * key)
484 {
485 ANTLR3_UINT32 hash;
486 pANTLR3_HASH_BUCKET bucket;
487 pANTLR3_HASH_ENTRY entry;
490 /* First we need to know the hash of the provided key
491 */
492 hash = antlr3Hash(key, (ANTLR3_UINT32)strlen((const char *)key));
494 /* Knowing the hash, we can find the bucket
495 */
496 bucket = table->buckets + (hash % table->modulo);
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;
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 }
514 /* If we got here, then we did not find the key
515 */
516 return NULL;
517 }
519 /** Add the element pointer in to the table, based upon the
520 * hash of the provided key.
521 */
522 static ANTLR3_INT32
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;
530 /* First we need to know the hash of the provided key
531 */
532 hash = (ANTLR3_UINT32)(key % (ANTLR3_INTKEY)(table->modulo));
534 /* Knowing the hash, we can find the bucket
535 */
536 bucket = table->buckets + hash;
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;
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 }
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 }
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));
571 if (entry == NULL)
572 {
573 return ANTLR3_ERR_NOMEM;
574 }
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 */
582 *newPointer = entry; /* Install the next entry in this bucket */
584 table->count++;
586 return ANTLR3_SUCCESS;
587 }
590 /** Add the element pointer in to the table, based upon the
591 * hash of the provided key.
592 */
593 static ANTLR3_INT32
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;
601 /* First we need to know the hash of the provided key
602 */
603 hash = antlr3Hash(key, (ANTLR3_UINT32)strlen((const char *)key));
605 /* Knowing the hash, we can find the bucket
606 */
607 bucket = table->buckets + (hash % table->modulo);
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;
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 }
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 }
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));
642 if (entry == NULL)
643 {
644 return ANTLR3_ERR_NOMEM;
645 }
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 */
660 *newPointer = entry; /* Install the next entry in this bucket */
662 table->count++;
664 return ANTLR3_SUCCESS;
665 }
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
673 antlr3EnumNew (pANTLR3_HASH_TABLE table)
674 {
675 pANTLR3_HASH_ENUM en;
677 /* Allocate structure memory
678 */
679 en = (pANTLR3_HASH_ENUM) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_HASH_ENUM));
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 }
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 */
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 }
705 /* Install the interface
706 */
707 en->free = antlr3EnumFree;
708 en->next = antlr3EnumNext;
710 /* All is good
711 */
712 return en;
713 }
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
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 }
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;
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);
751 return ANTLR3_SUCCESS;
752 }
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
765 antlr3EnumNextEntry(pANTLR3_HASH_ENUM en)
766 {
767 pANTLR3_HASH_BUCKET bucket;
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 }
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++;
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;
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 }
806 /* There was nothing in the bucket we just examined, move to the
807 * next one.
808 */
809 en->bucket++;
810 }
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 }
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
822 antlr3EnumFree (pANTLR3_HASH_ENUM en)
823 {
824 /* Nothing to check, we just free it.
825 */
826 ANTLR3_FREE(en);
827 }
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
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;
842 hash = 0;
843 keyPtr = (pANTLR3_UINT8) key;
845 /* Iterate the key and accumulate the hash
846 */
847 while(keylen > 0)
848 {
849 hash = (hash << 4) + (*(keyPtr++));
851 if ((i1=hash&0xf0000000) != 0)
852 {
853 hash = hash ^ (i1 >> 24);
854 hash = hash ^ i1;
855 }
856 keylen--;
857 }
859 return hash;
860 }
862 ANTLR3_API pANTLR3_LIST
863 antlr3ListNew (ANTLR3_UINT32 sizeHint)
864 {
865 pANTLR3_LIST list;
867 /* Allocate memory
868 */
869 list = (pANTLR3_LIST)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_LIST));
871 if (list == NULL)
872 {
873 return (pANTLR3_LIST)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
874 }
876 /* Now we need to add a new table
877 */
878 list->table = antlr3HashTableNew(sizeHint);
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 }
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;
895 return list;
896 }
898 static ANTLR3_UINT32 antlr3ListSize (pANTLR3_LIST list)
899 {
900 return list->table->size(list->table);
901 }
903 static void
904 antlr3ListFree (pANTLR3_LIST list)
905 {
906 /* Free the hashtable that stores the list
907 */
908 list->table->free(list->table);
910 /* Free the allocation for the list itself
911 */
912 ANTLR3_FREE(list);
913 }
915 static void
916 antlr3ListDelete (pANTLR3_LIST list, ANTLR3_INTKEY key)
917 {
918 list->table->delI(list->table, key);
919 }
921 static void *
922 antlr3ListGet (pANTLR3_LIST list, ANTLR3_INTKEY key)
923 {
924 return list->table->getI(list->table, key);
925 }
927 /** Add the supplied element to the list, at the next available key
928 */
929 static ANTLR3_INT32 antlr3ListAdd (pANTLR3_LIST list, void * element, void (ANTLR3_CDECL *freeptr)(void *))
930 {
931 ANTLR3_INTKEY key;
933 key = list->table->size(list->table) + 1;
934 return list->put(list, key, element, freeptr);
935 }
937 /** Remove from the list, but don't free the element, just send it back to the
938 * caller.
939 */
940 static void *
941 antlr3ListRemove (pANTLR3_LIST list, ANTLR3_INTKEY key)
942 {
943 pANTLR3_HASH_ENTRY entry;
945 entry = list->table->removeI(list->table, key);
947 if (entry != NULL)
948 {
949 return entry->data;
950 }
951 else
952 {
953 return NULL;
954 }
955 }
957 static ANTLR3_INT32
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 }
963 ANTLR3_API pANTLR3_STACK
964 antlr3StackNew (ANTLR3_UINT32 sizeHint)
965 {
966 pANTLR3_STACK stack;
968 /* Allocate memory
969 */
970 stack = (pANTLR3_STACK)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_STACK));
972 if (stack == NULL)
973 {
974 return (pANTLR3_STACK)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
975 }
977 /* Now we need to add a new table
978 */
979 stack->vector = antlr3VectorNew(sizeHint);
980 stack->top = NULL;
982 if (stack->vector == (pANTLR3_VECTOR)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM))
983 {
984 return (pANTLR3_STACK)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
985 }
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;
996 return stack;
997 }
999 static ANTLR3_UINT32 antlr3StackSize (pANTLR3_STACK stack)
1000 {
1001 return stack->vector->count;
1002 }
1005 static void
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;
1014 ANTLR3_FREE(stack);
1015 }
1017 static void *
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);
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 }
1034 static void *
1035 antlr3StackGet (pANTLR3_STACK stack, ANTLR3_INTKEY key)
1036 {
1037 return stack->vector->get(stack->vector, (ANTLR3_UINT32)key);
1038 }
1040 static void *
1041 antlr3StackPeek (pANTLR3_STACK stack)
1042 {
1043 return stack->top;
1044 }
1046 static ANTLR3_BOOLEAN
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 }
1053 ANTLR3_API pANTLR3_VECTOR
1054 antlr3VectorNew (ANTLR3_UINT32 sizeHint)
1055 {
1056 pANTLR3_VECTOR vector;
1059 // Allocate memory for the vector structure itself
1060 //
1061 vector = (pANTLR3_VECTOR) ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR)));
1063 if (vector == NULL)
1064 {
1065 return (pANTLR3_VECTOR)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
1066 }
1068 // Now fill in the defaults
1069 //
1070 antlr3SetVectorApi(vector, sizeHint);
1072 // And everything is hunky dory
1073 //
1074 return vector;
1075 }
1077 ANTLR3_API void
1078 antlr3SetVectorApi (pANTLR3_VECTOR vector, ANTLR3_UINT32 sizeHint)
1079 {
1080 ANTLR3_UINT32 initialSize;
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 }
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 }
1102 if (vector->elements == NULL)
1103 {
1104 ANTLR3_FREE(vector);
1105 return;
1106 }
1108 // Memory allocated successfully
1109 //
1110 vector->count = 0; // No entries yet of course
1111 vector->elementsSize = initialSize; // Available entries
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;
1125 // Assume that this is not a factory made vector
1126 //
1127 vector->factoryMade = ANTLR3_FALSE;
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 //
1134 static void
1135 antlr3VectorClear (pANTLR3_VECTOR vector)
1136 {
1137 ANTLR3_UINT32 entry;
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)
1146 {
1147 vector->elements[entry].freeptr(vector->elements[entry].element);
1148 }
1149 vector->elements[entry].freeptr = NULL;
1150 vector->elements[entry].element = NULL;
1151 }
1153 // Having called any free pointers, we just reset the entry count
1154 // back to zero.
1155 //
1156 vector->count = 0;
1157 }
1159 static
1160 void ANTLR3_CDECL antlr3VectorFree (pANTLR3_VECTOR vector)
1161 {
1162 ANTLR3_UINT32 entry;
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)
1171 {
1172 vector->elements[entry].freeptr(vector->elements[entry].element);
1173 }
1174 vector->elements[entry].freeptr = NULL;
1175 vector->elements[entry].element = NULL;
1176 }
1178 if (vector->factoryMade == ANTLR3_FALSE)
1179 {
1180 // The entries are freed, so free the element allocation
1181 //
1182 if (vector->elementsSize > ANTLR3_VECTOR_INTERNAL_SIZE)
1183 {
1184 ANTLR3_FREE(vector->elements);
1185 }
1186 vector->elements = NULL;
1188 // Finally, free the allocation for the vector itself
1189 //
1190 ANTLR3_FREE(vector);
1191 }
1192 }
1194 static 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 }
1203 // Valid request, check for free pointer and call it if present
1204 //
1205 if (vector->elements[entry].freeptr != NULL)
1206 {
1207 vector->elements[entry].freeptr(vector->elements[entry].element);
1208 vector->elements[entry].freeptr = NULL;
1209 }
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;
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));
1223 }
1225 // One less entry in the vector now
1226 //
1227 vector->count--;
1228 }
1230 static 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;
1243 }
1244 }
1246 /// Remove the entry from the vector, but do not free any entry, even if it has
1247 /// a free pointer.
1248 ///
1249 static void * antrl3VectorRemove (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry)
1250 {
1251 void * element;
1253 // Check this is a valid request first
1254 //
1255 if (entry >= vector->count)
1256 {
1257 return NULL;
1258 }
1260 // Valid request, return the sorted pointer
1261 //
1263 element = vector->elements[entry].element;
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;
1271 vector->elements[entry].freeptr = NULL;
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));
1278 }
1280 // One less entry in the vector now
1281 //
1282 vector->count--;
1284 return element;
1285 }
1287 static void
1288 antlr3VectorResize (pANTLR3_VECTOR vector, ANTLR3_UINT32 hint)
1289 {
1290 ANTLR3_UINT32 newSize;
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 }
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_SIZE)
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));
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));
1322 ANTLR3_MEMCPY(vector->elements, vector->internal, ANTLR3_VECTOR_INTERNAL_SIZE * sizeof(ANTLR3_VECTOR_ELEMENT));
1323 }
1325 vector->elementsSize = newSize;
1326 }
1328 /// Add the supplied pointer and freeing function pointer to the list,
1329 /// expanding the vector if needed.
1330 ///
1331 static 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 }
1340 // Insert the new entry
1341 //
1342 vector->elements[vector->count].element = element;
1343 vector->elements[vector->count].freeptr = freeptr;
1345 vector->count++; // One more element counted
1347 return (ANTLR3_UINT32)(vector->count);
1349 }
1351 /// Replace the element at the specified entry point with the supplied
1352 /// entry.
1353 ///
1354 static ANTLR3_UINT32
1355 antlr3VectorSet (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry, void * element, void (ANTLR3_CDECL *freeptr)(void *), ANTLR3_BOOLEAN freeExisting)
1356 {
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 }
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 // And the existing element has a free pointer
1370 )
1371 {
1372 vector->elements[entry].freeptr(vector->elements[entry].element);
1373 }
1375 // Install the new pointers
1376 //
1377 vector->elements[entry].freeptr = freeptr;
1378 vector->elements[entry].element = element;
1380 if (entry >= vector->count)
1381 {
1382 vector->count = entry + 1;
1383 }
1384 return (ANTLR3_UINT32)(entry); // Indicates the replacement was successful
1386 }
1388 /// Replace the element at the specified entry point with the supplied
1389 /// entry.
1390 ///
1391 static ANTLR3_BOOLEAN
1392 antlr3VectorSwap (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry1, ANTLR3_UINT32 entry2)
1393 {
1395 void * tempEntry;
1396 void (ANTLR3_CDECL *freeptr)(void *);
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_FALSE;
1403 }
1405 // Valid request, swap them
1406 //
1407 tempEntry = vector->elements[entry1].element;
1408 freeptr = vector->elements[entry1].freeptr;
1410 // Install the new pointers
1411 //
1412 vector->elements[entry1].freeptr = vector->elements[entry2].freeptr;
1413 vector->elements[entry1].element = vector->elements[entry2].element;
1415 vector->elements[entry2].freeptr = freeptr;
1416 vector->elements[entry2].element = tempEntry;
1418 return ANTLR3_TRUE;
1420 }
1422 static ANTLR3_UINT32 antlr3VectorSize (pANTLR3_VECTOR vector)
1423 {
1424 return vector->count;
1425 }
1427 #ifdef ANTLR3_WINDOWS
1428 #pragma warning (push)
1429 #pragma warning (disable : 4100)
1430 #endif
1431 /// Vector factory creation
1432 ///
1433 ANTLR3_API pANTLR3_VECTOR_FACTORY
1434 antlr3VectorFactoryNew (ANTLR3_UINT32 sizeHint)
1435 {
1436 pANTLR3_VECTOR_FACTORY factory;
1438 // Allocate memory for the factory
1439 //
1440 factory = (pANTLR3_VECTOR_FACTORY)ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR_FACTORY)));
1442 if (factory == NULL)
1443 {
1444 return NULL;
1445 }
1447 // Factory memory is good, so create a new vector pool
1448 //
1449 factory->pools = NULL;
1450 factory->thisPool = -1;
1452 newPool(factory);
1454 // Initialize the API, ignore the hint as this algorithm does
1455 // a better job really.
1456 //
1457 antlr3SetVectorApi(&(factory->unTruc), ANTLR3_VECTOR_INTERNAL_SIZE);
1459 factory->unTruc.factoryMade = ANTLR3_TRUE;
1461 // Install the factory API
1462 //
1463 factory->close = closeVectorFactory;
1464 factory->newVector = newVector;
1465 factory->returnVector = returnVector;
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
1476 static void
1477 returnVector (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);
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);
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 }
1493 static void
1494 newPool(pANTLR3_VECTOR_FACTORY factory)
1495 {
1496 /* Increment factory count
1497 */
1498 factory->thisPool++;
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) */
1504 (ANTLR3_UINT32)((factory->thisPool + 1) * sizeof(pANTLR3_VECTOR *)) /* Memory for new pool pointers */
1505 );
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));
1514 /* Reset the counters
1515 */
1516 factory->nextVector = 0;
1518 /* Done
1519 */
1520 return;
1521 }
1523 static void
1524 closeVectorFactory (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;
1532 // First see if we have a free chain stack to release?
1533 //
1534 if (factory->freeStack != NULL)
1535 {
1536 factory->freeStack->free(factory->freeStack);
1537 }
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];
1547 /* Work out how many tokens we need to check in this pool.
1548 */
1549 limit = (poolCount == factory->thisPool ? factory->nextVector : ANTLR3_FACTORY_VPOOL_SIZE);
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;
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 }
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];
1589 /* Work out how many tokens we need to check in this pool.
1590 */
1591 limit = (poolCount == factory->thisPool ? factory->nextVector : ANTLR3_FACTORY_VPOOL_SIZE);
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;
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_TRUE && check->elementsSize > ANTLR3_VECTOR_INTERNAL_SIZE)
1611 {
1612 ANTLR3_FREE(check->elements);
1613 check->elements = NULL;
1614 }
1615 }
1616 }
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]);
1622 factory->pools[poolCount] = NULL;
1623 }
1625 /* All the pools are deallocated we can free the pointers to the pools
1626 * now.
1627 */
1628 ANTLR3_FREE(factory->pools);
1630 /* Finally, we can free the space for the factory itself
1631 */
1632 ANTLR3_FREE(factory);
1634 }
1636 static pANTLR3_VECTOR
1637 newVector(pANTLR3_VECTOR_FACTORY factory)
1638 {
1639 pANTLR3_VECTOR vector;
1641 // If we have anything on the re claim stack, reuse it
1642 //
1643 vector = factory->freeStack->peek(factory->freeStack);
1645 if (vector != NULL)
1646 {
1647 // Cool we got something we could reuse
1648 //
1649 factory->freeStack->pop(factory->freeStack);
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;
1654 }
1656 // See if we need a new vector pool before allocating a new
1657 // one
1658 //
1659 if (factory->nextVector >= ANTLR3_FACTORY_VPOOL_SIZE)
1660 {
1661 // We ran out of vectors in the current pool, so we need a new pool
1662 //
1663 newPool(factory);
1664 }
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++;
1672 // We have our token pointer now, so we can initialize it to the predefined model.
1673 //
1674 antlr3SetVectorApi(vector, ANTLR3_VECTOR_INTERNAL_SIZE);
1675 vector->factoryMade = ANTLR3_TRUE;
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;
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);
1685 // And we are done
1686 //
1687 return vector;
1688 }
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 */
1710 static 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 };
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 */
1742 static 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 };
1762 /* INT TRIE Implementation of depth 64 bits, being the number of bits
1763 * in a 64 bit integer.
1764 */
1766 pANTLR3_INT_TRIE
1767 antlr3IntTrieNew(ANTLR3_UINT32 depth)
1768 {
1769 pANTLR3_INT_TRIE trie;
1771 trie = (pANTLR3_INT_TRIE) ANTLR3_CALLOC(1, sizeof(ANTLR3_INT_TRIE)); /* Base memory required */
1773 if (trie == NULL)
1774 {
1775 return (pANTLR3_INT_TRIE) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
1776 }
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));
1784 if (trie->root == NULL)
1785 {
1786 ANTLR3_FREE(trie);
1787 return (pANTLR3_INT_TRIE) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
1788 }
1790 trie->add = intTrieAdd;
1791 trie->del = intTrieDel;
1792 trie->free = intTrieFree;
1793 trie->get = intTrieGet;
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;
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;
1809 /* Finally, note that the key for this root node is 0 because
1810 * we use calloc() to initialise it.
1811 */
1813 return trie;
1814 }
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 */
1819 static pANTLR3_TRIE_ENTRY
1820 intTrieGet (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key)
1821 {
1822 pANTLR3_INT_TRIE_NODE thisNode;
1823 pANTLR3_INT_TRIE_NODE nextNode;
1825 if (trie->count == 0)
1826 {
1827 return NULL; /* 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 */
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;
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 }
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; /* That key is not in the trie (note that we set the pointer to -1 if no payload) */
1885 }
1886 }
1889 static ANTLR3_BOOLEAN
1890 intTrieDel (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key)
1891 {
1892 pANTLR3_INT_TRIE_NODE p;
1894 p=trie->root;
1895 key = key;
1897 return ANTLR3_FALSE;
1898 }
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 */
1911 static ANTLR3_BOOLEAN
1912 intTrieAdd (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;
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;
1927 thisNode = trie->root; /* Start with the root node */
1928 nextNode = trie->root->leftN; /* And assume we start to the left */
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;
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_TRUE)
1962 {
1963 /* Yes, we are accepting duplicates
1964 */
1965 newEnt = (pANTLR3_TRIE_ENTRY)ANTLR3_CALLOC(1, sizeof(ANTLR3_TRIE_ENTRY));
1967 if (newEnt == NULL)
1968 {
1969 /* Out of memory, all we can do is return the fact that the insert failed.
1970 */
1971 return ANTLR3_FALSE;
1972 }
1974 /* Otherwise insert this in the chain
1975 */
1976 newEnt->type = type;
1977 newEnt->freeptr = freeptr;
1978 if (type == ANTLR3_HASH_TYPE_STR)
1979 {
1980 newEnt->data.ptr = data;
1981 }
1982 else
1983 {
1984 newEnt->data.intVal = intVal;
1985 }
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)
1993 {
1994 nextEnt = nextEnt->next;
1995 }
1996 nextEnt->next = newEnt;
1998 trie->count++;
1999 return ANTLR3_TRUE;
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_FALSE;
2007 }
2008 }
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*/
2018 /* Most common case is a 32 bit key really
2019 */
2020 #ifdef ANTLR3_USE_64BIT
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 }
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;
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;
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 }
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));
2113 if (nextNode == NULL)
2114 {
2115 /* All that work and no memory - bummer.
2116 */
2117 return ANTLR3_FALSE;
2118 }
2120 /* Build a new entry block for the new node
2121 */
2122 newEnt = (pANTLR3_TRIE_ENTRY)ANTLR3_CALLOC(1, sizeof(ANTLR3_TRIE_ENTRY));
2124 if (newEnt == NULL)
2125 {
2126 /* Out of memory, all we can do is return the fact that the insert failed.
2127 */
2128 return ANTLR3_FALSE;
2129 }
2131 /* Otherwise enter this in our new node
2132 */
2133 newEnt->type = type;
2134 newEnt->freeptr = freeptr;
2135 if (type == ANTLR3_HASH_TYPE_STR)
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;
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 }
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 }
2178 /* Et voila
2179 */
2180 trie->count++;
2181 return ANTLR3_TRUE;
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 */
2188 static void
2189 freeIntNode(pANTLR3_INT_TRIE_NODE node)
2190 {
2191 pANTLR3_TRIE_ENTRY thisEntry;
2192 pANTLR3_TRIE_ENTRY nextEntry;
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 }
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 }
2214 /* Now all the children are dealt with, we can destroy
2215 * this node too
2216 */
2217 thisEntry = node->buckets;
2219 while (thisEntry != NULL)
2220 {
2221 nextEntry = thisEntry->next;
2223 /* Do we need to call a custom free pointer for this string entry?
2224 */
2225 if (thisEntry->type == ANTLR3_HASH_TYPE_STR && thisEntry->freeptr != NULL)
2226 {
2227 thisEntry->freeptr(thisEntry->data.ptr);
2228 }
2230 /* Now free the data for this bucket entry
2231 */
2232 ANTLR3_FREE(thisEntry);
2233 thisEntry = nextEntry; /* See if there are any more to free */
2234 }
2236 /* The bucket entry is now gone, so we can free the memory for
2237 * the entry itself.
2238 */
2239 ANTLR3_FREE(node);
2241 /* And that should be it for everything under this node and itself
2242 */
2243 }
2245 /** Called to free all nodes and the structure itself.
2246 */
2247 static void
2248 intTrieFree (pANTLR3_INT_TRIE trie)
2249 {
2250 /* Descend from the root and free all the nodes
2251 */
2252 freeIntNode(trie->root);
2254 /* the nodes are all gone now, so we need only free the memory
2255 * for the structure itself
2256 */
2257 ANTLR3_FREE(trie);
2258 }
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
2271 pANTLR3_TOPO topo;
2272 topo = antlr3NewTopo();
2274 if (topo == NULL) { out of memory }
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)
2280 * /verbatim
2281 */
2282 ANTLR3_API pANTLR3_TOPO
2283 antlr3TopoNew()
2284 {
2285 pANTLR3_TOPO topo = (pANTLR3_TOPO)ANTLR3_MALLOC(sizeof(ANTLR3_TOPO));
2287 if (topo == NULL)
2288 {
2289 return NULL;
2290 }
2292 // Initialize variables
2293 //
2295 topo->visited = NULL; // Don't know how big it is yet
2296 topo->limit = 1; // No edges added yet
2297 topo->edges = NULL; // No edges added yet
2298 topo->sorted = NULL; // Nothing sorted at the start
2299 topo->cycle = NULL; // No cycles at the start
2300 topo->cycleMark = 0; // No cycles at the start
2301 topo->hasCycle = ANTLR3_FALSE; // No cycle at the start
2303 // API
2304 //
2305 topo->addEdge = addEdge;
2306 topo->sortToArray = sortToArray;
2307 topo->sortVector = sortVector;
2308 topo->free = freeTopo;
2310 return topo;
2311 }
2312 // Topological sorter
2313 //
2314 static void
2315 addEdge (pANTLR3_TOPO topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency)
2316 {
2317 ANTLR3_UINT32 i;
2318 ANTLR3_UINT32 maxEdge;
2319 pANTLR3_BITSET edgeDeps;
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 //
2333 // First see if we have enough room in the edges array to add the edge?
2334 //
2335 if (topo->edges == NULL)
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);
2340 if (topo->edges == NULL)
2341 {
2342 return;
2343 }
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));
2354 if (topo->edges == NULL)
2355 {
2356 return;
2357 }
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;
2364 }
2366 // Set the limit to what we have now
2367 //
2368 topo->limit = maxEdge + 1;
2369 }
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 }
2380 // Pick up the bit map for the requested edge
2381 //
2382 edgeDeps = *((topo->edges) + edge);
2384 if (edgeDeps == NULL)
2385 {
2386 // No edges are defined yet for this node
2387 //
2388 edgeDeps = antlr3BitsetNew(0);
2389 *((topo->edges) + edge) = edgeDeps;
2390 if (edgeDeps == NULL )
2391 {
2392 return; // Out of memory
2393 }
2394 }
2396 // Set the bit in the bitmap that corresponds to the requested
2397 // dependency.
2398 //
2399 edgeDeps->add(edgeDeps, dependency);
2401 // And we are all set
2402 //
2403 return;
2404 }
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 */
2413 static void
2414 DFS(pANTLR3_TOPO topo, ANTLR3_UINT32 node)
2415 {
2416 pANTLR3_BITSET edges;
2418 // Guard against a revisit and check for cycles
2419 //
2420 if (topo->hasCycle == ANTLR3_TRUE)
2421 {
2422 return; // We don't do anything else if we found a cycle
2423 }
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;
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;
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 }
2447 // Recalculate the limit
2448 //
2449 topo->cycleMark -= i;
2451 // Signal disaster
2452 //
2453 topo->hasCycle = ANTLR3_TRUE;
2454 }
2455 }
2456 return;
2457 }
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;
2466 // First flag that we have visited this node
2467 //
2468 topo->visited->add(topo->visited, node);
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)
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;
2484 numBits = edges->numBits(edges);
2485 range = edges->size(edges); // Number of set bits
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
2497 // Found an edge, make sure we visit and descend it
2498 //
2499 DFS(topo, i);
2500 }
2501 }
2502 }
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;
2511 // Remove this node from the cycle list if we have not detected a cycle
2512 //
2513 if (topo->hasCycle == ANTLR3_FALSE)
2514 {
2515 topo->cycleMark--;
2516 }
2518 return;
2519 }
2521 static pANTLR3_UINT32
2522 sortToArray (pANTLR3_TOPO topo)
2523 {
2524 ANTLR3_UINT32 v;
2525 ANTLR3_UINT32 oldLimit;
2527 // Guard against being called with no edges defined
2528 //
2529 if (topo->edges == NULL)
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));
2538 topo->cycle = ANTLR3_MALLOC(topo->limit * sizeof(ANTLR3_UINT32));
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);
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
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_FALSE)
2560 {
2561 // We have not visited this one so descend it
2562 //
2563 DFS(topo, v);
2564 }
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_TRUE)
2570 {
2571 break;
2572 }
2573 }
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;
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 }
2589 static void
2590 sortVector (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;
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;
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 }
2617 if (topo->hasCycle == ANTLR3_TRUE)
2618 {
2619 return; // Do nothing if we detected a cycle
2620 }
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));
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 }
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;
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 }
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);
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 }
2684 // Having traversed all the entries, we have sorted the vector in place.
2685 //
2686 ANTLR3_FREE(vIndex);
2687 return;
2688 }
2690 static void
2691 freeTopo (pANTLR3_TOPO topo)
2692 {
2693 ANTLR3_UINT32 i;
2695 // Free the result vector
2696 //
2697 if (topo->sorted != NULL)
2698 {
2699 ANTLR3_FREE(topo->sorted);
2700 topo->sorted = NULL;
2701 }
2703 // Free the visited map
2704 //
2705 if (topo->visited != NULL)
2706 {
2708 topo->visited->free(topo->visited);
2709 topo->visited = NULL;
2710 }
2712 // Free any edgemaps
2713 //
2714 if (topo->edges != NULL)
2715 {
2716 pANTLR3_BITSET edgeList;
2719 for (i=0; i<topo->limit; i++)
2720 {
2721 edgeList = *((topo->edges) + i);
2722 if (edgeList != NULL)
2723 {
2724 edgeList->free(edgeList);
2725 }
2726 }
2728 ANTLR3_FREE(topo->edges);
2729 }
2730 topo->edges = NULL;
2732 // Free any cycle map
2733 //
2734 if (topo->cycle != NULL)
2735 {
2736 ANTLR3_FREE(topo->cycle);
2737 }
2739 ANTLR3_FREE(topo);
2740 }