ObjFW  Check-in [da0d602dc8]

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

@class OFArray;

#ifdef OF_HAVE_BLOCKS
typedef void (^of_dictionary_enumeration_block_t)(id key, id obj, BOOL *stop);
typedef BOOL (^of_dictionary_filter_block_t)(id key, id obj);
typedef id (^of_dictionary_map_block_t)(id key, id obj);
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;

 * \return A new autoreleased OFDictionary
 */
+ dictionary;

/**
 * Creates a new OFDictionary with the specified dictionary.
 *
 * \param dict An OFDictionary
 * \param dictionary An OFDictionary
 * \return A new autoreleased OFDictionary
 */
+ dictionaryWithDictionary: (OFDictionary*)dict;
+ dictionaryWithDictionary: (OFDictionary*)dictionary;

/**
 * Creates a new OFDictionary with the specified key and object.
 *
 * \param key The key
 * \param obj The object
 * \param object The object
 * \return A new autoreleased OFDictionary
 */
+ dictionaryWithObject: (id)obj
+ dictionaryWithObject: (id)object
		forKey: (id <OFCopying>)key;

/**
 * Creates a new OFDictionary with the specified keys and objects.
 *
 * \param keys An array of keys
 * \param objs An array of objects
 * \param objects An array of objects
 * \return A new autoreleased OFDictionary
 */
+ dictionaryWithObjects: (OFArray*)objs
+ dictionaryWithObjects: (OFArray*)objects
		forKeys: (OFArray*)keys;

/**
 * Creates a new OFDictionary with the specified keys objects.
 *
 * \param key The first key
 * \param firstKey The first key
 * \return A new autoreleased OFDictionary
 */
+ dictionaryWithKeysAndObjects: (id <OFCopying>)key, ...;
+ dictionaryWithKeysAndObjects: (id <OFCopying>)firstKey, ...;

/**
 * Initializes an already allocated OFDictionary.
 *
 * \return An initialized OFDictionary
 */
- init;

/**
 * Initializes an already allocated OFDictionary with the specified
 * OFDictionary.
 *
 * \param dict An OFDictionary
 * \param dictionary An OFDictionary
 * \return An initialized OFDictionary
 */
- initWithDictionary: (OFDictionary*)dict;
- initWithDictionary: (OFDictionary*)dictionary;

/**
 * Initializes an already allocated OFDictionary with the specified key and
 * object.
 *
 * \param key The key
 * \param obj The object
 * \param object The object
 * \return A new initialized OFDictionary
 */
- initWithObject: (id)obj
- initWithObject: (id)object
	  forKey: (id <OFCopying>)key;

/**
 * Initializes an already allocated OFDictionary with the specified keys and
 * objects.
 *
 * \param keys An array of keys
 * \param objs An array of objects
 * \param objects An array of objects
 * \return A new initialized OFDictionary
 */
- initWithObjects: (OFArray*)objs
- initWithObjects: (OFArray*)objects
	  forKeys: (OFArray*)keys;

/**
 * Initializes an already allocated OFDictionary with the specified keys and
 * objects.
 *
 * \param first The first key
 * \param firstKey The first key
 * \return A new initialized OFDictionary
 */
- initWithKeysAndObjects: (id <OFCopying>)first, ...;
- initWithKeysAndObjects: (id <OFCopying>)firstKey, ...;

/**
 * Initializes an already allocated OFDictionary with the specified key and
 * va_list.
 *
 * \param first The first key
 * \param args A va_list of the other arguments
 * \param firstKey The first key
 * \param arguments A va_list of the other arguments
 * \return A new initialized OFDictionary
 */
- initWithKey: (id <OFCopying>)first
      argList: (va_list)args;
-  initWithKey: (id <OFCopying>)firstKey
  argumentList: (va_list)arguments;

