CFDictionary.c   [plain text]

/*
 * Copyright (c) 2005 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/*	CFDictionary.c
	Copyright 1998-2002, Apple, Inc. All rights reserved.
	Responsibility: Christopher Kane
*/

#include <CoreFoundation/CFDictionary.h>
#include "CFInternal.h"

const CFDictionaryKeyCallBacks kCFTypeDictionaryKeyCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
const CFDictionaryKeyCallBacks kCFCopyStringDictionaryKeyCallBacks = {0, (void *)CFStringCreateCopy, __CFTypeCollectionRelease, CFCopyDescription, CFEqual, CFHash};
const CFDictionaryValueCallBacks kCFTypeDictionaryValueCallBacks = {0, __CFTypeCollectionRetain, __CFTypeCollectionRelease, CFCopyDescription, CFEqual};
static const CFDictionaryKeyCallBacks __kCFNullDictionaryKeyCallBacks = {0, NULL, NULL, NULL, NULL, NULL};
static const CFDictionaryValueCallBacks __kCFNullDictionaryValueCallBacks = {0, NULL, NULL, NULL, NULL};

static const uint32_t __CFDictionaryCapacities[42] = {
    4, 8, 17, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349,
    15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498,
    3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324,
    228826127, 370248451, 599074578, 969323029, 1568397607, 2537720636U
};

static const uint32_t __CFDictionaryBuckets[42] = {	// primes
    5, 11, 23, 41, 67, 113, 199, 317, 521, 839, 1361, 2207, 3571, 5779, 9349, 15121,
    24473, 39607, 64081, 103681, 167759, 271429, 439199, 710641, 1149857, 1860503, 3010349,
    4870843, 7881193, 12752029, 20633237, 33385273, 54018521, 87403763, 141422317, 228826121,
    370248451, 599074561, 969323023, 1568397599, 2537720629U, 4106118251U
};

CF_INLINE CFIndex __CFDictionaryRoundUpCapacity(CFIndex capacity) {
    CFIndex idx;
    for (idx = 0; idx < 42 && __CFDictionaryCapacities[idx] < (uint32_t)capacity; idx++);
    if (42 <= idx) HALT;
    return __CFDictionaryCapacities[idx];
}

CF_INLINE CFIndex __CFDictionaryNumBucketsForCapacity(CFIndex capacity) {
    CFIndex idx;
    for (idx = 0; idx < 42 && __CFDictionaryCapacities[idx] < (uint32_t)capacity; idx++);
    if (42 <= idx) HALT;
    return __CFDictionaryBuckets[idx];
}

enum {		/* Bits 1-0 */
    __kCFDictionaryImmutable = 0,	/* unchangable and fixed capacity */
    __kCFDictionaryMutable = 1,		/* changeable and variable capacity */
    __kCFDictionaryFixedMutable = 3	/* changeable and fixed capacity */
};

enum {		/* Bits 5-4 (value), 3-2 (key) */
    __kCFDictionaryHasNullCallBacks = 0,
    __kCFDictionaryHasCFTypeCallBacks = 1,
    __kCFDictionaryHasCustomCallBacks = 3	/* callbacks are at end of header */
};

// Under GC, we fudge the key/value memory in two ways
// First, if we had null callbacks or null for both retain/release, we use unscanned memory
// This means that if people were doing addValue:[xxx new] and never removing, well, that doesn't work
//
// Second, if we notice standard retain/release implementations we substitute scanned memory
// and zero out the retain/release callbacks.  This is fine, but when copying we need to restore them

enum {
    __kCFDictionaryRestoreKeys =       (1 << 0),
    __kCFDictionaryRestoreValues =     (1 << 1),
    __kCFDictionaryRestoreStringKeys = (1 << 2),
    __kCFDictionaryWeakKeys =          (1 << 3),
    __kCFDictionaryWeakValues =        (1 << 4)
};

struct __CFDictionary {
    CFRuntimeBase _base;
    CFIndex _count;		/* number of values */
    CFIndex _capacity;		/* maximum number of values */
    CFIndex _bucketsNum;	/* number of slots */
    uintptr_t _marker;
    void *_context;		/* private */
    CFIndex _deletes;
    CFOptionFlags _xflags;      /* bits for GC */
    const void **_keys;		/* can be NULL if not allocated yet */
    const void **_values;	/* can be NULL if not allocated yet */
};

/* Bits 1-0 of the base reserved bits are used for mutability variety */
/* Bits 3-2 of the base reserved bits are used for key callback indicator bits */
/* Bits 5-4 of the base reserved bits are used for value callback indicator bits */
/* Bit 6 is special KVO actions bit */

CF_INLINE CFIndex __CFDictionaryGetType(CFDictionaryRef dict) {
    return __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 1, 0);
}

CF_INLINE CFIndex __CFDictionaryGetSizeOfType(CFIndex t) {
    CFIndex size = sizeof(struct __CFDictionary);
    if (__CFBitfieldGetValue(t, 3, 2) == __kCFDictionaryHasCustomCallBacks) {
	size += sizeof(CFDictionaryKeyCallBacks);
    }
    if (__CFBitfieldGetValue(t, 5, 4) == __kCFDictionaryHasCustomCallBacks) {
	size += sizeof(CFDictionaryValueCallBacks);
    }
    return size;
}

CF_INLINE const CFDictionaryKeyCallBacks *__CFDictionaryGetKeyCallBacks(CFDictionaryRef dict) {
    CFDictionaryKeyCallBacks *result = NULL;
    switch (__CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
    case __kCFDictionaryHasNullCallBacks:
	return &__kCFNullDictionaryKeyCallBacks;
    case __kCFDictionaryHasCFTypeCallBacks:
	return &kCFTypeDictionaryKeyCallBacks;
    case __kCFDictionaryHasCustomCallBacks:
	break;
    }
    result = (CFDictionaryKeyCallBacks *)((uint8_t *)dict + sizeof(struct __CFDictionary));
    return result;
}

CF_INLINE bool __CFDictionaryKeyCallBacksMatchNull(const CFDictionaryKeyCallBacks *c) {
    return (NULL == c ||
	(c->retain == __kCFNullDictionaryKeyCallBacks.retain &&
	 c->release == __kCFNullDictionaryKeyCallBacks.release &&
	 c->copyDescription == __kCFNullDictionaryKeyCallBacks.copyDescription &&
	 c->equal == __kCFNullDictionaryKeyCallBacks.equal &&
	 c->hash == __kCFNullDictionaryKeyCallBacks.hash));
}

CF_INLINE bool __CFDictionaryKeyCallBacksMatchCFType(const CFDictionaryKeyCallBacks *c) {
    return (&kCFTypeDictionaryKeyCallBacks == c ||
	(c->retain == kCFTypeDictionaryKeyCallBacks.retain &&
	 c->release == kCFTypeDictionaryKeyCallBacks.release &&
	 c->copyDescription == kCFTypeDictionaryKeyCallBacks.copyDescription &&
	 c->equal == kCFTypeDictionaryKeyCallBacks.equal &&
	 c->hash == kCFTypeDictionaryKeyCallBacks.hash));
}

CF_INLINE const CFDictionaryValueCallBacks *__CFDictionaryGetValueCallBacks(CFDictionaryRef dict) {
    CFDictionaryValueCallBacks *result = NULL;
    switch (__CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 5, 4)) {
    case __kCFDictionaryHasNullCallBacks:
	return &__kCFNullDictionaryValueCallBacks;
    case __kCFDictionaryHasCFTypeCallBacks:
	return &kCFTypeDictionaryValueCallBacks;
    case __kCFDictionaryHasCustomCallBacks:
	break;
    }
    if (__CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2) == __kCFDictionaryHasCustomCallBacks) {
	result = (CFDictionaryValueCallBacks *)((uint8_t *)dict + sizeof(struct __CFDictionary) + sizeof(CFDictionaryKeyCallBacks));
    } else {
	result = (CFDictionaryValueCallBacks *)((uint8_t *)dict + sizeof(struct __CFDictionary));
    }
    return result;
}

CF_INLINE bool __CFDictionaryValueCallBacksMatchNull(const CFDictionaryValueCallBacks *c) {
    return (NULL == c ||
	(c->retain == __kCFNullDictionaryValueCallBacks.retain &&
	 c->release == __kCFNullDictionaryValueCallBacks.release &&
	 c->copyDescription == __kCFNullDictionaryValueCallBacks.copyDescription &&
	 c->equal == __kCFNullDictionaryValueCallBacks.equal));
}

