| /* |
| * Copyright (c) 2008-2009 Brent Fulgham <bfulgham@gmail.org>. All rights reserved. |
| * |
| * This source code is a modified version of the CoreFoundation sources released by Apple Inc. under |
| * the terms of the APSL version 2.0 (see below). |
| * |
| * For information about changes from the original Apple source release can be found by reviewing the |
| * source control system for the project at https://sourceforge.net/svn/?group_id=246198. |
| * |
| * The original license information is as follows: |
| * |
| * 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" |
| #if DEPLOYMENT_TARGET_MACOSX |
| #include <mach-o/dyld.h> |
| #endif |
| |
| #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 = (CFHashCode)__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 = (CFHashCode)__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 = (CFHashCode)__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); |
| for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) { |
| if (__CFHashKeyIsValue(hc, hc->_keys[idx])) { |
| for (CFIndex cnt = __CFHashGetOccurrenceCount(hc, idx); cnt--;) { |
| #if CFDictionary |
| INVOKE_CALLBACK3(applier, (const_any_pointer_t)hc->_keys[idx], (const_any_pointer_t)hc->_values[idx], context); |
| #endif |
| #if CFSet || CFBag |
| INVOKE_CALLBACK2(applier, (const_any_pointer_t)hc->_keys[idx], context); |
| #endif |
| } |
| } |
| } |
| } |
| |
| |
| // This function is for Foundation's benefit; no one else should use it. |
| bool _CFSetIsMutable(CFSetRef set) { |
| return (__CFHashGetType(set) != __kCFHashImmutable); |
| } |
| |
| 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 |
| |
