CFSet.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
  24 /*      CFSet.c
  25         Copyright 1998-2008, Apple, Inc. All rights reserved.
  26         Responsibility: Christopher Kane
  27         Machine generated from Notes/HashingCode.template
  28 */
  29
  30
  31
  32
  33
  34 #include <CoreFoundation/CFSet.h>
  35 #include "CFInternal.h"
  36 #include "CFBasicHash.h"
  37 #include <CoreFoundation/CFString.h>
  38
  39 #define CFDictionary 0
  40 #define CFSet 0
  41 #define CFBag 0
  42 #undef CFSet
  43 #define CFSet 1
  44
  45 #if CFDictionary
  46 const CFSetKeyCallBacks kCFTypeSetKeyCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  47 const CFSetKeyCallBacks kCFCopyStringSetKeyCallBacks = {0, __CFStringCollectionCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  48 const CFSetValueCallBacks kCFTypeSetValueCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual};
  49 static const CFSetKeyCallBacks __kCFNullSetKeyCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
  50 static const CFSetValueCallBacks __kCFNullSetValueCallBacks = {0, NULL, NULL, NULL, NULL};
  51
  52 #define CFHashRef CFDictionaryRef
  53 #define CFMutableHashRef CFMutableDictionaryRef
  54 #define CFHashKeyCallBacks CFSetKeyCallBacks
  55 #define CFHashValueCallBacks CFSetValueCallBacks
  56 #endif
  57
  58 #if CFSet
  59 const CFSetCallBacks kCFTypeSetCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  60 const CFSetCallBacks kCFCopyStringSetCallBacks = {0, __CFStringCollectionCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  61 static const CFSetCallBacks __kCFNullSetCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
  62
  63 #define CFSetKeyCallBacks CFSetCallBacks
  64 #define CFSetValueCallBacks CFSetCallBacks
  65 #define kCFTypeSetKeyCallBacks kCFTypeSetCallBacks
  66 #define kCFTypeSetValueCallBacks kCFTypeSetCallBacks
  67 #define __kCFNullSetKeyCallBacks __kCFNullSetCallBacks
  68 #define __kCFNullSetValueCallBacks __kCFNullSetCallBacks
  69
  70 #define CFHashRef CFSetRef
  71 #define CFMutableHashRef CFMutableSetRef
  72 #define CFHashKeyCallBacks CFSetCallBacks
  73 #define CFHashValueCallBacks CFSetCallBacks
  74 #endif
  75
  76 #if CFBag
  77 const CFSetCallBacks kCFTypeSetCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  78 const CFSetCallBacks kCFCopyStringSetCallBacks = {0, __CFStringCollectionCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
  79 static const CFSetCallBacks __kCFNullSetCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
  80
  81 #define CFSetKeyCallBacks CFSetCallBacks
  82 #define CFSetValueCallBacks CFSetCallBacks
  83 #define kCFTypeSetKeyCallBacks kCFTypeSetCallBacks
  84 #define kCFTypeSetValueCallBacks kCFTypeSetCallBacks
  85 #define __kCFNullSetKeyCallBacks __kCFNullSetCallBacks
  86 #define __kCFNullSetValueCallBacks __kCFNullSetCallBacks
  87
  88 #define CFHashRef CFBagRef
  89 #define CFMutableHashRef CFMutableBagRef
  90 #define CFHashKeyCallBacks CFSetCallBacks
  91 #define CFHashValueCallBacks CFSetCallBacks
  92 #endif
  93
  94
  95 typedef uintptr_t any_t;
  96 typedef const void * const_any_pointer_t;
  97 typedef void * any_pointer_t;
  98
  99 static Boolean __CFSetEqual(CFTypeRef cf1, CFTypeRef cf2) {
 100     return __CFBasicHashEqual((CFBasicHashRef)cf1, (CFBasicHashRef)cf2);
 101 }
 102
 103 static CFHashCode __CFSetHash(CFTypeRef cf) {
 104     return __CFBasicHashHash((CFBasicHashRef)cf);
 105 }
 106
 107 static CFStringRef __CFSetCopyDescription(CFTypeRef cf) {
 108     return __CFBasicHashCopyDescription((CFBasicHashRef)cf);
 109 }
 110
 111 static void __CFSetDeallocate(CFTypeRef cf) {
 112     __CFBasicHashDeallocate((CFBasicHashRef)cf);
 113 }
 114
 115 static CFTypeID __kCFSetTypeID = _kCFRuntimeNotATypeID;
 116
 117 static const CFRuntimeClass __CFSetClass = {
 118     _kCFRuntimeScannedObject,
 119     "CFSet",
 120     NULL,        // init
 121     NULL,        // copy
 122     __CFSetDeallocate,
 123     __CFSetEqual,
 124     __CFSetHash,
 125     NULL,        //
 126     __CFSetCopyDescription
 127 };
 128
 129 CFTypeID CFSetGetTypeID(void) {
 130     if (_kCFRuntimeNotATypeID == __kCFSetTypeID) __kCFSetTypeID = _CFRuntimeRegisterClass(&__CFSetClass);
 131     return __kCFSetTypeID;
 132 }
 133
 134 static uintptr_t __CFSetCallback(CFBasicHashRef ht, uint8_t op, uintptr_t a1, uintptr_t a2, CFBasicHashCallbacks *cb) {
 135     switch (op) {
 136     case kCFBasicHashCallbackOpCopyCallbacks: {
 137         CFBasicHashCallbacks *newcb = NULL;
 138         if (CF_IS_COLLECTABLE_ALLOCATOR((CFAllocatorRef)a1)) {
 139             newcb = (CFBasicHashCallbacks *)auto_zone_allocate_object(auto_zone(), 10 * sizeof(void *), AUTO_MEMORY_UNSCANNED, true, false);
 140         } else {
 141             newcb = (CFBasicHashCallbacks *)CFAllocatorAllocate((CFAllocatorRef)a1, 10 * sizeof(void *), 0);
 142         }
 143         if (!newcb) HALT;
 144         memmove(newcb, (void *)cb, 10 * sizeof(void *));
 145         return (uintptr_t)newcb;
 146     }
 147     case kCFBasicHashCallbackOpFreeCallbacks: {
 148         if (CF_IS_COLLECTABLE_ALLOCATOR((CFAllocatorRef)a1)) {
 149             auto_zone_release(auto_zone(), cb);
 150         } else {
 151             CFAllocatorDeallocate((CFAllocatorRef)a1, cb);
 152         }
 153         return 0;
 154     }
 155     case kCFBasicHashCallbackOpRetainValue: {
 156         const_any_pointer_t (*value_retain)(CFAllocatorRef, const_any_pointer_t) = (const_any_pointer_t (*)(CFAllocatorRef, const_any_pointer_t))cb->context[0];
 157         if (NULL == value_retain) return a1;
 158         return (uintptr_t)INVOKE_CALLBACK2(value_retain, CFGetAllocator(ht), (const_any_pointer_t)a1);
 159     }
 160     case kCFBasicHashCallbackOpRetainKey: {
 161         const_any_pointer_t (*key_retain)(CFAllocatorRef, const_any_pointer_t) = (const_any_pointer_t (*)(CFAllocatorRef, const_any_pointer_t))cb->context[1];
 162         if (NULL == key_retain) return a1;
 163         return (uintptr_t)INVOKE_CALLBACK2(key_retain, CFGetAllocator(ht), (const_any_pointer_t)a1);
 164     }
 165     case kCFBasicHashCallbackOpReleaseValue: {
 166         void (*value_release)(CFAllocatorRef, const_any_pointer_t) = (void (*)(CFAllocatorRef, const_any_pointer_t))cb->context[2];
 167         if (NULL != value_release) INVOKE_CALLBACK2(value_release, CFGetAllocator(ht), (const_any_pointer_t)a1);
 168         return 0;
 169     }
 170     case kCFBasicHashCallbackOpReleaseKey: {
 171         void (*key_release)(CFAllocatorRef, const_any_pointer_t) = (void (*)(CFAllocatorRef, const_any_pointer_t))cb->context[3];
 172         if (NULL != key_release) INVOKE_CALLBACK2(key_release, CFGetAllocator(ht), (const_any_pointer_t)a1);
 173         return 0;
 174     }
 175     case kCFBasicHashCallbackOpValueEqual: {
 176         Boolean (*value_equal)(const_any_pointer_t, const_any_pointer_t) = (Boolean (*)(const_any_pointer_t, const_any_pointer_t))cb->context[4];
 177         if (NULL == value_equal) return (a1 == a2);
 178         return INVOKE_CALLBACK2(value_equal, (const_any_pointer_t)a1, (const_any_pointer_t)a2) ? 1 : 0;
 179     }
 180     case kCFBasicHashCallbackOpKeyEqual: {
 181         Boolean (*key_equal)(const_any_pointer_t, const_any_pointer_t) = (Boolean (*)(const_any_pointer_t, const_any_pointer_t))cb->context[5];
 182         if (NULL == key_equal) return (a1 == a2);
 183         return INVOKE_CALLBACK2(key_equal, (const_any_pointer_t)a1, (const_any_pointer_t)a2) ? 1 : 0;
 184     }
 185     case kCFBasicHashCallbackOpHashKey: {
 186         CFHashCode (*hash)(const_any_pointer_t) = (CFHashCode (*)(const_any_pointer_t))cb->context[6];
 187         if (NULL == hash) return a1;
 188         return (uintptr_t)INVOKE_CALLBACK1(hash, (const_any_pointer_t)a1);
 189     }
 190     case kCFBasicHashCallbackOpDescribeValue: {
 191         CFStringRef (*value_describe)(const_any_pointer_t) = (CFStringRef (*)(const_any_pointer_t))cb->context[7];
 192         if (NULL == value_describe) return (uintptr_t)CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<%p>"), (const_any_pointer_t)a1);
 193         return (uintptr_t)INVOKE_CALLBACK1(value_describe, (const_any_pointer_t)a1);
 194     }
 195     case kCFBasicHashCallbackOpDescribeKey: {
 196         CFStringRef (*key_describe)(const_any_pointer_t) = (CFStringRef (*)(const_any_pointer_t))cb->context[8];
 197         if (NULL == key_describe) return (uintptr_t)CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("<%p>"), (const_any_pointer_t)a1);
 198         return (uintptr_t)INVOKE_CALLBACK1(key_describe, (const_any_pointer_t)a1);
 199     }
 200     }
 201     return 0;
 202 }
 203
 204 static CFBasicHashRef __CFSetCreateGeneric(CFAllocatorRef allocator, const CFHashKeyCallBacks *keyCallBacks, const CFHashValueCallBacks *valueCallBacks, Boolean useValueCB) {
 205
 206     CFBasicHashCallbacks *cb = NULL;
 207     CFOptionFlags flags = kCFBasicHashLinearHashing; // kCFBasicHashExponentialHashing
 208     flags |= (CFDictionary ? kCFBasicHashHasKeys : 0) | (CFBag ? kCFBasicHashHasCounts : 0);
 209
 210     const_any_pointer_t (*key_retain)(CFAllocatorRef, const_any_pointer_t) = NULL;
 211     void (*key_release)(CFAllocatorRef, const_any_pointer_t) = NULL;
 212     const_any_pointer_t (*value_retain)(CFAllocatorRef, const_any_pointer_t) = NULL;
 213     void (*value_release)(CFAllocatorRef, const_any_pointer_t) = NULL;
 214     Boolean std_cb = false;
 215     if ((NULL == keyCallBacks || (keyCallBacks && 0 == memcmp(&__kCFNullSetKeyCallBacks, keyCallBacks, sizeof(__kCFNullSetKeyCallBacks))))
 216                 && (!useValueCB || (NULL == valueCallBacks || (valueCallBacks && 0 == memcmp(&__kCFNullSetValueCallBacks, valueCallBacks, sizeof(__kCFNullSetValueCallBacks)))))) {
 217         cb = (CFBasicHashCallbacks *)& CFBasicHashNullCallbacks;
 218     } else if ((&kCFTypeSetKeyCallBacks == keyCallBacks || (keyCallBacks && 0 == memcmp(&kCFTypeSetKeyCallBacks, keyCallBacks, sizeof(kCFTypeSetKeyCallBacks))))
 219                 && (!useValueCB || (&kCFTypeSetValueCallBacks == valueCallBacks || (valueCallBacks && 0 == memcmp(&kCFTypeSetValueCallBacks, valueCallBacks, sizeof(kCFTypeSetValueCallBacks)))))) {
 220         std_cb = true;
 221         cb = (CFBasicHashCallbacks *)& CFBasicHashStandardCallbacks;
 222     } else {
 223         Boolean (*key_equal)(const_any_pointer_t, const_any_pointer_t) = NULL;
 224         Boolean (*value_equal)(const_any_pointer_t, const_any_pointer_t) = NULL;
 225         CFStringRef (*key_describe)(const_any_pointer_t) = NULL;
 226         CFStringRef (*value_describe)(const_any_pointer_t) = NULL;
 227         CFHashCode (*hash_key)(const_any_pointer_t) = NULL;
 228         key_retain = keyCallBacks ? keyCallBacks->retain : NULL;
 229         key_release = keyCallBacks ? keyCallBacks->release : NULL;
 230         key_equal = keyCallBacks ? keyCallBacks->equal : NULL;
 231         key_describe = keyCallBacks ? keyCallBacks->copyDescription : NULL;
 232         if (useValueCB) {
 233             value_retain = valueCallBacks ? valueCallBacks->retain : NULL;
 234             value_release = valueCallBacks ? valueCallBacks->release : NULL;
 235             value_equal = valueCallBacks ? valueCallBacks->equal : NULL;
 236             value_describe = valueCallBacks ? valueCallBacks->copyDescription : NULL;
 237         } else {
 238             value_retain = key_retain;
 239             value_release = key_release;
 240             value_equal = key_equal;
 241             value_describe = key_describe;
 242         }
 243         hash_key = keyCallBacks ? keyCallBacks->hash : NULL;
 244         FAULT_CALLBACK((void **)&key_retain);
 245         FAULT_CALLBACK((void **)&key_release);
 246         FAULT_CALLBACK((void **)&value_retain);
 247         FAULT_CALLBACK((void **)&value_release);
 248         FAULT_CALLBACK((void **)&key_equal);
 249         FAULT_CALLBACK((void **)&value_equal);
 250         FAULT_CALLBACK((void **)&key_describe);
 251         FAULT_CALLBACK((void **)&value_describe);
 252         FAULT_CALLBACK((void **)&hash_key);
 253
 254         CFBasicHashCallbacks *newcb = NULL;
 255         if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 256             newcb = (CFBasicHashCallbacks *)auto_zone_allocate_object(auto_zone(), 10 * sizeof(void *), AUTO_MEMORY_UNSCANNED, true, false);
 257         } else {
 258             newcb = (CFBasicHashCallbacks *)CFAllocatorAllocate(allocator, 10 * sizeof(void *), 0);
 259         }
 260         if (!newcb) HALT;
 261         newcb->func = (CFBasicHashCallbackType)__CFSetCallback;
 262         newcb->context[0] = (uintptr_t)value_retain;
 263         newcb->context[1] = (uintptr_t)key_retain;
 264         newcb->context[2] = (uintptr_t)value_release;
 265         newcb->context[3] = (uintptr_t)key_release;
 266         newcb->context[4] = (uintptr_t)value_equal;
 267         newcb->context[5] = (uintptr_t)key_equal;
 268         newcb->context[6] = (uintptr_t)hash_key;
 269         newcb->context[7] = (uintptr_t)value_describe;
 270         newcb->context[8] = (uintptr_t)key_describe;
 271         cb = newcb;
 272     }
 273
 274     if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
 275         if (std_cb || value_retain != NULL || value_release != NULL) {
 276             flags |= kCFBasicHashStrongValues;
 277         }
 278         if (std_cb || key_retain != NULL || key_release != NULL) {
 279             flags |= kCFBasicHashStrongKeys;
 280         }
 281     }
 282
 283     return CFBasicHashCreate(allocator, flags, cb);
 284 }
 285
 286 #if CFDictionary
 287 CFHashRef CFSetCreate(CFAllocatorRef allocator, const_any_pointer_t *klist, const_any_pointer_t *vlist, CFIndex numValues, const CFSetKeyCallBacks *keyCallBacks, const CFSetValueCallBacks *valueCallBacks) {
 288 #endif
 289 #if CFSet || CFBag
 290 CFHashRef CFSetCreate(CFAllocatorRef allocator, const_any_pointer_t *klist, CFIndex numValues, const CFSetKeyCallBacks *keyCallBacks) {
 291     const_any_pointer_t *vlist = klist;
 292     const CFSetValueCallBacks *valueCallBacks = 0;
 293 #endif
 294     CFTypeID typeID = CFSetGetTypeID();
 295     CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%ld) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
 296     CFBasicHashRef ht = __CFSetCreateGeneric(allocator, keyCallBacks, valueCallBacks, CFDictionary);
 297     if (0 < numValues) CFBasicHashSetCapacity(ht, numValues);
 298     for (CFIndex idx = 0; idx < numValues; idx++) {
 299         CFBasicHashAddValue(ht, (uintptr_t)klist[idx], (uintptr_t)vlist[idx]);
 300     }
 301     CFBasicHashMakeImmutable(ht);
 302     *(uintptr_t *)ht = __CFISAForTypeID(typeID);
 303     _CFRuntimeSetInstanceTypeID(ht, typeID);
 304     if (__CFOASafe) __CFSetLastAllocationEventName(ht, "CFSet (immutable)");
 305     return (CFHashRef)ht;
 306 }
 307
 308 #if CFDictionary
 309 CFMutableHashRef CFSetCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFSetKeyCallBacks *keyCallBacks, const CFSetValueCallBacks *valueCallBacks) {
 310 #endif
 311 #if CFSet || CFBag
 312 CFMutableHashRef CFSetCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFSetKeyCallBacks *keyCallBacks) {
 313     const CFSetValueCallBacks *valueCallBacks = 0;
 314 #endif
 315     CFTypeID typeID = CFSetGetTypeID();
 316     CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%ld) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
 317     CFBasicHashRef ht = __CFSetCreateGeneric(allocator, keyCallBacks, valueCallBacks, CFDictionary);
 318     *(uintptr_t *)ht = __CFISAForTypeID(typeID);
 319     _CFRuntimeSetInstanceTypeID(ht, typeID);
 320     if (__CFOASafe) __CFSetLastAllocationEventName(ht, "CFSet (mutable)");
 321     return (CFMutableHashRef)ht;
 322 }
 323
 324 CFHashRef CFSetCreateCopy(CFAllocatorRef allocator, CFHashRef other) {
 325     CFTypeID typeID = CFSetGetTypeID();
 326     CFAssert1(other, __kCFLogAssertion, "%s(): other CFSet cannot be NULL", __PRETTY_FUNCTION__);
 327     __CFGenericValidateType(other, typeID);
 328     CFBasicHashRef ht = NULL;
 329     if (CF_IS_OBJC(typeID, other)) {
 330         CFIndex numValues = CFSetGetCount(other);
 331         const_any_pointer_t vbuffer[256], kbuffer[256];
 332         const_any_pointer_t *vlist = (numValues <= 256) ? vbuffer : (const_any_pointer_t *)CFAllocatorAllocate(kCFAllocatorSystemDefault, numValues * sizeof(const_any_pointer_t), 0);
 333 #if CFSet || CFBag
 334         const_any_pointer_t *klist = vlist;
 335         CFSetGetValues(other, vlist);
 336 #endif
 337 #if CFDictionary
 338         const_any_pointer_t *klist = (numValues <= 256) ? kbuffer : (const_any_pointer_t *)CFAllocatorAllocate(kCFAllocatorSystemDefault, numValues * sizeof(const_any_pointer_t), 0);
 339         CFDictionaryGetKeysAndValues(other, klist, vlist);
 340 #endif
 341         ht = __CFSetCreateGeneric(allocator, & kCFTypeSetKeyCallBacks, CFDictionary ? & kCFTypeSetValueCallBacks : NULL, CFDictionary);
 342         if (0 < numValues) CFBasicHashSetCapacity(ht, numValues);
 343         for (CFIndex idx = 0; idx < numValues; idx++) {
 344             CFBasicHashAddValue(ht, (uintptr_t)klist[idx], (uintptr_t)vlist[idx]);
 345         }
 346         if (klist != kbuffer && klist != vlist) CFAllocatorDeallocate(kCFAllocatorSystemDefault, klist);
 347         if (vlist != vbuffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, vlist);
 348     } else {
 349         ht = CFBasicHashCreateCopy(allocator, (CFBasicHashRef)other);
 350     }
 351     CFBasicHashMakeImmutable(ht);
 352     *(uintptr_t *)ht = __CFISAForTypeID(typeID);
 353     _CFRuntimeSetInstanceTypeID(ht, typeID);
 354     if (__CFOASafe) __CFSetLastAllocationEventName(ht, "CFSet (immutable)");
 355     return (CFHashRef)ht;
 356 }
 357
 358 CFMutableHashRef CFSetCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFHashRef other) {
 359     CFTypeID typeID = CFSetGetTypeID();
 360     CFAssert1(other, __kCFLogAssertion, "%s(): other CFSet cannot be NULL", __PRETTY_FUNCTION__);
 361     __CFGenericValidateType(other, typeID);
 362     CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%ld) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
 363     CFBasicHashRef ht = NULL;
 364     if (CF_IS_OBJC(typeID, other)) {
 365         CFIndex numValues = CFSetGetCount(other);
 366         const_any_pointer_t vbuffer[256], kbuffer[256];
 367         const_any_pointer_t *vlist = (numValues <= 256) ? vbuffer : (const_any_pointer_t *)CFAllocatorAllocate(kCFAllocatorSystemDefault, numValues * sizeof(const_any_pointer_t), 0);
 368 #if CFSet || CFBag
 369         const_any_pointer_t *klist = vlist;
 370         CFSetGetValues(other, vlist);
 371 #endif
 372 #if CFDictionary
 373         const_any_pointer_t *klist = (numValues <= 256) ? kbuffer : (const_any_pointer_t *)CFAllocatorAllocate(kCFAllocatorSystemDefault, numValues * sizeof(const_any_pointer_t), 0);
 374         CFDictionaryGetKeysAndValues(other, klist, vlist);
 375 #endif
 376         ht = __CFSetCreateGeneric(allocator, & kCFTypeSetKeyCallBacks, CFDictionary ? & kCFTypeSetValueCallBacks : NULL, CFDictionary);
 377         if (0 < numValues) CFBasicHashSetCapacity(ht, numValues);
 378         for (CFIndex idx = 0; idx < numValues; idx++) {
 379             CFBasicHashAddValue(ht, (uintptr_t)klist[idx], (uintptr_t)vlist[idx]);
 380         }
 381         if (klist != kbuffer && klist != vlist) CFAllocatorDeallocate(kCFAllocatorSystemDefault, klist);
 382         if (vlist != vbuffer) CFAllocatorDeallocate(kCFAllocatorSystemDefault, vlist);
 383     } else {
 384         ht = CFBasicHashCreateCopy(allocator, (CFBasicHashRef)other);
 385     }
 386     *(uintptr_t *)ht = __CFISAForTypeID(typeID);
 387     _CFRuntimeSetInstanceTypeID(ht, typeID);
 388     if (__CFOASafe) __CFSetLastAllocationEventName(ht, "CFSet (mutable)");
 389     return (CFMutableHashRef)ht;
 390 }
 391
 392 CFIndex CFSetGetCount(CFHashRef hc) {
 393     if (CFDictionary) CF_OBJC_FUNCDISPATCH0(__kCFSetTypeID, CFIndex, hc, "count");
 394     if (CFSet) CF_OBJC_FUNCDISPATCH0(__kCFSetTypeID, CFIndex, hc, "count");
 395     __CFGenericValidateType(hc, __kCFSetTypeID);
 396     return CFBasicHashGetCount((CFBasicHashRef)hc);
 397 }
 398
 399 #if CFDictionary
 400 CFIndex CFSetGetCountOfKey(CFHashRef hc, const_any_pointer_t key) {
 401 #endif
 402 #if CFSet || CFBag
 403 CFIndex CFSetGetCountOfValue(CFHashRef hc, const_any_pointer_t key) {
 404 #endif
 405     if (CFDictionary) CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, CFIndex, hc, "countForKey:", key);
 406     if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, CFIndex, hc, "countForObject:", key);
 407     __CFGenericValidateType(hc, __kCFSetTypeID);
 408     return CFBasicHashGetCountOfKey((CFBasicHashRef)hc, (uintptr_t)key);
 409 }
 410
 411 #if CFDictionary
 412 Boolean CFSetContainsKey(CFHashRef hc, const_any_pointer_t key) {
 413 #endif
 414 #if CFSet || CFBag
 415 Boolean CFSetContainsValue(CFHashRef hc, const_any_pointer_t key) {
 416 #endif
 417     if (CFDictionary) CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, char, hc, "containsKey:", key);
 418     if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, char, hc, "containsObject:", key);
 419     __CFGenericValidateType(hc, __kCFSetTypeID);
 420     return (0 < CFBasicHashGetCountOfKey((CFBasicHashRef)hc, (uintptr_t)key));
 421 }
 422
 423 const_any_pointer_t CFSetGetValue(CFHashRef hc, const_any_pointer_t key) {
 424     if (CFDictionary) CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, const_any_pointer_t, hc, "objectForKey:", key);
 425     if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, const_any_pointer_t, hc, "member:", key);
 426     __CFGenericValidateType(hc, __kCFSetTypeID);
 427     CFBasicHashBucket bkt = CFBasicHashFindBucket((CFBasicHashRef)hc, (uintptr_t)key);
 428     return (0 < bkt.count ? (const_any_pointer_t)bkt.weak_value : 0);
 429 }
 430
 431 Boolean CFSetGetValueIfPresent(CFHashRef hc, const_any_pointer_t key, const_any_pointer_t *value) {
 432     if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFSetTypeID, Boolean, hc, "_getValue:forKey:", (any_t *)value, key);
 433     if (CFSet) CF_OBJC_FUNCDISPATCH2(__kCFSetTypeID, Boolean, hc, "_getValue:forObj:", (any_t *)value, key);
 434     __CFGenericValidateType(hc, __kCFSetTypeID);
 435     CFBasicHashBucket bkt = CFBasicHashFindBucket((CFBasicHashRef)hc, (uintptr_t)key);
 436     if (0 < bkt.count) {
 437         if (value) {
 438             if (kCFUseCollectableAllocator && (CFBasicHashGetFlags((CFBasicHashRef)hc) & kCFBasicHashStrongValues)) {
 439                 __CFAssignWithWriteBarrier((void **)value, (void *)bkt.weak_value);
 440             } else {
 441                 *value = (const_any_pointer_t)bkt.weak_value;
 442             }
 443         }
 444         return true;
 445     }
 446     return false;
 447 }
 448
 449 #if CFDictionary
 450 CFIndex CFDictionaryGetCountOfValue(CFHashRef hc, const_any_pointer_t value) {
 451     CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, CFIndex, hc, "countForObject:", value);
 452     __CFGenericValidateType(hc, __kCFSetTypeID);
 453     return CFBasicHashGetCountOfValue((CFBasicHashRef)hc, (uintptr_t)value);
 454 }
 455
 456 Boolean CFDictionaryContainsValue(CFHashRef hc, const_any_pointer_t value) {
 457     CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, char, hc, "containsObject:", value);
 458     __CFGenericValidateType(hc, __kCFSetTypeID);
 459     return (0 < CFBasicHashGetCountOfValue((CFBasicHashRef)hc, (uintptr_t)value));
 460 }
 461
 462 CF_EXPORT Boolean CFDictionaryGetKeyIfPresent(CFHashRef hc, const_any_pointer_t key, const_any_pointer_t *actualkey) {
 463     CF_OBJC_FUNCDISPATCH2(__kCFSetTypeID, Boolean, hc, "getActualKey:forKey:", actualkey, key);
 464     __CFGenericValidateType(hc, __kCFSetTypeID);
 465     CFBasicHashBucket bkt = CFBasicHashFindBucket((CFBasicHashRef)hc, (uintptr_t)key);
 466     if (0 < bkt.count) {
 467         if (actualkey) {
 468             if (kCFUseCollectableAllocator && (CFBasicHashGetFlags((CFBasicHashRef)hc) & kCFBasicHashStrongKeys)) {
 469                 __CFAssignWithWriteBarrier((void **)actualkey, (void *)bkt.weak_key);
 470             } else {
 471                 *actualkey = (const_any_pointer_t)bkt.weak_key;
 472             }
 473         }
 474         return true;
 475     }
 476     return false;
 477 }
 478 #endif
 479
 480 #if CFDictionary
 481 void CFSetGetKeysAndValues(CFHashRef hc, const_any_pointer_t *keybuf, const_any_pointer_t *valuebuf) {
 482 #endif
 483 #if CFSet || CFBag
 484 void CFSetGetValues(CFHashRef hc, const_any_pointer_t *keybuf) {
 485     const_any_pointer_t *valuebuf = 0;
 486 #endif
 487     if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFSetTypeID, void, hc, "getObjects:andKeys:", (any_t *)valuebuf, (any_t *)keybuf);
 488     if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, hc, "getObjects:", (any_t *)keybuf);
 489     __CFGenericValidateType(hc, __kCFSetTypeID);
 490     if (kCFUseCollectableAllocator) {
 491         CFOptionFlags flags = CFBasicHashGetFlags((CFBasicHashRef)hc);
 492         __block const_any_pointer_t *keys = keybuf, *values = valuebuf;
 493         CFBasicHashApply((CFBasicHashRef)hc, ^(CFBasicHashBucket bkt) {
 494                 for (CFIndex cnt = bkt.count; cnt--;) {
 495                     if (keybuf && (flags & kCFBasicHashStrongKeys)) { __CFAssignWithWriteBarrier((void **)keys, (void *)bkt.weak_key); keys++; }
 496                     if (keybuf && !(flags & kCFBasicHashStrongKeys)) { *keys++ = (const_any_pointer_t)bkt.weak_key; }
 497                     if (valuebuf && (flags & kCFBasicHashStrongValues)) { __CFAssignWithWriteBarrier((void **)values, (void *)bkt.weak_value); values++; }
 498                     if (valuebuf && !(flags & kCFBasicHashStrongValues)) { *values++ = (const_any_pointer_t)bkt.weak_value; }
 499                 }
 500                 return (Boolean)true;
 501             });
 502     } else {
 503         CFBasicHashGetElements((CFBasicHashRef)hc, CFSetGetCount(hc), (uintptr_t *)valuebuf, NULL, (uintptr_t *)keybuf, NULL);
 504     }
 505 }
 506
 507 void CFSetApplyFunction(CFHashRef hc, CFSetApplierFunction applier, any_pointer_t context) {
 508     FAULT_CALLBACK((void **)&(applier));
 509     if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFSetTypeID, void, hc, "_apply:context:", applier, context);
 510     if (CFSet) CF_OBJC_FUNCDISPATCH2(__kCFSetTypeID, void, hc, "_applyValues:context:", applier, context);
 511     __CFGenericValidateType(hc, __kCFSetTypeID);
 512     CFBasicHashApply((CFBasicHashRef)hc, ^(CFBasicHashBucket bkt) {
 513 #if CFDictionary
 514             INVOKE_CALLBACK3(applier, (const_any_pointer_t)bkt.weak_key, (const_any_pointer_t)bkt.weak_value, context);
 515 #endif
 516 #if CFSet
 517             INVOKE_CALLBACK2(applier, (const_any_pointer_t)bkt.weak_value, context);
 518 #endif
 519 #if CFBag
 520             for (CFIndex cnt = bkt.count; cnt--;) {
 521                 INVOKE_CALLBACK2(applier, (const_any_pointer_t)bkt.weak_value, context);
 522             }
 523 #endif
 524             return (Boolean)true;
 525         });
 526 }
 527
 528 // This function is for Foundation's benefit; no one else should use it.
 529 CF_EXPORT unsigned long _CFSetFastEnumeration(CFHashRef hc, struct __objcFastEnumerationStateEquivalent *state, void *stackbuffer, unsigned long count) {
 530     if (CF_IS_OBJC(__kCFSetTypeID, hc)) return 0;
 531     __CFGenericValidateType(hc, __kCFSetTypeID);
 532     return __CFBasicHashFastEnumeration((CFBasicHashRef)hc, (struct __objcFastEnumerationStateEquivalent2 *)state, stackbuffer, count);
 533 }
 534
 535 // This function is for Foundation's benefit; no one else should use it.
 536 CF_EXPORT Boolean _CFSetIsMutable(CFHashRef hc) {
 537     if (CF_IS_OBJC(__kCFSetTypeID, hc)) return false;
 538     __CFGenericValidateType(hc, __kCFSetTypeID);
 539     return CFBasicHashIsMutable((CFBasicHashRef)hc);
 540 }
 541
 542 // This function is for Foundation's benefit; no one else should use it.
 543 CF_EXPORT void _CFSetSetCapacity(CFMutableHashRef hc, CFIndex cap) {
 544     if (CF_IS_OBJC(__kCFSetTypeID, hc)) return;
 545     __CFGenericValidateType(hc, __kCFSetTypeID);
 546     CFAssert2(CFBasicHashIsMutable((CFBasicHashRef)hc), __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
 547     CFAssert3(CFSetGetCount(hc) <= cap, __kCFLogAssertion, "%s(): desired capacity (%ld) is less than count (%ld)", __PRETTY_FUNCTION__, cap, CFSetGetCount(hc));
 548     CFBasicHashSetCapacity((CFBasicHashRef)hc, cap);
 549 }
 550
 551 CF_INLINE CFIndex __CFSetGetKVOBit(CFHashRef hc) {
 552     return __CFBitfieldGetValue(((CFRuntimeBase *)hc)->_cfinfo[CF_INFO_BITS], 0, 0);
 553 }
 554
 555 CF_INLINE void __CFSetSetKVOBit(CFHashRef hc, CFIndex bit) {
 556     __CFBitfieldSetValue(((CFRuntimeBase *)hc)->_cfinfo[CF_INFO_BITS], 0, 0, ((uintptr_t)bit & 0x1));
 557 }
 558
 559 // This function is for Foundation's benefit; no one else should use it.
 560 CF_EXPORT CFIndex _CFSetGetKVOBit(CFHashRef hc) {
 561     return __CFSetGetKVOBit(hc);
 562 }
 563
 564 // This function is for Foundation's benefit; no one else should use it.
 565 CF_EXPORT void _CFSetSetKVOBit(CFHashRef hc, CFIndex bit) {
 566     __CFSetSetKVOBit(hc, bit);
 567 }
 568
 569
 570 #if !defined(CF_OBJC_KVO_WILLCHANGE)
 571 #define CF_OBJC_KVO_WILLCHANGE(obj, key)
 572 #define CF_OBJC_KVO_DIDCHANGE(obj, key)
 573 #define CF_OBJC_KVO_WILLCHANGEALL(obj)
 574 #define CF_OBJC_KVO_DIDCHANGEALL(obj)
 575 #endif
 576
 577 #if CFDictionary
 578 void CFSetAddValue(CFMutableHashRef hc, const_any_pointer_t key, const_any_pointer_t value) {
 579 #endif
 580 #if CFSet || CFBag
 581 void CFSetAddValue(CFMutableHashRef hc, const_any_pointer_t key) {
 582     const_any_pointer_t value = key;
 583 #endif
 584     if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFSetTypeID, void, hc, "addObject:forKey:", value, key);
 585     if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, hc, "addObject:", key);
 586     __CFGenericValidateType(hc, __kCFSetTypeID);
 587     CFAssert2(CFBasicHashIsMutable((CFBasicHashRef)hc), __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
 588     if (!CFBasicHashIsMutable((CFBasicHashRef)hc)) {
 589         CFLog(3, CFSTR("%s(): immutable collection %p given to mutating function"), __PRETTY_FUNCTION__, hc);
 590     }
 591     CF_OBJC_KVO_WILLCHANGE(hc, key);
 592     CFBasicHashAddValue((CFBasicHashRef)hc, (uintptr_t)key, (uintptr_t)value);
 593     CF_OBJC_KVO_DIDCHANGE(hc, key);
 594 }
 595
 596 #if CFDictionary
 597 void CFSetReplaceValue(CFMutableHashRef hc, const_any_pointer_t key, const_any_pointer_t value) {
 598 #endif
 599 #if CFSet || CFBag
 600 void CFSetReplaceValue(CFMutableHashRef hc, const_any_pointer_t key) {
 601     const_any_pointer_t value = key;
 602 #endif
 603     if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFSetTypeID, void, hc, "replaceObject:forKey:", value, key);
 604     if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, hc, "replaceObject:", key);
 605     __CFGenericValidateType(hc, __kCFSetTypeID);
 606     CFAssert2(CFBasicHashIsMutable((CFBasicHashRef)hc), __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
 607     if (!CFBasicHashIsMutable((CFBasicHashRef)hc)) {
 608         CFLog(3, CFSTR("%s(): immutable collection %p given to mutating function"), __PRETTY_FUNCTION__, hc);
 609     }
 610     CF_OBJC_KVO_WILLCHANGE(hc, key);
 611     CFBasicHashReplaceValue((CFBasicHashRef)hc, (uintptr_t)key, (uintptr_t)value);
 612     CF_OBJC_KVO_DIDCHANGE(hc, key);
 613 }
 614
 615 #if CFDictionary
 616 void CFSetSetValue(CFMutableHashRef hc, const_any_pointer_t key, const_any_pointer_t value) {
 617 #endif
 618 #if CFSet || CFBag
 619 void CFSetSetValue(CFMutableHashRef hc, const_any_pointer_t key) {
 620     const_any_pointer_t value = key;
 621 #endif
 622     if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFSetTypeID, void, hc, "setObject:forKey:", value, key);
 623     if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, hc, "_setObject:", key);
 624     __CFGenericValidateType(hc, __kCFSetTypeID);
 625     CFAssert2(CFBasicHashIsMutable((CFBasicHashRef)hc), __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
 626     if (!CFBasicHashIsMutable((CFBasicHashRef)hc)) {
 627         CFLog(3, CFSTR("%s(): immutable collection %p given to mutating function"), __PRETTY_FUNCTION__, hc);
 628     }
 629     CF_OBJC_KVO_WILLCHANGE(hc, key);
 630 //#warning this for a dictionary used to not replace the key
 631     CFBasicHashSetValue((CFBasicHashRef)hc, (uintptr_t)key, (uintptr_t)value);
 632     CF_OBJC_KVO_DIDCHANGE(hc, key);
 633 }
 634
 635 void CFSetRemoveValue(CFMutableHashRef hc, const_any_pointer_t key) {
 636     if (CFDictionary) CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, hc, "removeObjectForKey:", key);
 637     if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, hc, "removeObject:", key);
 638     __CFGenericValidateType(hc, __kCFSetTypeID);
 639     CFAssert2(CFBasicHashIsMutable((CFBasicHashRef)hc), __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
 640     if (!CFBasicHashIsMutable((CFBasicHashRef)hc)) {
 641         CFLog(3, CFSTR("%s(): immutable collection %p given to mutating function"), __PRETTY_FUNCTION__, hc);
 642     }
 643     CF_OBJC_KVO_WILLCHANGE(hc, key);
 644     CFBasicHashRemoveValue((CFBasicHashRef)hc, (uintptr_t)key);
 645     CF_OBJC_KVO_DIDCHANGE(hc, key);
 646 }
 647
 648 void CFSetRemoveAllValues(CFMutableHashRef hc) {
 649     if (CFDictionary) CF_OBJC_FUNCDISPATCH0(__kCFSetTypeID, void, hc, "removeAllObjects");
 650     if (CFSet) CF_OBJC_FUNCDISPATCH0(__kCFSetTypeID, void, hc, "removeAllObjects");
 651     __CFGenericValidateType(hc, __kCFSetTypeID);
 652     CFAssert2(CFBasicHashIsMutable((CFBasicHashRef)hc), __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
 653     if (!CFBasicHashIsMutable((CFBasicHashRef)hc)) {
 654         CFLog(3, CFSTR("%s(): immutable collection %p given to mutating function"), __PRETTY_FUNCTION__, hc);
 655     }
 656     CF_OBJC_KVO_WILLCHANGEALL(hc);
 657     CFBasicHashRemoveAllValues((CFBasicHashRef)hc);
 658     CF_OBJC_KVO_DIDCHANGEALL(hc);
 659 }
 660
 661 #undef CF_OBJC_KVO_WILLCHANGE
 662 #undef CF_OBJC_KVO_DIDCHANGE
 663 #undef CF_OBJC_KVO_WILLCHANGEALL
 664 #undef CF_OBJC_KVO_DIDCHANGEALL
 665