ObjFW  Check-in [c0098f89fe]

       OFBlock.m			\
       OFConstantString.m		\
       OFCountedSet.m			\
       OFDataArray.m			\
       OFDataArray+Hashing.m		\
       OFDate.m				\
       OFDictionary.m			\
       OFDictionary_hashtable.m		\
       OFDoubleMatrix.m			\
       OFDoubleVector.m			\
       OFEnumerator.m			\
       OFFile.m				\
       OFFloatMatrix.m			\
       OFFloatVector.m			\
       OFHash.m				\
       OFHTTPRequest.m			\
       OFIntrospection.m		\
       OFList.m				\
       OFMD5Hash.m			\
       OFMutableArray.m			\
       OFMutableArray_adjacent.m	\
       OFMutableDictionary.m		\
       OFMutableDictionary_hashtable.m	\
       OFMutableSet.m			\
       OFMutableString.m		\
       OFNull.m				\
       OFNumber.m			\
       OFObject.m			\
       OFObject+Serialization.m		\
       ${OFPLUGIN_M}			\

    BOOL *stop);
typedef BOOL (^of_array_filter_block_t)(id odject, size_t index);
typedef id (^of_array_map_block_t)(id object, size_t index);
typedef id (^of_array_fold_block_t)(id left, id right);
#endif

/**
 * \brief A class for storing objects in an array.
 * \brief An abstract class for storing objects in an array.
 */
@interface OFArray: OFObject <OFCopying, OFMutableCopying, OFCollection,
    OFSerialization>
/**
 * \brief Creates a new OFArray.
 *
 * \return A new autoreleased OFArray

+ arrayWithCArray: (id*)objects
	   length: (size_t)length
{
	return [[[self alloc] initWithCArray: objects
				      length: length] autorelease];
}

- init
{
	if ([self class] == [OFArray class] ||
	    [self class] == [OFMutableArray class]) {
		Class c = isa;
		[self release];
		@throw [OFNotImplementedException newWithClass: c
						      selector: _cmd];
	}

	return [super init];
}

- initWithObject: (id)object
{
	return [self initWithObjects: object, nil];
}

- initWithObjects: (id)firstObject, ...

 */

#include "config.h"

#define OF_COUNTED_SET_M

#import "OFCountedSet.h"
#import "OFDictionary.h"
#import "OFMutableDictionary_hashtable.h"
#import "OFNumber.h"
#import "OFArray.h"
#import "OFString.h"
#import "OFAutoreleasePool.h"

