ObjFW  Check-in [bbf1f79b8f]

 * Q Public License 1.0, which can be found in the file LICENSE included in
 * the packaging of this file.
 */

#include <stdarg.h>

#import "OFObject.h"
#import "OFList.h"
#import "OFArray.h"

typedef struct __of_dictionary_list_object
struct of_dictionary_bucket
{
	/* of_list_object_t */
	OFObject <OFCopying> *key;
	struct __of_dictionary_list_object *next;
	struct __of_dictionary_list_object *prev;
	id				   object;
	OFObject	     *object;
	/* OFDictionary additions */
	id				   key;
	uint32_t			   hash;
	uint32_t	     hash;
} of_dictionary_list_object_t;
};

/**
 * The OFDictionary class provides a class for using hash tables.
 */
@interface OFDictionary: OFObject <OFCopying, OFMutableCopying>
{
	OFList **data;
	size_t size;
	struct of_dictionary_bucket *data;
	size_t			    size;
	size_t			    count;
}

/**
 * Creates a new OFDictionary, defaulting to a 12 bit hash.
 * Creates a new OFDictionary.
 *
 * \return A new autoreleased OFDictionary
 */
+ dictionary;

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

/**
 * Creates a new OFDictionary with a hash of N bits.
 *
 * \param bits The size of the hash to use
 * \return A new autoreleased OFDictionary
 */
+ dictionaryWithHashSize: (int)hashsize;

/**
 * Creates a new OFDictionary with the specified key and object.
 *
 * \param key The key
 * \param obj The object
 * \return A new autoreleased OFDictionary
 */

 */
+ dictionaryWithObjects: (OFArray*)objs
		forKeys: (OFArray*)keys;

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

/**
 * Initializes an already allocated OFDictionary, defaulting to a 12 bit hash.
 * Initializes an already allocated OFDictionary.
 *
 * \return An initialized OFDictionary
 */
- init;

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

/**
 * Initializes an already allocated OFDictionary with a hash of N bits.
 *
 * \param bits The size of the hash to use
 * \return An initialized OFDictionary
 */
- initWithHashSize: (int)hashsize;

/**
 * Initializes an already allocated OFDictionary with the specified key and
 * object.
 *
 * \param key The key
 * \param obj The object
 * \return A new initialized OFDictionary

 *
 * \param first The first key
 * \return A new initialized OFDictionary
 */
- initWithKey: (OFObject <OFCopying>*)first
      argList: (va_list)args;

/**
 * \return The average number of items in a used bucket. Buckets that are
 *	   completely empty are not in the calculation. If this value is >= 2.0,
 *	   you should resize the dictionary, in most cases even earlier!
 */
- (float)averageItemsPerBucket;

/**
 * \param key The key whose object should be returned
 * \return The object for the given key or nil if the key was not found
 */
- (id)objectForKey: (OFObject*)key;
- (id)objectForKey: (OFObject <OFCopying>*)key;

/**
 * \return The number of objects in the dictionary
 */
- (size_t)count;

- setObject: (OFObject*)obj
     forKey: (OFObject <OFCopying>*)key;
- removeObjectForKey: (OFObject*)key;
- changeHashSize: (int)hashsize;
@end

#import "OFIterator.h"
#import "OFMutableDictionary.h"

#include <string.h>

#import "OFDictionary.h"
#import "OFIterator.h"
#import "OFAutoreleasePool.h"
#import "OFExceptions.h"

#define BUCKET_SIZE sizeof(struct of_dictionary_bucket)

/* References for static linking */
void _references_to_categories_of_OFDictionary()
{
	_OFIterator_reference = 1;
}

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

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

+ dictionaryWithHashSize: (int)hashsize
{
	return [[[self alloc] initWithHashSize: hashsize] autorelease];
}

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

	return ret;
}

