]> git.saurik.com Git - apple/cf.git/blame - Collections.subproj/CFSet.c
projects / apple / cf.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
CF-299.35.tar.gz
[apple/cf.git] / Collections.subproj / CFSet.c
CommitLineData
9ce05555
A		 1/*
2 * Copyright (c) 2003 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
7 *
8 * This file contains Original Code and/or Modifications of Original Code
9 * as defined in and that are subject to the Apple Public Source License
10 * Version 2.0 (the 'License'). You may not use this file except in
11 * compliance with the License. Please obtain a copy of the License at
12 * http://www.opensource.apple.com/apsl/ and read it before using this
13 * file.
14 *
15 * The Original Code and all software distributed under the License are
16 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
17 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
18 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
20 * Please see the License for the specific language governing rights and
21 * limitations under the License.
22 *
23 * @APPLE_LICENSE_HEADER_END@
24 */
25/* CFSet.c
26 Copyright 1998-2002, Apple, Inc. All rights reserved.
27 Responsibility: Christopher Kane
28*/
29
30#include <CoreFoundation/CFSet.h>
31#include "CFInternal.h"
32
33const CFSetCallBacks kCFTypeSetCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
34const CFSetCallBacks kCFCopyStringSetCallBacks = {0, (void *)CFStringCreateCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
35static const CFSetCallBacks __kCFNullSetCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
36
37
38static const uint32_t __CFSetCapacities[42] = {
39 4, 8, 17, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349,
40 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498,
41 3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324,
42 228826127, 370248451, 599074578, 969323029, 1568397607, 2537720636U
43};
44
45static const uint32_t __CFSetBuckets[42] = { // primes
46 5, 11, 23, 41, 67, 113, 199, 317, 521, 839, 1361, 2207, 3571, 5779, 9349, 15121,
47 24473, 39607, 64081, 103681, 167759, 271429, 439199, 710641, 1149857, 1860503, 3010349,
48 4870843, 7881193, 12752029, 20633237, 33385273, 54018521, 87403763, 141422317, 228826121,
49 370248451, 599074561, 969323023, 1568397599, 2537720629U, 4106118251U
50};
51
52CF_INLINE CFIndex __CFSetRoundUpCapacity(CFIndex capacity) {
53 CFIndex idx;
54 for (idx = 0; idx < 42 && __CFSetCapacities[idx] < (uint32_t)capacity; idx++);
55 if (42 <= idx) HALT;
56 return __CFSetCapacities[idx];
57}
58
59CF_INLINE CFIndex __CFSetNumBucketsForCapacity(CFIndex capacity) {
60 CFIndex idx;
61 for (idx = 0; idx < 42 && __CFSetCapacities[idx] < (uint32_t)capacity; idx++);
62 if (42 <= idx) HALT;
63 return __CFSetBuckets[idx];
64}
65
66enum { /* Bits 1-0 */
67 __kCFSetImmutable = 0, /* unchangable and fixed capacity */
68 __kCFSetMutable = 1, /* changeable and variable capacity */
69 __kCFSetFixedMutable = 3 /* changeable and fixed capacity */
70};
71
72enum { /* Bits 3-2 */
73 __kCFSetHasNullCallBacks = 0,
74 __kCFSetHasCFTypeCallBacks = 1,
75 __kCFSetHasCustomCallBacks = 3 /* callbacks are at end of header */
76};
77
78struct __CFSetBucket {
79 const void *_key;
80};
81
82struct __CFSet {
83 CFRuntimeBase _base;
84 CFIndex _count; /* number of values */
85 CFIndex _capacity; /* maximum number of values */
86 CFIndex _bucketsUsed; /* number of slots used */
87 CFIndex _bucketsNum; /* number of slots */
88 const void *_emptyMarker;
89 const void *_deletedMarker;
90 void *_context; /* private */
91 struct __CFSetBucket *_buckets; /* can be NULL if not allocated yet */
92};
93
94CF_INLINE bool __CFSetBucketIsEmpty(CFSetRef set, const struct __CFSetBucket *bucket) {
95 return (set->_emptyMarker == bucket->_key);
96}
97
98CF_INLINE bool __CFSetBucketIsDeleted(CFSetRef set, const struct __CFSetBucket *bucket) {
99 return (set->_deletedMarker == bucket->_key);
100}
101
102CF_INLINE bool __CFSetBucketIsOccupied(CFSetRef set, const struct __CFSetBucket *bucket) {
103 return (set->_emptyMarker != bucket->_key && set->_deletedMarker != bucket->_key);
104}
105
106/* Bits 1-0 of the base reserved bits are used for mutability variety */
107/* Bits 3-2 of the base reserved bits are used for callback indicator bits */
108
109CF_INLINE CFIndex __CFSetGetType(CFSetRef set) {
110 return __CFBitfieldGetValue(((const CFRuntimeBase *)set)->_info, 1, 0);
111}
112
113CF_INLINE CFIndex __CFSetGetSizeOfType(CFIndex t) {
114 CFIndex size = sizeof(struct __CFSet);
115 if (__CFBitfieldGetValue(t, 3, 2) == __kCFSetHasCustomCallBacks) {
116 size += sizeof(CFSetCallBacks);
117 }
118 return size;
119}
120
121CF_INLINE const CFSetCallBacks *__CFSetGetCallBacks(CFSetRef set) {
122 CFSetCallBacks *result = NULL;
123 switch (__CFBitfieldGetValue(((const CFRuntimeBase *)set)->_info, 3, 2)) {
124 case __kCFSetHasNullCallBacks:
125 return &__kCFNullSetCallBacks;
126 case __kCFSetHasCFTypeCallBacks:
127 return &kCFTypeSetCallBacks;
128 case __kCFSetHasCustomCallBacks:
129 break;
130 }
131 result = (CFSetCallBacks *)((uint8_t *)set + sizeof(struct __CFSet));
132 return result;
133}
134
135CF_INLINE bool __CFSetCallBacksMatchNull(const CFSetCallBacks *c) {
136 return (NULL == c ||
137 (c->retain == __kCFNullSetCallBacks.retain &&
138 c->release == __kCFNullSetCallBacks.release &&
139 c->copyDescription == __kCFNullSetCallBacks.copyDescription &&
140 c->equal == __kCFNullSetCallBacks.equal &&
141 c->hash == __kCFNullSetCallBacks.hash));
142}
143
144CF_INLINE bool __CFSetCallBacksMatchCFType(const CFSetCallBacks *c) {
145 return (&kCFTypeSetCallBacks == c ||
146 (c->retain == kCFTypeSetCallBacks.retain &&
147 c->release == kCFTypeSetCallBacks.release &&
148 c->copyDescription == kCFTypeSetCallBacks.copyDescription &&
149 c->equal == kCFTypeSetCallBacks.equal &&
150 c->hash == kCFTypeSetCallBacks.hash));
151}
152
153
154static void __CFSetFindBuckets1(CFSetRef set, const void *key, struct __CFSetBucket **match) {
155 const CFSetCallBacks *cb = __CFSetGetCallBacks(set);
156 struct __CFSetBucket *buckets = set->_buckets;
157 CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, set->_context) : (CFHashCode)key;
158 UInt32 start = keyHash % set->_bucketsNum;
159 UInt32 probe = start;
160 UInt32 probeskip = 1;
161 *match = NULL;
162 for (;;) {
163 struct __CFSetBucket *currentBucket = buckets + probe;
164 if (__CFSetBucketIsEmpty(set, currentBucket)) {
165 return;
166 } else if (__CFSetBucketIsDeleted(set, currentBucket)) {
167 /* do nothing */
168 } else if (currentBucket->_key == key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(void *, void *, void*))cb->equal, currentBucket->_key, key, set->_context))) {
169 *match = currentBucket;
170 return;
171 }
172 probe = (probe + probeskip) % set->_bucketsNum;
173 if (start == probe) return;
174 }
175}
176
177static void __CFSetFindBuckets2(CFSetRef set, const void *key, struct __CFSetBucket **match, struct __CFSetBucket **nomatch) {
178 const CFSetCallBacks *cb = __CFSetGetCallBacks(set);
179 struct __CFSetBucket *buckets = set->_buckets;
180 CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, set->_context) : (CFHashCode)key;
181 UInt32 start = keyHash % set->_bucketsNum;
182 UInt32 probe = start;
183 UInt32 probeskip = 1;
184 *match = NULL;
185 *nomatch = NULL;
186 for (;;) {
187 struct __CFSetBucket *currentBucket = buckets + probe;
188 if (__CFSetBucketIsEmpty(set, currentBucket)) {
189 if (!*nomatch) *nomatch = currentBucket;
190 return;
191 } else if (__CFSetBucketIsDeleted(set, currentBucket)) {
192 if (!*nomatch) *nomatch = currentBucket;
193 } else if (!*match && (currentBucket->_key == key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(void *, void *, void*))cb->equal, currentBucket->_key, key, set->_context)))) {
194 *match = currentBucket;
195 if (*nomatch) return;
196 }
197 probe = (probe + probeskip) % set->_bucketsNum;
198 if (start == probe) return;
199 }
200}
201
202static void __CFSetFindNewEmptyMarker(CFSetRef set) {
203 struct __CFSetBucket *buckets;
204 const void *newEmpty;
205 bool hit;
206 CFIndex idx, nbuckets;
207 buckets = set->_buckets;
208 nbuckets = set->_bucketsNum;
209 newEmpty = set->_emptyMarker;
210 do {
211 (intptr_t)newEmpty -= 2;
212 hit = false;
213 for (idx = 0; idx < nbuckets; idx++) {
214 if (newEmpty == buckets[idx]._key) {
215 hit = true;
216 break;
217 }
218 }
219 } while (hit);
220 for (idx = 0; idx < nbuckets; idx++) {
221 if (set->_emptyMarker == buckets[idx]._key) {
222 buckets[idx]._key = newEmpty;
223 }
224 }
225 ((struct __CFSet *)set)->_emptyMarker = newEmpty;
226}
227
228static void __CFSetFindNewDeletedMarker(CFSetRef set) {
229 struct __CFSetBucket *buckets;
230 const void *newDeleted;
231 bool hit;
232 CFIndex idx, nbuckets;
233 buckets = set->_buckets;
234 nbuckets = set->_bucketsNum;
235 newDeleted = set->_deletedMarker;
236 do {
237 (intptr_t)newDeleted += 2;
238 hit = false;
239 for (idx = 0; idx < nbuckets; idx++) {
240 if (newDeleted == buckets[idx]._key) {
241 hit = true;
242 break;
243 }
244 }
245 } while (hit);
246 for (idx = 0; idx < nbuckets; idx++) {
247 if (set->_deletedMarker == buckets[idx]._key) {
248 buckets[idx]._key = newDeleted;
249 }
250 }
251 ((struct __CFSet *)set)->_deletedMarker = newDeleted;
252}
253
254static bool __CFSetEqual(CFTypeRef cf1, CFTypeRef cf2) {
255 CFSetRef set1 = (CFSetRef)cf1;
256 CFSetRef set2 = (CFSetRef)cf2;
257 const CFSetCallBacks *cb1, *cb2;
258 const struct __CFSetBucket *buckets;
259 CFIndex idx, nbuckets;
260 if (set1 == set2) return true;
261 if (set1->_count != set2->_count) return false;
262 cb1 = __CFSetGetCallBacks(set1);
263 cb2 = __CFSetGetCallBacks(set2);
264 if (cb1->equal != cb2->equal) return false;
265 if (0 == set1->_count) return true; /* after function comparison! */
266 buckets = set1->_buckets;
267 nbuckets = set1->_bucketsNum;
268 for (idx = 0; idx < nbuckets; idx++) {
269 if (__CFSetBucketIsOccupied(set1, &buckets[idx])) {
270 if (1 != CFSetGetCountOfValue(set2, buckets[idx]._key)) {
271 return false;
272 }
273 }
274 }
275 return true;
276}
277
278static CFHashCode __CFSetHash(CFTypeRef cf) {
279 CFSetRef set = (CFSetRef)cf;
280 return set->_count;
281}
282
283static CFStringRef __CFSetCopyDescription(CFTypeRef cf) {
284 CFSetRef set = (CFSetRef)cf;
285 const CFSetCallBacks *cb;
286 const struct __CFSetBucket *buckets;
287 CFIndex idx, nbuckets;
288 CFMutableStringRef result;
289 cb = __CFSetGetCallBacks(set);
290 buckets = set->_buckets;
291 nbuckets = set->_bucketsNum;
292 result = CFStringCreateMutable(kCFAllocatorSystemDefault, 0);
293 CFStringAppendFormat(result, NULL, CFSTR("<CFSet %p [%p]>{count = %u, capacity = %u, values = (\n"), set, CFGetAllocator(set), set->_count, set->_capacity);
294 for (idx = 0; idx < nbuckets; idx++) {
295 if (__CFSetBucketIsOccupied(set, &buckets[idx])) {
296 CFStringRef desc = NULL;
297 if (NULL != cb->copyDescription) {
298 desc = (CFStringRef)INVOKE_CALLBACK2(((CFStringRef (*)(const void *, void *))cb->copyDescription), buckets[idx]._key, set->_context);
299 }
300 if (NULL != desc) {
301 CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@\n"), idx, desc, NULL);
302 CFRelease(desc);
303 } else {
304 CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p>\n"), idx, buckets[idx]._key, NULL);
305 }
306 }
307 }
308 CFStringAppend(result, CFSTR(")}"));
309 return result;
310}
311
312static void __CFSetDeallocate(CFTypeRef cf) {
313 CFMutableSetRef set = (CFMutableSetRef)cf;
314 CFAllocatorRef allocator = __CFGetAllocator(set);
315 if (__CFSetGetType(set) == __kCFSetImmutable) {
316 __CFBitfieldSetValue(((CFRuntimeBase *)set)->_info, 1, 0, __kCFSetFixedMutable);
317 }
318 CFSetRemoveAllValues(set);
319 if (__CFSetGetType(set) == __kCFSetMutable && set->_buckets) {
320 CFAllocatorDeallocate(allocator, set->_buckets);
321 }
322}
323
324static CFTypeID __kCFSetTypeID = _kCFRuntimeNotATypeID;
325
326static const CFRuntimeClass __CFSetClass = {
327 0,
328 "CFSet",
329 NULL, // init
330 NULL, // copy
331 __CFSetDeallocate,
332 (void *)__CFSetEqual,
333 __CFSetHash,
334 NULL, //
335 __CFSetCopyDescription
336};
337
338__private_extern__ void __CFSetInitialize(void) {
339 __kCFSetTypeID = _CFRuntimeRegisterClass(&__CFSetClass);
340}
341
342CFTypeID CFSetGetTypeID(void) {
343 return __kCFSetTypeID;
344}
345
346static CFSetRef __CFSetInit(CFAllocatorRef allocator, UInt32 flags, CFIndex capacity, const CFSetCallBacks *callBacks) {
347 struct __CFSet *memory;
348 UInt32 size;
349 CFIndex idx;
350 __CFBitfieldSetValue(flags, 31, 2, 0);
351 if (__CFSetCallBacksMatchNull(callBacks)) {
352 __CFBitfieldSetValue(flags, 3, 2, __kCFSetHasNullCallBacks);
353 } else if (__CFSetCallBacksMatchCFType(callBacks)) {
354 __CFBitfieldSetValue(flags, 3, 2, __kCFSetHasCFTypeCallBacks);
355 } else {
356 __CFBitfieldSetValue(flags, 3, 2, __kCFSetHasCustomCallBacks);
357 }
358 size = __CFSetGetSizeOfType(flags) - sizeof(CFRuntimeBase);
359 switch (__CFBitfieldGetValue(flags, 1, 0)) {
360 case __kCFSetImmutable:
361 case __kCFSetFixedMutable:
362 size += __CFSetNumBucketsForCapacity(capacity) * sizeof(struct __CFSetBucket);
363 break;
364 case __kCFSetMutable:
365 break;
366 }
367 memory = (struct __CFSet *)_CFRuntimeCreateInstance(allocator, __kCFSetTypeID, size, NULL);
368 if (NULL == memory) {
369 return NULL;
370 }
371 __CFBitfieldSetValue(memory->_base._info, 6, 0, flags);
372 memory->_count = 0;
373 memory->_bucketsUsed = 0;
374 memory->_emptyMarker = (const void *)0xa1b1c1d3;
375 memory->_deletedMarker = (const void *)0xa1b1c1d5;
376 memory->_context = NULL;
377 switch (__CFBitfieldGetValue(flags, 1, 0)) {
378 case __kCFSetImmutable:
379 if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFSet (immutable)");
380 memory->_capacity = capacity; /* Don't round up capacity */
381 memory->_bucketsNum = __CFSetNumBucketsForCapacity(memory->_capacity);
382 memory->_buckets = (struct __CFSetBucket *)((uint8_t *)memory + __CFSetGetSizeOfType(flags));
383 for (idx = memory->_bucketsNum; idx--;) {
384 memory->_buckets[idx]._key = memory->_emptyMarker;
385 }
386 break;
387 case __kCFSetFixedMutable:
388 if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFSet (mutable-fixed)");
389 memory->_capacity = capacity; /* Don't round up capacity */
390 memory->_bucketsNum = __CFSetNumBucketsForCapacity(memory->_capacity);
391 memory->_buckets = (struct __CFSetBucket *)((uint8_t *)memory + __CFSetGetSizeOfType(flags));
392 for (idx = memory->_bucketsNum; idx--;) {
393 memory->_buckets[idx]._key = memory->_emptyMarker;
394 }
395 break;
396 case __kCFSetMutable:
397 if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFSet (mutable-variable)");
398 memory->_capacity = __CFSetRoundUpCapacity(1);
399 memory->_bucketsNum = 0;
400 memory->_buckets = NULL;
401 break;
402 }
403 if (__kCFSetHasCustomCallBacks == __CFBitfieldGetValue(flags, 3, 2)) {
404 const CFSetCallBacks *cb = __CFSetGetCallBacks((CFSetRef)memory);
405 *(CFSetCallBacks *)cb = *callBacks;
406 FAULT_CALLBACK((void **)&(cb->retain));
407 FAULT_CALLBACK((void **)&(cb->release));
408 FAULT_CALLBACK((void **)&(cb->copyDescription));
409 FAULT_CALLBACK((void **)&(cb->equal));
410 FAULT_CALLBACK((void **)&(cb->hash));
411 }
412 return (CFSetRef)memory;
413}
414
415CFSetRef CFSetCreate(CFAllocatorRef allocator, const void **values, CFIndex numValues, const CFSetCallBacks *callBacks) {
416 CFSetRef result;
417 UInt32 flags;
418 CFIndex idx;
419 CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
420 result = __CFSetInit(allocator, __kCFSetImmutable, numValues, callBacks);
421 flags = __CFBitfieldGetValue(((const CFRuntimeBase *)result)->_info, 1, 0);
422 if (flags == __kCFSetImmutable) {
423 __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, __kCFSetFixedMutable);
424 }
425 for (idx = 0; idx < numValues; idx++) {
426 CFSetAddValue((CFMutableSetRef)result, values[idx]);
427 }
428 __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, flags);
429 return result;
430}
431
432CFMutableSetRef CFSetCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFSetCallBacks *callBacks) {
433 CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
434 return (CFMutableSetRef)__CFSetInit(allocator, (0 == capacity) ? __kCFSetMutable : __kCFSetFixedMutable, capacity, callBacks);
435}
436
437CFSetRef CFSetCreateCopy(CFAllocatorRef allocator, CFSetRef set) {
438 CFSetRef result;
439 const CFSetCallBacks *cb;
440 CFIndex numValues = CFSetGetCount(set);
441 const void **list, *buffer[256];
442 list = (numValues <= 256) ? buffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0);
443 if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFSet (temp)");
444 CFSetGetValues(set, list);
445 cb = CF_IS_OBJC(__kCFSetTypeID, set) ? &kCFTypeSetCallBacks : __CFSetGetCallBacks(set);
446 result = CFSetCreate(allocator, list, numValues, cb);
447 if (list != buffer) CFAllocatorDeallocate(allocator, list);
448 return result;
449}
450
451CFMutableSetRef CFSetCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFSetRef set) {
452 CFMutableSetRef result;
453 const CFSetCallBacks *cb;
454 CFIndex idx, numValues = CFSetGetCount(set);
455 const void **list, *buffer[256];
456 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);
457 list = (numValues <= 256) ? buffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0);
458 if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFSet (temp)");
459 CFSetGetValues(set, list);
460 cb = CF_IS_OBJC(__kCFSetTypeID, set) ? &kCFTypeSetCallBacks : __CFSetGetCallBacks(set);
461 result = CFSetCreateMutable(allocator, capacity, cb);
462 if (0 == capacity) _CFSetSetCapacity(result, numValues);
463 for (idx = 0; idx < numValues; idx++) {
464 CFSetAddValue(result, list[idx]);
465 }
466 if (list != buffer) CFAllocatorDeallocate(allocator, list);
467 return result;
468}
469
470void _CFSetSetContext(CFSetRef set, void *context) {
471 ((struct __CFSet *)set)->_context = context;
472}
473
474CFIndex CFSetGetCount(CFSetRef set) {
475 CF_OBJC_FUNCDISPATCH0(__kCFSetTypeID, CFIndex, set, "count");
476 __CFGenericValidateType(set, __kCFSetTypeID);
477 return set->_count;
478}
479
480CFIndex CFSetGetCountOfValue(CFSetRef set, const void *value) {
481 struct __CFSetBucket *match;
482 CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, CFIndex, set, "countForObject:", value);
483 __CFGenericValidateType(set, __kCFSetTypeID);
484 if (0 == set->_count) return 0;
485 __CFSetFindBuckets1(set, value, &match);
486 return (match ? 1 : 0);
487}
488
489Boolean CFSetContainsValue(CFSetRef set, const void *value) {
490 struct __CFSetBucket *match;
491 CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, char, set, "containsObject:", value);
492 __CFGenericValidateType(set, __kCFSetTypeID);
493 if (0 == set->_count) return false;
494 __CFSetFindBuckets1(set, value, &match);
495 return (match ? true : false);
496}
497
498const void *CFSetGetValue(CFSetRef set, const void *value) {
499 struct __CFSetBucket *match;
500 CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, const void *, set, "member:", value);
501 __CFGenericValidateType(set, __kCFSetTypeID);
502 if (0 == set->_count) return NULL;
503 __CFSetFindBuckets1(set, value, &match);
504 return (match ? match->_key : NULL);
505}
506
507Boolean CFSetGetValueIfPresent(CFSetRef set, const void *candidate, const void **value) {
508 struct __CFSetBucket *match;
509 CF_OBJC_FUNCDISPATCH2(__kCFSetTypeID, char, set, "_getValue:forObj:", (void * *)value, candidate);
510 __CFGenericValidateType(set, __kCFSetTypeID);
511 if (0 == set->_count) return false;
512 __CFSetFindBuckets1(set, candidate, &match);
513 return (match ? ((value ? *value = match->_key : NULL), true) : false);
514}
515
516void CFSetGetValues(CFSetRef set, const void **values) {
517 struct __CFSetBucket *buckets;
518 CFIndex idx, cnt, nbuckets;
519 CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, set, "getObjects:", (void * *)values);
520 __CFGenericValidateType(set, __kCFSetTypeID);
521 buckets = set->_buckets;
522 nbuckets = set->_bucketsNum;
523 for (idx = 0; idx < nbuckets; idx++) {
524 if (__CFSetBucketIsOccupied(set, &buckets[idx])) {
525 for (cnt = 1; cnt--;) {
526 if (values) *values++ = buckets[idx]._key;
527 }
528 }
529 }
530}
531
532void CFSetApplyFunction(CFSetRef set, CFSetApplierFunction applier, void *context) {
533 struct __CFSetBucket *buckets;
534 CFIndex idx, cnt, nbuckets;
535 FAULT_CALLBACK((void **)&(applier));
536 CF_OBJC_FUNCDISPATCH2(__kCFSetTypeID, void, set, "_applyValues:context:", applier, context);
537 __CFGenericValidateType(set, __kCFSetTypeID);
538 buckets = set->_buckets;
539 nbuckets = set->_bucketsNum;
540 for (idx = 0; idx < nbuckets; idx++) {
541 if (__CFSetBucketIsOccupied(set, &buckets[idx])) {
542 for (cnt = 1; cnt--;) {
543 INVOKE_CALLBACK2(applier, buckets[idx]._key, context);
544 }
545 }
546 }
547}
548
549static void __CFSetGrow(CFMutableSetRef set, CFIndex numNewValues) {
550 struct __CFSetBucket *oldbuckets = set->_buckets;
551 CFIndex idx, oldnbuckets = set->_bucketsNum;
552 CFIndex oldCount = set->_count;
553 set->_capacity = __CFSetRoundUpCapacity(oldCount + numNewValues);
554 set->_bucketsNum = __CFSetNumBucketsForCapacity(set->_capacity);
555 set->_buckets = CFAllocatorAllocate(__CFGetAllocator(set), set->_bucketsNum * sizeof(struct __CFSetBucket), 0);
556 if (NULL == set->_buckets) HALT;
557 if (__CFOASafe) __CFSetLastAllocationEventName(set->_buckets, "CFSet (store)");
558 for (idx = set->_bucketsNum; idx--;) {
559 set->_buckets[idx]._key = set->_emptyMarker;
560 }
561 if (NULL == oldbuckets) return;
562 for (idx = 0; idx < oldnbuckets; idx++) {
563 if (__CFSetBucketIsOccupied(set, &oldbuckets[idx])) {
564 struct __CFSetBucket *match, *nomatch;
565 __CFSetFindBuckets2(set, oldbuckets[idx]._key, &match, &nomatch);
566 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);
567 nomatch->_key = oldbuckets[idx]._key;
568 }
569 }
570 CFAssert1(set->_count == oldCount, __kCFLogAssertion, "%s(): set count differs after rehashing; error", __PRETTY_FUNCTION__);
571 CFAllocatorDeallocate(__CFGetAllocator(set), oldbuckets);
572}
573
574// This function is for Foundation's benefit; no one else should use it.
575void _CFSetSetCapacity(CFMutableSetRef set, CFIndex cap) {
576 if (CF_IS_OBJC(__kCFSetTypeID, set)) return;
577#if defined(DEBUG)
578 __CFGenericValidateType(set, __kCFSetTypeID);
579 CFAssert1(__CFSetGetType(set) != __kCFSetImmutable && __CFSetGetType(set) != __kCFSetFixedMutable, __kCFLogAssertion, "%s(): set is immutable or fixed-mutable", __PRETTY_FUNCTION__);
580 CFAssert3(set->_count <= cap, __kCFLogAssertion, "%s(): desired capacity (%d) is less than count (%d)", __PRETTY_FUNCTION__, cap, set->_count);
581#endif
582 __CFSetGrow(set, cap - set->_count);
583}
584
585// This function is for Foundation's benefit; no one else should use it.
586bool _CFSetIsMutable(CFSetRef set) {
587 return (__CFSetGetType(set) != __kCFSetImmutable);
588}
589
590void CFSetAddValue(CFMutableSetRef set, const void *value) {
591 struct __CFSetBucket *match, *nomatch;
592 const CFSetCallBacks *cb;
593 const void *newValue;
594 CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, set, "addObject:", value);
595 __CFGenericValidateType(set, __kCFSetTypeID);
596 switch (__CFSetGetType(set)) {
597 case __kCFSetMutable:
598 if (set->_bucketsUsed == set->_capacity || NULL == set->_buckets) {
599 __CFSetGrow(set, 1);
600 }
601 break;
602 case __kCFSetFixedMutable:
603 CFAssert3(set->_count < set->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity set %p (capacity = %d)", __PRETTY_FUNCTION__, set, set->_capacity);
604 break;
605 default:
606 CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
607 break;
608 }
609 __CFSetFindBuckets2(set, value, &match, &nomatch);
610 if (match) {
611 } else {
612 cb = __CFSetGetCallBacks(set);
613 if (cb->retain) {
614 newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), __CFGetAllocator(set), value, set->_context);
615 } else {
616 newValue = value;
617 }
618 if (set->_emptyMarker == newValue) {
619 __CFSetFindNewEmptyMarker(set);
620 }
621 if (set->_deletedMarker == newValue) {
622 __CFSetFindNewDeletedMarker(set);
623 }
624 nomatch->_key = newValue;
625 set->_bucketsUsed++;
626 set->_count++;
627 }
628}
629
630__private_extern__ const void *__CFSetAddValueAndReturn(CFMutableSetRef set, const void *value) {
631 struct __CFSetBucket *match, *nomatch;
632 const CFSetCallBacks *cb;
633 const void *newValue;
634// #warning not toll-free bridged, but internal
635 __CFGenericValidateType(set, __kCFSetTypeID);
636 switch (__CFSetGetType(set)) {
637 case __kCFSetMutable:
638 if (set->_bucketsUsed == set->_capacity || NULL == set->_buckets) {
639 __CFSetGrow(set, 1);
640 }
641 break;
642 case __kCFSetFixedMutable:
643 CFAssert3(set->_count < set->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity set %p (capacity = %d)", __PRETTY_FUNCTION__, set, set->_capacity);
644 break;
645 default:
646 CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
647 break;
648 }
649 __CFSetFindBuckets2(set, value, &match, &nomatch);
650 if (match) {
651 return match->_key;
652 } else {
653 cb = __CFSetGetCallBacks(set);
654 if (cb->retain) {
655 newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), __CFGetAllocator(set), value, set->_context);
656 } else {
657 newValue = value;
658 }
659 if (set->_emptyMarker == newValue) {
660 __CFSetFindNewEmptyMarker(set);
661 }
662 if (set->_deletedMarker == newValue) {
663 __CFSetFindNewDeletedMarker(set);
664 }
665 nomatch->_key = newValue;
666 set->_bucketsUsed++;
667 set->_count++;
668 return newValue;
669 }
670}
671
672void CFSetReplaceValue(CFMutableSetRef set, const void *value) {
673 struct __CFSetBucket *match;
674 const CFSetCallBacks *cb;
675 const void *newValue;
676 CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, set, "_replaceObject:", value);
677 __CFGenericValidateType(set, __kCFSetTypeID);
678 switch (__CFSetGetType(set)) {
679 case __kCFSetMutable:
680 case __kCFSetFixedMutable:
681 break;
682 default:
683 CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
684 break;
685 }
686 if (0 == set->_count) return;
687 __CFSetFindBuckets1(set, value, &match);
688 if (!match) return;
689 cb = __CFSetGetCallBacks(set);
690 if (cb->retain) {
691 newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), __CFGetAllocator(set), value, set->_context);
692 } else {
693 newValue = value;
694 }
695 if (cb->release) {
696 INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), __CFGetAllocator(set), match->_key, set->_context);
697 match->_key = set->_deletedMarker;
698 }
699 if (set->_emptyMarker == newValue) {
700 __CFSetFindNewEmptyMarker(set);
701 }
702 if (set->_deletedMarker == newValue) {
703 __CFSetFindNewDeletedMarker(set);
704 }
705 match->_key = newValue;
706}
707
708void CFSetSetValue(CFMutableSetRef set, const void *value) {
709 struct __CFSetBucket *match, *nomatch;
710 const CFSetCallBacks *cb;
711 const void *newValue;
712 CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, set, "_setObject:", value);
713 __CFGenericValidateType(set, __kCFSetTypeID);
714 switch (__CFSetGetType(set)) {
715 case __kCFSetMutable:
716 if (set->_bucketsUsed == set->_capacity || NULL == set->_buckets) {
717 __CFSetGrow(set, 1);
718 }
719 break;
720 case __kCFSetFixedMutable:
721 break;
722 default:
723 CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
724 break;
725 }
726 __CFSetFindBuckets2(set, value, &match, &nomatch);
727 cb = __CFSetGetCallBacks(set);
728 if (cb->retain) {
729 newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), __CFGetAllocator(set), value, set->_context);
730 } else {
731 newValue = value;
732 }
733 if (match) {
734 if (cb->release) {
735 INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), __CFGetAllocator(set), match->_key, set->_context);
736 match->_key = set->_deletedMarker;
737 }
738 if (set->_emptyMarker == newValue) {
739 __CFSetFindNewEmptyMarker(set);
740 }
741 if (set->_deletedMarker == newValue) {
742 __CFSetFindNewDeletedMarker(set);
743 }
744 match->_key = newValue;
745 } else {
746 CFAssert3(__kCFSetFixedMutable != __CFSetGetType(set) || set->_count < set->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity set %p (capacity = %d)", __PRETTY_FUNCTION__, set, set->_capacity);
747 if (set->_emptyMarker == newValue) {
748 __CFSetFindNewEmptyMarker(set);
749 }
750 if (set->_deletedMarker == newValue) {
751 __CFSetFindNewDeletedMarker(set);
752 }
753 nomatch->_key = newValue;
754 set->_bucketsUsed++;
755 set->_count++;
756 }
757}
758
759void CFSetRemoveValue(CFMutableSetRef set, const void *value) {
760 struct __CFSetBucket *match;
761 const CFSetCallBacks *cb;
762 CF_OBJC_FUNCDISPATCH1(__kCFSetTypeID, void, set, "removeObject:", value);
763 __CFGenericValidateType(set, __kCFSetTypeID);
764 switch (__CFSetGetType(set)) {
765 case __kCFSetMutable:
766 case __kCFSetFixedMutable:
767 break;
768 default:
769 CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
770 break;
771 }
772 if (0 == set->_count) return;
773 __CFSetFindBuckets1(set, value, &match);
774 if (!match) return;
775 set->_count--;
776 if (1) {
777 cb = __CFSetGetCallBacks(set);
778 if (cb->release) {
779 INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), __CFGetAllocator(set), match->_key, set->_context);
780 }
781 match->_key = set->_deletedMarker;
782 set->_bucketsUsed--;
783 }
784}
785
786void CFSetRemoveAllValues(CFMutableSetRef set) {
787 struct __CFSetBucket *buckets;
788 const CFSetCallBacks *cb;
789 CFAllocatorRef allocator;
790 CFIndex idx, nbuckets;
791 CF_OBJC_FUNCDISPATCH0(__kCFSetTypeID, void, set, "removeAllObjects");
792 __CFGenericValidateType(set, __kCFSetTypeID);
793 switch (__CFSetGetType(set)) {
794 case __kCFSetMutable:
795 case __kCFSetFixedMutable:
796 break;
797 default:
798 CFAssert2(__CFSetGetType(set) != __kCFSetImmutable, __kCFLogAssertion, "%s(): immutable set %p passed to mutating operation", __PRETTY_FUNCTION__, set);
799 break;
800 }
801 if (0 == set->_count) return;
802 buckets = set->_buckets;
803 nbuckets = set->_bucketsNum;
804 cb = __CFSetGetCallBacks(set);
805 allocator = __CFGetAllocator(set);
806 for (idx = 0; idx < nbuckets; idx++) {
807 if (__CFSetBucketIsOccupied(set, &buckets[idx])) {
808 if (cb->release) {
809 INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), allocator, buckets[idx]._key, set->_context);
810 }
811 buckets[idx]._key = set->_emptyMarker;
812 }
813 }
814 set->_bucketsUsed = 0;
815 set->_count = 0;
816}
817
mirror of CF