--- /dev/null
+/*
+ * Copyright (c) 2008 Apple Inc. All rights reserved.
+ *
+ * @APPLE_LICENSE_HEADER_START@
+ *
+ * This file contains Original Code and/or Modifications of Original Code
+ * as defined in and that are subject to the Apple Public Source License
+ * Version 2.0 (the 'License'). You may not use this file except in
+ * compliance with the License. Please obtain a copy of the License at
+ * http://www.opensource.apple.com/apsl/ and read it before using this
+ * file.
+ *
+ * The Original Code and all software distributed under the License are
+ * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
+ * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
+ * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
+ * Please see the License for the specific language governing rights and
+ * limitations under the License.
+ *
+ * @APPLE_LICENSE_HEADER_END@
+ */
+/* CFSet.c
+ Copyright 1998-2006, Apple, Inc. All rights reserved.
+ Responsibility: Christopher Kane
+ Machine generated from Notes/HashingCode.template
+*/
+
+
+
+
+#include <CoreFoundation/CFSet.h>
+#include "CFInternal.h"
+#include <mach-o/dyld.h>
+
+#define CFDictionary 0
+#define CFSet 0
+#define CFBag 0
+#undef CFSet
+#define CFSet 1
+
+#if CFDictionary
+const CFSetKeyCallBacks kCFTypeSetKeyCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
+const CFSetKeyCallBacks kCFCopyStringSetKeyCallBacks = {0, __CFStringCollectionCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
+const CFSetValueCallBacks kCFTypeSetValueCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual};
+static const CFSetKeyCallBacks __kCFNullSetKeyCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
+static const CFSetValueCallBacks __kCFNullSetValueCallBacks = {0, NULL, NULL, NULL, NULL};
+
+#define CFHashRef CFDictionaryRef
+#define CFMutableHashRef CFMutableDictionaryRef
+#define __kCFHashTypeID __kCFDictionaryTypeID
+#endif
+
+#if CFSet
+const CFSetCallBacks kCFTypeSetCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
+const CFSetCallBacks kCFCopyStringSetCallBacks = {0, __CFStringCollectionCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
+static const CFSetCallBacks __kCFNullSetCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
+
+#define CFSetKeyCallBacks CFSetCallBacks
+#define CFSetValueCallBacks CFSetCallBacks
+#define kCFTypeSetKeyCallBacks kCFTypeSetCallBacks
+#define kCFTypeSetValueCallBacks kCFTypeSetCallBacks
+#define __kCFNullSetKeyCallBacks __kCFNullSetCallBacks
+#define __kCFNullSetValueCallBacks __kCFNullSetCallBacks
+
+#define CFHashRef CFSetRef
+#define CFMutableHashRef CFMutableSetRef
+#define __kCFHashTypeID __kCFSetTypeID
+#endif
+
+#if CFBag
+const CFSetCallBacks kCFTypeSetCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
+const CFSetCallBacks kCFCopyStringSetCallBacks = {0, __CFStringCollectionCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
+static const CFSetCallBacks __kCFNullSetCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
+
+#define CFSetKeyCallBacks CFSetCallBacks
+#define CFSetValueCallBacks CFSetCallBacks
+#define kCFTypeSetKeyCallBacks kCFTypeSetCallBacks
+#define kCFTypeSetValueCallBacks kCFTypeSetCallBacks
+#define __kCFNullSetKeyCallBacks __kCFNullSetCallBacks
+#define __kCFNullSetValueCallBacks __kCFNullSetCallBacks
+
+#define CFHashRef CFBagRef
+#define CFMutableHashRef CFMutableBagRef
+#define __kCFHashTypeID __kCFBagTypeID
+#endif
+
+#define GETNEWKEY(newKey, oldKey) \
+ any_t (*kretain)(CFAllocatorRef, any_t, any_pointer_t) = \
+ !hasBeenFinalized(hc) \
+ ? (any_t (*)(CFAllocatorRef,any_t,any_pointer_t))__CFSetGetKeyCallBacks(hc)->retain \
+ : (any_t (*)(CFAllocatorRef,any_t,any_pointer_t))0; \
+ any_t newKey = kretain ? (any_t)INVOKE_CALLBACK3(kretain, allocator, (any_t)key, hc->_context) : (any_t)oldKey
+
+#define RELEASEKEY(oldKey) \
+ void (*krelease)(CFAllocatorRef, any_t, any_pointer_t) = \
+ !hasBeenFinalized(hc) \
+ ? (void (*)(CFAllocatorRef,any_t,any_pointer_t))__CFSetGetKeyCallBacks(hc)->release \
+ : (void (*)(CFAllocatorRef,any_t,any_pointer_t))0; \
+ if (krelease) INVOKE_CALLBACK3(krelease, allocator, oldKey, hc->_context)
+
+#if CFDictionary
+#define GETNEWVALUE(newValue) \
+ any_t (*vretain)(CFAllocatorRef, any_t, any_pointer_t) = \
+ !hasBeenFinalized(hc) \
+ ? (any_t (*)(CFAllocatorRef,any_t,any_pointer_t))__CFSetGetValueCallBacks(hc)->retain \
+ : (any_t (*)(CFAllocatorRef,any_t,any_pointer_t))0; \
+ any_t newValue = vretain ? (any_t)INVOKE_CALLBACK3(vretain, allocator, (any_t)value, hc->_context) : (any_t)value
+
+#define RELEASEVALUE(oldValue) \
+ void (*vrelease)(CFAllocatorRef, any_t, any_pointer_t) = \
+ !hasBeenFinalized(hc) \
+ ? (void (*)(CFAllocatorRef,any_t,any_pointer_t))__CFSetGetValueCallBacks(hc)->release \
+ : (void (*)(CFAllocatorRef,any_t,any_pointer_t))0; \
+ if (vrelease) INVOKE_CALLBACK3(vrelease, allocator, oldValue, hc->_context)
+
+#endif
+
+static void __CFSetHandleOutOfMemory(CFTypeRef obj, CFIndex numBytes) {
+ CFStringRef msg = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("Attempt to allocate %ld bytes for NS/CFSet failed"), numBytes);
+ CFBadErrorCallBack cb = _CFGetOutOfMemoryErrorCallBack();
+ if (NULL == cb || !cb(obj, CFSTR("NS/CFSet"), msg)) {
+ CFLog(kCFLogLevelCritical, CFSTR("%@"), msg);
+ HALT;
+ }
+ CFRelease(msg);
+}
+
+
+// Max load is 3/4 number of buckets
+CF_INLINE CFIndex __CFHashRoundUpCapacity(CFIndex capacity) {
+ return 3 * ((CFIndex)1 << (flsl((capacity - 1) / 3)));
+}
+
+// Returns next power of two higher than the capacity
+// threshold for the given input capacity.
+CF_INLINE CFIndex __CFHashNumBucketsForCapacity(CFIndex capacity) {
+ return 4 * ((CFIndex)1 << (flsl((capacity - 1) / 3)));
+}
+
+enum { /* Bits 1-0 */
+ __kCFHashImmutable = 0, /* unchangable and fixed capacity */
+ __kCFHashMutable = 1, /* changeable and variable capacity */
+};
+
+enum { /* Bits 5-4 (value), 3-2 (key) */
+ __kCFHashHasNullCallBacks = 0,
+ __kCFHashHasCFTypeCallBacks = 1,
+ __kCFHashHasCustomCallBacks = 3 /* callbacks are at end of header */
+};
+
+// Under GC, we fudge the key/value memory in two ways
+// First, if we had null callbacks or null for both retain/release, we use unscanned memory and get
+// standard 'dangling' references.
+// This means that if people were doing addValue:[xxx new] and never removing, well, that doesn't work
+//
+// Second, if we notice standard retain/release implementations we use scanned memory, and fudge the
+// standard callbacks to generally do nothing if the collection was allocated in GC memory. On special
+// CF objects, however, like those used for precious resources like video-card buffers, we do indeed
+// do CFRetain on input and CFRelease on output. The tricky case is GC finalization; we need to remember
+// that we did the CFReleases so that subsequent collection operations, like removal, don't double CFRelease.
+// (In fact we don't really use CFRetain/CFRelease but go directly to the collector)
+//
+
+enum {
+ __kCFHashFinalized = (1 << 7),
+ __kCFHashWeakKeys = (1 << 8),
+ __kCFHashWeakValues = (1 << 9)
+};
+
+typedef uintptr_t any_t;
+typedef const void * const_any_pointer_t;
+typedef void * any_pointer_t;
+
+struct __CFSet {
+ CFRuntimeBase _base;
+ CFIndex _count; /* number of values */
+ CFIndex _bucketsNum; /* number of buckets */
+ CFIndex _bucketsUsed; /* number of used buckets */
+ CFIndex _bucketsCap; /* maximum number of used buckets */
+ CFIndex _mutations;
+ CFIndex _deletes;
+ any_pointer_t _context; /* private */
+ CFOptionFlags _xflags;
+ any_t _marker;
+ any_t *_keys; /* can be NULL if not allocated yet */
+ any_t *_values; /* can be NULL if not allocated yet */
+};
+
+/* Bits 1-0 of the _xflags are used for mutability variety */
+/* Bits 3-2 of the _xflags are used for key callback indicator bits */
+/* Bits 5-4 of the _xflags are used for value callback indicator bits */
+/* Bit 6 of the _xflags is special KVO actions bit */
+/* Bits 7,8,9 are GC use */
+
+CF_INLINE bool hasBeenFinalized(CFTypeRef collection) {
+ return __CFBitfieldGetValue(((const struct __CFSet *)collection)->_xflags, 7, 7) != 0;
+}
+
+CF_INLINE void markFinalized(CFTypeRef collection) {
+ __CFBitfieldSetValue(((struct __CFSet *)collection)->_xflags, 7, 7, 1);
+}
+
+
+CF_INLINE CFIndex __CFHashGetType(CFHashRef hc) {
+ return __CFBitfieldGetValue(hc->_xflags, 1, 0);
+}
+
+CF_INLINE CFIndex __CFSetGetSizeOfType(CFIndex t) {
+ CFIndex size = sizeof(struct __CFSet);
+ if (__CFBitfieldGetValue(t, 3, 2) == __kCFHashHasCustomCallBacks) {
+ size += sizeof(CFSetKeyCallBacks);
+ }
+ if (__CFBitfieldGetValue(t, 5, 4) == __kCFHashHasCustomCallBacks) {
+ size += sizeof(CFSetValueCallBacks);
+ }
+ return size;
+}
+
+CF_INLINE const CFSetKeyCallBacks *__CFSetGetKeyCallBacks(CFHashRef hc) {
+ CFSetKeyCallBacks *result = NULL;
+ switch (__CFBitfieldGetValue(hc->_xflags, 3, 2)) {
+ case __kCFHashHasNullCallBacks:
+ return &__kCFNullSetKeyCallBacks;
+ case __kCFHashHasCFTypeCallBacks:
+ return &kCFTypeSetKeyCallBacks;
+ case __kCFHashHasCustomCallBacks:
+ break;
+ }
+ result = (CFSetKeyCallBacks *)((uint8_t *)hc + sizeof(struct __CFSet));
+ return result;
+}
+
+CF_INLINE Boolean __CFSetKeyCallBacksMatchNull(const CFSetKeyCallBacks *c) {
+ return (NULL == c ||
+ (c->retain == __kCFNullSetKeyCallBacks.retain &&
+ c->release == __kCFNullSetKeyCallBacks.release &&
+ c->copyDescription == __kCFNullSetKeyCallBacks.copyDescription &&
+ c->equal == __kCFNullSetKeyCallBacks.equal &&
+ c->hash == __kCFNullSetKeyCallBacks.hash));
+}
+
+CF_INLINE Boolean __CFSetKeyCallBacksMatchCFType(const CFSetKeyCallBacks *c) {
+ return (&kCFTypeSetKeyCallBacks == c ||
+ (c->retain == kCFTypeSetKeyCallBacks.retain &&
+ c->release == kCFTypeSetKeyCallBacks.release &&
+ c->copyDescription == kCFTypeSetKeyCallBacks.copyDescription &&
+ c->equal == kCFTypeSetKeyCallBacks.equal &&
+ c->hash == kCFTypeSetKeyCallBacks.hash));
+}
+
+CF_INLINE const CFSetValueCallBacks *__CFSetGetValueCallBacks(CFHashRef hc) {
+ CFSetValueCallBacks *result = NULL;
+ switch (__CFBitfieldGetValue(hc->_xflags, 5, 4)) {
+ case __kCFHashHasNullCallBacks:
+ return &__kCFNullSetValueCallBacks;
+ case __kCFHashHasCFTypeCallBacks:
+ return &kCFTypeSetValueCallBacks;
+ case __kCFHashHasCustomCallBacks:
+ break;
+ }
+ if (__CFBitfieldGetValue(hc->_xflags, 3, 2) == __kCFHashHasCustomCallBacks) {
+ result = (CFSetValueCallBacks *)((uint8_t *)hc + sizeof(struct __CFSet) + sizeof(CFSetKeyCallBacks));
+ } else {
+ result = (CFSetValueCallBacks *)((uint8_t *)hc + sizeof(struct __CFSet));
+ }
+ return result;
+}
+
+CF_INLINE Boolean __CFSetValueCallBacksMatchNull(const CFSetValueCallBacks *c) {
+ return (NULL == c ||
+ (c->retain == __kCFNullSetValueCallBacks.retain &&
+ c->release == __kCFNullSetValueCallBacks.release &&
+ c->copyDescription == __kCFNullSetValueCallBacks.copyDescription &&
+ c->equal == __kCFNullSetValueCallBacks.equal));
+}
+
+CF_INLINE Boolean __CFSetValueCallBacksMatchCFType(const CFSetValueCallBacks *c) {
+ return (&kCFTypeSetValueCallBacks == c ||
+ (c->retain == kCFTypeSetValueCallBacks.retain &&
+ c->release == kCFTypeSetValueCallBacks.release &&
+ c->copyDescription == kCFTypeSetValueCallBacks.copyDescription &&
+ c->equal == kCFTypeSetValueCallBacks.equal));
+}
+
+CFIndex _CFSetGetKVOBit(CFHashRef hc) {
+ return __CFBitfieldGetValue(hc->_xflags, 6, 6);
+}
+
+void _CFSetSetKVOBit(CFHashRef hc, CFIndex bit) {
+ __CFBitfieldSetValue(((CFMutableHashRef)hc)->_xflags, 6, 6, ((uintptr_t)bit & 0x1));
+}
+
+CF_INLINE Boolean __CFSetShouldShrink(CFHashRef hc) {
+ return (__kCFHashMutable == __CFHashGetType(hc)) &&
+ !(CF_USING_COLLECTABLE_MEMORY && auto_zone_is_finalized(__CFCollectableZone, hc)) && /* GC: don't shrink finalizing hcs! */
+ (hc->_bucketsNum < 4 * hc->_deletes || (256 <= hc->_bucketsCap && hc-> _bucketsUsed < 3 * hc->_bucketsCap / 16));
+}
+
+CF_INLINE CFIndex __CFHashGetOccurrenceCount(CFHashRef hc, CFIndex idx) {
+#if CFBag
+ return hc->_values[idx];
+#endif
+ return 1;
+}
+
+CF_INLINE Boolean __CFHashKeyIsValue(CFHashRef hc, any_t key) {
+ return (hc->_marker != key && ~hc->_marker != key) ? true : false;
+}
+
+CF_INLINE Boolean __CFHashKeyIsMagic(CFHashRef hc, any_t key) {
+ return (hc->_marker == key || ~hc->_marker == key) ? true : false;
+}
+
+
+#if !defined(CF_OBJC_KVO_WILLCHANGE)
+#define CF_OBJC_KVO_WILLCHANGE(obj, key)
+#define CF_OBJC_KVO_DIDCHANGE(obj, key)
+#endif
+
+CF_INLINE uintptr_t __CFSetScrambleHash(uintptr_t k) {
+#if 0
+ return k;
+#else
+#if __LP64__
+ uintptr_t a = 0x4368726973746F70ULL;
+ uintptr_t b = 0x686572204B616E65ULL;
+#else
+ uintptr_t a = 0x4B616E65UL;
+ uintptr_t b = 0x4B616E65UL;
+#endif
+ uintptr_t c = 1;
+ a += k;
+#if __LP64__
+ a -= b; a -= c; a ^= (c >> 43);
+ b -= c; b -= a; b ^= (a << 9);
+ c -= a; c -= b; c ^= (b >> 8);
+ a -= b; a -= c; a ^= (c >> 38);
+ b -= c; b -= a; b ^= (a << 23);
+ c -= a; c -= b; c ^= (b >> 5);
+ a -= b; a -= c; a ^= (c >> 35);
+ b -= c; b -= a; b ^= (a << 49);
+ c -= a; c -= b; c ^= (b >> 11);
+ a -= b; a -= c; a ^= (c >> 12);
+ b -= c; b -= a; b ^= (a << 18);
+ c -= a; c -= b; c ^= (b >> 22);
+#else
+ a -= b; a -= c; a ^= (c >> 13);
+ b -= c; b -= a; b ^= (a << 8);
+ c -= a; c -= b; c ^= (b >> 13);
+ a -= b; a -= c; a ^= (c >> 12);
+ b -= c; b -= a; b ^= (a << 16);
+ c -= a; c -= b; c ^= (b >> 5);
+ a -= b; a -= c; a ^= (c >> 3);
+ b -= c; b -= a; b ^= (a << 10);
+ c -= a; c -= b; c ^= (b >> 15);
+#endif
+ return c;
+#endif
+}
+
+static CFIndex __CFSetFindBuckets1a(CFHashRef hc, any_t key) {
+ CFHashCode keyHash = (CFHashCode)key;
+ keyHash = __CFSetScrambleHash(keyHash);
+ any_t *keys = hc->_keys;
+ any_t marker = hc->_marker;
+ CFIndex probe = keyHash & (hc->_bucketsNum - 1);
+ CFIndex probeskip = 1; // See RemoveValue() for notes before changing this value
+ CFIndex start = probe;
+ for (;;) {
+ any_t currKey = keys[probe];
+ if (marker == currKey) { /* empty */
+ return kCFNotFound;
+ } else if (~marker == currKey) { /* deleted */
+ /* do nothing */
+ } else if (currKey == key) {
+ return probe;
+ }
+ probe = probe + probeskip;
+ // This alternative to probe % buckets assumes that
+ // probeskip is always positive and less than the
+ // number of buckets.
+ if (hc->_bucketsNum <= probe) {
+ probe -= hc->_bucketsNum;
+ }
+ if (start == probe) {
+ return kCFNotFound;
+ }
+ }
+}
+
+static CFIndex __CFSetFindBuckets1b(CFHashRef hc, any_t key) {
+ const CFSetKeyCallBacks *cb = __CFSetGetKeyCallBacks(hc);
+ CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(any_t, any_pointer_t))cb->hash), key, hc->_context) : (CFHashCode)key;
+ keyHash = __CFSetScrambleHash(keyHash);
+ any_t *keys = hc->_keys;
+ any_t marker = hc->_marker;
+ CFIndex probe = keyHash & (hc->_bucketsNum - 1);
+ CFIndex probeskip = 1; // See RemoveValue() for notes before changing this value
+ CFIndex start = probe;
+ for (;;) {
+ any_t currKey = keys[probe];
+ if (marker == currKey) { /* empty */
+ return kCFNotFound;
+ } else if (~marker == currKey) { /* deleted */
+ /* do nothing */
+ } else if (currKey == key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(any_t, any_t, any_pointer_t))cb->equal, currKey, key, hc->_context))) {
+ return probe;
+ }
+ probe = probe + probeskip;
+ // This alternative to probe % buckets assumes that
+ // probeskip is always positive and less than the
+ // number of buckets.
+ if (hc->_bucketsNum <= probe) {
+ probe -= hc->_bucketsNum;
+ }
+ if (start == probe) {
+ return kCFNotFound;
+ }
+ }
+}
+
+CF_INLINE CFIndex __CFSetFindBuckets1(CFHashRef hc, any_t key) {
+ if (__kCFHashHasNullCallBacks == __CFBitfieldGetValue(hc->_xflags, 3, 2)) {
+ return __CFSetFindBuckets1a(hc, key);
+ }
+ return __CFSetFindBuckets1b(hc, key);
+}
+
+static void __CFSetFindBuckets2(CFHashRef hc, any_t key, CFIndex *match, CFIndex *nomatch) {
+ const CFSetKeyCallBacks *cb = __CFSetGetKeyCallBacks(hc);
+ CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(any_t, any_pointer_t))cb->hash), key, hc->_context) : (CFHashCode)key;
+ keyHash = __CFSetScrambleHash(keyHash);
+ any_t *keys = hc->_keys;
+ any_t marker = hc->_marker;
+ CFIndex probe = keyHash & (hc->_bucketsNum - 1);
+ CFIndex probeskip = 1; // See RemoveValue() for notes before changing this value
+ CFIndex start = probe;
+ *match = kCFNotFound;
+ *nomatch = kCFNotFound;
+ for (;;) {
+ any_t currKey = keys[probe];
+ if (marker == currKey) { /* empty */
+ if (nomatch) *nomatch = probe;
+ return;
+ } else if (~marker == currKey) { /* deleted */
+ if (nomatch) {
+ *nomatch = probe;
+ nomatch = NULL;
+ }
+ } else if (currKey == key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(any_t, any_t, any_pointer_t))cb->equal, currKey, key, hc->_context))) {
+ *match = probe;
+ return;
+ }
+ probe = probe + probeskip;
+ // This alternative to probe % buckets assumes that
+ // probeskip is always positive and less than the
+ // number of buckets.
+ if (hc->_bucketsNum <= probe) {
+ probe -= hc->_bucketsNum;
+ }
+ if (start == probe) {
+ return;
+ }
+ }
+}
+
+static void __CFSetFindNewMarker(CFHashRef hc) {
+ any_t *keys = hc->_keys;
+ any_t newMarker;
+ CFIndex idx, nbuckets;
+ Boolean hit;
+
+ nbuckets = hc->_bucketsNum;
+ newMarker = hc->_marker;
+ do {
+ newMarker--;
+ hit = false;
+ for (idx = 0; idx < nbuckets; idx++) {
+ if (newMarker == keys[idx] || ~newMarker == keys[idx]) {
+ hit = true;
+ break;
+ }
+ }
+ } while (hit);
+ for (idx = 0; idx < nbuckets; idx++) {
+ if (hc->_marker == keys[idx]) {
+ keys[idx] = newMarker;
+ } else if (~hc->_marker == keys[idx]) {
+ keys[idx] = ~newMarker;
+ }
+ }
+ ((struct __CFSet *)hc)->_marker = newMarker;
+}
+
+static Boolean __CFSetEqual(CFTypeRef cf1, CFTypeRef cf2) {
+ CFHashRef hc1 = (CFHashRef)cf1;
+ CFHashRef hc2 = (CFHashRef)cf2;
+ const CFSetKeyCallBacks *cb1, *cb2;
+ const CFSetValueCallBacks *vcb1, *vcb2;
+ any_t *keys;
+ CFIndex idx, nbuckets;
+ if (hc1 == hc2) return true;
+ if (hc1->_count != hc2->_count) return false;
+ cb1 = __CFSetGetKeyCallBacks(hc1);
+ cb2 = __CFSetGetKeyCallBacks(hc2);
+ if (cb1->equal != cb2->equal) return false;
+ vcb1 = __CFSetGetValueCallBacks(hc1);
+ vcb2 = __CFSetGetValueCallBacks(hc2);
+ if (vcb1->equal != vcb2->equal) return false;
+ if (0 == hc1->_bucketsUsed) return true; /* after function comparison! */
+ keys = hc1->_keys;
+ nbuckets = hc1->_bucketsNum;
+ for (idx = 0; idx < nbuckets; idx++) {
+ if (hc1->_marker != keys[idx] && ~hc1->_marker != keys[idx]) {
+#if CFDictionary
+ const_any_pointer_t value;
+ if (!CFSetGetValueIfPresent(hc2, (any_pointer_t)keys[idx], &value)) return false;
+ if (hc1->_values[idx] != (any_t)value) {
+ if (NULL == vcb1->equal) return false;
+ if (!INVOKE_CALLBACK3((Boolean (*)(any_t, any_t, any_pointer_t))vcb1->equal, hc1->_values[idx], (any_t)value, hc1->_context)) return false;
+ }
+#endif
+#if CFSet
+ const_any_pointer_t value;
+ if (!CFSetGetValueIfPresent(hc2, (any_pointer_t)keys[idx], &value)) return false;
+#endif
+#if CFBag
+ if (hc1->_values[idx] != CFSetGetCountOfValue(hc2, (any_pointer_t)keys[idx])) return false;
+#endif
+ }
+ }
+ return true;
+}
+
+static CFHashCode __CFSetHash(CFTypeRef cf) {
+ CFHashRef hc = (CFHashRef)cf;
+ return hc->_count;
+}
+
+static CFStringRef __CFSetCopyDescription(CFTypeRef cf) {
+ CFHashRef hc = (CFHashRef)cf;
+ CFAllocatorRef allocator;
+ const CFSetKeyCallBacks *cb;
+ const CFSetValueCallBacks *vcb;
+ any_t *keys;
+ CFIndex idx, nbuckets;
+ CFMutableStringRef result;
+ cb = __CFSetGetKeyCallBacks(hc);
+ vcb = __CFSetGetValueCallBacks(hc);
+ keys = hc->_keys;
+ nbuckets = hc->_bucketsNum;
+ allocator = CFGetAllocator(hc);
+ result = CFStringCreateMutable(allocator, 0);
+ const char *type = "?";
+ switch (__CFHashGetType(hc)) {
+ case __kCFHashImmutable: type = "immutable"; break;
+ case __kCFHashMutable: type = "mutable"; break;
+ }
+ CFStringAppendFormat(result, NULL, CFSTR("<CFSet %p [%p]>{type = %s, count = %u, capacity = %u, pairs = (\n"), cf, allocator, type, hc->_count, hc->_bucketsCap);
+ for (idx = 0; idx < nbuckets; idx++) {
+ if (__CFHashKeyIsValue(hc, keys[idx])) {
+ CFStringRef kDesc = NULL, vDesc = NULL;
+ if (NULL != cb->copyDescription) {
+ kDesc = (CFStringRef)INVOKE_CALLBACK2(((CFStringRef (*)(any_t, any_pointer_t))cb->copyDescription), keys[idx], hc->_context);
+ }
+ if (NULL != vcb->copyDescription) {
+ vDesc = (CFStringRef)INVOKE_CALLBACK2(((CFStringRef (*)(any_t, any_pointer_t))vcb->copyDescription), hc->_values[idx], hc->_context);
+ }
+#if CFDictionary
+ if (NULL != kDesc && NULL != vDesc) {
+ CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@ = %@\n"), idx, kDesc, vDesc);
+ CFRelease(kDesc);
+ CFRelease(vDesc);
+ } else if (NULL != kDesc) {
+ CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@ = <%p>\n"), idx, kDesc, hc->_values[idx]);
+ CFRelease(kDesc);
+ } else if (NULL != vDesc) {
+ CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p> = %@\n"), idx, keys[idx], vDesc);
+ CFRelease(vDesc);
+ } else {
+ CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p> = <%p>\n"), idx, keys[idx], hc->_values[idx]);
+ }
+#endif
+#if CFSet
+ if (NULL != kDesc) {
+ CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@\n"), idx, kDesc);
+ CFRelease(kDesc);
+ } else {
+ CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p>\n"), idx, keys[idx]);
+ }
+#endif
+#if CFBag
+ if (NULL != kDesc) {
+ CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@ (%ld)\n"), idx, kDesc, hc->_values[idx]);
+ CFRelease(kDesc);
+ } else {
+ CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p> (%ld)\n"), idx, keys[idx], hc->_values[idx]);
+ }
+#endif
+ }
+ }
+ CFStringAppend(result, CFSTR(")}"));
+ return result;
+}
+
+static void __CFSetDeallocate(CFTypeRef cf) {
+ CFMutableHashRef hc = (CFMutableHashRef)cf;
+ CFAllocatorRef allocator = __CFGetAllocator(hc);
+ const CFSetKeyCallBacks *cb = __CFSetGetKeyCallBacks(hc);
+ const CFSetValueCallBacks *vcb = __CFSetGetValueCallBacks(hc);
+
+ // mark now in case any callout somehow tries to add an entry back in
+ markFinalized(cf);
+ if (vcb->release || cb->release) {
+ any_t *keys = hc->_keys;
+ CFIndex idx, nbuckets = hc->_bucketsNum;
+ for (idx = 0; idx < nbuckets; idx++) {
+ any_t oldkey = keys[idx];
+ if (hc->_marker != oldkey && ~hc->_marker != oldkey) {
+ if (vcb->release) {
+ INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, any_t, any_pointer_t))vcb->release), allocator, hc->_values[idx], hc->_context);
+ }
+ if (cb->release) {
+ INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, any_t, any_pointer_t))cb->release), allocator, oldkey, hc->_context);
+ }
+ }
+ }
+ }
+
+ if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
+ // return early so that contents are preserved after finalization
+ return;
+ }
+
+ _CFAllocatorDeallocateGC(allocator, hc->_keys);
+#if CFDictionary || CFBag
+ _CFAllocatorDeallocateGC(allocator, hc->_values);
+#endif
+ hc->_keys = NULL;
+ hc->_values = NULL;
+ hc->_count = 0; // GC: also zero count, so the hc will appear empty.
+ hc->_bucketsUsed = 0;
+ hc->_bucketsNum = 0;
+}
+
+static CFTypeID __kCFSetTypeID = _kCFRuntimeNotATypeID;
+
+static const CFRuntimeClass __CFSetClass = {
+ _kCFRuntimeScannedObject,
+ "CFSet",
+ NULL, // init
+ NULL, // copy
+ __CFSetDeallocate,
+ __CFSetEqual,
+ __CFSetHash,
+ NULL, //
+ __CFSetCopyDescription
+};
+
+__private_extern__ void __CFSetInitialize(void) {
+ __kCFHashTypeID = _CFRuntimeRegisterClass(&__CFSetClass);
+}
+
+CFTypeID CFSetGetTypeID(void) {
+ return __kCFHashTypeID;
+}
+
+static CFMutableHashRef __CFSetInit(CFAllocatorRef allocator, CFOptionFlags flags, CFIndex capacity, const CFSetKeyCallBacks *keyCallBacks
+#if CFDictionary
+, const CFSetValueCallBacks *valueCallBacks
+#endif
+) {
+ struct __CFSet *hc;
+ CFIndex size;
+ __CFBitfieldSetValue(flags, 31, 2, 0);
+ CFOptionFlags xflags = 0;
+ if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
+ // preserve NULL for key or value CB, otherwise fix up.
+ if (!keyCallBacks || (keyCallBacks->retain == NULL && keyCallBacks->release == NULL)) {
+ xflags = __kCFHashWeakKeys;
+ }
+#if CFDictionary
+ if (!valueCallBacks || (valueCallBacks->retain == NULL && valueCallBacks->release == NULL)) {
+ xflags |= __kCFHashWeakValues;
+ }
+#endif
+#if CFBag
+ xflags |= __kCFHashWeakValues;
+#endif
+ }
+ if (__CFSetKeyCallBacksMatchNull(keyCallBacks)) {
+ __CFBitfieldSetValue(flags, 3, 2, __kCFHashHasNullCallBacks);
+ } else if (__CFSetKeyCallBacksMatchCFType(keyCallBacks)) {
+ __CFBitfieldSetValue(flags, 3, 2, __kCFHashHasCFTypeCallBacks);
+ } else {
+ __CFBitfieldSetValue(flags, 3, 2, __kCFHashHasCustomCallBacks);
+ }
+#if CFDictionary
+ if (__CFSetValueCallBacksMatchNull(valueCallBacks)) {
+ __CFBitfieldSetValue(flags, 5, 4, __kCFHashHasNullCallBacks);
+ } else if (__CFSetValueCallBacksMatchCFType(valueCallBacks)) {
+ __CFBitfieldSetValue(flags, 5, 4, __kCFHashHasCFTypeCallBacks);
+ } else {
+ __CFBitfieldSetValue(flags, 5, 4, __kCFHashHasCustomCallBacks);
+ }
+#endif
+ size = __CFSetGetSizeOfType(flags) - sizeof(CFRuntimeBase);
+ hc = (struct __CFSet *)_CFRuntimeCreateInstance(allocator, __kCFHashTypeID, size, NULL);
+ if (NULL == hc) {
+ return NULL;
+ }
+ hc->_count = 0;
+ hc->_bucketsUsed = 0;
+ hc->_marker = (any_t)0xa1b1c1d3;
+ hc->_context = NULL;
+ hc->_deletes = 0;
+ hc->_mutations = 1;
+ hc->_xflags = xflags | flags;
+ switch (__CFBitfieldGetValue(flags, 1, 0)) {
+ case __kCFHashImmutable:
+ if (__CFOASafe) __CFSetLastAllocationEventName(hc, "CFSet (immutable)");
+ break;
+ case __kCFHashMutable:
+ if (__CFOASafe) __CFSetLastAllocationEventName(hc, "CFSet (mutable-variable)");
+ break;
+ }
+ hc->_bucketsCap = __CFHashRoundUpCapacity(1);
+ hc->_bucketsNum = 0;
+ hc->_keys = NULL;
+ hc->_values = NULL;
+ if (__kCFHashHasCustomCallBacks == __CFBitfieldGetValue(flags, 3, 2)) {
+ CFSetKeyCallBacks *cb = (CFSetKeyCallBacks *)__CFSetGetKeyCallBacks((CFHashRef)hc);
+ *cb = *keyCallBacks;
+ FAULT_CALLBACK((void **)&(cb->retain));
+ FAULT_CALLBACK((void **)&(cb->release));
+ FAULT_CALLBACK((void **)&(cb->copyDescription));
+ FAULT_CALLBACK((void **)&(cb->equal));
+ FAULT_CALLBACK((void **)&(cb->hash));
+ }
+#if CFDictionary
+ if (__kCFHashHasCustomCallBacks == __CFBitfieldGetValue(flags, 5, 4)) {
+ CFSetValueCallBacks *vcb = (CFSetValueCallBacks *)__CFSetGetValueCallBacks((CFHashRef)hc);
+ *vcb = *valueCallBacks;
+ FAULT_CALLBACK((void **)&(vcb->retain));
+ FAULT_CALLBACK((void **)&(vcb->release));
+ FAULT_CALLBACK((void **)&(vcb->copyDescription));
+ FAULT_CALLBACK((void **)&(vcb->equal));
+ }
+#endif
+ return hc;
+}
+
+#if CFDictionary
+CFHashRef CFSetCreate(CFAllocatorRef allocator, const_any_pointer_t *keys, const_any_pointer_t *values, CFIndex numValues, const CFSetKeyCallBacks *keyCallBacks, const CFSetValueCallBacks *valueCallBacks) {
+#endif
+#if CFSet || CFBag
+CFHashRef CFSetCreate(CFAllocatorRef allocator, const_any_pointer_t *keys, CFIndex numValues, const CFSetKeyCallBacks *keyCallBacks) {
+#endif
+ CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%ld) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
+#if CFDictionary
+ CFMutableHashRef hc = __CFSetInit(allocator, __kCFHashImmutable, numValues, keyCallBacks, valueCallBacks);
+#endif
+#if CFSet || CFBag
+ CFMutableHashRef hc = __CFSetInit(allocator, __kCFHashImmutable, numValues, keyCallBacks);
+#endif
+ __CFBitfieldSetValue(hc->_xflags, 1, 0, __kCFHashMutable);
+ for (CFIndex idx = 0; idx < numValues; idx++) {
+#if CFDictionary
+ CFSetAddValue(hc, keys[idx], values[idx]);
+#endif
+#if CFSet || CFBag
+ CFSetAddValue(hc, keys[idx]);
+#endif
+ }
+ __CFBitfieldSetValue(hc->_xflags, 1, 0, __kCFHashImmutable);
+ return (CFHashRef)hc;
+}
+
+#if CFDictionary
+CFMutableHashRef CFSetCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFSetKeyCallBacks *keyCallBacks, const CFSetValueCallBacks *valueCallBacks) {
+#endif
+#if CFSet || CFBag
+CFMutableHashRef CFSetCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFSetKeyCallBacks *keyCallBacks) {
+#endif
+ CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%ld) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
+#if CFDictionary
+ CFMutableHashRef hc = __CFSetInit(allocator, __kCFHashMutable, capacity, keyCallBacks, valueCallBacks);
+#endif
+#if CFSet || CFBag
+ CFMutableHashRef hc = __CFSetInit(allocator, __kCFHashMutable, capacity, keyCallBacks);
+#endif
+ return hc;
+}
+
+#if CFDictionary || CFSet
+// does not have Add semantics for Bag; it has Set semantics ... is that best?
+static void __CFSetGrow(CFMutableHashRef hc, CFIndex numNewValues);
+
+// This creates a hc which is for CFTypes or NSObjects, with a CFRetain style ownership transfer;
+// the hc does not take a retain (since it claims 1), and the caller does not need to release the inserted objects (since we do it).
+// The incoming objects must also be collectable if allocated out of a collectable allocator - and are neither released nor retained.
+#if CFDictionary
+CFHashRef _CFSetCreate_ex(CFAllocatorRef allocator, Boolean isMutable, const_any_pointer_t *keys, const_any_pointer_t *values, CFIndex numValues) {
+#endif
+#if CFSet || CFBag
+CFHashRef _CFSetCreate_ex(CFAllocatorRef allocator, Boolean isMutable, const_any_pointer_t *keys, CFIndex numValues) {
+#endif
+ CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%ld) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
+#if CFDictionary
+ CFMutableHashRef hc = __CFSetInit(allocator, __kCFHashMutable, numValues, &kCFTypeSetKeyCallBacks, &kCFTypeSetValueCallBacks);
+#endif
+#if CFSet || CFBag
+ CFMutableHashRef hc = __CFSetInit(allocator, __kCFHashMutable, numValues, &kCFTypeSetKeyCallBacks);
+#endif
+ __CFSetGrow(hc, numValues);
+ for (CFIndex idx = 0; idx < numValues; idx++) {
+ CFIndex match, nomatch;
+ __CFSetFindBuckets2(hc, (any_t)keys[idx], &match, &nomatch);
+ if (kCFNotFound == match) {
+ CFAllocatorRef allocator = __CFGetAllocator(hc);
+ any_t newKey = (any_t)keys[idx];
+ if (__CFHashKeyIsMagic(hc, newKey)) {
+ __CFSetFindNewMarker(hc);
+ }
+ if (hc->_keys[nomatch] == ~hc->_marker) {
+ hc->_deletes--;
+ }
+ CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
+ CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[nomatch], newKey);
+#if CFDictionary
+ any_t newValue = (any_t)values[idx];
+ CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
+ CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[nomatch], newValue);
+#endif
+#if CFBag
+ hc->_values[nomatch] = 1;
+#endif
+ hc->_bucketsUsed++;
+ hc->_count++;
+ } else {
+ CFAllocatorRef allocator = __CFGetAllocator(hc);
+#if CFSet || CFBag
+ any_t oldKey = hc->_keys[match];
+ any_t newKey = (any_t)keys[idx];
+ CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
+ CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], ~hc->_marker);
+ if (__CFHashKeyIsMagic(hc, newKey)) {
+ __CFSetFindNewMarker(hc);
+ }
+ CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], newKey);
+ RELEASEKEY(oldKey);
+#endif
+#if CFDictionary
+ any_t oldValue = hc->_values[match];
+ any_t newValue = (any_t)values[idx];
+ CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
+ CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[match], newValue);
+ RELEASEVALUE(oldValue);
+#endif
+ }
+ }
+ if (!isMutable) __CFBitfieldSetValue(hc->_xflags, 1, 0, __kCFHashImmutable);
+ return (CFHashRef)hc;
+}
+#endif
+
+CFHashRef CFSetCreateCopy(CFAllocatorRef allocator, CFHashRef other) {
+ CFMutableHashRef hc = CFSetCreateMutableCopy(allocator, CFSetGetCount(other), other);
+ __CFBitfieldSetValue(hc->_xflags, 1, 0, __kCFHashImmutable);
+ if (__CFOASafe) __CFSetLastAllocationEventName(hc, "CFSet (immutable)");
+ return hc;
+}
+
+CFMutableHashRef CFSetCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFHashRef other) {
+ CFIndex numValues = CFSetGetCount(other);
+ const_any_pointer_t *list, buffer[256];
+ list = (numValues <= 256) ? buffer : (const_any_pointer_t *)CFAllocatorAllocate(allocator, numValues * sizeof(const_any_pointer_t), 0);
+ if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFSet (temp)");
+#if CFDictionary
+ const_any_pointer_t *vlist, vbuffer[256];
+ vlist = (numValues <= 256) ? vbuffer : (const_any_pointer_t *)CFAllocatorAllocate(allocator, numValues * sizeof(const_any_pointer_t), 0);
+ if (vlist != vbuffer && __CFOASafe) __CFSetLastAllocationEventName(vlist, "CFSet (temp)");
+#endif
+#if CFSet || CFBag
+ CFSetGetValues(other, list);
+#endif
+#if CFDictionary
+ CFSetGetKeysAndValues(other, list, vlist);
+#endif
+ const CFSetKeyCallBacks *kcb;
+ const CFSetValueCallBacks *vcb;
+ if (CF_IS_OBJC(__kCFHashTypeID, other)) {
+ kcb = &kCFTypeSetKeyCallBacks;
+ vcb = &kCFTypeSetValueCallBacks;
+ } else {
+ kcb = __CFSetGetKeyCallBacks(other);
+ vcb = __CFSetGetValueCallBacks(other);
+ }
+#if CFDictionary
+ CFMutableHashRef hc = __CFSetInit(allocator, __kCFHashMutable, capacity, kcb, vcb);
+#endif
+#if CFSet || CFBag
+ CFMutableHashRef hc = __CFSetInit(allocator, __kCFHashMutable, capacity, kcb);
+#endif
+ if (0 == capacity) _CFSetSetCapacity(hc, numValues);
+ for (CFIndex idx = 0; idx < numValues; idx++) {
+#if CFDictionary
+ CFSetAddValue(hc, list[idx], vlist[idx]);
+#endif
+#if CFSet || CFBag
+ CFSetAddValue(hc, list[idx]);
+#endif
+ }
+ if (list != buffer) CFAllocatorDeallocate(allocator, list);
+#if CFDictionary
+ if (vlist != vbuffer) CFAllocatorDeallocate(allocator, vlist);
+#endif
+ return hc;
+}
+
+// Used by NSHashTables/NSMapTables and KVO
+void _CFSetSetContext(CFHashRef hc, any_pointer_t context) {
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ CF_WRITE_BARRIER_BASE_ASSIGN(__CFGetAllocator(hc), hc, hc->_context, context);
+}
+
+any_pointer_t _CFSetGetContext(CFHashRef hc) {
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ return hc->_context;
+}
+
+CFIndex CFSetGetCount(CFHashRef hc) {
+ if (CFDictionary || CFSet) CF_OBJC_FUNCDISPATCH0(__kCFHashTypeID, CFIndex, hc, "count");
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ return hc->_count;
+}
+
+#if CFDictionary
+CFIndex CFSetGetCountOfKey(CFHashRef hc, const_any_pointer_t key) {
+#endif
+#if CFSet || CFBag
+CFIndex CFSetGetCountOfValue(CFHashRef hc, const_any_pointer_t key) {
+#endif
+ if (CFDictionary) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, CFIndex, hc, "countForKey:", key);
+ if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, CFIndex, hc, "countForObject:", key);
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ if (0 == hc->_bucketsUsed) return 0;
+ CFIndex match = __CFSetFindBuckets1(hc, (any_t)key);
+ return (kCFNotFound != match ? __CFHashGetOccurrenceCount(hc, match) : 0);
+}
+
+#if CFDictionary
+Boolean CFSetContainsKey(CFHashRef hc, const_any_pointer_t key) {
+#endif
+#if CFSet || CFBag
+Boolean CFSetContainsValue(CFHashRef hc, const_any_pointer_t key) {
+#endif
+ if (CFDictionary) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, char, hc, "containsKey:", key);
+ if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, char, hc, "containsObject:", key);
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ if (0 == hc->_bucketsUsed) return false;
+ CFIndex match = __CFSetFindBuckets1(hc, (any_t)key);
+ return (kCFNotFound != match ? true : false);
+}
+
+#if CFDictionary
+CFIndex CFSetGetCountOfValue(CFHashRef hc, const_any_pointer_t value) {
+ CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, CFIndex, hc, "countForObject:", value);
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ if (0 == hc->_bucketsUsed) return 0;
+ any_t *keys = hc->_keys;
+ Boolean (*equal)(any_t, any_t, any_pointer_t) = (Boolean (*)(any_t, any_t, any_pointer_t))__CFSetGetValueCallBacks(hc)->equal;
+ CFIndex cnt = 0;
+ for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
+ if (__CFHashKeyIsValue(hc, keys[idx])) {
+ if ((hc->_values[idx] == (any_t)value) || (equal && INVOKE_CALLBACK3(equal, hc->_values[idx], (any_t)value, hc->_context))) {
+ cnt++;
+ }
+ }
+ }
+ return cnt;
+}
+
+Boolean CFSetContainsValue(CFHashRef hc, const_any_pointer_t value) {
+ CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, char, hc, "containsObject:", value);
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ if (0 == hc->_bucketsUsed) return false;
+ any_t *keys = hc->_keys;
+ Boolean (*equal)(any_t, any_t, any_pointer_t) = (Boolean (*)(any_t, any_t, any_pointer_t))__CFSetGetValueCallBacks(hc)->equal;
+ for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
+ if (__CFHashKeyIsValue(hc, keys[idx])) {
+ if ((hc->_values[idx] == (any_t)value) || (equal && INVOKE_CALLBACK3(equal, hc->_values[idx], (any_t)value, hc->_context))) {
+ return true;
+ }
+ }
+ }
+ return false;
+}
+#endif
+
+const_any_pointer_t CFSetGetValue(CFHashRef hc, const_any_pointer_t key) {
+ if (CFDictionary) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, const_any_pointer_t, hc, "objectForKey:", key);
+ if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, const_any_pointer_t, hc, "member:", key);
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ if (0 == hc->_bucketsUsed) return 0;
+ CFIndex match = __CFSetFindBuckets1(hc, (any_t)key);
+ return (kCFNotFound != match ? (const_any_pointer_t)(CFDictionary ? hc->_values[match] : hc->_keys[match]) : 0);
+}
+
+Boolean CFSetGetValueIfPresent(CFHashRef hc, const_any_pointer_t key, const_any_pointer_t *value) {
+ if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, Boolean, hc, "_getValue:forKey:", (any_t *)value, key);
+ if (CFSet) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, Boolean, hc, "_getValue:forObj:", (any_t *)value, key);
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ if (0 == hc->_bucketsUsed) return false;
+ CFIndex match = __CFSetFindBuckets1(hc, (any_t)key);
+ return (kCFNotFound != match ? ((value ? __CFObjCStrongAssign((const_any_pointer_t)(CFDictionary ? hc->_values[match] : hc->_keys[match]), value) : 0), true) : false);
+}
+
+#if CFDictionary
+Boolean CFSetGetKeyIfPresent(CFHashRef hc, const_any_pointer_t key, const_any_pointer_t *actualkey) {
+ CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, Boolean, hc, "getActualKey:forKey:", actualkey, key);
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ if (0 == hc->_bucketsUsed) return false;
+ CFIndex match = __CFSetFindBuckets1(hc, (any_t)key);
+ return (kCFNotFound != match ? ((actualkey ? __CFObjCStrongAssign((const_any_pointer_t)hc->_keys[match], actualkey) : NULL), true) : false);
+}
+#endif
+
+#if CFDictionary
+void CFSetGetKeysAndValues(CFHashRef hc, const_any_pointer_t *keybuf, const_any_pointer_t *valuebuf) {
+#endif
+#if CFSet || CFBag
+void CFSetGetValues(CFHashRef hc, const_any_pointer_t *keybuf) {
+ const_any_pointer_t *valuebuf = 0;
+#endif
+ if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "getObjects:andKeys:", (any_t *)valuebuf, (any_t *)keybuf);
+ if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "getObjects:", (any_t *)keybuf);
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ if (CF_USING_COLLECTABLE_MEMORY) {
+ // GC: speculatively issue a write-barrier on the copied to buffers
+ __CFObjCWriteBarrierRange(keybuf, hc->_count * sizeof(any_t));
+ __CFObjCWriteBarrierRange(valuebuf, hc->_count * sizeof(any_t));
+ }
+ any_t *keys = hc->_keys;
+ for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
+ if (__CFHashKeyIsValue(hc, keys[idx])) {
+ for (CFIndex cnt = __CFHashGetOccurrenceCount(hc, idx); cnt--;) {
+ if (keybuf) *keybuf++ = (const_any_pointer_t)keys[idx];
+ if (valuebuf) *valuebuf++ = (const_any_pointer_t)hc->_values[idx];
+ }
+ }
+ }
+}
+
+#if CFDictionary || CFSet
+unsigned long _CFSetFastEnumeration(CFHashRef hc, struct __objcFastEnumerationStateEquivalent *state, void *stackbuffer, unsigned long count) {
+ /* copy as many as count items over */
+ if (0 == state->state) { /* first time */
+ state->mutationsPtr = (unsigned long *)&hc->_mutations;
+ }
+ state->itemsPtr = (unsigned long *)stackbuffer;
+ CFIndex cnt = 0;
+ any_t *keys = hc->_keys;
+ for (CFIndex idx = (CFIndex)state->state, nbuckets = hc->_bucketsNum; idx < nbuckets && cnt < (CFIndex)count; idx++) {
+ if (__CFHashKeyIsValue(hc, keys[idx])) {
+ state->itemsPtr[cnt++] = (unsigned long)keys[idx];
+ }
+ state->state++;
+ }
+ return cnt;
+}
+#endif
+
+void CFSetApplyFunction(CFHashRef hc, CFSetApplierFunction applier, any_pointer_t context) {
+ FAULT_CALLBACK((void **)&(applier));
+ if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "_apply:context:", applier, context);
+ if (CFSet) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "_applyValues:context:", applier, context);
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ any_t *keys = hc->_keys;
+ for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
+ if (__CFHashKeyIsValue(hc, keys[idx])) {
+ for (CFIndex cnt = __CFHashGetOccurrenceCount(hc, idx); cnt--;) {
+#if CFDictionary
+ INVOKE_CALLBACK3(applier, (const_any_pointer_t)keys[idx], (const_any_pointer_t)hc->_values[idx], context);
+#endif
+#if CFSet || CFBag
+ INVOKE_CALLBACK2(applier, (const_any_pointer_t)keys[idx], context);
+#endif
+ }
+ }
+ }
+}
+
+static void __CFSetGrow(CFMutableHashRef hc, CFIndex numNewValues) {
+ any_t *oldkeys = hc->_keys;
+ any_t *oldvalues = hc->_values;
+ CFIndex nbuckets = hc->_bucketsNum;
+ hc->_bucketsCap = __CFHashRoundUpCapacity(hc->_bucketsUsed + numNewValues);
+ hc->_bucketsNum = __CFHashNumBucketsForCapacity(hc->_bucketsCap);
+ hc->_deletes = 0;
+ CFAllocatorRef allocator = __CFGetAllocator(hc);
+ CFOptionFlags weakOrStrong = (hc->_xflags & __kCFHashWeakKeys) ? 0 : __kCFAllocatorGCScannedMemory;
+ any_t *mem = (any_t *)_CFAllocatorAllocateGC(allocator, hc->_bucketsNum * sizeof(any_t), weakOrStrong);
+ if (NULL == mem) __CFSetHandleOutOfMemory(hc, hc->_bucketsNum * sizeof(any_t));
+ if (__CFOASafe) __CFSetLastAllocationEventName(mem, "CFSet (key-store)");
+ CF_WRITE_BARRIER_BASE_ASSIGN(allocator, hc, hc->_keys, mem);
+ CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator; // GC: avoids write-barrier in weak case.
+ any_t *keysBase = mem;
+#if CFDictionary || CFBag
+ weakOrStrong = (hc->_xflags & __kCFHashWeakValues) ? 0 : __kCFAllocatorGCScannedMemory;
+ mem = (any_t *)_CFAllocatorAllocateGC(allocator, hc->_bucketsNum * sizeof(any_t), weakOrStrong);
+ if (NULL == mem) __CFSetHandleOutOfMemory(hc, hc->_bucketsNum * sizeof(any_t));
+ if (__CFOASafe) __CFSetLastAllocationEventName(mem, "CFSet (value-store)");
+ CF_WRITE_BARRIER_BASE_ASSIGN(allocator, hc, hc->_values, mem);
+#endif
+#if CFDictionary
+ CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator; // GC: avoids write-barrier in weak case.
+ any_t *valuesBase = mem;
+#endif
+ for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
+ hc->_keys[idx] = hc->_marker;
+#if CFDictionary || CFBag
+ hc->_values[idx] = 0;
+#endif
+ }
+ if (NULL == oldkeys) return;
+ for (CFIndex idx = 0; idx < nbuckets; idx++) {
+ if (__CFHashKeyIsValue(hc, oldkeys[idx])) {
+ CFIndex match, nomatch;
+ __CFSetFindBuckets2(hc, oldkeys[idx], &match, &nomatch);
+ CFAssert3(kCFNotFound == 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__, oldkeys[idx], hc->_keys[match]);
+ if (kCFNotFound != nomatch) {
+ CF_WRITE_BARRIER_BASE_ASSIGN(keysAllocator, keysBase, hc->_keys[nomatch], oldkeys[idx]);
+#if CFDictionary
+ CF_WRITE_BARRIER_BASE_ASSIGN(valuesAllocator, valuesBase, hc->_values[nomatch], oldvalues[idx]);
+#endif
+#if CFBag
+ hc->_values[nomatch] = oldvalues[idx];
+#endif
+ }
+ }
+ }
+ _CFAllocatorDeallocateGC(allocator, oldkeys);
+ _CFAllocatorDeallocateGC(allocator, oldvalues);
+}
+
+// This function is for Foundation's benefit; no one else should use it.
+void _CFSetSetCapacity(CFMutableHashRef hc, CFIndex cap) {
+ if (CF_IS_OBJC(__kCFHashTypeID, hc)) return;
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ CFAssert1(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): collection is immutable", __PRETTY_FUNCTION__);
+ CFAssert3(hc->_bucketsUsed <= cap, __kCFLogAssertion, "%s(): desired capacity (%ld) is less than bucket count (%ld)", __PRETTY_FUNCTION__, cap, hc->_bucketsUsed);
+ __CFSetGrow(hc, cap - hc->_bucketsUsed);
+}
+
+
+#if CFDictionary
+void CFSetAddValue(CFMutableHashRef hc, const_any_pointer_t key, const_any_pointer_t value) {
+#endif
+#if CFSet || CFBag
+void CFSetAddValue(CFMutableHashRef hc, const_any_pointer_t key) {
+ #define value 0
+#endif
+ if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "_addObject:forKey:", value, key);
+ if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "addObject:", key);
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ switch (__CFHashGetType(hc)) {
+ case __kCFHashMutable:
+ if (hc->_bucketsUsed == hc->_bucketsCap || NULL == hc->_keys) {
+ __CFSetGrow(hc, 1);
+ }
+ break;
+ default:
+ CFAssert2(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
+ break;
+ }
+ hc->_mutations++;
+ CFIndex match, nomatch;
+ __CFSetFindBuckets2(hc, (any_t)key, &match, &nomatch);
+ if (kCFNotFound != match) {
+#if CFBag
+ CF_OBJC_KVO_WILLCHANGE(hc, hc->_keys[match]);
+ hc->_values[match]++;
+ hc->_count++;
+ CF_OBJC_KVO_DIDCHANGE(hc, hc->_keys[match]);
+#endif
+ } else {
+ CFAllocatorRef allocator = __CFGetAllocator(hc);
+ GETNEWKEY(newKey, key);
+#if CFDictionary
+ GETNEWVALUE(newValue);
+#endif
+ if (__CFHashKeyIsMagic(hc, newKey)) {
+ __CFSetFindNewMarker(hc);
+ }
+ if (hc->_keys[nomatch] == ~hc->_marker) {
+ hc->_deletes--;
+ }
+ CF_OBJC_KVO_WILLCHANGE(hc, key);
+ CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
+ CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[nomatch], newKey);
+#if CFDictionary
+ CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
+ CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[nomatch], newValue);
+#endif
+#if CFBag
+ hc->_values[nomatch] = 1;
+#endif
+ hc->_bucketsUsed++;
+ hc->_count++;
+ CF_OBJC_KVO_DIDCHANGE(hc, key);
+ }
+}
+
+#if CFDictionary
+void CFSetReplaceValue(CFMutableHashRef hc, const_any_pointer_t key, const_any_pointer_t value) {
+#endif
+#if CFSet || CFBag
+void CFSetReplaceValue(CFMutableHashRef hc, const_any_pointer_t key) {
+ #define value 0
+#endif
+ if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "_replaceObject:forKey:", value, key);
+ if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "_replaceObject:", key);
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ switch (__CFHashGetType(hc)) {
+ case __kCFHashMutable:
+ break;
+ default:
+ CFAssert2(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
+ break;
+ }
+ hc->_mutations++;
+ if (0 == hc->_bucketsUsed) return;
+ CFIndex match = __CFSetFindBuckets1(hc, (any_t)key);
+ if (kCFNotFound == match) return;
+ CFAllocatorRef allocator = __CFGetAllocator(hc);
+#if CFSet || CFBag
+ GETNEWKEY(newKey, key);
+#endif
+#if CFDictionary
+ GETNEWVALUE(newValue);
+#endif
+ any_t oldKey = hc->_keys[match];
+ CF_OBJC_KVO_WILLCHANGE(hc, oldKey);
+#if CFSet || CFBag
+ CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
+ CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], ~hc->_marker);
+ if (__CFHashKeyIsMagic(hc, newKey)) {
+ __CFSetFindNewMarker(hc);
+ }
+ CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], newKey);
+#endif
+#if CFDictionary
+ any_t oldValue = hc->_values[match];
+ CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
+ CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[match], newValue);
+#endif
+ CF_OBJC_KVO_DIDCHANGE(hc, oldKey);
+#if CFSet || CFBag
+ RELEASEKEY(oldKey);
+#endif
+#if CFDictionary
+ RELEASEVALUE(oldValue);
+#endif
+}
+
+#if CFDictionary
+void CFSetSetValue(CFMutableHashRef hc, const_any_pointer_t key, const_any_pointer_t value) {
+#endif
+#if CFSet || CFBag
+void CFSetSetValue(CFMutableHashRef hc, const_any_pointer_t key) {
+ #define value 0
+#endif
+ if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "setObject:forKey:", value, key);
+ if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "_setObject:", key);
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ switch (__CFHashGetType(hc)) {
+ case __kCFHashMutable:
+ if (hc->_bucketsUsed == hc->_bucketsCap || NULL == hc->_keys) {
+ __CFSetGrow(hc, 1);
+ }
+ break;
+ default:
+ CFAssert2(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
+ break;
+ }
+ hc->_mutations++;
+ CFIndex match, nomatch;
+ __CFSetFindBuckets2(hc, (any_t)key, &match, &nomatch);
+ if (kCFNotFound == match) {
+ CFAllocatorRef allocator = __CFGetAllocator(hc);
+ GETNEWKEY(newKey, key);
+#if CFDictionary
+ GETNEWVALUE(newValue);
+#endif
+ if (__CFHashKeyIsMagic(hc, newKey)) {
+ __CFSetFindNewMarker(hc);
+ }
+ if (hc->_keys[nomatch] == ~hc->_marker) {
+ hc->_deletes--;
+ }
+ CF_OBJC_KVO_WILLCHANGE(hc, key);
+ CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
+ CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[nomatch], newKey);
+#if CFDictionary
+ CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
+ CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[nomatch], newValue);
+#endif
+#if CFBag
+ hc->_values[nomatch] = 1;
+#endif
+ hc->_bucketsUsed++;
+ hc->_count++;
+ CF_OBJC_KVO_DIDCHANGE(hc, key);
+ } else {
+ CFAllocatorRef allocator = __CFGetAllocator(hc);
+#if CFSet || CFBag
+ GETNEWKEY(newKey, key);
+#endif
+#if CFDictionary
+ GETNEWVALUE(newValue);
+#endif
+ any_t oldKey = hc->_keys[match];
+ CF_OBJC_KVO_WILLCHANGE(hc, oldKey);
+#if CFSet || CFBag
+ CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
+ CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], ~hc->_marker);
+ if (__CFHashKeyIsMagic(hc, newKey)) {
+ __CFSetFindNewMarker(hc);
+ }
+ CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], newKey);
+#endif
+#if CFDictionary
+ any_t oldValue = hc->_values[match];
+ CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
+ CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[match], newValue);
+#endif
+ CF_OBJC_KVO_DIDCHANGE(hc, oldKey);
+#if CFSet || CFBag
+ RELEASEKEY(oldKey);
+#endif
+#if CFDictionary
+ RELEASEVALUE(oldValue);
+#endif
+ }
+}
+
+void CFSetRemoveValue(CFMutableHashRef hc, const_any_pointer_t key) {
+ if (CFDictionary) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "removeObjectForKey:", key);
+ if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "removeObject:", key);
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ switch (__CFHashGetType(hc)) {
+ case __kCFHashMutable:
+ break;
+ default:
+ CFAssert2(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
+ break;
+ }
+ hc->_mutations++;
+ if (0 == hc->_bucketsUsed) return;
+ CFIndex match = __CFSetFindBuckets1(hc, (any_t)key);
+ if (kCFNotFound == match) return;
+ if (1 < __CFHashGetOccurrenceCount(hc, match)) {
+#if CFBag
+ CF_OBJC_KVO_WILLCHANGE(hc, hc->_keys[match]);
+ hc->_values[match]--;
+ hc->_count--;
+ CF_OBJC_KVO_DIDCHANGE(hc, hc->_keys[match]);
+#endif
+ } else {
+ CFAllocatorRef allocator = __CFGetAllocator(hc);
+ any_t oldKey = hc->_keys[match];
+ CF_OBJC_KVO_WILLCHANGE(hc, oldKey);
+ CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
+ CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], ~hc->_marker);
+#if CFDictionary
+ any_t oldValue = hc->_values[match];
+ CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
+ CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[match], 0);
+#endif
+#if CFBag
+ hc->_values[match] = 0;
+#endif
+ hc->_count--;
+ hc->_bucketsUsed--;
+ hc->_deletes++;
+ CF_OBJC_KVO_DIDCHANGE(hc, oldKey);
+ RELEASEKEY(oldKey);
+#if CFDictionary
+ RELEASEVALUE(oldValue);
+#endif
+ if (__CFSetShouldShrink(hc)) {
+ __CFSetGrow(hc, 0);
+ } else {
+ // When the probeskip == 1 always and only, a DELETED slot followed by an EMPTY slot
+ // can be converted to an EMPTY slot. By extension, a chain of DELETED slots followed
+ // by an EMPTY slot can be converted to EMPTY slots, which is what we do here.
+ if (match < hc->_bucketsNum - 1 && hc->_keys[match + 1] == hc->_marker) {
+ while (0 <= match && hc->_keys[match] == ~hc->_marker) {
+ hc->_keys[match] = hc->_marker;
+ hc->_deletes--;
+ match--;
+ }
+ }
+ }
+ }
+}
+
+void CFSetRemoveAllValues(CFMutableHashRef hc) {
+ if (CFDictionary) CF_OBJC_FUNCDISPATCH0(__kCFHashTypeID, void, hc, "removeAllObjects");
+ if (CFSet) CF_OBJC_FUNCDISPATCH0(__kCFHashTypeID, void, hc, "removeAllObjects");
+ __CFGenericValidateType(hc, __kCFHashTypeID);
+ switch (__CFHashGetType(hc)) {
+ case __kCFHashMutable:
+ break;
+ default:
+ CFAssert2(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
+ break;
+ }
+ hc->_mutations++;
+ if (0 == hc->_bucketsUsed) return;
+ CFAllocatorRef allocator = __CFGetAllocator(hc);
+ any_t *keys = hc->_keys;
+ for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
+ if (__CFHashKeyIsValue(hc, keys[idx])) {
+ any_t oldKey = keys[idx];
+ CF_OBJC_KVO_WILLCHANGE(hc, oldKey);
+#if CFDictionary || CFSet
+ hc->_count--;
+#endif
+#if CFBag
+ hc->_count -= hc->_values[idx];
+#endif
+ CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
+ CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[idx], ~hc->_marker);
+#if CFDictionary
+ any_t oldValue = hc->_values[idx];
+ CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
+ CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[idx], 0);
+#endif
+#if CFBag
+ hc->_values[idx] = 0;
+#endif
+ hc->_bucketsUsed--;
+ hc->_deletes++;
+ CF_OBJC_KVO_DIDCHANGE(hc, oldKey);
+ RELEASEKEY(oldKey);
+#if CFDictionary
+ RELEASEVALUE(oldValue);
+#endif
+ }
+ }
+ for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
+ keys[idx] = hc->_marker;
+ }
+ hc->_deletes = 0;
+ hc->_bucketsUsed = 0;
+ hc->_count = 0;
+ if (__CFSetShouldShrink(hc) && (256 <= hc->_bucketsCap)) {
+ __CFSetGrow(hc, 128);
+ }
+}
+
+#undef CF_OBJC_KVO_WILLCHANGE
+#undef CF_OBJC_KVO_DIDCHANGE
+
projects / apple / cf.git / blobdiff