CF_INLINE bool __CFDictionaryValueCallBacksMatchCFType(const CFDictionaryValueCallBacks *c) {
    return (&kCFTypeDictionaryValueCallBacks == c ||
	(c->retain == kCFTypeDictionaryValueCallBacks.retain &&
	 c->release == kCFTypeDictionaryValueCallBacks.release &&
	 c->copyDescription == kCFTypeDictionaryValueCallBacks.copyDescription &&
	 c->equal == kCFTypeDictionaryValueCallBacks.equal));
}

CFIndex _CFDictionaryGetKVOBit(CFDictionaryRef dict) {
    return __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 6, 6);
}

void _CFDictionarySetKVOBit(CFDictionaryRef dict, CFIndex bit) {
    __CFBitfieldSetValue(((CFRuntimeBase *)dict)->_info, 6, 6, (bit & 0x1));
}

CF_INLINE bool _CFDictionaryIsSplit(CFDictionaryRef dict) {
    return ((dict->_xflags & (__kCFDictionaryWeakKeys|__kCFDictionaryWeakValues)) != 0);
}


#define CF_OBJC_KVO_WILLCHANGE(obj, sel)
#define CF_OBJC_KVO_DIDCHANGE(obj, sel)



static CFIndex __CFDictionaryFindBuckets1a(CFDictionaryRef dict, const void *key) {
    CFHashCode keyHash = (CFHashCode)key;
    const void **keys = dict->_keys;
    uintptr_t marker = dict->_marker;
    CFIndex probe = keyHash % dict->_bucketsNum;
    CFIndex probeskip = 1;	// See RemoveValue() for notes before changing this value
    CFIndex start = probe;
    for (;;) {
	uintptr_t currKey = (uintptr_t)keys[probe];
	if (marker == currKey) {		/* empty */
	    return kCFNotFound;
	} else if (~marker == currKey) {	/* deleted */
	    /* do nothing */
	} else if (currKey == (uintptr_t)key) {
	    return probe;
	}
	probe = probe + probeskip;
	// This alternative to probe % buckets assumes that
	// probeskip is always positive and less than the
	// number of buckets.
	if (dict->_bucketsNum <= probe) {
	    probe -= dict->_bucketsNum;
	}
	if (start == probe) {
	    return kCFNotFound;
	}
    }
}

static CFIndex __CFDictionaryFindBuckets1b(CFDictionaryRef dict, const void *key) {
    const CFDictionaryKeyCallBacks *cb = __CFDictionaryGetKeyCallBacks(dict);
    CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, dict->_context) : (CFHashCode)key;
    const void **keys = dict->_keys;
    uintptr_t marker = dict->_marker;
    CFIndex probe = keyHash % dict->_bucketsNum;
    CFIndex probeskip = 1;	// See RemoveValue() for notes before changing this value
    CFIndex start = probe;
    for (;;) {
	uintptr_t currKey = (uintptr_t)keys[probe];
	if (marker == currKey) {		/* empty */
	    return kCFNotFound;
	} else if (~marker == currKey) {	/* deleted */
	    /* do nothing */
	} else if (currKey == (uintptr_t)key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void*))cb->equal, (void *)currKey, key, dict->_context))) {
	    return probe;
	}
	probe = probe + probeskip;
	// This alternative to probe % buckets assumes that
	// probeskip is always positive and less than the
	// number of buckets.
	if (dict->_bucketsNum <= probe) {
	    probe -= dict->_bucketsNum;
	}
	if (start == probe) {
	    return kCFNotFound;
	}
    }
}

static void __CFDictionaryFindBuckets2(CFDictionaryRef dict, const void *key, CFIndex *match, CFIndex *nomatch) {
    const CFDictionaryKeyCallBacks *cb = __CFDictionaryGetKeyCallBacks(dict);
    CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, dict->_context) : (CFHashCode)key;
    const void **keys = dict->_keys;
    uintptr_t marker = dict->_marker;
    CFIndex probe = keyHash % dict->_bucketsNum;
    CFIndex probeskip = 1;	// See RemoveValue() for notes before changing this value
    CFIndex start = probe;
    *match = kCFNotFound;
    *nomatch = kCFNotFound;
    for (;;) {
	uintptr_t currKey = (uintptr_t)keys[probe];
	if (marker == currKey) {		/* empty */
	    if (nomatch) *nomatch = probe;
	    return;
	} else if (~marker == currKey) {	/* deleted */
	    if (nomatch) {
		*nomatch = probe;
		nomatch = NULL;
	    }
	} else if (currKey == (uintptr_t)key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void*))cb->equal, (void *)currKey, key, dict->_context))) {
	    *match = probe;
	    return;
	}
	probe = probe + probeskip;
	// This alternative to probe % buckets assumes that
	// probeskip is always positive and less than the
	// number of buckets.
	if (dict->_bucketsNum <= probe) {
	    probe -= dict->_bucketsNum;
	}
	if (start == probe) {
	    return;
	}
    }
}

static void __CFDictionaryFindNewMarker(CFDictionaryRef dict) {
    const void **keys = dict->_keys;
    uintptr_t newMarker;
    CFIndex idx, nbuckets;
    bool hit;

    nbuckets = dict->_bucketsNum;
    newMarker = dict->_marker;
    do {
	newMarker--;
	hit = false;
	for (idx = 0; idx < nbuckets; idx++) {
	    if (newMarker == (uintptr_t)keys[idx] || ~newMarker == (uintptr_t)keys[idx]) {
		hit = true;
		break;
	    }
	}
    } while (hit);
    for (idx = 0; idx < nbuckets; idx++) {
	if (dict->_marker == (uintptr_t)keys[idx]) {
	    keys[idx] = (const void *)newMarker;
	} else if (~dict->_marker == (uintptr_t)keys[idx]) {
	    keys[idx] = (const void *)~newMarker;
	}
    }
    ((struct __CFDictionary *)dict)->_marker = newMarker;
}

static bool __CFDictionaryEqual(CFTypeRef cf1, CFTypeRef cf2) {
    CFDictionaryRef dict1 = (CFDictionaryRef)cf1;
    CFDictionaryRef dict2 = (CFDictionaryRef)cf2;
    const CFDictionaryKeyCallBacks *cb1, *cb2;
    const CFDictionaryValueCallBacks *vcb1, *vcb2;
    const void **keys;
    CFIndex idx, nbuckets;
    if (dict1 == dict2) return true;
    if (dict1->_count != dict2->_count) return false;
    cb1 = __CFDictionaryGetKeyCallBacks(dict1);
    cb2 = __CFDictionaryGetKeyCallBacks(dict2);
    if (cb1->equal != cb2->equal) return false;
    vcb1 = __CFDictionaryGetValueCallBacks(dict1);
    vcb2 = __CFDictionaryGetValueCallBacks(dict2);
    if (vcb1->equal != vcb2->equal) return false;
    if (0 == dict1->_count) return true; /* after function comparison! */
    keys = dict1->_keys;
    nbuckets = dict1->_bucketsNum;
    for (idx = 0; idx < nbuckets; idx++) {
	if (dict1->_marker != (uintptr_t)keys[idx] && ~dict1->_marker != (uintptr_t)keys[idx]) {
	    const void *value;
	    if (!CFDictionaryGetValueIfPresent(dict2, keys[idx], &value)) return false;
	    if (dict1->_values[idx] != value && vcb1->equal && !INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void*))vcb1->equal, dict1->_values[idx], value, dict1->_context)) {
		return false;
	    }
	}
    }
    return true;
}

static CFHashCode __CFDictionaryHash(CFTypeRef cf) {
    CFDictionaryRef dict = (CFDictionaryRef)cf;
    return dict->_count;
}

