1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#ifndef ANTLR3COLLECTIONS_H 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#define ANTLR3COLLECTIONS_H 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// [The "BSD licence"] 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// http://www.temporal-wave.com 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// http://www.linkedin.com/in/jimidle 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// All rights reserved. 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// Redistribution and use in source and binary forms, with or without 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// modification, are permitted provided that the following conditions 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// are met: 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 1. Redistributions of source code must retain the above copyright 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// notice, this list of conditions and the following disclaimer. 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 2. Redistributions in binary form must reproduce the above copyright 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// notice, this list of conditions and the following disclaimer in the 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// documentation and/or other materials provided with the distribution. 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 3. The name of the author may not be used to endorse or promote products 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// derived from this software without specific prior written permission. 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#include <antlr3defs.h> 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#include <antlr3bitset.h> 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#define ANTLR3_HASH_TYPE_INT 0 /**< Indicates the hashed file has integer keys */ 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#define ANTLR3_HASH_TYPE_STR 1 /**< Indicates the hashed file has numeric keys */ 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#ifdef __cplusplus 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverextern "C" { 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#endif 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvertypedef struct ANTLR3_HASH_KEY_struct 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT8 type; /**< One of ##ANTLR3_HASH_TYPE_INT or ##ANTLR3_HASH_TYPE_STR */ 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver union 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_UINT8 sKey; /**< Used if type is ANTLR3_HASH_TYPE_STR */ 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_INTKEY iKey; /**< used if type is ANTLR3_HASH_TYPE_INT */ 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver key; 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} ANTLR3_HASH_KEY, *pANTLR3_HASH_KEY; 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** Internal structure representing an element in a hash bucket. 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Stores the original key so that duplicate keys can be rejected 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * if necessary, and contains function can be supported. If the hash key 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * could be unique I would have invented the perfect compression algorithm ;-) 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvertypedef struct ANTLR3_HASH_ENTRY_struct 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Key that created this particular entry 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_HASH_KEY keybase; 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Pointer to the data for this particular entry 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void * data; 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Pointer to routine that knows how to release the memory 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * structure pointed at by data. If this is NULL then we assume 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * that the data pointer does not need to be freed when the entry 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is deleted from the table. 75324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (ANTLR3_CDECL *free)(void * data); 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Pointer to the next entry in this bucket if there 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is one. Sometimes different keys will hash to the same bucket (especially 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * if the number of buckets is small). We could implement dual hashing algorithms 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to minimize this, but that seems over the top for what this is needed for. 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver struct ANTLR3_HASH_ENTRY_struct * nextEntry; 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_HASH_ENTRY; 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** Internal structure of a hash table bucket, which tracks 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * all keys that hash to the same bucket. 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvertypedef struct ANTLR3_HASH_BUCKET_struct 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Pointer to the first entry in the bucket (if any, it 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * may be NULL). Duplicate entries are chained from 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * here. 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_HASH_ENTRY entries; 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_HASH_BUCKET; 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** Structure that tracks a hash table 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvertypedef struct ANTLR3_HASH_TABLE_struct 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Indicates whether the table allows duplicate keys 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int allowDups; 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Number of buckets available in this table 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 modulo; 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Points to the memory where the array of buckets 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * starts. 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_HASH_BUCKET buckets; 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** How many elements currently exist in the table. 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 count; 121324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Whether the hash table should strdup the keys it is given or not. 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_BOOLEAN doStrdup; 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Pointer to function to completely delete this table 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (*free) (struct ANTLR3_HASH_TABLE_struct * table); 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* String keyed hashtable functions */ 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (*del) (struct ANTLR3_HASH_TABLE_struct * table, void * key); 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_HASH_ENTRY (*remove) (struct ANTLR3_HASH_TABLE_struct * table, void * key); 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void * (*get) (struct ANTLR3_HASH_TABLE_struct * table, void * key); 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_INT32 (*put) (struct ANTLR3_HASH_TABLE_struct * table, void * key, void * element, void (ANTLR3_CDECL *freeptr)(void *)); 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* Integer based hash functions */ 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (*delI) (struct ANTLR3_HASH_TABLE_struct * table, ANTLR3_INTKEY key); 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_HASH_ENTRY (*removeI) (struct ANTLR3_HASH_TABLE_struct * table, ANTLR3_INTKEY key); 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void * (*getI) (struct ANTLR3_HASH_TABLE_struct * table, ANTLR3_INTKEY key); 140324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_INT32 (*putI) (struct ANTLR3_HASH_TABLE_struct * table, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *)); 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 (*size) (struct ANTLR3_HASH_TABLE_struct * table); 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_HASH_TABLE; 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** Internal structure representing an enumeration of a table. 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This is returned by antlr3Enumeration() 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Allows the programmer to traverse the table in hash order without 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * knowing what is in the actual table. 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Note that it is up to the caller to ensure that the table 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * structure does not change in the hash bucket that is currently being 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * enumerated as this structure just tracks the next pointers in the 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * bucket series. 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvertypedef struct ANTLR3_HASH_ENUM_struct 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* Pointer to the table we are enumerating 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_HASH_TABLE table; 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* Bucket we are currently enumerating (if NULL then we are done) 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 bucket; 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* Next entry to return, if NULL, then move to next bucket if any 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_HASH_ENTRY entry; 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /* Interface 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int (*next) (struct ANTLR3_HASH_ENUM_struct * en, pANTLR3_HASH_KEY *key, void ** data); 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (*free) (struct ANTLR3_HASH_ENUM_struct * table); 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_HASH_ENUM; 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** Structure that represents a LIST collection 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvertypedef struct ANTLR3_LIST_struct 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Hash table that is storing the list elements 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_HASH_TABLE table; 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (*free) (struct ANTLR3_LIST_struct * list); 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (*del) (struct ANTLR3_LIST_struct * list, ANTLR3_INTKEY key); 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void * (*get) (struct ANTLR3_LIST_struct * list, ANTLR3_INTKEY key); 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void * (*remove) (struct ANTLR3_LIST_struct * list, ANTLR3_INTKEY key); 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_INT32 (*add) (struct ANTLR3_LIST_struct * list, void * element, void (ANTLR3_CDECL *freeptr)(void *)); 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_INT32 (*put) (struct ANTLR3_LIST_struct * list, ANTLR3_INTKEY key, void * element, void (ANTLR3_CDECL *freeptr)(void *)); 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 (*size) (struct ANTLR3_LIST_struct * list); 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_LIST; 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** Structure that represents a Stack collection 198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvertypedef struct ANTLR3_STACK_struct 200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** List that supports the stack structure 202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_VECTOR vector; 204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Used for quick access to the top of the stack 206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 207324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void * top; 208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (*free) (struct ANTLR3_STACK_struct * stack); 209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void * (*pop) (struct ANTLR3_STACK_struct * stack); 210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void * (*get) (struct ANTLR3_STACK_struct * stack, ANTLR3_INTKEY key); 211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_BOOLEAN (*push) (struct ANTLR3_STACK_struct * stack, void * element, void (ANTLR3_CDECL *freeptr)(void *)); 212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 (*size) (struct ANTLR3_STACK_struct * stack); 213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void * (*peek) (struct ANTLR3_STACK_struct * stack); 214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_STACK; 217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* Structure that represents a vector element 219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvertypedef struct ANTLR3_VECTOR_ELEMENT_struct 221324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 222324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void * element; 223324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (ANTLR3_CDECL *freeptr)(void *); 224324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 225324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_VECTOR_ELEMENT, *pANTLR3_VECTOR_ELEMENT; 226324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 227324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#define ANTLR3_VECTOR_INTERNAL_SIZE 16 228324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* Structure that represents a vector collection. A vector is a simple list 229324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * that contains a pointer to the element and a pointer to a function that 230324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * that can free the element if it is removed. It auto resizes but does not 231324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * use hash techniques as it is referenced by a simple numeric index. It is not a 232324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * sparse list, so if any element is deleted, then the ones following are moved 233324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * down in memory and the count is adjusted. 234324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 235324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvertypedef struct ANTLR3_VECTOR_struct 236324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 237324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Array of pointers to vector elements 238324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 239324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_VECTOR_ELEMENT elements; 240324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 241324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Number of entries currently in the list; 242324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 243324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 count; 244324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 245324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Many times, a vector holds just a few nodes in an AST and it 246324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is too much overhead to malloc the space for elements so 247324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * at the expense of a few bytes of memory, we hold the first 248324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * few elements internally. It means we must copy them when 249324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * we grow beyond this initial size, but that is less overhead than 250324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the malloc/free callas we would otherwise require. 251324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 252324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_VECTOR_ELEMENT internal[ANTLR3_VECTOR_INTERNAL_SIZE]; 253324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 254324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Indicates if the structure was made by a factory, in which 255324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * case only the factory can free the memory for the actual vector, 256324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * though the vector free function is called and will recurse through its 257324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * entries calling any free pointers for each entry. 258324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 259324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_BOOLEAN factoryMade; 260324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 261324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Total number of entries in elements at any point in time 262324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 263324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 elementsSize; 264324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 265324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (ANTLR3_CDECL *free) (struct ANTLR3_VECTOR_struct * vector); 266324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (*del) (struct ANTLR3_VECTOR_struct * vector, ANTLR3_UINT32 entry); 267324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void * (*get) (struct ANTLR3_VECTOR_struct * vector, ANTLR3_UINT32 entry); 268324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void * (*remove) (struct ANTLR3_VECTOR_struct * vector, ANTLR3_UINT32 entry); 269324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (*clear) (struct ANTLR3_VECTOR_struct * vector); 270324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_BOOLEAN (*swap) (struct ANTLR3_VECTOR_struct *, ANTLR3_UINT32 entry1, ANTLR3_UINT32 entry2); 271324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 (*add) (struct ANTLR3_VECTOR_struct * vector, void * element, void (ANTLR3_CDECL *freeptr)(void *)); 272324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 (*set) (struct ANTLR3_VECTOR_struct * vector, ANTLR3_UINT32 entry, void * element, void (ANTLR3_CDECL *freeptr)(void *), ANTLR3_BOOLEAN freeExisting); 273324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 (*size) (struct ANTLR3_VECTOR_struct * vector); 274324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 275324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_VECTOR; 276324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 277324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** Default vector pool size if otherwise unspecified 278324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 279324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#define ANTLR3_FACTORY_VPOOL_SIZE 256 280324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 281324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** Structure that tracks vectors in a vector and auto deletes the vectors 282324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * in the vector factory when closed. 283324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 284324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvertypedef struct ANTLR3_VECTOR_FACTORY_struct 285324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 286324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 287324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** List of all vector pools allocated so far 288324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 289324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_VECTOR *pools; 290324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 291324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Count of the vector pools allocated so far (current active pool) 292324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 293324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_INT32 thisPool; 294324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 295324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** The next vector available in the pool 296324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 297324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 nextVector; 298324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 299324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Trick to quickly initialize a new vector via memcpy and not a function call 300324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 301324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_VECTOR unTruc; 302324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 303324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Consumers from the factory can release a factory produced vector 304324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * back to the factory so that it may be reused (and thus conserve memory) 305324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * by another caller. The available vectors are stored here. Note that 306324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the only vectors avaible in the free chain are produced by this factory, so they 307324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * need not be explicitly freed when the factory is closed. 308324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 309324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_STACK freeStack; 310324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 311324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Function to close the vector factory 312324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 313324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (*close) (struct ANTLR3_VECTOR_FACTORY_struct * factory); 314324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 315324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** Function to supply a new vector 316324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 317324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_VECTOR (*newVector) (struct ANTLR3_VECTOR_FACTORY_struct * factory); 318324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 319324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /// Function to return a vector to the factory for reuse 320324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /// 321324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (*returnVector) (struct ANTLR3_VECTOR_FACTORY_struct * factory, pANTLR3_VECTOR vector); 322324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 323324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 324324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverANTLR3_VECTOR_FACTORY; 325324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 326324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 327324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/* -------------- TRIE Interfaces ---------------- */ 328324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 329324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 330324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** Structure that holds the payload entry in an ANTLR3_INT_TRIE or ANTLR3_STRING_TRIE 331324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 332324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvertypedef struct ANTLR3_TRIE_ENTRY_struct 333324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 334324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 type; 335324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (ANTLR3_CDECL *freeptr)(void *); 336324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver union 337324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 338324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_INTKEY intVal; 339324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void * ptr; 340324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } data; 341324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 342324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver struct ANTLR3_TRIE_ENTRY_struct * next; /* Allows duplicate entries for same key in insertion order */ 343324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 344324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverANTLR3_TRIE_ENTRY, * pANTLR3_TRIE_ENTRY; 345324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 346324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 347324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** Structure that defines an element/node in an ANTLR3_INT_TRIE 348324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 349324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvertypedef struct ANTLR3_INT_TRIE_NODE_struct 350324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 351324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 bitNum; /**< This is the left/right bit index for traversal along the nodes */ 352324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_INTKEY key; /**< This is the actual key that the entry represents if it is a terminal node */ 353324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_TRIE_ENTRY buckets; /**< This is the data bucket(s) that the key indexes, which may be NULL */ 354324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver struct ANTLR3_INT_TRIE_NODE_struct * leftN; /**< Pointer to the left node from here when sKey & bitNum = 0 */ 355324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver struct ANTLR3_INT_TRIE_NODE_struct * rightN; /**< Pointer to the right node from here when sKey & bitNum, = 1 */ 356324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 357324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_INT_TRIE_NODE, * pANTLR3_INT_TRIE_NODE; 358324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 359324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** Structure that defines an ANTLR3_INT_TRIE. For this particular implementation, 360324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * as you might expect, the key is turned into a "string" by looking at bit(key, depth) 361324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * of the integer key. Using 64 bit keys gives us a depth limit of 64 (or bit 0..63) 362324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * and potentially a huge trie. This is the algorithm for a Patricia Trie. 363324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Note also that this trie [can] accept multiple entries for the same key and is 364324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * therefore a kind of elastic bucket patricia trie. 365324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 366324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If you find this code useful, please feel free to 'steal' it for any purpose 367324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * as covered by the BSD license under which ANTLR is issued. You can cut the code 368324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * but as the ANTLR library is only about 50K (Windows Vista), you might find it 369324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * easier to just link the library. Please keep all comments and licenses and so on 370324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * in any version of this you create of course. 371324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 372324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Jim Idle. 373324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 374324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 375324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvertypedef struct ANTLR3_INT_TRIE_struct 376324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 377324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_INT_TRIE_NODE root; /* Root node of this integer trie */ 378324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_INT_TRIE_NODE current; /* Used to traverse the TRIE with the next() method */ 379324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 count; /* Current entry count */ 380324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_BOOLEAN allowDups; /* Whether this trie accepts duplicate keys */ 381324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 382324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 383324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_TRIE_ENTRY (*get) (struct ANTLR3_INT_TRIE_struct * trie, ANTLR3_INTKEY key); 384324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_BOOLEAN (*del) (struct ANTLR3_INT_TRIE_struct * trie, ANTLR3_INTKEY key); 385324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_BOOLEAN (*add) (struct ANTLR3_INT_TRIE_struct * trie, ANTLR3_INTKEY key, ANTLR3_UINT32 type, ANTLR3_INTKEY intVal, void * data, void (ANTLR3_CDECL *freeptr)(void *)); 386324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (*free) (struct ANTLR3_INT_TRIE_struct * trie); 387324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 388324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 389324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_INT_TRIE; 390324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 391324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** 392324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A topological sort system that given a set of dependencies of a node m on node n, 393324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * can sort them in dependency order. This is a generally useful utility object 394324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * that does not care what the things are it is sorting. Generally the set 395324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to be sorted will be numeric indexes into some other structure such as an ANTLR3_VECTOR. 396324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * I have provided a sort method that given ANTLR3_VECTOR as an input will sort 397324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the vector entries in place, as well as a sort method that just returns an 398324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * array of the sorted noded indexes, in case you are not sorting ANTLR3_VECTORS but 399324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * some set of your own device. 400324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 401324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * Of the two main algorithms that could be used, I chose to use the depth first 402324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * search for unvisited nodes as a) This runs in linear time, and b) it is what 403324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * we used in the ANTLR Tool to perform a topological sort of the input grammar files 404324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * based on their dependencies. 405324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 406324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvertypedef struct ANTLR3_TOPO_struct 407324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 408324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 409324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A vector of vectors of edges, built by calling the addEdge method() 410324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * to indicate that node number n depends on node number m. Each entry in the vector 411324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * contains a bitset, which has a bit index set for each node upon which the 412324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * entry node depends. 413324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 414324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_BITSET * edges; 415324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 416324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 417324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A vector used to build up the sorted output order. Note that 418324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * as the vector contains UINT32 then the maximum node index is 419324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 'limited' to 2^32, as nodes should be zero based. 420324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 421324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_UINT32 sorted; 422324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 423324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 424324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A vector used to detect cycles in the edge dependecies. It is used 425324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * as a stack and each time we descend a node to one of its edges we 426324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * add the node into this stack. If we find a node that we have already 427324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * visited in the stack, then it means there wasa cycle such as 9->8->1->9 428324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * as the only way a node can be on the stack is if we are currently 429324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * descnding from it as we remove it from the stack as we exit from 430324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * descending its dependencies 431324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 432324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_UINT32 cycle; 433324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 434324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 435324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A flag that indicates the algorithm found a cycle in the edges 436324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * such as 9->8->1->9 437324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * If this flag is set after you have called one of the sort routines 438324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * then the detected cycle will be contained in the cycle array and 439324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * cycleLimit will point to the one after the last entry in the cycle. 440324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 441324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_BOOLEAN hasCycle; 442324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 443324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 444324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A watermark used to accumulate potential cycles in the cycle array. 445324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * This should be zero when we are done. Check hasCycle after calling one 446324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * of the sort methods and if it is ANTLR3_TRUE then you can find the cycle 447324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * in cycle[0]...cycle[cycleMark-1] 448324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 449324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 cycleMark; 450324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 451324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 452324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * One more than the largest node index that is contained in edges/sorted. 453324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 454324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 limit; 455324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 456324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 457324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The set of visited nodes as determined by a set entry in 458324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * the bitmap. 459324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 460324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_BITSET visited; 461324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 462324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 463324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A method that adds an edge from one node to another. An edge 464324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * of n -> m indicates that node n is dependent on node m. Note that 465324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * while building these edges, it is perfectly OK to add nodes out of 466324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * sequence. So, if you have edges: 467324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 468324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 3 -> 0 469324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 2 -> 1 470324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 1 -> 3 471324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 472324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The you can add them in that order and so add node 3 before nodes 2 and 1 473324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 474324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 475324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (*addEdge) (struct ANTLR3_TOPO_struct * topo, ANTLR3_UINT32 edge, ANTLR3_UINT32 dependency); 476324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 477324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 478324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 479324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A method that returns a pointer to an array of sorted node indexes. 480324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The array is sorted in topological sorted order. Note that the array 481324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * is only as large as the largest node index you created an edge for. This means 482324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * that if you had an input of 32 nodes, but that largest node with an edge 483324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * was 16, then the returned array will be the sorted order of the first 16 484324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * nodes and the last 16 nodes of your array are basically fine as they are 485324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * as they had no dependencies and do not need any particular sort order. 486324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 487324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * NB: If the structure that contains the array is freed, then the sorted 488324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * array will be freed too so you should use the value of limit to 489324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * make a long term copy of this array if you do not want to keep the topo 490324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * structure around as well. 491324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 492324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_UINT32 (*sortToArray) (struct ANTLR3_TOPO_struct * topo); 493324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 494324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 495324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A method that sorts the supplied ANTLR3_VECTOR in place based 496324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * on the previously supplied edge data. 497324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 498324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (*sortVector) (struct ANTLR3_TOPO_struct * topo, pANTLR3_VECTOR v); 499324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 500324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver /** 501324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * A method to free this structure and any associated memory. 502324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 503324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver void (*free) (struct ANTLR3_TOPO_struct * topo); 504324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 505324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_TOPO; 506324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 507324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#ifdef __cplusplus 508324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 509324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#endif 510324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 511324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#endif 512324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 513324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 514