A fully bridged multimap implementation.

CFIMultiMap.c

/*
 * Copyright (c) 2013 CodaFi. 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@
 */

/*  CFIMultiMap
 Copyright (c) 2013, CodaFi. All rights reserved.
 Responsibility: Robert Widmann
 Machine generated from Notes/HashingCode.template
 */

#include <stdlib.h>
#include "CFIMultiMap.h"
#include <CoreFoundation/CFString.h>

typedef const void * const_any_pointer_t;

enum {
	_kCFRuntimeNotATypeID =                0
};

typedef struct __CFRuntimeBase {
	uintptr_t _cfisa;
	uint8_t _cfinfo[4];
#if __LP64__
	uint32_t _rc;
#endif
} CFRuntimeBase;

typedef struct __CFRuntimeClass {	// Version 0 struct
	CFIndex version;
	const char *className;
	void (*init)(CFTypeRef cf);
	CFTypeRef (*copy)(CFAllocatorRef allocator, CFTypeRef cf);
#if MAC_OS_X_VERSION_10_2 <= MAC_OS_X_VERSION_MAX_ALLOWED
	void (*finalize)(CFTypeRef cf);
#else
	void (*dealloc)(CFTypeRef cf);
#endif
	Boolean (*equal)(CFTypeRef cf1, CFTypeRef cf2);
	CFHashCode (*hash)(CFTypeRef cf);
	CFStringRef (*copyFormattingDesc)(CFTypeRef cf, CFDictionaryRef formatOptions);	// str with retain
	CFStringRef (*copyDebugDesc)(CFTypeRef cf);	// str with retain
#if MAC_OS_X_VERSION_10_5 <= MAC_OS_X_VERSION_MAX_ALLOWED
#define CF_RECLAIM_AVAILABLE 1
	void (*reclaim)(CFTypeRef cf);
#endif
} CFRuntimeClass;

CF_EXPORT CFTypeID _CFRuntimeRegisterClass(const CFRuntimeClass * const cls);
CF_EXPORT CFTypeRef _CFRuntimeCreateInstance(CFAllocatorRef allocator, CFTypeID typeID, CFIndex extraBytes, unsigned char *category);

struct __CFIMultiMap {
	CFRuntimeBase _base;
	CFMutableDictionaryRef _dict;
};

static CFTypeID __kCFIMultiMapTypeID = _kCFRuntimeNotATypeID;

static void __CFIMultiMapDeallocate(CFTypeRef cf) {
	CFRelease(((CFIMultiMapRef)cf)->_dict);
}

static CFStringRef __CFIMultiMapCopyDescription(CFTypeRef cf)
{
	CFIMultiMapRef val = (void*)cf;
	return CFStringCreateWithFormat(CFGetAllocator(cf), NULL, CFSTR("<MyValue %p [%p]>{dict = %p}"), cf, CFGetAllocator(cf), val->_dict);
}

CFMutableDictionaryRef CFIRemapKeysAndValues(const void **keys, const void **values, CFIndex numValues) {
	CFMutableDictionaryRef retVal = CFDictionaryCreateMutable(kCFAllocatorDefault, numValues, NULL, NULL);
	CFIndex idx = 0;
	while (idx != numValues) {
		CFMutableSetRef set = (CFMutableSetRef)CFDictionaryGetValue(retVal, *keys);
		if (set == NULL) {
			set = CFSetCreateMutable(kCFAllocatorDefault, 1, NULL);
			CFDictionarySetValue(retVal, *keys, set);
			CFRelease(set);
		}
		CFSetSetValue(set, *values);
		(values)++;
		(keys)++;
		idx++;
	}
	return retVal;
}

static const CFRuntimeClass __CFIMultiMapClass = {
	0,
	"CFIMultiMap",
	NULL,        // init
	NULL,        // copy
	__CFIMultiMapDeallocate,
	NULL,
	NULL,
	NULL,        //
	__CFIMultiMapCopyDescription
};