static CFStringRef __CFDictionaryCopyDescription(CFTypeRef cf) {
    CFDictionaryRef dict = (CFDictionaryRef)cf;
    CFAllocatorRef allocator;
    const CFDictionaryKeyCallBacks *cb;
    const CFDictionaryValueCallBacks *vcb;
    const void **keys;
    CFIndex idx, nbuckets;
    CFMutableStringRef result;
    cb = __CFDictionaryGetKeyCallBacks(dict);
    vcb = __CFDictionaryGetValueCallBacks(dict);
    keys = dict->_keys;
    nbuckets = dict->_bucketsNum;
    allocator = CFGetAllocator(dict);
    result = CFStringCreateMutable(allocator, 0);
    switch (__CFDictionaryGetType(dict)) {
    case __kCFDictionaryImmutable:
	CFStringAppendFormat(result, NULL, CFSTR("<CFDictionary %p [%p]>{type = immutable, count = %u, capacity = %u, pairs = (\n"), cf, allocator, dict->_count, dict->_capacity);
	break;
    case __kCFDictionaryFixedMutable:
	CFStringAppendFormat(result, NULL, CFSTR("<CFDictionary %p [%p]>{type = fixed-mutable, count = %u, capacity = %u, pairs = (\n"), cf, allocator, dict->_count, dict->_capacity);
	break;
    case __kCFDictionaryMutable:
	CFStringAppendFormat(result, NULL, CFSTR("<CFDictionary %p [%p]>{type = mutable, count = %u, capacity = %u, pairs = (\n"), cf, allocator, dict->_count, dict->_capacity);
	break;
    }
    for (idx = 0; idx < nbuckets; idx++) {
	if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
	    CFStringRef kDesc = NULL, vDesc = NULL;
	    if (NULL != cb->copyDescription) {
		kDesc = (CFStringRef)INVOKE_CALLBACK2(((CFStringRef (*)(const void *, void *))cb->copyDescription), keys[idx], dict->_context);
	    }
	    if (NULL != vcb->copyDescription) {
		vDesc = (CFStringRef)INVOKE_CALLBACK2(((CFStringRef (*)(const void *, void *))vcb->copyDescription), dict->_values[idx], dict->_context);
	    }
	    if (NULL != kDesc && NULL != vDesc) {
		CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@ = %@\n"), idx, kDesc, vDesc);
		CFRelease(kDesc);
		CFRelease(vDesc);
	    } else if (NULL != kDesc) {
		CFStringAppendFormat(result, NULL, CFSTR("\t%u : %@ = <%p>\n"), idx, kDesc, dict->_values[idx]);
		CFRelease(kDesc);
	    } else if (NULL != vDesc) {
		CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p> = %@\n"), idx, keys[idx], vDesc);
		CFRelease(vDesc);
	    } else {
		CFStringAppendFormat(result, NULL, CFSTR("\t%u : <%p> = <%p>\n"), idx, keys[idx], dict->_values[idx]);
	    }
	}
    }
    CFStringAppend(result, CFSTR(")}"));
    return result;
}

static void __CFDictionaryDeallocate(CFTypeRef cf) {
    CFMutableDictionaryRef dict = (CFMutableDictionaryRef)cf;
    CFAllocatorRef allocator = __CFGetAllocator(dict);
    if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
        const CFDictionaryKeyCallBacks *kcb = __CFDictionaryGetKeyCallBacks(dict);
        const CFDictionaryValueCallBacks *vcb = __CFDictionaryGetValueCallBacks(dict);
        if (kcb->retain == NULL && kcb->release == NULL && vcb->retain == NULL && vcb->release == NULL)
            return; // XXX_PCB keep dictionary intact during finalization.
    }
    if (__CFDictionaryGetType(dict) == __kCFDictionaryImmutable) {
        __CFBitfieldSetValue(((CFRuntimeBase *)dict)->_info, 1, 0, __kCFDictionaryFixedMutable);
    }

    const CFDictionaryKeyCallBacks *cb = __CFDictionaryGetKeyCallBacks(dict);
    const CFDictionaryValueCallBacks *vcb = __CFDictionaryGetValueCallBacks(dict);
    if (vcb->release || cb->release) {
	const void **keys = dict->_keys;
	CFIndex idx, nbuckets = dict->_bucketsNum;
	for (idx = 0; idx < nbuckets; idx++) {
	    if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
		const void *oldkey = keys[idx];
		if (vcb->release) {
		    INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), allocator, dict->_values[idx], dict->_context);
		}
		if (cb->release) {
		    INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), allocator, oldkey, dict->_context);
		}
	    }
	}
    }

    if (__CFDictionaryGetType(dict) == __kCFDictionaryMutable && dict->_keys) {
        _CFAllocatorDeallocateGC(allocator, dict->_keys);
        if (_CFDictionaryIsSplit(dict)) {   // iff GC, split allocations
            _CFAllocatorDeallocateGC(allocator, dict->_values);
        }
        dict->_keys = NULL;
        dict->_values = NULL;
    }
}

/*
 * When running under GC, we suss up dictionaries with standard string copy to hold
 * onto everything, including the copies of incoming keys, in strong memory without retain counts.
 * This is the routine that makes that copy.
 * Not for inputs of constant strings we'll get a constant string back, and so the result
 * is not guaranteed to be from the auto zone, hence the call to CFRelease since it will figure
 * out where the refcount really is.
 */
static CFStringRef _CFStringCreateCopyCollected(CFAllocatorRef allocator, CFStringRef theString) {
    return CFMakeCollectable(CFStringCreateCopy(NULL, theString));
}

static CFTypeID __kCFDictionaryTypeID = _kCFRuntimeNotATypeID;

static const CFRuntimeClass __CFDictionaryClass = {
    _kCFRuntimeScannedObject,
    "CFDictionary",
    NULL,	// init
    NULL,	// copy
    __CFDictionaryDeallocate,
    (void *)__CFDictionaryEqual,
    __CFDictionaryHash,
    NULL,	// 
    __CFDictionaryCopyDescription
};

__private_extern__ void __CFDictionaryInitialize(void) {
    __kCFDictionaryTypeID = _CFRuntimeRegisterClass(&__CFDictionaryClass);
}

CFTypeID CFDictionaryGetTypeID(void) {
    return __kCFDictionaryTypeID;
}

