CoreFoundation/CFBitVector.c

/*
 * Copyright (c) 2008-2009 Brent Fulgham <bfulgham@gmail.org>.  All rights reserved.
 *
 * This source code is a modified version of the CoreFoundation sources released by Apple Inc. under
 * the terms of the APSL version 2.0 (see below).
 *
 * For information about changes from the original Apple source release can be found by reviewing the
 * source control system for the project at https://sourceforge.net/svn/?group_id=246198.
 *
 * The original license information is as follows:
 * 
 * Copyright (c) 2008 Apple Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/*	CFBitVector.c
	Copyright 1998-2002, Apple, Inc. All rights reserved.
	Responsibility: Christopher Kane
*/

#include <CoreFoundation/CFBitVector.h>
#include "CFInternal.h"
#include <string.h>

/* The bucket type must be unsigned, at least one byte in size, and
   a power of 2 in number of bits; bits are numbered from 0 from left
   to right (bit 0 is the most significant) */
typedef uint8_t __CFBitVectorBucket;

enum {
    __CF_BITS_PER_BYTE = 8
};

enum {
    __CF_BITS_PER_BUCKET = (__CF_BITS_PER_BYTE * sizeof(__CFBitVectorBucket))
};

CF_INLINE CFIndex __CFBitVectorRoundUpCapacity(CFIndex capacity) {
    return ((capacity + 63) / 64) * 64;
}

CF_INLINE CFIndex __CFBitVectorNumBucketsForCapacity(CFIndex capacity) {
    return (capacity + __CF_BITS_PER_BUCKET - 1) / __CF_BITS_PER_BUCKET;
}

struct __CFBitVector {
    CFRuntimeBase _base;
    CFIndex _count;	/* number of bits */
    CFIndex _capacity;	/* maximum number of bits */
    __CFBitVectorBucket *_buckets;
};

CF_INLINE UInt32 __CFBitVectorMutableVariety(const void *cf) {
    return __CFBitfieldGetValue(((const CFRuntimeBase *)cf)->_cfinfo[CF_INFO_BITS], 3, 2);
}

CF_INLINE void __CFBitVectorSetMutableVariety(void *cf, UInt32 v) {
    __CFBitfieldSetValue(((CFRuntimeBase *)cf)->_cfinfo[CF_INFO_BITS], 3, 2, v);
}

CF_INLINE UInt32 __CFBitVectorMutableVarietyFromFlags(UInt32 flags) {
    return __CFBitfieldGetValue(flags, 1, 0);
}

// ensure that uses of these inlines are correct, bytes vs. buckets vs. bits
CF_INLINE CFIndex __CFBitVectorCount(CFBitVectorRef bv) {
    return bv->_count;
}

CF_INLINE void __CFBitVectorSetCount(CFMutableBitVectorRef bv, CFIndex v) {
    bv->_count = v;
}

CF_INLINE CFIndex __CFBitVectorCapacity(CFBitVectorRef bv) {
    return bv->_capacity;
}

CF_INLINE void __CFBitVectorSetCapacity(CFMutableBitVectorRef bv, CFIndex v) {
    bv->_capacity = v;
}

CF_INLINE CFIndex __CFBitVectorNumBucketsUsed(CFBitVectorRef bv) {
    return bv->_count / __CF_BITS_PER_BUCKET + 1;
}

CF_INLINE void __CFBitVectorSetNumBucketsUsed(CFMutableBitVectorRef bv, CFIndex v) {
    /* for a CFBitVector, _bucketsUsed == _count / __CF_BITS_PER_BUCKET + 1 */
}

CF_INLINE CFIndex __CFBitVectorNumBuckets(CFBitVectorRef bv) {
    return bv->_capacity / __CF_BITS_PER_BUCKET + 1;
}

CF_INLINE void __CFBitVectorSetNumBuckets(CFMutableBitVectorRef bv, CFIndex v) {
    /* for a CFBitVector, _bucketsNum == _capacity / __CF_BITS_PER_BUCKET + 1 */
}

static __CFBitVectorBucket __CFBitBucketMask(CFIndex bottomBit, CFIndex topBit) {
    CFIndex shiftL = __CF_BITS_PER_BUCKET - topBit + bottomBit - 1;
    __CFBitVectorBucket result = ~(__CFBitVectorBucket)0;
    result = (result << shiftL);
    result = (result >> bottomBit);
    return result;
}