CFIMultiMapRef CFIMultiMapCreate(CFAllocatorRef allocator, const void **keys, const void **values, CFIndex numValues, const CFDictionaryKeyCallBacks *keyCallBacks, const CFDictionaryValueCallBacks *valueCallBacks) {
	uint32_t size = sizeof(struct __CFIMultiMap) - sizeof(CFRuntimeBase);
	CFIMultiMapRef memory = (void *)_CFRuntimeCreateInstance(allocator, CFIMultiMapGetTypeID(), size, NULL);
	if (NULL == memory) {
		return NULL;
	}
	if (keys != NULL && values != NULL) {
		((struct __CFIMultiMap *)memory)->_dict = CFIRemapKeysAndValues(keys, values, numValues);
	} else {
		((struct __CFIMultiMap *)memory)->_dict = CFDictionaryCreateMutable(allocator, 0, keyCallBacks, valueCallBacks);
	}
	return memory;
}

CFIMultiMapRef CFIMultiMapCreateCopy(CFAllocatorRef allocator, CFIMultiMapRef theMultiMap) {
	uint32_t size = sizeof(struct __CFIMultiMap) - sizeof(CFRuntimeBase);
	CFIMultiMapRef memory = (void*)_CFRuntimeCreateInstance(allocator, CFIMultiMapGetTypeID(), size, NULL);
	if (NULL == memory) {
		return NULL;
	}
	((struct __CFIMultiMap *)memory)->_dict = CFDictionaryCreateMutableCopy(allocator, CFDictionaryGetCount(theMultiMap->_dict), theMultiMap->_dict);
	return memory;
}

CFIMutableMultiMapRef CFIMultiMapCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFDictionaryKeyCallBacks *keyCallBacks, const CFDictionaryValueCallBacks *valueCallBacks) {
	uint32_t size = sizeof(struct __CFIMultiMap) - sizeof(CFRuntimeBase);
	CFIMutableMultiMapRef memory = (void*)_CFRuntimeCreateInstance(allocator, CFIMultiMapGetTypeID(), size, NULL);
	if (NULL == memory) {
		return NULL;
	}
	((struct __CFIMultiMap *)memory)->_dict = CFDictionaryCreateMutable(allocator, capacity, keyCallBacks, valueCallBacks);
	return memory;
}

CFIMutableMultiMapRef CFIMultiMapCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFIMultiMapRef theMultiMap) {
	uint32_t size = sizeof(struct __CFIMultiMap) - sizeof(CFRuntimeBase);
	CFIMutableMultiMapRef memory = (void*)_CFRuntimeCreateInstance(allocator, CFIMultiMapGetTypeID(), size, NULL);
	if (NULL == memory) {
		return NULL;
	}
	((struct __CFIMultiMap *)memory)->_dict = CFDictionaryCreateMutableCopy(allocator, CFDictionaryGetCount(theMultiMap->_dict), theMultiMap->_dict);
	return memory;
}

CFIndex CFIMultiMapGetCount(CFIMultiMapRef theMultiMap) {
	return CFDictionaryGetCount(theMultiMap->_dict);
}

CFIndex CFIMultiMapGetCountOfValuesForKey(CFIMultiMapRef theMultiMap, const void *key) {
	CFMutableSetRef setRef = (CFMutableSetRef)CFDictionaryGetValue(theMultiMap->_dict, key);
	if (setRef == NULL) {
		return (CFIndex)0;
	}
	return CFSetGetCount(setRef);
}

Boolean CFIMultiMapContainsKey(CFIMultiMapRef theMultiMap, const void *key) {
	return CFDictionaryContainsKey(theMultiMap->_dict, key);
}

Boolean CFIMultiMapContainsValueForKey(CFIMultiMapRef theMultiMap, const void *value, const void *key) {
	CFMutableSetRef setRef = (CFMutableSetRef)CFDictionaryGetValue(theMultiMap->_dict, key);
	return CFSetContainsValue(setRef, value);
}

const CFSetRef CFIMultiMapGetAllValuesForKey(CFIMultiMapRef theMultiMap, const void *key) {
	return (const CFSetRef)CFDictionaryGetValue(theMultiMap->_dict, key);
}

Boolean CFIMultiMapGetAllValuesForKeyIfPresent(CFIMultiMapRef theMultiMap, const void *key, const void **value) {
	Boolean containsValue = CFDictionaryContainsKey(theMultiMap->_dict, key);
	if (containsValue && value != NULL) {
		*value = CFDictionaryGetValue(theMultiMap->_dict, key);
	}
	return containsValue;
}

void CFIMultiMapGetKeysAndValues(CFIMultiMapRef theMultiMap, const void **keys, const void **values) {
	CFDictionaryGetKeysAndValues(theMultiMap->_dict, keys, values);
}

