1/* 2 * Copyright (c) 2014 Apple Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23 24/* CFBitVector.c 25 Copyright (c) 1998-2013, Apple Inc. All rights reserved. 26 Responsibility: Christopher Kane 27*/ 28 29#include <CoreFoundation/CFBitVector.h> 30#include "CFInternal.h" 31#include <string.h> 32 33/* The bucket type must be unsigned, at least one byte in size, and 34 a power of 2 in number of bits; bits are numbered from 0 from left 35 to right (bit 0 is the most significant) */ 36typedef uint8_t __CFBitVectorBucket; 37 38#define __CFBITVECTORBUCKET_SIZE 8 39#define __CF_BITS_PER_BYTE 8 40 41enum { 42 __CF_BITS_PER_BYTE_MASK = 0x07 43}; 44 45enum { 46 __CF_BITS_PER_BUCKET = (__CF_BITS_PER_BYTE * sizeof(__CFBitVectorBucket)), 47 __CF_BITS_PER_BUCKET_MASK = 0x07 // __CF_BITS_PER_BYTE_MASK * lg2(sizeof(__CFBitVectorBucket)) 48}; 49 50CF_INLINE CFIndex __CFBitVectorRoundUpCapacity(CFIndex capacity) { 51 if (0 == capacity) capacity = 1; 52 return ((capacity + 63) / 64) * 64; 53} 54 55CF_INLINE CFIndex __CFBitVectorNumBucketsForCapacity(CFIndex capacity) { 56 return capacity / __CF_BITS_PER_BUCKET + ((capacity & __CF_BITS_PER_BUCKET_MASK) ? 1 : 0); 57} 58 59struct __CFBitVector { 60 CFRuntimeBase _base; 61 CFIndex _count; /* number of bits */ 62 CFIndex _capacity; /* maximum number of bits */ 63 __CFBitVectorBucket *_buckets; 64}; 65 66CF_INLINE UInt32 __CFBitVectorMutableVariety(const void *cf) { 67 return __CFBitfieldGetValue(((const CFRuntimeBase *)cf)->_cfinfo[CF_INFO_BITS], 3, 2); 68} 69 70CF_INLINE void __CFBitVectorSetMutableVariety(void *cf, UInt32 v) { 71 __CFBitfieldSetValue(((CFRuntimeBase *)cf)->_cfinfo[CF_INFO_BITS], 3, 2, v); 72} 73 74CF_INLINE UInt32 __CFBitVectorMutableVarietyFromFlags(UInt32 flags) { 75 return __CFBitfieldGetValue(flags, 1, 0); 76} 77 78// ensure that uses of these inlines are correct, bytes vs. buckets vs. bits 79CF_INLINE CFIndex __CFBitVectorCount(CFBitVectorRef bv) { 80 return bv->_count; 81} 82 83CF_INLINE void __CFBitVectorSetCount(CFMutableBitVectorRef bv, CFIndex v) { 84 bv->_count = v; 85} 86 87CF_INLINE CFIndex __CFBitVectorCapacity(CFBitVectorRef bv) { 88 return bv->_capacity; 89} 90 91CF_INLINE void __CFBitVectorSetCapacity(CFMutableBitVectorRef bv, CFIndex v) { 92 bv->_capacity = v; 93} 94 95CF_INLINE CFIndex __CFBitVectorNumBucketsUsed(CFBitVectorRef bv) { 96 return bv->_count / __CF_BITS_PER_BUCKET + 1; 97} 98 99CF_INLINE void __CFBitVectorSetNumBucketsUsed(CFMutableBitVectorRef bv, CFIndex v) { 100 /* for a CFBitVector, _bucketsUsed == _count / __CF_BITS_PER_BUCKET + 1 */ 101} 102 103CF_INLINE CFIndex __CFBitVectorNumBuckets(CFBitVectorRef bv) { 104 return bv->_capacity / __CF_BITS_PER_BUCKET + 1; 105} 106 107CF_INLINE void __CFBitVectorSetNumBuckets(CFMutableBitVectorRef bv, CFIndex v) { 108 /* for a CFBitVector, _bucketsNum == _capacity / __CF_BITS_PER_BUCKET + 1 */ 109} 110 111static __CFBitVectorBucket __CFBitBucketMask(CFIndex bottomBit, CFIndex topBit) { 112 CFIndex shiftL = __CF_BITS_PER_BUCKET - topBit + bottomBit - 1; 113 __CFBitVectorBucket result = ~(__CFBitVectorBucket)0; 114 result = (result << shiftL); 115 result = (result >> bottomBit); 116 return result; 117} 118 119CF_INLINE CFBit __CFBitVectorBit(__CFBitVectorBucket *buckets, CFIndex idx) { 120 CFIndex bucketIdx = idx / __CF_BITS_PER_BUCKET; 121 CFIndex bitOfBucket = idx & (__CF_BITS_PER_BUCKET - 1); 122 return (buckets[bucketIdx] >> (__CF_BITS_PER_BUCKET - 1 - bitOfBucket)) & 0x1; 123} 124 125CF_INLINE void __CFSetBitVectorBit(__CFBitVectorBucket *buckets, CFIndex idx, CFBit value) { 126 CFIndex bucketIdx = idx / __CF_BITS_PER_BUCKET; 127 CFIndex bitOfBucket = idx & (__CF_BITS_PER_BUCKET - 1); 128 if (value) { 129 buckets[bucketIdx] |= (1 << (__CF_BITS_PER_BUCKET - 1 - bitOfBucket)); 130 } else { 131 buckets[bucketIdx] &= ~(1 << (__CF_BITS_PER_BUCKET - 1 - bitOfBucket)); 132 } 133} 134 135CF_INLINE void __CFFlipBitVectorBit(__CFBitVectorBucket *buckets, CFIndex idx) { 136 CFIndex bucketIdx = idx / __CF_BITS_PER_BUCKET; 137 CFIndex bitOfBucket = idx & (__CF_BITS_PER_BUCKET - 1); 138 buckets[bucketIdx] ^= (1 << (__CF_BITS_PER_BUCKET - 1 - bitOfBucket)); 139} 140 141#if defined(DEBUG) 142CF_INLINE void __CFBitVectorValidateRange(CFBitVectorRef bv, CFRange range, const char *func) { 143 CFAssert2(0 <= range.location && range.location < __CFBitVectorCount(bv), __kCFLogAssertion, "%s(): range.location index (%d) out of bounds", func, range.location); 144 CFAssert2(0 <= range.length, __kCFLogAssertion, "%s(): range.length (%d) cannot be less than zero", func, range.length); 145 CFAssert2(range.location + range.length <= __CFBitVectorCount(bv), __kCFLogAssertion, "%s(): ending index (%d) out of bounds", func, range.location + range.length); 146} 147#else 148#define __CFBitVectorValidateRange(bf,r,f) 149#endif 150 151static Boolean __CFBitVectorEqual(CFTypeRef cf1, CFTypeRef cf2) { 152 CFBitVectorRef bv1 = (CFBitVectorRef)cf1; 153 CFBitVectorRef bv2 = (CFBitVectorRef)cf2; 154 CFIndex idx, cnt; 155 cnt = __CFBitVectorCount(bv1); 156 if (cnt != __CFBitVectorCount(bv2)) return false; 157 if (0 == cnt) return true; 158 for (idx = 0; idx < (cnt / __CF_BITS_PER_BUCKET) + 1; idx++) { 159 __CFBitVectorBucket val1 = bv1->_buckets[idx]; 160 __CFBitVectorBucket val2 = bv2->_buckets[idx]; 161 if (val1 != val2) return false; 162 } 163 return true; 164} 165 166static CFHashCode __CFBitVectorHash(CFTypeRef cf) { 167 CFBitVectorRef bv = (CFBitVectorRef)cf; 168 return __CFBitVectorCount(bv); 169} 170 171static CFStringRef __CFBitVectorCopyDescription(CFTypeRef cf) { 172 CFBitVectorRef bv = (CFBitVectorRef)cf; 173 CFMutableStringRef result; 174 CFIndex idx, cnt; 175 __CFBitVectorBucket *buckets; 176 cnt = __CFBitVectorCount(bv); 177 buckets = bv->_buckets; 178 result = CFStringCreateMutable(kCFAllocatorSystemDefault, 0); 179 CFStringAppendFormat(result, NULL, CFSTR("<CFBitVector %p [%p]>{count = %lu, capacity = %lu, objects = (\n"), cf, CFGetAllocator(bv), (unsigned long)cnt, __CFBitVectorCapacity(bv)); 180 for (idx = 0; idx < (cnt / 64); idx++) { /* Print groups of 64 */ 181 CFIndex idx2; 182 CFStringAppendFormat(result, NULL, CFSTR("\t%lu : "), (unsigned long)(idx * 64)); 183 for (idx2 = 0; idx2 < 64; idx2 += 4) { 184 CFIndex bucketIdx = (idx << 6) + idx2; 185 CFStringAppendFormat(result, NULL, CFSTR("%u%u%u%u"), 186 (unsigned int)__CFBitVectorBit(buckets, bucketIdx + 0), 187 (unsigned int)__CFBitVectorBit(buckets, bucketIdx + 1), 188 (unsigned int)__CFBitVectorBit(buckets, bucketIdx + 2), 189 (unsigned int)__CFBitVectorBit(buckets, bucketIdx + 3)); 190 } 191 CFStringAppend(result, CFSTR("\n")); 192 } 193 if (idx * 64 < cnt) { 194 CFStringAppendFormat(result, NULL, CFSTR("\t%lu : "), (unsigned long)(idx * 64)); 195 for (idx = (idx * 64); idx < cnt; idx++) { /* Print remainder */ 196 CFStringAppendFormat(result, NULL, CFSTR("%u"), (unsigned int)__CFBitVectorBit(buckets, idx)); 197 } 198 } 199 CFStringAppend(result, CFSTR("\n)}")); 200 return result; 201} 202 203enum { 204 kCFBitVectorImmutable = 0x0, /* unchangable and fixed capacity; default */ 205 kCFBitVectorMutable = 0x1, /* changeable and variable capacity */ 206}; 207 208static void __CFBitVectorDeallocate(CFTypeRef cf) { 209 CFMutableBitVectorRef bv = (CFMutableBitVectorRef)cf; 210 CFAllocatorRef allocator = CFGetAllocator(bv); 211 if (bv->_buckets) _CFAllocatorDeallocateGC(allocator, bv->_buckets); 212} 213 214static CFTypeID __kCFBitVectorTypeID = _kCFRuntimeNotATypeID; 215 216static const CFRuntimeClass __CFBitVectorClass = { 217 _kCFRuntimeScannedObject, 218 "CFBitVector", 219 NULL, // init 220 NULL, // copy 221 __CFBitVectorDeallocate, 222 __CFBitVectorEqual, 223 __CFBitVectorHash, 224 NULL, // 225 __CFBitVectorCopyDescription 226}; 227 228CF_PRIVATE void __CFBitVectorInitialize(void) { 229 __kCFBitVectorTypeID = _CFRuntimeRegisterClass(&__CFBitVectorClass); 230} 231 232CFTypeID CFBitVectorGetTypeID(void) { 233 return __kCFBitVectorTypeID; 234} 235 236static CFMutableBitVectorRef __CFBitVectorInit(CFAllocatorRef allocator, CFOptionFlags flags, CFIndex capacity, const uint8_t *bytes, CFIndex numBits) { 237 CFMutableBitVectorRef memory; 238 CFIndex size; 239 CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity); 240 CFAssert2(0 <= numBits, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numBits); 241 size = sizeof(struct __CFBitVector) - sizeof(CFRuntimeBase); 242 memory = (CFMutableBitVectorRef)_CFRuntimeCreateInstance(allocator, __kCFBitVectorTypeID, size, NULL); 243 if (NULL == memory) { 244 return NULL; 245 } 246 __CFBitVectorSetCapacity(memory, __CFBitVectorRoundUpCapacity(numBits)); 247 __CFBitVectorSetNumBuckets(memory, __CFBitVectorNumBucketsForCapacity(__CFBitVectorRoundUpCapacity(numBits))); 248 __CFAssignWithWriteBarrier((void **)&memory->_buckets, _CFAllocatorAllocateGC(allocator, __CFBitVectorNumBuckets(memory) * sizeof(__CFBitVectorBucket), 0)); 249 if (__CFOASafe) __CFSetLastAllocationEventName(memory->_buckets, "CFBitVector (store)"); 250 if (NULL == memory->_buckets) { 251 CFRelease(memory); 252 return NULL; 253 } 254 memset(memory->_buckets, 0, __CFBitVectorNumBuckets(memory) * sizeof(__CFBitVectorBucket)); 255 __CFBitVectorSetNumBucketsUsed(memory, numBits / __CF_BITS_PER_BUCKET + 1); 256 __CFBitVectorSetCount(memory, numBits); 257 if (bytes) { 258 /* This move is possible because bits are numbered from 0 on the left */ 259 memmove(memory->_buckets, bytes, numBits / __CF_BITS_PER_BYTE + (numBits & __CF_BITS_PER_BYTE_MASK ? 1 : 0)); 260 } 261 __CFBitVectorSetMutableVariety(memory, __CFBitVectorMutableVarietyFromFlags(flags)); 262 return memory; 263} 264 265CFBitVectorRef CFBitVectorCreate(CFAllocatorRef allocator, const uint8_t *bytes, CFIndex numBits) { 266 return __CFBitVectorInit(allocator, kCFBitVectorImmutable, numBits, bytes, numBits); 267} 268 269CFMutableBitVectorRef CFBitVectorCreateMutable(CFAllocatorRef allocator, CFIndex capacity) { 270 return __CFBitVectorInit(allocator, kCFBitVectorMutable, capacity, NULL, 0); 271} 272 273CFBitVectorRef CFBitVectorCreateCopy(CFAllocatorRef allocator, CFBitVectorRef bv) { 274 __CFGenericValidateType(bv, __kCFBitVectorTypeID); 275 return __CFBitVectorInit(allocator, kCFBitVectorImmutable, __CFBitVectorCount(bv), (const uint8_t *)bv->_buckets, __CFBitVectorCount(bv)); 276} 277 278CFMutableBitVectorRef CFBitVectorCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFBitVectorRef bv) { 279 __CFGenericValidateType(bv, __kCFBitVectorTypeID); 280 return __CFBitVectorInit(allocator, kCFBitVectorMutable, capacity, (const uint8_t *)bv->_buckets, __CFBitVectorCount(bv)); 281} 282 283CFIndex CFBitVectorGetCount(CFBitVectorRef bv) { 284 __CFGenericValidateType(bv, __kCFBitVectorTypeID); 285 return __CFBitVectorCount(bv); 286} 287 288typedef __CFBitVectorBucket (*__CFInternalMapper)(__CFBitVectorBucket bucketValue, __CFBitVectorBucket bucketValueMask, void *context); 289 290static void __CFBitVectorInternalMap(CFMutableBitVectorRef bv, CFRange range, __CFInternalMapper mapper, void *context) { 291 CFIndex bucketIdx, bitOfBucket; 292 CFIndex nBuckets; 293 __CFBitVectorBucket bucketValMask, newBucketVal; 294 if (0 == range.length) return; 295 bucketIdx = range.location / __CF_BITS_PER_BUCKET; 296 bitOfBucket = range.location & (__CF_BITS_PER_BUCKET - 1); 297 /* Follow usual pattern of ramping up to a bit bucket boundary ...*/ 298 if (bitOfBucket + range.length < __CF_BITS_PER_BUCKET) { 299 bucketValMask = __CFBitBucketMask(bitOfBucket, bitOfBucket + range.length - 1); 300 range.length = 0; 301 } else { 302 bucketValMask = __CFBitBucketMask(bitOfBucket, __CF_BITS_PER_BUCKET - 1); 303 range.length -= __CF_BITS_PER_BUCKET - bitOfBucket; 304 } 305 newBucketVal = mapper(bv->_buckets[bucketIdx], bucketValMask, context); 306 bv->_buckets[bucketIdx] = (bv->_buckets[bucketIdx] & ~bucketValMask) | (newBucketVal & bucketValMask); 307 bucketIdx++; 308 /* ... clipping along with entire bit buckets ... */ 309 nBuckets = range.length / __CF_BITS_PER_BUCKET; 310 range.length -= nBuckets * __CF_BITS_PER_BUCKET; 311 while (nBuckets--) { 312 newBucketVal = mapper(bv->_buckets[bucketIdx], ~0, context); 313 bv->_buckets[bucketIdx] = newBucketVal; 314 bucketIdx++; 315 } 316 /* ... and ramping down with the last fragmentary bit bucket. */ 317 if (0 != range.length) { 318 bucketValMask = __CFBitBucketMask(0, range.length - 1); 319 newBucketVal = mapper(bv->_buckets[bucketIdx], bucketValMask, context); 320 bv->_buckets[bucketIdx] = (bv->_buckets[bucketIdx] & ~bucketValMask) | (newBucketVal & bucketValMask); 321 } 322} 323 324struct _occursContext { 325 CFBit value; 326 CFIndex count; 327}; 328 329static __CFBitVectorBucket __CFBitVectorCountBits(__CFBitVectorBucket bucketValue, __CFBitVectorBucket bucketValueMask, struct _occursContext *context) { 330 static const __CFBitVectorBucket __CFNibbleBitCount[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}; 331 __CFBitVectorBucket val; 332 CFIndex idx; 333 val = (context->value) ? (bucketValue & bucketValueMask) : (~bucketValue & bucketValueMask); 334 for (idx = 0; idx < (CFIndex)sizeof(__CFBitVectorBucket) * 2; idx++) { 335 context->count += __CFNibbleBitCount[val & 0xF]; 336 val = val >> 4; 337 } 338 return bucketValue; 339} 340 341CFIndex CFBitVectorGetCountOfBit(CFBitVectorRef bv, CFRange range, CFBit value) { 342 struct _occursContext context; 343 __CFGenericValidateType(bv, __kCFBitVectorTypeID); 344 __CFBitVectorValidateRange(bv, range, __PRETTY_FUNCTION__); 345 if (0 == range.length) return 0; 346 context.value = value; 347 context.count = 0; 348 __CFBitVectorInternalMap((CFMutableBitVectorRef)bv, range, (__CFInternalMapper)__CFBitVectorCountBits, &context); 349 return context.count; 350} 351 352Boolean CFBitVectorContainsBit(CFBitVectorRef bv, CFRange range, CFBit value) { 353 __CFGenericValidateType(bv, __kCFBitVectorTypeID); 354 __CFBitVectorValidateRange(bv, range, __PRETTY_FUNCTION__); 355 return (CFBitVectorGetCountOfBit(bv, range, value) != 0) ? true : false; 356} 357 358CFBit CFBitVectorGetBitAtIndex(CFBitVectorRef bv, CFIndex idx) { 359 __CFGenericValidateType(bv, __kCFBitVectorTypeID); 360 CFAssert2(0 <= idx && idx < __CFBitVectorCount(bv), __kCFLogAssertion, "%s(): index (%d) out of bounds", __PRETTY_FUNCTION__, idx); 361 return __CFBitVectorBit(bv->_buckets, idx); 362} 363 364struct _getBitsContext { 365 uint8_t *curByte; 366 CFIndex initBits; /* Bits to extract off the front for the prev. byte */ 367 CFIndex totalBits; /* This is for stopping at the end */ 368 bool ignoreFirstInitBits; 369}; 370 371static __CFBitVectorBucket __CFBitVectorGetBits(__CFBitVectorBucket bucketValue, __CFBitVectorBucket bucketValueMask, void *ctx) { 372 struct _getBitsContext *context = (struct _getBitsContext *)ctx; 373 __CFBitVectorBucket val; 374 CFIndex nBits; 375 val = bucketValue & bucketValueMask; 376 nBits = __CFMin(__CF_BITS_PER_BUCKET - context->initBits, context->totalBits); 377 /* First initBits bits go in *curByte ... */ 378 if (0 < context->initBits) { 379 if (!context->ignoreFirstInitBits) { 380 *context->curByte |= (uint8_t)(val >> (__CF_BITS_PER_BUCKET - context->initBits)); 381 context->curByte++; 382 context->totalBits -= context->initBits; 383 context->ignoreFirstInitBits = false; 384 } 385 val <<= context->initBits; 386 } 387 /* ... then next groups of __CF_BITS_PER_BYTE go in *curByte ... */ 388 while (__CF_BITS_PER_BYTE <= nBits) { 389 *context->curByte = (uint8_t)(val >> (__CF_BITS_PER_BUCKET - __CF_BITS_PER_BYTE)); 390 context->curByte++; 391 context->totalBits -= context->initBits; 392 nBits -= __CF_BITS_PER_BYTE; 393#if __CFBITVECTORBUCKET_SIZE > __CF_BITS_PER_BYTE 394 val <<= __CF_BITS_PER_BYTE; 395#else 396 val = 0; 397#endif 398 } 399 /* ... then remaining bits go in *curByte */ 400 if (0 < nBits) { 401 *context->curByte = (uint8_t)(val >> (__CF_BITS_PER_BUCKET - __CF_BITS_PER_BYTE)); 402 context->totalBits -= nBits; 403 } 404 return bucketValue; 405} 406 407void CFBitVectorGetBits(CFBitVectorRef bv, CFRange range, uint8_t *bytes) { 408 struct _getBitsContext context; 409 __CFGenericValidateType(bv, __kCFBitVectorTypeID); 410 __CFBitVectorValidateRange(bv, range, __PRETTY_FUNCTION__); 411 if (0 == range.length) return; 412 context.curByte = bytes; 413 context.initBits = range.location & (__CF_BITS_PER_BUCKET - 1); 414 context.totalBits = range.length; 415 context.ignoreFirstInitBits = true; 416 __CFBitVectorInternalMap((CFMutableBitVectorRef)bv, range, __CFBitVectorGetBits, &context); 417} 418 419CFIndex CFBitVectorGetFirstIndexOfBit(CFBitVectorRef bv, CFRange range, CFBit value) { 420 CFIndex idx; 421 __CFGenericValidateType(bv, __kCFBitVectorTypeID); 422 __CFBitVectorValidateRange(bv, range, __PRETTY_FUNCTION__); 423 for (idx = 0; idx < range.length; idx++) { 424 if (value == CFBitVectorGetBitAtIndex(bv, range.location + idx)) { 425 return range.location + idx; 426 } 427 } 428 return kCFNotFound; 429} 430 431CFIndex CFBitVectorGetLastIndexOfBit(CFBitVectorRef bv, CFRange range, CFBit value) { 432 CFIndex idx; 433 __CFGenericValidateType(bv, __kCFBitVectorTypeID); 434 __CFBitVectorValidateRange(bv, range, __PRETTY_FUNCTION__); 435 for (idx = range.length; idx--;) { 436 if (value == CFBitVectorGetBitAtIndex(bv, range.location + idx)) { 437 return range.location + idx; 438 } 439 } 440 return kCFNotFound; 441} 442 443static void __CFBitVectorGrow(CFMutableBitVectorRef bv, CFIndex numNewValues) { 444 CFIndex oldCount = __CFBitVectorCount(bv); 445 CFIndex capacity = __CFBitVectorRoundUpCapacity(oldCount + numNewValues); 446 CFAllocatorRef allocator = CFGetAllocator(bv); 447 __CFBitVectorSetCapacity(bv, capacity); 448 __CFBitVectorSetNumBuckets(bv, __CFBitVectorNumBucketsForCapacity(capacity)); 449 __CFAssignWithWriteBarrier((void **)&bv->_buckets, CFAllocatorReallocate(allocator, bv->_buckets, __CFBitVectorNumBuckets(bv) * sizeof(__CFBitVectorBucket), 0)); 450 if (__CFOASafe) __CFSetLastAllocationEventName(bv->_buckets, "CFBitVector (store)"); 451 if (NULL == bv->_buckets) HALT; 452} 453 454static __CFBitVectorBucket __CFBitVectorZeroBits(__CFBitVectorBucket bucketValue, __CFBitVectorBucket bucketValueMask, void *context) { 455 return 0; 456} 457 458static __CFBitVectorBucket __CFBitVectorOneBits(__CFBitVectorBucket bucketValue, __CFBitVectorBucket bucketValueMask, void *context) { 459 return ~(__CFBitVectorBucket)0; 460} 461 462void CFBitVectorSetCount(CFMutableBitVectorRef bv, CFIndex count) { 463 CFIndex cnt; 464 CFAssert1(__CFBitVectorMutableVariety(bv) == kCFBitVectorMutable, __kCFLogAssertion, "%s(): bit vector is immutable", __PRETTY_FUNCTION__); 465 cnt = __CFBitVectorCount(bv); 466 switch (__CFBitVectorMutableVariety(bv)) { 467 case kCFBitVectorMutable: 468 if (cnt < count) { 469 __CFBitVectorGrow(bv, count - cnt); 470 } 471 break; 472 } 473 if (cnt < count) { 474 CFRange range = CFRangeMake(cnt, count - cnt); 475 __CFBitVectorInternalMap(bv, range, __CFBitVectorZeroBits, NULL); 476 } 477 __CFBitVectorSetNumBucketsUsed(bv, count / __CF_BITS_PER_BUCKET + 1); 478 __CFBitVectorSetCount(bv, count); 479} 480 481void CFBitVectorFlipBitAtIndex(CFMutableBitVectorRef bv, CFIndex idx) { 482 __CFGenericValidateType(bv, __kCFBitVectorTypeID); 483 CFAssert2(0 <= idx && idx < __CFBitVectorCount(bv), __kCFLogAssertion, "%s(): index (%d) out of bounds", __PRETTY_FUNCTION__, idx); 484 CFAssert1(__CFBitVectorMutableVariety(bv) == kCFBitVectorMutable, __kCFLogAssertion, "%s(): bit vector is immutable", __PRETTY_FUNCTION__); 485 __CFFlipBitVectorBit(bv->_buckets, idx); 486} 487 488static __CFBitVectorBucket __CFBitVectorFlipBits(__CFBitVectorBucket bucketValue, __CFBitVectorBucket bucketValueMask, void *context) { 489 return (~(__CFBitVectorBucket)0) ^ bucketValue; 490} 491 492void CFBitVectorFlipBits(CFMutableBitVectorRef bv, CFRange range) { 493 __CFGenericValidateType(bv, __kCFBitVectorTypeID); 494 __CFBitVectorValidateRange(bv, range, __PRETTY_FUNCTION__); 495 CFAssert1(__CFBitVectorMutableVariety(bv) == kCFBitVectorMutable, __kCFLogAssertion, "%s(): bit vector is immutable", __PRETTY_FUNCTION__); 496 if (0 == range.length) return; 497 __CFBitVectorInternalMap(bv, range, __CFBitVectorFlipBits, NULL); 498} 499 500void CFBitVectorSetBitAtIndex(CFMutableBitVectorRef bv, CFIndex idx, CFBit value) { 501 __CFGenericValidateType(bv, __kCFBitVectorTypeID); 502 CFAssert2(0 <= idx && idx < __CFBitVectorCount(bv), __kCFLogAssertion, "%s(): index (%d) out of bounds", __PRETTY_FUNCTION__, idx); 503 CFAssert1(__CFBitVectorMutableVariety(bv) == kCFBitVectorMutable, __kCFLogAssertion, "%s(): bit vector is immutable", __PRETTY_FUNCTION__); 504 __CFSetBitVectorBit(bv->_buckets, idx, value); 505} 506 507void CFBitVectorSetBits(CFMutableBitVectorRef bv, CFRange range, CFBit value) { 508 __CFGenericValidateType(bv, __kCFBitVectorTypeID); 509 __CFBitVectorValidateRange(bv, range, __PRETTY_FUNCTION__); 510 CFAssert1(__CFBitVectorMutableVariety(bv) == kCFBitVectorMutable , __kCFLogAssertion, "%s(): bit vector is immutable", __PRETTY_FUNCTION__); 511 if (0 == range.length) return; 512 if (value) { 513 __CFBitVectorInternalMap(bv, range, __CFBitVectorOneBits, NULL); 514 } else { 515 __CFBitVectorInternalMap(bv, range, __CFBitVectorZeroBits, NULL); 516 } 517} 518 519void CFBitVectorSetAllBits(CFMutableBitVectorRef bv, CFBit value) { 520 CFIndex nBuckets, leftover; 521 __CFGenericValidateType(bv, __kCFBitVectorTypeID); 522 CFAssert1(__CFBitVectorMutableVariety(bv) == kCFBitVectorMutable , __kCFLogAssertion, "%s(): bit vector is immutable", __PRETTY_FUNCTION__); 523 nBuckets = __CFBitVectorCount(bv) / __CF_BITS_PER_BUCKET; 524 leftover = __CFBitVectorCount(bv) - nBuckets * __CF_BITS_PER_BUCKET; 525 if (0 < leftover) { 526 CFRange range = CFRangeMake(nBuckets * __CF_BITS_PER_BUCKET, leftover); 527 if (value) { 528 __CFBitVectorInternalMap(bv, range, __CFBitVectorOneBits, NULL); 529 } else { 530 __CFBitVectorInternalMap(bv, range, __CFBitVectorZeroBits, NULL); 531 } 532 } 533 memset(bv->_buckets, (value ? ~0 : 0), nBuckets); 534} 535 536#undef __CFBitVectorValidateRange 537 538