CF_INLINE CFBit __CFBitVectorBit(__CFBitVectorBucket *buckets, CFIndex idx) {
    CFIndex bucketIdx = idx / __CF_BITS_PER_BUCKET;
    CFIndex bitOfBucket = idx & (__CF_BITS_PER_BUCKET - 1);
    return (buckets[bucketIdx] >> (__CF_BITS_PER_BUCKET - 1 - bitOfBucket)) & 0x1;
}

CF_INLINE void __CFSetBitVectorBit(__CFBitVectorBucket *buckets, CFIndex idx, CFBit value) {
    CFIndex bucketIdx = idx / __CF_BITS_PER_BUCKET;
    CFIndex bitOfBucket = idx & (__CF_BITS_PER_BUCKET - 1);
    if (value) {
	buckets[bucketIdx] |= (1 << (__CF_BITS_PER_BUCKET - 1 - bitOfBucket));
    } else {
	buckets[bucketIdx] &= ~(1 << (__CF_BITS_PER_BUCKET - 1 - bitOfBucket));
    }
}

CF_INLINE void __CFFlipBitVectorBit(__CFBitVectorBucket *buckets, CFIndex idx) {
    CFIndex bucketIdx = idx / __CF_BITS_PER_BUCKET;
    CFIndex bitOfBucket = idx & (__CF_BITS_PER_BUCKET - 1);
    buckets[bucketIdx] ^= (1 << (__CF_BITS_PER_BUCKET - 1 - bitOfBucket));
}

#if defined(DEBUG)
CF_INLINE void __CFBitVectorValidateRange(CFBitVectorRef bv, CFRange range, const char *func) {
    CFAssert2(0 <= range.location && range.location < __CFBitVectorCount(bv), __kCFLogAssertion, "%s(): range.location index (%d) out of bounds", func, range.location);
    CFAssert2(0 <= range.length, __kCFLogAssertion, "%s(): range.length (%d) cannot be less than zero", func, range.length);
    CFAssert2(range.location + range.length <= __CFBitVectorCount(bv), __kCFLogAssertion, "%s(): ending index (%d) out of bounds", func, range.location + range.length);
}
#else
#define __CFBitVectorValidateRange(bf,r,f)
#endif

static Boolean __CFBitVectorEqual(CFTypeRef cf1, CFTypeRef cf2) {
    CFBitVectorRef bv1 = (CFBitVectorRef)cf1;
    CFBitVectorRef bv2 = (CFBitVectorRef)cf2;
    CFIndex idx, cnt;
    cnt = __CFBitVectorCount(bv1);
    if (cnt != __CFBitVectorCount(bv2)) return false;
    if (0 == cnt) return true;
    for (idx = 0; idx < (cnt / __CF_BITS_PER_BUCKET) + 1; idx++) {
	__CFBitVectorBucket val1 = bv1->_buckets[idx];
	__CFBitVectorBucket val2 = bv2->_buckets[idx];
	if (val1 != val2) return false;
    }
    return true;
}

static CFHashCode __CFBitVectorHash(CFTypeRef cf) {
    CFBitVectorRef bv = (CFBitVectorRef)cf;
    return __CFBitVectorCount(bv);
}

static CFStringRef __CFBitVectorCopyDescription(CFTypeRef cf) {
    CFBitVectorRef bv = (CFBitVectorRef)cf;
    CFMutableStringRef result;
    CFIndex idx, cnt;
    __CFBitVectorBucket *buckets;
    cnt = __CFBitVectorCount(bv);
    buckets = bv->_buckets;
    result = CFStringCreateMutable(kCFAllocatorSystemDefault, 0);
    CFStringAppendFormat(result, NULL, CFSTR("<CFBitVector %p [%p]>{count = %u, capacity = %u, objects = (\n"), cf, CFGetAllocator(bv), cnt, __CFBitVectorCapacity(bv));
    for (idx = 0; idx < (cnt / 64); idx++) {	/* Print groups of 64 */
	CFIndex idx2;
	CFStringAppendFormat(result, NULL, CFSTR("\t%u : "), (idx * 64));
	for (idx2 = 0; idx2 < 64; idx2 += 4) {
	    CFIndex bucketIdx = (idx << 6) + idx2;
	    CFStringAppendFormat(result, NULL, CFSTR("%d%d%d%d"),
		__CFBitVectorBit(buckets, bucketIdx + 0),
		__CFBitVectorBit(buckets, bucketIdx + 1),
		__CFBitVectorBit(buckets, bucketIdx + 2),
		__CFBitVectorBit(buckets, bucketIdx + 3));
	}
	CFStringAppend(result, CFSTR("\n"));
    }
    if (idx * 64 < cnt) {
	CFStringAppendFormat(result, NULL, CFSTR("\t%u : "), (idx * 64));
	for (idx = (idx * 64); idx < cnt; idx++) {	/* Print remainder */
	    CFStringAppendFormat(result, NULL, CFSTR("%d"), __CFBitVectorBit(buckets, idx));
	}
    }
    CFStringAppend(result, CFSTR("\n)}"));
    return result;
}