void CFIMultiMapApplyFunction(CFIMultiMapRef theMultiMap, CFIMultiMapApplierFunction applier, void *context) {
	size_t size = CFDictionaryGetCount(theMultiMap->_dict);
	CFTypeRef *keys = (CFTypeRef *)malloc(size * sizeof(CFTypeRef));
	CFSetRef value = NULL;
	CFIMultiMapGetKeysAndValues(theMultiMap, (const void**)keys, NULL);
	CFIndex keyCount = CFIMultiMapGetCount(theMultiMap);
	CFIndex idx = CFIMultiMapGetCount(theMultiMap);
	while (idx != keyCount) {
		if (CFIMultiMapGetAllValuesForKeyIfPresent(theMultiMap, *keys, (const void **)&value)) {
			size = CFSetGetCount(value);
			CFTypeRef *setValues = (CFTypeRef *)malloc(size * sizeof(CFTypeRef));
			CFSetGetValues(value, (const void**)setValues);
			CFIndex setIdx = 0;
			CFIndex setCount = CFSetGetCount(value);
			while (setIdx != setCount) {
				applier(*keys, *setValues, context);
				(*setValues)++;
				setIdx++;
			}
			free(setValues);
		}
		idx++;
		(*keys)++;
	}
	free(keys);
}

void CFIMultiMapAddValue(CFIMutableMultiMapRef theMultiMap, const void *key, const void *value) {
	CFMutableDictionaryRef retVal = theMultiMap->_dict;
	CFMutableSetRef set = (CFMutableSetRef)CFDictionaryGetValue(retVal, key);
	if (set == NULL) {
		set = CFSetCreateMutable(kCFAllocatorDefault, 1, NULL);
		CFDictionarySetValue(retVal, key, set);
		CFRelease(set);
	}
	CFSetSetValue(set, value);
}

void CFIMultiMapReplaceValue(CFIMutableMultiMapRef theMultiMap, const void *key, const void *value) {
	CFMutableSetRef set = CFSetCreateMutable(kCFAllocatorDefault, 1, NULL);
	CFSetSetValue(set, value);
	CFDictionarySetValue(theMultiMap->_dict, key, set);
}

void CFIMultiMapRemoveValue(CFIMutableMultiMapRef theMultiMap, const void *key) {
	CFDictionaryRemoveValue(theMultiMap->_dict, key);
}

void CFIMultiMapRemoveAllValues(CFIMutableMultiMapRef theMultiMap) {
	CFDictionaryRemoveAllValues(theMultiMap->_dict);
}

CFTypeID CFIMultiMapGetTypeID(void) {
	if (_kCFRuntimeNotATypeID == __kCFIMultiMapTypeID) __kCFIMultiMapTypeID = _CFRuntimeRegisterClass(&__CFIMultiMapClass);
	return __kCFIMultiMapTypeID;
}

CFIMultiMap.h

/*
 * Copyright (c) 2012 CodaFi. All rights reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

/*  CFIMultiMap.h
 Copyright (c) 2012 CodaFi. All rights reserved.
 */

/*!
 @header CFIMultiMap
 CFIMultiMap implements a container which pairs pointer-sized keys
 with a container of pointer-sized values.  A CFIMultiMap differs 
 from a CFDictionary in that more than one value can be associated
 with a given key.  Just like an NSDictionary, order is not 
 guaranteed for both its keys and its values, and the index
 used to retrieve a given value can change at any time. To enable 
 later retrieval of a value, the key of the key-value pair should 
 be constant (or treated as constant); if the key changes after 
 being used to put a value in the multimap, the value may not be 
 retrievable. The keys of a multimap form a set; that is, no two 
 keys which are equal to one another are present in the dictionary 
 at any time.
 
 MultiMaps come in two flavors, immutable, which cannot have
 values added to them or removed from them after the multimap is
 created, and mutable, to which you can add values or from which
 remove values. Mutable multimaps can have an unlimited number
 of values (or rather, limited only by constraints external to
 CFIMultiMap, like the amount of available memory).
 
 As with all CoreFoundation collection types, multimaps maintain
 hard references on the values you put in them, but the retaining and
 releasing functions are user-defined callbacks that can actually do
 whatever the user wants (for example, nothing).
 
 Although a particular implementation of CFIMultiMap may not use
 hashing and a hash table for storage of the values, the keys have
 a hash-code generating function defined for them, and a function
 to test for equality of two keys. These two functions together
 must maintain the invariant that if equal(X, Y), then hash(X) ==
 hash(Y). Note that the converse will not generally be true (but
 the contrapositive, if hash(X) != hash(Y), then !equal(X, Y),
 will be as required by Boolean logic). If the hash() and equal()
 key callbacks are NULL, the key is used as a pointer-sized integer,
 and pointer equality is used. Care should be taken to provide a
 hash() callback which will compute sufficiently dispersed hash
 codes for the key set for best performance.
 
 Computational Complexity
 The access time for a value in the dictionary is guaranteed to be at
 worst O(N) for any implementation, current and future, but will
 often be O(1) (constant time). Insertion or deletion operations
 will typically be constant time as well, but are O(N*N) in the
 worst case in some implementations. Access of values through a key
 is faster than accessing values directly (if there are any such
 operations). Dictionaries will tend to use significantly more memory
 than a array with the same number of values.
 */

