CFSet.c

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