enum {
    kCFBitVectorImmutable = 0x0,		/* unchangable and fixed capacity; default */
    kCFBitVectorMutable = 0x1,		/* changeable and variable capacity */
    kCFBitVectorFixedMutable = 0x3	/* changeable and fixed capacity */
};

static void __CFBitVectorDeallocate(CFTypeRef cf) {
    CFMutableBitVectorRef bv = (CFMutableBitVectorRef)cf;
    CFAllocatorRef allocator = CFGetAllocator(bv);
    if (__CFBitVectorMutableVariety(bv) == kCFBitVectorMutable) {
	_CFAllocatorDeallocateGC(allocator, bv->_buckets);
    }
}

static CFTypeID __kCFBitVectorTypeID = _kCFRuntimeNotATypeID;

static const CFRuntimeClass __CFBitVectorClass = {
    _kCFRuntimeScannedObject,
    "CFBitVector",
    NULL,	// init
    NULL,	// copy
    __CFBitVectorDeallocate,
    __CFBitVectorEqual,
    __CFBitVectorHash,
    NULL,	// 
    __CFBitVectorCopyDescription
};

__private_extern__ void __CFBitVectorInitialize(void) {
    __kCFBitVectorTypeID = _CFRuntimeRegisterClass(&__CFBitVectorClass);
}

CFTypeID CFBitVectorGetTypeID(void) {
    return __kCFBitVectorTypeID;
}

static CFMutableBitVectorRef __CFBitVectorInit(CFAllocatorRef allocator, CFOptionFlags flags, CFIndex capacity, const uint8_t *bytes, CFIndex numBits) {
    CFMutableBitVectorRef memory;
    CFIndex size;
    CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
    CFAssert3(kCFBitVectorFixedMutable != __CFBitVectorMutableVarietyFromFlags(flags) || numBits <= capacity, __kCFLogAssertion, "%s(): for fixed mutable bit vectors, capacity (%d) must be greater than or equal to number of initial elements (%d)", __PRETTY_FUNCTION__, capacity, numBits);
    CFAssert2(0 <= numBits, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numBits);
    size = sizeof(struct __CFBitVector) - sizeof(CFRuntimeBase);
    if (__CFBitVectorMutableVarietyFromFlags(flags) != kCFBitVectorMutable)
	size += sizeof(__CFBitVectorBucket) * __CFBitVectorNumBucketsForCapacity(capacity);
    memory = (CFMutableBitVectorRef)_CFRuntimeCreateInstance(allocator, __kCFBitVectorTypeID, size, NULL);
    if (NULL == memory) {
	return NULL;
    }
    switch (__CFBitVectorMutableVarietyFromFlags(flags)) {
    case kCFBitVectorMutable:
	__CFBitVectorSetCapacity(memory, __CFBitVectorRoundUpCapacity(1));
	__CFBitVectorSetNumBuckets(memory, __CFBitVectorNumBucketsForCapacity(__CFBitVectorRoundUpCapacity(1)));
	CF_WRITE_BARRIER_BASE_ASSIGN(allocator, memory, memory->_buckets, _CFAllocatorAllocateGC(allocator, __CFBitVectorNumBuckets(memory) * sizeof(__CFBitVectorBucket), 0));
	if (__CFOASafe) __CFSetLastAllocationEventName(memory->_buckets, "CFBitVector (store)");
	if (NULL == memory->_buckets) {
	    CFRelease(memory);
	    return NULL;
	}
	break;
    case kCFBitVectorFixedMutable:
    case kCFBitVectorImmutable:
	/* Don't round up capacity */
	__CFBitVectorSetCapacity(memory, capacity);
	__CFBitVectorSetNumBuckets(memory, __CFBitVectorNumBucketsForCapacity(capacity));
	memory->_buckets = (__CFBitVectorBucket *)((int8_t *)memory + sizeof(struct __CFBitVector));
	break;
    }
    __CFBitVectorSetNumBucketsUsed(memory, numBits / __CF_BITS_PER_BUCKET + 1);
    __CFBitVectorSetCount(memory, numBits);
    if (bytes) {
	/* This move is possible because bits are numbered from 0 on the left */
	memmove(memory->_buckets, bytes, (numBits + __CF_BITS_PER_BYTE - 1) / __CF_BITS_PER_BYTE);
    }
    __CFBitVectorSetMutableVariety(memory, __CFBitVectorMutableVarietyFromFlags(flags));
    return memory;
}