static CFDictionaryRef __CFDictionaryInit(CFAllocatorRef allocator, uint32_t flags, CFIndex capacity, const CFDictionaryKeyCallBacks *keyCallBacks, const CFDictionaryValueCallBacks *valueCallBacks) {
    struct __CFDictionary *memory;
    uint32_t size;
    CFIndex idx;
    __CFBitfieldSetValue(flags, 31, 2, 0);
    CFDictionaryKeyCallBacks nonRetainingKeyCallbacks;
    CFDictionaryValueCallBacks nonRetainingValueCallbacks;
    CFOptionFlags xflags = 0;
    if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
        // preserve NULL for key or value CB, otherwise fix up.
        if (!keyCallBacks || (keyCallBacks->retain == NULL && keyCallBacks->release == NULL)) {
	    xflags = __kCFDictionaryWeakKeys;
	}
        else {
	    if (keyCallBacks->retain == __CFTypeCollectionRetain && keyCallBacks->release == __CFTypeCollectionRelease) {
                // copy everything
                nonRetainingKeyCallbacks = *keyCallBacks;
                nonRetainingKeyCallbacks.retain = NULL;
                nonRetainingKeyCallbacks.release = NULL;
                keyCallBacks = &nonRetainingKeyCallbacks;
		xflags = __kCFDictionaryRestoreKeys;
            }
	    else if (keyCallBacks->retain == CFStringCreateCopy && keyCallBacks->release == __CFTypeCollectionRelease) {
                // copy everything
                nonRetainingKeyCallbacks = *keyCallBacks;
                nonRetainingKeyCallbacks.retain = (void *)_CFStringCreateCopyCollected;   // XXX fix with better cast
                nonRetainingKeyCallbacks.release = NULL;
                keyCallBacks = &nonRetainingKeyCallbacks;
		xflags = (__kCFDictionaryRestoreKeys | __kCFDictionaryRestoreStringKeys);
            }
        }
	if (!valueCallBacks || (valueCallBacks->retain == NULL && valueCallBacks->release == NULL)) {
	    xflags |= __kCFDictionaryWeakValues;
	}
        else {
            if (valueCallBacks->retain == __CFTypeCollectionRetain && valueCallBacks->release == __CFTypeCollectionRelease) {
                nonRetainingValueCallbacks = *valueCallBacks;
                nonRetainingValueCallbacks.retain = NULL;
                nonRetainingValueCallbacks.release = NULL;
                valueCallBacks = &nonRetainingValueCallbacks;
		xflags |= __kCFDictionaryRestoreValues;
            }
        }
    }
    if (__CFDictionaryKeyCallBacksMatchNull(keyCallBacks)) {
	__CFBitfieldSetValue(flags, 3, 2, __kCFDictionaryHasNullCallBacks);
    } else if (__CFDictionaryKeyCallBacksMatchCFType(keyCallBacks)) {
	__CFBitfieldSetValue(flags, 3, 2, __kCFDictionaryHasCFTypeCallBacks);
    } else {
	__CFBitfieldSetValue(flags, 3, 2, __kCFDictionaryHasCustomCallBacks);
    }
    if (__CFDictionaryValueCallBacksMatchNull(valueCallBacks)) {
	__CFBitfieldSetValue(flags, 5, 4, __kCFDictionaryHasNullCallBacks);
    } else if (__CFDictionaryValueCallBacksMatchCFType(valueCallBacks)) {
	__CFBitfieldSetValue(flags, 5, 4, __kCFDictionaryHasCFTypeCallBacks);
    } else {
	__CFBitfieldSetValue(flags, 5, 4, __kCFDictionaryHasCustomCallBacks);
    }
    size = __CFDictionaryGetSizeOfType(flags) - sizeof(CFRuntimeBase);
    switch (__CFBitfieldGetValue(flags, 1, 0)) {
    case __kCFDictionaryImmutable:
    case __kCFDictionaryFixedMutable:
        size += 2 * __CFDictionaryNumBucketsForCapacity(capacity) * sizeof(const void *);
        break;
    case __kCFDictionaryMutable:
        break;
    }
    memory = (struct __CFDictionary *)_CFRuntimeCreateInstance(allocator, __kCFDictionaryTypeID, size, NULL);
    if (NULL == memory) {
	return NULL;
    }
    __CFBitfieldSetValue(memory->_base._info, 6, 0, flags);
    memory->_count = 0;
    memory->_marker = (uintptr_t)0xa1b1c1d3;
    memory->_context = NULL;
    memory->_deletes = 0;
    memory->_xflags = xflags;
    switch (__CFBitfieldGetValue(flags, 1, 0)) {
    case __kCFDictionaryImmutable:
        // GC note: we can't support weak part of mixed weak/strong in fixed case, we treat it as strong XXX blaine
        if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)
                && (xflags & (__kCFDictionaryWeakKeys|__kCFDictionaryWeakValues)) == (__kCFDictionaryWeakKeys|__kCFDictionaryWeakValues)) { // if both weak, don't scan
            auto_zone_set_layout_type(__CFCollectableZone, memory, AUTO_OBJECT_UNSCANNED);
        }
        if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFDictionary (immutable)");
	memory->_capacity = capacity;	/* Don't round up capacity */
	memory->_bucketsNum = __CFDictionaryNumBucketsForCapacity(memory->_capacity);
	memory->_keys = (const void **)((uint8_t *)memory + __CFDictionaryGetSizeOfType(flags));
	memory->_values = (const void **)(memory->_keys + memory->_bucketsNum);
	for (idx = memory->_bucketsNum; idx--;) {
	    memory->_keys[idx] = (const void *)memory->_marker;
	}
	break;
    case __kCFDictionaryFixedMutable:
	// GC note: we can't support weak part of mixed weak/strong in fixed case, we treat it as strong XXX blaine
	if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)
		&& (xflags & (__kCFDictionaryWeakKeys|__kCFDictionaryWeakValues)) == (__kCFDictionaryWeakKeys|__kCFDictionaryWeakValues)) { // if both weak, don't scan
	    auto_zone_set_layout_type(__CFCollectableZone, memory, AUTO_OBJECT_UNSCANNED);
	}
	if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFDictionary (mutable-fixed)");
	memory->_capacity = capacity;	/* Don't round up capacity */
	memory->_bucketsNum = __CFDictionaryNumBucketsForCapacity(memory->_capacity);
	memory->_keys = (const void **)((uint8_t *)memory + __CFDictionaryGetSizeOfType(flags));
	memory->_values = (const void **)(memory->_keys + memory->_bucketsNum);
	for (idx = memory->_bucketsNum; idx--;) {
	    memory->_keys[idx] = (const void *)memory->_marker;
	}
	break;
    case __kCFDictionaryMutable:
	if (__CFOASafe) __CFSetLastAllocationEventName(memory, "CFDictionary (mutable-variable)");
	memory->_capacity = __CFDictionaryRoundUpCapacity(1);
	memory->_bucketsNum = 0;
	memory->_keys = NULL;
	memory->_values = NULL;
	break;
    }
    if (__kCFDictionaryHasCustomCallBacks == __CFBitfieldGetValue(flags, 3, 2)) {
	CFDictionaryKeyCallBacks *cb = (CFDictionaryKeyCallBacks *)__CFDictionaryGetKeyCallBacks((CFDictionaryRef)memory);
	*cb = *keyCallBacks;
	FAULT_CALLBACK((void **)&(cb->retain));
	FAULT_CALLBACK((void **)&(cb->release));
	FAULT_CALLBACK((void **)&(cb->copyDescription));
	FAULT_CALLBACK((void **)&(cb->equal));
	FAULT_CALLBACK((void **)&(cb->hash));
    }
    if (__kCFDictionaryHasCustomCallBacks == __CFBitfieldGetValue(flags, 5, 4)) {
	CFDictionaryValueCallBacks *vcb = (CFDictionaryValueCallBacks *)__CFDictionaryGetValueCallBacks((CFDictionaryRef)memory);
	*vcb = *valueCallBacks;
	FAULT_CALLBACK((void **)&(vcb->retain));
	FAULT_CALLBACK((void **)&(vcb->release));
	FAULT_CALLBACK((void **)&(vcb->copyDescription));
	FAULT_CALLBACK((void **)&(vcb->equal));
    }
    return (CFDictionaryRef)memory;
}

CFDictionaryRef CFDictionaryCreate(CFAllocatorRef allocator, const void **keys, const void **values, CFIndex numValues, const CFDictionaryKeyCallBacks *keyCallBacks, const CFDictionaryValueCallBacks *valueCallBacks) {
    CFDictionaryRef result;
    uint32_t flags;
    CFIndex idx;
    CFAssert2(0 <= numValues, __kCFLogAssertion, "%s(): numValues (%d) cannot be less than zero", __PRETTY_FUNCTION__, numValues);
    result = __CFDictionaryInit(allocator, __kCFDictionaryImmutable, numValues, keyCallBacks, valueCallBacks);
    flags = __CFBitfieldGetValue(((const CFRuntimeBase *)result)->_info, 1, 0);
    if (flags == __kCFDictionaryImmutable) {
	// tweak flags so that we can add our immutable values
        __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, __kCFDictionaryFixedMutable);
    }
    for (idx = 0; idx < numValues; idx++) {
	CFDictionaryAddValue((CFMutableDictionaryRef)result, keys[idx], values[idx]);
    }
    __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, flags);
    return result;
}

CFMutableDictionaryRef CFDictionaryCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFDictionaryKeyCallBacks *keyCallBacks, const CFDictionaryValueCallBacks *valueCallBacks) {
    CFAssert2(0 <= capacity, __kCFLogAssertion, "%s(): capacity (%d) cannot be less than zero", __PRETTY_FUNCTION__, capacity);
    return (CFMutableDictionaryRef)__CFDictionaryInit(allocator, (0 == capacity) ? __kCFDictionaryMutable : __kCFDictionaryFixedMutable, capacity, keyCallBacks, valueCallBacks);
}

static void __CFDictionaryGrow(CFMutableDictionaryRef dict, CFIndex numNewValues);