/**
 * Returns the object for the given key or nil if the key was not found.
 *
 * The returned object is <i>not</i> retained and autoreleased for performance
 * reasons!
 *

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

#import "macros.h"

struct of_dictionary_bucket of_dictionary_deleted_bucket = {};

#define BUCKET struct of_dictionary_bucket
#define DELETED &of_dictionary_deleted_bucket

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

+ dictionaryWithDictionary: (OFDictionary*)dict
+ dictionaryWithDictionary: (OFDictionary*)dictionary
{
	return [[[self alloc] initWithDictionary: dict] autorelease];
	return [[[self alloc] initWithDictionary: dictionary] autorelease];
}

+ dictionaryWithObject: (id)obj
+ dictionaryWithObject: (id)object
		forKey: (id <OFCopying>)key
{
	return [[[self alloc] initWithObject: obj
	return [[[self alloc] initWithObject: object
				      forKey: key] autorelease];
}

+ dictionaryWithObjects: (OFArray*)objs
+ dictionaryWithObjects: (OFArray*)objects
		forKeys: (OFArray*)keys
{
	return [[[self alloc] initWithObjects: objs
	return [[[self alloc] initWithObjects: objects
				      forKeys: keys] autorelease];
}

+ dictionaryWithKeysAndObjects: (id <OFCopying>)first, ...
+ dictionaryWithKeysAndObjects: (id <OFCopying>)firstKey, ...
{
	id ret;
	va_list args;
	va_list arguments;

	va_start(args, first);
	ret = [[[self alloc] initWithKey: first
				 argList: args] autorelease];
	va_end(args);
	va_start(arguments, firstKey);
	ret = [[[self alloc] initWithKey: firstKey
			    argumentList: arguments] autorelease];
	va_end(arguments);

	return ret;
}

- init
{
	self = [super init];

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

	return self;
}

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

	@try {
		uint32_t i;

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

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

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

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

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

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

			b = [self allocMemoryWithSize: sizeof(BUCKET)];
			key = [dict->data[i]->key copy];
			bucket = [self allocMemoryWithSize: sizeof(*bucket)];
			key = [dictionary->data[i]->key copy];

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

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

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

	return self;
}

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

	@try {
		uint32_t i;
		BUCKET *b;
		struct of_dictionary_bucket *bucket;

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

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

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

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

		b->key = key;
		b->object = obj;
		b->hash = [(id)key hash];
		bucket->key = key;
		bucket->object = object;
		bucket->hash = [key hash];

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

	return self;
}

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

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

		keys_carray = [keys cArray];
		objs_carray = [objs cArray];
		keysCArray = [keys cArray];
		objectsCArray = [objects cArray];
		count = [keys count];

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

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

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

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

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

		size = nsize;
		size = newSize;

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

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

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

			/* Key not in dictionary */
			if (j >= last || data[j] == NULL ||
			    ![(id)data[j]->key isEqual: keys_carray[i]]) {
				BUCKET *b;
			    ![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 =
				b = [self allocMemoryWithSize: sizeof(BUCKET)];
				key = [keys_carray[i] copy];
				    [self allocMemoryWithSize: sizeof(*bucket)];
				key = [keysCArray[i] copy];

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

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

				data[j] = b;
				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.
			 */
			[objs_carray[i] retain];
			[objectsCArray[i] retain];

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

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

	return self;
}

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

	va_start(args, first);
	ret = [self initWithKey: first
			argList: args];
	va_end(args);
	va_start(arguments, firstKey);
	ret = [self initWithKey: firstKey
		   argumentList: arguments];
	va_end(arguments);

	return ret;
}

- initWithKey: (id <OFCopying>)key
      argList: (va_list)args
