Collections.subproj/CFSet.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 /*      CFSet.c
  26         Copyright 1998-2002, Apple, Inc. All rights reserved.
  27         Responsibility: Christopher Kane
  28 */
  29
  30 #include <CoreFoundation/CFSet.h>
  31 #include "CFInternal.h"
  32
  33 const CFSetCallBacks kCFTypeSetCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  34 const CFSetCallBacks kCFCopyStringSetCallBacks = {0, (void *)CFStringCreateCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  35 static const CFSetCallBacks __kCFNullSetCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
  36
  37
  38 static const uint32_t __CFSetCapacities[42] = {
  39     4, 8, 17, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349,
  40     15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498,
  41     3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324,
  42     228826127, 370248451, 599074578, 969323029, 1568397607, 2537720636U
  43 };
  44
  45 static const uint32_t __CFSetBuckets[42] = {    // primes
  46     5, 11, 23, 41, 67, 113, 199, 317, 521, 839, 1361, 2207, 3571, 5779, 9349, 15121,
  47     24473, 39607, 64081, 103681, 167759, 271429, 439199, 710641, 1149857, 1860503, 3010349,
  48     4870843, 7881193, 12752029, 20633237, 33385273, 54018521, 87403763, 141422317, 228826121,
  49     370248451, 599074561, 969323023, 1568397599, 2537720629U, 4106118251U
  50 };
  51
  52 CF_INLINE CFIndex __CFSetRoundUpCapacity(CFIndex capacity) {
  53     CFIndex idx;
  54     for (idx = 0; idx < 42 && __CFSetCapacities[idx] < (uint32_t)capacity; idx++);
  55     if (42 <= idx) HALT;
  56     return __CFSetCapacities[idx];
  57 }
  58
  59 CF_INLINE CFIndex __CFSetNumBucketsForCapacity(CFIndex capacity) {
  60     CFIndex idx;
  61     for (idx = 0; idx < 42 && __CFSetCapacities[idx] < (uint32_t)capacity; idx++);
  62     if (42 <= idx) HALT;
  63     return __CFSetBuckets[idx];
  64 }
  65
  66 enum {          /* Bits 1-0 */
  67     __kCFSetImmutable = 0,              /* unchangable and fixed capacity */
  68     __kCFSetMutable = 1,                /* changeable and variable capacity */
  69     __kCFSetFixedMutable = 3            /* changeable and fixed capacity */
  70 };
  71
  72 enum {          /* Bits 3-2 */
  73     __kCFSetHasNullCallBacks = 0,
  74     __kCFSetHasCFTypeCallBacks = 1,
  75     __kCFSetHasCustomCallBacks = 3      /* callbacks are at end of header */
  76 };
  77
  78 struct __CFSetBucket {
  79     const void *_key;
  80 };
  81
  82 struct __CFSet {
  83     CFRuntimeBase _base;
  84     CFIndex _count;             /* number of values */
  85     CFIndex _capacity;          /* maximum number of values */
  86     CFIndex _bucketsUsed;       /* number of slots used */
  87     CFIndex _bucketsNum;        /* number of slots */
  88     const void *_emptyMarker;
  89     const void *_deletedMarker;
  90     void *_context;             /* private */
  91     struct __CFSetBucket *_buckets;     /* can be NULL if not allocated yet */
  92 };
  93
  94 CF_INLINE bool __CFSetBucketIsEmpty(CFSetRef set, const struct __CFSetBucket *bucket) {
  95     return (set->_emptyMarker == bucket->_key);
  96 }
  97
  98 CF_INLINE bool __CFSetBucketIsDeleted(CFSetRef set, const struct __CFSetBucket *bucket) {
  99     return (set->_deletedMarker == bucket->_key);
 100 }
 101
 102 CF_INLINE bool __CFSetBucketIsOccupied(CFSetRef set, const struct __CFSetBucket *bucket) {
 103     return (set->_emptyMarker != bucket->_key && set->_deletedMarker != bucket->_key);
 104 }
 105
 106 /* Bits 1-0 of the base reserved bits are used for mutability variety */
 107 /* Bits 3-2 of the base reserved bits are used for callback indicator bits */
 108
 109 CF_INLINE CFIndex __CFSetGetType(CFSetRef set) {
 110     return __CFBitfieldGetValue(((const CFRuntimeBase *)set)->_info, 1, 0);
 111 }
 112
 113 CF_INLINE CFIndex __CFSetGetSizeOfType(CFIndex t) {
 114     CFIndex size = sizeof(struct __CFSet);
 115     if (__CFBitfieldGetValue(t, 3, 2) == __kCFSetHasCustomCallBacks) {
 116         size += sizeof(CFSetCallBacks);
 117     }
 118     return size;
 119 }
 120
 121 CF_INLINE const CFSetCallBacks *__CFSetGetCallBacks(CFSetRef set) {
 122     CFSetCallBacks *result = NULL;
 123     switch (__CFBitfieldGetValue(((const CFRuntimeBase *)set)->_info, 3, 2)) {
 124     case __kCFSetHasNullCallBacks:
 125         return &__kCFNullSetCallBacks;
 126     case __kCFSetHasCFTypeCallBacks:
 127         return &kCFTypeSetCallBacks;
 128     case __kCFSetHasCustomCallBacks:
 129         break;
 130     }
 131     result = (CFSetCallBacks *)((uint8_t *)set + sizeof(struct __CFSet));
 132     return result;
 133 }
 134
 135 CF_INLINE bool __CFSetCallBacksMatchNull(const CFSetCallBacks *c) {
 136     return (NULL == c ||
 137         (c->retain == __kCFNullSetCallBacks.retain &&
 138          c->release == __kCFNullSetCallBacks.release &&
 139          c->copyDescription == __kCFNullSetCallBacks.copyDescription &&
 140          c->equal == __kCFNullSetCallBacks.equal &&
 141          c->hash == __kCFNullSetCallBacks.hash));
 142 }
 143
 144 CF_INLINE bool __CFSetCallBacksMatchCFType(const CFSetCallBacks *c) {
 145     return (&kCFTypeSetCallBacks == c ||
 146         (c->retain == kCFTypeSetCallBacks.retain &&
 147          c->release == kCFTypeSetCallBacks.release &&
 148          c->copyDescription == kCFTypeSetCallBacks.copyDescription &&
 149          c->equal == kCFTypeSetCallBacks.equal &&
 150          c->hash == kCFTypeSetCallBacks.hash));
 151 }
 152
 153
 154 static void __CFSetFindBuckets1(CFSetRef set, const void *key, struct __CFSetBucket **match) {
 155     const CFSetCallBacks *cb = __CFSetGetCallBacks(set);
 156     struct __CFSetBucket *buckets = set->_buckets;
 157     CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, set->_context) : (CFHashCode)key;
 158     UInt32 start = keyHash % set->_bucketsNum;
 159     UInt32 probe = start;
 160     UInt32 probeskip = 1;
 161     *match = NULL;
 162     for (;;) {
 163         struct __CFSetBucket *currentBucket = buckets + probe;
 164         if (__CFSetBucketIsEmpty(set, currentBucket)) {
 165             return;
 166         } else if (__CFSetBucketIsDeleted(set, currentBucket)) {
 167             /* do nothing */
 168         } else if (currentBucket->_key == key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(void *, void *, void*))cb->equal, currentBucket->_key, key, set->_context))) {
 169             *match = currentBucket;
 170             return;
 171         }
 172         probe = (probe + probeskip) % set->_bucketsNum;
 173         if (start == probe) return;
 174     }
 175 }
 176
 177 static void __CFSetFindBuckets2(CFSetRef set, const void *key, struct __CFSetBucket **match, struct __CFSetBucket **nomatch) {
 178     const CFSetCallBacks *cb = __CFSetGetCallBacks(set);
 179     struct __CFSetBucket *buckets = set->_buckets;
 180     CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, set->_context) : (CFHashCode)key;
 181     UInt32 start = keyHash % set->_bucketsNum;
 182     UInt32 probe = start;
 183     UInt32 probeskip = 1;
 184     *match = NULL;
 185     *nomatch = NULL;
 186     for (;;) {
 187         struct __CFSetBucket *currentBucket = buckets + probe;
 188         if (__CFSetBucketIsEmpty(set, currentBucket)) {
 189             if (!*nomatch) *nomatch = currentBucket;
 190             return;
 191         } else if (__CFSetBucketIsDeleted(set, currentBucket)) {
 192             if (!*nomatch) *nomatch = currentBucket;
 193         } else if (!*match && (currentBucket->_key == key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(void *, void *, void*))cb->equal, currentBucket->_key, key, set->_context)))) {
 194             *match = currentBucket;
 195             if (*nomatch) return;
 196         }
 197         probe = (probe + probeskip) % set->_bucketsNum;
 198         if (start == probe) return;
 199     }
 200 }
 201
 202 static void __CFSetFindNewEmptyMarker(CFSetRef set) {
 203     struct __CFSetBucket *buckets;
 204     const void *newEmpty;
 205     bool hit;
 206     CFIndex idx, nbuckets;
 207     buckets = set->_buckets;
 208     nbuckets = set->_bucketsNum;
 209     newEmpty = set->_emptyMarker;
 210     do {
 211         (intptr_t)newEmpty -= 2;
 212         hit = false;
 213         for (idx = 0; idx < nbuckets; idx++) {
 214             if (newEmpty == buckets[idx]._key) {
 215                 hit = true;
 216                 break;
 217             }
 218         }
 219     } while (hit);
 220     for (idx = 0; idx < nbuckets; idx++) {
 221         if (set->_emptyMarker == buckets[idx]._key) {
 222             buckets[idx]._key = newEmpty;
 223         }
 224     }
 225     ((struct __CFSet *)set)->_emptyMarker = newEmpty;
 226 }
 227
 228 static void __CFSetFindNewDeletedMarker(CFSetRef set) {
 229     struct __CFSetBucket *buckets;
 230     const void *newDeleted;
 231     bool hit;
 232     CFIndex idx, nbuckets;
 233     buckets = set->_buckets;
 234     nbuckets = set->_bucketsNum;
 235     newDeleted = set->_deletedMarker;
 236     do {
 237         (intptr_t)newDeleted += 2;
 238         hit = false;
 239         for (idx = 0; idx < nbuckets; idx++) {
 240             if (newDeleted == buckets[idx]._key) {
 241                 hit = true;
 242                 break;
 243             }
 244         }
 245     } while (hit);
 246     for (idx = 0; idx < nbuckets; idx++) {
 247         if (set->_deletedMarker == buckets[idx]._key) {
 248             buckets[idx]._key = newDeleted;
 249         }
 250     }
 251     ((struct __CFSet *)set)->_deletedMarker = newDeleted;
 252 }
 253
 254 static bool __CFSetEqual(CFTypeRef cf1, CFTypeRef cf2) {
 255     CFSetRef set1 = (CFSetRef)cf1;
 256     CFSetRef set2 = (CFSetRef)cf2;
 257     const CFSetCallBacks *cb1, *cb2;
 258     const struct __CFSetBucket *buckets;
 259     CFIndex idx, nbuckets;
 260     if (set1 == set2) return true;
 261     if (set1->_count != set2->_count) return false;
 262     cb1 = __CFSetGetCallBacks(set1);
 263     cb2 = __CFSetGetCallBacks(set2);
 264     if (cb1->equal != cb2->equal) return false;
 265     if (0 == set1->_count) return true; /* after function comparison! */
 266     buckets = set1->_buckets;
 267     nbuckets = set1->_bucketsNum;
 268     for (idx = 0; idx < nbuckets; idx++) {
 269         if (__CFSetBucketIsOccupied(set1, &buckets[idx])) {
 270             if (1 != CFSetGetCountOfValue(set2, buckets[idx]._key)) {
 271                 return false;
 272             }
 273         }
 274     }
 275     return true;
 276 }
 277
 278 static CFHashCode __CFSetHash(CFTypeRef cf) {
 279     CFSetRef set = (CFSetRef)cf;
 280     return set->_count;
 281 }
 282
 283 static CFStringRef __CFSetCopyDescription(CFTypeRef cf) {
 284     CFSetRef set = (CFSetRef)cf;
 285     const CFSetCallBacks *cb;
 286     const struct __CFSetBucket *buckets;
 287     CFIndex idx, nbuckets;
 288     CFMutableStringRef result;
 289     cb = __CFSetGetCallBacks(set);
 290     buckets = set->_buckets;
 291     nbuckets = set->_bucketsNum;
 292     result = CFStringCreateMutable(kCFAllocatorSystemDefault, 0);
 293     CFStringAppendFormat(result, NULL, CFSTR("<CFSet %p [%p]>{count = %u, capacity = %u, values = (\n"), set, CFGetAllocator(set), set->_count, set->_capacity);
 294     for (idx = 0; idx < nbuckets; idx++) {
 295         if (__CFSetBucketIsOccupied(set, &buckets[idx])) {
 296             CFStringRef desc = NULL;
 297             if (NULL != cb->copyDescription) {
 298                 desc = (CFStringRef)INVOKE_CALLBACK2(((CFStringRef (*)(const void *, void *))cb->copyDescription), buckets[idx]._key, set->_context);
 299             }
 300             if (NULL != desc) {
 301                 CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@\n"), idx, desc, NULL);
 302                 CFRelease(desc);
 303             } else {
 304                 CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p>\n"), idx, buckets[idx]._key, NULL);
 305             }
 306         }
 307     }
 308     CFStringAppend(result, CFSTR(")}"));
 309     return result;
 310 }
 311
 312 static void __CFSetDeallocate(CFTypeRef cf) {
 313     CFMutableSetRef set = (CFMutableSetRef)cf;
 314     CFAllocatorRef allocator = __CFGetAllocator(set);
 315     if (__CFSetGetType(set) == __kCFSetImmutable) {
 316         __CFBitfieldSetValue(((CFRuntimeBase *)set)->_info, 1, 0, __kCFSetFixedMutable);
 317     }
 318     CFSetRemoveAllValues(set);
 319     if (__CFSetGetType(set) == __kCFSetMutable && set->_buckets) {
 320         CFAllocatorDeallocate(allocator, set->_buckets);
 321     }
 322 }
 323
 324 static CFTypeID __kCFSetTypeID = _kCFRuntimeNotATypeID;
 325
 326 static const CFRuntimeClass __CFSetClass = {
 327     0,
 328     "CFSet",
 329     NULL,       // init
 330     NULL,       // copy
 331     __CFSetDeallocate,
 332     (void *)__CFSetEqual,
 333     __CFSetHash,
 334     NULL,       //
 335     __CFSetCopyDescription
 336 };
 337
 338 __private_extern__ void __CFSetInitialize(void) {
 339     __kCFSetTypeID = _CFRuntimeRegisterClass(&__CFSetClass);
 340 }
 341
 342 CFTypeID CFSetGetTypeID(void) {
 343     return __kCFSetTypeID;
 344 }
 345
 346 static CFSetRef __CFSetInit(CFAllocatorRef allocator, UInt32 flags, CFIndex capacity, const CFSetCallBacks *callBacks) {
 347     struct __CFSet *memory;
 348     UInt32 size;
 349     CFIndex idx;
 350     __CFBitfieldSetValue(flags, 31, 2, 0);
 351     if (__CFSetCallBacksMatchNull(callBacks)) {
 352         __CFBitfieldSetValue(flags, 3, 2, __kCFSetHasNullCallBacks);
 353     } else if (__CFSetCallBacksMatchCFType(callBacks)) {
 354         __CFBitfieldSetValue(flags, 3, 2, __kCFSetHasCFTypeCallBacks);
 355     } else {
 356         __CFBitfieldSetValue(flags, 3, 2, __kCFSetHasCustomCallBacks);
 357     }
 358     size = __CFSetGetSizeOfType(flags) - sizeof(CFRuntimeBase);
 359     switch (__CFBitfieldGetValue(flags, 1, 0)) {
 360     case __kCFSetImmutable:
 361     case __kCFSetFixedMutable:
 362         size += __CFSetNumBucketsForCapacity(capacity) * sizeof(struct __CFSetBucket);
 363         break;
 364     case __kCFSetMutable:
 365         break;
 366     }
 367     memory = (struct __CFSet *)_CFRuntimeCreateInstance(allocator, __kCFSetTypeID, size, NULL);
 368     if (NULL == memory) {
 369         return NULL;
 370     }
 371     __CFBitfieldSetValue(memory->_base._info, 6, 0, flags);
 372     memory->_count = 0;
 373     memory->_bucketsUsed = 0;
 374     memory->_emptyMarker = (const void *)0xa1b1c1d3;
 375     memory->_deletedMarker = (const void *)0xa1b1c1d5;
 376     memory->_context = NULL;
 377     switch (__CFBitfieldGetValue(flags, 1, 0)) {
 378     case __kCFSetImmutable:
 379         if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFSet (immutable)");
 380         memory->_capacity = capacity;   /* Don't round up capacity */
 381         memory->_bucketsNum = __CFSetNumBucketsForCapacity(memory->_capacity);
 382         memory->_buckets = (struct __CFSetBucket *)((uint8_t *)memory + __CFSetGetSizeOfType(flags));
 383         for (idx = memory->_bucketsNum; idx--;) {
 384             memory->_buckets[idx]._key = memory->_emptyMarker;
 385         }
 386         break;
 387     case __kCFSetFixedMutable:
 388         if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFSet (mutable-fixed)");
 389         memory->_capacity = capacity;   /* Don't round up capacity */
 390         memory->_bucketsNum = __CFSetNumBucketsForCapacity(memory->_capacity);
 391         memory->_buckets = (struct __CFSetBucket *)((uint8_t *)memory + __CFSetGetSizeOfType(flags));
 392         for (idx = memory->_bucketsNum; idx--;) {
 393             memory->_buckets[idx]._key = memory->_emptyMarker;
 394         }
 395         break;
 396     case __kCFSetMutable:
 397         if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFSet (mutable-variable)");
 398         memory->_capacity = __CFSetRoundUpCapacity(1);
 399         memory->_bucketsNum = 0;
 400         memory->_buckets = NULL;
 401         break;
 402     }
 403     if (__kCFSetHasCustomCallBacks == __CFBitfieldGetValue(flags, 3, 2)) {
 404         const CFSetCallBacks *cb = __CFSetGetCallBacks((CFSetRef)memory);
 405         *(CFSetCallBacks *)cb = *callBacks;
 406         FAULT_CALLBACK((void **)&(cb->retain));
 407         FAULT_CALLBACK((void **)&(cb->release));
 408         FAULT_CALLBACK((void **)&(cb->copyDescription));
 409         FAULT_CALLBACK((void **)&(cb->equal));
 410         FAULT_CALLBACK((void **)&(cb->hash));
 411     }
 412     return (CFSetRef)memory;
 413 }
 414
 415 CFSetRef CFSetCreate(CFAllocatorRef allocator, const void **values, CFIndex numValues, const CFSetCallBacks *callBacks) {
 416     CFSetRef result;
 417     UInt32 flags;
 418     CFIndex idx;
 419     CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
 420     result = __CFSetInit(allocator, __kCFSetImmutable, numValues, callBacks);
 421     flags = __CFBitfieldGetValue(((const CFRuntimeBase *)result)->_info, 1, 0);
 422     if (flags == __kCFSetImmutable) {
 423         __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, __kCFSetFixedMutable);
 424     }
 425     for (idx = 0; idx < numValues; idx++) {
 426         CFSetAddValue((CFMutableSetRef)result, values[idx]);
 427     }
 428     __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, flags);
 429     return result;
 430 }
 431
 432 CFMutableSetRef CFSetCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFSetCallBacks *callBacks) {
 433     CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
 434     return (CFMutableSetRef)__CFSetInit(allocator, (0 == capacity) ? __kCFSetMutable : __kCFSetFixedMutable, capacity, callBacks);
 435 }
 436
 437 CFSetRef CFSetCreateCopy(CFAllocatorRef allocator, CFSetRef set) {
 438     CFSetRef result;
 439     const CFSetCallBacks *cb;
 440     CFIndex numValues = CFSetGetCount(set);
 441     const void **list, *buffer[256];
 442     list = (numValues <= 256) ? buffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0);
 443     if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFSet (temp)");
 444     CFSetGetValues(set, list);
 445     cb = CF_IS_OBJC(__kCFSetTypeID, set) ? &kCFTypeSetCallBacks : __CFSetGetCallBacks(set);
 446     result = CFSetCreate(allocator, list, numValues, cb);
 447     if (list != buffer) CFAllocatorDeallocate(allocator, list);
 448     return result;
 449 }
 450
 451 CFMutableSetRef CFSetCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFSetRef set) {
 452     CFMutableSetRef result;
 453     const CFSetCallBacks *cb;
 454     CFIndex idx, numValues = CFSetGetCount(set);
 455     const void **list, *buffer[256];
 456     CFAssert3(0 == capacity || numValues <= capacity, __kCFLogAssertion, "%s(): for fixed-mutable sets, capacity (%d) must be greater than or equal to initial number of values (%d)", __PRETTY_FUNCTION__, capacity, numValues);
 457     list = (numValues <= 256) ? buffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0);
 458     if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFSet (temp)");
 459     CFSetGetValues(set, list);
 460     cb = CF_IS_OBJC(__kCFSetTypeID, set) ? &kCFTypeSetCallBacks : __CFSetGetCallBacks(set);
 461     result = CFSetCreateMutable(allocator, capacity, cb);
 462     if (0 == capacity) _CFSetSetCapacity(result, numValues);
 463     for (idx = 0; idx < numValues; idx++) {
 464         CFSetAddValue(result, list[idx]);
 465     }
 466     if (list != buffer) CFAllocatorDeallocate(allocator, list);
 467     return result;
 468 }
 469
 470 void _CFSetSetContext(CFSetRef set, void *context) {
 471     ((struct __CFSet *)set)->_context = context;
 472 }
 473
 474 CFIndex CFSetGetCount(CFSetRef set) {
 475     CF_OBJC_FUNCDISPATCH0(__kCFSetTypeID, CFIndex, set, "count");
 476     __CFGenericValidateType(set, __kCFSetTypeID);
 477     return set->_count;
 478 }
 479
 480 CFIndex CFSetGetCountOfValue(CFSetRef set, const void *value) {
 481     struct __CFSetBucket *match;
 482     CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, CFIndex, set, "countForObject:", value);
 483     __CFGenericValidateType(set, __kCFSetTypeID);
 484     if (0 == set->_count) return 0;
 485     __CFSetFindBuckets1(set, value, &match);
 486     return (match ? 1 : 0);
 487 }
 488
 489 Boolean CFSetContainsValue(CFSetRef set, const void *value) {
 490     struct __CFSetBucket *match;
 491     CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, char, set, "containsObject:", value);
 492     __CFGenericValidateType(set, __kCFSetTypeID);
 493     if (0 == set->_count) return false;
 494     __CFSetFindBuckets1(set, value, &match);
 495     return (match ? true : false);
 496 }
 497
 498 const void *CFSetGetValue(CFSetRef set, const void *value) {
 499     struct __CFSetBucket *match;
 500     CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, const void *, set, "member:", value);
 501     __CFGenericValidateType(set, __kCFSetTypeID);
 502     if (0 == set->_count) return NULL;
 503     __CFSetFindBuckets1(set, value, &match);
 504     return (match ? match->_key : NULL);
 505 }
 506
 507 Boolean CFSetGetValueIfPresent(CFSetRef set, const void *candidate, const void **value) {
 508     struct __CFSetBucket *match;
 509     CF_OBJC_FUNCDISPATCH2(__kCFSetTypeID, char, set, "_getValue:forObj:", (void * *)value, candidate);
 510     __CFGenericValidateType(set, __kCFSetTypeID);
 511     if (0 == set->_count) return false;
 512     __CFSetFindBuckets1(set, candidate, &match);
 513     return (match ? ((value ? *value = match->_key : NULL), true) : false);
 514 }
 515
 516 void CFSetGetValues(CFSetRef set, const void **values) {
 517     struct __CFSetBucket *buckets;
 518     CFIndex idx, cnt, nbuckets;
 519     CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, set, "getObjects:", (void * *)values);
 520     __CFGenericValidateType(set, __kCFSetTypeID);
 521     buckets = set->_buckets;
 522     nbuckets = set->_bucketsNum;
 523     for (idx = 0; idx < nbuckets; idx++) {
 524         if (__CFSetBucketIsOccupied(set, &buckets[idx])) {
 525             for (cnt = 1; cnt--;) {
 526                 if (values) *values++ = buckets[idx]._key;
 527             }
 528         }
 529     }
 530 }
 531
 532 void CFSetApplyFunction(CFSetRef set, CFSetApplierFunction applier, void *context) {
 533     struct __CFSetBucket *buckets;
 534     CFIndex idx, cnt, nbuckets;
 535     FAULT_CALLBACK((void **)&(applier));
 536     CF_OBJC_FUNCDISPATCH2(__kCFSetTypeID, void, set, "_applyValues:context:", applier, context);
 537     __CFGenericValidateType(set, __kCFSetTypeID);
 538     buckets = set->_buckets;
 539     nbuckets = set->_bucketsNum;
 540     for (idx = 0; idx < nbuckets; idx++) {
 541         if (__CFSetBucketIsOccupied(set, &buckets[idx])) {
 542             for (cnt = 1; cnt--;) {
 543                 INVOKE_CALLBACK2(applier, buckets[idx]._key, context);
 544             }
 545         }
 546     }
 547 }
 548
 549 static void __CFSetGrow(CFMutableSetRef set, CFIndex numNewValues) {
 550     struct __CFSetBucket *oldbuckets = set->_buckets;
 551     CFIndex idx, oldnbuckets = set->_bucketsNum;
 552     CFIndex oldCount = set->_count;
 553     set->_capacity = __CFSetRoundUpCapacity(oldCount + numNewValues);
 554     set->_bucketsNum = __CFSetNumBucketsForCapacity(set->_capacity);
 555     set->_buckets = CFAllocatorAllocate(__CFGetAllocator(set), set->_bucketsNum * sizeof(struct __CFSetBucket), 0);
 556     if (NULL == set->_buckets) HALT;
 557     if (__CFOASafe) __CFSetLastAllocationEventName(set->_buckets, "CFSet (store)");
 558     for (idx = set->_bucketsNum; idx--;) {
 559         set->_buckets[idx]._key = set->_emptyMarker;
 560     }
 561     if (NULL == oldbuckets) return;
 562     for (idx = 0; idx < oldnbuckets; idx++) {
 563         if (__CFSetBucketIsOccupied(set, &oldbuckets[idx])) {
 564             struct __CFSetBucket *match, *nomatch;
 565             __CFSetFindBuckets2(set, oldbuckets[idx]._key, &match, &nomatch);
 566             CFAssert3(!match, __kCFLogAssertion, "%s(): two values (%p, %p) now hash to the same slot; mutable value changed while in table or hash value is not immutable", __PRETTY_FUNCTION__, oldbuckets[idx]._key, match->_key);
 567             nomatch->_key = oldbuckets[idx]._key;
 568         }
 569     }
 570     CFAssert1(set->_count == oldCount, __kCFLogAssertion, "%s(): set count differs after rehashing; error", __PRETTY_FUNCTION__);
 571     CFAllocatorDeallocate(__CFGetAllocator(set), oldbuckets);
 572 }
 573
 574 // This function is for Foundation's benefit; no one else should use it.
 575 void _CFSetSetCapacity(CFMutableSetRef set, CFIndex cap) {
 576     if (CF_IS_OBJC(__kCFSetTypeID, set)) return;
 577 #if defined(DEBUG)
 578     __CFGenericValidateType(set, __kCFSetTypeID);
 579     CFAssert1(__CFSetGetType(set) != __kCFSetImmutable && __CFSetGetType(set) != __kCFSetFixedMutable, __kCFLogAssertion, "%s(): set is immutable or fixed-mutable", __PRETTY_FUNCTION__);
 580     CFAssert3(set->_count <= cap, __kCFLogAssertion, "%s(): desired capacity (%d) is less than count (%d)", __PRETTY_FUNCTION__, cap, set->_count);
 581 #endif
 582     __CFSetGrow(set, cap - set->_count);
 583 }
 584
 585 // This function is for Foundation's benefit; no one else should use it.
 586 bool _CFSetIsMutable(CFSetRef set) {
 587     return (__CFSetGetType(set) != __kCFSetImmutable);
 588 }
 589
 590 void CFSetAddValue(CFMutableSetRef set, const void *value) {
 591     struct __CFSetBucket *match, *nomatch;
 592     const CFSetCallBacks *cb;
 593     const void *newValue;
 594     CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, set, "addObject:", value);
 595     __CFGenericValidateType(set, __kCFSetTypeID);
 596     switch (__CFSetGetType(set)) {
 597     case __kCFSetMutable:
 598         if (set->_bucketsUsed == set->_capacity || NULL == set->_buckets) {
 599             __CFSetGrow(set, 1);
 600         }
 601         break;
 602     case __kCFSetFixedMutable:
 603         CFAssert3(set->_count < set->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity set %p (capacity = %d)", __PRETTY_FUNCTION__, set, set->_capacity);
 604         break;
 605     default:
 606         CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
 607         break;
 608     }
 609     __CFSetFindBuckets2(set, value, &match, &nomatch);
 610     if (match) {
 611     } else {
 612         cb = __CFSetGetCallBacks(set);
 613         if (cb->retain) {
 614             newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), __CFGetAllocator(set), value, set->_context);
 615         } else {
 616             newValue = value;
 617         }
 618         if (set->_emptyMarker == newValue) {
 619             __CFSetFindNewEmptyMarker(set);
 620         }
 621         if (set->_deletedMarker == newValue) {
 622             __CFSetFindNewDeletedMarker(set);
 623         }
 624         nomatch->_key = newValue;
 625         set->_bucketsUsed++;
 626         set->_count++;
 627     }
 628 }
 629
 630 __private_extern__ const void *__CFSetAddValueAndReturn(CFMutableSetRef set, const void *value) {
 631     struct __CFSetBucket *match, *nomatch;
 632     const CFSetCallBacks *cb;
 633     const void *newValue;
 634 // #warning not toll-free bridged, but internal
 635     __CFGenericValidateType(set, __kCFSetTypeID);
 636     switch (__CFSetGetType(set)) {
 637     case __kCFSetMutable:
 638         if (set->_bucketsUsed == set->_capacity || NULL == set->_buckets) {
 639             __CFSetGrow(set, 1);
 640         }
 641         break;
 642     case __kCFSetFixedMutable:
 643         CFAssert3(set->_count < set->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity set %p (capacity = %d)", __PRETTY_FUNCTION__, set, set->_capacity);
 644         break;
 645     default:
 646         CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
 647         break;
 648     }
 649     __CFSetFindBuckets2(set, value, &match, &nomatch);
 650     if (match) {
 651         return match->_key;
 652     } else {
 653         cb = __CFSetGetCallBacks(set);
 654         if (cb->retain) {
 655             newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), __CFGetAllocator(set), value, set->_context);
 656         } else {
 657             newValue = value;
 658         }
 659         if (set->_emptyMarker == newValue) {
 660             __CFSetFindNewEmptyMarker(set);
 661         }
 662         if (set->_deletedMarker == newValue) {
 663             __CFSetFindNewDeletedMarker(set);
 664         }
 665         nomatch->_key = newValue;
 666         set->_bucketsUsed++;
 667         set->_count++;
 668         return newValue;
 669     }
 670 }
 671
 672 void CFSetReplaceValue(CFMutableSetRef set, const void *value) {
 673     struct __CFSetBucket *match;
 674     const CFSetCallBacks *cb;
 675     const void *newValue;
 676     CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, set, "_replaceObject:", value);
 677     __CFGenericValidateType(set, __kCFSetTypeID);
 678     switch (__CFSetGetType(set)) {
 679     case __kCFSetMutable:
 680     case __kCFSetFixedMutable:
 681         break;
 682     default:
 683         CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
 684         break;
 685     }
 686     if (0 == set->_count) return;
 687     __CFSetFindBuckets1(set, value, &match);
 688     if (!match) return;
 689     cb = __CFSetGetCallBacks(set);
 690     if (cb->retain) {
 691         newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), __CFGetAllocator(set), value, set->_context);
 692     } else {
 693         newValue = value;
 694     }
 695     if (cb->release) {
 696         INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), __CFGetAllocator(set), match->_key, set->_context);
 697         match->_key = set->_deletedMarker;
 698     }
 699     if (set->_emptyMarker == newValue) {
 700         __CFSetFindNewEmptyMarker(set);
 701     }
 702     if (set->_deletedMarker == newValue) {
 703         __CFSetFindNewDeletedMarker(set);
 704     }
 705     match->_key = newValue;
 706 }
 707
 708 void CFSetSetValue(CFMutableSetRef set, const void *value) {
 709     struct __CFSetBucket *match, *nomatch;
 710     const CFSetCallBacks *cb;
 711     const void *newValue;
 712     CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, set, "_setObject:", value);
 713     __CFGenericValidateType(set, __kCFSetTypeID);
 714     switch (__CFSetGetType(set)) {
 715     case __kCFSetMutable:
 716         if (set->_bucketsUsed == set->_capacity || NULL == set->_buckets) {
 717             __CFSetGrow(set, 1);
 718         }
 719         break;
 720     case __kCFSetFixedMutable:
 721         break;
 722     default:
 723         CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
 724         break;
 725     }
 726     __CFSetFindBuckets2(set, value, &match, &nomatch);
 727     cb = __CFSetGetCallBacks(set);
 728     if (cb->retain) {
 729         newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), __CFGetAllocator(set), value, set->_context);
 730     } else {
 731         newValue = value;
 732     }
 733     if (match) {
 734         if (cb->release) {
 735             INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), __CFGetAllocator(set), match->_key, set->_context);
 736             match->_key = set->_deletedMarker;
 737         }
 738         if (set->_emptyMarker == newValue) {
 739             __CFSetFindNewEmptyMarker(set);
 740         }
 741         if (set->_deletedMarker == newValue) {
 742             __CFSetFindNewDeletedMarker(set);
 743         }
 744         match->_key = newValue;
 745     } else {
 746         CFAssert3(__kCFSetFixedMutable != __CFSetGetType(set) || set->_count < set->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity set %p (capacity = %d)", __PRETTY_FUNCTION__, set, set->_capacity);
 747         if (set->_emptyMarker == newValue) {
 748             __CFSetFindNewEmptyMarker(set);
 749         }
 750         if (set->_deletedMarker == newValue) {
 751             __CFSetFindNewDeletedMarker(set);
 752         }
 753         nomatch->_key = newValue;
 754         set->_bucketsUsed++;
 755         set->_count++;
 756     }
 757 }
 758
 759 void CFSetRemoveValue(CFMutableSetRef set, const void *value) {
 760     struct __CFSetBucket *match;
 761     const CFSetCallBacks *cb;
 762     CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, set, "removeObject:", value);
 763     __CFGenericValidateType(set, __kCFSetTypeID);
 764     switch (__CFSetGetType(set)) {
 765     case __kCFSetMutable:
 766     case __kCFSetFixedMutable:
 767         break;
 768     default:
 769         CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
 770         break;
 771     }
 772     if (0 == set->_count) return;
 773     __CFSetFindBuckets1(set, value, &match);
 774     if (!match) return;
 775     set->_count--;
 776     if (1) {
 777         cb = __CFSetGetCallBacks(set);
 778         if (cb->release) {
 779             INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), __CFGetAllocator(set), match->_key, set->_context);
 780         }
 781         match->_key = set->_deletedMarker;
 782         set->_bucketsUsed--;
 783     }
 784 }
 785
 786 void CFSetRemoveAllValues(CFMutableSetRef set) {
 787     struct __CFSetBucket *buckets;
 788     const CFSetCallBacks *cb;
 789     CFAllocatorRef allocator;
 790     CFIndex idx, nbuckets;
 791     CF_OBJC_FUNCDISPATCH0(__kCFSetTypeID, void, set, "removeAllObjects");
 792     __CFGenericValidateType(set, __kCFSetTypeID);
 793     switch (__CFSetGetType(set)) {
 794     case __kCFSetMutable:
 795     case __kCFSetFixedMutable:
 796         break;
 797     default:
 798         CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
 799         break;
 800     }
 801     if (0 == set->_count) return;
 802     buckets = set->_buckets;
 803     nbuckets = set->_bucketsNum;
 804     cb = __CFSetGetCallBacks(set);
 805     allocator = __CFGetAllocator(set);
 806     for (idx = 0; idx < nbuckets; idx++) {
 807         if (__CFSetBucketIsOccupied(set, &buckets[idx])) {
 808             if (cb->release) {
 809                 INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), allocator, buckets[idx]._key, set->_context);
 810             }
 811             buckets[idx]._key = set->_emptyMarker;
 812         }
 813     }
 814     set->_bucketsUsed = 0;
 815     set->_count = 0;
 816 }
 817