]> git.saurik.com Git - apple/cf.git/blame - CFSet.c
projects / apple / cf.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
CF-476.10.tar.gz
[apple/cf.git] / CFSet.c
CommitLineData
bd5b749c
A		 1/*
2 * Copyright (c) 2008 Apple Inc. All rights reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
11 * file.
12 *
13 * The Original Code and all software distributed under the License are
14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 */
23/* CFSet.c
24 Copyright 1998-2006, Apple, Inc. All rights reserved.
25 Responsibility: Christopher Kane
26 Machine generated from Notes/HashingCode.template
27*/
28
29
30
31
32#include <CoreFoundation/CFSet.h>
33#include "CFInternal.h"
34#include <mach-o/dyld.h>
35
36#define CFDictionary 0
37#define CFSet 0
38#define CFBag 0
39#undef CFSet
40#define CFSet 1
41
42#if CFDictionary
43const CFSetKeyCallBacks kCFTypeSetKeyCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
44const CFSetKeyCallBacks kCFCopyStringSetKeyCallBacks = {0, __CFStringCollectionCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
45const CFSetValueCallBacks kCFTypeSetValueCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual};
46static const CFSetKeyCallBacks __kCFNullSetKeyCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
47static const CFSetValueCallBacks __kCFNullSetValueCallBacks = {0, NULL, NULL, NULL, NULL};
48
49#define CFHashRef CFDictionaryRef
50#define CFMutableHashRef CFMutableDictionaryRef
51#define __kCFHashTypeID __kCFDictionaryTypeID
52#endif
53
54#if CFSet
55const CFSetCallBacks kCFTypeSetCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
56const CFSetCallBacks kCFCopyStringSetCallBacks = {0, __CFStringCollectionCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
57static const CFSetCallBacks __kCFNullSetCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
58
59#define CFSetKeyCallBacks CFSetCallBacks
60#define CFSetValueCallBacks CFSetCallBacks
61#define kCFTypeSetKeyCallBacks kCFTypeSetCallBacks
62#define kCFTypeSetValueCallBacks kCFTypeSetCallBacks
63#define __kCFNullSetKeyCallBacks __kCFNullSetCallBacks
64#define __kCFNullSetValueCallBacks __kCFNullSetCallBacks
65
66#define CFHashRef CFSetRef
67#define CFMutableHashRef CFMutableSetRef
68#define __kCFHashTypeID __kCFSetTypeID
69#endif
70
71#if CFBag
72const CFSetCallBacks kCFTypeSetCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
73const CFSetCallBacks kCFCopyStringSetCallBacks = {0, __CFStringCollectionCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
74static const CFSetCallBacks __kCFNullSetCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
75
76#define CFSetKeyCallBacks CFSetCallBacks
77#define CFSetValueCallBacks CFSetCallBacks
78#define kCFTypeSetKeyCallBacks kCFTypeSetCallBacks
79#define kCFTypeSetValueCallBacks kCFTypeSetCallBacks
80#define __kCFNullSetKeyCallBacks __kCFNullSetCallBacks
81#define __kCFNullSetValueCallBacks __kCFNullSetCallBacks
82
83#define CFHashRef CFBagRef
84#define CFMutableHashRef CFMutableBagRef
85#define __kCFHashTypeID __kCFBagTypeID
86#endif
87
88#define GETNEWKEY(newKey, oldKey) \
89 any_t (*kretain)(CFAllocatorRef, any_t, any_pointer_t) = \
90 !hasBeenFinalized(hc) \
91 ? (any_t (*)(CFAllocatorRef,any_t,any_pointer_t))__CFSetGetKeyCallBacks(hc)->retain \
92 : (any_t (*)(CFAllocatorRef,any_t,any_pointer_t))0; \
93 any_t newKey = kretain ? (any_t)INVOKE_CALLBACK3(kretain, allocator, (any_t)key, hc->_context) : (any_t)oldKey
94
95#define RELEASEKEY(oldKey) \
96 void (*krelease)(CFAllocatorRef, any_t, any_pointer_t) = \
97 !hasBeenFinalized(hc) \
98 ? (void (*)(CFAllocatorRef,any_t,any_pointer_t))__CFSetGetKeyCallBacks(hc)->release \
99 : (void (*)(CFAllocatorRef,any_t,any_pointer_t))0; \
100 if (krelease) INVOKE_CALLBACK3(krelease, allocator, oldKey, hc->_context)
101
102#if CFDictionary
103#define GETNEWVALUE(newValue) \
104 any_t (*vretain)(CFAllocatorRef, any_t, any_pointer_t) = \
105 !hasBeenFinalized(hc) \
106 ? (any_t (*)(CFAllocatorRef,any_t,any_pointer_t))__CFSetGetValueCallBacks(hc)->retain \
107 : (any_t (*)(CFAllocatorRef,any_t,any_pointer_t))0; \
108 any_t newValue = vretain ? (any_t)INVOKE_CALLBACK3(vretain, allocator, (any_t)value, hc->_context) : (any_t)value
109
110#define RELEASEVALUE(oldValue) \
111 void (*vrelease)(CFAllocatorRef, any_t, any_pointer_t) = \
112 !hasBeenFinalized(hc) \
113 ? (void (*)(CFAllocatorRef,any_t,any_pointer_t))__CFSetGetValueCallBacks(hc)->release \
114 : (void (*)(CFAllocatorRef,any_t,any_pointer_t))0; \
115 if (vrelease) INVOKE_CALLBACK3(vrelease, allocator, oldValue, hc->_context)
116
117#endif
118
119static void __CFSetHandleOutOfMemory(CFTypeRef obj, CFIndex numBytes) {
120 CFStringRef msg = CFStringCreateWithFormat(kCFAllocatorSystemDefault, NULL, CFSTR("Attempt to allocate %ld bytes for NS/CFSet failed"), numBytes);
121 CFBadErrorCallBack cb = _CFGetOutOfMemoryErrorCallBack();
122 if (NULL == cb || !cb(obj, CFSTR("NS/CFSet"), msg)) {
123 CFLog(kCFLogLevelCritical, CFSTR("%@"), msg);
124 HALT;
125 }
126 CFRelease(msg);
127}
128
129
130// Max load is 3/4 number of buckets
131CF_INLINE CFIndex __CFHashRoundUpCapacity(CFIndex capacity) {
132 return 3 * ((CFIndex)1 << (flsl((capacity - 1) / 3)));
133}
134
135// Returns next power of two higher than the capacity
136// threshold for the given input capacity.
137CF_INLINE CFIndex __CFHashNumBucketsForCapacity(CFIndex capacity) {
138 return 4 * ((CFIndex)1 << (flsl((capacity - 1) / 3)));
139}
140
141enum { /* Bits 1-0 */
142 __kCFHashImmutable = 0, /* unchangable and fixed capacity */
143 __kCFHashMutable = 1, /* changeable and variable capacity */
144};
145
146enum { /* Bits 5-4 (value), 3-2 (key) */
147 __kCFHashHasNullCallBacks = 0,
148 __kCFHashHasCFTypeCallBacks = 1,
149 __kCFHashHasCustomCallBacks = 3 /* callbacks are at end of header */
150};
151
152// Under GC, we fudge the key/value memory in two ways
153// First, if we had null callbacks or null for both retain/release, we use unscanned memory and get
154// standard 'dangling' references.
155// This means that if people were doing addValue:[xxx new] and never removing, well, that doesn't work
156//
157// Second, if we notice standard retain/release implementations we use scanned memory, and fudge the
158// standard callbacks to generally do nothing if the collection was allocated in GC memory. On special
159// CF objects, however, like those used for precious resources like video-card buffers, we do indeed
160// do CFRetain on input and CFRelease on output. The tricky case is GC finalization; we need to remember
161// that we did the CFReleases so that subsequent collection operations, like removal, don't double CFRelease.
162// (In fact we don't really use CFRetain/CFRelease but go directly to the collector)
163//
164
165enum {
166 __kCFHashFinalized = (1 << 7),
167 __kCFHashWeakKeys = (1 << 8),
168 __kCFHashWeakValues = (1 << 9)
169};
170
171typedef uintptr_t any_t;
172typedef const void * const_any_pointer_t;
173typedef void * any_pointer_t;
174
175struct __CFSet {
176 CFRuntimeBase _base;
177 CFIndex _count; /* number of values */
178 CFIndex _bucketsNum; /* number of buckets */
179 CFIndex _bucketsUsed; /* number of used buckets */
180 CFIndex _bucketsCap; /* maximum number of used buckets */
181 CFIndex _mutations;
182 CFIndex _deletes;
183 any_pointer_t _context; /* private */
184 CFOptionFlags _xflags;
185 any_t _marker;
186 any_t *_keys; /* can be NULL if not allocated yet */
187 any_t *_values; /* can be NULL if not allocated yet */
188};
189
190/* Bits 1-0 of the _xflags are used for mutability variety */
191/* Bits 3-2 of the _xflags are used for key callback indicator bits */
192/* Bits 5-4 of the _xflags are used for value callback indicator bits */
193/* Bit 6 of the _xflags is special KVO actions bit */
194/* Bits 7,8,9 are GC use */
195
196CF_INLINE bool hasBeenFinalized(CFTypeRef collection) {
197 return __CFBitfieldGetValue(((const struct __CFSet *)collection)->_xflags, 7, 7) != 0;
198}
199
200CF_INLINE void markFinalized(CFTypeRef collection) {
201 __CFBitfieldSetValue(((struct __CFSet *)collection)->_xflags, 7, 7, 1);
202}
203
204
205CF_INLINE CFIndex __CFHashGetType(CFHashRef hc) {
206 return __CFBitfieldGetValue(hc->_xflags, 1, 0);
207}
208
209CF_INLINE CFIndex __CFSetGetSizeOfType(CFIndex t) {
210 CFIndex size = sizeof(struct __CFSet);
211 if (__CFBitfieldGetValue(t, 3, 2) == __kCFHashHasCustomCallBacks) {
212 size += sizeof(CFSetKeyCallBacks);
213 }
214 if (__CFBitfieldGetValue(t, 5, 4) == __kCFHashHasCustomCallBacks) {
215 size += sizeof(CFSetValueCallBacks);
216 }
217 return size;
218}
219
220CF_INLINE const CFSetKeyCallBacks *__CFSetGetKeyCallBacks(CFHashRef hc) {
221 CFSetKeyCallBacks *result = NULL;
222 switch (__CFBitfieldGetValue(hc->_xflags, 3, 2)) {
223 case __kCFHashHasNullCallBacks:
224 return &__kCFNullSetKeyCallBacks;
225 case __kCFHashHasCFTypeCallBacks:
226 return &kCFTypeSetKeyCallBacks;
227 case __kCFHashHasCustomCallBacks:
228 break;
229 }
230 result = (CFSetKeyCallBacks *)((uint8_t *)hc + sizeof(struct __CFSet));
231 return result;
232}
233
234CF_INLINE Boolean __CFSetKeyCallBacksMatchNull(const CFSetKeyCallBacks *c) {
235 return (NULL == c ||
236 (c->retain == __kCFNullSetKeyCallBacks.retain &&
237 c->release == __kCFNullSetKeyCallBacks.release &&
238 c->copyDescription == __kCFNullSetKeyCallBacks.copyDescription &&
239 c->equal == __kCFNullSetKeyCallBacks.equal &&
240 c->hash == __kCFNullSetKeyCallBacks.hash));
241}
242
243CF_INLINE Boolean __CFSetKeyCallBacksMatchCFType(const CFSetKeyCallBacks *c) {
244 return (&kCFTypeSetKeyCallBacks == c ||
245 (c->retain == kCFTypeSetKeyCallBacks.retain &&
246 c->release == kCFTypeSetKeyCallBacks.release &&
247 c->copyDescription == kCFTypeSetKeyCallBacks.copyDescription &&
248 c->equal == kCFTypeSetKeyCallBacks.equal &&
249 c->hash == kCFTypeSetKeyCallBacks.hash));
250}
251
252CF_INLINE const CFSetValueCallBacks *__CFSetGetValueCallBacks(CFHashRef hc) {
253 CFSetValueCallBacks *result = NULL;
254 switch (__CFBitfieldGetValue(hc->_xflags, 5, 4)) {
255 case __kCFHashHasNullCallBacks:
256 return &__kCFNullSetValueCallBacks;
257 case __kCFHashHasCFTypeCallBacks:
258 return &kCFTypeSetValueCallBacks;
259 case __kCFHashHasCustomCallBacks:
260 break;
261 }
262 if (__CFBitfieldGetValue(hc->_xflags, 3, 2) == __kCFHashHasCustomCallBacks) {
263 result = (CFSetValueCallBacks *)((uint8_t *)hc + sizeof(struct __CFSet) + sizeof(CFSetKeyCallBacks));
264 } else {
265 result = (CFSetValueCallBacks *)((uint8_t *)hc + sizeof(struct __CFSet));
266 }
267 return result;
268}
269
270CF_INLINE Boolean __CFSetValueCallBacksMatchNull(const CFSetValueCallBacks *c) {
271 return (NULL == c ||
272 (c->retain == __kCFNullSetValueCallBacks.retain &&
273 c->release == __kCFNullSetValueCallBacks.release &&
274 c->copyDescription == __kCFNullSetValueCallBacks.copyDescription &&
275 c->equal == __kCFNullSetValueCallBacks.equal));
276}
277
278CF_INLINE Boolean __CFSetValueCallBacksMatchCFType(const CFSetValueCallBacks *c) {
279 return (&kCFTypeSetValueCallBacks == c ||
280 (c->retain == kCFTypeSetValueCallBacks.retain &&
281 c->release == kCFTypeSetValueCallBacks.release &&
282 c->copyDescription == kCFTypeSetValueCallBacks.copyDescription &&
283 c->equal == kCFTypeSetValueCallBacks.equal));
284}
285
286CFIndex _CFSetGetKVOBit(CFHashRef hc) {
287 return __CFBitfieldGetValue(hc->_xflags, 6, 6);
288}
289
290void _CFSetSetKVOBit(CFHashRef hc, CFIndex bit) {
291 __CFBitfieldSetValue(((CFMutableHashRef)hc)->_xflags, 6, 6, ((uintptr_t)bit & 0x1));
292}
293
294CF_INLINE Boolean __CFSetShouldShrink(CFHashRef hc) {
295 return (__kCFHashMutable == __CFHashGetType(hc)) &&
296 !(CF_USING_COLLECTABLE_MEMORY && auto_zone_is_finalized(__CFCollectableZone, hc)) && /* GC: don't shrink finalizing hcs! */
297 (hc->_bucketsNum < 4 * hc->_deletes || (256 <= hc->_bucketsCap && hc-> _bucketsUsed < 3 * hc->_bucketsCap / 16));
298}
299
300CF_INLINE CFIndex __CFHashGetOccurrenceCount(CFHashRef hc, CFIndex idx) {
301#if CFBag
302 return hc->_values[idx];
303#endif
304 return 1;
305}
306
307CF_INLINE Boolean __CFHashKeyIsValue(CFHashRef hc, any_t key) {
308 return (hc->_marker != key && ~hc->_marker != key) ? true : false;
309}
310
311CF_INLINE Boolean __CFHashKeyIsMagic(CFHashRef hc, any_t key) {
312 return (hc->_marker == key || ~hc->_marker == key) ? true : false;
313}
314
315
316#if !defined(CF_OBJC_KVO_WILLCHANGE)
317#define CF_OBJC_KVO_WILLCHANGE(obj, key)
318#define CF_OBJC_KVO_DIDCHANGE(obj, key)
319#endif
320
321CF_INLINE uintptr_t __CFSetScrambleHash(uintptr_t k) {
322#if 0
323 return k;
324#else
325#if __LP64__
326 uintptr_t a = 0x4368726973746F70ULL;
327 uintptr_t b = 0x686572204B616E65ULL;
328#else
329 uintptr_t a = 0x4B616E65UL;
330 uintptr_t b = 0x4B616E65UL;
331#endif
332 uintptr_t c = 1;
333 a += k;
334#if __LP64__
335 a -= b; a -= c; a ^= (c >> 43);
336 b -= c; b -= a; b ^= (a << 9);
337 c -= a; c -= b; c ^= (b >> 8);
338 a -= b; a -= c; a ^= (c >> 38);
339 b -= c; b -= a; b ^= (a << 23);
340 c -= a; c -= b; c ^= (b >> 5);
341 a -= b; a -= c; a ^= (c >> 35);
342 b -= c; b -= a; b ^= (a << 49);
343 c -= a; c -= b; c ^= (b >> 11);
344 a -= b; a -= c; a ^= (c >> 12);
345 b -= c; b -= a; b ^= (a << 18);
346 c -= a; c -= b; c ^= (b >> 22);
347#else
348 a -= b; a -= c; a ^= (c >> 13);
349 b -= c; b -= a; b ^= (a << 8);
350 c -= a; c -= b; c ^= (b >> 13);
351 a -= b; a -= c; a ^= (c >> 12);
352 b -= c; b -= a; b ^= (a << 16);
353 c -= a; c -= b; c ^= (b >> 5);
354 a -= b; a -= c; a ^= (c >> 3);
355 b -= c; b -= a; b ^= (a << 10);
356 c -= a; c -= b; c ^= (b >> 15);
357#endif
358 return c;
359#endif
360}
361
362static CFIndex __CFSetFindBuckets1a(CFHashRef hc, any_t key) {
363 CFHashCode keyHash = (CFHashCode)key;
364 keyHash = __CFSetScrambleHash(keyHash);
365 any_t *keys = hc->_keys;
366 any_t marker = hc->_marker;
367 CFIndex probe = keyHash & (hc->_bucketsNum - 1);
368 CFIndex probeskip = 1; // See RemoveValue() for notes before changing this value
369 CFIndex start = probe;
370 for (;;) {
371 any_t currKey = keys[probe];
372 if (marker == currKey) { /* empty */
373 return kCFNotFound;
374 } else if (~marker == currKey) { /* deleted */
375 /* do nothing */
376 } else if (currKey == key) {
377 return probe;
378 }
379 probe = probe + probeskip;
380 // This alternative to probe % buckets assumes that
381 // probeskip is always positive and less than the
382 // number of buckets.
383 if (hc->_bucketsNum <= probe) {
384 probe -= hc->_bucketsNum;
385 }
386 if (start == probe) {
387 return kCFNotFound;
388 }
389 }
390}
391
392static CFIndex __CFSetFindBuckets1b(CFHashRef hc, any_t key) {
393 const CFSetKeyCallBacks *cb = __CFSetGetKeyCallBacks(hc);
394 CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(any_t, any_pointer_t))cb->hash), key, hc->_context) : (CFHashCode)key;
395 keyHash = __CFSetScrambleHash(keyHash);
396 any_t *keys = hc->_keys;
397 any_t marker = hc->_marker;
398 CFIndex probe = keyHash & (hc->_bucketsNum - 1);
399 CFIndex probeskip = 1; // See RemoveValue() for notes before changing this value
400 CFIndex start = probe;
401 for (;;) {
402 any_t currKey = keys[probe];
403 if (marker == currKey) { /* empty */
404 return kCFNotFound;
405 } else if (~marker == currKey) { /* deleted */
406 /* do nothing */
407 } else if (currKey == key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(any_t, any_t, any_pointer_t))cb->equal, currKey, key, hc->_context))) {
408 return probe;
409 }
410 probe = probe + probeskip;
411 // This alternative to probe % buckets assumes that
412 // probeskip is always positive and less than the
413 // number of buckets.
414 if (hc->_bucketsNum <= probe) {
415 probe -= hc->_bucketsNum;
416 }
417 if (start == probe) {
418 return kCFNotFound;
419 }
420 }
421}
422
423CF_INLINE CFIndex __CFSetFindBuckets1(CFHashRef hc, any_t key) {
424 if (__kCFHashHasNullCallBacks == __CFBitfieldGetValue(hc->_xflags, 3, 2)) {
425 return __CFSetFindBuckets1a(hc, key);
426 }
427 return __CFSetFindBuckets1b(hc, key);
428}
429
430static void __CFSetFindBuckets2(CFHashRef hc, any_t key, CFIndex *match, CFIndex *nomatch) {
431 const CFSetKeyCallBacks *cb = __CFSetGetKeyCallBacks(hc);
432 CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(any_t, any_pointer_t))cb->hash), key, hc->_context) : (CFHashCode)key;
433 keyHash = __CFSetScrambleHash(keyHash);
434 any_t *keys = hc->_keys;
435 any_t marker = hc->_marker;
436 CFIndex probe = keyHash & (hc->_bucketsNum - 1);
437 CFIndex probeskip = 1; // See RemoveValue() for notes before changing this value
438 CFIndex start = probe;
439 *match = kCFNotFound;
440 *nomatch = kCFNotFound;
441 for (;;) {
442 any_t currKey = keys[probe];
443 if (marker == currKey) { /* empty */
444 if (nomatch) *nomatch = probe;
445 return;
446 } else if (~marker == currKey) { /* deleted */
447 if (nomatch) {
448 *nomatch = probe;
449 nomatch = NULL;
450 }
451 } else if (currKey == key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(any_t, any_t, any_pointer_t))cb->equal, currKey, key, hc->_context))) {
452 *match = probe;
453 return;
454 }
455 probe = probe + probeskip;
456 // This alternative to probe % buckets assumes that
457 // probeskip is always positive and less than the
458 // number of buckets.
459 if (hc->_bucketsNum <= probe) {
460 probe -= hc->_bucketsNum;
461 }
462 if (start == probe) {
463 return;
464 }
465 }
466}
467
468static void __CFSetFindNewMarker(CFHashRef hc) {
469 any_t *keys = hc->_keys;
470 any_t newMarker;
471 CFIndex idx, nbuckets;
472 Boolean hit;
473
474 nbuckets = hc->_bucketsNum;
475 newMarker = hc->_marker;
476 do {
477 newMarker--;
478 hit = false;
479 for (idx = 0; idx < nbuckets; idx++) {
480 if (newMarker == keys[idx] || ~newMarker == keys[idx]) {
481 hit = true;
482 break;
483 }
484 }
485 } while (hit);
486 for (idx = 0; idx < nbuckets; idx++) {
487 if (hc->_marker == keys[idx]) {
488 keys[idx] = newMarker;
489 } else if (~hc->_marker == keys[idx]) {
490 keys[idx] = ~newMarker;
491 }
492 }
493 ((struct __CFSet *)hc)->_marker = newMarker;
494}
495
496static Boolean __CFSetEqual(CFTypeRef cf1, CFTypeRef cf2) {
497 CFHashRef hc1 = (CFHashRef)cf1;
498 CFHashRef hc2 = (CFHashRef)cf2;
499 const CFSetKeyCallBacks *cb1, *cb2;
500 const CFSetValueCallBacks *vcb1, *vcb2;
501 any_t *keys;
502 CFIndex idx, nbuckets;
503 if (hc1 == hc2) return true;
504 if (hc1->_count != hc2->_count) return false;
505 cb1 = __CFSetGetKeyCallBacks(hc1);
506 cb2 = __CFSetGetKeyCallBacks(hc2);
507 if (cb1->equal != cb2->equal) return false;
508 vcb1 = __CFSetGetValueCallBacks(hc1);
509 vcb2 = __CFSetGetValueCallBacks(hc2);
510 if (vcb1->equal != vcb2->equal) return false;
511 if (0 == hc1->_bucketsUsed) return true; /* after function comparison! */
512 keys = hc1->_keys;
513 nbuckets = hc1->_bucketsNum;
514 for (idx = 0; idx < nbuckets; idx++) {
515 if (hc1->_marker != keys[idx] && ~hc1->_marker != keys[idx]) {
516#if CFDictionary
517 const_any_pointer_t value;
518 if (!CFSetGetValueIfPresent(hc2, (any_pointer_t)keys[idx], &value)) return false;
519 if (hc1->_values[idx] != (any_t)value) {
520 if (NULL == vcb1->equal) return false;
521 if (!INVOKE_CALLBACK3((Boolean (*)(any_t, any_t, any_pointer_t))vcb1->equal, hc1->_values[idx], (any_t)value, hc1->_context)) return false;
522 }
523#endif
524#if CFSet
525 const_any_pointer_t value;
526 if (!CFSetGetValueIfPresent(hc2, (any_pointer_t)keys[idx], &value)) return false;
527#endif
528#if CFBag
529 if (hc1->_values[idx] != CFSetGetCountOfValue(hc2, (any_pointer_t)keys[idx])) return false;
530#endif
531 }
532 }
533 return true;
534}
535
536static CFHashCode __CFSetHash(CFTypeRef cf) {
537 CFHashRef hc = (CFHashRef)cf;
538 return hc->_count;
539}
540
541static CFStringRef __CFSetCopyDescription(CFTypeRef cf) {
542 CFHashRef hc = (CFHashRef)cf;
543 CFAllocatorRef allocator;
544 const CFSetKeyCallBacks *cb;
545 const CFSetValueCallBacks *vcb;
546 any_t *keys;
547 CFIndex idx, nbuckets;
548 CFMutableStringRef result;
549 cb = __CFSetGetKeyCallBacks(hc);
550 vcb = __CFSetGetValueCallBacks(hc);
551 keys = hc->_keys;
552 nbuckets = hc->_bucketsNum;
553 allocator = CFGetAllocator(hc);
554 result = CFStringCreateMutable(allocator, 0);
555 const char *type = "?";
556 switch (__CFHashGetType(hc)) {
557 case __kCFHashImmutable: type = "immutable"; break;
558 case __kCFHashMutable: type = "mutable"; break;
559 }
560 CFStringAppendFormat(result, NULL, CFSTR("<CFSet %p [%p]>{type = %s, count = %u, capacity = %u, pairs = (\n"), cf, allocator, type, hc->_count, hc->_bucketsCap);
561 for (idx = 0; idx < nbuckets; idx++) {
562 if (__CFHashKeyIsValue(hc, keys[idx])) {
563 CFStringRef kDesc = NULL, vDesc = NULL;
564 if (NULL != cb->copyDescription) {
565 kDesc = (CFStringRef)INVOKE_CALLBACK2(((CFStringRef (*)(any_t, any_pointer_t))cb->copyDescription), keys[idx], hc->_context);
566 }
567 if (NULL != vcb->copyDescription) {
568 vDesc = (CFStringRef)INVOKE_CALLBACK2(((CFStringRef (*)(any_t, any_pointer_t))vcb->copyDescription), hc->_values[idx], hc->_context);
569 }
570#if CFDictionary
571 if (NULL != kDesc && NULL != vDesc) {
572 CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@ = %@\n"), idx, kDesc, vDesc);
573 CFRelease(kDesc);
574 CFRelease(vDesc);
575 } else if (NULL != kDesc) {
576 CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@ = <%p>\n"), idx, kDesc, hc->_values[idx]);
577 CFRelease(kDesc);
578 } else if (NULL != vDesc) {
579 CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p> = %@\n"), idx, keys[idx], vDesc);
580 CFRelease(vDesc);
581 } else {
582 CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p> = <%p>\n"), idx, keys[idx], hc->_values[idx]);
583 }
584#endif
585#if CFSet
586 if (NULL != kDesc) {
587 CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@\n"), idx, kDesc);
588 CFRelease(kDesc);
589 } else {
590 CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p>\n"), idx, keys[idx]);
591 }
592#endif
593#if CFBag
594 if (NULL != kDesc) {
595 CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@ (%ld)\n"), idx, kDesc, hc->_values[idx]);
596 CFRelease(kDesc);
597 } else {
598 CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p> (%ld)\n"), idx, keys[idx], hc->_values[idx]);
599 }
600#endif
601 }
602 }
603 CFStringAppend(result, CFSTR(")}"));
604 return result;
605}
606
607static void __CFSetDeallocate(CFTypeRef cf) {
608 CFMutableHashRef hc = (CFMutableHashRef)cf;
609 CFAllocatorRef allocator = __CFGetAllocator(hc);
610 const CFSetKeyCallBacks *cb = __CFSetGetKeyCallBacks(hc);
611 const CFSetValueCallBacks *vcb = __CFSetGetValueCallBacks(hc);
612
613 // mark now in case any callout somehow tries to add an entry back in
614 markFinalized(cf);
615 if (vcb->release || cb->release) {
616 any_t *keys = hc->_keys;
617 CFIndex idx, nbuckets = hc->_bucketsNum;
618 for (idx = 0; idx < nbuckets; idx++) {
619 any_t oldkey = keys[idx];
620 if (hc->_marker != oldkey && ~hc->_marker != oldkey) {
621 if (vcb->release) {
622 INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, any_t, any_pointer_t))vcb->release), allocator, hc->_values[idx], hc->_context);
623 }
624 if (cb->release) {
625 INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, any_t, any_pointer_t))cb->release), allocator, oldkey, hc->_context);
626 }
627 }
628 }
629 }
630
631 if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
632 // return early so that contents are preserved after finalization
633 return;
634 }
635
636 _CFAllocatorDeallocateGC(allocator, hc->_keys);
637#if CFDictionary || CFBag
638 _CFAllocatorDeallocateGC(allocator, hc->_values);
639#endif
640 hc->_keys = NULL;
641 hc->_values = NULL;
642 hc->_count = 0; // GC: also zero count, so the hc will appear empty.
643 hc->_bucketsUsed = 0;
644 hc->_bucketsNum = 0;
645}
646
647static CFTypeID __kCFSetTypeID = _kCFRuntimeNotATypeID;
648
649static const CFRuntimeClass __CFSetClass = {
650 _kCFRuntimeScannedObject,
651 "CFSet",
652 NULL, // init
653 NULL, // copy
654 __CFSetDeallocate,
655 __CFSetEqual,
656 __CFSetHash,
657 NULL, //
658 __CFSetCopyDescription
659};
660
661__private_extern__ void __CFSetInitialize(void) {
662 __kCFHashTypeID = _CFRuntimeRegisterClass(&__CFSetClass);
663}
664
665CFTypeID CFSetGetTypeID(void) {
666 return __kCFHashTypeID;
667}
668
669static CFMutableHashRef __CFSetInit(CFAllocatorRef allocator, CFOptionFlags flags, CFIndex capacity, const CFSetKeyCallBacks *keyCallBacks
670#if CFDictionary
671, const CFSetValueCallBacks *valueCallBacks
672#endif
673) {
674 struct __CFSet *hc;
675 CFIndex size;
676 __CFBitfieldSetValue(flags, 31, 2, 0);
677 CFOptionFlags xflags = 0;
678 if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
679 // preserve NULL for key or value CB, otherwise fix up.
680 if (!keyCallBacks || (keyCallBacks->retain == NULL && keyCallBacks->release == NULL)) {
681 xflags = __kCFHashWeakKeys;
682 }
683#if CFDictionary
684 if (!valueCallBacks || (valueCallBacks->retain == NULL && valueCallBacks->release == NULL)) {
685 xflags |= __kCFHashWeakValues;
686 }
687#endif
688#if CFBag
689 xflags |= __kCFHashWeakValues;
690#endif
691 }
692 if (__CFSetKeyCallBacksMatchNull(keyCallBacks)) {
693 __CFBitfieldSetValue(flags, 3, 2, __kCFHashHasNullCallBacks);
694 } else if (__CFSetKeyCallBacksMatchCFType(keyCallBacks)) {
695 __CFBitfieldSetValue(flags, 3, 2, __kCFHashHasCFTypeCallBacks);
696 } else {
697 __CFBitfieldSetValue(flags, 3, 2, __kCFHashHasCustomCallBacks);
698 }
699#if CFDictionary
700 if (__CFSetValueCallBacksMatchNull(valueCallBacks)) {
701 __CFBitfieldSetValue(flags, 5, 4, __kCFHashHasNullCallBacks);
702 } else if (__CFSetValueCallBacksMatchCFType(valueCallBacks)) {
703 __CFBitfieldSetValue(flags, 5, 4, __kCFHashHasCFTypeCallBacks);
704 } else {
705 __CFBitfieldSetValue(flags, 5, 4, __kCFHashHasCustomCallBacks);
706 }
707#endif
708 size = __CFSetGetSizeOfType(flags) - sizeof(CFRuntimeBase);
709 hc = (struct __CFSet *)_CFRuntimeCreateInstance(allocator, __kCFHashTypeID, size, NULL);
710 if (NULL == hc) {
711 return NULL;
712 }
713 hc->_count = 0;
714 hc->_bucketsUsed = 0;
715 hc->_marker = (any_t)0xa1b1c1d3;
716 hc->_context = NULL;
717 hc->_deletes = 0;
718 hc->_mutations = 1;
719 hc->_xflags = xflags | flags;
720 switch (__CFBitfieldGetValue(flags, 1, 0)) {
721 case __kCFHashImmutable:
722 if (__CFOASafe) __CFSetLastAllocationEventName(hc, "CFSet (immutable)");
723 break;
724 case __kCFHashMutable:
725 if (__CFOASafe) __CFSetLastAllocationEventName(hc, "CFSet (mutable-variable)");
726 break;
727 }
728 hc->_bucketsCap = __CFHashRoundUpCapacity(1);
729 hc->_bucketsNum = 0;
730 hc->_keys = NULL;
731 hc->_values = NULL;
732 if (__kCFHashHasCustomCallBacks == __CFBitfieldGetValue(flags, 3, 2)) {
733 CFSetKeyCallBacks *cb = (CFSetKeyCallBacks *)__CFSetGetKeyCallBacks((CFHashRef)hc);
734 *cb = *keyCallBacks;
735 FAULT_CALLBACK((void **)&(cb->retain));
736 FAULT_CALLBACK((void **)&(cb->release));
737 FAULT_CALLBACK((void **)&(cb->copyDescription));
738 FAULT_CALLBACK((void **)&(cb->equal));
739 FAULT_CALLBACK((void **)&(cb->hash));
740 }
741#if CFDictionary
742 if (__kCFHashHasCustomCallBacks == __CFBitfieldGetValue(flags, 5, 4)) {
743 CFSetValueCallBacks *vcb = (CFSetValueCallBacks *)__CFSetGetValueCallBacks((CFHashRef)hc);
744 *vcb = *valueCallBacks;
745 FAULT_CALLBACK((void **)&(vcb->retain));
746 FAULT_CALLBACK((void **)&(vcb->release));
747 FAULT_CALLBACK((void **)&(vcb->copyDescription));
748 FAULT_CALLBACK((void **)&(vcb->equal));
749 }
750#endif
751 return hc;
752}
753
754#if CFDictionary
755CFHashRef CFSetCreate(CFAllocatorRef allocator, const_any_pointer_t *keys, const_any_pointer_t *values, CFIndex numValues, const CFSetKeyCallBacks *keyCallBacks, const CFSetValueCallBacks *valueCallBacks) {
756#endif
757#if CFSet || CFBag
758CFHashRef CFSetCreate(CFAllocatorRef allocator, const_any_pointer_t *keys, CFIndex numValues, const CFSetKeyCallBacks *keyCallBacks) {
759#endif
760 CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%ld) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
761#if CFDictionary
762 CFMutableHashRef hc = __CFSetInit(allocator, __kCFHashImmutable, numValues, keyCallBacks, valueCallBacks);
763#endif
764#if CFSet || CFBag
765 CFMutableHashRef hc = __CFSetInit(allocator, __kCFHashImmutable, numValues, keyCallBacks);
766#endif
767 __CFBitfieldSetValue(hc->_xflags, 1, 0, __kCFHashMutable);
768 for (CFIndex idx = 0; idx < numValues; idx++) {
769#if CFDictionary
770 CFSetAddValue(hc, keys[idx], values[idx]);
771#endif
772#if CFSet || CFBag
773 CFSetAddValue(hc, keys[idx]);
774#endif
775 }
776 __CFBitfieldSetValue(hc->_xflags, 1, 0, __kCFHashImmutable);
777 return (CFHashRef)hc;
778}
779
780#if CFDictionary
781CFMutableHashRef CFSetCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFSetKeyCallBacks *keyCallBacks, const CFSetValueCallBacks *valueCallBacks) {
782#endif
783#if CFSet || CFBag
784CFMutableHashRef CFSetCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFSetKeyCallBacks *keyCallBacks) {
785#endif
786 CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%ld) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
787#if CFDictionary
788 CFMutableHashRef hc = __CFSetInit(allocator, __kCFHashMutable, capacity, keyCallBacks, valueCallBacks);
789#endif
790#if CFSet || CFBag
791 CFMutableHashRef hc = __CFSetInit(allocator, __kCFHashMutable, capacity, keyCallBacks);
792#endif
793 return hc;
794}
795
796#if CFDictionary || CFSet
797// does not have Add semantics for Bag; it has Set semantics ... is that best?
798static void __CFSetGrow(CFMutableHashRef hc, CFIndex numNewValues);
799
800// This creates a hc which is for CFTypes or NSObjects, with a CFRetain style ownership transfer;
801// 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).
802// The incoming objects must also be collectable if allocated out of a collectable allocator - and are neither released nor retained.
803#if CFDictionary
804CFHashRef _CFSetCreate_ex(CFAllocatorRef allocator, Boolean isMutable, const_any_pointer_t *keys, const_any_pointer_t *values, CFIndex numValues) {
805#endif
806#if CFSet || CFBag
807CFHashRef _CFSetCreate_ex(CFAllocatorRef allocator, Boolean isMutable, const_any_pointer_t *keys, CFIndex numValues) {
808#endif
809 CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%ld) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
810#if CFDictionary
811 CFMutableHashRef hc = __CFSetInit(allocator, __kCFHashMutable, numValues, &kCFTypeSetKeyCallBacks, &kCFTypeSetValueCallBacks);
812#endif
813#if CFSet || CFBag
814 CFMutableHashRef hc = __CFSetInit(allocator, __kCFHashMutable, numValues, &kCFTypeSetKeyCallBacks);
815#endif
816 __CFSetGrow(hc, numValues);
817 for (CFIndex idx = 0; idx < numValues; idx++) {
818 CFIndex match, nomatch;
819 __CFSetFindBuckets2(hc, (any_t)keys[idx], &match, &nomatch);
820 if (kCFNotFound == match) {
821 CFAllocatorRef allocator = __CFGetAllocator(hc);
822 any_t newKey = (any_t)keys[idx];
823 if (__CFHashKeyIsMagic(hc, newKey)) {
824 __CFSetFindNewMarker(hc);
825 }
826 if (hc->_keys[nomatch] == ~hc->_marker) {
827 hc->_deletes--;
828 }
829 CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
830 CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[nomatch], newKey);
831#if CFDictionary
832 any_t newValue = (any_t)values[idx];
833 CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
834 CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[nomatch], newValue);
835#endif
836#if CFBag
837 hc->_values[nomatch] = 1;
838#endif
839 hc->_bucketsUsed++;
840 hc->_count++;
841 } else {
842 CFAllocatorRef allocator = __CFGetAllocator(hc);
843#if CFSet || CFBag
844 any_t oldKey = hc->_keys[match];
845 any_t newKey = (any_t)keys[idx];
846 CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
847 CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], ~hc->_marker);
848 if (__CFHashKeyIsMagic(hc, newKey)) {
849 __CFSetFindNewMarker(hc);
850 }
851 CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], newKey);
852 RELEASEKEY(oldKey);
853#endif
854#if CFDictionary
855 any_t oldValue = hc->_values[match];
856 any_t newValue = (any_t)values[idx];
857 CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
858 CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[match], newValue);
859 RELEASEVALUE(oldValue);
860#endif
861 }
862 }
863 if (!isMutable) __CFBitfieldSetValue(hc->_xflags, 1, 0, __kCFHashImmutable);
864 return (CFHashRef)hc;
865}
866#endif
867
868CFHashRef CFSetCreateCopy(CFAllocatorRef allocator, CFHashRef other) {
869 CFMutableHashRef hc = CFSetCreateMutableCopy(allocator, CFSetGetCount(other), other);
870 __CFBitfieldSetValue(hc->_xflags, 1, 0, __kCFHashImmutable);
871 if (__CFOASafe) __CFSetLastAllocationEventName(hc, "CFSet (immutable)");
872 return hc;
873}
874
875CFMutableHashRef CFSetCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFHashRef other) {
876 CFIndex numValues = CFSetGetCount(other);
877 const_any_pointer_t *list, buffer[256];
878 list = (numValues <= 256) ? buffer : (const_any_pointer_t *)CFAllocatorAllocate(allocator, numValues * sizeof(const_any_pointer_t), 0);
879 if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFSet (temp)");
880#if CFDictionary
881 const_any_pointer_t *vlist, vbuffer[256];
882 vlist = (numValues <= 256) ? vbuffer : (const_any_pointer_t *)CFAllocatorAllocate(allocator, numValues * sizeof(const_any_pointer_t), 0);
883 if (vlist != vbuffer && __CFOASafe) __CFSetLastAllocationEventName(vlist, "CFSet (temp)");
884#endif
885#if CFSet || CFBag
886 CFSetGetValues(other, list);
887#endif
888#if CFDictionary
889 CFSetGetKeysAndValues(other, list, vlist);
890#endif
891 const CFSetKeyCallBacks *kcb;
892 const CFSetValueCallBacks *vcb;
893 if (CF_IS_OBJC(__kCFHashTypeID, other)) {
894 kcb = &kCFTypeSetKeyCallBacks;
895 vcb = &kCFTypeSetValueCallBacks;
896 } else {
897 kcb = __CFSetGetKeyCallBacks(other);
898 vcb = __CFSetGetValueCallBacks(other);
899 }
900#if CFDictionary
901 CFMutableHashRef hc = __CFSetInit(allocator, __kCFHashMutable, capacity, kcb, vcb);
902#endif
903#if CFSet || CFBag
904 CFMutableHashRef hc = __CFSetInit(allocator, __kCFHashMutable, capacity, kcb);
905#endif
906 if (0 == capacity) _CFSetSetCapacity(hc, numValues);
907 for (CFIndex idx = 0; idx < numValues; idx++) {
908#if CFDictionary
909 CFSetAddValue(hc, list[idx], vlist[idx]);
910#endif
911#if CFSet || CFBag
912 CFSetAddValue(hc, list[idx]);
913#endif
914 }
915 if (list != buffer) CFAllocatorDeallocate(allocator, list);
916#if CFDictionary
917 if (vlist != vbuffer) CFAllocatorDeallocate(allocator, vlist);
918#endif
919 return hc;
920}
921
922// Used by NSHashTables/NSMapTables and KVO
923void _CFSetSetContext(CFHashRef hc, any_pointer_t context) {
924 __CFGenericValidateType(hc, __kCFHashTypeID);
925 CF_WRITE_BARRIER_BASE_ASSIGN(__CFGetAllocator(hc), hc, hc->_context, context);
926}
927
928any_pointer_t _CFSetGetContext(CFHashRef hc) {
929 __CFGenericValidateType(hc, __kCFHashTypeID);
930 return hc->_context;
931}
932
933CFIndex CFSetGetCount(CFHashRef hc) {
934 if (CFDictionary || CFSet) CF_OBJC_FUNCDISPATCH0(__kCFHashTypeID, CFIndex, hc, "count");
935 __CFGenericValidateType(hc, __kCFHashTypeID);
936 return hc->_count;
937}
938
939#if CFDictionary
940CFIndex CFSetGetCountOfKey(CFHashRef hc, const_any_pointer_t key) {
941#endif
942#if CFSet || CFBag
943CFIndex CFSetGetCountOfValue(CFHashRef hc, const_any_pointer_t key) {
944#endif
945 if (CFDictionary) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, CFIndex, hc, "countForKey:", key);
946 if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, CFIndex, hc, "countForObject:", key);
947 __CFGenericValidateType(hc, __kCFHashTypeID);
948 if (0 == hc->_bucketsUsed) return 0;
949 CFIndex match = __CFSetFindBuckets1(hc, (any_t)key);
950 return (kCFNotFound != match ? __CFHashGetOccurrenceCount(hc, match) : 0);
951}
952
953#if CFDictionary
954Boolean CFSetContainsKey(CFHashRef hc, const_any_pointer_t key) {
955#endif
956#if CFSet || CFBag
957Boolean CFSetContainsValue(CFHashRef hc, const_any_pointer_t key) {
958#endif
959 if (CFDictionary) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, char, hc, "containsKey:", key);
960 if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, char, hc, "containsObject:", key);
961 __CFGenericValidateType(hc, __kCFHashTypeID);
962 if (0 == hc->_bucketsUsed) return false;
963 CFIndex match = __CFSetFindBuckets1(hc, (any_t)key);
964 return (kCFNotFound != match ? true : false);
965}
966
967#if CFDictionary
968CFIndex CFSetGetCountOfValue(CFHashRef hc, const_any_pointer_t value) {
969 CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, CFIndex, hc, "countForObject:", value);
970 __CFGenericValidateType(hc, __kCFHashTypeID);
971 if (0 == hc->_bucketsUsed) return 0;
972 any_t *keys = hc->_keys;
973 Boolean (*equal)(any_t, any_t, any_pointer_t) = (Boolean (*)(any_t, any_t, any_pointer_t))__CFSetGetValueCallBacks(hc)->equal;
974 CFIndex cnt = 0;
975 for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
976 if (__CFHashKeyIsValue(hc, keys[idx])) {
977 if ((hc->_values[idx] == (any_t)value) || (equal && INVOKE_CALLBACK3(equal, hc->_values[idx], (any_t)value, hc->_context))) {
978 cnt++;
979 }
980 }
981 }
982 return cnt;
983}
984
985Boolean CFSetContainsValue(CFHashRef hc, const_any_pointer_t value) {
986 CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, char, hc, "containsObject:", value);
987 __CFGenericValidateType(hc, __kCFHashTypeID);
988 if (0 == hc->_bucketsUsed) return false;
989 any_t *keys = hc->_keys;
990 Boolean (*equal)(any_t, any_t, any_pointer_t) = (Boolean (*)(any_t, any_t, any_pointer_t))__CFSetGetValueCallBacks(hc)->equal;
991 for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
992 if (__CFHashKeyIsValue(hc, keys[idx])) {
993 if ((hc->_values[idx] == (any_t)value) || (equal && INVOKE_CALLBACK3(equal, hc->_values[idx], (any_t)value, hc->_context))) {
994 return true;
995 }
996 }
997 }
998 return false;
999}
1000#endif
1001
1002const_any_pointer_t CFSetGetValue(CFHashRef hc, const_any_pointer_t key) {
1003 if (CFDictionary) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, const_any_pointer_t, hc, "objectForKey:", key);
1004 if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, const_any_pointer_t, hc, "member:", key);
1005 __CFGenericValidateType(hc, __kCFHashTypeID);
1006 if (0 == hc->_bucketsUsed) return 0;
1007 CFIndex match = __CFSetFindBuckets1(hc, (any_t)key);
1008 return (kCFNotFound != match ? (const_any_pointer_t)(CFDictionary ? hc->_values[match] : hc->_keys[match]) : 0);
1009}
1010
1011Boolean CFSetGetValueIfPresent(CFHashRef hc, const_any_pointer_t key, const_any_pointer_t *value) {
1012 if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, Boolean, hc, "_getValue:forKey:", (any_t *)value, key);
1013 if (CFSet) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, Boolean, hc, "_getValue:forObj:", (any_t *)value, key);
1014 __CFGenericValidateType(hc, __kCFHashTypeID);
1015 if (0 == hc->_bucketsUsed) return false;
1016 CFIndex match = __CFSetFindBuckets1(hc, (any_t)key);
1017 return (kCFNotFound != match ? ((value ? __CFObjCStrongAssign((const_any_pointer_t)(CFDictionary ? hc->_values[match] : hc->_keys[match]), value) : 0), true) : false);
1018}
1019
1020#if CFDictionary
1021Boolean CFSetGetKeyIfPresent(CFHashRef hc, const_any_pointer_t key, const_any_pointer_t *actualkey) {
1022 CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, Boolean, hc, "getActualKey:forKey:", actualkey, key);
1023 __CFGenericValidateType(hc, __kCFHashTypeID);
1024 if (0 == hc->_bucketsUsed) return false;
1025 CFIndex match = __CFSetFindBuckets1(hc, (any_t)key);
1026 return (kCFNotFound != match ? ((actualkey ? __CFObjCStrongAssign((const_any_pointer_t)hc->_keys[match], actualkey) : NULL), true) : false);
1027}
1028#endif
1029
1030#if CFDictionary
1031void CFSetGetKeysAndValues(CFHashRef hc, const_any_pointer_t *keybuf, const_any_pointer_t *valuebuf) {
1032#endif
1033#if CFSet || CFBag
1034void CFSetGetValues(CFHashRef hc, const_any_pointer_t *keybuf) {
1035 const_any_pointer_t *valuebuf = 0;
1036#endif
1037 if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "getObjects:andKeys:", (any_t *)valuebuf, (any_t *)keybuf);
1038 if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "getObjects:", (any_t *)keybuf);
1039 __CFGenericValidateType(hc, __kCFHashTypeID);
1040 if (CF_USING_COLLECTABLE_MEMORY) {
1041 // GC: speculatively issue a write-barrier on the copied to buffers
1042 __CFObjCWriteBarrierRange(keybuf, hc->_count * sizeof(any_t));
1043 __CFObjCWriteBarrierRange(valuebuf, hc->_count * sizeof(any_t));
1044 }
1045 any_t *keys = hc->_keys;
1046 for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
1047 if (__CFHashKeyIsValue(hc, keys[idx])) {
1048 for (CFIndex cnt = __CFHashGetOccurrenceCount(hc, idx); cnt--;) {
1049 if (keybuf) *keybuf++ = (const_any_pointer_t)keys[idx];
1050 if (valuebuf) *valuebuf++ = (const_any_pointer_t)hc->_values[idx];
1051 }
1052 }
1053 }
1054}
1055
1056#if CFDictionary || CFSet
1057unsigned long _CFSetFastEnumeration(CFHashRef hc, struct __objcFastEnumerationStateEquivalent *state, void *stackbuffer, unsigned long count) {
1058 /* copy as many as count items over */
1059 if (0 == state->state) { /* first time */
1060 state->mutationsPtr = (unsigned long *)&hc->_mutations;
1061 }
1062 state->itemsPtr = (unsigned long *)stackbuffer;
1063 CFIndex cnt = 0;
1064 any_t *keys = hc->_keys;
1065 for (CFIndex idx = (CFIndex)state->state, nbuckets = hc->_bucketsNum; idx < nbuckets && cnt < (CFIndex)count; idx++) {
1066 if (__CFHashKeyIsValue(hc, keys[idx])) {
1067 state->itemsPtr[cnt++] = (unsigned long)keys[idx];
1068 }
1069 state->state++;
1070 }
1071 return cnt;
1072}
1073#endif
1074
1075void CFSetApplyFunction(CFHashRef hc, CFSetApplierFunction applier, any_pointer_t context) {
1076 FAULT_CALLBACK((void **)&(applier));
1077 if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "_apply:context:", applier, context);
1078 if (CFSet) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "_applyValues:context:", applier, context);
1079 __CFGenericValidateType(hc, __kCFHashTypeID);
1080 any_t *keys = hc->_keys;
1081 for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
1082 if (__CFHashKeyIsValue(hc, keys[idx])) {
1083 for (CFIndex cnt = __CFHashGetOccurrenceCount(hc, idx); cnt--;) {
1084#if CFDictionary
1085 INVOKE_CALLBACK3(applier, (const_any_pointer_t)keys[idx], (const_any_pointer_t)hc->_values[idx], context);
1086#endif
1087#if CFSet || CFBag
1088 INVOKE_CALLBACK2(applier, (const_any_pointer_t)keys[idx], context);
1089#endif
1090 }
1091 }
1092 }
1093}
1094
1095static void __CFSetGrow(CFMutableHashRef hc, CFIndex numNewValues) {
1096 any_t *oldkeys = hc->_keys;
1097 any_t *oldvalues = hc->_values;
1098 CFIndex nbuckets = hc->_bucketsNum;
1099 hc->_bucketsCap = __CFHashRoundUpCapacity(hc->_bucketsUsed + numNewValues);
1100 hc->_bucketsNum = __CFHashNumBucketsForCapacity(hc->_bucketsCap);
1101 hc->_deletes = 0;
1102 CFAllocatorRef allocator = __CFGetAllocator(hc);
1103 CFOptionFlags weakOrStrong = (hc->_xflags & __kCFHashWeakKeys) ? 0 : __kCFAllocatorGCScannedMemory;
1104 any_t *mem = (any_t *)_CFAllocatorAllocateGC(allocator, hc->_bucketsNum * sizeof(any_t), weakOrStrong);
1105 if (NULL == mem) __CFSetHandleOutOfMemory(hc, hc->_bucketsNum * sizeof(any_t));
1106 if (__CFOASafe) __CFSetLastAllocationEventName(mem, "CFSet (key-store)");
1107 CF_WRITE_BARRIER_BASE_ASSIGN(allocator, hc, hc->_keys, mem);
1108 CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator; // GC: avoids write-barrier in weak case.
1109 any_t *keysBase = mem;
1110#if CFDictionary || CFBag
1111 weakOrStrong = (hc->_xflags & __kCFHashWeakValues) ? 0 : __kCFAllocatorGCScannedMemory;
1112 mem = (any_t *)_CFAllocatorAllocateGC(allocator, hc->_bucketsNum * sizeof(any_t), weakOrStrong);
1113 if (NULL == mem) __CFSetHandleOutOfMemory(hc, hc->_bucketsNum * sizeof(any_t));
1114 if (__CFOASafe) __CFSetLastAllocationEventName(mem, "CFSet (value-store)");
1115 CF_WRITE_BARRIER_BASE_ASSIGN(allocator, hc, hc->_values, mem);
1116#endif
1117#if CFDictionary
1118 CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator; // GC: avoids write-barrier in weak case.
1119 any_t *valuesBase = mem;
1120#endif
1121 for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
1122 hc->_keys[idx] = hc->_marker;
1123#if CFDictionary || CFBag
1124 hc->_values[idx] = 0;
1125#endif
1126 }
1127 if (NULL == oldkeys) return;
1128 for (CFIndex idx = 0; idx < nbuckets; idx++) {
1129 if (__CFHashKeyIsValue(hc, oldkeys[idx])) {
1130 CFIndex match, nomatch;
1131 __CFSetFindBuckets2(hc, oldkeys[idx], &match, &nomatch);
1132 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]);
1133 if (kCFNotFound != nomatch) {
1134 CF_WRITE_BARRIER_BASE_ASSIGN(keysAllocator, keysBase, hc->_keys[nomatch], oldkeys[idx]);
1135#if CFDictionary
1136 CF_WRITE_BARRIER_BASE_ASSIGN(valuesAllocator, valuesBase, hc->_values[nomatch], oldvalues[idx]);
1137#endif
1138#if CFBag
1139 hc->_values[nomatch] = oldvalues[idx];
1140#endif
1141 }
1142 }
1143 }
1144 _CFAllocatorDeallocateGC(allocator, oldkeys);
1145 _CFAllocatorDeallocateGC(allocator, oldvalues);
1146}
1147
1148// This function is for Foundation's benefit; no one else should use it.
1149void _CFSetSetCapacity(CFMutableHashRef hc, CFIndex cap) {
1150 if (CF_IS_OBJC(__kCFHashTypeID, hc)) return;
1151 __CFGenericValidateType(hc, __kCFHashTypeID);
1152 CFAssert1(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): collection is immutable", __PRETTY_FUNCTION__);
1153 CFAssert3(hc->_bucketsUsed <= cap, __kCFLogAssertion, "%s(): desired capacity (%ld) is less than bucket count (%ld)", __PRETTY_FUNCTION__, cap, hc->_bucketsUsed);
1154 __CFSetGrow(hc, cap - hc->_bucketsUsed);
1155}
1156
1157
1158#if CFDictionary
1159void CFSetAddValue(CFMutableHashRef hc, const_any_pointer_t key, const_any_pointer_t value) {
1160#endif
1161#if CFSet || CFBag
1162void CFSetAddValue(CFMutableHashRef hc, const_any_pointer_t key) {
1163 #define value 0
1164#endif
1165 if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "_addObject:forKey:", value, key);
1166 if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "addObject:", key);
1167 __CFGenericValidateType(hc, __kCFHashTypeID);
1168 switch (__CFHashGetType(hc)) {
1169 case __kCFHashMutable:
1170 if (hc->_bucketsUsed == hc->_bucketsCap || NULL == hc->_keys) {
1171 __CFSetGrow(hc, 1);
1172 }
1173 break;
1174 default:
1175 CFAssert2(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
1176 break;
1177 }
1178 hc->_mutations++;
1179 CFIndex match, nomatch;
1180 __CFSetFindBuckets2(hc, (any_t)key, &match, &nomatch);
1181 if (kCFNotFound != match) {
1182#if CFBag
1183 CF_OBJC_KVO_WILLCHANGE(hc, hc->_keys[match]);
1184 hc->_values[match]++;
1185 hc->_count++;
1186 CF_OBJC_KVO_DIDCHANGE(hc, hc->_keys[match]);
1187#endif
1188 } else {
1189 CFAllocatorRef allocator = __CFGetAllocator(hc);
1190 GETNEWKEY(newKey, key);
1191#if CFDictionary
1192 GETNEWVALUE(newValue);
1193#endif
1194 if (__CFHashKeyIsMagic(hc, newKey)) {
1195 __CFSetFindNewMarker(hc);
1196 }
1197 if (hc->_keys[nomatch] == ~hc->_marker) {
1198 hc->_deletes--;
1199 }
1200 CF_OBJC_KVO_WILLCHANGE(hc, key);
1201 CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
1202 CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[nomatch], newKey);
1203#if CFDictionary
1204 CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
1205 CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[nomatch], newValue);
1206#endif
1207#if CFBag
1208 hc->_values[nomatch] = 1;
1209#endif
1210 hc->_bucketsUsed++;
1211 hc->_count++;
1212 CF_OBJC_KVO_DIDCHANGE(hc, key);
1213 }
1214}
1215
1216#if CFDictionary
1217void CFSetReplaceValue(CFMutableHashRef hc, const_any_pointer_t key, const_any_pointer_t value) {
1218#endif
1219#if CFSet || CFBag
1220void CFSetReplaceValue(CFMutableHashRef hc, const_any_pointer_t key) {
1221 #define value 0
1222#endif
1223 if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "_replaceObject:forKey:", value, key);
1224 if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "_replaceObject:", key);
1225 __CFGenericValidateType(hc, __kCFHashTypeID);
1226 switch (__CFHashGetType(hc)) {
1227 case __kCFHashMutable:
1228 break;
1229 default:
1230 CFAssert2(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
1231 break;
1232 }
1233 hc->_mutations++;
1234 if (0 == hc->_bucketsUsed) return;
1235 CFIndex match = __CFSetFindBuckets1(hc, (any_t)key);
1236 if (kCFNotFound == match) return;
1237 CFAllocatorRef allocator = __CFGetAllocator(hc);
1238#if CFSet || CFBag
1239 GETNEWKEY(newKey, key);
1240#endif
1241#if CFDictionary
1242 GETNEWVALUE(newValue);
1243#endif
1244 any_t oldKey = hc->_keys[match];
1245 CF_OBJC_KVO_WILLCHANGE(hc, oldKey);
1246#if CFSet || CFBag
1247 CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
1248 CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], ~hc->_marker);
1249 if (__CFHashKeyIsMagic(hc, newKey)) {
1250 __CFSetFindNewMarker(hc);
1251 }
1252 CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], newKey);
1253#endif
1254#if CFDictionary
1255 any_t oldValue = hc->_values[match];
1256 CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
1257 CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[match], newValue);
1258#endif
1259 CF_OBJC_KVO_DIDCHANGE(hc, oldKey);
1260#if CFSet || CFBag
1261 RELEASEKEY(oldKey);
1262#endif
1263#if CFDictionary
1264 RELEASEVALUE(oldValue);
1265#endif
1266}
1267
1268#if CFDictionary
1269void CFSetSetValue(CFMutableHashRef hc, const_any_pointer_t key, const_any_pointer_t value) {
1270#endif
1271#if CFSet || CFBag
1272void CFSetSetValue(CFMutableHashRef hc, const_any_pointer_t key) {
1273 #define value 0
1274#endif
1275 if (CFDictionary) CF_OBJC_FUNCDISPATCH2(__kCFHashTypeID, void, hc, "setObject:forKey:", value, key);
1276 if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "_setObject:", key);
1277 __CFGenericValidateType(hc, __kCFHashTypeID);
1278 switch (__CFHashGetType(hc)) {
1279 case __kCFHashMutable:
1280 if (hc->_bucketsUsed == hc->_bucketsCap || NULL == hc->_keys) {
1281 __CFSetGrow(hc, 1);
1282 }
1283 break;
1284 default:
1285 CFAssert2(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
1286 break;
1287 }
1288 hc->_mutations++;
1289 CFIndex match, nomatch;
1290 __CFSetFindBuckets2(hc, (any_t)key, &match, &nomatch);
1291 if (kCFNotFound == match) {
1292 CFAllocatorRef allocator = __CFGetAllocator(hc);
1293 GETNEWKEY(newKey, key);
1294#if CFDictionary
1295 GETNEWVALUE(newValue);
1296#endif
1297 if (__CFHashKeyIsMagic(hc, newKey)) {
1298 __CFSetFindNewMarker(hc);
1299 }
1300 if (hc->_keys[nomatch] == ~hc->_marker) {
1301 hc->_deletes--;
1302 }
1303 CF_OBJC_KVO_WILLCHANGE(hc, key);
1304 CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
1305 CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[nomatch], newKey);
1306#if CFDictionary
1307 CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
1308 CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[nomatch], newValue);
1309#endif
1310#if CFBag
1311 hc->_values[nomatch] = 1;
1312#endif
1313 hc->_bucketsUsed++;
1314 hc->_count++;
1315 CF_OBJC_KVO_DIDCHANGE(hc, key);
1316 } else {
1317 CFAllocatorRef allocator = __CFGetAllocator(hc);
1318#if CFSet || CFBag
1319 GETNEWKEY(newKey, key);
1320#endif
1321#if CFDictionary
1322 GETNEWVALUE(newValue);
1323#endif
1324 any_t oldKey = hc->_keys[match];
1325 CF_OBJC_KVO_WILLCHANGE(hc, oldKey);
1326#if CFSet || CFBag
1327 CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
1328 CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], ~hc->_marker);
1329 if (__CFHashKeyIsMagic(hc, newKey)) {
1330 __CFSetFindNewMarker(hc);
1331 }
1332 CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], newKey);
1333#endif
1334#if CFDictionary
1335 any_t oldValue = hc->_values[match];
1336 CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
1337 CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[match], newValue);
1338#endif
1339 CF_OBJC_KVO_DIDCHANGE(hc, oldKey);
1340#if CFSet || CFBag
1341 RELEASEKEY(oldKey);
1342#endif
1343#if CFDictionary
1344 RELEASEVALUE(oldValue);
1345#endif
1346 }
1347}
1348
1349void CFSetRemoveValue(CFMutableHashRef hc, const_any_pointer_t key) {
1350 if (CFDictionary) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "removeObjectForKey:", key);
1351 if (CFSet) CF_OBJC_FUNCDISPATCH1(__kCFHashTypeID, void, hc, "removeObject:", key);
1352 __CFGenericValidateType(hc, __kCFHashTypeID);
1353 switch (__CFHashGetType(hc)) {
1354 case __kCFHashMutable:
1355 break;
1356 default:
1357 CFAssert2(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
1358 break;
1359 }
1360 hc->_mutations++;
1361 if (0 == hc->_bucketsUsed) return;
1362 CFIndex match = __CFSetFindBuckets1(hc, (any_t)key);
1363 if (kCFNotFound == match) return;
1364 if (1 < __CFHashGetOccurrenceCount(hc, match)) {
1365#if CFBag
1366 CF_OBJC_KVO_WILLCHANGE(hc, hc->_keys[match]);
1367 hc->_values[match]--;
1368 hc->_count--;
1369 CF_OBJC_KVO_DIDCHANGE(hc, hc->_keys[match]);
1370#endif
1371 } else {
1372 CFAllocatorRef allocator = __CFGetAllocator(hc);
1373 any_t oldKey = hc->_keys[match];
1374 CF_OBJC_KVO_WILLCHANGE(hc, oldKey);
1375 CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
1376 CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[match], ~hc->_marker);
1377#if CFDictionary
1378 any_t oldValue = hc->_values[match];
1379 CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
1380 CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[match], 0);
1381#endif
1382#if CFBag
1383 hc->_values[match] = 0;
1384#endif
1385 hc->_count--;
1386 hc->_bucketsUsed--;
1387 hc->_deletes++;
1388 CF_OBJC_KVO_DIDCHANGE(hc, oldKey);
1389 RELEASEKEY(oldKey);
1390#if CFDictionary
1391 RELEASEVALUE(oldValue);
1392#endif
1393 if (__CFSetShouldShrink(hc)) {
1394 __CFSetGrow(hc, 0);
1395 } else {
1396 // When the probeskip == 1 always and only, a DELETED slot followed by an EMPTY slot
1397 // can be converted to an EMPTY slot. By extension, a chain of DELETED slots followed
1398 // by an EMPTY slot can be converted to EMPTY slots, which is what we do here.
1399 if (match < hc->_bucketsNum - 1 && hc->_keys[match + 1] == hc->_marker) {
1400 while (0 <= match && hc->_keys[match] == ~hc->_marker) {
1401 hc->_keys[match] = hc->_marker;
1402 hc->_deletes--;
1403 match--;
1404 }
1405 }
1406 }
1407 }
1408}
1409
1410void CFSetRemoveAllValues(CFMutableHashRef hc) {
1411 if (CFDictionary) CF_OBJC_FUNCDISPATCH0(__kCFHashTypeID, void, hc, "removeAllObjects");
1412 if (CFSet) CF_OBJC_FUNCDISPATCH0(__kCFHashTypeID, void, hc, "removeAllObjects");
1413 __CFGenericValidateType(hc, __kCFHashTypeID);
1414 switch (__CFHashGetType(hc)) {
1415 case __kCFHashMutable:
1416 break;
1417 default:
1418 CFAssert2(__CFHashGetType(hc) != __kCFHashImmutable, __kCFLogAssertion, "%s(): immutable collection %p passed to mutating operation", __PRETTY_FUNCTION__, hc);
1419 break;
1420 }
1421 hc->_mutations++;
1422 if (0 == hc->_bucketsUsed) return;
1423 CFAllocatorRef allocator = __CFGetAllocator(hc);
1424 any_t *keys = hc->_keys;
1425 for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
1426 if (__CFHashKeyIsValue(hc, keys[idx])) {
1427 any_t oldKey = keys[idx];
1428 CF_OBJC_KVO_WILLCHANGE(hc, oldKey);
1429#if CFDictionary || CFSet
1430 hc->_count--;
1431#endif
1432#if CFBag
1433 hc->_count -= hc->_values[idx];
1434#endif
1435 CFAllocatorRef keysAllocator = (hc->_xflags & __kCFHashWeakKeys) ? kCFAllocatorNull : allocator;
1436 CF_WRITE_BARRIER_ASSIGN(keysAllocator, hc->_keys[idx], ~hc->_marker);
1437#if CFDictionary
1438 any_t oldValue = hc->_values[idx];
1439 CFAllocatorRef valuesAllocator = (hc->_xflags & __kCFHashWeakValues) ? kCFAllocatorNull : allocator;
1440 CF_WRITE_BARRIER_ASSIGN(valuesAllocator, hc->_values[idx], 0);
1441#endif
1442#if CFBag
1443 hc->_values[idx] = 0;
1444#endif
1445 hc->_bucketsUsed--;
1446 hc->_deletes++;
1447 CF_OBJC_KVO_DIDCHANGE(hc, oldKey);
1448 RELEASEKEY(oldKey);
1449#if CFDictionary
1450 RELEASEVALUE(oldValue);
1451#endif
1452 }
1453 }
1454 for (CFIndex idx = 0, nbuckets = hc->_bucketsNum; idx < nbuckets; idx++) {
1455 keys[idx] = hc->_marker;
1456 }
1457 hc->_deletes = 0;
1458 hc->_bucketsUsed = 0;
1459 hc->_count = 0;
1460 if (__CFSetShouldShrink(hc) && (256 <= hc->_bucketsCap)) {
1461 __CFSetGrow(hc, 128);
1462 }
1463}
1464
1465#undef CF_OBJC_KVO_WILLCHANGE
1466#undef CF_OBJC_KVO_DIDCHANGE
1467
mirror of CF