@implementation OFCountedSet
- initWithSet: (OFSet*)set
{
	self = [super init];

	@try {
		[dictionary release];
		dictionary = nil;
		dictionary = [[OFMutableDictionary alloc]
		dictionary = [[OFMutableDictionary_hashtable alloc]
			_initWithDictionary: set->dictionary
				   copyKeys: NO];
	} @catch (id e) {
		[self release];
		@throw e;
	}

#ifdef OF_HAVE_BLOCKS
typedef void (^of_dictionary_enumeration_block_t)(id key, id object,
     BOOL *stop);
typedef BOOL (^of_dictionary_filter_block_t)(id key, id object);
typedef id (^of_dictionary_map_block_t)(id key, id object);
#endif

struct of_dictionary_bucket
{
	id <OFCopying> key;
	id object;
	uint32_t hash;
};

/**
 * \brief A class for storing objects in a hash table.
 * \brief An abstract class for storing objects in a dictionary.
 *
 * Note: Fast enumeration on a dictionary enumerates through the keys of the
 * dictionary.
 */
@interface OFDictionary: OFObject <OFCopying, OFMutableCopying, OFCollection,
    OFSerialization>
{
	struct of_dictionary_bucket **data;
	uint32_t size;
	size_t count;
}

/**
 * \brief Creates a new OFDictionary.
 *
 * \return A new autoreleased OFDictionary
 */
+ dictionary;

#if defined(OF_SET_M) || defined(OF_COUNTED_SET_M)
- _initWithDictionary: (OFDictionary*)dictionary
	     copyKeys: (BOOL)copyKeys;
#endif
@end

@interface OFDictionaryEnumerator: OFEnumerator
@interface OFDictionary_placeholder: OFDictionary
{
	OFDictionary *dictionary;
	struct of_dictionary_bucket **data;
	uint32_t size;
	unsigned long mutations;
	unsigned long *mutationsPtr;
	uint32_t pos;
}

- initWithDictionary: (OFDictionary*)dictionary
		data: (struct of_dictionary_bucket**)data
		size: (uint32_t)size
    mutationsPointer: (unsigned long*)mutationsPtr;
@end

@interface OFDictionaryObjectEnumerator: OFDictionaryEnumerator
@end

@interface OFDictionaryKeyEnumerator: OFDictionaryEnumerator
@end

#import "OFMutableDictionary.h"

#ifdef __cplusplus
extern "C" {
#endif
extern struct of_dictionary_bucket of_dictionary_deleted_bucket;
#ifdef __cplusplus
}
#endif

 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#include "config.h"

#include <string.h>

#include <assert.h>

#import "OFDictionary.h"
#import "OFEnumerator.h"
#import "OFDictionary_hashtable.h"
#import "OFArray.h"
#import "OFString.h"
#import "OFXMLElement.h"
#import "OFAutoreleasePool.h"

#import "OFEnumerationMutationException.h"
#import "OFInvalidArgumentException.h"
#import "OFInvalidFormatException.h"
#import "OFNotImplementedException.h"
#import "OFOutOfRangeException.h"

#import "macros.h"

static struct {
	Class isa;
} placeholder;
struct of_dictionary_bucket of_dictionary_deleted_bucket = {};

#define DELETED &of_dictionary_deleted_bucket


@implementation OFDictionary_placeholder
- init
{
	return (id)[[OFDictionary_hashtable alloc] init];
}

- initWithDictionary: (OFDictionary*)dictionary
{
	return (id)[[OFDictionary_hashtable alloc]
	    initWithDictionary: dictionary];
}

- initWithObject: (id)object
	  forKey: (id <OFCopying>)key
{
	return (id)[[OFDictionary_hashtable alloc] initWithObject: object
							   forKey: key];
}

- initWithObjects: (OFArray*)objects
	  forKeys: (OFArray*)keys
{
	return (id)[[OFDictionary_hashtable alloc] initWithObjects: objects
							   forKeys: keys];
}

- initWithKeysAndObjects: (id <OFCopying>)firstKey, ...
{
	id ret;
	va_list arguments;

	va_start(arguments, firstKey);
	ret = [[OFDictionary_hashtable alloc] initWithKey: firstKey
						arguments: arguments];
	va_end(arguments);

	return ret;
}

- initWithKey: (id <OFCopying>)firstKey
    arguments: (va_list)arguments
{
	return (id)[[OFDictionary_hashtable alloc] initWithKey: firstKey
						     arguments: arguments];
}

- initWithSerialization: (OFXMLElement*)element
{
	return (id)[[OFDictionary_hashtable alloc]
	    initWithSerialization: element];
}

- retain
{
	return self;
}

- autorelease
{
	return self;
}

- (void)release
{
}

- (void)dealloc
{
	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];
	[super dealloc];	/* Get rid of a stupid warning */
}
@end

@implementation OFDictionary
+ (void)initialize
{
	if (self == [OFDictionary class])
		placeholder.isa = [OFDictionary_placeholder class];
}

+ alloc
{
	if (self == [OFDictionary class])
		return (id)&placeholder;

	return [super alloc];
}

+ dictionary
{
	return [[[self alloc] init] autorelease];
}

+ dictionaryWithDictionary: (OFDictionary*)dictionary
{

	va_end(arguments);

	return ret;
}

- init
{
	self = [super init];

	if ([self class] == [OFDictionary class] ||
	@try {
		data = [self allocMemoryWithSize:
		    sizeof(struct of_dictionary_bucket)];
		size = 1;
	    [self class] == [OFMutableDictionary class]) {
		Class c = isa;
		data[0] = NULL;
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- _initWithDictionary: (OFDictionary*)dictionary
	     copyKeys: (BOOL)copyKeys
{
	self = [super init];

	@try {
		uint32_t i;

		if (dictionary == nil)
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		@throw [OFNotImplementedException newWithClass: c
						      selector: _cmd];
	}
		data = [self allocMemoryForNItems: dictionary->size
					 withSize: sizeof(*data)];

		for (i = 0; i < dictionary->size; i++)
			data[i] = NULL;

		size = dictionary->size;
		count = dictionary->count;

		for (i = 0; i < size; i++) {
			id key;
			struct of_dictionary_bucket *bucket;

			if (dictionary->data[i] == NULL ||
			    dictionary->data[i] == DELETED)
				continue;

			bucket = [self allocMemoryWithSize: sizeof(*bucket)];
			key = (copyKeys
			    ? [dictionary->data[i]->key copy]
			    : [dictionary->data[i]->key retain]);

			@try {
				[dictionary->data[i]->object retain];
			} @catch (id e) {
				[key release];
				@throw e;
			}

			bucket->key = key;
			bucket->object = dictionary->data[i]->object;
			bucket->hash = dictionary->data[i]->hash;

			data[i] = bucket;
		}
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
	return [super init];
}

- initWithDictionary: (OFDictionary*)dictionary
{
	return [self _initWithDictionary: dictionary
				copyKeys: YES];
}

	Class c = isa;
- initWithObject: (id)object
	  forKey: (id <OFCopying>)key
{
	self = [super init];

	[self release];
	@try {
		uint32_t i;
		struct of_dictionary_bucket *bucket;

		if (key == nil || object == nil)
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

	@throw [OFNotImplementedException newWithClass: c
					      selector: _cmd];
}
		data = [self allocMemoryForNItems: 2
					 withSize: sizeof(*data)];

		size = 2;
		for (i = 0; i < size; i++)
			data[i] = NULL;

- initWithObject: (id)object
		i = [key hash] & 1;
		bucket = [self allocMemoryWithSize: sizeof(*bucket)];
		key = [key copy];

	  forKey: (id <OFCopying>)key
		@try {
			[object retain];
		} @catch (id e) {
			[key release];
			@throw e;
		}

{
		bucket->key = key;
		bucket->object = object;
		bucket->hash = [key hash];

	return [self initWithKeysAndObjects: key, object, nil];
		data[i] = bucket;
		count = 1;
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithObjects: (OFArray*)objects
	  forKeys: (OFArray*)keys
{
	self = [super init];

	Class c = isa;
	@try {
		id *objectsCArray, *keysCArray;
		uint32_t i, j, newSize;

		keysCArray = [keys cArray];
		objectsCArray = [objects cArray];
		count = [keys count];

		if (count > UINT32_MAX)
			@throw [OFOutOfRangeException newWithClass: isa];

		for (newSize = 1; newSize < count; newSize <<= 1);

		if (newSize == 0)
			@throw [OFOutOfRangeException newWithClass: isa];

		data = [self allocMemoryForNItems: newSize
					 withSize: sizeof(*data)];

		for (j = 0; j < newSize; j++)
			data[j] = NULL;

		size = newSize;

		for (i = 0; i < count; i++) {
			uint32_t hash, last;

			hash = [keysCArray[i] hash];
			last = size;

			for (j = hash & (size - 1); j < last && data[j] != NULL;
			    j++)
				if ([data[j]->key isEqual: keysCArray[i]])
					break;

			/* In case the last bucket is already used */
			if (j >= last) {
				last = hash & (size - 1);

				for (j = 0; j < last && data[j] != NULL; j++)
					if ([data[j]->key
					    isEqual: keysCArray[i]])
						break;
			}

			/* Key not in dictionary */
			if (j >= last || data[j] == NULL ||
			    ![data[j]->key isEqual: keysCArray[i]]) {
				struct of_dictionary_bucket *bucket;
				id <OFCopying> key;

				last = size;

				j = hash & (size - 1);
				for (; j < last && data[j] != NULL; j++);

				/* In case the last bucket is already used */
				if (j >= last) {
					last = hash & (size - 1);

					for (j = 0; j < last && data[j] != NULL;
					    j++);
				}

				if (j >= last)
					@throw [OFOutOfRangeException
					    newWithClass: isa];

				bucket =
				    [self allocMemoryWithSize: sizeof(*bucket)];
				key = [keysCArray[i] copy];

				@try {
					[objectsCArray[i] retain];
				} @catch (id e) {
					[key release];
					@throw e;
				}

				bucket->key = key;
				bucket->object = objectsCArray[i];
				bucket->hash = hash;

				data[j] = bucket;

				continue;
			}

			/*
			 * The key is already in the dictionary. However, we
			 * just replace it so that the programmer gets the same
			 * behavior as if he'd call setObject:forKey: for each
			 * key/object pair.
			 */
			[objectsCArray[i] retain];

			@try {
				[data[j]->object release];
			} @catch (id e) {
				[objectsCArray[i] release];
				@throw e;
			}

			data[j]->object = objectsCArray[i];
		}
	} @catch (id e) {
		[self release];
		@throw e;
	[self release];
	@throw [OFNotImplementedException newWithClass: c
	}

					      selector: _cmd];
	return self;
}

- initWithKeysAndObjects: (id <OFCopying>)firstKey, ...
{
	id ret;
	va_list arguments;

	va_start(arguments, firstKey);
	ret = [self initWithKey: firstKey
		      arguments: arguments];
	va_end(arguments);

	return ret;
}

- initWithKey: (id <OFCopying>)firstKey
    arguments: (va_list)arguments
{
	self = [super init];

	Class c = isa;
	@try {
		id key, object;
		uint32_t i, j, hash, newSize;
		va_list argumentsCopy;
		struct of_dictionary_bucket *bucket;

		va_copy(argumentsCopy, arguments);

		if (firstKey == nil)
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		key = firstKey;

		if ((object = va_arg(arguments, id)) == nil)
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		count = 1;
		for (; va_arg(argumentsCopy, id) != nil; count++);
		count >>= 1;

		if (count > UINT32_MAX)
			@throw [OFOutOfRangeException newWithClass: isa];

		for (newSize = 1; newSize < count; newSize <<= 1);

		if (newSize == 0)
			@throw [OFOutOfRangeException newWithClass: isa];

		data = [self allocMemoryForNItems: newSize
					 withSize: sizeof(*data)];

		for (j = 0; j < newSize; j++)
			data[j] = NULL;

		size = newSize;

		/* Add first key / object pair */
		hash = [key hash];
		j = hash & (size - 1);

		bucket = [self allocMemoryWithSize: sizeof(*bucket)];
		key = [key copy];

		@try {
			[object retain];
		} @catch (id e) {
			[key release];
	[self release];
			@throw e;
		}

		bucket->key = key;
		bucket->object = object;
		bucket->hash = hash;

		data[j] = bucket;

		for (i = 1; i < count; i++) {
			uint32_t last;

			key = va_arg(arguments, id <OFCopying>);
			object = va_arg(arguments, id);

			if (key == nil || object == nil)
				@throw [OFInvalidArgumentException
				    newWithClass: isa
					selector: _cmd];
	@throw [OFNotImplementedException newWithClass: c
					      selector: _cmd];

			hash = [key hash];
			last = size;

			for (j = hash & (size - 1); j < last && data[j] != NULL;
			    j++)
				if ([data[j]->key isEqual: key])
					break;

			/* In case the last bucket is already used */
			if (j >= last) {
				last = hash & (size - 1);

				for (j = 0; j < last && data[j] != NULL; j++)
					if ([data[j]->key isEqual: key])
						break;
			}

			/* Key not in dictionary */
			if (j >= last || data[j] == NULL ||
			    ![data[j]->key isEqual: key]) {
				last = size;

				j = hash & (size - 1);
				for (; j < last && data[j] != NULL; j++);

				/* In case the last bucket is already used */
				if (j >= last) {
					last = hash & (size - 1);

					for (j = 0; j < last && data[j] != NULL;
					    j++);
				}

				if (j >= last)
					@throw [OFOutOfRangeException
					    newWithClass: isa];

				bucket =
				    [self allocMemoryWithSize: sizeof(*bucket)];
				key = [key copy];

				@try {
					[object retain];
				} @catch (id e) {
					[key release];
					@throw e;
				}

				bucket->key = key;
				bucket->object = object;
				bucket->hash = hash;

				data[j] = bucket;

				continue;
			}

			/*
			 * The key is already in the dictionary. However, we
			 * just replace it so that the programmer gets the same
			 * behavior as if he'd call setObject:forKey: for each
			 * key/object pair.
			 */
			[object retain];

			@try {
				[data[j]->object release];
			} @catch (id e) {
				[object release];
				@throw e;
			}

			data[j]->object = object;
			count--;
		}
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithSerialization: (OFXMLElement*)element
{
	@try {
		OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
		OFAutoreleasePool *pool2;
		OFMutableDictionary *dictionary;
		OFArray *keys, *objects;
		OFEnumerator *keyEnumerator, *objectEnumerator;
		OFXMLElement *keyElement, *objectElement;

	Class c = isa;
		if (![[element name] isEqual: [self className]] ||
		    ![[element namespace] isEqual: OF_SERIALIZATION_NS])
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		dictionary = [OFMutableDictionary dictionary];

		keys = [element elementsForName: @"key"
				      namespace: OF_SERIALIZATION_NS];
		objects = [element elementsForName: @"object"
					 namespace: OF_SERIALIZATION_NS];

		if ([keys count] != [objects count])
			@throw [OFInvalidFormatException newWithClass: isa];

		keyEnumerator = [keys objectEnumerator];
		objectEnumerator = [objects objectEnumerator];
		pool2 = [[OFAutoreleasePool alloc] init];

		while ((keyElement = [keyEnumerator nextObject]) != nil &&
		    (objectElement = [objectEnumerator nextObject]) != nil) {
			OFXMLElement *key, *object;

			key = [[keyElement elementsForNamespace:
			    OF_SERIALIZATION_NS] firstObject];
			object = [[objectElement elementsForNamespace:
			    OF_SERIALIZATION_NS] firstObject];

			if (key == nil || object == nil)
				@throw [OFInvalidFormatException
				    newWithClass: isa];

			[dictionary setObject: [object objectByDeserializing]
				       forKey: [key objectByDeserializing]];

			[pool2 releaseObjects];
		}

		self = [self initWithDictionary: dictionary];

		[pool release];
	} @catch (id e) {
		[self release];
		@throw e;
	[self release];
	@throw [OFNotImplementedException newWithClass: c
	}

					      selector: _cmd];
	return self;
}

- (id)objectForKey: (id <OFCopying>)key
{
	uint32_t i, hash, last;

	if (key == nil)
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];
	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];

	hash = [key hash];
	last = size;

	for (i = hash & (size - 1); i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key])
			return data[i]->object;
	}

	if (i < last)
		return nil;

	/* In case the last bucket is already used */
	last = hash & (size - 1);

	for (i = 0; i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key])
			return data[i]->object;
	}

	return nil;
}

- (size_t)count
{
	return count;
	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];
}

- copy
{
	return [self retain];
}

- mutableCopy
{
	return [[OFMutableDictionary alloc] initWithDictionary: self];
}

- (BOOL)isEqual: (id)dict
- (BOOL)isEqual: (id)dictionary
{
	OFAutoreleasePool *pool;
	OFEnumerator *enumerator;
	uint32_t i;
	id <OFCopying> key;

	if ([dict count] != count)
	if ([dictionary count] != [self count])
		return NO;

	pool = [[OFAutoreleasePool alloc] init];
	for (i = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED &&
		    ![[dict objectForKey: data[i]->key]
		    isEqual: data[i]->object])

	enumerator = [self keyEnumerator];
	while ((key = [enumerator nextObject]) != nil) {
		id object = [dictionary objectForKey: key];

		if (object == nil ||
		    ![object isEqual: [self objectForKey: key]]) {
			[pool release];
			return NO;
		}
	}

	[pool release];

	return YES;
}

- (BOOL)containsObject: (id)object
{
	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
	OFEnumerator *enumerator = [self objectEnumerator];
	uint32_t i;
	id currentObject;

	while ((currentObject = [enumerator nextObject]) != nil) {
	if (count == 0)
		return NO;

	for (i = 0; i < size; i++)
		if ([currentObject isEqual: object]) {
			[pool release];
			return YES;
		}
	}

		if (data[i] != NULL && data[i] != DELETED &&
		    [data[i]->object isEqual: object])
			return YES;
	[pool release];

	return NO;
}

- (BOOL)containsObjectIdenticalTo: (id)object
{
	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
	OFEnumerator *enumerator = [self objectEnumerator];
	uint32_t i;
	id currentObject;

	while ((currentObject = [enumerator nextObject]) != nil) {
	if (count == 0)
		return NO;

	for (i = 0; i < size; i++)
		if (currentObject == object) {
			[pool release];
			return YES;
		}
	}

		if (data[i] != NULL && data[i] != DELETED &&
		    data[i]->object == object)
			return YES;
	[pool release];

	return NO;
}

- (OFArray*)allKeys
{
	OFArray *ret;
	id *cArray = [self allocMemoryForNItems: count
	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
	id *cArray = [self allocMemoryForNItems: [self count]
				       withSize: sizeof(id)];
	OFEnumerator *enumerator;
	id <OFCopying> key;
	OFArray *ret;
	size_t i, j;
	size_t i = 0;

	pool = [[OFAutoreleasePool alloc] init];
	enumerator = [self keyEnumerator];
	for (i = j = 0; i < size; i++)

		if (data[i] != NULL && data[i] != DELETED)
			cArray[j++] = data[i]->key;
	while ((key = [enumerator nextObject]) != nil)
		cArray[i++] = key;

	assert(i == [self count]);
	assert(j == count);

	[pool release];

	@try {
		ret = [OFArray arrayWithCArray: cArray
					length: count];
					length: [self count]];
	} @finally {
		[self freeMemory: cArray];
	}

	return ret;
}

- (OFArray*)allObjects
{
	OFArray *ret;
	id *cArray = [self allocMemoryForNItems: count
	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
	id *cArray = [self allocMemoryForNItems: [self count]
				       withSize: sizeof(id)];
	OFEnumerator *enumerator;
	id object;
	OFArray *ret;
	size_t i, j;
	size_t i = 0;

	pool = [[OFAutoreleasePool alloc] init];
	enumerator = [self objectEnumerator];
	for (i = j = 0; i < size; i++)

		if (data[i] != NULL && data[i] != DELETED)
			cArray[j++] = data[i]->object;
	while ((object = [enumerator nextObject]) != nil)
		cArray[i++] = object;

	assert(i == [self count]);
	assert(j == count);

	[pool release];

	@try {
		ret = [OFArray arrayWithCArray: cArray
					length: count];
					length: [self count]];
	} @finally {
		[self freeMemory: cArray];
	}

	return ret;
}

- (OFEnumerator*)objectEnumerator
{
	return [[[OFDictionaryObjectEnumerator alloc]
	    initWithDictionary: self
			  data: data
	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];
			  size: size
	      mutationsPointer: NULL] autorelease];
}

