ObjFW  Check-in [1abbb97747]

	if (key == nil || object == nil)
		@throw [OFInvalidArgumentException
		    exceptionWithClass: [self class]];

	return [self initWithKeysAndObjects: key, object, nil];
}

- initWithObjects: (OFArray*)objects
	  forKeys: (OFArray*)keys
- initWithObjects: (OFArray*)objects_
	  forKeys: (OFArray*)keys_
{
	id *objects, *keys;
	size_t count;

	@try {
		count = [objects_ count];

		if (count != [keys_ count])
			@throw [OFInvalidArgumentException
	Class c = [self class];
	[self release];
	@throw [OFNotImplementedException exceptionWithClass: c
						    selector: _cmd];
			    exceptionWithClass: [self class]];

		objects = [objects_ objects];
		keys = [keys_ objects];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return [self initWithObjects: objects
			     forKeys: keys
			       count: count];
}

- initWithObjects: (id const*)objects
	  forKeys: (id const*)keys
	    count: (size_t)count
{
	Class c = [self class];

 * 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
@class OFMapTable;
{
	id key, object;
	uint32_t hash;
@class OFMapTableEnumerator;
};

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

	OFMapTable *mapTable;
#if defined(OF_SET_M) || defined(OF_COUNTED_SET_M) || \
    defined(OF_SET_HASHTABLE_M) || defined(OF_COUNTED_SET_HASHTABLE_M)
- OF_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

 * 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 "OFMapTable.h"
#import "OFArray.h"
#import "OFString.h"
#import "OFXMLElement.h"

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

#import "autorelease.h"
#import "macros.h"


static void*
copy(void *value)
{
struct of_dictionary_hashtable_bucket
    of_dictionary_hashtable_deleted_bucket = {};
	return [(id)value copy];
#define DELETED &of_dictionary_hashtable_deleted_bucket

@implementation OFDictionary_hashtable
- init
}

static void*
retain(void *value)
{
	self = [super init];

	@try {
	return [(id)value retain];
}

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

static uint32_t
hash(void *value)
{
	return self;
	return [(id)value hash];
}

- OF_initWithDictionary: (OFDictionary*)dictionary
	       copyKeys: (BOOL)copyKeys
static BOOL
equal(void *value1, void *value2)
{
	self = [super init];

	return [(id)value1 isEqual: (id)value2];
	@try {
		uint32_t i;
		OFDictionary_hashtable *hashtable;

}
		if (![dictionary isKindOfClass:
		    [OFDictionary_hashtable class]] &&
		    ![dictionary isKindOfClass:
		    [OFMutableDictionary_hashtable class]])
			@throw [OFInvalidArgumentException
			    exceptionWithClass: [self class]
				      selector: _cmd];

		hashtable = (OFDictionary_hashtable*)dictionary;

		data = [self allocMemoryWithSize: sizeof(*data)
					   count: hashtable->size];

static of_map_table_functions_t keyFunctions = {
	.retain = copy,
	.release = release,
	.hash = hash,
	.equal = equal
		for (i = 0; i < hashtable->size; i++)
			data[i] = NULL;

		size = hashtable->size;
		count = hashtable->count;
};
static of_map_table_functions_t valueFunctions = {
	.retain = retain,
	.release = release,
	.hash = hash,
	.equal = equal
};

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

@implementation OFDictionary_hashtable
- init
{
			if (hashtable->data[i] == NULL ||
			    hashtable->data[i] == DELETED)
				continue;

			bucket = [self allocMemoryWithSize: sizeof(*bucket)];
	return [self initWithCapacity: 0];
}

			bucket->key = (copyKeys
			    ? [hashtable->data[i]->key copy]
			    : [hashtable->data[i]->key retain]);
			bucket->object = [hashtable->data[i]->object retain];
			bucket->hash = hashtable->data[i]->hash;

			data[i] = bucket;
		}
- initWithCapacity: (size_t)capacity
{
	self = [super init];

	@try {
		mapTable = [[OFMapTable alloc]
		    initWithKeyFunctions: keyFunctions
			  valueFunctions: valueFunctions
				capacity: capacity];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithDictionary: (OFDictionary*)dictionary
{
	size_t count;

	if (dictionary == nil)
		return [self init];

	if ([dictionary class] == [OFDictionary_hashtable class] ||
	    [dictionary class] == [OFMutableDictionary_hashtable class])
	    [dictionary class] == [OFMutableDictionary_hashtable class]) {
		return [self OF_initWithDictionary: dictionary
					  copyKeys: YES];

	self = [super init];
		self = [super init];

	@try {
		void *pool;
		@try {
			OFDictionary_hashtable *dictionary_ =
			    (OFDictionary_hashtable*)dictionary;

		OFEnumerator *enumerator;
		id key;
		uint32_t i, newSize;

		if (dictionary == nil)
			mapTable = [dictionary_->mapTable copy];
		} @catch (id e) {
			[self release];
			@throw e;
		}

			@throw [OFInvalidArgumentException
			    exceptionWithClass: [self class]];

		return self;
	}

	@try {
		count = [dictionary count];

	} @catch (id e) {
		if (count > UINT32_MAX)
			@throw [OFOutOfRangeException
			    exceptionWithClass: [self class]];

		[self release];
		for (newSize = 1; newSize < count; newSize <<= 1);
		if (count * 4 / newSize >= 3)
			newSize <<= 1;

		if (newSize == 0)
			@throw [OFOutOfRangeException
		@throw e;
			    exceptionWithClass: [self class]];

	}
		data = [self allocMemoryWithSize: sizeof(*data)
					   count: newSize];

		for (i = 0; i < newSize; i++)
			data[i] = NULL;
	self = [self initWithCapacity: count];

		size = newSize;

		pool = objc_autoreleasePoolPush();

	@try {
		void *pool = objc_autoreleasePoolPush();
		OFEnumerator *keyEnumerator, *objectEnumerator;
		enumerator = [dictionary keyEnumerator];
		while ((key = [enumerator nextObject]) != nil) {
			uint32_t hash, last;
			struct of_dictionary_hashtable_bucket *bucket;
			id object;
		id key, object;

			hash = [key hash];
			last = size;

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

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

		while ((key = [keyEnumerator nextObject]) != nil &&
				for (i = 0; i < last && data[i] != NULL; i++);
			}

		    (object = [objectEnumerator nextObject]) != nil)
			if (data[i] != NULL)
				@throw [OFOutOfRangeException
				    exceptionWithClass: [self class]];

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

			object = [dictionary objectForKey: key];
				    forKey: key];

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

			data[i] = bucket;
		}

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

	return self;
}

- initWithObject: (id)object
	  forKey: (id)key
{
	self = [super init];
	self = [self initWithCapacity: 1];

	@try {
		uint32_t i;
		struct of_dictionary_hashtable_bucket *bucket;

		[mapTable setValue: object
		if (key == nil || object == nil)
			@throw [OFInvalidArgumentException
			    exceptionWithClass: [self class]
				      selector: _cmd];

			    forKey: key];
		data = [self allocMemoryWithSize: sizeof(*data)
					   count: 2];

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

		i = [key hash] & 1;

		bucket = [self allocMemoryWithSize: sizeof(*bucket)];
		bucket->key = [key copy];
		bucket->object = [object retain];
		bucket->hash = [key hash];

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

	return self;
}

- initWithObjects: (OFArray*)objects
	  forKeys: (OFArray*)keys
{
	id ret;

	@try {
		if ([objects count] != [keys count])
			@throw [OFInvalidArgumentException
			    exceptionWithClass: [self class]];

		ret = [self initWithObjects: [objects objects]
				    forKeys: [keys objects]
				      count: [objects count]];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return ret;
}

- initWithObjects: (id const*)objects
	  forKeys: (id const*)keys
	    count: (size_t)count_
	    count: (size_t)count
{
	self = [super init];
	self = [self initWithCapacity: count];

	@try {
		uint32_t i, j, newSize;

		size_t i;
		count = count_;

		if (count > UINT32_MAX)
			@throw [OFOutOfRangeException
			    exceptionWithClass: [self class]];

		for (newSize = 1; newSize < count; newSize <<= 1);
		if (count * 4 / newSize >= 3)
			newSize <<= 1;

		if (newSize == 0)
			@throw [OFOutOfRangeException
			    exceptionWithClass: [self class]];

		data = [self allocMemoryWithSize: sizeof(*data)
					   count: newSize];

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

		size = newSize;

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

			[mapTable setValue: objects[i]
			if (keys[i] == nil || objects[i] == nil)
				@throw [OFInvalidArgumentException
				    exceptionWithClass: [self class]];

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

			for (j = hash & (size - 1); j < last && data[j] != NULL;
			    j++)
				if ([data[j]->key isEqual: keys[i]])
				    forKey: keys[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: keys[i]])
						break;
			}

			/* Key not in dictionary */
			if (j >= last || data[j] == NULL ||
			    ![data[j]->key isEqual: keys[i]]) {
				struct of_dictionary_hashtable_bucket *bucket;
				id 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
					    exceptionWithClass: [self class]];

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

				bucket->key = key;
				bucket->object = [objects[i] retain];
				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.
			 */
			[objects[i] retain];
			[data[j]->object release];
			data[j]->object = objects[i];
		}
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

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

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

		va_copy(argumentsCopy, arguments);

		if (firstKey == nil)
			@throw [OFInvalidArgumentException
			    exceptionWithClass: [self class]
				      selector: _cmd];

		key = firstKey;

		if ((object = va_arg(arguments, id)) == nil)
			@throw [OFInvalidArgumentException
			    exceptionWithClass: [self class]
				      selector: _cmd];

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

		if (count > UINT32_MAX)
			@throw [OFOutOfRangeException
			    exceptionWithClass: [self class]];

		mapTable = [[OFMapTable alloc]
		for (newSize = 1; newSize < count; newSize <<= 1);
		if (count * 4 / newSize >= 3)
			newSize <<= 1;

		    initWithKeyFunctions: keyFunctions
		if (newSize == 0)
			@throw [OFOutOfRangeException
			    exceptionWithClass: [self class]];

			  valueFunctions: valueFunctions
		data = [self allocMemoryWithSize: sizeof(*data)
					   count: newSize];

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

		size = newSize;

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

			    forKey: key];
		bucket = [self allocMemoryWithSize: sizeof(*bucket)];
		bucket->key = [key copy];
		bucket->object = [object retain];
		bucket->hash = hash;

		data[j] = bucket;

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

			key = va_arg(arguments, id);
			object = va_arg(arguments, id);

			if (key == nil || object == nil)
				@throw [OFInvalidArgumentException
				    exceptionWithClass: [self class]
					      selector: _cmd];

			hash = [key hash];
			last = size;

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

				    forKey: key];
			/* 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
					    exceptionWithClass: [self class]];

				bucket =
				    [self allocMemoryWithSize: sizeof(*bucket)];
				bucket->key = [key copy];
				bucket->object = [object retain];
				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];
			[data[j]->object release];
			data[j]->object = object;
			count--;
		}
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithSerialization: (OFXMLElement*)element
{
	self = [super init];

	@try {
		void *pool = objc_autoreleasePoolPush();
		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
			    exceptionWithClass: [self class]
				      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
			    exceptionWithClass: [self class]];

		mapTable = [[OFMapTable alloc]
		    initWithKeyFunctions: keyFunctions
			  valueFunctions: valueFunctions
				capacity: [keys count]];

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

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

			if (key == nil || object == nil)
				@throw [OFInvalidFormatException
				    exceptionWithClass: [self class]];

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

			objc_autoreleasePoolPop(pool2);
		}

		self = [self initWithDictionary: dictionary];

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

	return self;
}

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

	if (key == nil)
		@throw [OFInvalidArgumentException
		    exceptionWithClass: [self class]
			      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;

	return [mapTable valueForKey: key];
}
	/* 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;
	return [mapTable count];
}

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

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

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

	dictionary_ = (OFDictionary_hashtable*)dictionary;
	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;
	return [dictionary_->mapTable isEqual: mapTable];
}

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

	if (object == nil || count == 0)
		return NO;
	return [mapTable containsValue: object];

	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;

	return [mapTable containsValueIdenticalTo: object];
	if (object == nil || 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 *keys;
	size_t count;

	count = [mapTable count];
	id *keys = [self allocMemoryWithSize: sizeof(*keys)
				       count: count];
	size_t i, j;
	keys = [self allocMemoryWithSize: sizeof(*keys)
				   count: count];

	@try {
		void *pool = objc_autoreleasePoolPush();
		OFMapTableEnumerator *enumerator;
		id key;
		size_t i;

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

	assert(j == count);
		i = 0;
		enumerator = [mapTable keyEnumerator];
		while ((key = [enumerator nextValue]) != nil) {
			assert(i < count);

			keys[i++] = key;
		}

		objc_autoreleasePoolPop(pool);

	@try {
		ret = [OFArray arrayWithObjects: keys
					  count: count];
	} @finally {
		[self freeMemory: keys];
	}

	return ret;
}

- (OFArray*)allObjects
{
	OFArray *ret;
	id *objects;
	size_t count;

	count = [mapTable count];
	id *objects = [self allocMemoryWithSize: sizeof(*objects)
					  count: count];
	size_t i, j;
	objects = [self allocMemoryWithSize: sizeof(*objects)
				      count: count];

	@try {
		void *pool = objc_autoreleasePoolPush();
		OFMapTableEnumerator *enumerator;
		id object;
		size_t i;

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

	assert(j == count);
		i = 0;
		enumerator = [mapTable valueEnumerator];
		while ((object = [enumerator nextValue]) != nil) {
			assert(i < count);

			objects[i++] = object;
		}

		objc_autoreleasePoolPop(pool);

	@try {
		ret = [OFArray arrayWithObjects: objects
					  count: count];
	} @finally {
		[self freeMemory: objects];
	}

	return ret;
}

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

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

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

	return [mapTable countByEnumeratingWithState: state
	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;
					     objects: objects
	state->mutationsPtr = (unsigned long*)self;

					       count: count_];
	return i;
}

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

	@try {
		[mapTable enumerateKeysAndValuesUsingBlock:
		    ^ (void *key, void *value, BOOL *stop) {
			block(key, value, stop);
		}];
	} @catch (OFEnumerationMutationException *e) {
		@throw [OFEnumerationMutationException
		    exceptionWithClass: [self class]
				object: self];
	}
	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;

	[mapTable dealloc];
	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;
	return [mapTable 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
		    exceptionWithClass: [dictionary class]
				object: dictionary];

	pos = 0;
}
@end

@implementation OFDictionaryObjectEnumerator_hashtable
- (id)nextObject
{
	if (mutationsPtr != NULL && *mutationsPtr != mutations)
		@throw [OFEnumerationMutationException
		    exceptionWithClass: [dictionary class]
				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
		    exceptionWithClass: [dictionary class]
				object: dictionary];

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

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

#ifdef OF_HAVE_BLOCKS
- (void)enumerateObjectsUsingBlock: (of_array_enumeration_block_t)block
{
	id *objects = [array cArray];
	size_t i, count = [array count];
	BOOL stop = NO;
	unsigned long mutations2 = mutations;
	unsigned long mutations_ = mutations;

	for (i = 0; i < count && !stop; i++) {
		if (mutations != mutations2)
		if (mutations != mutations_)
			@throw [OFEnumerationMutationException
			    exceptionWithClass: [self class]
					object: self];

		block(objects[i], i, &stop);
	}
}

- (void)replaceObjectsUsingBlock: (of_array_replace_block_t)block
{
	id *objects = [array cArray];
	size_t i, count = [array count];
	BOOL stop = NO;
	unsigned long mutations2 = mutations;
	unsigned long mutations_ = mutations;

	for (i = 0; i < count && !stop; i++) {
		id newObject;

		if (mutations != mutations2)
		if (mutations != mutations_)
			@throw [OFEnumerationMutationException
			    exceptionWithClass: [self class]
					object: self];

		newObject = block(objects[i], i, &stop);

		if (newObject == nil)

 * 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"

@class OFMapTable;

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

#if defined(OF_SET_HASHTABLE_M) || defined(OF_MUTABLE_SET_HASHTABLE_M) || \
    defined(OF_COUNTED_SET_HASHTABLE_M)
- (void)OF_setObject: (id)object
	      forKey: (id)key
	     copyKey: (BOOL)copyKey;
#endif
@end

#include "config.h"

#include <string.h>

#import "OFMutableDictionary_hashtable.h"
#import "OFDictionary_hashtable.h"
#import "OFMapTable.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]) {
	if (self == [OFMutableDictionary_hashtable class])
		dictionary = [OFDictionary_hashtable class];
		[self inheritMethodsFromClass: dictionary];
		[self inheritMethodsFromClass: [OFDictionary_hashtable class]];
	}
}

- (void)OF_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 exceptionWithClass: [self class]];

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

	if (newSize == 0)
		@throw [OFOutOfRangeException exceptionWithClass: [self class]];

	newData = [self allocMemoryWithSize: sizeof(*newData)
				      count: newSize];

	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
				    exceptionWithClass: [self class]];
			}

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

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

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

	if (key == nil || object == nil)
		@throw [OFInvalidArgumentException
		    exceptionWithClass: [self class]
			      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 OF_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
			    exceptionWithClass: [self class]];

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

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

		bucket->object = [object retain];
		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)key
{
	[self OF_setObject: object
		    forKey: key
	[mapTable setValue: object
		    forKey: key];
		   copyKey: YES];
}

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

	[mapTable removeValueForKey: key];
	if (key == nil)
		@throw [OFInvalidArgumentException
		    exceptionWithClass: [self class]
			      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 OF_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 OF_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
			    exceptionWithClass: [self class]
					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;
	@try {
		[mapTable replaceValuesUsingBlock:
		    ^ void* (void *key, void *value, BOOL *stop) {
			return block(key, value, stop);
	unsigned long mutations2 = mutations;

		}];
	for (i = 0; i < size && !stop; i++) {
		if (mutations != mutations2)
			@throw [OFEnumerationMutationException
			    exceptionWithClass: [self class]
					object: self];
	} @catch (OFEnumerationMutationException *e) {
		@throw [OFEnumerationMutationException
		    exceptionWithClass: [self class]
				object: self];

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

			if (new == nil)
				@throw [OFInvalidArgumentException
				    exceptionWithClass: [self class]
					      selector: _cmd];

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

- (void)makeImmutable
{
	object_setClass(self, [OFDictionary_hashtable class]);
}
@end

		 forKey: keys[0]];

#ifdef OF_HAVE_FAST_ENUMERATION
	size_t i = 0;
	BOOL ok = YES;

	for (OFString *key in dict) {
		if (i > 1 || ![key isEqual: keys[1 - i]]) {
		if (i > 1 || ![key isEqual: keys[i]]) {
			ok = NO;
			break;
		}

		[dict setObject: [dict objectForKey: key]
			 forKey: key];
		i++;

#ifdef OF_HAVE_BLOCKS
	{
		__block size_t i = 0;
		__block BOOL ok = YES;

		[dict enumerateKeysAndObjectsUsingBlock:
		    ^ (id key, id obj, BOOL *stop) {
			if (i > 1 || ![key isEqual: keys[1 - i]]) {
			if (i > 1 || ![key isEqual: keys[i]]) {
				ok = NO;
				*stop = YES;
				return;
			}

			[dict setObject: [dict objectForKey: key]
				 forKey: key];

	    [[[dict mappedDictionaryUsingBlock: ^ id (id key, id obj) {
		if ([key isEqual: keys[0]])
			return @"val1";
		if ([key isEqual: keys[1]])
			return @"val2";

		return nil;
	    }] description] isEqual: @"{\n\tkey2 = val2;\n\tkey1 = val1;\n}"])
	    }] description] isEqual: @"{\n\tkey1 = val1;\n\tkey2 = val2;\n}"])

	TEST(@"-[filteredDictionaryUsingBlock:]",
	    [[[dict filteredDictionaryUsingBlock: ^ BOOL (id key, id obj) {
		return ([key isEqual: keys[0]] ?  YES : NO);
	    }] description] isEqual: @"{\n\tkey1 = value_1;\n}"])
#endif

		[OFNumber numberWithBool: NO],
		nil],
	    nil];

	TEST(@"-[JSONValue #1]", [[s JSONValue] isEqual: d])

	TEST(@"-[JSONRepresentation]", [[d JSONRepresentation] isEqual:
	    @"{\"foo\":\"ba\\r\",\"x\":[0.5,15,null,\"foo\",false]}"])
	    @"{\"x\":[0.5,15,null,\"foo\",false],\"foo\":\"ba\\r\"}"])

	EXPECT_EXCEPTION(@"-[JSONValue #2]", OFInvalidJSONException,
	    [@"{" JSONValue])
	EXPECT_EXCEPTION(@"-[JSONValue #3]", OFInvalidJSONException,
	    [@"]" JSONValue])
	EXPECT_EXCEPTION(@"-[JSONValue #4]", OFInvalidJSONException,
	    [@"bar" JSONValue])
	EXPECT_EXCEPTION(@"-[JSONValue #5]", OFInvalidJSONException,
	    [@"[\"a\" \"b\"]" JSONValue])

	[pool drain];
}
@end