]> git.saurik.com Git - apple/cf.git/blame - Collections.subproj/CFDictionary.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 / CFDictionary.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/* CFDictionary.c
26 Copyright 1998-2002, Apple, Inc. All rights reserved.
27 Responsibility: Christopher Kane
28*/
29
30#include <CoreFoundation/CFDictionary.h>
31#include "CFInternal.h"
32
33const CFDictionaryKeyCallBacks kCFTypeDictionaryKeyCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
34const CFDictionaryKeyCallBacks kCFCopyStringDictionaryKeyCallBacks = {0, (void *)CFStringCreateCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
35const CFDictionaryValueCallBacks kCFTypeDictionaryValueCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual};
36static const CFDictionaryKeyCallBacks __kCFNullDictionaryKeyCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
37static const CFDictionaryValueCallBacks __kCFNullDictionaryValueCallBacks = {0, NULL, NULL, NULL, NULL};
38
39static const uint32_t __CFDictionaryCapacities[42] = {
40 4, 8, 17, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349,
41 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498,
42 3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324,
43 228826127, 370248451, 599074578, 969323029, 1568397607, 2537720636U
44};
45
46static const uint32_t __CFDictionaryBuckets[42] = { // primes
47 5, 11, 23, 41, 67, 113, 199, 317, 521, 839, 1361, 2207, 3571, 5779, 9349, 15121,
48 24473, 39607, 64081, 103681, 167759, 271429, 439199, 710641, 1149857, 1860503, 3010349,
49 4870843, 7881193, 12752029, 20633237, 33385273, 54018521, 87403763, 141422317, 228826121,
50 370248451, 599074561, 969323023, 1568397599, 2537720629U, 4106118251U
51};
52
53CF_INLINE CFIndex __CFDictionaryRoundUpCapacity(CFIndex capacity) {
54 CFIndex idx;
55 for (idx = 0; idx < 42 && __CFDictionaryCapacities[idx] < (uint32_t)capacity; idx++);
56 if (42 <= idx) HALT;
57 return __CFDictionaryCapacities[idx];
58}
59
60CF_INLINE CFIndex __CFDictionaryNumBucketsForCapacity(CFIndex capacity) {
61 CFIndex idx;
62 for (idx = 0; idx < 42 && __CFDictionaryCapacities[idx] < (uint32_t)capacity; idx++);
63 if (42 <= idx) HALT;
64 return __CFDictionaryBuckets[idx];
65}
66
67enum { /* Bits 1-0 */
68 __kCFDictionaryImmutable = 0, /* unchangable and fixed capacity */
69 __kCFDictionaryMutable = 1, /* changeable and variable capacity */
70 __kCFDictionaryFixedMutable = 3 /* changeable and fixed capacity */
71};
72
73enum { /* Bits 5-4 (value), 3-2 (key) */
74 __kCFDictionaryHasNullCallBacks = 0,
75 __kCFDictionaryHasCFTypeCallBacks = 1,
76 __kCFDictionaryHasCustomCallBacks = 3 /* callbacks are at end of header */
77};
78
79struct __CFDictionary {
80 CFRuntimeBase _base;
81 CFIndex _count; /* number of values */
82 CFIndex _capacity; /* maximum number of values */
83 CFIndex _bucketsNum; /* number of slots */
84 uintptr_t _marker;
85 void *_context; /* private */
86 CFIndex _deletes;
87 const void **_keys; /* can be NULL if not allocated yet */
88 const void **_values; /* can be NULL if not allocated yet */
89};
90
91/* Bits 1-0 of the base reserved bits are used for mutability variety */
92/* Bits 3-2 of the base reserved bits are used for key callback indicator bits */
93/* Bits 5-4 of the base reserved bits are used for value callback indicator bits */
94/* Bit 6 is special KVO actions bit */
95
96CF_INLINE CFIndex __CFDictionaryGetType(CFDictionaryRef dict) {
97 return __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 1, 0);
98}
99
100CF_INLINE CFIndex __CFDictionaryGetSizeOfType(CFIndex t) {
101 CFIndex size = sizeof(struct __CFDictionary);
102 if (__CFBitfieldGetValue(t, 3, 2) == __kCFDictionaryHasCustomCallBacks) {
103 size += sizeof(CFDictionaryKeyCallBacks);
104 }
105 if (__CFBitfieldGetValue(t, 5, 4) == __kCFDictionaryHasCustomCallBacks) {
106 size += sizeof(CFDictionaryValueCallBacks);
107 }
108 return size;
109}
110
111CF_INLINE const CFDictionaryKeyCallBacks *__CFDictionaryGetKeyCallBacks(CFDictionaryRef dict) {
112 CFDictionaryKeyCallBacks *result = NULL;
113 switch (__CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
114 case __kCFDictionaryHasNullCallBacks:
115 return &__kCFNullDictionaryKeyCallBacks;
116 case __kCFDictionaryHasCFTypeCallBacks:
117 return &kCFTypeDictionaryKeyCallBacks;
118 case __kCFDictionaryHasCustomCallBacks:
119 break;
120 }
121 result = (CFDictionaryKeyCallBacks *)((uint8_t *)dict + sizeof(struct __CFDictionary));
122 return result;
123}
124
125CF_INLINE bool __CFDictionaryKeyCallBacksMatchNull(const CFDictionaryKeyCallBacks *c) {
126 return (NULL == c ||
127 (c->retain == __kCFNullDictionaryKeyCallBacks.retain &&
128 c->release == __kCFNullDictionaryKeyCallBacks.release &&
129 c->copyDescription == __kCFNullDictionaryKeyCallBacks.copyDescription &&
130 c->equal == __kCFNullDictionaryKeyCallBacks.equal &&
131 c->hash == __kCFNullDictionaryKeyCallBacks.hash));
132}
133
134CF_INLINE bool __CFDictionaryKeyCallBacksMatchCFType(const CFDictionaryKeyCallBacks *c) {
135 return (&kCFTypeDictionaryKeyCallBacks == c ||
136 (c->retain == kCFTypeDictionaryKeyCallBacks.retain &&
137 c->release == kCFTypeDictionaryKeyCallBacks.release &&
138 c->copyDescription == kCFTypeDictionaryKeyCallBacks.copyDescription &&
139 c->equal == kCFTypeDictionaryKeyCallBacks.equal &&
140 c->hash == kCFTypeDictionaryKeyCallBacks.hash));
141}
142
143CF_INLINE const CFDictionaryValueCallBacks *__CFDictionaryGetValueCallBacks(CFDictionaryRef dict) {
144 CFDictionaryValueCallBacks *result = NULL;
145 switch (__CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 5, 4)) {
146 case __kCFDictionaryHasNullCallBacks:
147 return &__kCFNullDictionaryValueCallBacks;
148 case __kCFDictionaryHasCFTypeCallBacks:
149 return &kCFTypeDictionaryValueCallBacks;
150 case __kCFDictionaryHasCustomCallBacks:
151 break;
152 }
153 if (__CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2) == __kCFDictionaryHasCustomCallBacks) {
154 result = (CFDictionaryValueCallBacks *)((uint8_t *)dict + sizeof(struct __CFDictionary) + sizeof(CFDictionaryKeyCallBacks));
155 } else {
156 result = (CFDictionaryValueCallBacks *)((uint8_t *)dict + sizeof(struct __CFDictionary));
157 }
158 return result;
159}
160
161CF_INLINE bool __CFDictionaryValueCallBacksMatchNull(const CFDictionaryValueCallBacks *c) {
162 return (NULL == c ||
163 (c->retain == __kCFNullDictionaryValueCallBacks.retain &&
164 c->release == __kCFNullDictionaryValueCallBacks.release &&
165 c->copyDescription == __kCFNullDictionaryValueCallBacks.copyDescription &&
166 c->equal == __kCFNullDictionaryValueCallBacks.equal));
167}
168
169CF_INLINE bool __CFDictionaryValueCallBacksMatchCFType(const CFDictionaryValueCallBacks *c) {
170 return (&kCFTypeDictionaryValueCallBacks == c ||
171 (c->retain == kCFTypeDictionaryValueCallBacks.retain &&
172 c->release == kCFTypeDictionaryValueCallBacks.release &&
173 c->copyDescription == kCFTypeDictionaryValueCallBacks.copyDescription &&
174 c->equal == kCFTypeDictionaryValueCallBacks.equal));
175}
176
177CFIndex _CFDictionaryGetKVOBit(CFDictionaryRef dict) {
178 return __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 6, 6);
179}
180
181void _CFDictionarySetKVOBit(CFDictionaryRef dict, CFIndex bit) {
182 __CFBitfieldSetValue(((CFRuntimeBase *)dict)->_info, 6, 6, (bit & 0x1));
183}
184
185#if !defined(__MACH__)
186
187#define CF_OBJC_KVO_WILLCHANGE(obj, sel, a1)
188#define CF_OBJC_KVO_DIDCHANGE(obj, sel, a1)
189
190#else
191
192static SEL __CF_KVO_WillChangeSelector = 0;
193static SEL __CF_KVO_DidChangeSelector = 0;
194
195#define CF_OBJC_KVO_WILLCHANGE(obj, key) \
196 if (__CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 6, 6)) \
197 {void (*func)(const void *, SEL, ...) = (void *)__CFSendObjCMsg; \
198 if (!__CF_KVO_WillChangeSelector) __CF_KVO_WillChangeSelector = __CFGetObjCSelector("willChangeValueForKey:"); \
199 func((const void *)(obj), __CF_KVO_WillChangeSelector, (key));}
200
201#define CF_OBJC_KVO_DIDCHANGE(obj, key) \
202 if (__CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 6, 6)) \
203 {void (*func)(const void *, SEL, ...) = (void *)__CFSendObjCMsg; \
204 if (!__CF_KVO_DidChangeSelector) __CF_KVO_DidChangeSelector = __CFGetObjCSelector("didChangeValueForKey:"); \
205 func((const void *)(obj), __CF_KVO_DidChangeSelector, (key));}
206
207#endif
208
209
210static CFIndex __CFDictionaryFindBuckets1a(CFDictionaryRef dict, const void *key) {
211 CFHashCode keyHash = (CFHashCode)key;
212 const void **keys = dict->_keys;
213 uintptr_t marker = dict->_marker;
214 CFIndex probe = keyHash % dict->_bucketsNum;
215 CFIndex probeskip = 1; // See RemoveValue() for notes before changing this value
216 CFIndex start = probe;
217 for (;;) {
218 uintptr_t currKey = (uintptr_t)keys[probe];
219 if (marker == currKey) { /* empty */
220 return kCFNotFound;
221 } else if (~marker == currKey) { /* deleted */
222 /* do nothing */
223 } else if (currKey == (uintptr_t)key) {
224 return probe;
225 }
226 probe = probe + probeskip;
227 // This alternative to probe % buckets assumes that
228 // probeskip is always positive and less than the
229 // number of buckets.
230 if (dict->_bucketsNum <= probe) {
231 probe -= dict->_bucketsNum;
232 }
233 if (start == probe) {
234 return kCFNotFound;
235 }
236 }
237}
238
239static CFIndex __CFDictionaryFindBuckets1b(CFDictionaryRef dict, const void *key) {
240 const CFDictionaryKeyCallBacks *cb = __CFDictionaryGetKeyCallBacks(dict);
241 CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, dict->_context) : (CFHashCode)key;
242 const void **keys = dict->_keys;
243 uintptr_t marker = dict->_marker;
244 CFIndex probe = keyHash % dict->_bucketsNum;
245 CFIndex probeskip = 1; // See RemoveValue() for notes before changing this value
246 CFIndex start = probe;
247 for (;;) {
248 uintptr_t currKey = (uintptr_t)keys[probe];
249 if (marker == currKey) { /* empty */
250 return kCFNotFound;
251 } else if (~marker == currKey) { /* deleted */
252 /* do nothing */
253 } else if (currKey == (uintptr_t)key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(void *, void *, void*))cb->equal, currKey, key, dict->_context))) {
254 return probe;
255 }
256 probe = probe + probeskip;
257 // This alternative to probe % buckets assumes that
258 // probeskip is always positive and less than the
259 // number of buckets.
260 if (dict->_bucketsNum <= probe) {
261 probe -= dict->_bucketsNum;
262 }
263 if (start == probe) {
264 return kCFNotFound;
265 }
266 }
267}
268
269static void __CFDictionaryFindBuckets2(CFDictionaryRef dict, const void *key, CFIndex *match, CFIndex *nomatch) {
270 const CFDictionaryKeyCallBacks *cb = __CFDictionaryGetKeyCallBacks(dict);
271 CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, dict->_context) : (CFHashCode)key;
272 const void **keys = dict->_keys;
273 uintptr_t marker = dict->_marker;
274 CFIndex probe = keyHash % dict->_bucketsNum;
275 CFIndex probeskip = 1; // See RemoveValue() for notes before changing this value
276 CFIndex start = probe;
277 *match = kCFNotFound;
278 *nomatch = kCFNotFound;
279 for (;;) {
280 uintptr_t currKey = (uintptr_t)keys[probe];
281 if (marker == currKey) { /* empty */
282 if (kCFNotFound == *nomatch) *nomatch = probe;
283 return;
284 } else if (~marker == currKey) { /* deleted */
285 if (kCFNotFound == *nomatch) *nomatch = probe;
286 if (kCFNotFound != *match) {
287 return;
288 }
289 } else if (kCFNotFound == *match && (currKey == (uintptr_t)key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(void *, void *, void*))cb->equal, currKey, key, dict->_context)))) {
290 *match = probe;
291 if (kCFNotFound != *nomatch) {
292 return;
293 }
294 }
295 probe = probe + probeskip;
296 // This alternative to probe % buckets assumes that
297 // probeskip is always positive and less than the
298 // number of buckets.
299 if (dict->_bucketsNum <= probe) {
300 probe -= dict->_bucketsNum;
301 }
302 if (start == probe) {
303 return;
304 }
305 }
306}
307
308static void __CFDictionaryFindNewMarker(CFDictionaryRef dict) {
309 const void **keys = dict->_keys;
310 uintptr_t newMarker;
311 CFIndex idx, nbuckets;
312 bool hit;
313
314 nbuckets = dict->_bucketsNum;
315 newMarker = dict->_marker;
316 do {
317 newMarker--;
318 hit = false;
319 for (idx = 0; idx < nbuckets; idx++) {
320 if (newMarker == (uintptr_t)keys[idx] || ~newMarker == (uintptr_t)keys[idx]) {
321 hit = true;
322 break;
323 }
324 }
325 } while (hit);
326 for (idx = 0; idx < nbuckets; idx++) {
327 if (dict->_marker == (uintptr_t)keys[idx]) {
328 keys[idx] = (const void *)newMarker;
329 } else if (~dict->_marker == (uintptr_t)keys[idx]) {
330 keys[idx] = (const void *)~newMarker;
331 }
332 }
333 ((struct __CFDictionary *)dict)->_marker = newMarker;
334}
335
336static bool __CFDictionaryEqual(CFTypeRef cf1, CFTypeRef cf2) {
337 CFDictionaryRef dict1 = (CFDictionaryRef)cf1;
338 CFDictionaryRef dict2 = (CFDictionaryRef)cf2;
339 const CFDictionaryKeyCallBacks *cb1, *cb2;
340 const CFDictionaryValueCallBacks *vcb1, *vcb2;
341 const void **keys;
342 CFIndex idx, nbuckets;
343 if (dict1 == dict2) return true;
344 if (dict1->_count != dict2->_count) return false;
345 cb1 = __CFDictionaryGetKeyCallBacks(dict1);
346 cb2 = __CFDictionaryGetKeyCallBacks(dict2);
347 if (cb1->equal != cb2->equal) return false;
348 vcb1 = __CFDictionaryGetValueCallBacks(dict1);
349 vcb2 = __CFDictionaryGetValueCallBacks(dict2);
350 if (vcb1->equal != vcb2->equal) return false;
351 if (0 == dict1->_count) return true; /* after function comparison! */
352 keys = dict1->_keys;
353 nbuckets = dict1->_bucketsNum;
354 for (idx = 0; idx < nbuckets; idx++) {
355 if (dict1->_marker != (uintptr_t)keys[idx] && ~dict1->_marker != (uintptr_t)keys[idx]) {
356 const void *value;
357 if (!CFDictionaryGetValueIfPresent(dict2, keys[idx], &value)) return false;
358 if (dict1->_values[idx] != value && vcb1->equal && !INVOKE_CALLBACK3((Boolean (*)(void *, void *, void*))vcb1->equal, dict1->_values[idx], value, dict1->_context)) {
359 return false;
360 }
361 }
362 }
363 return true;
364}
365
366static CFHashCode __CFDictionaryHash(CFTypeRef cf) {
367 CFDictionaryRef dict = (CFDictionaryRef)cf;
368 return dict->_count;
369}
370
371static CFStringRef __CFDictionaryCopyDescription(CFTypeRef cf) {
372 CFDictionaryRef dict = (CFDictionaryRef)cf;
373 CFAllocatorRef allocator;
374 const CFDictionaryKeyCallBacks *cb;
375 const CFDictionaryValueCallBacks *vcb;
376 const void **keys;
377 CFIndex idx, nbuckets;
378 CFMutableStringRef result;
379 cb = __CFDictionaryGetKeyCallBacks(dict);
380 vcb = __CFDictionaryGetValueCallBacks(dict);
381 keys = dict->_keys;
382 nbuckets = dict->_bucketsNum;
383 allocator = CFGetAllocator(dict);
384 result = CFStringCreateMutable(allocator, 0);
385 switch (__CFDictionaryGetType(dict)) {
386 case __kCFDictionaryImmutable:
387 CFStringAppendFormat(result, NULL, CFSTR("<CFDictionary %p [%p]>{type = immutable, count = %u, capacity = %u, pairs = (\n"), cf, allocator, dict->_count, dict->_capacity);
388 break;
389 case __kCFDictionaryFixedMutable:
390 CFStringAppendFormat(result, NULL, CFSTR("<CFDictionary %p [%p]>{type = fixed-mutable, count = %u, capacity = %u, pairs = (\n"), cf, allocator, dict->_count, dict->_capacity);
391 break;
392 case __kCFDictionaryMutable:
393 CFStringAppendFormat(result, NULL, CFSTR("<CFDictionary %p [%p]>{type = mutable, count = %u, capacity = %u, pairs = (\n"), cf, allocator, dict->_count, dict->_capacity);
394 break;
395 }
396 for (idx = 0; idx < nbuckets; idx++) {
397 if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
398 CFStringRef kDesc = NULL, vDesc = NULL;
399 if (NULL != cb->copyDescription) {
400 kDesc = (CFStringRef)INVOKE_CALLBACK2(((CFStringRef (*)(const void *, void *))cb->copyDescription), keys[idx], dict->_context);
401 }
402 if (NULL != vcb->copyDescription) {
403 vDesc = (CFStringRef)INVOKE_CALLBACK2(((CFStringRef (*)(const void *, void *))vcb->copyDescription), dict->_values[idx], dict->_context);
404 }
405 if (NULL != kDesc && NULL != vDesc) {
406 CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@ = %@\n"), idx, kDesc, vDesc);
407 CFRelease(kDesc);
408 CFRelease(vDesc);
409 } else if (NULL != kDesc) {
410 CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@ = <%p>\n"), idx, kDesc, dict->_values[idx]);
411 CFRelease(kDesc);
412 } else if (NULL != vDesc) {
413 CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p> = %@\n"), idx, keys[idx], vDesc);
414 CFRelease(vDesc);
415 } else {
416 CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p> = <%p>\n"), idx, keys[idx], dict->_values[idx]);
417 }
418 }
419 }
420 CFStringAppend(result, CFSTR(")}"));
421 return result;
422}
423
424static void __CFDictionaryDeallocate(CFTypeRef cf) {
425 CFMutableDictionaryRef dict = (CFMutableDictionaryRef)cf;
426 CFAllocatorRef allocator = __CFGetAllocator(dict);
427 if (__CFDictionaryGetType(dict) == __kCFDictionaryImmutable) {
428 __CFBitfieldSetValue(((CFRuntimeBase *)dict)->_info, 1, 0, __kCFDictionaryFixedMutable);
429 }
430 CFDictionaryRemoveAllValues(dict);
431 if (__CFDictionaryGetType(dict) == __kCFDictionaryMutable && dict->_keys) {
432 CFAllocatorDeallocate(allocator, dict->_keys);
433 }
434}
435
436static CFTypeID __kCFDictionaryTypeID = _kCFRuntimeNotATypeID;
437
438static const CFRuntimeClass __CFDictionaryClass = {
439 0,
440 "CFDictionary",
441 NULL, // init
442 NULL, // copy
443 __CFDictionaryDeallocate,
444 (void *)__CFDictionaryEqual,
445 __CFDictionaryHash,
446 NULL, //
447 __CFDictionaryCopyDescription
448};
449
450__private_extern__ void __CFDictionaryInitialize(void) {
451 __kCFDictionaryTypeID = _CFRuntimeRegisterClass(&__CFDictionaryClass);
452}
453
454CFTypeID CFDictionaryGetTypeID(void) {
455 return __kCFDictionaryTypeID;
456}
457
458static CFDictionaryRef __CFDictionaryInit(CFAllocatorRef allocator, uint32_t flags, CFIndex capacity, const CFDictionaryKeyCallBacks *callBacks, const CFDictionaryValueCallBacks *valueCallBacks) {
459 struct __CFDictionary *memory;
460 uint32_t size;
461 CFIndex idx;
462 __CFBitfieldSetValue(flags, 31, 2, 0);
463 if (__CFDictionaryKeyCallBacksMatchNull(callBacks)) {
464 __CFBitfieldSetValue(flags, 3, 2, __kCFDictionaryHasNullCallBacks);
465 } else if (__CFDictionaryKeyCallBacksMatchCFType(callBacks)) {
466 __CFBitfieldSetValue(flags, 3, 2, __kCFDictionaryHasCFTypeCallBacks);
467 } else {
468 __CFBitfieldSetValue(flags, 3, 2, __kCFDictionaryHasCustomCallBacks);
469 }
470 if (__CFDictionaryValueCallBacksMatchNull(valueCallBacks)) {
471 __CFBitfieldSetValue(flags, 5, 4, __kCFDictionaryHasNullCallBacks);
472 } else if (__CFDictionaryValueCallBacksMatchCFType(valueCallBacks)) {
473 __CFBitfieldSetValue(flags, 5, 4, __kCFDictionaryHasCFTypeCallBacks);
474 } else {
475 __CFBitfieldSetValue(flags, 5, 4, __kCFDictionaryHasCustomCallBacks);
476 }
477 size = __CFDictionaryGetSizeOfType(flags) - sizeof(CFRuntimeBase);
478 switch (__CFBitfieldGetValue(flags, 1, 0)) {
479 case __kCFDictionaryImmutable:
480 case __kCFDictionaryFixedMutable:
481 size += 2 * __CFDictionaryNumBucketsForCapacity(capacity) * sizeof(const void *);
482 break;
483 case __kCFDictionaryMutable:
484 break;
485 }
486 memory = (struct __CFDictionary *)_CFRuntimeCreateInstance(allocator, __kCFDictionaryTypeID, size, NULL);
487 if (NULL == memory) {
488 return NULL;
489 }
490 __CFBitfieldSetValue(memory->_base._info, 6, 0, flags);
491 memory->_count = 0;
492 memory->_marker = (uintptr_t)0xa1b1c1d3;
493 memory->_context = NULL;
494 memory->_deletes = 0;
495 switch (__CFBitfieldGetValue(flags, 1, 0)) {
496 case __kCFDictionaryImmutable:
497 if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFDictionary (immutable)");
498 memory->_capacity = capacity; /* Don't round up capacity */
499 memory->_bucketsNum = __CFDictionaryNumBucketsForCapacity(memory->_capacity);
500 memory->_keys = (const void **)((uint8_t *)memory + __CFDictionaryGetSizeOfType(flags));
501 memory->_values = (const void **)(memory->_keys + memory->_bucketsNum);
502 for (idx = memory->_bucketsNum; idx--;) {
503 memory->_keys[idx] = (const void *)memory->_marker;
504 }
505 break;
506 case __kCFDictionaryFixedMutable:
507 if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFDictionary (mutable-fixed)");
508 memory->_capacity = capacity; /* Don't round up capacity */
509 memory->_bucketsNum = __CFDictionaryNumBucketsForCapacity(memory->_capacity);
510 memory->_keys = (const void **)((uint8_t *)memory + __CFDictionaryGetSizeOfType(flags));
511 memory->_values = (const void **)(memory->_keys + memory->_bucketsNum);
512 for (idx = memory->_bucketsNum; idx--;) {
513 memory->_keys[idx] = (const void *)memory->_marker;
514 }
515 break;
516 case __kCFDictionaryMutable:
517 if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFDictionary (mutable-variable)");
518 memory->_capacity = __CFDictionaryRoundUpCapacity(1);
519 memory->_bucketsNum = 0;
520 memory->_keys = NULL;
521 memory->_values = NULL;
522 break;
523 }
524 if (__kCFDictionaryHasCustomCallBacks == __CFBitfieldGetValue(flags, 3, 2)) {
525 const CFDictionaryKeyCallBacks *cb = __CFDictionaryGetKeyCallBacks((CFDictionaryRef)memory);
526 *(CFDictionaryKeyCallBacks *)cb = *callBacks;
527 FAULT_CALLBACK((void **)&(cb->retain));
528 FAULT_CALLBACK((void **)&(cb->release));
529 FAULT_CALLBACK((void **)&(cb->copyDescription));
530 FAULT_CALLBACK((void **)&(cb->equal));
531 FAULT_CALLBACK((void **)&(cb->hash));
532 }
533 if (__kCFDictionaryHasCustomCallBacks == __CFBitfieldGetValue(flags, 5, 4)) {
534 const CFDictionaryValueCallBacks *vcb = __CFDictionaryGetValueCallBacks((CFDictionaryRef)memory);
535 *(CFDictionaryValueCallBacks *)vcb = *valueCallBacks;
536 FAULT_CALLBACK((void **)&(vcb->retain));
537 FAULT_CALLBACK((void **)&(vcb->release));
538 FAULT_CALLBACK((void **)&(vcb->copyDescription));
539 FAULT_CALLBACK((void **)&(vcb->equal));
540 }
541 return (CFDictionaryRef)memory;
542}
543
544CFDictionaryRef CFDictionaryCreate(CFAllocatorRef allocator, const void **keys, const void **values, CFIndex numValues, const CFDictionaryKeyCallBacks *keyCallBacks, const CFDictionaryValueCallBacks *valueCallBacks) {
545 CFDictionaryRef result;
546 uint32_t flags;
547 CFIndex idx;
548 CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
549 result = __CFDictionaryInit(allocator, __kCFDictionaryImmutable, numValues, keyCallBacks, valueCallBacks);
550 flags = __CFBitfieldGetValue(((const CFRuntimeBase *)result)->_info, 1, 0);
551 if (flags == __kCFDictionaryImmutable) {
552 __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, __kCFDictionaryFixedMutable);
553 }
554 for (idx = 0; idx < numValues; idx++) {
555 CFDictionaryAddValue((CFMutableDictionaryRef)result, keys[idx], values[idx]);
556 }
557 __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, flags);
558 return result;
559}
560
561CFMutableDictionaryRef CFDictionaryCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFDictionaryKeyCallBacks *keyCallBacks, const CFDictionaryValueCallBacks *valueCallBacks) {
562 CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
563 return (CFMutableDictionaryRef)__CFDictionaryInit(allocator, (0 == capacity) ? __kCFDictionaryMutable : __kCFDictionaryFixedMutable, capacity, keyCallBacks, valueCallBacks);
564}
565
566static void __CFDictionaryGrow(CFMutableDictionaryRef dict, CFIndex numNewValues);
567
568CFDictionaryRef _CFDictionaryCreate_ex(CFAllocatorRef allocator, bool mutable, const void **keys, const void **values, CFIndex numValues) {
569 CFDictionaryRef result;
570 uint32_t flags;
571 CFIndex idx;
572 result = __CFDictionaryInit(allocator, mutable ? __kCFDictionaryMutable : __kCFDictionaryImmutable, numValues, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
573 flags = __CFBitfieldGetValue(((const CFRuntimeBase *)result)->_info, 1, 0);
574 if (!mutable) {
575 __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, __kCFDictionaryFixedMutable);
576 }
577 if (mutable) {
578 if (result->_count == result->_capacity || NULL == result->_keys) {
579 __CFDictionaryGrow((CFMutableDictionaryRef)result, numValues);
580 }
581 }
582 for (idx = 0; idx < numValues; idx++) {
583 CFIndex match, nomatch;
584 const void *newKey;
585 __CFDictionaryFindBuckets2(result, keys[idx], &match, &nomatch);
586 if (kCFNotFound != match) {
587 CFRelease(result->_values[match]);
588 result->_values[match] = values[idx];
589 } else {
590 newKey = keys[idx];
591 if (result->_marker == (uintptr_t)newKey || ~result->_marker == (uintptr_t)newKey) {
592 __CFDictionaryFindNewMarker(result);
593 }
594 result->_keys[nomatch] = newKey;
595 result->_values[nomatch] = values[idx];
596 ((CFMutableDictionaryRef)result)->_count++;
597 }
598 }
599 __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, flags);
600 return result;
601}
602
603CFDictionaryRef CFDictionaryCreateCopy(CFAllocatorRef allocator, CFDictionaryRef dict) {
604 CFDictionaryRef result;
605 const CFDictionaryKeyCallBacks *cb;
606 const CFDictionaryValueCallBacks *vcb;
607 CFIndex numValues = CFDictionaryGetCount(dict);
608 const void **list, *buffer[256];
609 const void **vlist, *vbuffer[256];
610 list = (numValues <= 256) ? buffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0);
611 if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFDictionary (temp)");
612 vlist = (numValues <= 256) ? vbuffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0);
613 if (vlist != vbuffer && __CFOASafe) __CFSetLastAllocationEventName(vlist, "CFDictionary (temp)");
614 CFDictionaryGetKeysAndValues(dict, list, vlist);
615 cb = CF_IS_OBJC(__kCFDictionaryTypeID, dict) ? &kCFTypeDictionaryKeyCallBacks : __CFDictionaryGetKeyCallBacks(dict);
616 vcb = CF_IS_OBJC(__kCFDictionaryTypeID, dict) ? &kCFTypeDictionaryValueCallBacks : __CFDictionaryGetValueCallBacks(dict);
617 result = CFDictionaryCreate(allocator, list, vlist, numValues, cb, vcb);
618 if (list != buffer) CFAllocatorDeallocate(allocator, list);
619 if (vlist != vbuffer) CFAllocatorDeallocate(allocator, vlist);
620 return result;
621}
622
623CFMutableDictionaryRef CFDictionaryCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFDictionaryRef dict) {
624 CFMutableDictionaryRef result;
625 const CFDictionaryKeyCallBacks *cb;
626 const CFDictionaryValueCallBacks *vcb;
627 CFIndex idx, numValues = CFDictionaryGetCount(dict);
628 const void **list, *buffer[256];
629 const void **vlist, *vbuffer[256];
630 CFAssert3(0 == capacity || numValues <= capacity, __kCFLogAssertion, "%s(): for fixed-mutable dicts, capacity (%d) must be greater than or equal to initial number of values (%d)", __PRETTY_FUNCTION__, capacity, numValues);
631 list = (numValues <= 256) ? buffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0);
632 if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFDictionary (temp)");
633 vlist = (numValues <= 256) ? vbuffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0);
634 if (vlist != vbuffer && __CFOASafe) __CFSetLastAllocationEventName(vlist, "CFDictionary (temp)");
635 CFDictionaryGetKeysAndValues(dict, list, vlist);
636 cb = CF_IS_OBJC(__kCFDictionaryTypeID, dict) ? &kCFTypeDictionaryKeyCallBacks : __CFDictionaryGetKeyCallBacks(dict);
637 vcb = CF_IS_OBJC(__kCFDictionaryTypeID, dict) ? &kCFTypeDictionaryValueCallBacks : __CFDictionaryGetValueCallBacks(dict);
638 result = CFDictionaryCreateMutable(allocator, capacity, cb, vcb);
639 if (0 == capacity) _CFDictionarySetCapacity(result, numValues);
640 for (idx = 0; idx < numValues; idx++) {
641 CFDictionaryAddValue(result, list[idx], vlist[idx]);
642 }
643 if (list != buffer) CFAllocatorDeallocate(allocator, list);
644 if (vlist != vbuffer) CFAllocatorDeallocate(allocator, vlist);
645 return result;
646}
647
648// Used by NSMapTables and KVO
649void _CFDictionarySetContext(CFDictionaryRef dict, void *context) {
650 ((struct __CFDictionary *)dict)->_context = context;
651}
652
653void *_CFDictionaryGetContext(CFDictionaryRef dict) {
654 return ((struct __CFDictionary *)dict)->_context;
655}
656
657CFIndex CFDictionaryGetCount(CFDictionaryRef dict) {
658 CF_OBJC_FUNCDISPATCH0(__kCFDictionaryTypeID, CFIndex, dict, "count");
659 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
660 return dict->_count;
661}
662
663CFIndex CFDictionaryGetCountOfKey(CFDictionaryRef dict, const void *key) {
664 CFIndex match;
665 CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, CFIndex, dict, "countForKey:", key);
666 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
667 if (0 == dict->_count) return 0;
668 if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
669 match = __CFDictionaryFindBuckets1a(dict, key);
670 } else {
671 match = __CFDictionaryFindBuckets1b(dict, key);
672 }
673 return (kCFNotFound != match ? 1 : 0);
674}
675
676CFIndex CFDictionaryGetCountOfValue(CFDictionaryRef dict, const void *value) {
677 const void **keys;
678 const CFDictionaryValueCallBacks *vcb;
679 CFIndex idx, cnt = 0, nbuckets;
680 CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, CFIndex, dict, "countForObject:", value);
681 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
682 if (0 == dict->_count) return 0;
683 keys = dict->_keys;
684 nbuckets = dict->_bucketsNum;
685 vcb = __CFDictionaryGetValueCallBacks(dict);
686 for (idx = 0; idx < nbuckets; idx++) {
687 if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
688 if ((dict->_values[idx] == value) || (vcb->equal && INVOKE_CALLBACK3((Boolean (*)(void *, void *, void*))vcb->equal, dict->_values[idx], value, dict->_context))) {
689 cnt++;
690 }
691 }
692 }
693 return cnt;
694}
695
696Boolean CFDictionaryContainsKey(CFDictionaryRef dict, const void *key) {
697 CFIndex match;
698 CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, char, dict, "containsKey:", key);
699 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
700 if (0 == dict->_count) return false;
701 if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
702 match = __CFDictionaryFindBuckets1a(dict, key);
703 } else {
704 match = __CFDictionaryFindBuckets1b(dict, key);
705 }
706 return (kCFNotFound != match ? true : false);
707}
708
709Boolean CFDictionaryContainsValue(CFDictionaryRef dict, const void *value) {
710 const void **keys;
711 const CFDictionaryValueCallBacks *vcb;
712 CFIndex idx, nbuckets;
713 CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, char, dict, "containsObject:", value);
714 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
715 if (0 == dict->_count) return false;
716 keys = dict->_keys;
717 nbuckets = dict->_bucketsNum;
718 vcb = __CFDictionaryGetValueCallBacks(dict);
719 for (idx = 0; idx < nbuckets; idx++) {
720 if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
721 if ((dict->_values[idx] == value) || (vcb->equal && INVOKE_CALLBACK3((Boolean (*)(void *, void *, void*))vcb->equal, dict->_values[idx], value, dict->_context))) {
722 return true;
723 }
724 }
725 }
726 return false;
727}
728
729const void *CFDictionaryGetValue(CFDictionaryRef dict, const void *key) {
730 CFIndex match;
731 CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, const void *, dict, "objectForKey:", key);
732 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
733 if (0 == dict->_count) return NULL;
734 if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
735 match = __CFDictionaryFindBuckets1a(dict, key);
736 } else {
737 match = __CFDictionaryFindBuckets1b(dict, key);
738 }
739 return (kCFNotFound != match ? dict->_values[match] : NULL);
740}
741
742Boolean CFDictionaryGetValueIfPresent(CFDictionaryRef dict, const void *key, const void **value) {
743 CFIndex match;
744 CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, char, dict, "_getValue:forKey:", (void * *)value, key);
745 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
746 if (0 == dict->_count) return false;
747 if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
748 match = __CFDictionaryFindBuckets1a(dict, key);
749 } else {
750 match = __CFDictionaryFindBuckets1b(dict, key);
751 }
752 return (kCFNotFound != match ? ((value ? *value = dict->_values[match] : NULL), true) : false);
753}
754
755bool CFDictionaryGetKeyIfPresent(CFDictionaryRef dict, const void *key, const void **actualkey) {
756 CFIndex match;
757//#warning CF: not toll-free bridged
758 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
759 if (0 == dict->_count) return false;
760 if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
761 match = __CFDictionaryFindBuckets1a(dict, key);
762 } else {
763 match = __CFDictionaryFindBuckets1b(dict, key);
764 }
765 return (kCFNotFound != match ? ((actualkey ? *actualkey = dict->_keys[match] : NULL), true) : false);
766}
767
768void CFDictionaryGetKeysAndValues(CFDictionaryRef dict, const void **keys, const void **values) {
769 CFIndex idx, cnt, nbuckets;
770 CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, void, dict, "getObjects:andKeys:", (void * *)values, (void * *)keys);
771 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
772 nbuckets = dict->_bucketsNum;
773 for (idx = 0; idx < nbuckets; idx++) {
774 if (dict->_marker != (uintptr_t)dict->_keys[idx] && ~dict->_marker != (uintptr_t)dict->_keys[idx]) {
775 for (cnt = 1; cnt--;) {
776 if (keys) *keys++ = dict->_keys[idx];
777 if (values) *values++ = dict->_values[idx];
778 }
779 }
780 }
781}
782
783void CFDictionaryApplyFunction(CFDictionaryRef dict, CFDictionaryApplierFunction applier, void *context) {
784 const void **keys;
785 CFIndex idx, cnt, nbuckets;
786 FAULT_CALLBACK((void **)&(applier));
787 CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, void, dict, "_apply:context:", applier, context);
788 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
789 keys = dict->_keys;
790 nbuckets = dict->_bucketsNum;
791 for (idx = 0; idx < nbuckets; idx++) {
792 if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
793 for (cnt = 1; cnt--;) {
794 INVOKE_CALLBACK3(applier, keys[idx], dict->_values[idx], context);
795 }
796 }
797 }
798}
799
800static void __CFDictionaryGrow(CFMutableDictionaryRef dict, CFIndex numNewValues) {
801 const void **oldkeys = dict->_keys;
802 const void **oldvalues = dict->_values;
803 CFIndex idx, oldnbuckets = dict->_bucketsNum;
804 CFIndex oldCount = dict->_count;
805 dict->_capacity = __CFDictionaryRoundUpCapacity(oldCount + numNewValues);
806 dict->_bucketsNum = __CFDictionaryNumBucketsForCapacity(dict->_capacity);
807 dict->_deletes = 0;
808 dict->_keys = CFAllocatorAllocate(__CFGetAllocator(dict), 2 * dict->_bucketsNum * sizeof(const void *), 0);
809 dict->_values = (const void **)(dict->_keys + dict->_bucketsNum);
810 if (NULL == dict->_keys) HALT;
811 if (__CFOASafe) __CFSetLastAllocationEventName(dict->_keys, "CFDictionary (store)");
812 for (idx = dict->_bucketsNum; idx--;) {
813 dict->_keys[idx] = (const void *)dict->_marker;
814 }
815 if (NULL == oldkeys) return;
816 for (idx = 0; idx < oldnbuckets; idx++) {
817 if (dict->_marker != (uintptr_t)oldkeys[idx] && ~dict->_marker != (uintptr_t)oldkeys[idx]) {
818 CFIndex match, nomatch;
819 __CFDictionaryFindBuckets2(dict, oldkeys[idx], &match, &nomatch);
820 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], dict->_keys[match]);
821 dict->_keys[nomatch] = oldkeys[idx];
822 dict->_values[nomatch] = oldvalues[idx];
823 }
824 }
825 CFAssert1(dict->_count == oldCount, __kCFLogAssertion, "%s(): dict count differs after rehashing; error", __PRETTY_FUNCTION__);
826 CFAllocatorDeallocate(__CFGetAllocator(dict), oldkeys);
827}
828
829// This function is for Foundation's benefit; no one else should use it.
830void _CFDictionarySetCapacity(CFMutableDictionaryRef dict, CFIndex cap) {
831 if (CF_IS_OBJC(__kCFDictionaryTypeID, dict)) return;
832#if defined(DEBUG)
833 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
834 CFAssert1(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable && __CFDictionaryGetType(dict) != __kCFDictionaryFixedMutable, __kCFLogAssertion, "%s(): dict is immutable or fixed-mutable", __PRETTY_FUNCTION__);
835 CFAssert3(dict->_count <= cap, __kCFLogAssertion, "%s(): desired capacity (%d) is less than count (%d)", __PRETTY_FUNCTION__, cap, dict->_count);
836#endif
837 __CFDictionaryGrow(dict, cap - dict->_count);
838}
839
840// This function is for Foundation's benefit; no one else should use it.
841bool _CFDictionaryIsMutable(CFDictionaryRef dict) {
842 return (__CFDictionaryGetType(dict) != __kCFDictionaryImmutable);
843}
844
845void CFDictionaryAddValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
846 CFIndex match, nomatch;
847 const CFDictionaryKeyCallBacks *cb;
848 const CFDictionaryValueCallBacks *vcb;
849 const void *newKey, *newValue;
850 CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, void, dict, "_addObject:forKey:", value, key);
851 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
852 switch (__CFDictionaryGetType(dict)) {
853 case __kCFDictionaryMutable:
854 if (dict->_count == dict->_capacity || NULL == dict->_keys) {
855 __CFDictionaryGrow(dict, 1);
856 }
857 break;
858 case __kCFDictionaryFixedMutable:
859 CFAssert3(dict->_count < dict->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity dict %p (capacity = %d)", __PRETTY_FUNCTION__, dict, dict->_capacity);
860 break;
861 default:
862 CFAssert2(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable, __kCFLogAssertion, "%s(): immutable dict %p passed to mutating operation", __PRETTY_FUNCTION__, dict);
863 break;
864 }
865 __CFDictionaryFindBuckets2(dict, key, &match, &nomatch);
866 if (kCFNotFound != match) {
867 } else {
868 cb = __CFDictionaryGetKeyCallBacks(dict);
869 vcb = __CFDictionaryGetValueCallBacks(dict);
870 if (cb->retain) {
871 newKey = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), __CFGetAllocator(dict), key, dict->_context);
872 } else {
873 newKey = key;
874 }
875 if (vcb->retain) {
876 newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))vcb->retain), __CFGetAllocator(dict), value, dict->_context);
877 } else {
878 newValue = value;
879 }
880 if (dict->_marker == (uintptr_t)newKey || ~dict->_marker == (uintptr_t)newKey) {
881 __CFDictionaryFindNewMarker(dict);
882 }
883 CF_OBJC_KVO_WILLCHANGE(dict, key);
884 dict->_keys[nomatch] = newKey;
885 dict->_values[nomatch] = newValue;
886 dict->_count++;
887 CF_OBJC_KVO_DIDCHANGE(dict, key);
888 }
889}
890
891void CFDictionaryReplaceValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
892 CFIndex match;
893 const CFDictionaryValueCallBacks *vcb;
894 const void *newValue;
895 CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, void, dict, "_replaceObject:forKey:", value, key);
896 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
897 switch (__CFDictionaryGetType(dict)) {
898 case __kCFDictionaryMutable:
899 case __kCFDictionaryFixedMutable:
900 break;
901 default:
902 CFAssert2(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable, __kCFLogAssertion, "%s(): immutable dict %p passed to mutating operation", __PRETTY_FUNCTION__, dict);
903 break;
904 }
905 if (0 == dict->_count) return;
906 if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
907 match = __CFDictionaryFindBuckets1a(dict, key);
908 } else {
909 match = __CFDictionaryFindBuckets1b(dict, key);
910 }
911 if (kCFNotFound == match) return;
912 vcb = __CFDictionaryGetValueCallBacks(dict);
913 if (vcb->retain) {
914 newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))vcb->retain), __CFGetAllocator(dict), value, dict->_context);
915 } else {
916 newValue = value;
917 }
918 CF_OBJC_KVO_WILLCHANGE(dict, key);
919 if (vcb->release) {
920 INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), __CFGetAllocator(dict), dict->_values[match], dict->_context);
921 }
922 dict->_values[match] = newValue;
923 CF_OBJC_KVO_DIDCHANGE(dict, key);
924}
925
926void CFDictionarySetValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
927 CFIndex match, nomatch;
928 const CFDictionaryKeyCallBacks *cb;
929 const CFDictionaryValueCallBacks *vcb;
930 const void *newKey, *newValue;
931 CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, void, dict, "setObject:forKey:", value, key);
932 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
933 switch (__CFDictionaryGetType(dict)) {
934 case __kCFDictionaryMutable:
935 if (dict->_count == dict->_capacity || NULL == dict->_keys) {
936 __CFDictionaryGrow(dict, 1);
937 }
938 break;
939 case __kCFDictionaryFixedMutable:
940 break;
941 default:
942 CFAssert2(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable, __kCFLogAssertion, "%s(): immutable dict %p passed to mutating operation", __PRETTY_FUNCTION__, dict);
943 break;
944 }
945 __CFDictionaryFindBuckets2(dict, key, &match, &nomatch);
946 vcb = __CFDictionaryGetValueCallBacks(dict);
947 if (vcb->retain) {
948 newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))vcb->retain), __CFGetAllocator(dict), value, dict->_context);
949 } else {
950 newValue = value;
951 }
952 if (kCFNotFound != match) {
953 CF_OBJC_KVO_WILLCHANGE(dict, key);
954 if (vcb->release) {
955 INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), __CFGetAllocator(dict), dict->_values[match], dict->_context);
956 }
957 dict->_values[match] = newValue;
958 CF_OBJC_KVO_DIDCHANGE(dict, key);
959 } else {
960 CFAssert3(__kCFDictionaryFixedMutable != __CFDictionaryGetType(dict) || dict->_count < dict->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity dict %p (capacity = %d)", __PRETTY_FUNCTION__, dict, dict->_capacity);
961 cb = __CFDictionaryGetKeyCallBacks(dict);
962 if (cb->retain) {
963 newKey = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), __CFGetAllocator(dict), key, dict->_context);
964 } else {
965 newKey = key;
966 }
967 if (dict->_marker == (uintptr_t)newKey || ~dict->_marker == (uintptr_t)newKey) {
968 __CFDictionaryFindNewMarker(dict);
969 }
970 CF_OBJC_KVO_WILLCHANGE(dict, key);
971 dict->_keys[nomatch] = newKey;
972 dict->_values[nomatch] = newValue;
973 dict->_count++;
974 CF_OBJC_KVO_DIDCHANGE(dict, key);
975 }
976}
977
978void CFDictionaryRemoveValue(CFMutableDictionaryRef dict, const void *key) {
979 CFIndex match;
980 const CFDictionaryKeyCallBacks *cb;
981 const CFDictionaryValueCallBacks *vcb;
982 CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, void, dict, "removeObjectForKey:", key);
983 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
984 switch (__CFDictionaryGetType(dict)) {
985 case __kCFDictionaryMutable:
986 case __kCFDictionaryFixedMutable:
987 break;
988 default:
989 CFAssert2(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable, __kCFLogAssertion, "%s(): immutable dict %p passed to mutating operation", __PRETTY_FUNCTION__, dict);
990 break;
991 }
992 if (0 == dict->_count) return;
993 if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
994 match = __CFDictionaryFindBuckets1a(dict, key);
995 } else {
996 match = __CFDictionaryFindBuckets1b(dict, key);
997 }
998 if (kCFNotFound == match) return;
999 if (1) {
1000 cb = __CFDictionaryGetKeyCallBacks(dict);
1001 vcb = __CFDictionaryGetValueCallBacks(dict);
1002 const void *oldkey = dict->_keys[match];
1003 CF_OBJC_KVO_WILLCHANGE(dict, oldkey);
1004 if (vcb->release) {
1005 INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), __CFGetAllocator(dict), dict->_values[match], dict->_context);
1006 }
1007 dict->_keys[match] = (const void *)~dict->_marker;
1008 dict->_count--;
1009 CF_OBJC_KVO_DIDCHANGE(dict, oldkey);
1010 if (cb->release) {
1011 INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), __CFGetAllocator(dict), oldkey, dict->_context);
1012 }
1013 dict->_deletes++;
1014 // _CFDictionaryDecrementValue() below has this same code.
1015 if ((__kCFDictionaryMutable == __CFDictionaryGetType(dict)) && (dict->_bucketsNum < 4 * dict->_deletes || (512 < dict->_capacity && 3.236067 * dict->_count < dict->_capacity))) {
1016 // 3.236067 == 2 * golden_mean; this comes about because we're trying to resize down
1017 // when the count is less than 2 capacities smaller, but not right away when count
1018 // is just less than 2 capacities smaller, because an add would then force growth;
1019 // well, the ratio between one capacity and the previous is close to the golden
1020 // mean currently, so (cap / m / m) would be two smaller; but so we're not close,
1021 // we take the average of that and the prior cap (cap / m / m / m). Well, after one
1022 // does the algebra, and uses the convenient fact that m^(x+2) = m^(x+1) + m^x if m
1023 // is the golden mean, this reduces to cap / 2m for the threshold. In general, the
1024 // possible threshold constant is 1 / (2 * m^k), k = 0, 1, 2, ... under this scheme.
1025 // Rehash; currently only for mutable-variable dictionaries
1026 __CFDictionaryGrow(dict, 0);
1027 } else {
1028 // When the probeskip == 1 always and only, a DELETED slot followed by an EMPTY slot
1029 // can be converted to an EMPTY slot. By extension, a chain of DELETED slots followed
1030 // by an EMPTY slot can be converted to EMPTY slots, which is what we do here.
1031 // _CFDictionaryDecrementValue() below has this same code.
1032 if (match < dict->_bucketsNum - 1 && dict->_keys[match + 1] == (const void *)dict->_marker) {
1033 while (0 <= match && dict->_keys[match] == (const void *)~dict->_marker) {
1034 dict->_keys[match] = (const void *)dict->_marker;
1035 dict->_deletes--;
1036 match--;
1037 }
1038 }
1039 }
1040 }
1041}
1042
1043void CFDictionaryRemoveAllValues(CFMutableDictionaryRef dict) {
1044 const void **keys;
1045 const CFDictionaryKeyCallBacks *cb;
1046 const CFDictionaryValueCallBacks *vcb;
1047 CFAllocatorRef allocator;
1048 CFIndex idx, nbuckets;
1049 CF_OBJC_FUNCDISPATCH0(__kCFDictionaryTypeID, void, dict, "removeAllObjects");
1050 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
1051 switch (__CFDictionaryGetType(dict)) {
1052 case __kCFDictionaryMutable:
1053 case __kCFDictionaryFixedMutable:
1054 break;
1055 default:
1056 CFAssert2(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable, __kCFLogAssertion, "%s(): immutable dict %p passed to mutating operation", __PRETTY_FUNCTION__, dict);
1057 break;
1058 }
1059 if (0 == dict->_count) return;
1060 keys = dict->_keys;
1061 nbuckets = dict->_bucketsNum;
1062 cb = __CFDictionaryGetKeyCallBacks(dict);
1063 vcb = __CFDictionaryGetValueCallBacks(dict);
1064 allocator = __CFGetAllocator(dict);
1065 for (idx = 0; idx < nbuckets; idx++) {
1066 if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
1067 const void *oldkey = keys[idx];
1068 CF_OBJC_KVO_WILLCHANGE(dict, oldkey);
1069 if (vcb->release) {
1070 INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), allocator, dict->_values[idx], dict->_context);
1071 }
1072 keys[idx] = (const void *)~dict->_marker;
1073 dict->_count--;
1074 CF_OBJC_KVO_DIDCHANGE(dict, oldkey);
1075 if (cb->release) {
1076 INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), allocator, oldkey, dict->_context);
1077 }
1078 }
1079 }
1080 for (idx = 0; idx < nbuckets; idx++) {
1081 keys[idx] = (const void *)dict->_marker;
1082 }
1083 dict->_count = 0;
1084 dict->_deletes = 0;
1085 if ((__kCFDictionaryMutable == __CFDictionaryGetType(dict)) && (512 < dict->_capacity)) {
1086 __CFDictionaryGrow(dict, 256);
1087 }
1088}
1089
1090void _CFDictionaryIncrementValue(CFMutableDictionaryRef dict, const void *key) {
1091 CFIndex match, nomatch;
1092
1093 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
1094 CFAssert1(__CFDictionaryGetType(dict) == __kCFDictionaryMutable, __kCFLogAssertion, "%s(): invalid dict type passed to increment operation", __PRETTY_FUNCTION__);
1095 CFAssert1(__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2), __kCFLogAssertion, "%s(): invalid dict passed to increment operation", __PRETTY_FUNCTION__);
1096 CFAssert1(__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 5, 4), __kCFLogAssertion, "%s(): invalid dict passed to increment operation", __PRETTY_FUNCTION__);
1097
1098 match = kCFNotFound;
1099 if (NULL != dict->_keys) {
1100 __CFDictionaryFindBuckets2(dict, key, &match, &nomatch);
1101 }
1102 if (kCFNotFound != match) {
1103 if (dict->_values[match] != (void *)UINT_MAX) {
1104 dict->_values[match] = (void *)((uintptr_t)dict->_values[match] + 1);
1105 }
1106 } else {
1107 if (dict->_marker == (uintptr_t)key || ~dict->_marker == (uintptr_t)key) {
1108 __CFDictionaryFindNewMarker(dict);
1109 }
1110 if (dict->_count == dict->_capacity || NULL == dict->_keys) {
1111 __CFDictionaryGrow(dict, 1);
1112 __CFDictionaryFindBuckets2(dict, key, &match, &nomatch);
1113 }
1114 dict->_keys[nomatch] = key;
1115 dict->_values[nomatch] = (void *)1;
1116 dict->_count++;
1117 }
1118}
1119
1120int _CFDictionaryDecrementValue(CFMutableDictionaryRef dict, const void *key) {
1121 CFIndex match;
1122
1123 __CFGenericValidateType(dict, __kCFDictionaryTypeID);
1124 CFAssert1(__CFDictionaryGetType(dict) == __kCFDictionaryMutable, __kCFLogAssertion, "%s(): invalid dict type passed to increment operation", __PRETTY_FUNCTION__);
1125 CFAssert1(__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2), __kCFLogAssertion, "%s(): invalid dict passed to increment operation", __PRETTY_FUNCTION__);
1126 CFAssert1(__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 5, 4), __kCFLogAssertion, "%s(): invalid dict passed to increment operation", __PRETTY_FUNCTION__);
1127
1128 if (0 == dict->_count) return -1;
1129 match = __CFDictionaryFindBuckets1a(dict, key);
1130 if (kCFNotFound == match) return -1;
1131 if (1 == (uintptr_t)dict->_values[match]) {
1132 dict->_count--;
1133 dict->_values[match] = 0;
1134 dict->_keys[match] = (const void *)~dict->_marker;
1135 dict->_deletes++;
1136 if ((__kCFDictionaryMutable == __CFDictionaryGetType(dict)) && (dict->_bucketsNum < 4 * dict->_deletes || (512 < dict->_capacity && 3.236067 * dict->_count < dict->_capacity))) {
1137 __CFDictionaryGrow(dict, 0);
1138 } else {
1139 if (match < dict->_bucketsNum - 1 && dict->_keys[match + 1] == (const void *)dict->_marker) {
1140 while (0 <= match && dict->_keys[match] == (const void *)~dict->_marker) {
1141 dict->_keys[match] = (const void *)dict->_marker;
1142 dict->_deletes--;
1143 match--;
1144 }
1145 }
1146 }
1147 return 0;
1148 } else if (dict->_values[match] != (void *)UINT_MAX) {
1149 dict->_values[match] = (void *)((uintptr_t)dict->_values[match] - 1);
1150 }
1151 return 1;
1152}
1153
mirror of CF