CFBitVectorRef CFBitVectorCreate(CFAllocatorRef allocator, const uint8_t *bytes, CFIndex numBits) {
   return __CFBitVectorInit(allocator, kCFBitVectorImmutable, numBits, bytes, numBits);
}

CFMutableBitVectorRef CFBitVectorCreateMutable(CFAllocatorRef allocator, CFIndex capacity) {
   return __CFBitVectorInit(allocator, (0 == capacity) ? kCFBitVectorMutable : kCFBitVectorFixedMutable, capacity, NULL, 0);
}

CFBitVectorRef CFBitVectorCreateCopy(CFAllocatorRef allocator, CFBitVectorRef bv) {
   __CFGenericValidateType(bv, __kCFBitVectorTypeID);
    return __CFBitVectorInit(allocator, kCFBitVectorImmutable, __CFBitVectorCount(bv), (const uint8_t *)bv->_buckets, __CFBitVectorCount(bv));
}

CFMutableBitVectorRef CFBitVectorCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFBitVectorRef bv) {
   __CFGenericValidateType(bv, __kCFBitVectorTypeID);
    return __CFBitVectorInit(allocator, (0 == capacity) ? kCFBitVectorMutable : kCFBitVectorFixedMutable, capacity, (const uint8_t *)bv->_buckets, __CFBitVectorCount(bv));
}

CFIndex CFBitVectorGetCount(CFBitVectorRef bv) {
    __CFGenericValidateType(bv, __kCFBitVectorTypeID);
    return __CFBitVectorCount(bv);
}

typedef __CFBitVectorBucket (*__CFInternalMapper)(__CFBitVectorBucket bucketValue, __CFBitVectorBucket bucketValueMask, void *context);

static void __CFBitVectorInternalMap(CFMutableBitVectorRef bv, CFRange range, __CFInternalMapper mapper, void *context) {
    CFIndex bucketIdx, bitOfBucket;
    CFIndex nBuckets;
    __CFBitVectorBucket bucketValMask, newBucketVal;
    if (0 == range.length) return;
    bucketIdx = range.location / __CF_BITS_PER_BUCKET;
    bitOfBucket = range.location & (__CF_BITS_PER_BUCKET - 1);
    /* Follow usual pattern of ramping up to a bit bucket boundary ...*/
    if (bitOfBucket + range.length < __CF_BITS_PER_BUCKET) {
	bucketValMask = __CFBitBucketMask(bitOfBucket, bitOfBucket + range.length - 1);
	range.length = 0;
    } else {
	bucketValMask = __CFBitBucketMask(bitOfBucket, __CF_BITS_PER_BUCKET - 1);
	range.length -= __CF_BITS_PER_BUCKET - bitOfBucket;
    }
    newBucketVal = mapper(bv->_buckets[bucketIdx], bucketValMask, context);
    bv->_buckets[bucketIdx] = (bv->_buckets[bucketIdx] & ~bucketValMask) | (newBucketVal & bucketValMask);
    bucketIdx++;
    /* ... clipping along with entire bit buckets ... */
    nBuckets = range.length / __CF_BITS_PER_BUCKET;
    range.length -= nBuckets * __CF_BITS_PER_BUCKET;
    while (nBuckets--) {
	newBucketVal = mapper(bv->_buckets[bucketIdx], ~0, context);
	bv->_buckets[bucketIdx] = newBucketVal;
	bucketIdx++;
    }
    /* ... and ramping down with the last fragmentary bit bucket. */
    if (0 != range.length) {
	bucketValMask = __CFBitBucketMask(0, range.length - 1);
	newBucketVal = mapper(bv->_buckets[bucketIdx], bucketValMask, context);
	bv->_buckets[bucketIdx] = (bv->_buckets[bucketIdx] & ~bucketValMask) | (newBucketVal & bucketValMask);
    }
}

