Collections.subproj/CFBitVector.c

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