- init
{
	self = [super init];

	size = 4096;
	size = 1;

	@try {
		data = [self allocMemoryForNItems: size
		data = [self allocMemoryWithSize: BUCKET_SIZE];
					 withSize: sizeof(OFList*)];
	} @catch (OFException *e) {
		/*
		 * We can't use [super dealloc] on OS X here. Compiler bug?
		 * Anyway, set size to 0 so that [self dealloc] works.
		 */
		size = 0;
		[self dealloc];
		@throw e;
	}
	memset(data, 0, size * sizeof(OFList*));
	data[0].key = nil;

	return self;
}

- initWithDictionary: (OFDictionary*)dict
{
	OFAutoreleasePool *pool;
	OFIterator *iter;
	of_iterator_pair_t pair;
	size_t i;
	of_iterator_pair_t (*next)(id, SEL);

	self = [super init];

	if (dict == nil) {
		Class c = isa;
		size = 0;
		[self dealloc];
		@throw [OFInvalidArgumentException newWithClass: c
						       selector: _cmd];
	}

	size = dict->size;

	@try {
		data = [self allocMemoryForNItems: size
					 withSize: sizeof(OFList*)];
		data = [self allocMemoryForNItems: dict->size
					 withSize: BUCKET_SIZE];
		memset(data, 0, size * sizeof(OFList*));

		pool = [[OFAutoreleasePool alloc] init];
		iter = [dict iterator];
		next = (of_iterator_pair_t(*)(id, SEL))
		    [iter methodForSelector: @selector(nextKeyObjectPair)];
	} @catch (OFException *e) {
		/*
		 * We can't use [super dealloc] on OS X here. Compiler bug?
		 * Anyway, set size to 0 so that [self dealloc] works.
		 * Anyway, we didn't do anything yet anyway, so [self dealloc]
		 * works.
		 */
		size = 0;
		[self dealloc];
		@throw e;
	}

	size = dict->size;
	for (;;) {
		uint32_t hash;
		OFObject <OFCopying> *key;

		pair = next(iter, @selector(nextKeyObjectPair));

		if (pair.key == nil || pair.object == nil)
			break;

		hash = pair.hash & (size - 1);

		@try {
			key = [pair.key copy];
		} @catch (OFException *e) {
			[self dealloc];
			@throw e;
		}

		@try {
			of_dictionary_list_object_t *o;

			if (data[hash] == nil)
				data[hash] = [[OFList alloc]
				    initWithListObjectSize:
				    sizeof(of_dictionary_list_object_t)];

			o = (of_dictionary_list_object_t*)
			    [data[hash] append: pair.object];
			o->key = key;
			o->hash = pair.hash;
		} @catch (OFException *e) {
			[key release];
			[self dealloc];
			@throw e;
		}
	}

	for (i = 0; i < size; i++) {
	[pool release];

		if (dict->data[i].key != nil) {
	return self;
}

			data[i].key = [dict->data[i].key copy];
- initWithHashSize: (int)hashsize
{
	self = [super init];

			data[i].object = [dict->data[i].object retain];
	if (hashsize < 8 || hashsize >= 28) {
		Class c = isa;
		[super dealloc];
		@throw [OFInvalidArgumentException newWithClass: c
						       selector: _cmd];
	}

			data[i].hash = dict->data[i].hash;
	size = (size_t)1 << hashsize;

		} else
	@try {
		data = [self allocMemoryForNItems: size
					 withSize: sizeof(OFList*)];
	} @catch (OFException *e) {
		/*
		 * We can't use [super dealloc] on OS X here. Compiler bug?
		 * Anyway, set size to 0 so that [self dealloc] works.
		 */
		size = 0;
			data[i].key = nil;
		[self dealloc];
		@throw e;
	}
	memset(data, 0, size * sizeof(OFList*));

	return self;
}

- initWithObject: (OFObject*)obj
	  forKey: (OFObject <OFCopying>*)key
{
	Class c;
	uint32_t fullhash, hash;
	const SEL sel = @selector(setObject:forKey:);
	IMP set = [OFMutableDictionary instanceMethodForSelector: sel];

	self = [self init];

	if (key == nil || obj == nil) {
		c = isa;
		[self dealloc];
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];
	}

	fullhash = [key hash];
	hash = fullhash & (size - 1);

	@try {
		key = [key copy];
	} @catch (OFException *e) {
		[self dealloc];
		@throw e;
	}

		set(self, sel, obj, key);
	@try {
		of_dictionary_list_object_t *o;

		data[hash] = [[OFList alloc] initWithListObjectSize:
		    sizeof(of_dictionary_list_object_t)];

		o = (of_dictionary_list_object_t*)[data[hash] append: obj];
		o->key = key;
		o->hash = fullhash;
	} @catch (OFException *e) {
		[key release];
		[self dealloc];
		@throw e;
	}

	return self;
}