- (OFEnumerator*)keyEnumerator
{
	return [[[OFDictionaryKeyEnumerator alloc]
	    initWithDictionary: self
			  data: data
	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];
			  size: size
	      mutationsPointer: NULL] autorelease];
}

- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state
			   objects: (id*)objects
			     count: (int)count_
{
	int i;

	@throw [OFNotImplementedException newWithClass: isa
	for (i = 0; i < count_; i++) {
		for (; state->state < size && (data[state->state] == NULL ||
		    data[state->state] == DELETED); state->state++);

					      selector: _cmd];
		if (state->state < size) {
			objects[i] = data[state->state]->key;
			state->state++;
		} else
			break;
	}

	state->itemsPtr = objects;
	state->mutationsPtr = (unsigned long*)self;

	return i;
}

#ifdef OF_HAVE_BLOCKS
- (void)enumerateKeysAndObjectsUsingBlock:
    (of_dictionary_enumeration_block_t)block
{
	size_t i;
	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
	OFEnumerator *enumerator = [self keyEnumerator];
	id <OFCopying> key;
	BOOL stop = NO;

	for (i = 0; i < size && !stop; i++)
		if (data[i] != NULL && data[i] != DELETED)
	while (!stop && (key = [enumerator nextObject]) != nil)
		block(key, [self objectForKey: key], &stop);

			block(data[i]->key, data[i]->object, &stop);
	[pool release];
}