#if !defined(__COREFOUNDATION_CFIMultiMap__)
#define __COREFOUNDATION_CFIMultiMap__ 1

#include <CoreFoundation/CFBase.h>
#include <CoreFoundation/CFDictionary.h>
#include <CoreFoundation/CFSet.h>

CF_IMPLICIT_BRIDGING_ENABLED
CF_EXTERN_C_BEGIN

typedef void (*CFIMultiMapApplierFunction)(const void *key, const void *value, void *context);
typedef const struct __CFIMultiMap * CFIMultiMapRef;
typedef struct __CFIMultiMap * CFIMutableMultiMapRef;

CF_EXPORT
CFTypeID CFIMultiMapGetTypeID(void);

CF_EXPORT
CFIMultiMapRef CFIMultiMapCreate(CFAllocatorRef allocator, const void **keys, const void **values, CFIndex numValues, const CFDictionaryKeyCallBacks *keyCallBacks, const CFDictionaryValueCallBacks *valueCallBacks);

CF_EXPORT
CFIMultiMapRef CFIMultiMapCreateCopy(CFAllocatorRef allocator, CFIMultiMapRef theMultiMap);

CF_EXPORT
CFIMutableMultiMapRef CFIMultiMapCreateMutable(CFAllocatorRef allocator, CFIndex capacity, const CFDictionaryKeyCallBacks *keyCallBacks, const CFDictionaryValueCallBacks *valueCallBacks);

CF_EXPORT
CFIMutableMultiMapRef CFIMultiMapCreateMutableCopy(CFAllocatorRef allocator, CFIndex capacity, CFIMultiMapRef theMultiMap);

CF_EXPORT
CFIndex CFIMultiMapGetCount(CFIMultiMapRef theMultiMap);

CF_EXPORT
CFIndex CFIMultiMapGetCountOfValuesForKey(CFIMultiMapRef theMultiMap, const void *key);

CF_EXPORT
Boolean CFIMultiMapContainsKey(CFIMultiMapRef theMultiMap, const void *key);

CF_EXPORT
Boolean CFIMultiMapContainsValueForKey(CFIMultiMapRef theMultiMap, const void *value, const void *key);

CF_EXPORT
const CFSetRef CFIMultiMapGetAllValuesForKey(CFIMultiMapRef theMultiMap, const void *key);

CF_EXPORT
Boolean CFIMultiMapGetAllValuesForKeyIfPresent(CFIMultiMapRef theMultiMap, const void *key, const void **value);

CF_EXPORT
void CFIMultiMapGetKeysAndValues(CFIMultiMapRef theMultiMap, const void **keys, const void **values);

CF_EXPORT
void CFIMultiMapApplyFunction(CFIMultiMapRef theMultiMap, CFIMultiMapApplierFunction applier, void *context);

CF_EXPORT
void CFIMultiMapAddValue(CFIMutableMultiMapRef theMultiMap, const void *key, const void *value);

CF_EXPORT
void CFIMultiMapReplaceValue(CFIMutableMultiMapRef theMultiMap, const void *key, const void *value);

CF_EXPORT
void CFIMultiMapRemoveValue(CFIMutableMultiMapRef theMultiMap, const void *key);

CF_EXPORT
void CFIMultiMapRemoveAllValues(CFIMutableMultiMapRef theMultiMap);

CF_EXTERN_C_END
CF_IMPLICIT_BRIDGING_DISABLED

#endif /* ! __COREFOUNDATION_CFIMultiMap__ */

CFIOMultiMap.h