- initWithObjects: (OFArray*)objs
	  forKeys: (OFArray*)keys
{
	Class c;
	OFObject <OFCopying> **keys_data;
	OFObject **objs_data;
	size_t count, i;
	id *objs_data, *keys_data;
	size_t objs_count, i;
	const SEL sel = @selector(setObject:forKey:);
	IMP set = [OFMutableDictionary instanceMethodForSelector: sel];

	self = [self init];
	count = [keys count];

	if (keys == nil || objs == nil || count != [objs count]) {
		c = isa;
		[self dealloc];
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];
	}

	objs_data = [objs data];
	keys_data = [keys data];
	objs_data = [objs data];
	objs_count = [objs count];

	for (i = 0; i < count; i++) {
		uint32_t fullhash, hash;
		OFObject <OFCopying> *key;

		if (keys_data[i] == nil || objs_data[i] == nil) {
			c = isa;
			[self dealloc];
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];
		}

		fullhash = [keys_data[i] hash];
		hash = fullhash & (size - 1);

	if (objs == nil || keys == nil || objs_count != [keys count]) {
		@try {
			key = [keys_data[i] copy];
		Class c = isa;
		} @catch (OFException *e) {
			[self dealloc];
			@throw e;
		}
		[self dealloc];
		@throw [OFInvalidArgumentException newWithClass: c
						       selector: _cmd];
	}

		@try {
	@try {
			of_dictionary_list_object_t *o;

		for (i = 0; i < objs_count; i++)
			if (data[hash] == nil)
				data[hash] = [[OFList alloc]
				    initWithListObjectSize:
				    sizeof(of_dictionary_list_object_t)];

			set(self, sel, objs_data[i], keys_data[i]);
			o = (of_dictionary_list_object_t*)
			    [data[hash] append: objs_data[i]];
			o->key = key;
			o->hash = fullhash;
		} @catch (OFException *e) {
	} @catch (OFException *e) {
			[key release];
			[self dealloc];
			@throw e;
		[self dealloc];
		@throw e;
		}
	}

	return self;
}

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

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

	return ret;
}

- initWithKey: (OFObject <OFCopying>*)first
- initWithKey: (OFObject <OFCopying>*)key
      argList: (va_list)args
{
	OFObject <OFCopying> *key;
	OFObject *obj;
	const SEL sel = @selector(setObject:forKey:);
	IMP set = [OFMutableDictionary instanceMethodForSelector: sel];
	Class c;
	uint32_t fullhash, hash;

	self = [self init];
	obj = va_arg(args, OFObject*);

	if (first == nil || obj == nil) {
		c = isa;
		[self dealloc];
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];
	}

	fullhash = [first hash];
	hash = fullhash & (size - 1);

	@try {
		set(self, sel, va_arg(args, OFObject*), key);
		key = [first copy];
		while ((key = va_arg(args, OFObject <OFCopying>*)) != nil)
			set(self, sel, va_arg(args, OFObject*), key);
	} @catch (OFException *e) {
		[self dealloc];
		@throw e;
	}

	@try {
		of_dictionary_list_object_t *o;

		if (data[hash] == nil)
			data[hash] = [[OFList alloc] initWithListObjectSize:
			    sizeof(of_dictionary_list_object_t)];

		o = (of_dictionary_list_object_t*)[data[hash] append: obj];
		o->key = key;
		o->hash = fullhash;
	} @catch (OFException *e) {
		[key release];
		[self dealloc];
		@throw e;
	}

	while ((key = va_arg(args, OFObject <OFCopying>*)) != nil) {
		if ((obj = va_arg(args, OFObject*)) == nil) {
			c = isa;
			[self dealloc];
			@throw [OFInvalidArgumentException newWithClass: isa
							       selector: _cmd];
		}

		fullhash = [key hash];
		hash = fullhash & (size - 1);

		@try {
			key = [key copy];
		} @catch (OFException *e) {
			[self dealloc];
			@throw e;
		}

		@try {
			of_dictionary_list_object_t *o;

			if (data[hash] == nil)
				data[hash] = [[OFList alloc]
				    initWithListObjectSize:
				    sizeof(of_dictionary_list_object_t)];

			o = (of_dictionary_list_object_t*)
			    [data[hash] append: obj];
			o->key = key;
			o->hash = fullhash;
		} @catch (OFException *e) {
			[key release];
			[self dealloc];
			@throw e;
		}
	}

	return self;
}