- (OFDictionary*)mappedDictionaryUsingBlock: (of_dictionary_map_block_t)block
{
	OFMutableDictionary *new = [OFMutableDictionary dictionary];

	[self enumerateKeysAndObjectsUsingBlock: ^ (id key, id object,

	[new makeImmutable];

	return new;
}
#endif

- (void)dealloc
{
	uint32_t i;

- (uint32_t)hash
{
	for (i = 0; i < size; i++) {
		if (data[i] != NULL && data[i] != DELETED) {
			[data[i]->key release];
	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
			[data[i]->object release];
		}
	}

	OFEnumerator *enumerator = [self keyEnumerator];
	[super dealloc];
}

	id <OFCopying> key;
- (uint32_t)hash
{
	uint32_t i;
	uint32_t hash;
	uint32_t hash = 0;

	OF_HASH_INIT(hash);

	while ((key = [enumerator nextObject]) != nil) {
	for (i = 0; i < size; i++) {
		if (data[i] != NULL && data[i] != DELETED) {
			uint32_t h = [data[i]->object hash];

		hash += [key hash];
			OF_HASH_ADD(hash, data[i]->hash >> 24);
			OF_HASH_ADD(hash, (data[i]->hash >> 16) & 0xFF);
			OF_HASH_ADD(hash, (data[i]->hash >> 8) & 0xFF);
			OF_HASH_ADD(hash, data[i]->hash & 0xFF);

		hash += [[self objectForKey: key] hash];
			OF_HASH_ADD(hash, h >> 24);
			OF_HASH_ADD(hash, (h >> 16) & 0xFF);
			OF_HASH_ADD(hash, (h >> 8) & 0xFF);
			OF_HASH_ADD(hash, h & 0xFF);
		}
	}

	}

	[pool release];
	OF_HASH_FINALIZE(hash);

	return hash;
}

- (OFString*)description
{
	OFMutableString *ret;
	OFAutoreleasePool *pool, *pool2;
	OFEnumerator *keyEnumerator, *objectEnumerator;
	id key, object;
	size_t i;
	size_t i, count = [self count];

	if (count == 0)
		return @"{()}";

	ret = [OFMutableString stringWithString: @"{\n"];
	pool = [[OFAutoreleasePool alloc] init];
	keyEnumerator = [self keyEnumerator];

{
	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
	OFAutoreleasePool *pool2;
	OFXMLElement *element;
	OFEnumerator *keyEnumerator, *objectEnumerator;
	id <OFSerialization> key, object;

	if ([self isKindOfClass: [OFMutableDictionary class]])
	element = [OFXMLElement elementWithName: [self className]
				      namespace: OF_SERIALIZATION_NS];
		element = [OFXMLElement elementWithName: @"OFMutableDictionary"
					      namespace: OF_SERIALIZATION_NS];
	else
		element = [OFXMLElement elementWithName: @"OFDictionary"
					      namespace: OF_SERIALIZATION_NS];

	keyEnumerator = [self keyEnumerator];
	objectEnumerator = [self objectEnumerator];
	pool2 = [[OFAutoreleasePool alloc] init];

	while ((key = [keyEnumerator nextObject]) != nil &&
	       (object = [objectEnumerator nextObject]) != nil) {

		[pool release];
	} @finally {
		[element autorelease];
	}

	return element;
}
@end

@implementation OFDictionaryEnumerator
- initWithDictionary: (OFDictionary*)dictionary_
		data: (struct of_dictionary_bucket**)data_
		size: (uint32_t)size_
    mutationsPointer: (unsigned long*)mutationsPtr_
{
	self = [super init];

	dictionary = [dictionary_ retain];
	data = data_;
	size = size_;
	mutations = (mutationsPtr_ != NULL ? *mutationsPtr_ : 0);
	mutationsPtr = mutationsPtr_;

	return self;
}

- (void)dealloc
{
	[dictionary release];

	[super dealloc];
}

- (void)reset
{
	if (mutationsPtr != NULL && *mutationsPtr != mutations)
		@throw [OFEnumerationMutationException
		    newWithClass: isa
			  object: dictionary];

	pos = 0;
}
@end

@implementation OFDictionaryObjectEnumerator
- (id)nextObject
{
	if (mutationsPtr != NULL && *mutationsPtr != mutations)
		@throw [OFEnumerationMutationException
		    newWithClass: isa
			  object: dictionary];

	for (; pos < size && (data[pos] == NULL ||
	    data[pos] == DELETED); pos++);

	if (pos < size)
		return data[pos++]->object;
	else
		return nil;
}
@end

@implementation OFDictionaryKeyEnumerator
- (id)nextObject
{
	if (mutationsPtr != NULL && *mutationsPtr != mutations)
		@throw [OFEnumerationMutationException
		    newWithClass: isa
			  object: dictionary];

	for (; pos < size && (data[pos] == NULL ||
	    data[pos] == DELETED); pos++);

	if (pos < size)
		return data[pos++]->key;
	else
		return nil;
}
@end

/*
 * Copyright (c) 2008, 2009, 2010, 2011
 *   Jonathan Schleifer <js@webkeks.org>
 *
 * All rights reserved.
 *
 * This file is part of ObjFW. It may be distributed under the terms of the
 * Q Public License 1.0, which can be found in the file LICENSE.QPL included in
 * the packaging of this file.
 *
 * Alternatively, it may be distributed under the terms of the GNU General
 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#import "OFDictionary.h"

struct of_dictionary_hashtable_bucket
{
	id <OFCopying> key;
	id object;
	uint32_t hash;
};

@interface OFDictionary_hashtable: OFDictionary
{
	struct of_dictionary_hashtable_bucket **data;
	uint32_t size;
	size_t count;
}

#if defined(OF_SET_M) || defined(OF_COUNTED_SET_M)
- _initWithDictionary: (OFDictionary*)dictionary
	     copyKeys: (BOOL)copyKeys;
#endif
@end

@interface OFDictionaryEnumerator_hashtable: OFEnumerator
{
	OFDictionary_hashtable *dictionary;
	struct of_dictionary_hashtable_bucket **data;
	uint32_t size;
	unsigned long mutations;
	unsigned long *mutationsPtr;
	uint32_t pos;
}

- initWithDictionary: (OFDictionary_hashtable*)dictionary
		data: (struct of_dictionary_hashtable_bucket**)data
		size: (uint32_t)size
    mutationsPointer: (unsigned long*)mutationsPtr;
@end

@interface OFDictionaryKeyEnumerator_hashtable: OFDictionaryEnumerator_hashtable
@end

@interface OFDictionaryObjectEnumerator_hashtable:
    OFDictionaryEnumerator_hashtable
@end

#ifdef __cplusplus
extern "C" {
#endif
extern struct of_dictionary_hashtable_bucket
    of_dictionary_hashtable_deleted_bucket;
#ifdef __cplusplus
}
#endif

/*
 * Copyright (c) 2008, 2009, 2010, 2011
 *   Jonathan Schleifer <js@webkeks.org>
 *
 * All rights reserved.
 *
 * This file is part of ObjFW. It may be distributed under the terms of the
 * Q Public License 1.0, which can be found in the file LICENSE.QPL included in
 * the packaging of this file.
 *
 * Alternatively, it may be distributed under the terms of the GNU General
 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#include "config.h"

#include <string.h>

#include <assert.h>

#import "OFDictionary_hashtable.h"
#import "OFMutableDictionary_hashtable.h"
#import "OFEnumerator.h"
#import "OFArray.h"
#import "OFString.h"
#import "OFXMLElement.h"
#import "OFAutoreleasePool.h"

#import "OFEnumerationMutationException.h"
#import "OFInvalidArgumentException.h"
#import "OFInvalidFormatException.h"
#import "OFNotImplementedException.h"
#import "OFOutOfRangeException.h"

#import "macros.h"

struct of_dictionary_hashtable_bucket
    of_dictionary_hashtable_deleted_bucket = {};
#define DELETED &of_dictionary_hashtable_deleted_bucket

@implementation OFDictionary_hashtable
- init
{
	self = [super init];

	@try {
		data = [self allocMemoryWithSize: sizeof(*data)];
		size = 1;
		data[0] = NULL;
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- _initWithDictionary: (OFDictionary*)dictionary
	     copyKeys: (BOOL)copyKeys
{
	self = [super init];

	@try {
		uint32_t i;
		OFDictionary_hashtable *hashtable;

		if (dictionary == nil)
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		if (![dictionary isKindOfClass:
		    [OFDictionary_hashtable class]] &&
		    ![dictionary isKindOfClass:
		    [OFMutableDictionary_hashtable class]])
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		hashtable = (OFDictionary_hashtable*)dictionary;

		data = [self allocMemoryForNItems: hashtable->size
					 withSize: sizeof(*data)];

		for (i = 0; i < hashtable->size; i++)
			data[i] = NULL;

		size = hashtable->size;
		count = hashtable->count;

		for (i = 0; i < size; i++) {
			id key;
			struct of_dictionary_hashtable_bucket *bucket;

			if (hashtable->data[i] == NULL ||
			    hashtable->data[i] == DELETED)
				continue;

			bucket = [self allocMemoryWithSize: sizeof(*bucket)];
			key = (copyKeys
			    ? [hashtable->data[i]->key copy]
			    : [hashtable->data[i]->key retain]);

			@try {
				[hashtable->data[i]->object retain];
			} @catch (id e) {
				[key release];
				@throw e;
			}

			bucket->key = key;
			bucket->object = hashtable->data[i]->object;
			bucket->hash = hashtable->data[i]->hash;

			data[i] = bucket;
		}
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithDictionary: (OFDictionary*)dictionary
{
	self = [super init];

	@try {
		OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
		OFEnumerator *enumerator;
		id <OFCopying> key;
		uint32_t i, newSize;

		count = [dictionary count];

		if (count > UINT32_MAX)
			@throw [OFOutOfRangeException newWithClass: isa];

		for (newSize = 1; newSize < count; newSize <<= 1);

		if (newSize == 0)
			@throw [OFOutOfRangeException newWithClass: isa];

		data = [self allocMemoryForNItems: newSize
					 withSize: sizeof(*data)];

		for (i = 0; i < newSize; i++)
			data[i] = NULL;

		size = newSize;

		pool = [[OFAutoreleasePool alloc] init];
		enumerator = [dictionary keyEnumerator];

		while ((key = [enumerator nextObject]) != nil) {
			uint32_t hash, last;
			struct of_dictionary_hashtable_bucket *bucket;
			id object;

			hash = [key hash];
			last = size;

			for (i = hash & (size - 1); i < last && data[i] != NULL;
			    i++);

			/* In case the last bucket is already used */
			if (i >= last) {
				last = hash & (size - 1);

				for (i = 0; i < last && data[i] != NULL; i++);
			}

			if (data[i] != NULL)
				@throw [OFOutOfRangeException
				    newWithClass: isa];

			bucket = [self allocMemoryWithSize: sizeof(*bucket)];
			key = [key copy];

			@try {
				object = [dictionary objectForKey: key];
				[object retain];
			} @catch (id e) {
				[key release];
				@throw e;
			}

			bucket->key = key;
			bucket->object = object;
			bucket->hash = hash;

			data[i] = bucket;
		}

		[pool release];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithObject: (id)object
	  forKey: (id <OFCopying>)key
{
	self = [super init];

	@try {
		uint32_t i;
		struct of_dictionary_hashtable_bucket *bucket;

		if (key == nil || object == nil)
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		data = [self allocMemoryForNItems: 2
					 withSize: sizeof(*data)];

		size = 2;
		for (i = 0; i < size; i++)
			data[i] = NULL;

		i = [key hash] & 1;
		bucket = [self allocMemoryWithSize: sizeof(*bucket)];
		key = [key copy];

		@try {
			[object retain];
		} @catch (id e) {
			[key release];
			@throw e;
		}

		bucket->key = key;
		bucket->object = object;
		bucket->hash = [key hash];

		data[i] = bucket;
		count = 1;
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithObjects: (OFArray*)objects
	  forKeys: (OFArray*)keys
{
	self = [super init];

	@try {
		id *objectsCArray, *keysCArray;
		uint32_t i, j, newSize;

		keysCArray = [keys cArray];
		objectsCArray = [objects cArray];
		count = [keys count];

		if (count > UINT32_MAX)
			@throw [OFOutOfRangeException newWithClass: isa];

		for (newSize = 1; newSize < count; newSize <<= 1);

		if (newSize == 0)
			@throw [OFOutOfRangeException newWithClass: isa];

		data = [self allocMemoryForNItems: newSize
					 withSize: sizeof(*data)];

		for (j = 0; j < newSize; j++)
			data[j] = NULL;

		size = newSize;

		for (i = 0; i < count; i++) {
			uint32_t hash, last;

			hash = [keysCArray[i] hash];
			last = size;

			for (j = hash & (size - 1); j < last && data[j] != NULL;
			    j++)
				if ([data[j]->key isEqual: keysCArray[i]])
					break;

			/* In case the last bucket is already used */
			if (j >= last) {
				last = hash & (size - 1);

				for (j = 0; j < last && data[j] != NULL; j++)
					if ([data[j]->key
					    isEqual: keysCArray[i]])
						break;
			}

			/* Key not in dictionary */
			if (j >= last || data[j] == NULL ||
			    ![data[j]->key isEqual: keysCArray[i]]) {
				struct of_dictionary_hashtable_bucket *bucket;
				id <OFCopying> key;

				last = size;

				j = hash & (size - 1);
				for (; j < last && data[j] != NULL; j++);

				/* In case the last bucket is already used */
				if (j >= last) {
					last = hash & (size - 1);

					for (j = 0; j < last && data[j] != NULL;
					    j++);
				}

				if (j >= last)
					@throw [OFOutOfRangeException
					    newWithClass: isa];

				bucket =
				    [self allocMemoryWithSize: sizeof(*bucket)];
				key = [keysCArray[i] copy];

				@try {
					[objectsCArray[i] retain];
				} @catch (id e) {
					[key release];
					@throw e;
				}

				bucket->key = key;
				bucket->object = objectsCArray[i];
				bucket->hash = hash;

				data[j] = bucket;

				continue;
			}

			/*
			 * The key is already in the dictionary. However, we
			 * just replace it so that the programmer gets the same
			 * behavior as if he'd call setObject:forKey: for each
			 * key/object pair.
			 */
			[objectsCArray[i] retain];

			@try {
				[data[j]->object release];
			} @catch (id e) {
				[objectsCArray[i] release];
				@throw e;
			}

			data[j]->object = objectsCArray[i];
		}
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithKey: (id <OFCopying>)firstKey
    arguments: (va_list)arguments
{
	self = [super init];

	@try {
		id key, object;
		uint32_t i, j, hash, newSize;
		va_list argumentsCopy;
		struct of_dictionary_hashtable_bucket *bucket;

		va_copy(argumentsCopy, arguments);

		if (firstKey == nil)
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		key = firstKey;

		if ((object = va_arg(arguments, id)) == nil)
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		count = 1;
		for (; va_arg(argumentsCopy, id) != nil; count++);
		count >>= 1;

		if (count > UINT32_MAX)
			@throw [OFOutOfRangeException newWithClass: isa];

		for (newSize = 1; newSize < count; newSize <<= 1);

		if (newSize == 0)
			@throw [OFOutOfRangeException newWithClass: isa];

		data = [self allocMemoryForNItems: newSize
					 withSize: sizeof(*data)];

		for (j = 0; j < newSize; j++)
			data[j] = NULL;

		size = newSize;

		/* Add first key / object pair */
		hash = [key hash];
		j = hash & (size - 1);

		bucket = [self allocMemoryWithSize: sizeof(*bucket)];
		key = [key copy];

		@try {
			[object retain];
		} @catch (id e) {
			[key release];
			@throw e;
		}

		bucket->key = key;
		bucket->object = object;
		bucket->hash = hash;

		data[j] = bucket;

		for (i = 1; i < count; i++) {
			uint32_t last;

			key = va_arg(arguments, id <OFCopying>);
			object = va_arg(arguments, id);

			if (key == nil || object == nil)
				@throw [OFInvalidArgumentException
				    newWithClass: isa
					selector: _cmd];

			hash = [key hash];
			last = size;

			for (j = hash & (size - 1); j < last && data[j] != NULL;
			    j++)
				if ([data[j]->key isEqual: key])
					break;

			/* In case the last bucket is already used */
			if (j >= last) {
				last = hash & (size - 1);

				for (j = 0; j < last && data[j] != NULL; j++)
					if ([data[j]->key isEqual: key])
						break;
			}

			/* Key not in dictionary */
			if (j >= last || data[j] == NULL ||
			    ![data[j]->key isEqual: key]) {
				last = size;

				j = hash & (size - 1);
				for (; j < last && data[j] != NULL; j++);

				/* In case the last bucket is already used */
				if (j >= last) {
					last = hash & (size - 1);

					for (j = 0; j < last && data[j] != NULL;
					    j++);
				}

				if (j >= last)
					@throw [OFOutOfRangeException
					    newWithClass: isa];

				bucket =
				    [self allocMemoryWithSize: sizeof(*bucket)];
				key = [key copy];

				@try {
					[object retain];
				} @catch (id e) {
					[key release];
					@throw e;
				}

				bucket->key = key;
				bucket->object = object;
				bucket->hash = hash;

				data[j] = bucket;

				continue;
			}

			/*
			 * The key is already in the dictionary. However, we
			 * just replace it so that the programmer gets the same
			 * behavior as if he'd call setObject:forKey: for each
			 * key/object pair.
			 */
			[object retain];

			@try {
				[data[j]->object release];
			} @catch (id e) {
				[object release];
				@throw e;
			}

			data[j]->object = object;
			count--;
		}
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithSerialization: (OFXMLElement*)element
{
	@try {
		OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
		OFAutoreleasePool *pool2;
		OFMutableDictionary *dictionary;
		OFArray *keys, *objects;
		OFEnumerator *keyEnumerator, *objectEnumerator;
		OFXMLElement *keyElement, *objectElement;

		if ((![[element name] isEqual: @"OFDictionary"] &&
		    ![[element name] isEqual: @"OFMutableDictionary"]) ||
		    ![[element namespace] isEqual: OF_SERIALIZATION_NS])
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];

		dictionary = [OFMutableDictionary dictionary];

		keys = [element elementsForName: @"key"
				      namespace: OF_SERIALIZATION_NS];
		objects = [element elementsForName: @"object"
					 namespace: OF_SERIALIZATION_NS];

		if ([keys count] != [objects count])
			@throw [OFInvalidFormatException newWithClass: isa];

		keyEnumerator = [keys objectEnumerator];
		objectEnumerator = [objects objectEnumerator];
		pool2 = [[OFAutoreleasePool alloc] init];

		while ((keyElement = [keyEnumerator nextObject]) != nil &&
		    (objectElement = [objectEnumerator nextObject]) != nil) {
			OFXMLElement *key, *object;

			key = [[keyElement elementsForNamespace:
			    OF_SERIALIZATION_NS] firstObject];
			object = [[objectElement elementsForNamespace:
			    OF_SERIALIZATION_NS] firstObject];

			if (key == nil || object == nil)
				@throw [OFInvalidFormatException
				    newWithClass: isa];

			[dictionary setObject: [object objectByDeserializing]
				       forKey: [key objectByDeserializing]];

			[pool2 releaseObjects];
		}

		self = [self initWithDictionary: dictionary];

		[pool release];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- (id)objectForKey: (id <OFCopying>)key
{
	uint32_t i, hash, last;

	if (key == nil)
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];

	hash = [key hash];
	last = size;

	for (i = hash & (size - 1); i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key])
			return data[i]->object;
	}

	if (i < last)
		return nil;

	/* In case the last bucket is already used */
	last = hash & (size - 1);

	for (i = 0; i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key])
			return data[i]->object;
	}

	return nil;
}

- (size_t)count
{
	return count;
}

- (BOOL)isEqual: (id)dictionary
{
	uint32_t i;

	if ([self class] != [OFDictionary_hashtable class] &&
	    [self class] != [OFMutableDictionary_hashtable class])
		return [super isEqual: dictionary];

	if ([dictionary count] != count)
		return NO;

	for (i = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED &&
		    ![[dictionary objectForKey: data[i]->key]
		    isEqual: data[i]->object])
			return NO;

	return YES;
}

- (BOOL)containsObject: (id)object
{
	uint32_t i;

	if (count == 0)
		return NO;

	for (i = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED &&
		    [data[i]->object isEqual: object])
			return YES;

	return NO;
}

- (BOOL)containsObjectIdenticalTo: (id)object
{
	uint32_t i;

	if (count == 0)
		return NO;

	for (i = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED &&
		    data[i]->object == object)
			return YES;

	return NO;
}

- (OFArray*)allKeys
{
	OFArray *ret;
	id *cArray = [self allocMemoryForNItems: count
				       withSize: sizeof(id)];
	size_t i, j;

	for (i = j = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED)
			cArray[j++] = data[i]->key;

	assert(j == count);

	@try {
		ret = [OFArray arrayWithCArray: cArray
					length: count];
	} @finally {
		[self freeMemory: cArray];
	}

	return ret;
}

- (OFArray*)allObjects
{
	OFArray *ret;
	id *cArray = [self allocMemoryForNItems: count
				       withSize: sizeof(id)];
	size_t i, j;

	for (i = j = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED)
			cArray[j++] = data[i]->object;

	assert(j == count);

	@try {
		ret = [OFArray arrayWithCArray: cArray
					length: count];
	} @finally {
		[self freeMemory: cArray];
	}

	return ret;
}

- (OFEnumerator*)keyEnumerator
{
	return [[[OFDictionaryKeyEnumerator_hashtable alloc]
	    initWithDictionary: self
			  data: data
			  size: size
	      mutationsPointer: NULL] autorelease];
}

- (OFEnumerator*)objectEnumerator
{
	return [[[OFDictionaryObjectEnumerator_hashtable alloc]
	    initWithDictionary: self
			  data: data
			  size: size
	      mutationsPointer: NULL] autorelease];
}

- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state
			   objects: (id*)objects
			     count: (int)count_
{
	int i;

	for (i = 0; i < count_; i++) {
		for (; state->state < size && (data[state->state] == NULL ||
		    data[state->state] == DELETED); state->state++);

		if (state->state < size) {
			objects[i] = data[state->state]->key;
			state->state++;
		} else
			break;
	}

	state->itemsPtr = objects;
	state->mutationsPtr = (unsigned long*)self;

	return i;
}

#ifdef OF_HAVE_BLOCKS
- (void)enumerateKeysAndObjectsUsingBlock:
    (of_dictionary_enumeration_block_t)block
{
	size_t i;
	BOOL stop = NO;

	for (i = 0; i < size && !stop; i++)
		if (data[i] != NULL && data[i] != DELETED)
			block(data[i]->key, data[i]->object, &stop);
}
#endif

- (void)dealloc
{
	uint32_t i;

	for (i = 0; i < size; i++) {
		if (data[i] != NULL && data[i] != DELETED) {
			[data[i]->key release];
			[data[i]->object release];
		}
	}

	[super dealloc];
}

- (uint32_t)hash
{
	uint32_t i, hash = 0;

	for (i = 0; i < size; i++) {
		if (data[i] != NULL && data[i] != DELETED) {
			hash += data[i]->hash;
			hash += [data[i]->object hash];
		}
	}

	return hash;
}
@end

@implementation OFDictionaryEnumerator_hashtable
- initWithDictionary: (OFDictionary_hashtable*)dictionary_
		data: (struct of_dictionary_hashtable_bucket**)data_
		size: (uint32_t)size_
    mutationsPointer: (unsigned long*)mutationsPtr_
{
	self = [super init];

	dictionary = [dictionary_ retain];
	data = data_;
	size = size_;
	mutations = (mutationsPtr_ != NULL ? *mutationsPtr_ : 0);
	mutationsPtr = mutationsPtr_;

	return self;
}

- (void)dealloc
{
	[dictionary release];

	[super dealloc];
}

- (void)reset
{
	if (mutationsPtr != NULL && *mutationsPtr != mutations)
		@throw [OFEnumerationMutationException
		    newWithClass: isa
			  object: dictionary];

	pos = 0;
}
@end

@implementation OFDictionaryObjectEnumerator_hashtable
- (id)nextObject
{
	if (mutationsPtr != NULL && *mutationsPtr != mutations)
		@throw [OFEnumerationMutationException
		    newWithClass: isa
			  object: dictionary];

	for (; pos < size && (data[pos] == NULL ||
	    data[pos] == DELETED); pos++);

	if (pos < size)
		return data[pos++]->object;
	else
		return nil;
}
@end

@implementation OFDictionaryKeyEnumerator_hashtable
- (id)nextObject
{
	if (mutationsPtr != NULL && *mutationsPtr != mutations)
		@throw [OFEnumerationMutationException
		    newWithClass: isa
			  object: dictionary];

	for (; pos < size && (data[pos] == NULL ||
	    data[pos] == DELETED); pos++);

	if (pos < size)
		return data[pos++]->key;
	else
		return nil;
}
@end

#import "OFDictionary.h"

#ifdef OF_HAVE_BLOCKS
typedef id (^of_dictionary_replace_block_t)(id key, id object, BOOL *stop);
#endif

/**
 * \brief A class for using mutable hash tables.
 * \brief An abstract class for using mutable dictionaries.
 */
@interface OFMutableDictionary: OFDictionary
{
	unsigned long mutations;
}

/**
 * \brief Sets an object for a key.
 *
 * A key can be any object that conforms to the OFCopying protocol.
 *
 * \param key The key to set
 * \param object The object to set the key to

 * \brief Replaces each object with the object returned by the block.
 *
 * \param block The block which returns a new object for each object
 */
- (void)replaceObjectsUsingBlock: (of_dictionary_replace_block_t)block;
#endif

#if defined(OF_SET_M) || defined(OF_MUTABLE_SET_M) || defined(OF_COUNTED_SET_M)
- (void)_setObject: (id)object
	    forKey: (id)key
	   copyKey: (BOOL)copyKey;
#endif

/**
 * \brief Converts the mutable dictionary to an immutable dictionary.
 */
- (void)makeImmutable;
@end

@interface OFMutableDictionary_placeholder: OFDictionary
@end

 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#include "config.h"

#import "OFMutableDictionary_hashtable.h"
#import "OFAutoreleasePool.h"
#include <string.h>

#import "OFNotImplementedException.h"

#import "macros.h"

static struct {
	Class isa;
} placeholder;

#import "OFMutableDictionary.h"
#import "OFAutoreleasePool.h"

#import "OFEnumerationMutationException.h"
#import "OFInvalidArgumentException.h"
#import "OFOutOfRangeException.h"

#import "macros.h"
@implementation OFMutableDictionary_placeholder
- init
{
	return (id)[[OFMutableDictionary_hashtable alloc] init];
}

- initWithDictionary: (OFDictionary*)dictionary
{
	return (id)[[OFMutableDictionary_hashtable alloc]
	    initWithDictionary: dictionary];
}

- initWithObject: (id)object
	  forKey: (id <OFCopying>)key
{
	return (id)[[OFMutableDictionary_hashtable alloc] initWithObject: object
								  forKey: key];
}

- initWithObjects: (OFArray*)objects
	  forKeys: (OFArray*)keys
{
	return (id)[[OFMutableDictionary_hashtable alloc]
	    initWithObjects: objects
		    forKeys: keys];
}

- initWithKeysAndObjects: (id <OFCopying>)firstKey, ...
{
	id ret;
	va_list arguments;

	va_start(arguments, firstKey);
	ret = (id)[[OFMutableDictionary_hashtable alloc]
	    initWithKey: firstKey
	      arguments: arguments];
	va_end(arguments);

	return ret;
}
#define DELETED &of_dictionary_deleted_bucket

- initWithKey: (id <OFCopying>)firstKey
    arguments: (va_list)arguments
{
	return (id)[[OFMutableDictionary_hashtable alloc]
	    initWithKey: firstKey
	      arguments: arguments];
}

- initWithSerialization: (OFXMLElement*)element
{
	return (id)[[OFMutableDictionary_hashtable alloc]
	    initWithSerialization: element];
}

- retain
{
	return self;
}

- autorelease
{
	return self;
}

- (void)release
{
}

- (void)dealloc
{
	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];
	[super dealloc];	/* Get rid of a stupid warning */
}
@end

@implementation OFMutableDictionary
- (void)_resizeForCount: (size_t)newCount
{
	size_t fullness = newCount * 4 / size;
	struct of_dictionary_bucket **newData;
	uint32_t i, newSize;

+ (void)initialize
	if (newCount > UINT32_MAX)
		@throw [OFOutOfRangeException newWithClass: isa];

{
	if (fullness >= 3)
		newSize = size << 1;
	else if (fullness <= 1)
		newSize = size >> 1;
	else
		return;

	if (self == [OFMutableDictionary class])
	if (newSize == 0)
		@throw [OFOutOfRangeException newWithClass: isa];

		placeholder.isa = [OFMutableDictionary_placeholder class];
	newData = [self allocMemoryForNItems: newSize
				    withSize: sizeof(*newData)];

}
	for (i = 0; i < newSize; i++)
		newData[i] = NULL;

	for (i = 0; i < size; i++) {
		if (data[i] != NULL && data[i] != DELETED) {
			uint32_t j, last;

			last = newSize;

			j = data[i]->hash & (newSize - 1);
			for (; j < last && newData[j] != NULL; j++);

			/* In case the last bucket is already used */
			if (j >= last) {
				last = data[i]->hash & (newSize - 1);

				for (j = 0; j < last &&
				    newData[j] != NULL; j++);
			}

			if (j >= last) {
				[self freeMemory: newData];
				@throw [OFOutOfRangeException
				    newWithClass: isa];
			}

			newData[j] = data[i];
		}
	}

	[self freeMemory: data];
	data = newData;
	size = newSize;
}

- (void)_setObject: (id)object
	    forKey: (id)key
	   copyKey: (BOOL)copyKey
{
	uint32_t i, hash, last;
	id old;

	if (key == nil || object == nil)
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];

	hash = [key hash];
	last = size;

	for (i = hash & (size - 1); i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key])
			break;
	}

+ alloc
	/* In case the last bucket is already used */
	if (i >= last) {
		last = hash & (size - 1);

{
		for (i = 0; i < last && data[i] != NULL; i++) {
			if (data[i] == DELETED)
				continue;

	if (self == [OFMutableDictionary class])
			if ([data[i]->key isEqual: key])
				break;
		}
	}

		return (id)&placeholder;
	/* Key not in dictionary */
	if (i >= last || data[i] == NULL || data[i] == DELETED ||
	    ![data[i]->key isEqual: key]) {
		struct of_dictionary_bucket *bucket;

		[self _resizeForCount: count + 1];

		mutations++;
		last = size;

		for (i = hash & (size - 1); i < last && data[i] != NULL &&
		    data[i] != DELETED; i++);

		/* In case the last bucket is already used */
		if (i >= last) {
			last = hash & (size - 1);

			for (i = 0; i < last && data[i] != NULL &&
			    data[i] != DELETED; i++);
		}

		if (i >= last)
			@throw [OFOutOfRangeException newWithClass: isa];

		bucket = [self allocMemoryWithSize: sizeof(*bucket)];

		@try {
			key = (copyKey ? [key copy] : [key retain]);
		} @catch (id e) {
			[self freeMemory: bucket];
			@throw e;
		}

		@try {
			[object retain];
		} @catch (id e) {
			[self freeMemory: bucket];
			[key release];
			@throw e;
		}

		bucket->key = key;
		bucket->object = object;
		bucket->hash = hash;
		data[i] = bucket;
		count++;

		return;
	return [super alloc];
	}

	old = data[i]->object;
	data[i]->object = [object retain];
	[old release];
}

- (void)setObject: (id)object
	   forKey: (id <OFCopying>)key
{
	[self _setObject: object
		  forKey: key
	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];
		 copyKey: YES];
}

- (void)removeObjectForKey: (id <OFCopying>)key
{
	uint32_t i, hash, last;

	if (key == nil)
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];
	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];

	hash = [key hash];
	last = size;

	for (i = hash & (size - 1); i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key]) {
			[data[i]->key release];
			[data[i]->object release];
			[self freeMemory: data[i]];
			data[i] = DELETED;

			count--;
			mutations++;
			[self _resizeForCount: count];

			return;
		}
	}

	if (i < last)
		return;

	/* In case the last bucket is already used */
	last = hash & (size - 1);

	for (i = 0; i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key]) {
			[data[i]->key release];
			[data[i]->object release];
			[self freeMemory: data[i]];
			data[i] = DELETED;

			count--;
			mutations++;
			[self _resizeForCount: count];

			return;
		}
	}
}