/*  CFIOMultiMap.h
 Copyright (c) 2013, CodaFi Inc. All rights reserved.
 */

#import <Foundation/Foundation.h>

@interface CFIOMultiMap : NSObject <NSCopying, NSMutableCopying, NSSecureCoding>

- (NSUInteger)count;
- (NSSet *)objectsForKey:(id)aKey;
- (NSEnumerator *)keyEnumerator;

@end

@interface CFIOMultiMap (CFIOExtendedMultiMap)

- (NSArray *)allKeys;
- (NSString *)description;
- (BOOL)isEqualToMultiMap:(CFIOMultiMap *)otherMultiMap;

- (NSArray *)keysSortedByValueUsingSelector:(SEL)comparator;
- (void)getObjects:(id __unsafe_unretained [])objects andKeys:(id __unsafe_unretained [])keys;

- (id)objectForKeyedSubscript:(id)key NS_AVAILABLE(10_8, 6_0);

#if NS_BLOCKS_AVAILABLE
- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(id key, NSSet *objs, BOOL *stop))block NS_AVAILABLE(10_6, 4_0);
- (void)enumerateKeysAndObjectsWithOptions:(NSEnumerationOptions)opts usingBlock:(void (^)(id key, NSSet *objs, BOOL *stop))block NS_AVAILABLE(10_6, 4_0);

#endif

@end

@interface CFIOMultiMap (CFIOMultiMapCreation)

+ (instancetype)multimap;

- (instancetype)init;	/* designated initializer */

- (instancetype)initWithMultimap:(CFIOMultiMap *)otherDictionary;
- (instancetype)initWithMultimap:(CFIOMultiMap *)otherDictionary copyItems:(BOOL)flag;

@end

/****************	Mutable MultiMap	****************/

@interface CFIOMutableMultiMap : CFIOMultiMap

- (void)removeObjectForKey:(id)aKey;
- (void)setObjects:(NSSet *)objects forKey:(id <NSCopying>)aKey;

@end

@interface CFIOMutableMultiMap (CFIOExtendedMutableMultiMap)

- (void)addEntriesFromMultiMap:(CFIOMultiMap *)otherMultiMap;
- (void)removeAllObjects;
- (void)removeObjectsForKeys:(NSArray *)keyArray;
- (void)setObject:(id)obj forKeyedSubscript:(id <NSCopying>)key NS_AVAILABLE(10_8, 6_0);

@end

@interface CFIOMutableMultiMap (CFIOMutableMultiMapCreation)

- (instancetype)init;	/* designated initializer */

@end

CFIOMultiMap.m

//
//  CFIOMultiMap.m
//  MultiMapTests
//
//  Created by Robert Widmann on 6/17/13.
//  Copyright (c) 2013 CodaFi. All rights reserved.
//

#import "CFIOMultiMap.h"
#include "CFIMultiMap.h"
#include <objc/runtime.h>

/**
typedef struct __CFRuntimeBase {
 uintptr_t _cfisa; //8
 uint8_t _cfinfo[4]; //8*4 = 32
#if __LP64__
 uint32_t _rc; //32
#endif
} CFRuntimeBase;
*/

struct __CFIMultiMapGuts {
  uintptr_t _isa;
	uint8_t _cfinfo[4]; //8*4 = 32
	uint32_t _base;
	CFMutableDictionaryRef _dict;
};
typedef struct __CFIMultiMapGuts CFIMultiMapGuts;

@implementation CFIOMultiMap {
@public
	CFIMultiMapGuts _guts;
}

#pragma mark - Lifecycle

- (id)retain {
	Class actualClass = object_getClass(self);
	object_setClass(self, NSObject.class);
	CFRetain(self);
	object_setClass(self, actualClass);

	return self;
}

- (oneway void)release {
	Class actualClass = object_getClass(self);
	BOOL shouldDealloc = ![self retainCount];
	
	if (shouldDealloc) {
		[self dealloc];
	}
	object_setClass(self, NSObject.class);
	CFRelease(self);
	if (!shouldDealloc)
		object_setClass(self, actualClass);
}

- (NSUInteger)retainCount {
	Class actualClass = object_getClass(self);
	NSUInteger rc;
	object_setClass(self, NSObject.class);
	rc = CFGetRetainCount(self);
	object_setClass(self, actualClass);
	return (NSUInteger)rc;
}

- (void)dealloc {
	NSZoneRealloc([self zone], self, sizeof(_guts) + sizeof(void));
	[super dealloc];
}