- (float)averageItemsPerBucket
{
	size_t items, buckets, i;

	items = 0;
	buckets = 0;

	for (i = 0; i < size; i++) {
		if (data[i] != nil) {
			items += [data[i] count];
			buckets++;
		}
	}

	return (float)items / buckets;
}

- (id)objectForKey: (OFObject*)key
- (id)objectForKey: (OFObject <OFCopying>*)key
{
	uint32_t hash;
	uint32_t i, hash;
	of_dictionary_list_object_t *iter;

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

	hash = [key hash] & (size - 1);
	hash = [key hash];

	for (i = hash & (size - 1); i < size && data[i].key != nil &&
	    ![data[i].key isEqual: key]; i++);
	if (data[hash] == nil)

	/* In case the last bucket is already used */
	if (i >= size)
		for (i = 0; i < size && data[i].key != nil &&
		    ![data[i].key isEqual: key]; i++);

	/* Key not in dictionary */
	if (i >= size || data[i].key == nil)
		return nil;

	for (iter = (of_dictionary_list_object_t*)[data[hash] first];
	    iter != NULL; iter = iter->next)
	return data[i].object;
}

		if ([iter->key isEqual: key])
			return iter->object;

	return nil;
- (size_t)count
{
	return count;
}

- (id)copy
{
	return [self retain];
}

*/

- (void)dealloc
{
	size_t i;

	for (i = 0; i < size; i++) {
		if (data[i] != nil) {
		if (data[i].key != nil) {
			of_dictionary_list_object_t *iter;

			for (iter = (of_dictionary_list_object_t*)
			    [data[i] first]; iter != NULL; iter = iter->next)
				[iter->key release];
			[data[i].key release];

			[data[i] release];
			[data[i].object release];
		}
	}

	[super dealloc];
}

- setObject: (OFObject*)obj
     forKey: (OFObject <OFCopying>*)key
{
	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];
}

- removeObjectForKey: (OFObject*)key
{
	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];
}

- changeHashSize: (int)hashsize
{
	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];
}
@end

 * An iterator pair combines a key and its object in a single struct.
 */
typedef struct __of_iterator_pair {
	/// The key
	id	 key;
	/// The object for the key
	id	 object;
	/// The hash of the key
	uint32_t hash;
} of_iterator_pair_t;

extern int _OFIterator_reference;

/**
 * The OFIterator class provides methods to iterate through objects.
 */
@interface OFIterator: OFObject
{
	OFList		 **data;
	size_t		 size;
	struct of_dictionary_bucket *data;
	size_t			    size;
	size_t			    pos;
	of_dictionary_list_object_t *last;
}

- initWithData: (OFList**)data
- initWithData: (struct of_dictionary_bucket*)data
	  size: (size_t)size;

/**
 * \return A struct containing the next key and object
 */
- (of_iterator_pair_t)nextKeyObjectPair;

/**
 * Resets the iterator, so the next call to nextObject returns the first again.
 */
- reset;
@end