- copy
{
	return [[OFDictionary alloc] initWithDictionary: self];
}

- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state
			   objects: (id*)objects
			     count: (int)count_
{
	int ret = [super countByEnumeratingWithState: state
					     objects: objects
					       count: count_];

	state->mutationsPtr = &mutations;

	return ret;
}

- (OFEnumerator*)objectEnumerator
{
	return [[[OFDictionaryObjectEnumerator alloc]
	    initWithDictionary: self
			 data: data
			 size: size
	     mutationsPointer: &mutations] autorelease];
}

- (OFEnumerator*)keyEnumerator
{
	return [[[OFDictionaryKeyEnumerator alloc]
	    initWithDictionary: self
			 data: data
			 size: size
	     mutationsPointer: &mutations] autorelease];
}

#ifdef OF_HAVE_BLOCKS
- (void)enumerateKeysAndObjectsUsingBlock:
    (of_dictionary_enumeration_block_t)block
{
	size_t i;
	BOOL stop = NO;
	unsigned long mutations2 = mutations;

	for (i = 0; i < size && !stop; i++) {
		if (mutations != mutations2)
			@throw [OFEnumerationMutationException
			    newWithClass: isa
				  object: self];

		if (data[i] != NULL && data[i] != DELETED)
			block(data[i]->key, data[i]->object, &stop);
	}
}