struct _occursContext {
    CFBit value;
    CFIndex count;
};

static __CFBitVectorBucket __CFBitVectorCountBits(__CFBitVectorBucket bucketValue, __CFBitVectorBucket bucketValueMask, struct _occursContext *context) {
    static const __CFBitVectorBucket __CFNibbleBitCount[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
    __CFBitVectorBucket val;
    CFIndex idx;
    val = (context->value) ? (bucketValue & bucketValueMask) : (~bucketValue & bucketValueMask);
    for (idx = 0; idx < (CFIndex)sizeof(__CFBitVectorBucket) * 2; idx++) {
	context->count += __CFNibbleBitCount[val & 0xF];
	val = val >> 4;
    }
    return bucketValue;
}

CFIndex CFBitVectorGetCountOfBit(CFBitVectorRef bv, CFRange range, CFBit value) {
    struct _occursContext context;
    __CFGenericValidateType(bv, __kCFBitVectorTypeID);
    __CFBitVectorValidateRange(bv, range, __PRETTY_FUNCTION__);
    if (0 == range.length) return 0;
    context.value = value;
    context.count = 0;
    __CFBitVectorInternalMap((CFMutableBitVectorRef)bv, range, (__CFInternalMapper)__CFBitVectorCountBits, &context);
    return context.count;
}

Boolean CFBitVectorContainsBit(CFBitVectorRef bv, CFRange range, CFBit value) {
    __CFGenericValidateType(bv, __kCFBitVectorTypeID);
    __CFBitVectorValidateRange(bv, range, __PRETTY_FUNCTION__);
    return (CFBitVectorGetCountOfBit(bv, range, value) != 0) ? true : false;
}

CFBit CFBitVectorGetBitAtIndex(CFBitVectorRef bv, CFIndex idx) {
    __CFGenericValidateType(bv, __kCFBitVectorTypeID);
    CFAssert2(0 <= idx && idx < __CFBitVectorCount(bv), __kCFLogAssertion, "%s(): index (%d) out of bounds", __PRETTY_FUNCTION__, idx);
    return __CFBitVectorBit(bv->_buckets, idx);
}

struct _getBitsContext {
    uint8_t *curByte;
    CFIndex initBits;	/* Bits to extract off the front for the prev. byte */
    CFIndex totalBits;	/* This is for stopping at the end */
    bool ignoreFirstInitBits;
};

static __CFBitVectorBucket __CFBitVectorGetBits(__CFBitVectorBucket bucketValue, __CFBitVectorBucket bucketValueMask, void *ctx) {
    struct _getBitsContext *context = (struct _getBitsContext *)ctx;
    __CFBitVectorBucket val;
    CFIndex nBits;
    val = bucketValue & bucketValueMask;
    nBits = __CFMin(__CF_BITS_PER_BUCKET - context->initBits, context->totalBits);
    /* First initBits bits go in *curByte ... */
    if (0 < context->initBits) {
	if (!context->ignoreFirstInitBits) {
	    *context->curByte |= (uint8_t)(val >> (__CF_BITS_PER_BUCKET - context->initBits));
	    context->curByte++;
	    context->totalBits -= context->initBits;
	    context->ignoreFirstInitBits = false;
	}
	val <<= context->initBits;
    }
    /* ... then next groups of __CF_BITS_PER_BYTE go in *curByte ... */
    while (__CF_BITS_PER_BYTE <= nBits) {
	*context->curByte = (uint8_t)(val >> (__CF_BITS_PER_BUCKET - __CF_BITS_PER_BYTE));
	context->curByte++;
	context->totalBits -= context->initBits;
	nBits -= __CF_BITS_PER_BYTE;
	val <<= __CF_BITS_PER_BYTE;
    }
    /* ... then remaining bits go in *curByte */
    if (0 < nBits) {
	*context->curByte = (uint8_t)(val >> (__CF_BITS_PER_BUCKET - __CF_BITS_PER_BYTE));
	context->totalBits -= nBits;
    }
    return bucketValue;
}

void CFBitVectorGetBits(CFBitVectorRef bv, CFRange range, uint8_t *bytes) {
    struct _getBitsContext context;
    __CFGenericValidateType(bv, __kCFBitVectorTypeID);
    __CFBitVectorValidateRange(bv, range, __PRETTY_FUNCTION__);
    if (0 == range.length) return;
    context.curByte = bytes;
    context.initBits = range.location & (__CF_BITS_PER_BUCKET - 1);
    context.totalBits = range.length;
    context.ignoreFirstInitBits = true;
    __CFBitVectorInternalMap((CFMutableBitVectorRef)bv, range, __CFBitVectorGetBits, &context);
}

CFIndex CFBitVectorGetFirstIndexOfBit(CFBitVectorRef bv, CFRange range, CFBit value) {
    CFIndex idx;
    __CFGenericValidateType(bv, __kCFBitVectorTypeID);
    __CFBitVectorValidateRange(bv, range, __PRETTY_FUNCTION__);
    for (idx = 0; idx < range.length; idx++) {
	if (value == CFBitVectorGetBitAtIndex(bv, range.location + idx)) {
	    return range.location + idx;
	}
    }
    return kCFNotFound;
}

CFIndex CFBitVectorGetLastIndexOfBit(CFBitVectorRef bv, CFRange range, CFBit value) {
    CFIndex idx;
    __CFGenericValidateType(bv, __kCFBitVectorTypeID);
    __CFBitVectorValidateRange(bv, range, __PRETTY_FUNCTION__);
    for (idx = range.length; idx--;) {
	if (value == CFBitVectorGetBitAtIndex(bv, range.location + idx)) {
	    return range.location + idx;
	}
    }
    return kCFNotFound;
}

static void __CFBitVectorGrow(CFMutableBitVectorRef bv, CFIndex numNewValues) {
    CFIndex oldCount = __CFBitVectorCount(bv);
    CFIndex capacity = __CFBitVectorRoundUpCapacity(oldCount + numNewValues);
    CFAllocatorRef allocator = CFGetAllocator(bv);
    __CFBitVectorSetCapacity(bv, capacity);
    __CFBitVectorSetNumBuckets(bv, __CFBitVectorNumBucketsForCapacity(capacity));
    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, bv, bv->_buckets, CFAllocatorReallocate(allocator, bv->_buckets, __CFBitVectorNumBuckets(bv) * sizeof(__CFBitVectorBucket), 0));
    if (__CFOASafe) __CFSetLastAllocationEventName(bv->_buckets, "CFBitVector (store)");
    if (NULL == bv->_buckets) HALT;
}