// This creates a dictionary which is for CFTypes or NSObjects, with an ownership transfer -- 
// the dictionary does not take a retain, and the caller does not need to release the inserted objects.
// The incoming objects must also be collectable if allocated out of a collectable allocator.
CFDictionaryRef _CFDictionaryCreate_ex(CFAllocatorRef allocator, bool mutable, const void **keys, const void **values, CFIndex numValues) {
    CFDictionaryRef result;
    void *bucketsBase;
    uint32_t flags;
    CFIndex idx;
    result = __CFDictionaryInit(allocator, mutable ? __kCFDictionaryMutable : __kCFDictionaryImmutable, numValues, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
    flags = __CFBitfieldGetValue(((const CFRuntimeBase *)result)->_info, 1, 0);
    if (!mutable) {
        __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, __kCFDictionaryFixedMutable);
    }
    if (mutable) {
	if (result->_count == result->_capacity || NULL == result->_keys) {
	    __CFDictionaryGrow((CFMutableDictionaryRef)result, numValues);
	}
    }
    // GC:  since kCFTypeDictionaryKeyCallBacks & kCFTypeDictionaryValueCallBacks are used, the keys
    // and values will be allocated contiguously.
    bool collectableContainer = CF_IS_COLLECTABLE_ALLOCATOR(allocator);
    bucketsBase = (collectableContainer ? auto_zone_base_pointer(__CFCollectableZone, result->_keys) : NULL);
    for (idx = 0; idx < numValues; idx++) {
	CFIndex match, nomatch;
	const void *newKey;
	__CFDictionaryFindBuckets2(result, keys[idx], &match, &nomatch);
	if (kCFNotFound != match) {
	    if (!collectableContainer) CFRelease(result->_values[match]);
	    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, bucketsBase, result->_values[match], values[idx]);
	    // GC: generation(_values) <= generation(values), but added for completeness.
	} else {
	    newKey = keys[idx];
	    if (result->_marker == (uintptr_t)newKey || ~result->_marker == (uintptr_t)newKey) {
		__CFDictionaryFindNewMarker(result);
	    }
	    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, bucketsBase, result->_keys[nomatch], newKey);
	    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, bucketsBase, result->_values[nomatch], values[idx]);
	    // GC: generation(_keys/_values) <= generation(keys/values), but added for completeness.
	    ((CFMutableDictionaryRef)result)->_count++;
	}
    }
    __CFBitfieldSetValue(((CFRuntimeBase *)result)->_info, 1, 0, flags);
    return result;
}

CFDictionaryRef CFDictionaryCreateCopy(CFAllocatorRef allocator, CFDictionaryRef dict) {
    CFDictionaryRef result;
    const CFDictionaryKeyCallBacks *cb;
    const CFDictionaryValueCallBacks *vcb;
    CFIndex numValues = CFDictionaryGetCount(dict);
    const void **list, *buffer[256];
    const void **vlist, *vbuffer[256];
    list = (numValues <= 256) ? buffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0); // XXX_PCB GC OK
    if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFDictionary (temp)");
    vlist = (numValues <= 256) ? vbuffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0); // XXX_PCB GC OK
    if (vlist != vbuffer && __CFOASafe) __CFSetLastAllocationEventName(vlist, "CFDictionary (temp)");
    CFDictionaryGetKeysAndValues(dict, list, vlist);
    CFDictionaryKeyCallBacks patchedKeyCB;
    CFDictionaryValueCallBacks patchedValueCB;
    if (CF_IS_OBJC(__kCFDictionaryTypeID, dict)) {
	cb = &kCFTypeDictionaryKeyCallBacks;
	vcb = &kCFTypeDictionaryValueCallBacks;
    }
    else {
	cb = __CFDictionaryGetKeyCallBacks(dict);
	vcb = __CFDictionaryGetValueCallBacks(dict);
	if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
	    if (dict->_xflags & __kCFDictionaryRestoreKeys) {
		patchedKeyCB = *cb;    // copy
		cb = &patchedKeyCB;    // reset to copy
		patchedKeyCB.retain = (dict->_xflags & __kCFDictionaryRestoreStringKeys) ? CFStringCreateCopy : __CFTypeCollectionRetain;
		patchedKeyCB.release = __CFTypeCollectionRelease;
	    }
	    if (dict->_xflags & __kCFDictionaryRestoreValues) {
		patchedValueCB = *vcb;    // copy
		vcb = &patchedValueCB;    // reset to copy
		patchedValueCB.retain = __CFTypeCollectionRetain;
		patchedValueCB.release = __CFTypeCollectionRelease;
	    }
	}
    }
    result = CFDictionaryCreate(allocator, list, vlist, numValues, cb, vcb);
    if (list != buffer) CFAllocatorDeallocate(allocator, list); // GC OK
    if (vlist != vbuffer) CFAllocatorDeallocate(allocator, vlist); // GC OK
    return result;
}

CFMutableDictionaryRef CFDictionaryCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFDictionaryRef dict) {
    CFMutableDictionaryRef result;
    const CFDictionaryKeyCallBacks *cb;
    const CFDictionaryValueCallBacks *vcb;
    CFIndex idx, numValues = CFDictionaryGetCount(dict);
    const void **list, *buffer[256];
    const void **vlist, *vbuffer[256];
    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);
    list = (numValues <= 256) ? buffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0); // XXX_PCB GC OK
    if (list != buffer && __CFOASafe) __CFSetLastAllocationEventName(list, "CFDictionary (temp)");
    vlist = (numValues <= 256) ? vbuffer : CFAllocatorAllocate(allocator, numValues * sizeof(void *), 0); // XXX_PCB GC OK
    if (vlist != vbuffer && __CFOASafe) __CFSetLastAllocationEventName(vlist, "CFDictionary (temp)");
    CFDictionaryGetKeysAndValues(dict, list, vlist);
    CFDictionaryKeyCallBacks patchedKeyCB;
    CFDictionaryValueCallBacks patchedValueCB;
    if (CF_IS_OBJC(__kCFDictionaryTypeID, dict)) {
	cb = &kCFTypeDictionaryKeyCallBacks;
	vcb = &kCFTypeDictionaryValueCallBacks;
    }
    else {
	cb = __CFDictionaryGetKeyCallBacks(dict);
	vcb = __CFDictionaryGetValueCallBacks(dict);
	if (CF_IS_COLLECTABLE_ALLOCATOR(allocator)) {
	    if (dict->_xflags & __kCFDictionaryRestoreKeys) {
		patchedKeyCB = *cb;    // copy
		cb = &patchedKeyCB;    // reset to copy
		patchedKeyCB.retain = (dict->_xflags & __kCFDictionaryRestoreStringKeys) ? CFStringCreateCopy : __CFTypeCollectionRetain;
		patchedKeyCB.release = __CFTypeCollectionRelease;
	    }
	    if (dict->_xflags & __kCFDictionaryRestoreValues) {
		patchedValueCB = *vcb;    // copy
		vcb = &patchedValueCB;    // reset to copy
		patchedValueCB.retain = __CFTypeCollectionRetain;
		patchedValueCB.release = __CFTypeCollectionRelease;
	    }
	}
    }
    result = CFDictionaryCreateMutable(allocator, capacity, cb, vcb);
    if (0 == capacity) _CFDictionarySetCapacity(result, numValues);
    for (idx = 0; idx < numValues; idx++) {
	CFDictionaryAddValue(result, list[idx], vlist[idx]);
    }
    if (list != buffer) CFAllocatorDeallocate(allocator, list); // XXX_PCB GC OK
    if (vlist != vbuffer) CFAllocatorDeallocate(allocator, vlist); // XXX_PCB GC OK
    return result;
}



// Used by NSMapTables and KVO
void _CFDictionarySetContext(CFDictionaryRef dict, void *context) {
    CFAllocatorRef allocator = CFGetAllocator(dict);
    CF_WRITE_BARRIER_BASE_ASSIGN(allocator, dict, dict->_context, context);
}

void *_CFDictionaryGetContext(CFDictionaryRef dict) {
    return ((struct __CFDictionary *)dict)->_context;
}

CFIndex CFDictionaryGetCount(CFDictionaryRef dict) {
    CF_OBJC_FUNCDISPATCH0(__kCFDictionaryTypeID, CFIndex, dict, "count");
    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    return dict->_count;
}

CFIndex CFDictionaryGetCountOfKey(CFDictionaryRef dict, const void *key) {
    CFIndex match;
    CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, CFIndex, dict, "countForKey:", key);
    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    if (0 == dict->_count) return 0;
    if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
	match = __CFDictionaryFindBuckets1a(dict, key);
    } else {
	match = __CFDictionaryFindBuckets1b(dict, key);
    }
    return (kCFNotFound != match ? 1 : 0);
}

CFIndex CFDictionaryGetCountOfValue(CFDictionaryRef dict, const void *value) {
    const void **keys;
    const CFDictionaryValueCallBacks *vcb;
    CFIndex idx, cnt = 0, nbuckets;
    CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, CFIndex, dict, "countForObject:", value);
    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    if (0 == dict->_count) return 0;
    keys = dict->_keys;
    nbuckets = dict->_bucketsNum;
    vcb = __CFDictionaryGetValueCallBacks(dict);
    for (idx = 0; idx < nbuckets; idx++) {
	if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
	    if ((dict->_values[idx] == value) || (vcb->equal && INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void*))vcb->equal, dict->_values[idx], value, dict->_context))) {
		cnt++;
	    }
	}
    }
    return cnt;
}