- (void)replaceObjectsUsingBlock: (of_dictionary_replace_block_t)block
{
	size_t i;
	BOOL stop = NO;
	unsigned long mutations2 = mutations;

	[self enumerateKeysAndObjectsUsingBlock: ^ (id key, id object,
	for (i = 0; i < size && !stop; i++) {
		if (mutations != mutations2)
			@throw [OFEnumerationMutationException
			    newWithClass: isa
				  object: self];

	    BOOL *stop) {
		if (data[i] != NULL && data[i] != DELETED) {
			id new = block(data[i]->key, data[i]->object, &stop);

		[self setObject: block(key, object, stop)
			if (new == nil)
				@throw [OFInvalidArgumentException
				    newWithClass: isa
					selector: _cmd];

			 forKey: key];
			[new retain];
			[data[i]->object release];
			data[i]->object = new;
		}
	}];
	}
}
#endif

- (void)makeImmutable
{
	isa = [OFDictionary class];
}
@end

/*
 * Copyright (c) 2008, 2009, 2010, 2011
 *   Jonathan Schleifer <js@webkeks.org>
 *
 * All rights reserved.
 *
 * This file is part of ObjFW. It may be distributed under the terms of the
 * Q Public License 1.0, which can be found in the file LICENSE.QPL included in
 * the packaging of this file.
 *
 * Alternatively, it may be distributed under the terms of the GNU General
 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#import "OFDictionary.h"

@interface OFMutableDictionary_hashtable: OFMutableDictionary
{
	struct of_dictionary_hashtable_bucket **data;
	uint32_t size;
	size_t count;
	unsigned long mutations;
}

#if defined(OF_SET_M) || defined(OF_COUNTED_SET_M)
- _initWithDictionary: (OFDictionary*)dictionary
	     copyKeys: (BOOL)copyKeys;
#endif

#if defined(OF_SET_M) || defined(OF_MUTABLE_SET_M) || defined(OF_COUNTED_SET_M)
- (void)_setObject: (id)object
	    forKey: (id)key
	   copyKey: (BOOL)copyKey;
#endif
@end

/*
 * Copyright (c) 2008, 2009, 2010, 2011
 *   Jonathan Schleifer <js@webkeks.org>
 *
 * All rights reserved.
 *
 * This file is part of ObjFW. It may be distributed under the terms of the
 * Q Public License 1.0, which can be found in the file LICENSE.QPL included in
 * the packaging of this file.
 *
 * Alternatively, it may be distributed under the terms of the GNU General
 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#include "config.h"

#include <string.h>

#import "OFMutableDictionary_hashtable.h"
#import "OFDictionary_hashtable.h"
#import "OFAutoreleasePool.h"

#import "OFEnumerationMutationException.h"
#import "OFInvalidArgumentException.h"
#import "OFOutOfRangeException.h"

#import "macros.h"

#define DELETED &of_dictionary_hashtable_deleted_bucket

static Class dictionary = Nil;

@implementation OFMutableDictionary_hashtable
+ (void)initialize
{
	if (self == [OFMutableDictionary_hashtable class]) {
		dictionary = [OFDictionary_hashtable class];
		[self inheritMethodsFromClass: dictionary];
	}
}

- (void)_resizeForCount: (size_t)newCount
{
	size_t fullness = newCount * 4 / size;
	struct of_dictionary_hashtable_bucket **newData;
	uint32_t i, newSize;

	if (newCount > UINT32_MAX)
		@throw [OFOutOfRangeException newWithClass: isa];

	if (fullness >= 3)
		newSize = size << 1;
	else if (fullness <= 1)
		newSize = size >> 1;
	else
		return;

	if (newSize == 0)
		@throw [OFOutOfRangeException newWithClass: isa];

	newData = [self allocMemoryForNItems: newSize
				    withSize: sizeof(*newData)];

	for (i = 0; i < newSize; i++)
		newData[i] = NULL;

	for (i = 0; i < size; i++) {
		if (data[i] != NULL && data[i] != DELETED) {
			uint32_t j, last;

			last = newSize;

			j = data[i]->hash & (newSize - 1);
			for (; j < last && newData[j] != NULL; j++);

			/* In case the last bucket is already used */
			if (j >= last) {
				last = data[i]->hash & (newSize - 1);

				for (j = 0; j < last &&
				    newData[j] != NULL; j++);
			}

			if (j >= last) {
				[self freeMemory: newData];
				@throw [OFOutOfRangeException
				    newWithClass: isa];
			}

			newData[j] = data[i];
		}
	}

	[self freeMemory: data];
	data = newData;
	size = newSize;
}