static __CFBitVectorBucket __CFBitVectorZeroBits(__CFBitVectorBucket bucketValue, __CFBitVectorBucket bucketValueMask, void *context) {
    return 0;
}

static __CFBitVectorBucket __CFBitVectorOneBits(__CFBitVectorBucket bucketValue, __CFBitVectorBucket bucketValueMask, void *context) {
    return ~(__CFBitVectorBucket)0;
}

void CFBitVectorSetCount(CFMutableBitVectorRef bv, CFIndex count) {
    CFIndex cnt;
    CFAssert1(__CFBitVectorMutableVariety(bv) == kCFBitVectorMutable || __CFBitVectorMutableVariety(bv) == kCFBitVectorFixedMutable, __kCFLogAssertion, "%s(): bit vector is immutable", __PRETTY_FUNCTION__);
    cnt = __CFBitVectorCount(bv);
    switch (__CFBitVectorMutableVariety(bv)) {
    case kCFBitVectorMutable:
	if (cnt < count) {
	    __CFBitVectorGrow(bv, count - cnt);
	}
	break;
    case kCFBitVectorFixedMutable:
	CFAssert1(count <= __CFBitVectorCapacity(bv), __kCFLogAssertion, "%s(): fixed-capacity bit vector is full", __PRETTY_FUNCTION__);
	break;
    }
    if (cnt < count) {
	CFRange range = CFRangeMake(cnt, count - cnt);
        __CFBitVectorInternalMap(bv, range, __CFBitVectorZeroBits, NULL);
    }
    __CFBitVectorSetNumBucketsUsed(bv, count / __CF_BITS_PER_BUCKET + 1);
    __CFBitVectorSetCount(bv, count);
}