@interface OFDictionary (OFIterator)
/**
 * Creates an OFIterator for the dictionary.
 *
 * It will copy the data of the OFDictionary so that OFIterator will always
 * operate on the data that was present when it was created. If you changed the
 * OFDictionary and want to operate on the new data, you need to create a new
 * OFIterator, as using reset will only reset the OFIterator, but won't update
 * the data. It will also retain the data inside the OFDictionary so the
 * OFIterator still works after you released the OFDictionary. Thus, if you want
 * to get rid of the objects in the OFDictionary, you also need to release the
 * OFIterator.
 *
 * \return An OFIterator for the OFDictionary
 */
- (OFIterator*)iterator;
@end

@implementation OFIterator
- init
{
	@throw [OFNotImplementedException newWithClass: isa
					      selector: _cmd];
}

- initWithData: (OFList**)data_
- initWithData: (struct of_dictionary_bucket*)data_
	  size: (size_t)size_
{
	size_t i;

	self = [super init];

	data = data_;
	size = size_;
	data = [self allocMemoryForNItems: size
				 withSize: sizeof(struct of_dictionary_bucket)];

	for (i = 0; i < size; i++) {
		if (data_[i].key != nil) {
			data[i].key = [data_[i].key copy];
			data[i].object = [data_[i].object retain];
		} else
	last = NULL;
			data[i].key = nil;
	}

	return self;
}

- (of_iterator_pair_t)nextKeyObjectPair
- (void)dealloc
{
	of_iterator_pair_t next;
	size_t i;

	for (;;) {
	for (i = 0; i < size; i++) {
		if (last == NULL) {
			for (; pos < size && data[pos] == nil; pos++);
			if (pos == size) {
				next.key = nil;
				next.object = nil;
		if (data[i].key != nil) {
			[data[i].key release];
			[data[i].object release];
				next.hash = 0;
				return next;
			}

			last = (of_dictionary_list_object_t*)
			    [data[pos++] first];
		}
	}

	[super dealloc];
}

			next.key = last->key;
			next.object = last->object;
- (of_iterator_pair_t)nextKeyObjectPair
			next.hash = last->hash;
			return next;
		}
{
	of_iterator_pair_t next;

	for (; pos < size && data[pos].key == nil; pos++);

		if ((last = last->next) != NULL) {
			next.key = last->key;
			next.object = last->object;
			next.hash = last->hash;
			return next;
		}
	}
	if (pos < size) {
		next.key = data[pos].key;
		next.object = data[pos].object;
		pos++;
	} else {
		next.key = nil;
		next.object = nil;
	}

	return next;
}

- reset
{
	pos = 0;
	last = NULL;

	return self;
}
@end

@implementation OFDictionary (OFIterator)
- (OFIterator*)iterator
{
	return [[[OFIterator alloc] initWithData: data
					    size: size] autorelease];
}
@end

/**
 * The OFList class provides easy to use double-linked lists.
 */
@interface OFList: OFObject <OFCopying>
{
	of_list_object_t *first;
	of_list_object_t *last;
	size_t		 listobj_size;
	size_t		 count;
	BOOL		 retain_and_release;
}

/**
 * \return A new autoreleased OFList
 */
+ list;

/**
 * \param listobj_size The size of a list object
 * \return A new autoreleased OFList with the specified list object size
 */
+ listWithListObjectSize: (size_t)listobj_size;

/**
 * Initializes an already allocated OFList with the specified list object size.
 *
 * \param listobj_size The size of a list object
 * \return An initialized OFList with the specified list object size
 */
- initWithListObjectSize: (size_t)listobj_size;

/**
 * Initializes an already allocated OFList that does not retain/release objects
 * added to it.
 *
 * \return An initialized OFList
 */
- initWithoutRetainAndRelease;

@implementation OFList
+ list
{
	return [[[self alloc] init] autorelease];
}

+ listWithListObjectSize: (size_t)listobj_size_
{
	return [[[self alloc]
	    initWithListObjectSize: listobj_size_] autorelease];
}

- init
{
	self = [super init];

	first = NULL;
	last = NULL;
	listobj_size = sizeof(of_list_object_t);
	retain_and_release = YES;

	return self;
}

