Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Branch: master
Fetching contributors…

Cannot retrieve contributors at this time

557 lines (494 sloc) 23.937 kB
/*
* 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
Jump to Line
Something went wrong with that request. Please try again.