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