bundles/org.simantics.databoard/cpp/DataBoardTest/libantlr3c-3.2/src/antlr3collections.c

   1 /// \file
   2 /// Provides a number of useful functions that are roughly equivalent
   3 /// to java HashTable and List for the purposes of Antlr 3 C runtime.
   4 /// Also useable by the C programmer for things like symbol tables pointers
   5 /// and so on.
   6 ///
   7 ///
   8
   9 // [The "BSD licence"]
  10 // Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC
  11 // http://www.temporal-wave.com
  12 // http://www.linkedin.com/in/jimidle
  13 //
  14 // All rights reserved.
  15 //
  16 // Redistribution and use in source and binary forms, with or without
  17 // modification, are permitted provided that the following conditions
  18 // are met:
  19 // 1. Redistributions of source code must retain the above copyright
  20 //    notice, this list of conditions and the following disclaimer.
  21 // 2. Redistributions in binary form must reproduce the above copyright
  22 //    notice, this list of conditions and the following disclaimer in the
  23 //    documentation and/or other materials provided with the distribution.
  24 // 3. The name of the author may not be used to endorse or promote products
  25 //    derived from this software without specific prior written permission.
  26 //
  27 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  28 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  29 // OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  30 // IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  31 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  32 // NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  33 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  34 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  35 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  36 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  37
  38 #include    <antlr3.h>
  39
  40 #include "antlr3collections.h"
  41
  42 // Interface functions for hash table
  43 //
  44
  45 // String based keys
  46 //
  47 static void                                     antlr3HashDelete    (pANTLR3_HASH_TABLE table, void * key);
  48 static void *                           antlr3HashGet   (pANTLR3_HASH_TABLE table, void * key);
  49 static pANTLR3_HASH_ENTRY   antlr3HashRemove    (pANTLR3_HASH_TABLE table, void * key);
  50 static ANTLR3_INT32                     antlr3HashPut   (pANTLR3_HASH_TABLE table, void * key, void * element, void (ANTLR3_CDECL *freeptr)(void *));
  51
  52 // Integer based keys (Lists and so on)
  53 //
  54 static void                                     antlr3HashDeleteI   (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key);
  55 static void *                           antlr3HashGetI  (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key);
  56 static pANTLR3_HASH_ENTRY   antlr3HashRemoveI   (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key);
  57 static ANTLR3_INT32                     antlr3HashPutI  (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *));
  58
  59 static void                                     antlr3HashFree  (pANTLR3_HASH_TABLE table);
  60 static ANTLR3_UINT32        antlr3HashSize      (pANTLR3_HASH_TABLE table);
  61
  62 // -----------
  63
  64 // Interface functions for enumeration
  65 //
  66 static int          antlr3EnumNext          (pANTLR3_HASH_ENUM en, pANTLR3_HASH_KEY * key, void ** data);
  67 static void         antlr3EnumFree          (pANTLR3_HASH_ENUM en);
  68
  69 // Interface functions for List
  70 //
  71 static void                             antlr3ListFree  (pANTLR3_LIST list);
  72 static void                             antlr3ListDelete(pANTLR3_LIST list, ANTLR3_INTKEY key);
  73 static void *                   antlr3ListGet   (pANTLR3_LIST list, ANTLR3_INTKEY key);
  74 static ANTLR3_INT32             antlr3ListPut   (pANTLR3_LIST list, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *));
  75 static ANTLR3_INT32             antlr3ListAdd   (pANTLR3_LIST list, void * element, void (ANTLR3_CDECL *freeptr)(void *));
  76 static void *                   antlr3ListRemove(pANTLR3_LIST list, ANTLR3_INTKEY key);
  77 static ANTLR3_UINT32    antlr3ListSize  (pANTLR3_LIST list);
  78
  79 // Interface functions for Stack
  80 //
  81 static void                             antlr3StackFree (pANTLR3_STACK  stack);
  82 static void *                   antlr3StackPop  (pANTLR3_STACK  stack);
  83 static void *                   antlr3StackGet  (pANTLR3_STACK  stack, ANTLR3_INTKEY key);
  84 static ANTLR3_BOOLEAN   antlr3StackPush (pANTLR3_STACK  stack, void * element, void (ANTLR3_CDECL *freeptr)(void *));
  85 static ANTLR3_UINT32    antlr3StackSize (pANTLR3_STACK  stack);
  86 static void *                   antlr3StackPeek (pANTLR3_STACK  stack);
  87
  88 // Interface functions for vectors
  89 //
  90 static  void ANTLR3_CDECL       antlr3VectorFree        (pANTLR3_VECTOR vector);
  91 static  void                            antlr3VectorDel         (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry);
  92 static  void *                          antlr3VectorGet         (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry);
  93 static  void *                          antrl3VectorRemove      (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry);
  94 static  void                            antlr3VectorClear       (pANTLR3_VECTOR vector);
  95 static  ANTLR3_UINT32           antlr3VectorAdd         (pANTLR3_VECTOR vector, void * element, void (ANTLR3_CDECL *freeptr)(void *));
  96 static  ANTLR3_UINT32           antlr3VectorSet         (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry, void * element, void (ANTLR3_CDECL *freeptr)(void *), ANTLR3_BOOLEAN freeExisting);
  97 static  ANTLR3_UINT32           antlr3VectorSize    (pANTLR3_VECTOR vector);
  98 static  ANTLR3_BOOLEAN      antlr3VectorSwap    (pANTLR3_VECTOR vector, ANTLR3_UINT32 entry1, ANTLR3_UINT32 entry2);
  99
 100 static  void                newPool             (pANTLR3_VECTOR_FACTORY factory);
 101 static  void                            closeVectorFactory  (pANTLR3_VECTOR_FACTORY factory);
 102 static  pANTLR3_VECTOR          newVector                       (pANTLR3_VECTOR_FACTORY factory);
 103 static  void                            returnVector            (pANTLR3_VECTOR_FACTORY factory, pANTLR3_VECTOR vector);
 104
 105
 106 // Interface functions for int TRIE
 107 //
 108 static  pANTLR3_TRIE_ENTRY      intTrieGet              (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key);
 109 static  ANTLR3_BOOLEAN          intTrieDel              (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key);
 110 static  ANTLR3_BOOLEAN          intTrieAdd              (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key, ANTLR3_UINT32 type, ANTLR3_INTKEY intType, void * data, void (ANTLR3_CDECL *freeptr)(void *));
 111 static  void                            intTrieFree             (pANTLR3_INT_TRIE trie);
 112
 113
 114 // Interface functions for topological sorter
 115 //
 116 static  void            addEdge          (pANTLR3_TOPO topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency);
 117 static  pANTLR3_UINT32  sortToArray      (pANTLR3_TOPO topo);
 118 static  void            sortVector       (pANTLR3_TOPO topo, pANTLR3_VECTOR v);
 119 static  void            freeTopo         (pANTLR3_TOPO topo);
 120
 121 // Local function to advance enumeration structure pointers
 122 //
 123 static void antlr3EnumNextEntry(pANTLR3_HASH_ENUM en);
 124
 125 pANTLR3_HASH_TABLE
 126 antlr3HashTableNew(ANTLR3_UINT32 sizeHint)
 127 {
 128         // All we have to do is create the hashtable tracking structure
 129         // and allocate memory for the requested number of buckets.
 130         //
 131         pANTLR3_HASH_TABLE      table;
 132
 133         ANTLR3_UINT32   bucket; // Used to traverse the buckets
 134
 135         table   = ANTLR3_MALLOC(sizeof(ANTLR3_HASH_TABLE));
 136
 137         // Error out if no memory left
 138         if      (table  == NULL)
 139         {
 140                 return  NULL;
 141         }
 142
 143         // Allocate memory for the buckets
 144         //
 145         table->buckets = (pANTLR3_HASH_BUCKET) ANTLR3_MALLOC((size_t) (sizeof(ANTLR3_HASH_BUCKET) * sizeHint));
 146
 147         if      (table->buckets == NULL)
 148         {
 149                 ANTLR3_FREE((void *)table);
 150                 return  NULL;
 151         }
 152
 153         // Modulo of the table, (bucket count).
 154         //
 155         table->modulo   = sizeHint;
 156
 157         table->count    = 0;        /* Nothing in there yet ( I hope)   */
 158
 159         /* Initialize the buckets to empty
 160         */
 161         for     (bucket = 0; bucket < sizeHint; bucket++)
 162         {
 163                 table->buckets[bucket].entries = NULL;
 164         }
 165
 166         /* Exclude duplicate entries by default
 167         */
 168         table->allowDups        = ANTLR3_FALSE;
 169
 170     /* Assume that keys should by strduped before they are
 171      * entered in the table.
 172      */
 173     table->doStrdup     = ANTLR3_TRUE;
 174
 175         /* Install the interface
 176         */
 177
 178         table->get              =  antlr3HashGet;
 179         table->put              =  antlr3HashPut;
 180         table->del              =  antlr3HashDelete;
 181         table->remove   =  antlr3HashRemove;
 182
 183         table->getI             =  antlr3HashGetI;
 184         table->putI             =  antlr3HashPutI;
 185         table->delI             =  antlr3HashDeleteI;
 186         table->removeI  =  antlr3HashRemoveI;
 187
 188         table->size             =  antlr3HashSize;
 189         table->free             =  antlr3HashFree;
 190
 191         return  table;
 192 }
 193
 194 static void
 195 antlr3HashFree(pANTLR3_HASH_TABLE table)
 196 {
 197     ANTLR3_UINT32       bucket; /* Used to traverse the buckets */
 198
 199     pANTLR3_HASH_BUCKET thisBucket;
 200     pANTLR3_HASH_ENTRY  entry;
 201     pANTLR3_HASH_ENTRY  nextEntry;
 202
 203     /* Free the table, all buckets and all entries, and all the
 204      * keys and data (if the table exists)
 205      */
 206     if  (table  != NULL)
 207     {
 208         for     (bucket = 0; bucket < table->modulo; bucket++)
 209         {
 210             thisBucket  = &(table->buckets[bucket]);
 211
 212             /* Allow sparse tables, though we don't create them as such at present
 213              */
 214             if  ( thisBucket != NULL)
 215             {
 216                 entry   = thisBucket->entries;
 217
 218                 /* Search all entries in the bucket and free them up
 219                  */
 220                 while   (entry != NULL)
 221                 {
 222                     /* Save next entry - we do not want to access memory in entry after we
 223                      * have freed it.
 224                      */
 225                     nextEntry   = entry->nextEntry;
 226
 227                     /* Free any data pointer, this only happens if the user supplied
 228                      * a pointer to a routine that knwos how to free the structure they
 229                      * added to the table.
 230                      */
 231                     if  (entry->free != NULL)
 232                     {
 233                         entry->free(entry->data);
 234                     }
 235
 236                     /* Free the key memory - we know that we allocated this
 237                      */
 238                     if  (entry->keybase.type == ANTLR3_HASH_TYPE_STR && entry->keybase.key.sKey != NULL)
 239                     {
 240                         ANTLR3_FREE(entry->keybase.key.sKey);
 241                     }
 242
 243                     /* Free this entry
 244                      */
 245                     ANTLR3_FREE(entry);
 246                     entry   = nextEntry;    /* Load next pointer to see if we shoud free it */
 247                 }
 248                 /* Invalidate the current pointer
 249                  */
 250                 thisBucket->entries = NULL;
 251             }
 252         }
 253
 254         /* Now we can free the bucket memory
 255          */
 256         ANTLR3_FREE(table->buckets);
 257     }
 258
 259     /* Now we free teh memory for the table itself
 260      */
 261     ANTLR3_FREE(table);
 262 }
 263
 264 /** return the current size of the hash table
 265  */
 266 static ANTLR3_UINT32    antlr3HashSize      (pANTLR3_HASH_TABLE table)
 267 {
 268     return  table->count;
 269 }
 270
 271 /** Remove a numeric keyed entry from a hash table if it exists,
 272  *  no error if it does not exist.
 273  */
 274 static pANTLR3_HASH_ENTRY   antlr3HashRemoveI   (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key)
 275 {
 276     ANTLR3_UINT32           hash;
 277     pANTLR3_HASH_BUCKET     bucket;
 278     pANTLR3_HASH_ENTRY      entry;
 279     pANTLR3_HASH_ENTRY      * nextPointer;
 280
 281     /* First we need to know the hash of the provided key
 282      */
 283     hash    = (ANTLR3_UINT32)(key % (ANTLR3_INTKEY)(table->modulo));
 284
 285     /* Knowing the hash, we can find the bucket
 286      */
 287     bucket  = table->buckets + hash;
 288
 289     /* Now, we traverse the entries in the bucket until
 290      * we find the key or the end of the entries in the bucket.
 291      * We track the element prior to the one we are examining
 292      * as we need to set its next pointer to the next pointer
 293      * of the entry we are deleting (if we find it).
 294      */
 295     entry           =   bucket->entries;    /* Entry to examine                                     */
 296     nextPointer     = & bucket->entries;    /* Where to put the next pointer of the deleted entry   */
 297
 298     while   (entry != NULL)
 299     {
 300         /* See if this is the entry we wish to delete
 301          */
 302         if  (entry->keybase.key.iKey == key)
 303         {
 304             /* It was the correct entry, so we set the next pointer
 305              * of the previous entry to the next pointer of this
 306              * located one, which takes it out of the chain.
 307              */
 308             (*nextPointer)              = entry->nextEntry;
 309
 310             table->count--;
 311
 312             return entry;
 313         }
 314         else
 315         {
 316             /* We found an entry but it wasn't the one that was wanted, so
 317              * move to the next one, if any.
 318              */
 319             nextPointer = & (entry->nextEntry);     /* Address of the next pointer in the current entry     */
 320             entry       = entry->nextEntry;         /* Address of the next element in the bucket (if any)   */
 321         }
 322     }
 323
 324     return NULL;  /* Not found */
 325 }
 326
 327 /** Remove the element in the hash table for a particular
 328  *  key value, if it exists - no error if it does not.
 329  */
 330 static pANTLR3_HASH_ENTRY
 331 antlr3HashRemove(pANTLR3_HASH_TABLE table, void * key)
 332 {
 333     ANTLR3_UINT32           hash;
 334     pANTLR3_HASH_BUCKET     bucket;
 335     pANTLR3_HASH_ENTRY      entry;
 336     pANTLR3_HASH_ENTRY      * nextPointer;
 337
 338     /* First we need to know the hash of the provided key
 339      */
 340     hash    = antlr3Hash(key, (ANTLR3_UINT32)strlen((const char *)key));
 341
 342     /* Knowing the hash, we can find the bucket
 343      */
 344     bucket  = table->buckets + (hash % table->modulo);
 345
 346     /* Now, we traverse the entries in the bucket until
 347      * we find the key or the end of the entires in the bucket.
 348      * We track the element prior to the one we are exmaining
 349      * as we need to set its next pointer to the next pointer
 350      * of the entry we are deleting (if we find it).
 351      */
 352     entry           =   bucket->entries;    /* Entry to examine                                     */
 353     nextPointer     = & bucket->entries;    /* Where to put the next pointer of the deleted entry   */
 354
 355     while   (entry != NULL)
 356     {
 357         /* See if this is the entry we wish to delete
 358          */
 359         if  (strcmp((const char *)key, (const char *)entry->keybase.key.sKey) == 0)
 360         {
 361             /* It was the correct entry, so we set the next pointer
 362              * of the previous entry to the next pointer of this
 363              * located one, which takes it out of the chain.
 364              */
 365             (*nextPointer)              = entry->nextEntry;
 366
 367             /* Release the key - if we allocated that
 368              */
 369         if (table->doStrdup == ANTLR3_TRUE)
 370         {
 371             ANTLR3_FREE(entry->keybase.key.sKey);
 372         }
 373             entry->keybase.key.sKey     = NULL;
 374
 375             table->count--;
 376
 377             return entry;
 378         }
 379         else
 380         {
 381             /* We found an entry but it wasn't the one that was wanted, so
 382              * move to the next one, if any.
 383              */
 384             nextPointer = & (entry->nextEntry);     /* Address of the next pointer in the current entry     */
 385             entry       = entry->nextEntry;         /* Address of the next element in the bucket (if any)   */
 386         }
 387     }
 388
 389     return NULL;  /* Not found */
 390 }
 391
 392 /** Takes the element with the supplied key out of the list, and deletes the data
 393  *  calling the supplied free() routine if any.
 394  */
 395 static void
 396 antlr3HashDeleteI    (pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key)
 397 {
 398     pANTLR3_HASH_ENTRY  entry;
 399
 400     entry = antlr3HashRemoveI(table, key);
 401
 402     /* Now we can free the elements and the entry in order
 403      */
 404     if  (entry != NULL && entry->free != NULL)
 405     {
 406         /* Call programmer supplied function to release this entry data
 407          */
 408         entry->free(entry->data);
 409         entry->data = NULL;
 410     }
 411     /* Finally release the space for this entry block.
 412      */
 413     ANTLR3_FREE(entry);
 414 }
 415
 416 /** Takes the element with the supplied key out of the list, and deletes the data
 417  *  calling the supplied free() routine if any.
 418  */
 419 static void
 420 antlr3HashDelete    (pANTLR3_HASH_TABLE table, void * key)
 421 {
 422     pANTLR3_HASH_ENTRY  entry;
 423
 424     entry = antlr3HashRemove(table, key);
 425
 426     /* Now we can free the elements and the entry in order
 427      */
 428     if  (entry != NULL && entry->free != NULL)
 429     {
 430         /* Call programmer supplied function to release this entry data
 431          */
 432         entry->free(entry->data);
 433         entry->data = NULL;
 434     }
 435     /* Finally release the space for this entry block.
 436      */
 437     ANTLR3_FREE(entry);
 438 }
 439
 440 /** Return the element pointer in the hash table for a particular
 441  *  key value, or NULL if it don't exist (or was itself NULL).
 442  */
 443 static void *
 444 antlr3HashGetI(pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key)
 445 {
 446     ANTLR3_UINT32           hash;
 447     pANTLR3_HASH_BUCKET     bucket;
 448     pANTLR3_HASH_ENTRY      entry;
 449
 450     /* First we need to know the hash of the provided key
 451      */
 452     hash    = (ANTLR3_UINT32)(key % (ANTLR3_INTKEY)(table->modulo));
 453
 454     /* Knowing the hash, we can find the bucket
 455      */
 456     bucket  = table->buckets + hash;
 457
 458     /* Now we can inspect the key at each entry in the bucket
 459      * and see if we have a match.
 460      */
 461     entry   = bucket->entries;
 462
 463     while   (entry != NULL)
 464     {
 465         if  (entry->keybase.key.iKey == key)
 466         {
 467             /* Match was found, return the data pointer for this entry
 468              */
 469             return  entry->data;
 470         }
 471         entry = entry->nextEntry;
 472     }
 473
 474     /* If we got here, then we did not find the key
 475      */
 476     return  NULL;
 477 }
 478
 479 /** Return the element pointer in the hash table for a particular
 480  *  key value, or NULL if it don't exist (or was itself NULL).
 481  */
 482 static void *
 483 antlr3HashGet(pANTLR3_HASH_TABLE table, void * key)
 484 {
 485     ANTLR3_UINT32           hash;
 486     pANTLR3_HASH_BUCKET     bucket;
 487     pANTLR3_HASH_ENTRY      entry;
 488
 489
 490     /* First we need to know the hash of the provided key
 491      */
 492     hash    = antlr3Hash(key, (ANTLR3_UINT32)strlen((const char *)key));
 493
 494     /* Knowing the hash, we can find the bucket
 495      */
 496     bucket  = table->buckets + (hash % table->modulo);
 497
 498     /* Now we can inspect the key at each entry in the bucket
 499      * and see if we have a match.
 500      */
 501     entry   = bucket->entries;
 502
 503     while   (entry != NULL)
 504     {
 505         if  (strcmp((const char *)key, (const char *)entry->keybase.key.sKey) == 0)
 506         {
 507             /* Match was found, return the data pointer for this entry
 508              */
 509             return  entry->data;
 510         }
 511         entry = entry->nextEntry;
 512     }
 513
 514     /* If we got here, then we did not find the key
 515      */
 516     return  NULL;
 517 }
 518
 519 /** Add the element pointer in to the table, based upon the
 520  *  hash of the provided key.
 521  */
 522 static  ANTLR3_INT32
 523 antlr3HashPutI(pANTLR3_HASH_TABLE table, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *))
 524 {
 525         ANTLR3_UINT32       hash;
 526         pANTLR3_HASH_BUCKET         bucket;
 527         pANTLR3_HASH_ENTRY          entry;
 528         pANTLR3_HASH_ENTRY          * newPointer;
 529
 530         /* First we need to know the hash of the provided key
 531         */
 532         hash    = (ANTLR3_UINT32)(key % (ANTLR3_INTKEY)(table->modulo));
 533
 534         /* Knowing the hash, we can find the bucket
 535         */
 536         bucket  = table->buckets + hash;
 537
 538         /* Knowing the bucket, we can traverse the entries until we
 539         * we find a NULL pointer or we find that this is already
 540         * in the table and duplicates were not allowed.
 541         */
 542         newPointer      = &bucket->entries;
 543
 544         while   (*newPointer !=  NULL)
 545         {
 546                 /* The value at new pointer is pointing to an existing entry.
 547                 * If duplicates are allowed then we don't care what it is, but
 548                 * must reject this add if the key is the same as the one we are
 549                 * supplied with.
 550                 */
 551                 if  (table->allowDups == ANTLR3_FALSE)
 552                 {
 553                         if      ((*newPointer)->keybase.key.iKey == key)
 554                         {
 555                                 return  ANTLR3_ERR_HASHDUP;
 556                         }
 557                 }
 558
 559                 /* Point to the next entry pointer of the current entry we
 560                 * are traversing, if it is NULL we will create our new
 561                 * structure and point this to it.
 562                 */
 563                 newPointer = &((*newPointer)->nextEntry);
 564         }
 565
 566         /* newPointer is now pointing at the pointer where we need to
 567         * add our new entry, so let's crate the entry and add it in.
 568         */
 569         entry   = (pANTLR3_HASH_ENTRY)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_HASH_ENTRY));
 570
 571         if      (entry == NULL)
 572         {
 573                 return  ANTLR3_ERR_NOMEM;
 574         }
 575
 576         entry->data                     = element;              /* Install the data element supplied                    */
 577         entry->free                     = freeptr;              /* Function that knows how to release the entry         */
 578         entry->keybase.type             = ANTLR3_HASH_TYPE_INT; /* Indicate the key type stored here for when we free   */
 579         entry->keybase.key.iKey = key;                  /* Record the key value                                 */
 580         entry->nextEntry                = NULL;                 /* Ensure that the forward pointer ends the chain       */
 581
 582         *newPointer     = entry;    /* Install the next entry in this bucket    */
 583
 584         table->count++;
 585
 586         return  ANTLR3_SUCCESS;
 587 }
 588
 589
 590 /** Add the element pointer in to the table, based upon the
 591  *  hash of the provided key.
 592  */
 593 static  ANTLR3_INT32
 594 antlr3HashPut(pANTLR3_HASH_TABLE table, void * key, void * element, void (ANTLR3_CDECL *freeptr)(void *))
 595 {
 596         ANTLR3_UINT32       hash;
 597         pANTLR3_HASH_BUCKET         bucket;
 598         pANTLR3_HASH_ENTRY          entry;
 599         pANTLR3_HASH_ENTRY          * newPointer;
 600
 601         /* First we need to know the hash of the provided key
 602         */
 603         hash    = antlr3Hash(key, (ANTLR3_UINT32)strlen((const char *)key));
 604
 605         /* Knowing the hash, we can find the bucket
 606         */
 607         bucket  = table->buckets + (hash % table->modulo);
 608
 609         /* Knowign the bucket, we can traverse the entries until we
 610         * we find a NULL pointer ofr we find that this is already
 611         * in the table and duplicates were not allowed.
 612         */
 613         newPointer      = &bucket->entries;
 614
 615         while   (*newPointer !=  NULL)
 616         {
 617                 /* The value at new pointer is pointing to an existing entry.
 618                 * If duplicates are allowed then we don't care what it is, but
 619                 * must reject this add if the key is the same as the one we are
 620                 * supplied with.
 621                 */
 622                 if  (table->allowDups == ANTLR3_FALSE)
 623                 {
 624                         if      (strcmp((const char*) key, (const char *)(*newPointer)->keybase.key.sKey) == 0)
 625                         {
 626                                 return  ANTLR3_ERR_HASHDUP;
 627                         }
 628                 }
 629
 630                 /* Point to the next entry pointer of the current entry we
 631                 * are traversing, if it is NULL we will create our new
 632                 * structure and point this to it.
 633                 */
 634                 newPointer = &((*newPointer)->nextEntry);
 635         }
 636
 637         /* newPointer is now poiting at the pointer where we need to
 638         * add our new entry, so let's crate the entry and add it in.
 639         */
 640         entry   = (pANTLR3_HASH_ENTRY)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_HASH_ENTRY));
 641
 642         if      (entry == NULL)
 643         {
 644                 return  ANTLR3_ERR_NOMEM;
 645         }
 646
 647         entry->data                     = element;                                      /* Install the data element supplied                            */
 648         entry->free                     = freeptr;                                      /* Function that knows how to release the entry     */
 649         entry->keybase.type     = ANTLR3_HASH_TYPE_STR;     /* Indicate the key type stored here for free()         */
 650     if  (table->doStrdup == ANTLR3_TRUE)
 651     {
 652         entry->keybase.key.sKey = ANTLR3_STRDUP(key);   /* Record the key value                                                         */
 653     }
 654     else
 655     {
 656         entry->keybase.key.sKey = key;                  /* Record the key value                                                         */
 657     }
 658         entry->nextEntry                = NULL;                                 /* Ensure that the forward pointer ends the chain   */
 659
 660         *newPointer     = entry;    /* Install the next entry in this bucket    */
 661
 662         table->count++;
 663
 664         return  ANTLR3_SUCCESS;
 665 }
 666
 667 /** \brief Creates an enumeration structure to traverse the hash table.
 668  *
 669  * \param table Table to enumerate
 670  * \return Pointer to enumeration structure.
 671  */
 672 pANTLR3_HASH_ENUM
 673 antlr3EnumNew   (pANTLR3_HASH_TABLE table)
 674 {
 675     pANTLR3_HASH_ENUM   en;
 676
 677     /* Allocate structure memory
 678      */
 679     en    = (pANTLR3_HASH_ENUM) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_HASH_ENUM));
 680
 681     /* Check that the allocation was good
 682      */
 683     if  (en == NULL)
 684     {
 685         return  (pANTLR3_HASH_ENUM) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
 686     }
 687
 688     /* Initialize the start pointers
 689     */
 690     en->table   = table;
 691     en->bucket  = 0;                            /* First bucket             */
 692     en->entry   = en->table->buckets->entries;  /* First entry to return    */
 693
 694     /* Special case in that the first bucket may not have anything in it
 695      * but the antlr3EnumNext() function expects that the en->entry is
 696      * set to the next valid pointer. Hence if it is not a valid element
 697      * pointer, attempt to find the next one that is, (table may be empty
 698      * of course.
 699      */
 700     if  (en->entry == NULL)
 701     {
 702         antlr3EnumNextEntry(en);
 703     }
 704
 705     /* Install the interface
 706      */
 707     en->free    =  antlr3EnumFree;
 708     en->next    =  antlr3EnumNext;
 709
 710     /* All is good
 711      */
 712     return  en;
 713 }
 714
 715 /** \brief Return the next entry in the hashtable being traversed by the supplied
 716  *         enumeration.
 717  *
 718  * \param[in] en Pointer to the enumeration tracking structure
 719  * \param key    Pointer to void pointer, where the key pointer is returned.
 720  * \param data   Pointer to void pointer where the data pointer is returned.
 721  * \return
 722  *      - ANTLR3_SUCCESS if there was a next key
 723  *      - ANTLR3_FAIL    if there were no more keys
 724  *
 725  * \remark
 726  *  No checking of input structure is performed!
 727  */
 728 static int
 729 antlr3EnumNext  (pANTLR3_HASH_ENUM en, pANTLR3_HASH_KEY * key, void ** data)
 730 {
 731     /* If the current entry is valid, then use it
 732      */
 733     if  (en->bucket >= en->table->modulo)
 734     {
 735         /* Already exhausted the table
 736          */
 737         return  ANTLR3_FAIL;
 738     }
 739
 740     /* Pointers are already set to the current entry to return, or
 741      * we would not be at this point in the logic flow.
 742      */
 743     *key        = &(en->entry->keybase);
 744     *data       = en->entry->data;
 745
 746     /* Return pointers are set up, so now we move the element
 747      * pointer to the next in the table (if any).
 748      */
 749     antlr3EnumNextEntry(en);
 750
 751     return      ANTLR3_SUCCESS;
 752 }
 753
 754 /** \brief Local function to advance the entry pointer of an enumeration
 755  * structure to the next valid entry (if there is one).
 756  *
 757  * \param[in] enum Pointer to ANTLR3 enumeration structure returned by antlr3EnumNew()
 758  *
 759  * \remark
 760  *   - The function always leaves the pointers pointing at a valid entry if there
 761  *     is one, so if the entry pointer is NULL when this function exits, there were
 762  *     no more entries in the table.
 763  */
 764 static void
 765 antlr3EnumNextEntry(pANTLR3_HASH_ENUM en)
 766 {
 767     pANTLR3_HASH_BUCKET bucket;
 768
 769     /* See if the current entry pointer is valid first of all
 770      */
 771     if  (en->entry != NULL)
 772     {
 773         /* Current entry was a valid point, see if there is another
 774          * one in the chain.
 775          */
 776         if  (en->entry->nextEntry != NULL)
 777         {
 778             /* Next entry in the enumeration is just the next entry
 779              * in the chain.
 780              */
 781             en->entry = en->entry->nextEntry;
 782             return;
 783         }
 784     }
 785
 786     /* There were no more entries in the current bucket, if there are
 787      * more buckets then chase them until we find an entry.
 788      */
 789     en->bucket++;
 790
 791     while   (en->bucket < en->table->modulo)
 792     {
 793         /* There was one more bucket, see if it has any elements in it
 794          */
 795         bucket  = en->table->buckets + en->bucket;
 796
 797         if  (bucket->entries != NULL)
 798         {
 799             /* There was an entry in this bucket, so we can use it
 800              * for the next entry in the enumeration.
 801              */
 802             en->entry   = bucket->entries;
 803             return;
 804         }
 805
 806         /* There was nothing in the bucket we just examined, move to the
 807          * next one.
 808          */
 809         en->bucket++;
 810     }
 811
 812     /* Here we have exhausted all buckets and the enumeration pointer will
 813      * have its bucket count = table->modulo which signifies that we are done.
 814      */
 815 }
 816
 817 /** \brief Frees up the memory structures that represent a hash table
 818  *  enumeration.
 819  * \param[in] enum Pointer to ANTLR3 enumeration structure returned by antlr3EnumNew()
 820  */
 821 static void
 822 antlr3EnumFree  (pANTLR3_HASH_ENUM en)
 823 {
 824     /* Nothing to check, we just free it.
 825      */
 826     ANTLR3_FREE(en);
 827 }
 828
 829 /** Given an input key of arbitrary length, return a hash value of
 830  *  it. This can then be used (with suitable modulo) to index other
 831  *  structures.
 832  */
 833 ANTLR3_API ANTLR3_UINT32
 834 antlr3Hash(void * key, ANTLR3_UINT32 keylen)
 835 {
 836     /* Accumulate the hash value of the key
 837      */
 838     ANTLR3_UINT32   hash;
 839     pANTLR3_UINT8   keyPtr;
 840     ANTLR3_UINT32   i1;
 841
 842     hash    = 0;
 843     keyPtr  = (pANTLR3_UINT8) key;
 844
 845     /* Iterate the key and accumulate the hash
 846      */
 847     while(keylen > 0)
 848     {
 849         hash = (hash << 4) + (*(keyPtr++));
 850
 851         if ((i1=hash&0xf0000000) != 0)
 852         {
 853                 hash = hash ^ (i1 >> 24);
 854                 hash = hash ^ i1;
 855         }
 856         keylen--;
 857     }
 858
 859     return  hash;
 860 }
 861
 862 ANTLR3_API  pANTLR3_LIST
 863 antlr3ListNew   (ANTLR3_UINT32 sizeHint)
 864 {
 865     pANTLR3_LIST    list;
 866
 867     /* Allocate memory
 868      */
 869     list    = (pANTLR3_LIST)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_LIST));
 870
 871     if  (list == NULL)
 872     {
 873         return  (pANTLR3_LIST)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
 874     }
 875
 876     /* Now we need to add a new table
 877      */
 878     list->table = antlr3HashTableNew(sizeHint);
 879
 880     if  (list->table == (pANTLR3_HASH_TABLE)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM))
 881     {
 882         return  (pANTLR3_LIST)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
 883     }
 884
 885     /* Allocation was good, install interface
 886      */
 887     list->free      =  antlr3ListFree;
 888     list->del       =  antlr3ListDelete;
 889     list->get       =  antlr3ListGet;
 890     list->add       =  antlr3ListAdd;
 891     list->remove    =  antlr3ListRemove;
 892     list->put       =  antlr3ListPut;
 893     list->size      =  antlr3ListSize;
 894
 895     return  list;
 896 }
 897
 898 static ANTLR3_UINT32    antlr3ListSize      (pANTLR3_LIST list)
 899 {
 900     return  list->table->size(list->table);
 901 }
 902
 903 static void
 904 antlr3ListFree  (pANTLR3_LIST list)
 905 {
 906     /* Free the hashtable that stores the list
 907      */
 908     list->table->free(list->table);
 909
 910     /* Free the allocation for the list itself
 911      */
 912     ANTLR3_FREE(list);
 913 }
 914
 915 static void
 916 antlr3ListDelete    (pANTLR3_LIST list, ANTLR3_INTKEY key)
 917 {
 918     list->table->delI(list->table, key);
 919 }
 920
 921 static void *
 922 antlr3ListGet       (pANTLR3_LIST list, ANTLR3_INTKEY key)
 923 {
 924     return list->table->getI(list->table, key);
 925 }
 926
 927 /** Add the supplied element to the list, at the next available key
 928  */
 929 static ANTLR3_INT32     antlr3ListAdd   (pANTLR3_LIST list, void * element, void (ANTLR3_CDECL *freeptr)(void *))
 930 {
 931     ANTLR3_INTKEY   key;
 932
 933     key     = list->table->size(list->table) + 1;
 934     return list->put(list, key, element, freeptr);
 935 }
 936
 937 /** Remove from the list, but don't free the element, just send it back to the
 938  *  caller.
 939  */
 940 static  void *
 941 antlr3ListRemove            (pANTLR3_LIST list, ANTLR3_INTKEY key)
 942 {
 943     pANTLR3_HASH_ENTRY      entry;
 944
 945     entry = list->table->removeI(list->table, key);
 946
 947     if  (entry != NULL)
 948     {
 949         return  entry->data;
 950     }
 951     else
 952     {
 953         return  NULL;
 954     }
 955 }
 956
 957 static  ANTLR3_INT32
 958 antlr3ListPut       (pANTLR3_LIST list, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *))
 959 {
 960     return  list->table->putI(list->table, key, element, freeptr);
 961 }
 962
 963 ANTLR3_API  pANTLR3_STACK
 964 antlr3StackNew  (ANTLR3_UINT32 sizeHint)
 965 {
 966     pANTLR3_STACK   stack;
 967
 968     /* Allocate memory
 969      */
 970     stack    = (pANTLR3_STACK)ANTLR3_MALLOC((size_t)sizeof(ANTLR3_STACK));
 971
 972     if  (stack == NULL)
 973     {
 974         return  (pANTLR3_STACK)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
 975     }
 976
 977     /* Now we need to add a new table
 978      */
 979     stack->vector   = antlr3VectorNew(sizeHint);
 980     stack->top      = NULL;
 981
 982     if  (stack->vector == (pANTLR3_VECTOR)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM))
 983     {
 984         return  (pANTLR3_STACK)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
 985     }
 986
 987     /* Looks good, now add the interface
 988      */
 989     stack->get  =  antlr3StackGet;
 990     stack->free =  antlr3StackFree;
 991     stack->pop  =  antlr3StackPop;
 992     stack->push =  antlr3StackPush;
 993     stack->size =  antlr3StackSize;
 994     stack->peek =  antlr3StackPeek;
 995
 996     return  stack;
 997 }
 998
 999 static ANTLR3_UINT32    antlr3StackSize     (pANTLR3_STACK stack)
