-struct __CFSet {
- CFRuntimeBase _base;
- CFIndex _count; /* number of values */
- CFIndex _bucketsNum; /* number of buckets */
- CFIndex _bucketsUsed; /* number of used buckets */
- CFIndex _bucketsCap; /* maximum number of used buckets */
- CFIndex _mutations;
- CFIndex _deletes;
- any_pointer_t _context; /* private */
- CFOptionFlags _xflags;
- any_t _marker;
- any_t *_keys; /* can be NULL if not allocated yet */
- any_t *_values; /* can be NULL if not allocated yet */
-};
-
-/* Bits 1-0 of the _xflags are used for mutability variety */
-/* Bits 3-2 of the _xflags are used for key callback indicator bits */
-/* Bits 5-4 of the _xflags are used for value callback indicator bits */
-/* Bit 6 of the _xflags is special KVO actions bit */
-/* Bits 7,8,9 are GC use */
-
-CF_INLINE bool hasBeenFinalized(CFTypeRef collection) {
- return __CFBitfieldGetValue(((const struct __CFSet *)collection)->_xflags, 7, 7) != 0;
-}
-
-CF_INLINE void markFinalized(CFTypeRef collection) {
- __CFBitfieldSetValue(((struct __CFSet *)collection)->_xflags, 7, 7, 1);
-}
-
-
-CF_INLINE CFIndex __CFHashGetType(CFHashRef hc) {
- return __CFBitfieldGetValue(hc->_xflags, 1, 0);
-}
-
-CF_INLINE CFIndex __CFSetGetSizeOfType(CFIndex t) {
- CFIndex size = sizeof(struct __CFSet);
- if (__CFBitfieldGetValue(t, 3, 2) == __kCFHashHasCustomCallBacks) {
- size += sizeof(CFSetKeyCallBacks);
- }
- if (__CFBitfieldGetValue(t, 5, 4) == __kCFHashHasCustomCallBacks) {
- size += sizeof(CFSetValueCallBacks);
- }
- return size;
-}
-
-CF_INLINE const CFSetKeyCallBacks *__CFSetGetKeyCallBacks(CFHashRef hc) {
- CFSetKeyCallBacks *result = NULL;
- switch (__CFBitfieldGetValue(hc->_xflags, 3, 2)) {
- case __kCFHashHasNullCallBacks:
- return &__kCFNullSetKeyCallBacks;
- case __kCFHashHasCFTypeCallBacks:
- return &kCFTypeSetKeyCallBacks;
- case __kCFHashHasCustomCallBacks:
- break;
- }
- result = (CFSetKeyCallBacks *)((uint8_t *)hc + sizeof(struct __CFSet));
- return result;
-}
-
-CF_INLINE Boolean __CFSetKeyCallBacksMatchNull(const CFSetKeyCallBacks *c) {
- return (NULL == c ||
- (c->retain == __kCFNullSetKeyCallBacks.retain &&
- c->release == __kCFNullSetKeyCallBacks.release &&
- c->copyDescription == __kCFNullSetKeyCallBacks.copyDescription &&
- c->equal == __kCFNullSetKeyCallBacks.equal &&
- c->hash == __kCFNullSetKeyCallBacks.hash));
-}
-
-CF_INLINE Boolean __CFSetKeyCallBacksMatchCFType(const CFSetKeyCallBacks *c) {
- return (&kCFTypeSetKeyCallBacks == c ||
- (c->retain == kCFTypeSetKeyCallBacks.retain &&
- c->release == kCFTypeSetKeyCallBacks.release &&
- c->copyDescription == kCFTypeSetKeyCallBacks.copyDescription &&
- c->equal == kCFTypeSetKeyCallBacks.equal &&
- c->hash == kCFTypeSetKeyCallBacks.hash));
-}
-
-CF_INLINE const CFSetValueCallBacks *__CFSetGetValueCallBacks(CFHashRef hc) {
- CFSetValueCallBacks *result = NULL;
- switch (__CFBitfieldGetValue(hc->_xflags, 5, 4)) {
- case __kCFHashHasNullCallBacks:
- return &__kCFNullSetValueCallBacks;
- case __kCFHashHasCFTypeCallBacks:
- return &kCFTypeSetValueCallBacks;
- case __kCFHashHasCustomCallBacks:
- break;
- }
- if (__CFBitfieldGetValue(hc->_xflags, 3, 2) == __kCFHashHasCustomCallBacks) {
- result = (CFSetValueCallBacks *)((uint8_t *)hc + sizeof(struct __CFSet) + sizeof(CFSetKeyCallBacks));
- } else {
- result = (CFSetValueCallBacks *)((uint8_t *)hc + sizeof(struct __CFSet));
- }
- return result;
-}
-
-CF_INLINE Boolean __CFSetValueCallBacksMatchNull(const CFSetValueCallBacks *c) {
- return (NULL == c ||
- (c->retain == __kCFNullSetValueCallBacks.retain &&
- c->release == __kCFNullSetValueCallBacks.release &&
- c->copyDescription == __kCFNullSetValueCallBacks.copyDescription &&
- c->equal == __kCFNullSetValueCallBacks.equal));
-}
-
-CF_INLINE Boolean __CFSetValueCallBacksMatchCFType(const CFSetValueCallBacks *c) {
- return (&kCFTypeSetValueCallBacks == c ||
- (c->retain == kCFTypeSetValueCallBacks.retain &&
- c->release == kCFTypeSetValueCallBacks.release &&
- c->copyDescription == kCFTypeSetValueCallBacks.copyDescription &&
- c->equal == kCFTypeSetValueCallBacks.equal));
-}
-
-CFIndex _CFSetGetKVOBit(CFHashRef hc) {
- return __CFBitfieldGetValue(hc->_xflags, 6, 6);
-}
-
-void _CFSetSetKVOBit(CFHashRef hc, CFIndex bit) {
- __CFBitfieldSetValue(((CFMutableHashRef)hc)->_xflags, 6, 6, ((uintptr_t)bit & 0x1));
-}
-
-CF_INLINE Boolean __CFSetShouldShrink(CFHashRef hc) {
- return (__kCFHashMutable == __CFHashGetType(hc)) &&
- !(CF_USING_COLLECTABLE_MEMORY && auto_zone_is_finalized(__CFCollectableZone, hc)) && /* GC: don't shrink finalizing hcs! */
- (hc->_bucketsNum < 4 * hc->_deletes || (256 <= hc->_bucketsCap && hc-> _bucketsUsed < 3 * hc->_bucketsCap / 16));
-}
-
-CF_INLINE CFIndex __CFHashGetOccurrenceCount(CFHashRef hc, CFIndex idx) {
-#if CFBag
- return hc->_values[idx];
-#endif
- return 1;
-}
-
-CF_INLINE Boolean __CFHashKeyIsValue(CFHashRef hc, any_t key) {
- return (hc->_marker != key && ~hc->_marker != key) ? true : false;
-}
-
-CF_INLINE Boolean __CFHashKeyIsMagic(CFHashRef hc, any_t key) {
- return (hc->_marker == key || ~hc->_marker == key) ? true : false;
-}
-
-
-#if !defined(CF_OBJC_KVO_WILLCHANGE)
-#define CF_OBJC_KVO_WILLCHANGE(obj, key)
-#define CF_OBJC_KVO_DIDCHANGE(obj, key)
-#endif
-
-CF_INLINE uintptr_t __CFSetScrambleHash(uintptr_t k) {
-#if 0
- return k;
-#else
-#if __LP64__
- uintptr_t a = 0x4368726973746F70ULL;
- uintptr_t b = 0x686572204B616E65ULL;
-#else
- uintptr_t a = 0x4B616E65UL;
- uintptr_t b = 0x4B616E65UL;
-#endif
- uintptr_t c = 1;
- a += k;
-#if __LP64__
- a -= b; a -= c; a ^= (c >> 43);
- b -= c; b -= a; b ^= (a << 9);
- c -= a; c -= b; c ^= (b >> 8);
- a -= b; a -= c; a ^= (c >> 38);
- b -= c; b -= a; b ^= (a << 23);
- c -= a; c -= b; c ^= (b >> 5);
- a -= b; a -= c; a ^= (c >> 35);
- b -= c; b -= a; b ^= (a << 49);
- c -= a; c -= b; c ^= (b >> 11);
- a -= b; a -= c; a ^= (c >> 12);
- b -= c; b -= a; b ^= (a << 18);
- c -= a; c -= b; c ^= (b >> 22);
-#else
- a -= b; a -= c; a ^= (c >> 13);
- b -= c; b -= a; b ^= (a << 8);
- c -= a; c -= b; c ^= (b >> 13);
- a -= b; a -= c; a ^= (c >> 12);
- b -= c; b -= a; b ^= (a << 16);
- c -= a; c -= b; c ^= (b >> 5);
- a -= b; a -= c; a ^= (c >> 3);
- b -= c; b -= a; b ^= (a << 10);
- c -= a; c -= b; c ^= (b >> 15);
-#endif
- return c;
-#endif
-}
-
-static CFIndex __CFSetFindBuckets1a(CFHashRef hc, any_t key) {
- CFHashCode keyHash = (CFHashCode)key;
- keyHash = __CFSetScrambleHash(keyHash);
- any_t *keys = hc->_keys;
- any_t marker = hc->_marker;
- CFIndex probe = keyHash & (hc->_bucketsNum - 1);
- CFIndex probeskip = 1; // See RemoveValue() for notes before changing this value
- CFIndex start = probe;
- for (;;) {
- any_t currKey = keys[probe];
- if (marker == currKey) { /* empty */
- return kCFNotFound;
- } else if (~marker == currKey) { /* deleted */
- /* do nothing */
- } else if (currKey == key) {
- return probe;
- }
- probe = probe + probeskip;
- // This alternative to probe % buckets assumes that
- // probeskip is always positive and less than the
- // number of buckets.
- if (hc->_bucketsNum <= probe) {
- probe -= hc->_bucketsNum;
- }
- if (start == probe) {
- return kCFNotFound;
- }
- }
-}
-
-static CFIndex __CFSetFindBuckets1b(CFHashRef hc, any_t key) {
- const CFSetKeyCallBacks *cb = __CFSetGetKeyCallBacks(hc);
- CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(any_t, any_pointer_t))cb->hash), key, hc->_context) : (CFHashCode)key;
- keyHash = __CFSetScrambleHash(keyHash);
- any_t *keys = hc->_keys;
- any_t marker = hc->_marker;
- CFIndex probe = keyHash & (hc->_bucketsNum - 1);
- CFIndex probeskip = 1; // See RemoveValue() for notes before changing this value
- CFIndex start = probe;
- for (;;) {
- any_t currKey = keys[probe];
- if (marker == currKey) { /* empty */
- return kCFNotFound;
- } else if (~marker == currKey) { /* deleted */
- /* do nothing */
- } else if (currKey == key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(any_t, any_t, any_pointer_t))cb->equal, currKey, key, hc->_context))) {
- return probe;
- }
- probe = probe + probeskip;
- // This alternative to probe % buckets assumes that
- // probeskip is always positive and less than the
- // number of buckets.
- if (hc->_bucketsNum <= probe) {
- probe -= hc->_bucketsNum;
- }
- if (start == probe) {
- return kCFNotFound;
- }
- }
-}
-
-CF_INLINE CFIndex __CFSetFindBuckets1(CFHashRef hc, any_t key) {
- if (__kCFHashHasNullCallBacks == __CFBitfieldGetValue(hc->_xflags, 3, 2)) {
- return __CFSetFindBuckets1a(hc, key);
- }
- return __CFSetFindBuckets1b(hc, key);
-}
-
-static void __CFSetFindBuckets2(CFHashRef hc, any_t key, CFIndex *match, CFIndex *nomatch) {
- const CFSetKeyCallBacks *cb = __CFSetGetKeyCallBacks(hc);
- CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(any_t, any_pointer_t))cb->hash), key, hc->_context) : (CFHashCode)key;
- keyHash = __CFSetScrambleHash(keyHash);
- any_t *keys = hc->_keys;
- any_t marker = hc->_marker;
- CFIndex probe = keyHash & (hc->_bucketsNum - 1);
- CFIndex probeskip = 1; // See RemoveValue() for notes before changing this value
- CFIndex start = probe;
- *match = kCFNotFound;
- *nomatch = kCFNotFound;
- for (;;) {
- any_t currKey = keys[probe];
- if (marker == currKey) { /* empty */
- if (nomatch) *nomatch = probe;
- return;
- } else if (~marker == currKey) { /* deleted */
- if (nomatch) {
- *nomatch = probe;
- nomatch = NULL;
- }
- } else if (currKey == key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(any_t, any_t, any_pointer_t))cb->equal, currKey, key, hc->_context))) {
- *match = probe;
- return;
- }
- probe = probe + probeskip;
- // This alternative to probe % buckets assumes that
- // probeskip is always positive and less than the
- // number of buckets.
- if (hc->_bucketsNum <= probe) {
- probe -= hc->_bucketsNum;
- }
- if (start == probe) {
- return;
- }
- }
-}
-
-static void __CFSetFindNewMarker(CFHashRef hc) {
- any_t *keys = hc->_keys;
- any_t newMarker;
- CFIndex idx, nbuckets;
- Boolean hit;
-
- nbuckets = hc->_bucketsNum;
- newMarker = hc->_marker;
- do {
- newMarker--;
- hit = false;
- for (idx = 0; idx < nbuckets; idx++) {
- if (newMarker == keys[idx] || ~newMarker == keys[idx]) {
- hit = true;
- break;
- }
- }
- } while (hit);
- for (idx = 0; idx < nbuckets; idx++) {
- if (hc->_marker == keys[idx]) {
- keys[idx] = newMarker;
- } else if (~hc->_marker == keys[idx]) {
- keys[idx] = ~newMarker;
- }
- }
- ((struct __CFSet *)hc)->_marker = newMarker;
-}
-
projects / apple / cf.git / blobdiff