#include <CoreFoundation/CFSet.h>
#include "CFInternal.h"
const CFSetCallBacks kCFTypeSetCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
const CFSetCallBacks kCFCopyStringSetCallBacks = {0, (void *)CFStringCreateCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
static const CFSetCallBacks __kCFNullSetCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
static const uint32_t __CFSetCapacities[42] = {
4, 8, 17, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349,
15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498,
3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324,
228826127, 370248451, 599074578, 969323029, 1568397607, 2537720636U
};
static const uint32_t __CFSetBuckets[42] = { 5, 11, 23, 41, 67, 113, 199, 317, 521, 839, 1361, 2207, 3571, 5779, 9349, 15121,
24473, 39607, 64081, 103681, 167759, 271429, 439199, 710641, 1149857, 1860503, 3010349,
4870843, 7881193, 12752029, 20633237, 33385273, 54018521, 87403763, 141422317, 228826121,
370248451, 599074561, 969323023, 1568397599, 2537720629U, 4106118251U
};
CF_INLINE CFIndex __CFSetRoundUpCapacity(CFIndex capacity) {
CFIndex idx;
for (idx = 0; idx < 42 && __CFSetCapacities[idx] < (uint32_t)capacity; idx++);
if (42 <= idx) HALT;
return __CFSetCapacities[idx];
}
CF_INLINE CFIndex __CFSetNumBucketsForCapacity(CFIndex capacity) {
CFIndex idx;
for (idx = 0; idx < 42 && __CFSetCapacities[idx] < (uint32_t)capacity; idx++);
if (42 <= idx) HALT;
return __CFSetBuckets[idx];
}
enum {
__kCFSetImmutable = 0,
__kCFSetMutable = 1,
__kCFSetFixedMutable = 3
};
enum {
__kCFSetHasNullCallBacks = 0,
__kCFSetHasCFTypeCallBacks = 1,
__kCFSetHasCustomCallBacks = 3
};
struct __CFSetBucket {
const void *_key;
};
struct __CFSet {
CFRuntimeBase _base;
CFIndex _count;
CFIndex _capacity;
CFIndex _bucketsUsed;
CFIndex _bucketsNum;
const void *_emptyMarker;
const void *_deletedMarker;
void *_context;
struct __CFSetBucket *_buckets;
};
CF_INLINE bool __CFSetBucketIsEmpty(CFSetRef set, const struct __CFSetBucket *bucket) {
return (set->_emptyMarker == bucket->_key);
}
CF_INLINE bool __CFSetBucketIsDeleted(CFSetRef set, const struct __CFSetBucket *bucket) {
return (set->_deletedMarker == bucket->_key);
}
CF_INLINE bool __CFSetBucketIsOccupied(CFSetRef set, const struct __CFSetBucket *bucket) {
return (set->_emptyMarker != bucket->_key && set->_deletedMarker != bucket->_key);
}
CF_INLINE CFIndex __CFSetGetType(CFSetRef set) {
return __CFBitfieldGetValue(((const CFRuntimeBase *)set)->_info, 1, 0);
}
CF_INLINE CFIndex __CFSetGetSizeOfType(CFIndex t) {
CFIndex size = sizeof(struct __CFSet);
if (__CFBitfieldGetValue(t, 3, 2) == __kCFSetHasCustomCallBacks) {
size += sizeof(CFSetCallBacks);
}
return size;
}
CF_INLINE const CFSetCallBacks *__CFSetGetCallBacks(CFSetRef set) {
CFSetCallBacks *result = NULL;
switch (__CFBitfieldGetValue(((const CFRuntimeBase *)set)->_info, 3, 2)) {
case __kCFSetHasNullCallBacks:
return &__kCFNullSetCallBacks;
case __kCFSetHasCFTypeCallBacks:
return &kCFTypeSetCallBacks;
case __kCFSetHasCustomCallBacks:
break;
}
result = (CFSetCallBacks *)((uint8_t *)set + sizeof(struct __CFSet));
return result;
}
CF_INLINE bool __CFSetCallBacksMatchNull(const CFSetCallBacks *c) {
return (NULL == c ||
(c->retain == __kCFNullSetCallBacks.retain &&
c->release == __kCFNullSetCallBacks.release &&
c->copyDescription == __kCFNullSetCallBacks.copyDescription &&
c->equal == __kCFNullSetCallBacks.equal &&
c->hash == __kCFNullSetCallBacks.hash));
}
CF_INLINE bool __CFSetCallBacksMatchCFType(const CFSetCallBacks *c) {
return (&kCFTypeSetCallBacks == c ||
(c->retain == kCFTypeSetCallBacks.retain &&
c->release == kCFTypeSetCallBacks.release &&
c->copyDescription == kCFTypeSetCallBacks.copyDescription &&
c->equal == kCFTypeSetCallBacks.equal &&
c->hash == kCFTypeSetCallBacks.hash));
}
static void __CFSetFindBuckets1(CFSetRef set, const void *key, struct __CFSetBucket **match) {
const CFSetCallBacks *cb = __CFSetGetCallBacks(set);
struct __CFSetBucket *buckets = set->_buckets;
CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, set->_context) : (CFHashCode)key;
UInt32 start = keyHash % set->_bucketsNum;
UInt32 probe = start;
UInt32 probeskip = 1;
*match = NULL;
for (;;) {
struct __CFSetBucket *currentBucket = buckets + probe;
if (__CFSetBucketIsEmpty(set, currentBucket)) {
return;
} else if (__CFSetBucketIsDeleted(set, currentBucket)) {
} else if (currentBucket->_key == key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(void *, void *, void*))cb->equal, currentBucket->_key, key, set->_context))) {
*match = currentBucket;
return;
}
probe = (probe + probeskip) % set->_bucketsNum;
if (start == probe) return;
}
}
static void __CFSetFindBuckets2(CFSetRef set, const void *key, struct __CFSetBucket **match, struct __CFSetBucket **nomatch) {
const CFSetCallBacks *cb = __CFSetGetCallBacks(set);
struct __CFSetBucket *buckets = set->_buckets;
CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, set->_context) : (CFHashCode)key;
UInt32 start = keyHash % set->_bucketsNum;
UInt32 probe = start;
UInt32 probeskip = 1;
*match = NULL;
*nomatch = NULL;
for (;;) {
struct __CFSetBucket *currentBucket = buckets + probe;
if (__CFSetBucketIsEmpty(set, currentBucket)) {
if (!*nomatch) *nomatch = currentBucket;
return;
} else if (__CFSetBucketIsDeleted(set, currentBucket)) {
if (!*nomatch) *nomatch = currentBucket;
} else if (!*match && (currentBucket->_key == key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(void *, void *, void*))cb->equal, currentBucket->_key, key, set->_context)))) {
*match = currentBucket;
if (*nomatch) return;
}
probe = (probe + probeskip) % set->_bucketsNum;
if (start == probe) return;
}
}
static void __CFSetFindNewEmptyMarker(CFSetRef set) {
struct __CFSetBucket *buckets;
const void *newEmpty;
bool hit;
CFIndex idx, nbuckets;
buckets = set->_buckets;
nbuckets = set->_bucketsNum;
newEmpty = set->_emptyMarker;
do {
(intptr_t)newEmpty -= 2;
hit = false;
for (idx = 0; idx < nbuckets; idx++) {
if (newEmpty == buckets[idx]._key) {
hit = true;
break;
}
}
} while (hit);
for (idx = 0; idx < nbuckets; idx++) {
if (set->_emptyMarker == buckets[idx]._key) {
buckets[idx]._key = newEmpty;
}
}
((struct __CFSet *)set)->_emptyMarker = newEmpty;
}
static void __CFSetFindNewDeletedMarker(CFSetRef set) {
struct __CFSetBucket *buckets;
const void *newDeleted;
bool hit;
CFIndex idx, nbuckets;
buckets = set->_buckets;
nbuckets = set->_bucketsNum;
newDeleted = set->_deletedMarker;
do {
(intptr_t)newDeleted += 2;
hit = false;
for (idx = 0; idx < nbuckets; idx++) {
if (newDeleted == buckets[idx]._key) {
hit = true;
break;
}
}
} while (hit);
for (idx = 0; idx < nbuckets; idx++) {
if (set->_deletedMarker == buckets[idx]._key) {
buckets[idx]._key = newDeleted;
}
}
((struct __CFSet *)set)->_deletedMarker = newDeleted;
}
static bool __CFSetEqual(CFTypeRef cf1, CFTypeRef cf2) {
CFSetRef set1 = (CFSetRef)cf1;
CFSetRef set2 = (CFSetRef)cf2;
const CFSetCallBacks *cb1, *cb2;
const struct __CFSetBucket *buckets;
CFIndex idx, nbuckets;
if (set1 == set2) return true;
if (set1->_count != set2->_count) return false;
cb1 = __CFSetGetCallBacks(set1);
cb2 = __CFSetGetCallBacks(set2);
if (cb1->equal != cb2->equal) return false;
if (0 == set1->_count) return true;
buckets = set1->_buckets;
nbuckets = set1->_bucketsNum;
for (idx = 0; idx < nbuckets; idx++) {
if (__CFSetBucketIsOccupied(set1, &buckets[idx])) {
if (1 != CFSetGetCountOfValue(set2, buckets[idx]._key)) {
return false;
}
}
}
return true;
}
static CFHashCode __CFSetHash(CFTypeRef cf) {
CFSetRef set = (CFSetRef)cf;
return set->_count;
}
static CFStringRef __CFSetCopyDescription(CFTypeRef cf) {
CFSetRef set = (CFSetRef)cf;
const CFSetCallBacks *cb;
const struct __CFSetBucket *buckets;
CFIndex idx, nbuckets;
CFMutableStringRef result;
cb = __CFSetGetCallBacks(set);
buckets = set->_buckets;
nbuckets = set->_bucketsNum;
result = CFStringCreateMutable(kCFAllocatorSystemDefault, 0);
CFStringAppendFormat(result, NULL, CFSTR("<CFSet %p [%p]>{count = %u, capacity = %u, values = (\n"), set, CFGetAllocator(set), set->_count, set->_capacity);
for (idx = 0; idx < nbuckets; idx++) {
if (__CFSetBucketIsOccupied(set, &buckets[idx])) {
CFStringRef desc = NULL;
if (NULL != cb->copyDescription) {
desc = (CFStringRef)INVOKE_CALLBACK2(((CFStringRef (*)(const void *, void *))cb->copyDescription), buckets[idx]._key, set->_context);
}
if (NULL != desc) {
CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@\n"), idx, desc, NULL);
CFRelease(desc);
} else {
CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p>\n"), idx, buckets[idx]._key, NULL);
}
}
}
CFStringAppend(result, CFSTR(")}"));
return result;
}
static void __CFSetDeallocate(CFTypeRef cf) {
CFMutableSetRef set = (CFMutableSetRef)cf;
CFAllocatorRef allocator = __CFGetAllocator(set);
if (__CFSetGetType(set) == __kCFSetImmutable) {
__CFBitfieldSetValue(((CFRuntimeBase *)set)->_info, 1, 0, __kCFSetFixedMutable);
}
CFSetRemoveAllValues(set);
if (__CFSetGetType(set) == __kCFSetMutable && set->_buckets) {
CFAllocatorDeallocate(allocator, set->_buckets);
}
}
static CFTypeID __kCFSetTypeID = _kCFRuntimeNotATypeID;
static const CFRuntimeClass __CFSetClass = {
0,
"CFSet",
NULL, NULL, __CFSetDeallocate,
(void *)__CFSetEqual,
__CFSetHash,
NULL, __CFSetCopyDescription
};
__private_extern__ void __CFSetInitialize(void) {
__kCFSetTypeID = _CFRuntimeRegisterClass(&__CFSetClass);
}
CFTypeID CFSetGetTypeID(void) {
return __kCFSetTypeID;
}
static CFSetRef __CFSetInit(CFAllocatorRef allocator, UInt32 flags, CFIndex capacity, const CFSetCallBacks *callBacks) {
struct __CFSet *memory;
UInt32 size;
CFIndex idx;
__CFBitfieldSetValue(flags, 31, 2, 0);
if (__CFSetCallBacksMatchNull(callBacks)) {
__CFBitfieldSetValue(flags, 3, 2, __kCFSetHasNullCallBacks);
} else if (__CFSetCallBacksMatchCFType(callBacks)) {
__CFBitfieldSetValue(flags, 3, 2, __kCFSetHasCFTypeCallBacks);
} else {
__CFBitfieldSetValue(flags, 3, 2, __kCFSetHasCustomCallBacks);
}
size = __CFSetGetSizeOfType(flags) - sizeof(CFRuntimeBase);
switch (__CFBitfieldGetValue(flags, 1, 0)) {
case __kCFSetImmutable:
case __kCFSetFixedMutable:
size += __CFSetNumBucketsForCapacity(capacity) * sizeof(struct __CFSetBucket);
break;
case __kCFSetMutable:
break;
}
memory = (struct __CFSet *)_CFRuntimeCreateInstance(allocator, __kCFSetTypeID, size, NULL);
if (NULL == memory) {
return NULL;
}
__CFBitfieldSetValue(memory->_base._info, 6, 0, flags);
memory->_count = 0;
memory->_bucketsUsed = 0;
memory->_emptyMarker = (const void *)0xa1b1c1d3;
memory->_deletedMarker = (const void *)0xa1b1c1d5;
memory->_context = NULL;
switch (__CFBitfieldGetValue(flags, 1, 0)) {
case __kCFSetImmutable:
if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFSet (immutable)");
memory->_capacity = capacity;
memory->_bucketsNum = __CFSetNumBucketsForCapacity(memory->_capacity);
memory->_buckets = (struct __CFSetBucket *)((uint8_t *)memory + __CFSetGetSizeOfType(flags));
for (idx = memory->_bucketsNum; idx--;) {
memory->_buckets[idx]._key = memory->_emptyMarker;
}
break;
case __kCFSetFixedMutable:
if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFSet (mutable-fixed)");
memory->_capacity = capacity;
memory->_bucketsNum = __CFSetNumBucketsForCapacity(memory->_capacity);
memory->_buckets = (struct __CFSetBucket *)((uint8_t *)memory + __CFSetGetSizeOfType(flags));
for (idx = memory->_bucketsNum; idx--;) {
memory->_buckets[idx]._key = memory->_emptyMarker;
}
break;
case __kCFSetMutable:
if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFSet (mutable-variable)");
memory->_capacity = __CFSetRoundUpCapacity(1);
memory->_bucketsNum = 0;
memory->_buckets = NULL;
break;
}
if (__kCFSetHasCustomCallBacks == __CFBitfieldGetValue(flags, 3, 2)) {
const CFSetCallBacks *cb = __CFSetGetCallBacks((CFSetRef)memory);
*(CFSetCallBacks *)cb = *callBacks;
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));
}
return (CFSetRef)memory;
}
CFSetRef CFSetCreate(CFAllocatorRef allocator, const void **values, CFIndex numValues, const CFSetCallBacks *callBacks) {
CFSetRef result;
UInt32 flags;
CFIndex idx;
CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
result = __CFSetInit(allocator, __kCFSetImmutable, numValues, callBacks);
flags = __CFBitfieldGetValue(((const CFRuntimeBase *)result)->_info, 1, 0);
if (flags == __kCFSetImmutable) {
__CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, __kCFSetFixedMutable);
}
for (idx = 0; idx < numValues; idx++) {
CFSetAddValue((CFMutableSetRef)result, values[idx]);
}
__CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, flags);
return result;
}
CFMutableSetRef CFSetCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFSetCallBacks *callBacks) {
CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
return (CFMutableSetRef)__CFSetInit(allocator, (0 == capacity) ? __kCFSetMutable : __kCFSetFixedMutable, capacity, callBacks);
}
CFSetRef CFSetCreateCopy(CFAllocatorRef allocator, CFSetRef set) {
CFSetRef result;
const CFSetCallBacks *cb;
CFIndex numValues = CFSetGetCount(set);
const void **list, *buffer[256];
list = (numValues <= 256) ? buffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0);
if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFSet (temp)");
CFSetGetValues(set, list);
cb = CF_IS_OBJC(__kCFSetTypeID, set) ? &kCFTypeSetCallBacks : __CFSetGetCallBacks(set);
result = CFSetCreate(allocator, list, numValues, cb);
if (list != buffer) CFAllocatorDeallocate(allocator, list);
return result;
}
CFMutableSetRef CFSetCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFSetRef set) {
CFMutableSetRef result;
const CFSetCallBacks *cb;
CFIndex idx, numValues = CFSetGetCount(set);
const void **list, *buffer[256];
CFAssert3(0 == capacity || numValues <= capacity, __kCFLogAssertion, "%s(): for fixed-mutable sets, capacity (%d) must be greater than or equal to initial number of values (%d)", __PRETTY_FUNCTION__, capacity, numValues);
list = (numValues <= 256) ? buffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0);
if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFSet (temp)");
CFSetGetValues(set, list);
cb = CF_IS_OBJC(__kCFSetTypeID, set) ? &kCFTypeSetCallBacks : __CFSetGetCallBacks(set);
result = CFSetCreateMutable(allocator, capacity, cb);
if (0 == capacity) _CFSetSetCapacity(result, numValues);
for (idx = 0; idx < numValues; idx++) {
CFSetAddValue(result, list[idx]);
}
if (list != buffer) CFAllocatorDeallocate(allocator, list);
return result;
}
void _CFSetSetContext(CFSetRef set, void *context) {
((struct __CFSet *)set)->_context = context;
}
CFIndex CFSetGetCount(CFSetRef set) {
CF_OBJC_FUNCDISPATCH0(__kCFSetTypeID, CFIndex, set, "count");
__CFGenericValidateType(set, __kCFSetTypeID);
return set->_count;
}
CFIndex CFSetGetCountOfValue(CFSetRef set, const void *value) {
struct __CFSetBucket *match;
CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, CFIndex, set, "countForObject:", value);
__CFGenericValidateType(set, __kCFSetTypeID);
if (0 == set->_count) return 0;
__CFSetFindBuckets1(set, value, &match);
return (match ? 1 : 0);
}
Boolean CFSetContainsValue(CFSetRef set, const void *value) {
struct __CFSetBucket *match;
CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, char, set, "containsObject:", value);
__CFGenericValidateType(set, __kCFSetTypeID);
if (0 == set->_count) return false;
__CFSetFindBuckets1(set, value, &match);
return (match ? true : false);
}
const void *CFSetGetValue(CFSetRef set, const void *value) {
struct __CFSetBucket *match;
CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, const void *, set, "member:", value);
__CFGenericValidateType(set, __kCFSetTypeID);
if (0 == set->_count) return NULL;
__CFSetFindBuckets1(set, value, &match);
return (match ? match->_key : NULL);
}
Boolean CFSetGetValueIfPresent(CFSetRef set, const void *candidate, const void **value) {
struct __CFSetBucket *match;
CF_OBJC_FUNCDISPATCH2(__kCFSetTypeID, char, set, "_getValue:forObj:", (void * *)value, candidate);
__CFGenericValidateType(set, __kCFSetTypeID);
if (0 == set->_count) return false;
__CFSetFindBuckets1(set, candidate, &match);
return (match ? ((value ? *value = match->_key : NULL), true) : false);
}
void CFSetGetValues(CFSetRef set, const void **values) {
struct __CFSetBucket *buckets;
CFIndex idx, cnt, nbuckets;
CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, set, "getObjects:", (void * *)values);
__CFGenericValidateType(set, __kCFSetTypeID);
buckets = set->_buckets;
nbuckets = set->_bucketsNum;
for (idx = 0; idx < nbuckets; idx++) {
if (__CFSetBucketIsOccupied(set, &buckets[idx])) {
for (cnt = 1; cnt--;) {
if (values) *values++ = buckets[idx]._key;
}
}
}
}
void CFSetApplyFunction(CFSetRef set, CFSetApplierFunction applier, void *context) {
struct __CFSetBucket *buckets;
CFIndex idx, cnt, nbuckets;
FAULT_CALLBACK((void **)&(applier));
CF_OBJC_FUNCDISPATCH2(__kCFSetTypeID, void, set, "_applyValues:context:", applier, context);
__CFGenericValidateType(set, __kCFSetTypeID);
buckets = set->_buckets;
nbuckets = set->_bucketsNum;
for (idx = 0; idx < nbuckets; idx++) {
if (__CFSetBucketIsOccupied(set, &buckets[idx])) {
for (cnt = 1; cnt--;) {
INVOKE_CALLBACK2(applier, buckets[idx]._key, context);
}
}
}
}
static void __CFSetGrow(CFMutableSetRef set, CFIndex numNewValues) {
struct __CFSetBucket *oldbuckets = set->_buckets;
CFIndex idx, oldnbuckets = set->_bucketsNum;
CFIndex oldCount = set->_count;
set->_capacity = __CFSetRoundUpCapacity(oldCount + numNewValues);
set->_bucketsNum = __CFSetNumBucketsForCapacity(set->_capacity);
set->_buckets = CFAllocatorAllocate(__CFGetAllocator(set), set->_bucketsNum * sizeof(struct __CFSetBucket), 0);
if (NULL == set->_buckets) HALT;
if (__CFOASafe) __CFSetLastAllocationEventName(set->_buckets, "CFSet (store)");
for (idx = set->_bucketsNum; idx--;) {
set->_buckets[idx]._key = set->_emptyMarker;
}
if (NULL == oldbuckets) return;
for (idx = 0; idx < oldnbuckets; idx++) {
if (__CFSetBucketIsOccupied(set, &oldbuckets[idx])) {
struct __CFSetBucket *match, *nomatch;
__CFSetFindBuckets2(set, oldbuckets[idx]._key, &match, &nomatch);
CFAssert3(!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__, oldbuckets[idx]._key, match->_key);
nomatch->_key = oldbuckets[idx]._key;
}
}
CFAssert1(set->_count == oldCount, __kCFLogAssertion, "%s(): set count differs after rehashing; error", __PRETTY_FUNCTION__);
CFAllocatorDeallocate(__CFGetAllocator(set), oldbuckets);
}
void _CFSetSetCapacity(CFMutableSetRef set, CFIndex cap) {
if (CF_IS_OBJC(__kCFSetTypeID, set)) return;
#if defined(DEBUG)
__CFGenericValidateType(set, __kCFSetTypeID);
CFAssert1(__CFSetGetType(set) != __kCFSetImmutable && __CFSetGetType(set) != __kCFSetFixedMutable, __kCFLogAssertion, "%s(): set is immutable or fixed-mutable", __PRETTY_FUNCTION__);
CFAssert3(set->_count <= cap, __kCFLogAssertion, "%s(): desired capacity (%d) is less than count (%d)", __PRETTY_FUNCTION__, cap, set->_count);
#endif
__CFSetGrow(set, cap - set->_count);
}
bool _CFSetIsMutable(CFSetRef set) {
return (__CFSetGetType(set) != __kCFSetImmutable);
}
void CFSetAddValue(CFMutableSetRef set, const void *value) {
struct __CFSetBucket *match, *nomatch;
const CFSetCallBacks *cb;
const void *newValue;
CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, set, "addObject:", value);
__CFGenericValidateType(set, __kCFSetTypeID);
switch (__CFSetGetType(set)) {
case __kCFSetMutable:
if (set->_bucketsUsed == set->_capacity || NULL == set->_buckets) {
__CFSetGrow(set, 1);
}
break;
case __kCFSetFixedMutable:
CFAssert3(set->_count < set->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity set %p (capacity = %d)", __PRETTY_FUNCTION__, set, set->_capacity);
break;
default:
CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
break;
}
__CFSetFindBuckets2(set, value, &match, &nomatch);
if (match) {
} else {
cb = __CFSetGetCallBacks(set);
if (cb->retain) {
newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), __CFGetAllocator(set), value, set->_context);
} else {
newValue = value;
}
if (set->_emptyMarker == newValue) {
__CFSetFindNewEmptyMarker(set);
}
if (set->_deletedMarker == newValue) {
__CFSetFindNewDeletedMarker(set);
}
nomatch->_key = newValue;
set->_bucketsUsed++;
set->_count++;
}
}
__private_extern__ const void *__CFSetAddValueAndReturn(CFMutableSetRef set, const void *value) {
struct __CFSetBucket *match, *nomatch;
const CFSetCallBacks *cb;
const void *newValue;
__CFGenericValidateType(set, __kCFSetTypeID);
switch (__CFSetGetType(set)) {
case __kCFSetMutable:
if (set->_bucketsUsed == set->_capacity || NULL == set->_buckets) {
__CFSetGrow(set, 1);
}
break;
case __kCFSetFixedMutable:
CFAssert3(set->_count < set->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity set %p (capacity = %d)", __PRETTY_FUNCTION__, set, set->_capacity);
break;
default:
CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
break;
}
__CFSetFindBuckets2(set, value, &match, &nomatch);
if (match) {
return match->_key;
} else {
cb = __CFSetGetCallBacks(set);
if (cb->retain) {
newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), __CFGetAllocator(set), value, set->_context);
} else {
newValue = value;
}
if (set->_emptyMarker == newValue) {
__CFSetFindNewEmptyMarker(set);
}
if (set->_deletedMarker == newValue) {
__CFSetFindNewDeletedMarker(set);
}
nomatch->_key = newValue;
set->_bucketsUsed++;
set->_count++;
return newValue;
}
}
void CFSetReplaceValue(CFMutableSetRef set, const void *value) {
struct __CFSetBucket *match;
const CFSetCallBacks *cb;
const void *newValue;
CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, set, "_replaceObject:", value);
__CFGenericValidateType(set, __kCFSetTypeID);
switch (__CFSetGetType(set)) {
case __kCFSetMutable:
case __kCFSetFixedMutable:
break;
default:
CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
break;
}
if (0 == set->_count) return;
__CFSetFindBuckets1(set, value, &match);
if (!match) return;
cb = __CFSetGetCallBacks(set);
if (cb->retain) {
newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), __CFGetAllocator(set), value, set->_context);
} else {
newValue = value;
}
if (cb->release) {
INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), __CFGetAllocator(set), match->_key, set->_context);
match->_key = set->_deletedMarker;
}
if (set->_emptyMarker == newValue) {
__CFSetFindNewEmptyMarker(set);
}
if (set->_deletedMarker == newValue) {
__CFSetFindNewDeletedMarker(set);
}
match->_key = newValue;
}
void CFSetSetValue(CFMutableSetRef set, const void *value) {
struct __CFSetBucket *match, *nomatch;
const CFSetCallBacks *cb;
const void *newValue;
CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, set, "_setObject:", value);
__CFGenericValidateType(set, __kCFSetTypeID);
switch (__CFSetGetType(set)) {
case __kCFSetMutable:
if (set->_bucketsUsed == set->_capacity || NULL == set->_buckets) {
__CFSetGrow(set, 1);
}
break;
case __kCFSetFixedMutable:
break;
default:
CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
break;
}
__CFSetFindBuckets2(set, value, &match, &nomatch);
cb = __CFSetGetCallBacks(set);
if (cb->retain) {
newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), __CFGetAllocator(set), value, set->_context);
} else {
newValue = value;
}
if (match) {
if (cb->release) {
INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), __CFGetAllocator(set), match->_key, set->_context);
match->_key = set->_deletedMarker;
}
if (set->_emptyMarker == newValue) {
__CFSetFindNewEmptyMarker(set);
}
if (set->_deletedMarker == newValue) {
__CFSetFindNewDeletedMarker(set);
}
match->_key = newValue;
} else {
CFAssert3(__kCFSetFixedMutable != __CFSetGetType(set) || set->_count < set->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity set %p (capacity = %d)", __PRETTY_FUNCTION__, set, set->_capacity);
if (set->_emptyMarker == newValue) {
__CFSetFindNewEmptyMarker(set);
}
if (set->_deletedMarker == newValue) {
__CFSetFindNewDeletedMarker(set);
}
nomatch->_key = newValue;
set->_bucketsUsed++;
set->_count++;
}
}
void CFSetRemoveValue(CFMutableSetRef set, const void *value) {
struct __CFSetBucket *match;
const CFSetCallBacks *cb;
CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, set, "removeObject:", value);
__CFGenericValidateType(set, __kCFSetTypeID);
switch (__CFSetGetType(set)) {
case __kCFSetMutable:
case __kCFSetFixedMutable:
break;
default:
CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
break;
}
if (0 == set->_count) return;
__CFSetFindBuckets1(set, value, &match);
if (!match) return;
set->_count--;
if (1) {
cb = __CFSetGetCallBacks(set);
if (cb->release) {
INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), __CFGetAllocator(set), match->_key, set->_context);
}
match->_key = set->_deletedMarker;
set->_bucketsUsed--;
}
}
void CFSetRemoveAllValues(CFMutableSetRef set) {
struct __CFSetBucket *buckets;
const CFSetCallBacks *cb;
CFAllocatorRef allocator;
CFIndex idx, nbuckets;
CF_OBJC_FUNCDISPATCH0(__kCFSetTypeID, void, set, "removeAllObjects");
__CFGenericValidateType(set, __kCFSetTypeID);
switch (__CFSetGetType(set)) {
case __kCFSetMutable:
case __kCFSetFixedMutable:
break;
default:
CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
break;
}
if (0 == set->_count) return;
buckets = set->_buckets;
nbuckets = set->_bucketsNum;
cb = __CFSetGetCallBacks(set);
allocator = __CFGetAllocator(set);
for (idx = 0; idx < nbuckets; idx++) {
if (__CFSetBucketIsOccupied(set, &buckets[idx])) {
if (cb->release) {
INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), allocator, buckets[idx]._key, set->_context);
}
buckets[idx]._key = set->_emptyMarker;
}
}
set->_bucketsUsed = 0;
set->_count = 0;
}