Boolean CFDictionaryContainsKey(CFDictionaryRef dict, const void *key) {
    CFIndex match;
    CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, char, dict, "containsKey:", key);
    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    if (0 == dict->_count) return false;
    if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
	match = __CFDictionaryFindBuckets1a(dict, key);
    } else {
	match = __CFDictionaryFindBuckets1b(dict, key);
    }
    return (kCFNotFound != match ? true : false);
}

Boolean CFDictionaryContainsValue(CFDictionaryRef dict, const void *value) {
    const void **keys;
    const CFDictionaryValueCallBacks *vcb;
    CFIndex idx, nbuckets;
    CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, char, dict, "containsObject:", value);
    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    if (0 == dict->_count) return false;
    keys = dict->_keys;
    nbuckets = dict->_bucketsNum;
    vcb = __CFDictionaryGetValueCallBacks(dict);
    for (idx = 0; idx < nbuckets; idx++) {
	if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
	    if ((dict->_values[idx] == value) || (vcb->equal && INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void*))vcb->equal, dict->_values[idx], value, dict->_context))) {
		return true;
	    }
	}
    }
    return false;
}

const void *CFDictionaryGetValue(CFDictionaryRef dict, const void *key) {
    CFIndex match;
    CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, const void *, dict, "objectForKey:", key);
    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    if (0 == dict->_count) return NULL;
    if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
	match = __CFDictionaryFindBuckets1a(dict, key);
    } else {
	match = __CFDictionaryFindBuckets1b(dict, key);
    }
    return (kCFNotFound != match ? dict->_values[match] : NULL);
}

Boolean CFDictionaryGetValueIfPresent(CFDictionaryRef dict, const void *key, const void **value) {
    CFIndex match;
    CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, char, dict, "_getValue:forKey:", (void * *)value, key);
    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    if (0 == dict->_count) return false;
    if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
	match = __CFDictionaryFindBuckets1a(dict, key);
    } else {
	match = __CFDictionaryFindBuckets1b(dict, key);
    }
    return (kCFNotFound != match ? ((value ? __CFObjCStrongAssign(dict->_values[match], value) : NULL), true) : false);
}

bool CFDictionaryGetKeyIfPresent(CFDictionaryRef dict, const void *key, const void **actualkey) {
    CFIndex match;
//#warning CF: not toll-free bridged
    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    if (0 == dict->_count) return false;
    if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
	match = __CFDictionaryFindBuckets1a(dict, key);
    } else {
	match = __CFDictionaryFindBuckets1b(dict, key);
    }
    return (kCFNotFound != match ? ((actualkey ? __CFObjCStrongAssign(dict->_keys[match], actualkey) : NULL), true) : false);
}

void CFDictionaryGetKeysAndValues(CFDictionaryRef dict, const void **keys, const void **values) {
    CFIndex idx, cnt, nbuckets;
    CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, void, dict, "getObjects:andKeys:", (void * *)values, (void * *)keys);
    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    if (CF_USING_COLLECTABLE_MEMORY) {
	// GC: speculatively issue a write-barrier on the copied to buffers (3743553).
	__CFObjCWriteBarrierRange(keys, dict->_count * sizeof(void *));
	__CFObjCWriteBarrierRange(values, dict->_count * sizeof(void *));
    }
    nbuckets = dict->_bucketsNum;
    for (idx = 0; idx < nbuckets; idx++) {
	if (dict->_marker != (uintptr_t)dict->_keys[idx] && ~dict->_marker != (uintptr_t)dict->_keys[idx]) {
	    for (cnt = 1; cnt--;) {
		if (keys) *keys++ = dict->_keys[idx];
		if (values) *values++ = dict->_values[idx];
	    }
	}
    }
}

void CFDictionaryApplyFunction(CFDictionaryRef dict, CFDictionaryApplierFunction applier, void *context) {
    const void **keys;
    CFIndex idx, cnt, nbuckets;
    FAULT_CALLBACK((void **)&(applier));
    CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, void, dict, "_apply:context:", applier, context);
    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    keys = dict->_keys;
    nbuckets = dict->_bucketsNum;
    for (idx = 0; idx < nbuckets; idx++) {
	if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
	    for (cnt = 1; cnt--;) {
		INVOKE_CALLBACK3(applier, keys[idx], dict->_values[idx], context);
	    }
	}
    }
}

static void __CFDictionaryGrow(CFMutableDictionaryRef dict, CFIndex numNewValues) {
    const void **oldkeys = dict->_keys;
    const void **oldvalues = dict->_values;
    CFIndex idx, oldnbuckets = dict->_bucketsNum;
    CFIndex oldCount = dict->_count;
    CFAllocatorRef allocator = __CFGetAllocator(dict), keysAllocator, valuesAllocator;
    void *keysBase, *valuesBase;
    dict->_capacity = __CFDictionaryRoundUpCapacity(oldCount + numNewValues);
    dict->_bucketsNum = __CFDictionaryNumBucketsForCapacity(dict->_capacity);
    dict->_deletes = 0;
    if (_CFDictionaryIsSplit(dict)) {   // iff GC, use split memory sometimes unscanned memory
	unsigned weakOrStrong = (dict->_xflags & __kCFDictionaryWeakKeys) ? AUTO_MEMORY_UNSCANNED : AUTO_MEMORY_SCANNED;
	void *mem = _CFAllocatorAllocateGC(allocator, dict->_bucketsNum * sizeof(const void *), weakOrStrong);
        CF_WRITE_BARRIER_BASE_ASSIGN(allocator, dict, dict->_keys, mem);
        keysAllocator = (dict->_xflags & __kCFDictionaryWeakKeys) ? kCFAllocatorNull : allocator;  // GC: avoids write-barrier in weak case.
        keysBase = mem;
	
        weakOrStrong = (dict->_xflags & __kCFDictionaryWeakValues) ? AUTO_MEMORY_UNSCANNED : AUTO_MEMORY_SCANNED;
	mem = _CFAllocatorAllocateGC(allocator, dict->_bucketsNum * sizeof(const void *), weakOrStrong);
        CF_WRITE_BARRIER_BASE_ASSIGN(allocator, dict, dict->_values, mem);
        valuesAllocator = (dict->_xflags & __kCFDictionaryWeakValues) ? kCFAllocatorNull : allocator; // GC: avoids write-barrier in weak case.
        valuesBase = mem;
    } else {
        CF_WRITE_BARRIER_BASE_ASSIGN(allocator, dict, dict->_keys, _CFAllocatorAllocateGC(allocator, 2 * dict->_bucketsNum * sizeof(const void *), AUTO_MEMORY_SCANNED));
        dict->_values = (const void **)(dict->_keys + dict->_bucketsNum);
        keysAllocator = valuesAllocator = allocator;
        keysBase = valuesBase = dict->_keys;
    }
    if (NULL == dict->_keys || NULL == dict->_values) HALT;
    if (__CFOASafe) __CFSetLastAllocationEventName(dict->_keys, "CFDictionary (store)");
    for (idx = dict->_bucketsNum; idx--;) {
        dict->_keys[idx] = (const void *)dict->_marker;
        dict->_values[idx] = 0;
    }
    if (NULL == oldkeys) return;
    for (idx = 0; idx < oldnbuckets; idx++) {
        if (dict->_marker != (uintptr_t)oldkeys[idx] && ~dict->_marker != (uintptr_t)oldkeys[idx]) {
            CFIndex match, nomatch;
            __CFDictionaryFindBuckets2(dict, oldkeys[idx], &match, &nomatch);
            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]);
            if (kCFNotFound != nomatch) {
                CF_WRITE_BARRIER_BASE_ASSIGN(keysAllocator, keysBase, dict->_keys[nomatch], oldkeys[idx]);
                CF_WRITE_BARRIER_BASE_ASSIGN(valuesAllocator, valuesBase, dict->_values[nomatch], oldvalues[idx]);
            }
        }
    }
    CFAssert1(dict->_count == oldCount, __kCFLogAssertion, "%s(): dict count differs after rehashing; error", __PRETTY_FUNCTION__);
    _CFAllocatorDeallocateGC(allocator, oldkeys);
    if (_CFDictionaryIsSplit(dict)) _CFAllocatorDeallocateGC(allocator, oldvalues);
}