- initWithListObjectSize: (size_t)listobj_size_;
{
	self = [super init];

	first = NULL;
	last = NULL;
	listobj_size = listobj_size_;
	retain_and_release = YES;

	return self;
}

- initWithoutRetainAndRelease
{
	self = [super init];

	first = NULL;
	last = NULL;
	listobj_size = sizeof(of_list_object_t);

	return self;
}

- (void)dealloc
{
	of_list_object_t *iter;

	return last;
}

- (of_list_object_t*)append: (id)obj
{
	of_list_object_t *o;

	o = [self allocMemoryWithSize: listobj_size];
	o = [self allocMemoryWithSize: sizeof(of_list_object_t)];
	o->object = obj;
	o->next = NULL;
	o->prev = last;

	if (last != NULL)
		last->next = o;

	return o;
}

- (of_list_object_t*)prepend: (id)obj
{
	of_list_object_t *o;

	o = [self allocMemoryWithSize: listobj_size];
	o = [self allocMemoryWithSize: sizeof(of_list_object_t)];
	o->object = obj;
	o->next = first;
	o->prev = NULL;

	if (first != NULL)
		first->prev = o;

}

- (of_list_object_t*)insert: (id)obj
		     before: (of_list_object_t*)listobj
{
	of_list_object_t *o;

	o = [self allocMemoryWithSize: listobj_size];
	o = [self allocMemoryWithSize: sizeof(of_list_object_t)];
	o->object = obj;
	o->next = listobj;
	o->prev = listobj->prev;

	if (listobj->prev != NULL)
		listobj->prev->next = o;

}

