1324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// 2324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// \file 3324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// Contains the C implementation of ANTLR3 bitsets as adapted from Terence Parr's 4324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// Java implementation. 5324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// 6324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 7324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// [The "BSD licence"] 8324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// Copyright (c) 2005-2009 Jim Idle, Temporal Wave LLC 9324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// http://www.temporal-wave.com 10324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// http://www.linkedin.com/in/jimidle 11324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 12324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// All rights reserved. 13324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 14324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// Redistribution and use in source and binary forms, with or without 15324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// modification, are permitted provided that the following conditions 16324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// are met: 17324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 1. Redistributions of source code must retain the above copyright 18324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// notice, this list of conditions and the following disclaimer. 19324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 2. Redistributions in binary form must reproduce the above copyright 20324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// notice, this list of conditions and the following disclaimer in the 21324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// documentation and/or other materials provided with the distribution. 22324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 3. The name of the author may not be used to endorse or promote products 23324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// derived from this software without specific prior written permission. 24324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 25324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 26324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 27324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 28324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 29324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 30324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 31324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 32324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 33324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 34324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 35324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 36324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver#include <antlr3bitset.h> 37324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 38324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// External interface 39324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 40324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 41324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic pANTLR3_BITSET antlr3BitsetClone (pANTLR3_BITSET inSet); 42324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic pANTLR3_BITSET antlr3BitsetOR (pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2); 43324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic void antlr3BitsetORInPlace (pANTLR3_BITSET bitset, pANTLR3_BITSET bitset2); 44324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic ANTLR3_UINT32 antlr3BitsetSize (pANTLR3_BITSET bitset); 45324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic void antlr3BitsetAdd (pANTLR3_BITSET bitset, ANTLR3_INT32 bit); 46324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic ANTLR3_BOOLEAN antlr3BitsetEquals (pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2); 47324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic ANTLR3_BOOLEAN antlr3BitsetMember (pANTLR3_BITSET bitset, ANTLR3_UINT32 bit); 48324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic ANTLR3_UINT32 antlr3BitsetNumBits (pANTLR3_BITSET bitset); 49324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic void antlr3BitsetRemove (pANTLR3_BITSET bitset, ANTLR3_UINT32 bit); 50324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic ANTLR3_BOOLEAN antlr3BitsetIsNil (pANTLR3_BITSET bitset); 51324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic pANTLR3_INT32 antlr3BitsetToIntList (pANTLR3_BITSET bitset); 52324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 53324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// Local functions 54324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver// 55324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic void growToInclude (pANTLR3_BITSET bitset, ANTLR3_INT32 bit); 56324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic void grow (pANTLR3_BITSET bitset, ANTLR3_INT32 newSize); 57324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic ANTLR3_UINT64 bitMask (ANTLR3_UINT32 bitNumber); 58324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic ANTLR3_UINT32 numWordsToHold (ANTLR3_UINT32 bit); 59324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic ANTLR3_UINT32 wordNumber (ANTLR3_UINT32 bit); 60324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic void antlr3BitsetFree (pANTLR3_BITSET bitset); 61324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 62324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic void 63324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetFree(pANTLR3_BITSET bitset) 64324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 65324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset->blist.bits != NULL) 66324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 67324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_FREE(bitset->blist.bits); 68324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->blist.bits = NULL; 69324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 70324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_FREE(bitset); 71324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 72324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 73324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 74324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 75324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverANTLR3_API pANTLR3_BITSET 76324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetNew(ANTLR3_UINT32 numBits) 77324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 78324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_BITSET bitset; 79324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 80324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 numelements; 81324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 82324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Allocate memory for the bitset structure itself 83324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 84324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset = (pANTLR3_BITSET) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_BITSET)); 85324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 86324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset == NULL) 87324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 88324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return NULL; 89324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 90324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 91324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Avoid memory thrashing at the up front expense of a few bytes 92324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 93324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (numBits < (8 * ANTLR3_BITSET_BITS)) 94324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 95324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver numBits = 8 * ANTLR3_BITSET_BITS; 96324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 97324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 98324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // No we need to allocate the memory for the number of bits asked for 99324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // in multiples of ANTLR3_UINT64. 100324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 101324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver numelements = ((numBits -1) >> ANTLR3_BITSET_LOG_BITS) + 1; 102324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 103324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->blist.bits = (pANTLR3_BITWORD) ANTLR3_MALLOC((size_t)(numelements * sizeof(ANTLR3_BITWORD))); 104324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver memset(bitset->blist.bits, 0, (size_t)(numelements * sizeof(ANTLR3_BITWORD))); 105324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->blist.length = numelements; 106324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 107324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset->blist.bits == NULL) 108324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 109324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_FREE(bitset); 110324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return NULL; 111324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 112324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 113324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver antlr3BitsetSetAPI(bitset); 114324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 115324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 116324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // All seems good 117324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 118324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return bitset; 119324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 120324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 121324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverANTLR3_API void 122324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetSetAPI(pANTLR3_BITSET bitset) 123324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 124324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->clone = antlr3BitsetClone; 125324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->bor = antlr3BitsetOR; 126324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->borInPlace = antlr3BitsetORInPlace; 127324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->size = antlr3BitsetSize; 128324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->add = antlr3BitsetAdd; 129324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->grow = grow; 130324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->equals = antlr3BitsetEquals; 131324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->isMember = antlr3BitsetMember; 132324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->numBits = antlr3BitsetNumBits; 133324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->remove = antlr3BitsetRemove; 134324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->isNilNode = antlr3BitsetIsNil; 135324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->toIntList = antlr3BitsetToIntList; 136324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 137324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->free = antlr3BitsetFree; 138324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 139324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 140324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverANTLR3_API pANTLR3_BITSET 141324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetCopy(pANTLR3_BITSET_LIST blist) 142324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 143324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_BITSET bitset; 144324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver int numElements; 145324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 146324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Allocate memory for the bitset structure itself 147324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 148324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset = (pANTLR3_BITSET) ANTLR3_MALLOC((size_t)sizeof(ANTLR3_BITSET)); 149324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 150324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset == NULL) 151324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 152324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return NULL; 153324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 154324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 155324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver numElements = blist->length; 156324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 157324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Avoid memory thrashing at the expense of a few more bytes 158324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 159324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (numElements < 8) 160324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 161324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver numElements = 8; 162324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 163324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 164324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Install the length in ANTLR3_UINT64 units 165324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 166324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->blist.length = numElements; 167324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 168324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->blist.bits = (pANTLR3_BITWORD)ANTLR3_MALLOC((size_t)(numElements * sizeof(ANTLR3_BITWORD))); 169324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 170324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset->blist.bits == NULL) 171324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 172324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_FREE(bitset); 173324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return NULL; 174324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 175324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 176324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_MEMCPY(bitset->blist.bits, blist->bits, (ANTLR3_UINT64)(numElements * sizeof(ANTLR3_BITWORD))); 177324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 178324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // All seems good 179324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 180324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return bitset; 181324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 182324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 183324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic pANTLR3_BITSET 184324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetClone(pANTLR3_BITSET inSet) 185324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 186324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_BITSET bitset; 187324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 188324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Allocate memory for the bitset structure itself 189324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 190324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset = antlr3BitsetNew(ANTLR3_BITSET_BITS * inSet->blist.length); 191324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 192324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset == NULL) 193324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 194324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return NULL; 195324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 196324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 197324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Install the actual bits in the source set 198324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 199324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_MEMCPY(bitset->blist.bits, inSet->blist.bits, (ANTLR3_UINT64)(inSet->blist.length * sizeof(ANTLR3_BITWORD))); 200324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 201324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // All seems good 202324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 203324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return bitset; 204324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 205324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 206324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 207324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverANTLR3_API pANTLR3_BITSET 208324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetList(pANTLR3_HASH_TABLE list) 209324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 210324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_BITSET bitSet; 211324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_HASH_ENUM en; 212324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_HASH_KEY key; 213324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT64 bit; 214324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 215324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // We have no idea what exactly is in the list 216324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // so create a default bitset and then just add stuff 217324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // as we enumerate. 218324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 219324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitSet = antlr3BitsetNew(0); 220324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 221324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver en = antlr3EnumNew(list); 222324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 223324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while (en->next(en, &key, (void **)(&bit)) == ANTLR3_SUCCESS) 224324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 225324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitSet->add(bitSet, (ANTLR3_UINT32)bit); 226324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 227324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver en->free(en); 228324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 229324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return NULL; 230324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 231324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 232324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// 233324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// \brief 234324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// Creates a new bitset with at least one 64 bit bset of bits, but as 235324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// many 64 bit sets as are required. 236324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// 237324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// \param[in] bset 238324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// A variable number of bits to add to the set, ending in -1 (impossible bit). 239324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// 240324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// \returns 241324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// A new bit set with all of the specified bitmaps in it and the API 242324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// initialized. 243324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// 244324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// Call as: 245324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// - pANTLR3_BITSET = antlrBitsetLoad(bset, bset11, ..., -1); 246324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// - pANTLR3_BITSET = antlrBitsetOf(-1); Create empty bitset 247324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// 248324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// \remarks 249324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// Stdargs function - must supply -1 as last paremeter, which is NOT 250324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// added to the set. 251324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// 252324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// 253324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverANTLR3_API pANTLR3_BITSET 254324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetLoad(pANTLR3_BITSET_LIST inBits) 255324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 256324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_BITSET bitset; 257324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 count; 258324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 259324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Allocate memory for the bitset structure itself 260324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // the input parameter is the bit number (0 based) 261324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // to include in the bitset, so we need at at least 262324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // bit + 1 bits. If any arguments indicate a 263324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // a bit higher than the default number of bits (0 means default size) 264324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // then Add() will take care 265324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // of it. 266324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 267324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset = antlr3BitsetNew(0); 268324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 269324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset == NULL) 270324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 271324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return NULL; 272324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 273324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 274324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (inBits != NULL) 275324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 276324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Now we can add the element bits into the set 277324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 278324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver count=0; 279324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while (count < inBits->length) 280324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 281324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset->blist.length <= count) 282324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 283324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->grow(bitset, count+1); 284324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 285324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 286324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->blist.bits[count] = *((inBits->bits)+count); 287324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver count++; 288324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 289324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 290324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 291324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // return the new bitset 292324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 293324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return bitset; 294324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 295324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 296324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// 297324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// \brief 298324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// Creates a new bitset with at least one element, but as 299324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// many elements are required. 300324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// 301324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// \param[in] bit 302324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// A variable number of bits to add to the set, ending in -1 (impossible bit). 303324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// 304324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// \returns 305324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// A new bit set with all of the specified elements added into it. 306324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// 307324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// Call as: 308324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// - pANTLR3_BITSET = antlrBitsetOf(n, n1, n2, -1); 309324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// - pANTLR3_BITSET = antlrBitsetOf(-1); Create empty bitset 310324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// 311324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// \remarks 312324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// Stdargs function - must supply -1 as last paremeter, which is NOT 313324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// added to the set. 314324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// 315324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/// 316324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverANTLR3_API pANTLR3_BITSET 317324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetOf(ANTLR3_INT32 bit, ...) 318324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 319324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_BITSET bitset; 320324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 321324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver va_list ap; 322324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 323324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Allocate memory for the bitset structure itself 324324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // the input parameter is the bit number (0 based) 325324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // to include in the bitset, so we need at at least 326324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // bit + 1 bits. If any arguments indicate a 327324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // a bit higher than the default number of bits (0 menas default size) 328324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // then Add() will take care 329324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // of it. 330324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 331324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset = antlr3BitsetNew(0); 332324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 333324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset == NULL) 334324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 335324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return NULL; 336324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 337324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 338324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Now we can add the element bits into the set 339324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 340324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver va_start(ap, bit); 341324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver while (bit != -1) 342324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 343324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver antlr3BitsetAdd(bitset, bit); 344324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bit = va_arg(ap, ANTLR3_UINT32); 345324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 346324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver va_end(ap); 347324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 348324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // return the new bitset 349324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 350324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return bitset; 351324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 352324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 353324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic pANTLR3_BITSET 354324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetOR(pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2) 355324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 356324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_BITSET bitset; 357324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 358324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset1 == NULL) 359324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 360324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return antlr3BitsetClone(bitset2); 361324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 362324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 363324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset2 == NULL) 364324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 365324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return antlr3BitsetClone(bitset1); 366324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 367324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 368324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Allocate memory for the newly ordered bitset structure itself. 369324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 370324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset = antlr3BitsetClone(bitset1); 371324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 372324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver antlr3BitsetORInPlace(bitset, bitset2); 373324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 374324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return bitset; 375324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 376324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 377324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 378324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic void 379324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetAdd(pANTLR3_BITSET bitset, ANTLR3_INT32 bit) 380324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 381324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 word; 382324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 383324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver word = wordNumber(bit); 384324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 385324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (word >= bitset->blist.length) 386324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 387324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver growToInclude(bitset, bit); 388324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 389324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 390324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->blist.bits[word] |= bitMask(bit); 391324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 392324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 393324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 394324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic void 395324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruvergrow(pANTLR3_BITSET bitset, ANTLR3_INT32 newSize) 396324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 397324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_BITWORD newBits; 398324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 399324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Space for newly sized bitset - TODO: come back to this and use realloc?, it may 400324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // be more efficient... 401324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 402324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver newBits = (pANTLR3_BITWORD) ANTLR3_CALLOC(1, (size_t)(newSize * sizeof(ANTLR3_BITWORD))); 403324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset->blist.bits != NULL) 404324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 405324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Copy existing bits 406324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 407324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_MEMCPY((void *)newBits, (const void *)bitset->blist.bits, (size_t)(bitset->blist.length * sizeof(ANTLR3_BITWORD))); 408324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 409324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Out with the old bits... de de de derrr 410324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 411324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_FREE(bitset->blist.bits); 412324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 413324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 414324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // In with the new bits... keerrrang. 415324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 416324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->blist.bits = newBits; 417324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->blist.length = newSize; 418324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 419324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 420324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic void 421324c4644fee44b9898524c09511bd33c3f12e2dfBen GruvergrowToInclude(pANTLR3_BITSET bitset, ANTLR3_INT32 bit) 422324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 423324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 bl; 424324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 nw; 425324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 426324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bl = (bitset->blist.length << 1); 427324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver nw = numWordsToHold(bit); 428324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 429324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bl > nw) 430324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 431324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->grow(bitset, bl); 432324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 433324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else 434324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 435324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->grow(bitset, nw); 436324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 437324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 438324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 439324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic void 440324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetORInPlace(pANTLR3_BITSET bitset, pANTLR3_BITSET bitset2) 441324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 442324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 minimum; 443324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 i; 444324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 445324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset2 == NULL) 446324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 447324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return; 448324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 449324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 450324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 451324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // First make sure that the target bitset is big enough 452324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // for the new bits to be ored in. 453324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 454324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset->blist.length < bitset2->blist.length) 455324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 456324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver growToInclude(bitset, (bitset2->blist.length * sizeof(ANTLR3_BITWORD))); 457324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 458324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 459324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Or the miniimum number of bits after any resizing went on 460324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 461324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset->blist.length < bitset2->blist.length) 462324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 463324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver minimum = bitset->blist.length; 464324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 465324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else 466324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 467324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver minimum = bitset2->blist.length; 468324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 469324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 470324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (i = minimum; i > 0; i--) 471324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 472324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->blist.bits[i-1] |= bitset2->blist.bits[i-1]; 473324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 474324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 475324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 476324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic ANTLR3_UINT64 477324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverbitMask(ANTLR3_UINT32 bitNumber) 478324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 479324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ((ANTLR3_UINT64)1) << (bitNumber & (ANTLR3_BITSET_MOD_MASK)); 480324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 481324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 482324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic ANTLR3_UINT32 483324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetSize(pANTLR3_BITSET bitset) 484324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 485324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 degree; 486324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_INT32 i; 487324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_INT8 bit; 488324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 489324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // TODO: Come back to this, it may be faster to & with 0x01 490324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // then shift right a copy of the 4 bits, than shift left a constant of 1. 491324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // But then again, the optimizer might just work this out 492324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // anyway. 493324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 494324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver degree = 0; 495324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (i = bitset->blist.length - 1; i>= 0; i--) 496324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 497324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset->blist.bits[i] != 0) 498324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 499324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (bit = ANTLR3_BITSET_BITS - 1; bit >= 0; bit--) 500324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 501324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ((bitset->blist.bits[i] & (((ANTLR3_BITWORD)1) << bit)) != 0) 502324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 503324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver degree++; 504324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 505324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 506324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 507324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 508324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return degree; 509324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 510324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 511324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic ANTLR3_BOOLEAN 512324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetEquals(pANTLR3_BITSET bitset1, pANTLR3_BITSET bitset2) 513324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 514324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_INT32 minimum; 515324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_INT32 i; 516324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 517324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset1 == NULL || bitset2 == NULL) 518324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 519324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ANTLR3_FALSE; 520324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 521324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 522324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Work out the minimum comparison set 523324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 524324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset1->blist.length < bitset2->blist.length) 525324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 526324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver minimum = bitset1->blist.length; 527324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 528324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else 529324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 530324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver minimum = bitset2->blist.length; 531324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 532324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 533324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Make sure explict in common bits are equal 534324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 535324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (i = minimum - 1; i >=0 ; i--) 536324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 537324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset1->blist.bits[i] != bitset2->blist.bits[i]) 538324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 539324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ANTLR3_FALSE; 540324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 541324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 542324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 543324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Now make sure the bits of the larger set are all turned 544324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // off. 545324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 546324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset1->blist.length > (ANTLR3_UINT32)minimum) 547324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 548324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (i = minimum ; (ANTLR3_UINT32)i < bitset1->blist.length; i++) 549324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 550324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset1->blist.bits[i] != 0) 551324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 552324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ANTLR3_FALSE; 553324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 554324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 555324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 556324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else if (bitset2->blist.length > (ANTLR3_UINT32)minimum) 557324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 558324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (i = minimum; (ANTLR3_UINT32)i < bitset2->blist.length; i++) 559324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 560324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset2->blist.bits[i] != 0) 561324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 562324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ANTLR3_FALSE; 563324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 564324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 565324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 566324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 567324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ANTLR3_TRUE; 568324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 569324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 570324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic ANTLR3_BOOLEAN 571324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetMember(pANTLR3_BITSET bitset, ANTLR3_UINT32 bit) 572324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 573324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 wordNo; 574324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 575324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver wordNo = wordNumber(bit); 576324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 577324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (wordNo >= bitset->blist.length) 578324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 579324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ANTLR3_FALSE; 580324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 581324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 582324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if ((bitset->blist.bits[wordNo] & bitMask(bit)) == 0) 583324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 584324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ANTLR3_FALSE; 585324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 586324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver else 587324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 588324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ANTLR3_TRUE; 589324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 590324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 591324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 592324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic void 593324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetRemove(pANTLR3_BITSET bitset, ANTLR3_UINT32 bit) 594324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 595324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 wordNo; 596324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 597324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver wordNo = wordNumber(bit); 598324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 599324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (wordNo < bitset->blist.length) 600324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 601324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver bitset->blist.bits[wordNo] &= ~(bitMask(bit)); 602324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 603324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 604324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic ANTLR3_BOOLEAN 605324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetIsNil(pANTLR3_BITSET bitset) 606324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 607324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_INT32 i; 608324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 609324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (i = bitset->blist.length -1; i>= 0; i--) 610324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 611324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset->blist.bits[i] != 0) 612324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 613324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ANTLR3_FALSE; 614324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 615324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 616324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 617324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return ANTLR3_TRUE; 618324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 619324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 620324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic ANTLR3_UINT32 621324c4644fee44b9898524c09511bd33c3f12e2dfBen GruvernumWordsToHold(ANTLR3_UINT32 bit) 622324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 623324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return (bit >> ANTLR3_BITSET_LOG_BITS) + 1; 624324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 625324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 626324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic ANTLR3_UINT32 627324c4644fee44b9898524c09511bd33c3f12e2dfBen GruverwordNumber(ANTLR3_UINT32 bit) 628324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 629324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return bit >> ANTLR3_BITSET_LOG_BITS; 630324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 631324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 632324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic ANTLR3_UINT32 633324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetNumBits(pANTLR3_BITSET bitset) 634324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 635324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return bitset->blist.length << ANTLR3_BITSET_LOG_BITS; 636324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 637324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 638324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver/** Produce an integer list of all the bits that are turned on 639324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * in this bitset. Used for error processing in the main as the bitset 640324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * reresents a number of integer tokens which we use for follow sets 641324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * and so on. 642324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * 643324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver * The first entry is the number of elements following in the list. 644324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver */ 645324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverstatic pANTLR3_INT32 646324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruverantlr3BitsetToIntList (pANTLR3_BITSET bitset) 647324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver{ 648324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 numInts; // How many integers we will need 649324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 numBits; // How many bits are in the set 650324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 i; 651324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver ANTLR3_UINT32 index; 652324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 653324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver pANTLR3_INT32 intList; 654324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 655324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver numInts = bitset->size(bitset) + 1; 656324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver numBits = bitset->numBits(bitset); 657324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 658324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver intList = (pANTLR3_INT32)ANTLR3_MALLOC(numInts * sizeof(ANTLR3_INT32)); 659324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 660324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (intList == NULL) 661324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 662324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return NULL; // Out of memory 663324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 664324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 665324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver intList[0] = numInts; 666324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 667324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Enumerate the bits that are turned on 668324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 669324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver for (i = 0, index = 1; i<numBits; i++) 670324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 671324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver if (bitset->isMember(bitset, i) == ANTLR3_TRUE) 672324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver { 673324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver intList[index++] = i; 674324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 675324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver } 676324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 677324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // Result set 678324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver // 679324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver return intList; 680324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver} 681324c4644fee44b9898524c09511bd33c3f12e2dfBen Gruver 682