Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Branch: master
Fetching contributors…

Cannot retrieve contributors at this time

1486 lines (1387 sloc) 60.06 kB
/*
* 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);
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
}
}
}
}
// 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
Jump to Line
Something went wrong with that request. Please try again.