/*
* A1BitArrayt.m
* BitArray is a framework that provides a scalable class that uses sparse allocation for
* addressing disjoint bits sets. This is an ideal framework for handling large amounts of
* preferences or as a front end to large data sets that need sparse indexes.
*
* Created by frankcastellucci on 1/3/11.
* Copyright 2011 Axiom:1, Inc. All rights reserved. (mailto:information@axiom1inc.com)
*
* This file is part of BitArray.
* BitArray is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
* BitArray is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
* You should have received a copy of the GNU General Public License
* called "COPYING" along with BitArray. If not, see <http://www.gnu.org/licenses/>.
*
*/
#import "A1BitArray.h"
#pragma mark -
#pragma mark Fine Control For Instances of BitSet
#define WORD_BITS 8
#define BASE_BIT_RANGE 1024
#define BASE_WORD_COUNT BASE_BIT_RANGE/WORD_BITS
#define LOW_EXTENT_SIZE 64
#define OFFSET_WORD_COUNT BASE_WORD_COUNT-1
#define OFFSET_BIT_RANGE BASE_BIT_RANGE-1
typedef struct _ExtentCtrl {
NSUInteger wordCount; // In bytes
NSRange wordRange; // Based on extent beyond BaseCtrl [n to (n+wordCount)-1]
Byte words[]; // Pointer to byte array for this range
} ExtentCtrl;
typedef ExtentCtrl* ExtentCtrlPtr;
typedef ExtentCtrlPtr* ExtentCtrlPtrPtr;
typedef struct _ExtentCollector {
NSUInteger count;
BOOL firstMatchesBase;
ExtentCtrlPtr theRest[];
} ExtentCollector;
typedef ExtentCollector* ExtentCollectorPtr;
typedef struct _ControlSet {
NSUInteger extentCount; // Number of existing extents
unsigned short extentSizeInBytes; // Size of extent (default is 1024 bits)
BOOL dirty; // Dirty flag
BOOL extentsAllowed; // Do we create extents
ExtentCtrlPtrPtr extents; // Pointer to extent pointers
ExtentCtrl base; // Initial array
} ControlSet;
typedef ControlSet* ControlSetPtr;
// Macros (inline)
#define CP(x) ((ControlSetPtr)x)
#define ECP(x) ((ExtentCtrlPtr)x)
#define MAKE_BITS(x) x*WORD_BITS
#define MAKE_WORD(x) x/WORD_BITS
#define MAKE_FRAMEPOS(x,y) ((x/y->extentSizeInBytes)*y->extentSizeInBytes)
// Error Domain
NSString *const BitArrayErrorDomain=@"com.axiom1.BitArray.BitArrayError";
@interface A1BitArray()
- (ControlSetPtr) control;
- (void) setExtentWords:(ExtentCtrlPtr) extentPtr wordRange:(NSRange)range withValue:(Byte) value error:(NSError **)err;
- (ExtentCtrlPtr) extent:(NSUInteger) position error:(NSError **)err;
- (ExtentCtrlPtr) createExtent:(NSUInteger) startPosition error:(NSError **)err;
- (ExtentCollectorPtr) getExtentsInRange:(NSRange) range;
- (void) or:(ExtentCtrlPtr)result larger:(ExtentCtrlPtr)a smaller:(ExtentCtrlPtr) b;
@end
#pragma mark -
#pragma mark Implementation
@implementation A1BitArray
/*!
@method init
Initializes an instance of a BitSet. When initialized:
It's dirty flag set to TRUE
The wordByteSize (bytes) is equal to NSUInteger (8)
*/
- (id) init{
if ((self = [super init])) {
control = calloc(1, sizeof(ControlSet)+BASE_WORD_COUNT);
CP(control)->dirty=YES;
CP(control)->base.wordCount = BASE_WORD_COUNT;
CP(control)->base.wordRange = NSMakeRange(0, OFFSET_WORD_COUNT);
}
return self;
}
- (id) initWithExtentsAllowed {
if ((self = [self init])) {
CP(control)->extentsAllowed = YES;
CP(control)->extentSizeInBytes = BASE_WORD_COUNT;
}
return self;
}
- (id) initWithExtentSize:(unsigned short) extentSizeInBytes {
if ((self = [self initWithExtentsAllowed])) {
CP(control)->extentSizeInBytes = (extentSizeInBytes < LOW_EXTENT_SIZE ? LOW_EXTENT_SIZE : (extentSizeInBytes / LOW_EXTENT_SIZE)*LOW_EXTENT_SIZE);
}
return self;
}
- (id) initWithCoder:(NSCoder *) decoder {
NSUInteger len=0;
ControlSetPtr target = calloc(1,sizeof(ControlSet)+BASE_WORD_COUNT);
void *ptr = [decoder decodeBytesWithReturnedLength:&len];
if (len == sizeof(ControlSet)+BASE_WORD_COUNT) {
memcpy(target,ptr,len);
target->extents = nil;
if (target->extentsAllowed && target->extentCount > 0) {
target->extents = calloc(target->extentCount, sizeof(void*));
NSUInteger ecount=0;
for (NSUInteger x=0;x<target->extentCount;x++) {
ExtentCtrlPtr etarget = calloc(1, sizeof(ExtentCtrl)+target->extentSizeInBytes);
ptr = [decoder decodeBytesWithReturnedLength:&len];
if (len == sizeof(ExtentCtrl)+target->extentSizeInBytes) {
memcpy(etarget,ptr,len);
target->extents[x] = etarget;
++ecount;
}
else {
free(etarget); // Free the current pointer
for (NSUInteger x=0;x<ecount;x++)
free(target->extents[x]);
free(target->extents);
target->extents=nil;
target->extentCount=0;
// Throw exception
break;
}
}
}
control = target;
}
else {
free(target);
// Throw exception
}
return self;
}
/*!
@function copyWithZone
*/
- (id) copyWithZone:(NSZone *)zone {
A1BitArray *copy = [[[self class] allocWithZone:zone]init];
ControlSetPtr target = [copy control];
ControlSetPtr source = CP(control);
memmove(&target->base,&source->base,sizeof(ExtentCtrl)+BASE_WORD_COUNT);
target->dirty = YES;
if (source->extentsAllowed && (source->extentCount > 0 && source->extents != nil)) {
target->extentsAllowed = source->extentsAllowed;
target->extentCount = source->extentCount;
target->extents = (ExtentCtrlPtrPtr) calloc(source->extentCount, sizeof(void *));
for(NSUInteger x=0;x<source->extentCount;x++) {
ExtentCtrlPtr eptr = source->extents[x];
target->extents[x] = memmove(calloc(1, sizeof(ExtentCtrl)+eptr->wordCount),
eptr,
sizeof(ExtentCtrl)+eptr->wordCount);
}
}
return copy;
}
- (void) encodeWithCoder:(NSCoder *) coder {
ControlSetPtr source = CP(control);
source->dirty = NO;
[coder encodeBytes:source length:sizeof(ControlSet)+BASE_WORD_COUNT];
for(NSUInteger x=0;x<source->extentCount;x++) {
ExtentCtrlPtr eptr = source->extents[x];
[coder encodeBytes:eptr length:sizeof(ExtentCtrl)+eptr->wordCount];
}
}
#pragma mark -
#pragma mark Getters
- (BOOL) dirty {
return CP(control)->dirty;
}
- (NSUInteger) bytesInBase {
return CP(control)->base.wordCount;
}
- (NSUInteger) bitsInBase {
return MAKE_BITS(CP(control)->base.wordCount);
}
- (BOOL) extentsAllowed {
return CP(control)->extentsAllowed;
}
- (NSUInteger) extentCount{
return CP(control)->extentCount;
}
- (NSUInteger) bytesInExtent {
return CP(control)->extentSizeInBytes;
}
- (NSUInteger) bitsInExtent {
return MAKE_BITS(CP(control)->extentSizeInBytes);
}
- (BOOL) bit:(NSUInteger)bitIndex error:(NSError **) err {
NSUInteger virtualPosition = MAKE_WORD(bitIndex); // Get the byte position
ExtentCtrlPtr eptr = [self extent:virtualPosition error:err];
return (eptr != nil ? (eptr->words[virtualPosition - eptr->wordRange.location] & (1<<bitIndex - MAKE_BITS(virtualPosition)) ? YES:NO) : NO);
}
#pragma mark -
#pragma mark Setters
/*!
@function clearBit
Clears (sets to 0, FALSE, NO) the bit at location bitIndex
*/
- (void) clearBit:(NSUInteger)bitIndex error:(NSError **) err {
NSUInteger virtualPosition = MAKE_WORD(bitIndex); // Get the byte position
ExtentCtrlPtr eptr = [self extent:virtualPosition error:err];
if (eptr != nil) {
eptr->words[virtualPosition - eptr->wordRange.location] &= ~(1<<bitIndex - MAKE_BITS(virtualPosition));
CP(control)->dirty=YES;
}
else if(CP(control)->extentsAllowed) {
if ([self createExtent:virtualPosition error:err]) {
[self clearBit:bitIndex error:err];
}
}
}
/*!
Clears the base array bits (sets all to FALSE)
*/
- (void) clear {
NSError *err=nil;
[self clearExtentWithBit:0 error:&err];
}
/*!
Clears the extent that includes the bitIndex bit
*/
- (void) clearExtentWithBit:(NSUInteger) bitIndex error:(NSError **)err {
ExtentCtrlPtr eptr = [self extent:MAKE_WORD(bitIndex) error:err];
if (eptr != nil) {
[self setExtentWords:eptr wordRange:NSMakeRange(0, eptr->wordCount-1) withValue:0 error:err];
}
else if(CP(control)->extentsAllowed) {
if ([self createExtent:MAKE_WORD(bitIndex) error:err]) {
[self clearExtentWithBit:bitIndex error:err];
}
}
}
- (void) setBit:(NSUInteger)bitIndex error:(NSError **) err {
NSUInteger virtualPosition = MAKE_WORD(bitIndex); // Get the byte position
ExtentCtrlPtr eptr = [self extent:virtualPosition error:err];
if (eptr != nil) {
eptr->words[virtualPosition - eptr->wordRange.location] |= (1<<bitIndex - MAKE_BITS(virtualPosition));
}
else if(CP(control)->extentsAllowed) {
if ([self createExtent:virtualPosition error:err]) {
[self setBit:bitIndex error:err];
}
}
}
- (void) set {
NSError *err=nil;
[self setExtentWithBit:0 error:&err];
}
- (void) setExtentWithBit:(NSUInteger) bitIndex error:(NSError **)err {
ExtentCtrlPtr eptr = [self extent:MAKE_WORD(bitIndex) error:err];
if (eptr != nil) {
[self setExtentWords:eptr wordRange:NSMakeRange(0, eptr->wordCount-1) withValue:1 error:err];
}
else if(CP(control)->extentsAllowed) {
if ([self createExtent:MAKE_WORD(bitIndex) error:err]) {
[self setExtentWithBit:bitIndex error:err];
}
}
}
#pragma mark -
#pragma mark Set Logic
- (A1BitArray *) arrayFromUnionWith:(A1BitArray *)secondBitArray error:(NSError **)error {
A1BitArray *result = nil;
BOOL hasExtents = NO;
A1BitArray *bigArray = self;
A1BitArray *smallArray = secondBitArray;
ControlSetPtr biggerPtr = self.control;
ControlSetPtr smallerPtr = secondBitArray.control;
if (secondBitArray != nil) {
// Determine if we need an extent result and, if so, the larger of the two
if ([self control]->extentsAllowed || [secondBitArray control]->extentsAllowed) {
// Shuffle the larger frame
if ([secondBitArray control]->extentSizeInBytes > [self control]->extentSizeInBytes) {
bigArray = secondBitArray;
smallArray = self;
}
hasExtents = ([bigArray control]->extentCount > 0 || [smallArray control]->extentCount > 0);
result = [[A1BitArray alloc]initWithExtentSize:[bigArray control]->extentSizeInBytes];
}
else {
result = [[A1BitArray alloc]init];
}
biggerPtr = [bigArray control];
smallerPtr = [smallArray control];
ControlSetPtr resultPtr = result.control;
[self or:&resultPtr->base larger:&biggerPtr->base smaller:&smallerPtr->base];
if (hasExtents) {
if ((biggerPtr->extentCount && !smallerPtr->extentCount) || (!biggerPtr->extentCount && smallerPtr->extentCount)) {
biggerPtr = (biggerPtr->extentCount ? biggerPtr : smallerPtr);
for (NSUInteger x=0;x<biggerPtr->extentCount;x++) {
ExtentCtrlPtr b0 = biggerPtr->extents[x];
ExtentCtrlPtr r0 = [result createExtent:b0->wordRange.location error:error];
[self or:r0 larger:b0 smaller:nil];
}
}
else {
NSUInteger bigEC = biggerPtr->extentCount;
NSUInteger smlEC = smallerPtr->extentCount;
for (NSUInteger x=0;x<biggerPtr->extentCount;x++) {
ExtentCtrlPtr b0 = biggerPtr->extents[x];
ExtentCollectorPtr eC = [smallArray getExtentsInRange:b0->wordRange];
ExtentCtrlPtr s0 = (eC && eC->firstMatchesBase ? eC->theRest[0] : nil) ;
ExtentCtrlPtr r0 = [result createExtent:b0->wordRange.location error:error];
[self or:r0 larger:b0 smaller:s0];
--bigEC;
if (eC) {
for(NSUInteger y=(eC->firstMatchesBase ? 1:0);y<eC->count;++y) {
[self or:r0 larger:eC->theRest[y] smaller:nil];
--smlEC;
}
if (eC->firstMatchesBase)
--smlEC;
free(eC);
}
}
if (smlEC) {
for (NSUInteger x=0;x<smallerPtr->extentCount;x++) {
ExtentCtrlPtr b0 = smallerPtr->extents[x];
ExtentCtrlPtr r0 = nil;
if (!(r0=[result extent:b0->wordRange.location error:error]) &&
![bigArray extent:b0->wordRange.location error:error]) {
r0=[result createExtent:b0->wordRange.location error:error];
[self or:r0 larger:b0 smaller:nil];
--smlEC;
}
}
}
}
}
}
else {
*error = [NSError errorWithDomain:BitArrayErrorDomain code:NullInstanceError userInfo:nil];
}
return [result autorelease];
}
#pragma mark -
#pragma mark Private Utility
- (ControlSetPtr) control {
return CP(control);
}
- (void) setExtentWords:(ExtentCtrlPtr) extentPtr wordRange:(NSRange)range withValue:(Byte) value error:(NSError **)err {
if (range.location < extentPtr->wordCount && range.length < extentPtr->wordCount) {
memset(&extentPtr->words[range.location],value,range.length);
*(volatile char *) extentPtr->words= *(volatile char*)extentPtr->words;
CP(control)->dirty=YES;
}
else if(err != nil) {
*err = [NSError errorWithDomain:BitArrayErrorDomain code:BitIndexOutOfRange userInfo:nil];
}
}
/*!
Create a new extent starting at the byte position specified
What we do know, at the moment, is that we arrive here because the startPosition was
not found in an existing extent. What we need to verify is if there is already an
extent that the end range overlaps with.
*/
- (ExtentCtrlPtr) createExtent:(NSUInteger)startPosition error:(NSError **)err{
ControlSetPtr cptr = CP(control);
NSUInteger framePosition = MAKE_FRAMEPOS(startPosition,cptr);
ExtentCtrlPtr eptr = calloc(1, sizeof(ExtentCtrl)+cptr->extentSizeInBytes);
if (eptr) {
@synchronized(self) {
if (cptr->extents == nil && cptr->extentCount == 0) {
cptr->extents = calloc(1, sizeof(void *));
}
else {
cptr->extents = realloc(cptr->extents, (cptr->extentCount+1) * sizeof(void *));
}
if (cptr->extents) {
cptr->extents[cptr->extentCount] = eptr;
cptr->extentCount++;
eptr->wordCount = cptr->extentSizeInBytes;
eptr->wordRange = NSMakeRange(framePosition, (framePosition+cptr->extentSizeInBytes)-1);
CP(control)->dirty=YES;
}
else {
free(eptr);
eptr = nil;
if(err != nil)
*err = [NSError errorWithDomain:BitArrayErrorDomain code:UnableToIncreaseExtentControl userInfo:nil];
}
}
}
else if (err != nil){
*err = [NSError errorWithDomain:BitArrayErrorDomain code:UnableToAllocateExtent userInfo:nil];
}
return eptr;
}
/*!
@function(extent)
Takes a byte position and returns extent, if exists
*/
- (ExtentCtrlPtr) extent:(NSUInteger) position error:(NSError **)err{
ControlSetPtr cptr = CP(control);
ExtentCtrlPtr eptr = nil;
if (position < cptr->base.wordCount) {
eptr = &cptr->base;
}
else if(cptr->extentsAllowed == NO){
if (err != nil)
*err = [NSError errorWithDomain:BitArrayErrorDomain code:BitIndexOutOfRange userInfo:nil];
}
else {
NSUInteger framePosition = MAKE_FRAMEPOS(position,cptr);
// Find the extent
for(NSUInteger x=0;x<cptr->extentCount;x++) {
ExtentCtrlPtr ieptr = cptr->extents[x];
if(framePosition == ieptr->wordRange.location) {
eptr = ieptr;
break;
}
}
}
return eptr;
}
/*!
@method getExtentsInRange
@abstract returns all matches for extents in range given
*/
- (ExtentCollectorPtr) getExtentsInRange:(NSRange) range {
ExtentCollectorPtr eir=nil;
if (CP(control)->extentCount) {
NSUInteger count=0;
ExtentCtrlPtr bMatch=nil;
// Calculate
for (NSUInteger x=0;x<CP(control)->extentCount;x++) {
ExtentCtrlPtr current = CP(control)->extents[x];
if (current->wordRange.location >= range.location && current->wordRange.length <= range.length) {
++count;
if (!bMatch && current->wordRange.location == range.location)
bMatch = current;
}
}
// Setup
if (count != 0) {
eir = calloc(1, sizeof(ExtentCollector) + sizeof(void *)*count);
eir->count = count;
NSUInteger index=0;
if (bMatch != nil) {
eir->firstMatchesBase = YES;
eir->theRest[0] = bMatch;
++index;
}
for (NSUInteger x=0;x<CP(control)->extentCount;x++) {
ExtentCtrlPtr current = CP(control)->extents[x];
if (current != bMatch) {
if (current->wordRange.location >= range.location && current->wordRange.length <= range.length) {
eir->theRest[index] = current;
++index;
}
}
}
}
}
return eir;
}
- (void) or:(ExtentCtrlPtr)result larger:(ExtentCtrlPtr)a smaller:(ExtentCtrlPtr) b {
NSUInteger *aWord = (NSUInteger *)a->words;
NSUInteger *baseWord = (NSUInteger *)(BytePtr)&result->words[a->wordRange.location - result->wordRange.location];
NSUInteger *bWord = (NSUInteger *)b->words;
NSUInteger maxcount = MAKE_WORD(a->wordCount);
NSUInteger bcnt = (b != nil ? MAKE_WORD(b->wordCount) : 0);
for (NSUInteger x=0;x<maxcount;x++) {
baseWord[x] |= aWord[x] | (b!=nil && bcnt>=x?bWord[x]:0);
}
}
- (void) dealloc {
// Free up extents and pointers
ControlSetPtr cptr = CP(control);
for(NSUInteger x=0;x<cptr->extentCount;x++) {
free(cptr->extents[x]);
}
cptr->extentCount=0;
if (cptr->extents != nil) {
free(cptr->extents);
cptr->extents = nil;
}
free(control);
control = nil;
[super dealloc];
}
@end