- (of_list_object_t*)insert: (id)obj
		      after: (of_list_object_t*)listobj
{
	of_list_object_t *o;

	o = [self allocMemoryWithSize: listobj_size];
	o = [self allocMemoryWithSize: sizeof(of_list_object_t)];
	o->object = obj;
	o->next = listobj->next;
	o->prev = listobj;

	if (listobj->next != NULL)
		listobj->next->prev = o;

		new = [[OFList alloc] initWithoutRetainAndRelease];

	o = NULL;
	prev = NULL;

	@try {
		for (iter = first; iter != NULL; iter = iter->next) {
			o = [new allocMemoryWithSize: listobj_size];
			o = [new allocMemoryWithSize: sizeof(of_list_object_t)];
			o->object = iter->object;
			o->next = NULL;
			o->prev = prev;

			if (new->first == NULL)
				new->first = o;
			if (prev != NULL)

/**
 * Remove the object with the given key from the dictionary.
 *
 * \param key The key whose object should be removed
 */
- removeObjectForKey: (OFObject*)key;

/**
 * Changes the hash size of the dictionary.
 *
 * \param hashsize The new hash size for the dictionary
 */
- changeHashSize: (int)hashsize;
@end

#include "config.h"

#include <string.h>

#import "OFMutableDictionary.h"
#import "OFExceptions.h"
#import "OFMacros.h"

#define BUCKET_SIZE sizeof(struct of_dictionary_bucket)

static OF_INLINE void
resize(id self, size_t count, struct of_dictionary_bucket **data, size_t *size)
{
	float fill = (float)count / *size;
	size_t newsize;
	struct of_dictionary_bucket *newdata;
	uint32_t i;

	/*
	 * FIXME:
	 *
	 * Throw an OFOutOfRangeException if it would overflow (unlikely to
	 * happen).
	 */
	if (fill > 0.75)
		newsize = *size * 2;
	else if (fill < 0.25)
		newsize = *size / 2;
	else
		return;

	newdata = [self allocMemoryForNItems: newsize
				    withSize: BUCKET_SIZE];
	memset(newdata, 0, newsize * BUCKET_SIZE);

	for (i = 0; i < *size; i++) {
		if ((*data)[i].key != nil) {
			uint32_t j = (*data)[i].hash & (newsize - 1);
			for (; j < newsize && newdata[j].key != nil; j++);

			/* In case the last bucket is already used */
			if (j >= newsize)
				for (j = 0; j < newsize &&
				    newdata[j].key != nil; i++);
			if (j >= newsize)
				@throw [OFOutOfRangeException
				    newWithClass: [self class]];

			newdata[j].key = (*data)[i].key;
			newdata[j].object = (*data)[i].object;
			newdata[j].hash = (*data)[i].hash;
		}
	}

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

@implementation OFMutableDictionary
- setObject: (OFObject*)obj
     forKey: (OFObject <OFCopying>*)key
{
	uint32_t fullhash, hash;
	uint32_t i, hash;
	of_dictionary_list_object_t *iter;

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

	fullhash = [key hash];
	hash = [key hash];
	hash = fullhash & (size - 1);

	if (data[hash] == nil)
		data[hash] = [[OFList alloc] initWithListObjectSize:
	for (i = hash & (size - 1); i < size && data[i].key != nil &&
	    ![data[i].key isEqual: key]; i++);
		    sizeof(of_dictionary_list_object_t)];

	/* In case the last bucket is already used */
	if (i >= size)
	for (iter = (of_dictionary_list_object_t*)[data[hash] first];
		for (i = 0; i < size && data[i].key != nil &&
	    iter != NULL; iter = iter->next) {
		if ([iter->key isEqual: key]) {
		    ![data[i].key isEqual: key]; i++);
			[obj retain];
			[iter->object release];
			iter->object = obj;

			return self;
		}
	}
	/* Key not in dictionary */
	if (i >= size || data[i].key == nil) {
		resize(self, count + 1, &data, &size);

		i = hash & (size - 1);
		for (; i < size && data[i].key != nil; i++);

		/* In case the last bucket is already used */
		if (i >= size)
			for (i = 0; i < size && data[i].key != nil; i++);
		if (i >= size)
			@throw [OFOutOfRangeException newWithClass: isa];

	key = [key copy];
		data[i].key = [key copy];
		data[i].object = [obj retain];
		data[i].hash = hash;
		count++;

	@try {
		return self;
		of_dictionary_list_object_t *o;

	}
		o = (of_dictionary_list_object_t*)[data[hash] append: obj];
		o->key = key;
		o->hash = fullhash;
	} @catch (OFException *e) {
		[key release];
		@throw e;
	}

	[obj retain];
	[data[i].object release];
	data[i].object = obj;

	return self;
}

- removeObjectForKey: (OFObject*)key
{
	uint32_t hash;
	uint32_t i, hash;
	of_dictionary_list_object_t *iter;

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

	hash = [key hash] & (size - 1);
	hash = [key hash];

	if (data[hash] == nil)
		return self;

	for (i = hash & (size - 1); i < size && data[i].key != nil &&
	for (iter = (of_dictionary_list_object_t*)[data[hash] first];
	    iter != NULL; iter = iter->next) {
		if ([iter->object isEqual: key]) {
	    ![data[i].key isEqual: key]; i++);
			[iter->key release];
			[data[hash] remove: (of_list_object_t*)iter];

			if ([data[hash] first] == NULL) {
				[data[hash] release];
				data[hash] = nil;
			}

	/* In case the last bucket is already used */
			return self;
		}
	}

	if (i >= size)
	return self;
}

		for (i = 0; i < size && data[i].key != nil &&
- changeHashSize: (int)hashsize
{
	OFList **newdata;
	size_t newsize, i;
	of_dictionary_list_object_t *iter;

		    ![data[i].key isEqual: key]; i++);
	if (hashsize < 8 || hashsize >= 28)
		@throw [OFInvalidArgumentException newWithClass: isa
						       selector: _cmd];

	newsize = (size_t)1 << hashsize;
	newdata = [self allocMemoryForNItems: newsize
				    withSize: sizeof(OFList*)];
	memset(newdata, 0, newsize * sizeof(OFList*));

	/* Key not in dictionary */
	for (i = 0; i < size; i++) {
		if (OF_LIKELY(data[i] == nil))
	if (i >= size || data[i].key == nil)
			continue;

		return self;
		for (iter = (of_dictionary_list_object_t*)[data[i] first];
		    iter != NULL; iter = iter->next) {
			uint32_t hash = iter->hash & (newsize - 1);
			of_dictionary_list_object_t *o;

			if (newdata[hash] == nil)
	[data[i].key release];
				newdata[hash] = [[OFList alloc]
				    initWithListObjectSize:
				    sizeof(of_dictionary_list_object_t)];

	[data[i].object release];
			o = (of_dictionary_list_object_t*)
			    [newdata[hash] append: iter->object];
			o->key = iter->key;
	data[i].key = nil;
			o->hash = iter->hash;
		}


	count--;
		[data[i] release];
	}

	resize(self, count, &data, &size);
	[self freeMemory: data];
	data = newdata;
	size = newsize;

	return self;
}

- (id)copy
{
	return [[OFDictionary alloc] initWithDictionary: self];
}
@end

#include <string.h>

#import "OFAutoreleasePool.h"
#import "OFDictionary.h"
#import "OFString.h"
#import "OFExceptions.h"

#define TESTS 15
#define TESTS 14

int
main()
{
	int i = 0;

	OFDictionary *dict = [OFMutableDictionary dictionaryWithHashSize: 16];
	OFDictionary *dict = [OFMutableDictionary dictionary];
	OFDictionary *dict2;
	OFArray *keys, *objs;
	OFIterator *iter = [dict iterator];
	OFIterator *iter;
	of_iterator_pair_t pair[2];

	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
	OFString *key1 = [OFString stringWithCString: "key1"];
	OFString *key2 = [OFString stringWithCString: "key2"];
	OFString *value1 = [OFString stringWithCString: "value1"];
	OFString *value2 = [OFString stringWithCString: "value2"];
	OFString *key1 = [OFString stringWithString: @"key1"];
	OFString *key2 = [OFString stringWithString: @"key2"];
	OFString *value1 = [OFString stringWithString: @"value1"];
	OFString *value2 = [OFString stringWithString: @"value2"];

	[dict setObject: value1
		 forKey: key1];
	[dict setObject: value2
		 forKey: key2];
	[pool release];

	i++;
	if (strcmp([[dict objectForKey: @"key1"] cString], "value1")) {
		printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS);
		return 1;
	}

	i++;
	if (strcmp([[dict objectForKey: key2] cString], "value2")) {
		printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS);
		return 1;
	}

	i++;
	pair[0] = [iter nextKeyObjectPair];
	pair[1] = [iter nextKeyObjectPair];
	if (![pair[0].key isEqual: @"key2"] ||
	    ![pair[0].object isEqual: @"value2"] ||
	    ![pair[1].key isEqual: @"key1"] ||
	    ![pair[1].object isEqual: @"value1"]) {
		printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS);
		return 1;
	}

	i++;
	[dict changeHashSize: 8];
	iter = [dict iterator];
	pair[0] = [iter nextKeyObjectPair];
	pair[1] = [iter nextKeyObjectPair];
	if (![pair[0].key isEqual: @"key1"] ||
	    ![pair[0].object isEqual: @"value1"] ||
	    ![pair[1].key isEqual: @"key2"] ||
	    ![pair[1].object isEqual: @"value2"]) {
		printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS);
		return 1;
	}

	i++;
	if ([dict averageItemsPerBucket] != 1.0) {
	if ([dict count] != 2) {
		printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS);
		return 1;
	}

	i++;
	if ([iter nextKeyObjectPair].object != nil) {
		printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS);
		return 1;
	}

	i++;
	if ([dict objectForKey: @"key3"] != nil) {
		printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS);
		return 1;
	}

	i++;
	[dict release];
	dict = [OFDictionary dictionaryWithKeysAndObjects: @"foo", @"bar",
							    @"baz", @"qux",
							    nil];
							   @"baz", @"qux",
							   nil];

	if (![[dict objectForKey: @"foo"] isEqual: @"bar"]) {
		printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS);
		return 1;
	}

	i++;