CFBitVector.c

   1 /*
   2  * Copyright (c) 2010 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-2009, 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 enum {
  39     __CF_BITS_PER_BYTE = 8,
  40     __CF_BITS_PER_BYTE_MASK = 0x07
  41 };
  42
  43 enum {
  44     __CF_BITS_PER_BUCKET = (__CF_BITS_PER_BYTE * sizeof(__CFBitVectorBucket)),
  45     __CF_BITS_PER_BUCKET_MASK = 0x07    // __CF_BITS_PER_BYTE_MASK * lg2(sizeof(__CFBitVectorBucket))
  46 };
  47
  48 CF_INLINE CFIndex __CFBitVectorRoundUpCapacity(CFIndex capacity) {
  49     if (0 == capacity) capacity = 1;
  50     return ((capacity + 63) / 64) * 64;
  51 }
  52
  53 CF_INLINE CFIndex __CFBitVectorNumBucketsForCapacity(CFIndex capacity) {
  54     return capacity / __CF_BITS_PER_BUCKET + ((capacity & __CF_BITS_PER_BUCKET_MASK) ? 1 : 0);
  55 }
  56
  57 struct __CFBitVector {
  58     CFRuntimeBase _base;
  59     CFIndex _count;     /* number of bits */
  60     CFIndex _capacity;  /* maximum number of bits */
  61     __CFBitVectorBucket *_buckets;
  62 };
  63
  64 CF_INLINE UInt32 __CFBitVectorMutableVariety(const void *cf) {
  65     return __CFBitfieldGetValue(((const CFRuntimeBase *)cf)->_cfinfo[CF_INFO_BITS], 3, 2);
  66 }
  67
  68 CF_INLINE void __CFBitVectorSetMutableVariety(void *cf, UInt32 v) {
  69     __CFBitfieldSetValue(((CFRuntimeBase *)cf)->_cfinfo[CF_INFO_BITS], 3, 2, v);
  70 }
  71
  72 CF_INLINE UInt32 __CFBitVectorMutableVarietyFromFlags(UInt32 flags) {
  73     return __CFBitfieldGetValue(flags, 1, 0);
  74 }
  75
  76 // ensure that uses of these inlines are correct, bytes vs. buckets vs. bits
  77 CF_INLINE CFIndex __CFBitVectorCount(CFBitVectorRef bv) {
  78     return bv->_count;
  79 }
  80
  81 CF_INLINE void __CFBitVectorSetCount(CFMutableBitVectorRef bv, CFIndex v) {
  82     bv->_count = v;
  83 }
  84
  85 CF_INLINE CFIndex __CFBitVectorCapacity(CFBitVectorRef bv) {
  86     return bv->_capacity;
  87 }
  88
  89 CF_INLINE void __CFBitVectorSetCapacity(CFMutableBitVectorRef bv, CFIndex v) {
  90     bv->_capacity = v;
  91 }
  92
  93 CF_INLINE CFIndex __CFBitVectorNumBucketsUsed(CFBitVectorRef bv) {
  94     return bv->_count / __CF_BITS_PER_BUCKET + 1;
  95 }
  96
  97 CF_INLINE void __CFBitVectorSetNumBucketsUsed(CFMutableBitVectorRef bv, CFIndex v) {
  98     /* for a CFBitVector, _bucketsUsed == _count / __CF_BITS_PER_BUCKET + 1 */
  99 }
 100
 101 CF_INLINE CFIndex __CFBitVectorNumBuckets(CFBitVectorRef bv) {
 102     return bv->_capacity / __CF_BITS_PER_BUCKET + 1;
 103 }
 104
 105 CF_INLINE void __CFBitVectorSetNumBuckets(CFMutableBitVectorRef bv, CFIndex v) {
 106     /* for a CFBitVector, _bucketsNum == _capacity / __CF_BITS_PER_BUCKET + 1 */
 107 }
 108
 109 static __CFBitVectorBucket __CFBitBucketMask(CFIndex bottomBit, CFIndex topBit) {
 110     CFIndex shiftL = __CF_BITS_PER_BUCKET - topBit + bottomBit - 1;
 111     __CFBitVectorBucket result = ~(__CFBitVectorBucket)0;
 112     result = (result << shiftL);
 113     result = (result >> bottomBit);
 114     return result;
 115 }
 116
 117 CF_INLINE CFBit __CFBitVectorBit(__CFBitVectorBucket *buckets, CFIndex idx) {
 118     CFIndex bucketIdx = idx / __CF_BITS_PER_BUCKET;
 119     CFIndex bitOfBucket = idx & (__CF_BITS_PER_BUCKET - 1);
 120     return (buckets[bucketIdx] >> (__CF_BITS_PER_BUCKET - 1 - bitOfBucket)) & 0x1;
 121 }
 122
 123 CF_INLINE void __CFSetBitVectorBit(__CFBitVectorBucket *buckets, CFIndex idx, CFBit value) {
 124     CFIndex bucketIdx = idx / __CF_BITS_PER_BUCKET;
 125     CFIndex bitOfBucket = idx & (__CF_BITS_PER_BUCKET - 1);
 126     if (value) {
 127         buckets[bucketIdx] |= (1 << (__CF_BITS_PER_BUCKET - 1 - bitOfBucket));
 128     } else {
 129         buckets[bucketIdx] &= ~(1 << (__CF_BITS_PER_BUCKET - 1 - bitOfBucket));
 130     }
 131 }
 132
 133 CF_INLINE void __CFFlipBitVectorBit(__CFBitVectorBucket *buckets, CFIndex idx) {
 134     CFIndex bucketIdx = idx / __CF_BITS_PER_BUCKET;
 135     CFIndex bitOfBucket = idx & (__CF_BITS_PER_BUCKET - 1);
 136     buckets[bucketIdx] ^= (1 << (__CF_BITS_PER_BUCKET - 1 - bitOfBucket));
 137 }
 138
 139 #if defined(DEBUG)
 140 CF_INLINE void __CFBitVectorValidateRange(CFBitVectorRef bv, CFRange range, const char *func) {
 141     CFAssert2(0 <= range.location && range.location < __CFBitVectorCount(bv), __kCFLogAssertion, "%s(): range.location index (%d) out of bounds", func, range.location);
 142     CFAssert2(0 <= range.length, __kCFLogAssertion, "%s(): range.length (%d) cannot be less than zero", func, range.length);
 143     CFAssert2(range.location + range.length <= __CFBitVectorCount(bv), __kCFLogAssertion, "%s(): ending index (%d) out of bounds", func, range.location + range.length);
 144 }
 145 #else
 146 #define __CFBitVectorValidateRange(bf,r,f)
 147 #endif
 148
 149 static Boolean __CFBitVectorEqual(CFTypeRef cf1, CFTypeRef cf2) {
 150     CFBitVectorRef bv1 = (CFBitVectorRef)cf1;
 151     CFBitVectorRef bv2 = (CFBitVectorRef)cf2;
 152     CFIndex idx, cnt;
 153     cnt = __CFBitVectorCount(bv1);
 154     if (cnt != __CFBitVectorCount(bv2)) return false;
 155     if (0 == cnt) return true;
 156     for (idx = 0; idx < (cnt / __CF_BITS_PER_BUCKET) + 1; idx++) {
 157         __CFBitVectorBucket val1 = bv1->_buckets[idx];
 158         __CFBitVectorBucket val2 = bv2->_buckets[idx];
 159         if (val1 != val2) return false;
 160     }
 161     return true;
 162 }
 163
 164 static CFHashCode __CFBitVectorHash(CFTypeRef cf) {
 165     CFBitVectorRef bv = (CFBitVectorRef)cf;
 166     return __CFBitVectorCount(bv);
 167 }
 168
 169 static CFStringRef __CFBitVectorCopyDescription(CFTypeRef cf) {
 170     CFBitVectorRef bv = (CFBitVectorRef)cf;
 171     CFMutableStringRef result;
 172     CFIndex idx, cnt;
 173     __CFBitVectorBucket *buckets;
 174     cnt = __CFBitVectorCount(bv);
 175     buckets = bv->_buckets;
 176     result = CFStringCreateMutable(kCFAllocatorSystemDefault, 0);
 177     CFStringAppendFormat(result, NULL, CFSTR("<CFBitVector %p [%p]>{count = %u, capacity = %u, objects = (\n"), cf, CFGetAllocator(bv), cnt, __CFBitVectorCapacity(bv));
 178     for (idx = 0; idx < (cnt / 64); idx++) {    /* Print groups of 64 */
 179         CFIndex idx2;
 180         CFStringAppendFormat(result, NULL, CFSTR("\t%u : "), (idx * 64));
 181         for (idx2 = 0; idx2 < 64; idx2 += 4) {
 182             CFIndex bucketIdx = (idx << 6) + idx2;
 183             CFStringAppendFormat(result, NULL, CFSTR("%d%d%d%d"),
 184                 __CFBitVectorBit(buckets, bucketIdx + 0),
 185                 __CFBitVectorBit(buckets, bucketIdx + 1),
 186                 __CFBitVectorBit(buckets, bucketIdx + 2),
 187                 __CFBitVectorBit(buckets, bucketIdx + 3));
 188         }
 189         CFStringAppend(result, CFSTR("\n"));
 190     }
 191     if (idx * 64 < cnt) {
 192         CFStringAppendFormat(result, NULL, CFSTR("\t%u : "), (idx * 64));
 193         for (idx = (idx * 64); idx < cnt; idx++) {      /* Print remainder */
 194             CFStringAppendFormat(result, NULL, CFSTR("%d"), __CFBitVectorBit(buckets, idx));
 195         }
 196     }
 197     CFStringAppend(result, CFSTR("\n)}"));
 198     return result;
 199 }
 200
 201 enum {
 202     kCFBitVectorImmutable = 0x0,        /* unchangable and fixed capacity; default */
 203     kCFBitVectorMutable = 0x1,          /* changeable and variable capacity */
 204 };
 205
 206 static void __CFBitVectorDeallocate(CFTypeRef cf) {
 207     CFMutableBitVectorRef bv = (CFMutableBitVectorRef)cf;
 208     CFAllocatorRef allocator = CFGetAllocator(bv);
 209     if (bv->_buckets) _CFAllocatorDeallocateGC(allocator, bv->_buckets);
 210 }
 211
 212 static CFTypeID __kCFBitVectorTypeID = _kCFRuntimeNotATypeID;
 213
 214 static const CFRuntimeClass __CFBitVectorClass = {
 215     _kCFRuntimeScannedObject,
 216     "CFBitVector",
 217     NULL,       // init
 218     NULL,       // copy
 219     __CFBitVectorDeallocate,
 220     __CFBitVectorEqual,
 221     __CFBitVectorHash,
 222     NULL,       //
 223     __CFBitVectorCopyDescription
 224 };
 225
 226 __private_extern__ void __CFBitVectorInitialize(void) {
 227     __kCFBitVectorTypeID = _CFRuntimeRegisterClass(&__CFBitVectorClass);
 228 }
 229
 230 CFTypeID CFBitVectorGetTypeID(void) {
 231     return __kCFBitVectorTypeID;
 232 }
 233
 234 static CFMutableBitVectorRef __CFBitVectorInit(CFAllocatorRef allocator, CFOptionFlags flags, CFIndex capacity, const uint8_t *bytes, CFIndex numBits) {
 235     CFMutableBitVectorRef memory;
 236     CFIndex size;
 237     CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
 238     CFAssert2(0 <= numBits, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numBits);
 239     size = sizeof(struct __CFBitVector) - sizeof(CFRuntimeBase);
 240     memory = (CFMutableBitVectorRef)_CFRuntimeCreateInstance(allocator, __kCFBitVectorTypeID, size, NULL);
 241     if (NULL == memory) {
 242         return NULL;
 243     }
 244     __CFBitVectorSetCapacity(memory, __CFBitVectorRoundUpCapacity(numBits));
 245     __CFBitVectorSetNumBuckets(memory, __CFBitVectorNumBucketsForCapacity(__CFBitVectorRoundUpCapacity(numBits)));
 246     __CFAssignWithWriteBarrier((void **)&memory->_buckets, _CFAllocatorAllocateGC(allocator, __CFBitVectorNumBuckets(memory) * sizeof(__CFBitVectorBucket), 0));
 247     if (__CFOASafe) __CFSetLastAllocationEventName(memory->_buckets, "CFBitVector (store)");
 248     if (NULL == memory->_buckets) {
 249         CFRelease(memory);
 250         return NULL;
 251     }
 252     memset(memory->_buckets, 0, __CFBitVectorNumBuckets(memory) * sizeof(__CFBitVectorBucket));
 253     __CFBitVectorSetNumBucketsUsed(memory, numBits / __CF_BITS_PER_BUCKET + 1);
 254     __CFBitVectorSetCount(memory, numBits);
 255     if (bytes) {
 256         /* This move is possible because bits are numbered from 0 on the left */
 257         memmove(memory->_buckets, bytes, numBits / __CF_BITS_PER_BYTE + (numBits & __CF_BITS_PER_BYTE_MASK ? 1 : 0));
 258     }
 259     __CFBitVectorSetMutableVariety(memory, __CFBitVectorMutableVarietyFromFlags(flags));
 260     return memory;
 261 }
 262
 263 CFBitVectorRef CFBitVectorCreate(CFAllocatorRef allocator, const uint8_t *bytes, CFIndex numBits) {
 264    return __CFBitVectorInit(allocator, kCFBitVectorImmutable, numBits, bytes, numBits);
 265 }
 266
 267 CFMutableBitVectorRef CFBitVectorCreateMutable(CFAllocatorRef allocator, CFIndex capacity) {
 268    return __CFBitVectorInit(allocator, kCFBitVectorMutable, capacity, NULL, 0);
 269 }
 270
 271 CFBitVectorRef CFBitVectorCreateCopy(CFAllocatorRef allocator, CFBitVectorRef bv) {
 272    __CFGenericValidateType(bv, __kCFBitVectorTypeID);
 273     return __CFBitVectorInit(allocator, kCFBitVectorImmutable, __CFBitVectorCount(bv), (const uint8_t *)bv->_buckets, __CFBitVectorCount(bv));
 274 }
 275
 276 CFMutableBitVectorRef CFBitVectorCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFBitVectorRef bv) {
 277    __CFGenericValidateType(bv, __kCFBitVectorTypeID);
 278     return __CFBitVectorInit(allocator, kCFBitVectorMutable, capacity, (const uint8_t *)bv->_buckets, __CFBitVectorCount(bv));
 279 }
 280
 281 CFIndex CFBitVectorGetCount(CFBitVectorRef bv) {
 282     __CFGenericValidateType(bv, __kCFBitVectorTypeID);
 283     return __CFBitVectorCount(bv);
 284 }
 285
 286 typedef __CFBitVectorBucket (*__CFInternalMapper)(__CFBitVectorBucket bucketValue, __CFBitVectorBucket bucketValueMask, void *context);
 287
 288 static void __CFBitVectorInternalMap(CFMutableBitVectorRef bv, CFRange range, __CFInternalMapper mapper, void *context) {
 289     CFIndex bucketIdx, bitOfBucket;
 290     CFIndex nBuckets;
 291     __CFBitVectorBucket bucketValMask, newBucketVal;
 292     if (0 == range.length) return;
 293     bucketIdx = range.location / __CF_BITS_PER_BUCKET;
 294     bitOfBucket = range.location & (__CF_BITS_PER_BUCKET - 1);
 295     /* Follow usual pattern of ramping up to a bit bucket boundary ...*/
 296     if (bitOfBucket + range.length < __CF_BITS_PER_BUCKET) {
 297         bucketValMask = __CFBitBucketMask(bitOfBucket, bitOfBucket + range.length - 1);
 298         range.length = 0;
 299     } else {
 300         bucketValMask = __CFBitBucketMask(bitOfBucket, __CF_BITS_PER_BUCKET - 1);
 301         range.length -= __CF_BITS_PER_BUCKET - bitOfBucket;
 302     }
 303     newBucketVal = mapper(bv->_buckets[bucketIdx], bucketValMask, context);
 304     bv->_buckets[bucketIdx] = (bv->_buckets[bucketIdx] & ~bucketValMask) | (newBucketVal & bucketValMask);
 305     bucketIdx++;
 306     /* ... clipping along with entire bit buckets ... */
 307     nBuckets = range.length / __CF_BITS_PER_BUCKET;
 308     range.length -= nBuckets * __CF_BITS_PER_BUCKET;
 309     while (nBuckets--) {
 310         newBucketVal = mapper(bv->_buckets[bucketIdx], ~0, context);
 311         bv->_buckets[bucketIdx] = newBucketVal;
 312         bucketIdx++;
 313     }
 314     /* ... and ramping down with the last fragmentary bit bucket. */
 315     if (0 != range.length) {
 316         bucketValMask = __CFBitBucketMask(0, range.length - 1);
 317         newBucketVal = mapper(bv->_buckets[bucketIdx], bucketValMask, context);
 318         bv->_buckets[bucketIdx] = (bv->_buckets[bucketIdx] & ~bucketValMask) | (newBucketVal & bucketValMask);
 319     }
 320 }
 321
 322 struct _occursContext {
 323     CFBit value;
 324     CFIndex count;
 325 };
 326
 327 static __CFBitVectorBucket __CFBitVectorCountBits(__CFBitVectorBucket bucketValue, __CFBitVectorBucket bucketValueMask, struct _occursContext *context) {
 328     static const __CFBitVectorBucket __CFNibbleBitCount[16] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
 329     __CFBitVectorBucket val;
 330     CFIndex idx;
 331     val = (context->value) ? (bucketValue & bucketValueMask) : (~bucketValue & bucketValueMask);
 332     for (idx = 0; idx < (CFIndex)sizeof(__CFBitVectorBucket) * 2; idx++) {
 333         context->count += __CFNibbleBitCount[val & 0xF];
 334         val = val >> 4;
 335     }
 336     return bucketValue;
 337 }
 338
 339 CFIndex CFBitVectorGetCountOfBit(CFBitVectorRef bv, CFRange range, CFBit value) {
 340     struct _occursContext context;
 341     __CFGenericValidateType(bv, __kCFBitVectorTypeID);
 342     __CFBitVectorValidateRange(bv, range, __PRETTY_FUNCTION__);
 343     if (0 == range.length) return 0;
 344     context.value = value;
 345     context.count = 0;
 346     __CFBitVectorInternalMap((CFMutableBitVectorRef)bv, range, (__CFInternalMapper)__CFBitVectorCountBits, &context);
 347     return context.count;
 348 }
 349
 350 Boolean CFBitVectorContainsBit(CFBitVectorRef bv, CFRange range, CFBit value) {
 351     __CFGenericValidateType(bv, __kCFBitVectorTypeID);
 352     __CFBitVectorValidateRange(bv, range, __PRETTY_FUNCTION__);
 353     return (CFBitVectorGetCountOfBit(bv, range, value) != 0) ? true : false;
 354 }
 355
 356 CFBit CFBitVectorGetBitAtIndex(CFBitVectorRef bv, CFIndex idx) {
 357     __CFGenericValidateType(bv, __kCFBitVectorTypeID);
 358     CFAssert2(0 <= idx && idx < __CFBitVectorCount(bv), __kCFLogAssertion, "%s(): index (%d) out of bounds", __PRETTY_FUNCTION__, idx);
 359     return __CFBitVectorBit(bv->_buckets, idx);
 360 }
 361
 362 struct _getBitsContext {
 363     uint8_t *curByte;
 364     CFIndex initBits;   /* Bits to extract off the front for the prev. byte */
 365     CFIndex totalBits;  /* This is for stopping at the end */
 366     bool ignoreFirstInitBits;
 367 };
 368
 369 static __CFBitVectorBucket __CFBitVectorGetBits(__CFBitVectorBucket bucketValue, __CFBitVectorBucket bucketValueMask, void *ctx) {
 370     struct _getBitsContext *context = (struct _getBitsContext *)ctx;
 371     __CFBitVectorBucket val;
 372     CFIndex nBits;
 373     val = bucketValue & bucketValueMask;
 374     nBits = __CFMin(__CF_BITS_PER_BUCKET - context->initBits, context->totalBits);
 375     /* First initBits bits go in *curByte ... */
 376     if (0 < context->initBits) {
 377         if (!context->ignoreFirstInitBits) {
 378             *context->curByte |= (uint8_t)(val >> (__CF_BITS_PER_BUCKET - context->initBits));
 379             context->curByte++;
 380             context->totalBits -= context->initBits;
 381             context->ignoreFirstInitBits = false;
 382         }
 383         val <<= context->initBits;
 384     }
 385     /* ... then next groups of __CF_BITS_PER_BYTE go in *curByte ... */
 386     while (__CF_BITS_PER_BYTE <= nBits) {
 387         *context->curByte = (uint8_t)(val >> (__CF_BITS_PER_BUCKET - __CF_BITS_PER_BYTE));
 388         context->curByte++;
 389         context->totalBits -= context->initBits;
 390         nBits -= __CF_BITS_PER_BYTE;
 391         val <<= __CF_BITS_PER_BYTE;
 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, __kCFBitVectorTypeID);
 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, __kCFBitVectorTypeID);
 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, __kCFBitVectorTypeID);
 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, __kCFBitVectorTypeID);
 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, __kCFBitVectorTypeID);
 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, __kCFBitVectorTypeID);
 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, __kCFBitVectorTypeID);
 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, __kCFBitVectorTypeID);
 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