1// [The "BSD licence"] 2// Copyright (c) 2006-2007 Kay Roepke 2010 Alan Condit 3// All rights reserved. 4// 5// Redistribution and use in source and binary forms, with or without 6// modification, are permitted provided that the following conditions 7// are met: 8// 1. Redistributions of source code must retain the above copyright 9// notice, this list of conditions and the following disclaimer. 10// 2. Redistributions in binary form must reproduce the above copyright 11// notice, this list of conditions and the following disclaimer in the 12// documentation and/or other materials provided with the distribution. 13// 3. The name of the author may not be used to endorse or promote products 14// derived from this software without specific prior written permission. 15// 16// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 17// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 18// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 19// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 20// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 21// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 25// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 27#import "ANTLRBitSet.h" 28 29@implementation ANTLRBitSet 30#pragma mark Class Methods 31 32+ (ANTLRBitSet *) newBitSet 33{ 34 return [[ANTLRBitSet alloc] init]; 35} 36 37+ (ANTLRBitSet *) newBitSetWithType:(TokenType)type 38{ 39 return [[ANTLRBitSet alloc] initWithType:type]; 40} 41 42/** Construct a ANTLRBitSet given the size 43 * @param nbits The size of the ANTLRBitSet in bits 44 */ 45+ (ANTLRBitSet *) newBitSetWithNBits:(NSUInteger)nbits 46{ 47 return [[ANTLRBitSet alloc] initWithNBits:nbits]; 48} 49 50+ (ANTLRBitSet *) newBitSetWithArray:(AMutableArray *)types 51{ 52 return [[ANTLRBitSet alloc] initWithArrayOfBits:types]; 53} 54 55+ (ANTLRBitSet *) newBitSetWithBits:(const unsigned long long *)theBits Count:(NSUInteger)longCount 56{ 57 return [[ANTLRBitSet alloc] initWithBits:theBits Count:longCount]; 58} 59 60 61+ (ANTLRBitSet *) of:(NSUInteger) el 62{ 63 ANTLRBitSet *s = [ANTLRBitSet newBitSetWithNBits:(el + 1)]; 64 [s add:el]; 65 return s; 66} 67 68+ (ANTLRBitSet *) of:(NSUInteger) a And2:(NSUInteger) b 69{ 70 NSInteger c = (((a>b)?a:b)+1); 71 ANTLRBitSet *s = [ANTLRBitSet newBitSetWithNBits:c]; 72 [s add:a]; 73 [s add:b]; 74 return s; 75} 76 77+ (ANTLRBitSet *) of:(NSUInteger)a And2:(NSUInteger)b And3:(NSUInteger)c 78{ 79 NSUInteger d = ((a>b)?a:b); 80 d = ((c>d)?c:d)+1; 81 ANTLRBitSet *s = [ANTLRBitSet newBitSetWithNBits:d]; 82 [s add:a]; 83 [s add:b]; 84 [s add:c]; 85 return s; 86} 87 88+ (ANTLRBitSet *) of:(NSUInteger)a And2:(NSUInteger)b And3:(NSUInteger)c And4:(NSUInteger)d 89{ 90 NSUInteger e = ((a>b)?a:b); 91 NSUInteger f = ((c>d)?c:d); 92 e = ((e>f)?e:f)+1; 93 ANTLRBitSet *s = [ANTLRBitSet newBitSetWithNBits:e]; 94 [s add:a]; 95 [s add:b]; 96 [s add:c]; 97 [s add:d]; 98 return s; 99} 100 101// initializer 102#pragma mark Initializer 103 104- (ANTLRBitSet *) init 105{ 106 if ((self = [super init]) != nil) { 107 bitVector = CFBitVectorCreateMutable(kCFAllocatorDefault,0); 108 } 109 return self; 110} 111 112- (ANTLRBitSet *) initWithType:(TokenType)type 113{ 114 if ((self = [super init]) != nil) { 115 bitVector = CFBitVectorCreateMutable(kCFAllocatorDefault,0); 116 if ((CFIndex)type >= CFBitVectorGetCount(bitVector)) 117 CFBitVectorSetCount(bitVector, type+1); 118 CFBitVectorSetBitAtIndex(bitVector, type, 1); 119 } 120 return self; 121} 122 123- (ANTLRBitSet *) initWithNBits:(NSUInteger)nbits 124{ 125 if ((self = [super init]) != nil) { 126 bitVector = CFBitVectorCreateMutable(kCFAllocatorDefault,0); 127 CFBitVectorSetCount( bitVector, nbits ); 128 } 129 return self; 130} 131 132- (ANTLRBitSet *) initWithBitVector:(CFMutableBitVectorRef)theBitVector 133{ 134 if ((self = [super init]) != nil) { 135 bitVector = theBitVector; 136 } 137 return self; 138} 139 140// Initialize the bit vector with a constant array of ulonglongs like ANTLR generates. 141// Converts to big endian, because the underlying CFBitVector works like that. 142- (ANTLRBitSet *) initWithBits:(const unsigned long long *)theBits Count:(NSUInteger)longCount 143{ 144 if ((self = [super init]) != nil) { 145 unsigned int longNo; 146// unsigned long long swappedBits = 0LL; 147 CFIndex bitIdx; 148 bitVector = CFBitVectorCreateMutable ( kCFAllocatorDefault, 0 ); 149 CFBitVectorSetCount( bitVector, sizeof(unsigned long long)*8*longCount ); 150 151 for (longNo = 0; longNo < longCount; longNo++) { 152 for (bitIdx = 0; bitIdx < (CFIndex)sizeof(unsigned long long)*8; bitIdx++) { 153// swappedBits = CFSwapInt64HostToBig(theBits[longNo]); 154// if (swappedBits & (1LL << bitIdx)) { 155 if (theBits[longNo] & (1LL << bitIdx)) { 156 CFBitVectorSetBitAtIndex(bitVector, bitIdx+(longNo*(sizeof(unsigned long long)*8)), 1); 157 } 158 } 159 } 160 } 161 return self; 162} 163 164// Initialize bit vector with an array of anything. Just test the boolValue and set the corresponding bit. 165// Note: This is big-endian! 166- (ANTLRBitSet *) initWithArrayOfBits:(NSArray *)theArray 167{ 168 if ((self = [super init]) != nil) { 169 bitVector = CFBitVectorCreateMutable ( kCFAllocatorDefault, 0 ); 170 id value; 171 int bit = 0; 172 for (value in theArray) { 173 if ([value boolValue] == YES) { 174 [self add:bit]; 175 //CFBitVectorSetBitAtIndex(bitVector, bit, 1); 176 } 177 bit++; 178 } 179 } 180 return self; 181} 182 183- (void)dealloc 184{ 185#ifdef DEBUG_DEALLOC 186 NSLog( @"called dealloc in ANTLRBitSet" ); 187#endif 188 CFRelease(bitVector); 189 [super dealloc]; 190} 191 192 // operations 193#pragma mark Operations 194// return a copy of (self|aBitSet) 195- (ANTLRBitSet *) or:(ANTLRBitSet *) aBitSet 196{ 197 ANTLRBitSet *bitsetCopy = [self mutableCopyWithZone:nil]; 198 [bitsetCopy orInPlace:aBitSet]; 199 return bitsetCopy; 200} 201 202// perform a bitwise OR operation in place by changing underlying bit vector, growing it if necessary 203- (void) orInPlace:(ANTLRBitSet *) aBitSet 204{ 205 CFIndex selfCnt = CFBitVectorGetCount(bitVector); 206 CFMutableBitVectorRef otherBitVector = [aBitSet _bitVector]; 207 CFIndex otherCnt = CFBitVectorGetCount(otherBitVector); 208 CFIndex maxBitCnt = selfCnt > otherCnt ? selfCnt : otherCnt; 209 CFBitVectorSetCount(bitVector,maxBitCnt); // be sure to grow the CFBitVector manually! 210 211 CFIndex currIdx; 212 for (currIdx = 0; currIdx < maxBitCnt; currIdx++) { 213 if (CFBitVectorGetBitAtIndex(bitVector, currIdx) | CFBitVectorGetBitAtIndex(otherBitVector, currIdx)) { 214 CFBitVectorSetBitAtIndex(bitVector, currIdx, 1); 215 } 216 } 217} 218 219// set a bit, grow the bit vector if necessary 220- (void) add:(NSUInteger) bit 221{ 222 if ((CFIndex)bit >= CFBitVectorGetCount(bitVector)) 223 CFBitVectorSetCount(bitVector, bit+1); 224 CFBitVectorSetBitAtIndex(bitVector, bit, 1); 225} 226 227// unset a bit 228- (void) remove:(NSUInteger) bit 229{ 230 CFBitVectorSetBitAtIndex(bitVector, bit, 0); 231} 232 233- (void) setAllBits:(BOOL) aState 234{ 235 for( NSInteger bit=0; bit < CFBitVectorGetCount(bitVector); bit++ ) { 236 CFBitVectorSetBitAtIndex(bitVector, bit, aState); 237 } 238} 239 240// returns the number of bits in the bit vector. 241- (NSInteger) numBits 242{ 243 // return CFBitVectorGetCount(bitVector); 244 return CFBitVectorGetCountOfBit(bitVector, CFRangeMake(0, CFBitVectorGetCount(bitVector)), 1); 245} 246 247// returns the number of bits in the bit vector. 248- (NSUInteger) size 249{ 250 return CFBitVectorGetCount(bitVector); 251} 252 253- (void) setSize:(NSUInteger) nBits 254{ 255 CFBitVectorSetCount( bitVector, nBits ); 256} 257 258#pragma mark Informational 259// return a bitmask representation of this bitvector for easy operations 260- (unsigned long long) bitMask:(NSUInteger) bitNumber 261{ 262 return 1LL << bitNumber; 263} 264 265// test a bit (no pun intended) 266- (BOOL) member:(NSUInteger) bitNumber 267{ 268 return CFBitVectorGetBitAtIndex(bitVector,bitNumber) ? YES : NO; 269} 270 271// are all bits off? 272- (BOOL) isNil 273{ 274 return ((CFBitVectorGetCountOfBit(bitVector, CFRangeMake(0,CFBitVectorGetCount(bitVector)), 1) == 0) ? YES : NO); 275} 276 277// debugging aid. GDB invokes this automagically 278// return a string representation of the bit vector, indicating by their bitnumber which bits are set 279- (NSString *) description 280{ 281 CFIndex length = CFBitVectorGetCount(bitVector); 282 CFIndex currBit; 283 NSMutableString *descString = [NSMutableString stringWithString:@"{"]; 284 BOOL haveInsertedBit = NO; 285 for (currBit = 0; currBit < length; currBit++) { 286 if ( CFBitVectorGetBitAtIndex(bitVector, currBit) ) { 287 if (haveInsertedBit) { 288 [descString appendString:@","]; 289 } 290 [descString appendFormat:@"%d", currBit]; 291 haveInsertedBit = YES; 292 } 293 } 294 [descString appendString:@"}"]; 295 return descString; 296} 297 298// return a string representation of the bit vector, indicating by their bitnumber which bits are set 299- (NSString *) toString 300{ 301 302 return [self description]; 303} 304 305 // NSCopying 306#pragma mark NSCopying support 307 308- (id) mutableCopyWithZone:(NSZone *) theZone 309{ 310 ANTLRBitSet *newBitSet = [[ANTLRBitSet allocWithZone:theZone] initWithBitVector:CFBitVectorCreateMutableCopy(kCFAllocatorDefault,0,bitVector)]; 311 return newBitSet; 312} 313 314- (CFMutableBitVectorRef) _bitVector 315{ 316 return bitVector; 317} 318 319@synthesize bitVector; 320@end 321 322NSInteger max(NSInteger a, NSInteger b) 323{ 324 return (a>b)?a:b; 325} 326 327