--- /dev/null
+/*
+ * 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
+
projects / apple / cf.git / blobdiff