-  initWithKey: (id <OFCopying>)key
  argumentList: (va_list)arguments
{
	self = [super init];

	@try {
		id obj;
		uint32_t i, j, hash, nsize;
		va_list args2;
		BUCKET *b;
		id object;
		uint32_t i, j, hash, newSize;
		va_list argumentsCopy;
		struct of_dictionary_bucket *bucket;

		va_copy(args2, args);
		va_copy(argumentsCopy, arguments);

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

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

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

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

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

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

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

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

		size = nsize;
		size = newSize;

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

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

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

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

		data[j] = b;
		data[j] = bucket;

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

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

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

			hash = [(id)key hash];
			hash = [key hash];
			last = size;

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

			/* Key not in dictionary */
			if (j >= last || data[j] == NULL ||
			    ![(id)data[j]->key isEqual: key]) {
			    ![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 =
				b = [self allocMemoryWithSize: sizeof(BUCKET)];
				    [self allocMemoryWithSize: sizeof(*bucket)];
				key = [key copy];

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

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

				data[j] = b;
				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.
			 */
			[obj retain];
			[object retain];

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

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

	return self;

	hash = [key hash];
	last = size;

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

		if ([(id)data[i]->key isEqual: key])
		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 ([(id)data[i]->key isEqual: key])
		if ([data[i]->key isEqual: key])
			return data[i]->object;
	}

	return nil;
}

- (size_t)count

	}

	[pool release];
}

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

	for (i = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED)
			[dict setObject: block(data[i]->key, data[i]->object)
				 forKey: data[i]->key];
			[new setObject: block(data[i]->key, data[i]->object)
				forKey: data[i]->key];

	/*
	 * Class swizzle the dictionary to be immutable. We declared the return
	 * type to be OFDictionary*, so it can't be modified anyway. But not
	 * swizzling it would create a real copy each time -[copy] is called.
	 */
	dict->isa = [OFDictionary class];
	return dict;
	new->isa = [OFDictionary class];
	return new;
}

- (OFDictionary*)filteredDictionaryUsingBlock:
    (of_dictionary_filter_block_t)block
{
	OFMutableDictionary *dict = [OFMutableDictionary dictionary];
	OFMutableDictionary *new = [OFMutableDictionary dictionary];
	size_t i;

	for (i = 0; i < size; i++)
		if (data[i] != NULL && data[i] != DELETED)
			if (block(data[i]->key, data[i]->object))
				[dict setObject: data[i]->object
					 forKey: data[i]->key];
				[new setObject: data[i]->object
					forKey: data[i]->key];

	/*
	 * Class swizzle the dictionary to be immutable. We declared the return
	 * type to be OFDictionary*, so it can't be modified anyway. But not
	 * swizzling it would create a real copy each time -[copy] is called.
	 */
	dict->isa = [OFDictionary class];
	return dict;
	new->isa = [OFDictionary class];
	return new;
}
#endif

- (void)dealloc
{
	uint32_t i;

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

	[super dealloc];
}

 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#import "OFDictionary.h"

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

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

/**
 * Sets an object for a key.
 * A key can be any object.
 *
 * \param key The key to set
 * \param obj The object to set the key to
 * \param object The object to set the key to
 */
- (void)setObject: (id)obj
- (void)setObject: (id)object
	   forKey: (id <OFCopying>)key;

/**
 * Remove the object with the given key from the dictionary.
 *
 * \param key The key whose object should be removed
 */

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

#import "macros.h"

#define BUCKET struct of_dictionary_bucket
#define DELETED &of_dictionary_deleted_bucket

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

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

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

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

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

	for (i = 0; i < newsize; i++)
		newdata[i] = NULL;
	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;
			last = newSize;

			j = data[i]->hash & (newsize - 1);
			for (; j < last && newdata[j] != NULL; j++);
			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);
				last = data[i]->hash & (newSize - 1);

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

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

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

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

- (void)setObject: (id)obj
- (void)setObject: (id)object
	   forKey: (id <OFCopying>)key
{
	uint32_t i, hash, last;
	id old;

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

	hash = [(id)key hash];
	hash = [key hash];
	last = size;

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

		if ([(id)data[i]->key isEqual: key])
		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 ([(id)data[i]->key isEqual: key])
			if ([data[i]->key isEqual: key])
				break;
		}
	}

	/* Key not in dictionary */
	if (i >= last || data[i] == NULL || data[i] == DELETED ||
	    ![(id)data[i]->key isEqual: key]) {
		BUCKET *b;
	    ![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];

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

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

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

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

		return;
	}

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

- (void)removeObjectForKey: (id)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 ([(id)data[i]->key isEqual: key]) {
			[(id)data[i]->key release];
		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];

	/* 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 ([(id)data[i]->key isEqual: key]) {
			[(id)data[i]->key release];
		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];