#pragma mark - Runtime

- (CFTypeID)_cfTypeID {
	return CFIMultiMapGetTypeID();
}

#pragma mark - Minimal Interface

- (NSUInteger)count {
	return CFDictionaryGetCount(_guts._dict);
}

- (NSEnumerator *)keyEnumerator {
	return [self.allKeys objectEnumerator];
}

- (NSSet *)objectsForKey:(id)aKey {
	if (!aKey) return nil;
	return (NSSet *)CFIMultiMapGetAllValuesForKey((CFIMultiMapRef)self, aKey);
}

#pragma mark - NSCopying

- (id)copyWithZone:(NSZone *)zone {
	CFIMultiMapRef mutableCopy = CFIMultiMapCreateCopy(NULL, (CFIMultiMapRef)self);
	if (mutableCopy == NULL) {
		return nil;
	}
	return (id)mutableCopy;
}

- (id)mutableCopyWithZone:(NSZone *)zone {
	CFIMutableMultiMapRef mutableCopy = CFIMultiMapCreateMutableCopy(NULL, 0, (CFIMultiMapRef)self);
	if (mutableCopy == NULL) {
		return nil;
	}
	return (id)mutableCopy;
}

#pragma mark - NSCoding

- (id)initWithCoder:(NSCoder *)aDecoder {
	self = [self init];
	
	CFDictionaryRef decodedDictionary = (__bridge CFDictionaryRef)[aDecoder decodeObjectForKey:@"CFIDictionaryGutsKey"];
	_guts._dict = CFDictionaryCreateMutableCopy(kCFAllocatorDefault, CFDictionaryGetCount(decodedDictionary), decodedDictionary);
	
	return self;
}

- (void)encodeWithCoder:(NSCoder *)aCoder {
	[aCoder encodeObject:(__bridge NSDictionary *)_guts._dict forKey:@"CFIDictionaryGutsKey"];
}

#pragma mark - NSSecureCoding

+ (BOOL)supportsSecureCoding {
	return YES;
}

@end

@implementation CFIOMultiMap (CFIOExtendedMultiMap)

- (NSArray *)allKeys {
	CFIndex size = CFDictionaryGetCount(_guts._dict);
	CFTypeRef *keys = (CFTypeRef *) malloc( size * sizeof(CFTypeRef) );
	CFDictionaryGetKeysAndValues(_guts._dict, (const void **)keys, NULL);
	NSArray *retVal =  CFBridgingRelease(CFArrayCreate(kCFAllocatorDefault, keys, size, NULL));
	free(keys);
	return retVal;
}

- (NSArray *)allValues {
	CFIndex size = CFDictionaryGetCount(_guts._dict);
	CFTypeRef *values = (CFTypeRef *) malloc( size * sizeof(CFTypeRef) );
	CFDictionaryGetKeysAndValues(_guts._dict, NULL, (const void **)values);
	NSArray *retVal = CFBridgingRelease(CFArrayCreate(kCFAllocatorDefault, values, size, NULL));
	free(values);
	return retVal;
}

- (NSString *)description {
	return [NSString stringWithFormat:@"<%@:%p>", self.class, self];
}

- (BOOL)isEqualToMultiMap:(CFIOMultiMap *)otherMultiMap {
	if (!otherMultiMap) return NO;
	if (self == otherMultiMap) return YES;
	
	return CFEqual((CFTypeRef)self, (CFTypeRef)otherMultiMap);
}

- (NSArray *)keysSortedByValueUsingSelector:(SEL)comparator {
	return [self.allKeys sortedArrayUsingSelector:comparator];
}

- (void)getObjects:(id __unsafe_unretained [])objects andKeys:(id __unsafe_unretained [])keys {
	CFDictionaryGetKeysAndValues(_guts._dict, (const void **)keys, (const void **)objects);
}

- (id)objectForKeyedSubscript:(id)key {
	return [self objectsForKey:key];
}

#if NS_BLOCKS_AVAILABLE
- (void)enumerateKeysAndObjectsUsingBlock:(void (^)(id key, NSSet *objs, BOOL *stop))block {
	BOOL stop = NO;
	NSEnumerator *keyEnumerator = self.keyEnumerator;
	id currentKey = nil;
	while (!stop && ((currentKey = [keyEnumerator nextObject]) != nil)) {
		block(currentKey, [self objectsForKey:currentKey], &stop);
	}
}

