CFBitVector.c

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