- (void)_setObject: (id)object
	    forKey: (id)key
	   copyKey: (BOOL)copyKey
{
	uint32_t i, hash, last;
	id old;

	if (key == nil || object == nil)
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];

	hash = [key hash];
	last = size;

	for (i = hash & (size - 1); i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key])
			break;
	}

	/* In case the last bucket is already used */
	if (i >= last) {
		last = hash & (size - 1);

		for (i = 0; i < last && data[i] != NULL; i++) {
			if (data[i] == DELETED)
				continue;

			if ([data[i]->key isEqual: key])
				break;
		}
	}

	/* Key not in dictionary */
	if (i >= last || data[i] == NULL || data[i] == DELETED ||
	    ![data[i]->key isEqual: key]) {
		struct of_dictionary_hashtable_bucket *bucket;

		[self _resizeForCount: count + 1];

		mutations++;
		last = size;

		for (i = hash & (size - 1); i < last && data[i] != NULL &&
		    data[i] != DELETED; i++);

		/* In case the last bucket is already used */
		if (i >= last) {
			last = hash & (size - 1);

			for (i = 0; i < last && data[i] != NULL &&
			    data[i] != DELETED; i++);
		}

		if (i >= last)
			@throw [OFOutOfRangeException newWithClass: isa];

		bucket = [self allocMemoryWithSize: sizeof(*bucket)];

		@try {
			key = (copyKey ? [key copy] : [key retain]);
		} @catch (id e) {
			[self freeMemory: bucket];
			@throw e;
		}

		@try {
			[object retain];
		} @catch (id e) {
			[self freeMemory: bucket];
			[key release];
			@throw e;
		}

		bucket->key = key;
		bucket->object = object;
		bucket->hash = hash;
		data[i] = bucket;
		count++;

		return;
	}

	old = data[i]->object;
	data[i]->object = [object retain];
	[old release];
}