- (void)enumerateKeysAndObjectsWithOptions:(NSEnumerationOptions)opts usingBlock:(void (^)(id key, NSSet *objs, BOOL *stop))block {
	[self enumerateKeysAndObjectsUsingBlock:block];
}
#endif

@end

@implementation CFIOMultiMap (CFIOMultiMapCreation)

+ (instancetype)multimap {
	return [[[[self class] alloc] init] autorelease];
}

- (instancetype) init {
	self = [super init];
	
	Class actualClass = object_getClass(self);
	CFIMultiMapRef ref = CFIMultiMapCreate(CFAllocatorGetDefault(), NULL, NULL, 0, NULL, NULL);
	memcpy(self, ref, sizeof(_guts));
	object_setClass(self, actualClass);
	CFAllocatorDeallocate(NULL, (void*)ref);
	_guts._dict = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, NULL, NULL);
	
	return self;
}

- (instancetype)initWithMultimap:(CFIOMultiMap *)otherDictionary {
	return [[self.class alloc] initWithMultimap:otherDictionary copyItems:NO];
}

- (instancetype)initWithMultimap:(CFIOMultiMap *)otherDictionary copyItems:(BOOL)flag {
	self = [self init];
	
	CFDictionaryRef dictionary = otherDictionary->_guts._dict;
	_guts._dict = CFDictionaryCreateMutableCopy(kCFAllocatorDefault, CFDictionaryGetCount(dictionary), dictionary);
	
	return self;
}

@end

@implementation CFIOMutableMultiMap : CFIOMultiMap

- (void)removeObjectForKey:(id)aKey {
	CFDictionaryRemoveValue(_guts._dict, (const void *)aKey);
}

- (void)setObjects:(NSSet *)objects forKey:(id <NSCopying>)aKey {
	CFDictionaryAddValue(_guts._dict, (const void *)aKey, (const void *)objects);
}

@end

@implementation CFIOMutableMultiMap (CFIOExtendedMutableMultiMap)

- (void)addEntriesFromMultiMap:(CFIOMultiMap *)otherMultiMap {
	NSEnumerator *keyEnumerator = otherMultiMap.keyEnumerator;
	id currentKey = nil;
	while ((currentKey = [keyEnumerator nextObject]) != nil) {
		CFDictionaryAddValue(_guts._dict, (const void *)currentKey, (const void *)[otherMultiMap objectsForKey:currentKey]);
	}
}

- (void)removeAllObjects {
	CFDictionaryRemoveAllValues(_guts._dict);
}

- (void)removeObjectsForKeys:(NSArray *)keyArray {
	NSEnumerator *keyEnumerator = keyArray.objectEnumerator;
	id currentKey = nil;
	while ((currentKey = [keyEnumerator nextObject]) != nil) {
		CFDictionaryRemoveValue(_guts._dict, (const void *)currentKey);
	}
}

- (void)setObject:(id)obj forKeyedSubscript:(id <NSCopying>)key {
	if ([obj isKindOfClass:NSSet.class]) {
		[self setObjects:obj forKey:key];
	} else {
		[self setObjects:[NSMutableSet setWithObject:obj] forKey:key];
	}
}

@end

@implementation CFIOMutableMultiMap (CFIOMutableMultiMapCreation)

- (instancetype)init {
	self = [super init];
	return self;
}

@end

I'd love to see this on Cocoapods. It took absolutely ages to find this multimap implementation. One would be led to believe that there's not one iOS implementation of a multimap...!

Hmmm. I'm having trouble getting this multimap to work properly. No matter what keys I set (NSNumber, NSString), subscripting always returns nil.

I studied the code and cannot see why the following doesn't work.

    it(@"multimap works", ^{
        CFIOMutableMultiMap *multimap = [[CFIOMutableMultiMap alloc] init];
        multimap[@"numbers"] = @1;

        // When
        expect(multimap[@"numbers"]).to.equal(@1);  // expected: 1, got: nil/null
    });

Hi, I just got your email. I'm so sorry it took this long to reply. First off, I do not recommend you ship any code using this class. It was made for iOS 6 and 7 as a way to explore how Toll-Free Bridging works. As such, there's private APIs out the wazoo in this thing.

Still, you're right about subscripting not working. It's strange that the Objective-C API is having issues like this. I'll look into it, but there's some bigger issues with this thing now that the runtime has changed in 7 and 8.