// This function is for Foundation's benefit; no one else should use it.
void _CFDictionarySetCapacity(CFMutableDictionaryRef dict, CFIndex cap) {
    if (CF_IS_OBJC(__kCFDictionaryTypeID, dict)) return;
#if defined(DEBUG)
    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    CFAssert1(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable && __CFDictionaryGetType(dict) != __kCFDictionaryFixedMutable, __kCFLogAssertion, "%s(): dict is immutable or fixed-mutable", __PRETTY_FUNCTION__);
    CFAssert3(dict->_count <= cap, __kCFLogAssertion, "%s(): desired capacity (%d) is less than count (%d)", __PRETTY_FUNCTION__, cap, dict->_count);
#endif
    __CFDictionaryGrow(dict, cap - dict->_count);
}


void CFDictionaryAddValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
    CFIndex match, nomatch;
    const CFDictionaryKeyCallBacks *cb;
    const CFDictionaryValueCallBacks *vcb;
    const void *newKey, *newValue;
    CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, void, dict, "_addObject:forKey:", value, key);
    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    switch (__CFDictionaryGetType(dict)) {
    case __kCFDictionaryMutable:
	if (dict->_count == dict->_capacity || NULL == dict->_keys) {
	    __CFDictionaryGrow(dict, 1);
	}
	break;
    case __kCFDictionaryFixedMutable:
	CFAssert3(dict->_count < dict->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity dict %p (capacity = %d)", __PRETTY_FUNCTION__, dict, dict->_capacity);
	break;
    default:
	CFAssert2(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable, __kCFLogAssertion, "%s(): immutable dict %p passed to mutating operation", __PRETTY_FUNCTION__, dict);
	break;
    }
    __CFDictionaryFindBuckets2(dict, key, &match, &nomatch);
    if (kCFNotFound != match) {
    } else {
        CFAllocatorRef allocator = __CFGetAllocator(dict);
        CFAllocatorRef keysAllocator = (dict->_xflags & __kCFDictionaryWeakKeys) ? kCFAllocatorNull : allocator;
        CFAllocatorRef valuesAllocator = (dict->_xflags & __kCFDictionaryWeakValues) ? kCFAllocatorNull : allocator;
	cb = __CFDictionaryGetKeyCallBacks(dict);
	vcb = __CFDictionaryGetValueCallBacks(dict);
	if (cb->retain) {
	    newKey = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), allocator, key, dict->_context);
	} else {
	    newKey = key;
	}
	if (vcb->retain) {
	    newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))vcb->retain), allocator, value, dict->_context);
	} else {
	    newValue = value;
	}
	if (dict->_marker == (uintptr_t)newKey || ~dict->_marker == (uintptr_t)newKey) {
	    __CFDictionaryFindNewMarker(dict);
	}
	CF_OBJC_KVO_WILLCHANGE(dict, key);
	CF_WRITE_BARRIER_ASSIGN(keysAllocator, dict->_keys[nomatch], newKey);
	CF_WRITE_BARRIER_ASSIGN(valuesAllocator, dict->_values[nomatch], newValue);
	dict->_count++;
	CF_OBJC_KVO_DIDCHANGE(dict, key);
    }
}

void CFDictionaryReplaceValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
    CFIndex match;
    const CFDictionaryValueCallBacks *vcb;
    const void *newValue;
    CFAllocatorRef allocator, valuesAllocator;
    CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, void, dict, "_replaceObject:forKey:", value, key);
    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    switch (__CFDictionaryGetType(dict)) {
    case __kCFDictionaryMutable:
    case __kCFDictionaryFixedMutable:
	break;
    default:
	CFAssert2(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable, __kCFLogAssertion, "%s(): immutable dict %p passed to mutating operation", __PRETTY_FUNCTION__, dict);
	break;
    }
    if (0 == dict->_count) return;
    if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
	match = __CFDictionaryFindBuckets1a(dict, key);
    } else {
	match = __CFDictionaryFindBuckets1b(dict, key);
    }
    if (kCFNotFound == match) return;
    vcb = __CFDictionaryGetValueCallBacks(dict);
    allocator = __CFGetAllocator(dict);
    valuesAllocator = (dict->_xflags & __kCFDictionaryWeakValues) ? kCFAllocatorNull : allocator;
    if (vcb->retain) {
	newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))vcb->retain), allocator, value, dict->_context);
    } else {
	newValue = value;
    }
    CF_OBJC_KVO_WILLCHANGE(dict, key);
    if (vcb->release) {
	INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), allocator, dict->_values[match], dict->_context);
    }
    CF_WRITE_BARRIER_ASSIGN(valuesAllocator, dict->_values[match], newValue);
    CF_OBJC_KVO_DIDCHANGE(dict, key);
}

void CFDictionarySetValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
    CFIndex match, nomatch;
    const CFDictionaryKeyCallBacks *cb;
    const CFDictionaryValueCallBacks *vcb;
    const void *newKey, *newValue;
    CFAllocatorRef allocator, keysAllocator, valuesAllocator;
    CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, void, dict, "setObject:forKey:", value, key);
    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    switch (__CFDictionaryGetType(dict)) {
    case __kCFDictionaryMutable:
	if (dict->_count == dict->_capacity || NULL == dict->_keys) {
	    __CFDictionaryGrow(dict, 1);
	}
	break;
    case __kCFDictionaryFixedMutable:
	break;
    default:
	CFAssert2(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable, __kCFLogAssertion, "%s(): immutable dict %p passed to mutating operation", __PRETTY_FUNCTION__, dict);
	break;
    }
    __CFDictionaryFindBuckets2(dict, key, &match, &nomatch);
    vcb = __CFDictionaryGetValueCallBacks(dict);
    allocator = __CFGetAllocator(dict);
    keysAllocator = (dict->_xflags & __kCFDictionaryWeakKeys) ? kCFAllocatorNull : allocator;
    valuesAllocator = (dict->_xflags & __kCFDictionaryWeakValues) ? kCFAllocatorNull : allocator;
    if (vcb->retain) {
	newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))vcb->retain), allocator, value, dict->_context);
    } else {
	newValue = value;
    }
    if (kCFNotFound != match) {
	CF_OBJC_KVO_WILLCHANGE(dict, key);
	if (vcb->release) {
	    INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), allocator, dict->_values[match], dict->_context);
	}
	CF_WRITE_BARRIER_ASSIGN(valuesAllocator, dict->_values[match], newValue);
	CF_OBJC_KVO_DIDCHANGE(dict, key);
    } else {
	CFAssert3(__kCFDictionaryFixedMutable != __CFDictionaryGetType(dict) || dict->_count < dict->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity dict %p (capacity = %d)", __PRETTY_FUNCTION__, dict, dict->_capacity);
	cb = __CFDictionaryGetKeyCallBacks(dict);
	if (cb->retain) {
	    newKey = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), allocator, key, dict->_context);
	} else {
	    newKey = key;
	}
	if (dict->_marker == (uintptr_t)newKey || ~dict->_marker == (uintptr_t)newKey) {
	    __CFDictionaryFindNewMarker(dict);
	}
	CF_OBJC_KVO_WILLCHANGE(dict, key);
	CF_WRITE_BARRIER_ASSIGN(keysAllocator, dict->_keys[nomatch], newKey);
	CF_WRITE_BARRIER_ASSIGN(valuesAllocator, dict->_values[nomatch], newValue);
	dict->_count++;
	CF_OBJC_KVO_DIDCHANGE(dict, key);
    }
}