1000 {
1001     return  stack->vector->count;
1002 }
1003
1004
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;
1013
1014     ANTLR3_FREE(stack);
1015 }
1016
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);
1023
1024     // And get the element that is the now the top of the stack (if anything)
1025     // NOTE! This is not quite like a 'real' stack, which would normally return you
1026     // the current top of the stack, then remove it from the stack.
1027     // TODO: Review this, it is correct for follow sets which is what this was done for
1028     //       but is not as obvious when using it as a 'real'stack.
1029     //
1030     stack->top = stack->vector->get(stack->vector, stack->vector->count - 1);
1031     return stack->top;
1032 }
1033
1034 static void *
1035 antlr3StackGet  (pANTLR3_STACK stack, ANTLR3_INTKEY key)
1036 {
1037     return  stack->vector->get(stack->vector, (ANTLR3_UINT32)key);
1038 }
1039
1040 static void *
1041 antlr3StackPeek (pANTLR3_STACK  stack)
1042 {
1043     return  stack->top;
1044 }
1045
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 }
1052
1053 ANTLR3_API  pANTLR3_VECTOR
1054 antlr3VectorNew (ANTLR3_UINT32 sizeHint)
1055 {
1056         pANTLR3_VECTOR  vector;
1057
1058
1059         // Allocate memory for the vector structure itself
1060         //
1061         vector  = (pANTLR3_VECTOR) ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR)));
1062
1063         if      (vector == NULL)
1064         {
1065                 return  (pANTLR3_VECTOR)ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
1066         }
1067
1068         // Now fill in the defaults
1069         //
1070     antlr3SetVectorApi(vector, sizeHint);
1071
1072         // And everything is hunky dory
1073         //
1074         return  vector;
1075 }
1076
1077 ANTLR3_API void
1078 antlr3SetVectorApi  (pANTLR3_VECTOR vector, ANTLR3_UINT32 sizeHint)
1079 {
1080         ANTLR3_UINT32   initialSize;
1081
1082         // Allow vectors to be guessed by ourselves, so input size can be zero
1083         //
1084         if      (sizeHint > ANTLR3_VECTOR_INTERNAL_SIZE)
1085         {
1086                 initialSize = sizeHint;
1087         }
1088         else
1089         {
1090                 initialSize = ANTLR3_VECTOR_INTERNAL_SIZE;
1091         }
1092
1093     if  (sizeHint > ANTLR3_VECTOR_INTERNAL_SIZE)
1094     {
1095         vector->elements        = (pANTLR3_VECTOR_ELEMENT)ANTLR3_MALLOC((size_t)(sizeof(ANTLR3_VECTOR_ELEMENT) * initialSize));
1096     }
1097     else
1098     {
1099         vector->elements    = vector->internal;
1100     }
1101
1102         if      (vector->elements == NULL)
1103         {
1104                 ANTLR3_FREE(vector);
1105                 return;
1106         }
1107
1108         // Memory allocated successfully
1109         //
1110         vector->count                   = 0;                    // No entries yet of course
1111         vector->elementsSize    = initialSize;  // Available entries
1112
1113         // Now we can install the API
1114         //
1115         vector->add         = antlr3VectorAdd;
1116         vector->del         = antlr3VectorDel;
1117         vector->get         = antlr3VectorGet;
1118         vector->free    = antlr3VectorFree;
1119         vector->set         = antlr3VectorSet;
1120         vector->remove  = antrl3VectorRemove;
1121         vector->clear   = antlr3VectorClear;
1122         vector->size    = antlr3VectorSize;
1123     vector->swap    = antlr3VectorSwap;
1124
1125         // Assume that this is not a factory made vector
1126         //
1127         vector->factoryMade     = ANTLR3_FALSE;
1128 }
1129 // 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;
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)
1146                 {
1147                         vector->elements[entry].freeptr(vector->elements[entry].element);
1148                 }
1149                 vector->elements[entry].freeptr    = NULL;
1150                 vector->elements[entry].element    = NULL;
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
1159 static
1160 void    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)
1171                 {
1172                         vector->elements[entry].freeptr(vector->elements[entry].element);
1173                 }
1174                 vector->elements[entry].freeptr    = NULL;
1175                 vector->elements[entry].element    = NULL;
1176         }
1177
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;
1187
1188                 // Finally, free the allocation for the vector itself
1189                 //
1190                 ANTLR3_FREE(vector);
1191         }
1192 }
1193
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         }
1202
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         }
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;
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         }
1224
1225         // One less entry in the vector now
1226         //
1227         vector->count--;
1228 }
1229
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 }
1245
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;
1252
1253         // Check this is a valid request first
1254         //
1255         if      (entry >= vector->count)
1256         {
1257                 return NULL;
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;
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         }
1279
1280         // One less entry in the vector now
1281         //
1282         vector->count--;
1283
1284         return  element;
1285 }
1286
1287 static  void
1288 antlr3VectorResize  (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_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     }
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 ///
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         }
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 ///
1354 static  ANTLR3_UINT32
1355 antlr3VectorSet     (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         // 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 ///
1391 static  ANTLR3_BOOLEAN
1392 antlr3VectorSwap            (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_FALSE;
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_TRUE;
1419
1420 }
1421
1422 static  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 ///
1433 ANTLR3_API pANTLR3_VECTOR_FACTORY
1434 antlr3VectorFactoryNew      (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)));
1441
1442         if      (factory == NULL)
1443         {
1444                 return  NULL;
1445         }
1446
1447         // Factory memory is good, so create a new vector pool
1448         //
1449     factory->pools      = NULL;
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_SIZE);
1458
1459     factory->unTruc.factoryMade = ANTLR3_TRUE;
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
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);
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);
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
1493 static void
1494 newPool(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)   */
1504                                         (ANTLR3_UINT32)((factory->thisPool + 1) * sizeof(pANTLR3_VECTOR *))     /* Memory for new pool pointers */
1505                                         );
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));
1512
1513
1514     /* Reset the counters
1515      */
1516     factory->nextVector = 0;
1517
1518     /* Done
1519      */
1520     return;
1521 }
1522
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;
1531
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         }
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_SIZE);
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_SIZE);
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_TRUE && check->elementsSize > ANTLR3_VECTOR_INTERNAL_SIZE)
1611                 {
1612                     ANTLR3_FREE(check->elements);
1613                     check->elements = NULL;
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]);
1622         factory->pools[poolCount] = NULL;
1623     }
1624
1625     /* All the pools are deallocated we can free the pointers to the pools
1626      * now.
1627      */
1628     ANTLR3_FREE(factory->pools);
1629
1630     /* Finally, we can free the space for the factory itself
1631      */
1632     ANTLR3_FREE(factory);
1633
1634 }
1635
1636 static pANTLR3_VECTOR
1637 newVector(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)
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_SIZE)
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_SIZE);
1675     vector->factoryMade = ANTLR3_TRUE;
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  */
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 };
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  */
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 };
1761
1762 /* INT TRIE Implementation of depth 64 bits, being the number of bits
1763  * in a 64 bit integer.
1764  */
1765
1766 pANTLR3_INT_TRIE
1767 antlr3IntTrieNew(ANTLR3_UINT32 depth)
1768 {
1769         pANTLR3_INT_TRIE        trie;
1770
1771         trie    = (pANTLR3_INT_TRIE) ANTLR3_CALLOC(1, sizeof(ANTLR3_INT_TRIE)); /* Base memory required */
1772
1773         if (trie == NULL)
1774         {
1775                 return  (pANTLR3_INT_TRIE) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
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));
1783
1784         if (trie->root == NULL)
1785         {
1786                 ANTLR3_FREE(trie);
1787                 return  (pANTLR3_INT_TRIE) ANTLR3_FUNC_PTR(ANTLR3_ERR_NOMEM);
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  */
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;
1824
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  */
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;   /* That key is not in the trie (note that we set the pointer to -1 if no payload) */
1885         }
1886 }
1887
1888
1889 static  ANTLR3_BOOLEAN
1890 intTrieDel      (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_FALSE;
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  */
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;
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;
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_TRUE)
1962                 {
1963                         /* Yes, we are accepting duplicates
1964                          */
1965                         newEnt = (pANTLR3_TRIE_ENTRY)ANTLR3_CALLOC(1, sizeof(ANTLR3_TRIE_ENTRY));
1966
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                         }
1973
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                         }
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)
1993                         {
1994                                 nextEnt = nextEnt->next;
1995                         }
1996                         nextEnt->next = newEnt;
1997
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         }
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_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         }
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));
2113     if (nextNode == NULL)
2114     {
2115         /* All that work and no memory - bummer.
2116          */
2117         return  ANTLR3_FALSE;
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));
2123
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     }
2130
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;
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_TRUE;
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  */
2188 static void
2189 freeIntNode(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)
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_STR && thisEntry->freeptr != NULL)
2226         {
2227             thisEntry->freeptr(thisEntry->data.ptr);
2228         }
2229
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     }
2235
2236     /* The bucket entry is now gone, so we can free the memory for
2237      * the entry itself.
2238      */
2239     ANTLR3_FREE(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  */
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);
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);
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  */
2282 ANTLR3_API pANTLR3_TOPO
2283 antlr3TopoNew()
2284 {
2285     pANTLR3_TOPO topo = (pANTLR3_TOPO)ANTLR3_MALLOC(sizeof(ANTLR3_TOPO));
2286
2287     if  (topo == NULL)
2288     {
2289         return NULL;
2290     }
2291
2292     // Initialize variables
2293     //
2294
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
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 //
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;
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)
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         }
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));
2354         if (topo->edges == NULL)
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;
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)
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     }
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  */
2413 static void
2414 DFS(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_TRUE)
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_TRUE;
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)
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_FALSE)
2514     {
2515         topo->cycleMark--;
2516     }
2517
2518     return;
2519 }
2520
2521 static  pANTLR3_UINT32
2522 sortToArray      (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)
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));
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_FALSE)
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_TRUE)
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
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;
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_TRUE)
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));
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);
2687     return;
2688 }
2689
2690 static  void
2691 freeTopo             (pANTLR3_TOPO topo)
2692 {
2693     ANTLR3_UINT32   i;
2694
2695     // Free the result vector
2696     //
2697     if  (topo->sorted != NULL)
2698     {
2699         ANTLR3_FREE(topo->sorted);
2700         topo->sorted = NULL;
2701     }
2702
2703     // Free the visited map
2704     //
2705     if  (topo->visited != NULL)
2706     {
2707
2708         topo->visited->free(topo->visited);
2709         topo->visited = NULL;
2710     }
2711
2712     // Free any edgemaps
2713     //
2714     if  (topo->edges != NULL)
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)
2723             {
2724                 edgeList->free(edgeList);
2725             }
2726         }
2727
2728         ANTLR3_FREE(topo->edges);
2729     }
2730     topo->edges = NULL;
2731
2732     // Free any cycle map
2733     //
2734     if  (topo->cycle != NULL)
2735     {
2736         ANTLR3_FREE(topo->cycle);
2737     }
2738
2739     ANTLR3_FREE(topo);
2740 }