- (void)setObject: (id)object
	   forKey: (id <OFCopying>)key
{
	[self _setObject: object
		  forKey: key
		 copyKey: YES];
}

- (void)removeObjectForKey: (id <OFCopying>)key
{
	uint32_t i, hash, last;

	if (key == nil)
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];

	hash = [key hash];
	last = size;

	for (i = hash & (size - 1); i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key]) {
			[data[i]->key release];
			[data[i]->object release];
			[self freeMemory: data[i]];
			data[i] = DELETED;

			count--;
			mutations++;
			[self _resizeForCount: count];

			return;
		}
	}

	if (i < last)
		return;

	/* In case the last bucket is already used */
	last = hash & (size - 1);

	for (i = 0; i < last && data[i] != NULL; i++) {
		if (data[i] == DELETED)
			continue;

		if ([data[i]->key isEqual: key]) {
			[data[i]->key release];
			[data[i]->object release];
			[self freeMemory: data[i]];
			data[i] = DELETED;

			count--;
			mutations++;
			[self _resizeForCount: count];

			return;
		}
	}
}

- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state
			   objects: (id*)objects
			     count: (int)count_
{
	const SEL selector =
	    @selector(countByEnumeratingWithState:objects:count:);
	int (*imp)(id, SEL, of_fast_enumeration_state_t*, id*, int) =
	    (int(*)(id, SEL, of_fast_enumeration_state_t*, id*, int))
	    [dictionary instanceMethodForSelector: selector];

	int ret = imp(self, selector, state, objects, count_);

	state->mutationsPtr = &mutations;

	return ret;
}

- (OFEnumerator*)objectEnumerator
{
	return [[[OFDictionaryObjectEnumerator_hashtable alloc]
	    initWithDictionary: (OFDictionary_hashtable*)self
			  data: data
			  size: size
	      mutationsPointer: &mutations] autorelease];
}

- (OFEnumerator*)keyEnumerator
{
	return [[[OFDictionaryKeyEnumerator_hashtable alloc]
	    initWithDictionary: (OFDictionary_hashtable*)self
			  data: data
			  size: size
	      mutationsPointer: &mutations] autorelease];
}

#ifdef OF_HAVE_BLOCKS
- (void)enumerateKeysAndObjectsUsingBlock:
    (of_dictionary_enumeration_block_t)block
{
	size_t i;
	BOOL stop = NO;
	unsigned long mutations2 = mutations;

	for (i = 0; i < size && !stop; i++) {
		if (mutations != mutations2)
			@throw [OFEnumerationMutationException
			    newWithClass: isa
				  object: self];

		if (data[i] != NULL && data[i] != DELETED)
			block(data[i]->key, data[i]->object, &stop);
	}
}

- (void)replaceObjectsUsingBlock: (of_dictionary_replace_block_t)block
{
	size_t i;
	BOOL stop = NO;
	unsigned long mutations2 = mutations;

	for (i = 0; i < size && !stop; i++) {
		if (mutations != mutations2)
			@throw [OFEnumerationMutationException
			    newWithClass: isa
				  object: self];

		if (data[i] != NULL && data[i] != DELETED) {
			id new = block(data[i]->key, data[i]->object, &stop);

			if (new == nil)
				@throw [OFInvalidArgumentException
				    newWithClass: isa
					selector: _cmd];

			[new retain];
			[data[i]->object release];
			data[i]->object = new;
		}
	}
}
#endif

- (void)makeImmutable
{
	isa = [OFDictionary_hashtable class];
}
@end

 */

#include "config.h"

#define OF_MUTABLE_SET_M

#import "OFMutableSet.h"
#import "OFDictionary.h"
#import "OFMutableDictionary_hashtable.h"
#import "OFArray.h"
#import "OFNumber.h"
#import "OFAutoreleasePool.h"

@implementation OFMutableSet
- (void)addObject: (id)object
{

 */

#include <stdarg.h>

#import "OFObject.h"
#import "OFCollection.h"

@class OFMutableDictionary;
@class OFMutableDictionary_hashtable;
@class OFArray;

#ifdef OF_HAVE_BLOCKS
typedef void (^of_set_enumeration_block_t)(id object, BOOL *stop);
typedef BOOL (^of_set_filter_block_t)(id object);
#endif

/**
 * \brief An unordered set of unique objects.
 */
@interface OFSet: OFObject <OFCollection, OFCopying, OFMutableCopying>
{
	OFMutableDictionary *dictionary;
	OFMutableDictionary_hashtable *dictionary;
}

/**
 * \brief Returns a new, autoreleased set.
 *
 * \return A new, autoreleased set
 */

 */

#include "config.h"

#define OF_SET_M

#import "OFSet.h"
#import "OFDictionary.h"
#import "OFMutableDictionary_hashtable.h"
#import "OFArray.h"
#import "OFString.h"
#import "OFNumber.h"
#import "OFAutoreleasePool.h"

@implementation OFSet
+ set

}

- init
{
	self = [super init];

	@try {
		dictionary = [[OFMutableDictionary alloc] init];
		dictionary = [[OFMutableDictionary_hashtable alloc] init];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

<?xml version='1.0' encoding='UTF-8'?>
<serialization xmlns='https://webkeks.org/objfw/serialization' version='0'>
  <OFMutableDictionary>
    <key>
      <OFArray>
        <OFString>Qu&quot;xbar
test</OFString>
        <OFNumber type='signed'>1234</OFNumber>
        <OFMutableString>asd</OFMutableString>
        <OFDate seconds='1234' microseconds='5678'/>
      </OFArray>
    </key>
    <object>
      <OFString>Hello</OFString>
    </object>
    <key>
      <OFList>
        <OFString>Hello</OFString>
        <OFString>Wo&#xD;ld!
How are you?</OFString>
        <OFURL>https://webkeks.org/</OFURL>
        <OFXMLElement name='x'>
          <namespaces>

          </children>
        </OFXMLElement>
      </OFList>
    </key>
    <object>
      <OFString>list</OFString>
    </object>
    <key>
      <OFArray>
        <OFString>Qu&quot;xbar
test</OFString>
        <OFNumber type='signed'>1234</OFNumber>
        <OFMutableString>asd</OFMutableString>
        <OFDate seconds='1234' microseconds='5678'/>
      </OFArray>
    </key>
    <object>
      <OFString>Hello</OFString>
    </object>
    <key>
      <OFString>Blub</OFString>
    </key>
    <object>
      <OFString>B&quot;la</OFString>
    </object>
    <key>