void CFDictionaryRemoveValue(CFMutableDictionaryRef dict, const void *key) {
    CFIndex match;
    const CFDictionaryKeyCallBacks *cb;
    const CFDictionaryValueCallBacks *vcb;
    CF_OBJC_FUNCDISPATCH1(__kCFDictionaryTypeID, void, dict, "removeObjectForKey:", key);
    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    switch (__CFDictionaryGetType(dict)) {
    case __kCFDictionaryMutable:
    case __kCFDictionaryFixedMutable:
	break;
    default:
	CFAssert2(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable, __kCFLogAssertion, "%s(): immutable dict %p passed to mutating operation", __PRETTY_FUNCTION__, dict);
	break;
    }
    if (0 == dict->_count) return;
    if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
	match = __CFDictionaryFindBuckets1a(dict, key);
    } else {
	match = __CFDictionaryFindBuckets1b(dict, key);
    }
    if (kCFNotFound == match) return;
    if (1) {
	cb = __CFDictionaryGetKeyCallBacks(dict);
	vcb = __CFDictionaryGetValueCallBacks(dict);
	const void *oldkey = dict->_keys[match];
	CFAllocatorRef allocator = CFGetAllocator(dict);
	CF_OBJC_KVO_WILLCHANGE(dict, oldkey);
	if (vcb->release) {
	    INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), allocator, dict->_values[match], dict->_context);
	}
        dict->_keys[match] = (const void *)~dict->_marker;
	dict->_values[match] = 0;
	dict->_count--;
	CF_OBJC_KVO_DIDCHANGE(dict, oldkey);
	if (cb->release) {
	    INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), __CFGetAllocator(dict), oldkey, dict->_context);
	}
	dict->_deletes++;
	// _CFDictionaryDecrementValue() below has this same code.
	if ((__kCFDictionaryMutable == __CFDictionaryGetType(dict)) && (dict->_bucketsNum < 4 * dict->_deletes || (512 < dict->_capacity && 3.236067 * dict->_count < dict->_capacity))) {
	    // 3.236067 == 2 * golden_mean; this comes about because we're trying to resize down
	    // when the count is less than 2 capacities smaller, but not right away when count
	    // is just less than 2 capacities smaller, because an add would then force growth;
	    // well, the ratio between one capacity and the previous is close to the golden
	    // mean currently, so (cap / m / m) would be two smaller; but so we're not close,
	    // we take the average of that and the prior cap (cap / m / m / m). Well, after one
	    // does the algebra, and uses the convenient fact that m^(x+2) = m^(x+1) + m^x if m
	    // is the golden mean, this reduces to cap / 2m for the threshold. In general, the
	    // possible threshold constant is 1 / (2 * m^k), k = 0, 1, 2, ... under this scheme.
	    // Rehash; currently only for mutable-variable dictionaries
	    __CFDictionaryGrow(dict, 0);
	} else {
	    // When the probeskip == 1 always and only, a DELETED slot followed by an EMPTY slot
	    // can be converted to an EMPTY slot.  By extension, a chain of DELETED slots followed
	    // by an EMPTY slot can be converted to EMPTY slots, which is what we do here.
	    // _CFDictionaryDecrementValue() below has this same code.
	    if (match < dict->_bucketsNum - 1 && dict->_keys[match + 1] == (const void *)dict->_marker) {
		while (0 <= match && dict->_keys[match] == (const void *)~dict->_marker) {
		    dict->_keys[match] = (const void *)dict->_marker;
		    dict->_deletes--;
		    match--;
		}
	    }
	}
    }
}

void CFDictionaryRemoveAllValues(CFMutableDictionaryRef dict) {
    const void **keys;
    const CFDictionaryKeyCallBacks *cb;
    const CFDictionaryValueCallBacks *vcb;
    CFAllocatorRef allocator;
    CFIndex idx, nbuckets;
    CF_OBJC_FUNCDISPATCH0(__kCFDictionaryTypeID, void, dict, "removeAllObjects");
    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    switch (__CFDictionaryGetType(dict)) {
    case __kCFDictionaryMutable:
    case __kCFDictionaryFixedMutable:
	break;
    default:
	CFAssert2(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable, __kCFLogAssertion, "%s(): immutable dict %p passed to mutating operation", __PRETTY_FUNCTION__, dict);
	break;
    }
    if (0 == dict->_count) return;
    keys = dict->_keys;
    nbuckets = dict->_bucketsNum;
    cb = __CFDictionaryGetKeyCallBacks(dict);
    vcb = __CFDictionaryGetValueCallBacks(dict);
    allocator = __CFGetAllocator(dict);
    for (idx = 0; idx < nbuckets; idx++) {
	if (dict->_marker != (uintptr_t)keys[idx] && ~dict->_marker != (uintptr_t)keys[idx]) {
	    const void *oldkey = keys[idx];
	    CF_OBJC_KVO_WILLCHANGE(dict, oldkey);
	    if (vcb->release) {
		INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), allocator, dict->_values[idx], dict->_context);
	    }
	    keys[idx] = (const void *)~dict->_marker;
	    dict->_values[idx] = 0;
	    dict->_count--;
	    CF_OBJC_KVO_DIDCHANGE(dict, oldkey);
	    if (cb->release) {
		INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), allocator, oldkey, dict->_context);
	    }
	}
    }
    // XXX need memset here
    for (idx = 0; idx < nbuckets; idx++) {
	keys[idx] = (const void *)dict->_marker;
	dict->_values[idx] = 0;
    }
    dict->_count = 0;
    dict->_deletes = 0;
    if ((__kCFDictionaryMutable == __CFDictionaryGetType(dict)) && (512 < dict->_capacity)) {
	__CFDictionaryGrow(dict, 256);
    }
}

void _CFDictionaryIncrementValue(CFMutableDictionaryRef dict, const void *key) {
    CFIndex match, nomatch;

    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    CFAssert1(__CFDictionaryGetType(dict) == __kCFDictionaryMutable, __kCFLogAssertion, "%s(): invalid dict type passed to increment operation", __PRETTY_FUNCTION__);
    CFAssert1(__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2), __kCFLogAssertion, "%s(): invalid dict passed to increment operation", __PRETTY_FUNCTION__);
    CFAssert1(__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 5, 4), __kCFLogAssertion, "%s(): invalid dict passed to increment operation", __PRETTY_FUNCTION__);

    match = kCFNotFound;
    if (NULL != dict->_keys) {
	__CFDictionaryFindBuckets2(dict, key, &match, &nomatch);
    }
    if (kCFNotFound != match) {
	if (dict->_values[match] != (void *)UINT_MAX) {
	    dict->_values[match] = (void *)((uintptr_t)dict->_values[match] + 1);
	}
    } else {
	if (dict->_marker == (uintptr_t)key || ~dict->_marker == (uintptr_t)key) {
	    __CFDictionaryFindNewMarker(dict);
	}
	if (dict->_count == dict->_capacity || NULL == dict->_keys) {
	    __CFDictionaryGrow(dict, 1);
	    __CFDictionaryFindBuckets2(dict, key, &match, &nomatch);
	}
	dict->_keys[nomatch] = key;
	dict->_values[nomatch] = (void *)1;
	dict->_count++;
    }
}

int _CFDictionaryDecrementValue(CFMutableDictionaryRef dict, const void *key) {
    CFIndex match;

    __CFGenericValidateType(dict, __kCFDictionaryTypeID);
    CFAssert1(__CFDictionaryGetType(dict) == __kCFDictionaryMutable, __kCFLogAssertion, "%s(): invalid dict type passed to increment operation", __PRETTY_FUNCTION__);
    CFAssert1(__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2), __kCFLogAssertion, "%s(): invalid dict passed to increment operation", __PRETTY_FUNCTION__);
    CFAssert1(__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 5, 4), __kCFLogAssertion, "%s(): invalid dict passed to increment operation", __PRETTY_FUNCTION__);

    if (0 == dict->_count) return -1;
    match = __CFDictionaryFindBuckets1a(dict, key);
    if (kCFNotFound == match) return -1;
    if (1 == (uintptr_t)dict->_values[match]) {
	dict->_count--;
	dict->_values[match] = 0;
        dict->_keys[match] = (const void *)~dict->_marker;
	dict->_deletes++;
	if ((__kCFDictionaryMutable == __CFDictionaryGetType(dict)) && (dict->_bucketsNum < 4 * dict->_deletes || (512 < dict->_capacity && 3.236067 * dict->_count < dict->_capacity))) {
	    __CFDictionaryGrow(dict, 0);
	} else {
	    if (match < dict->_bucketsNum - 1 && dict->_keys[match + 1] == (const void *)dict->_marker) {
		while (0 <= match && dict->_keys[match] == (const void *)~dict->_marker) {
		    dict->_keys[match] = (const void *)dict->_marker;
		    dict->_deletes--;
		    match--;
		}
	    }
	}
	return 0;
    } else if (dict->_values[match] != (void *)UINT_MAX) {
	dict->_values[match] = (void *)((uintptr_t)dict->_values[match] - 1);
    }
    return 1;
}