void CFBitVectorFlipBitAtIndex(CFMutableBitVectorRef bv, CFIndex idx) {
    __CFGenericValidateType(bv, __kCFBitVectorTypeID);
    CFAssert2(0 <= idx && idx < __CFBitVectorCount(bv), __kCFLogAssertion, "%s(): index (%d) out of bounds", __PRETTY_FUNCTION__, idx);
    CFAssert1(__CFBitVectorMutableVariety(bv) == kCFBitVectorMutable || __CFBitVectorMutableVariety(bv) == kCFBitVectorFixedMutable, __kCFLogAssertion, "%s(): bit vector is immutable", __PRETTY_FUNCTION__);
    __CFFlipBitVectorBit(bv->_buckets, idx);
}

static __CFBitVectorBucket __CFBitVectorFlipBits(__CFBitVectorBucket bucketValue, __CFBitVectorBucket bucketValueMask, void *context) {
    return (~(__CFBitVectorBucket)0) ^ bucketValue;
}

void CFBitVectorFlipBits(CFMutableBitVectorRef bv, CFRange range) {
    __CFGenericValidateType(bv, __kCFBitVectorTypeID);
    __CFBitVectorValidateRange(bv, range, __PRETTY_FUNCTION__);
    CFAssert1(__CFBitVectorMutableVariety(bv) == kCFBitVectorMutable || __CFBitVectorMutableVariety(bv) == kCFBitVectorFixedMutable, __kCFLogAssertion, "%s(): bit vector is immutable", __PRETTY_FUNCTION__);
    if (0 == range.length) return;
    __CFBitVectorInternalMap(bv, range, __CFBitVectorFlipBits, NULL);
}

void CFBitVectorSetBitAtIndex(CFMutableBitVectorRef bv, CFIndex idx, CFBit value) {
    __CFGenericValidateType(bv, __kCFBitVectorTypeID);
    CFAssert2(0 <= idx && idx < __CFBitVectorCount(bv), __kCFLogAssertion, "%s(): index (%d) out of bounds", __PRETTY_FUNCTION__, idx);
    CFAssert1(__CFBitVectorMutableVariety(bv) == kCFBitVectorMutable || __CFBitVectorMutableVariety(bv) == kCFBitVectorFixedMutable, __kCFLogAssertion, "%s(): bit vector is immutable", __PRETTY_FUNCTION__);
    __CFSetBitVectorBit(bv->_buckets, idx, value);
}

void CFBitVectorSetBits(CFMutableBitVectorRef bv, CFRange range, CFBit value) {
    __CFGenericValidateType(bv, __kCFBitVectorTypeID);
    __CFBitVectorValidateRange(bv, range, __PRETTY_FUNCTION__);
    CFAssert1(__CFBitVectorMutableVariety(bv) == kCFBitVectorMutable || __CFBitVectorMutableVariety(bv) == kCFBitVectorFixedMutable, __kCFLogAssertion, "%s(): bit vector is immutable", __PRETTY_FUNCTION__);
    if (0 == range.length) return;
    if (value) {
	__CFBitVectorInternalMap(bv, range, __CFBitVectorOneBits, NULL);
    } else {
	__CFBitVectorInternalMap(bv, range, __CFBitVectorZeroBits, NULL);
    }
}

void CFBitVectorSetAllBits(CFMutableBitVectorRef bv, CFBit value) {
    CFIndex nBuckets, leftover;
    __CFGenericValidateType(bv, __kCFBitVectorTypeID);
    CFAssert1(__CFBitVectorMutableVariety(bv) == kCFBitVectorMutable || __CFBitVectorMutableVariety(bv) == kCFBitVectorFixedMutable, __kCFLogAssertion, "%s(): bit vector is immutable", __PRETTY_FUNCTION__);
    nBuckets = __CFBitVectorCount(bv) / __CF_BITS_PER_BUCKET;
    leftover = __CFBitVectorCount(bv) - nBuckets * __CF_BITS_PER_BUCKET;
    if (0 < leftover) {
	CFRange range = CFRangeMake(nBuckets * __CF_BITS_PER_BUCKET, leftover);
	if (value) {
	    __CFBitVectorInternalMap(bv, range, __CFBitVectorOneBits, NULL);
	} else {
	    __CFBitVectorInternalMap(bv, range, __CFBitVectorZeroBits, NULL);
	}
    }
    memset(bv->_buckets, (value ? ~0 : 0), nBuckets);
}

#undef __CFBitVectorValidateRange