ObjFW  Check-in [71abb030af]

       OFDictionary.m		\
       OFExceptions.m		\
       OFFile.m			\
       OFHashes.m		\
       OFIterator.m		\
       OFList.m			\
       OFMutableArray.m		\
       OFMutableDictionary.m	\
       OFMutableString.m	\
       OFNumber.m		\
       OFObject.m		\
       ${OFPLUGIN_M}		\
       OFSocket.m		\
       OFStream.m		\
       OFString.m		\

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

/**
 * \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)get: (OFObject*)key;

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

/**
 * \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)get: (OFObject*)key;

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

/**
 * \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;

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

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

#import "config.h"

#include <string.h>

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

/* Reference for static linking */
void _reference_to_OFIterator_in_OFDictionary()
{
	_OFIterator_reference = 1;
}

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

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

- init
{
	self = [super init];

	size = 4096;

		@throw e;
	}
	memset(data, 0, size * sizeof(OFList*));

	return self;
}

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

	for (i = 0; i < size; i++)
		if (data[i] != nil)
			[data[i] release];

	items = 0;
	[super dealloc];
}

	buckets = 0;
- set: (OFObject <OFCopying>*)key
   to: (OFObject*)obj
{

	uint32_t hash;
	of_list_object_t *iter, *key_obj;

	for (i = 0; i < size; i++) {
	if (key == nil || obj == nil)
		@throw [OFInvalidArgumentException newWithClass: isa
						    andSelector: _cmd];

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

	if (data[hash] == nil)
		if (data[i] != nil) {
		data[hash] = [[OFList alloc] init];

			items += [data[i] items] / 2;
	for (iter = [data[hash] first]; iter != NULL; iter = iter->next->next) {
		if ([iter->object isEqual: key]) {
			[iter->next->object release];
			[obj retain];
			iter->next->object = obj;

			buckets++;
			return self;
		}
	}

	key = [key copy];
	@try {
		key_obj = [data[hash] append: key];
	} @finally {
		[key release];
	}

	@try {
		[data[hash] append: obj];
	} @catch (OFException *e) {
		[data[hash] remove: key_obj];
		@throw e;
	}

	return self;
	return (float)items / buckets;
}

- (id)get: (OFObject*)key
{
	uint32_t hash;
	of_list_object_t *iter;

	for (iter = [data[hash] first]; iter != NULL; iter = iter->next->next)
		if ([iter->object isEqual: key])
			return iter->next->object;

	return nil;
}

- remove: (OFObject*)key
- set: (OFObject <OFCopying>*)key
{
	uint32_t hash;
	of_list_object_t *iter;

   to: (OFObject*)obj
{
	if (key == nil)
		@throw [OFInvalidArgumentException newWithClass: isa
						    andSelector: _cmd];

	@throw [OFNotImplementedException newWithClass: isa
					   andSelector: _cmd];
}
	hash = [key hash] & (size - 1);

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

	for (iter = [data[hash] first]; iter != NULL; iter = iter->next->next) {
		if ([iter->object isEqual: key]) {
			[data[hash] remove: iter->next];
			[data[hash] remove: iter];

- remove: (OFObject*)key
{
			if ([data[hash] first] == NULL) {
				[data[hash] release];
				data[hash] = nil;
			}

	@throw [OFNotImplementedException newWithClass: isa
			return self;
		}
	}

					   andSelector: _cmd];
	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] items] / 2;
			buckets++;
		}
	}

	return (float)items / buckets;
}

- changeHashSize: (int)hashsize
{
	OFList **newdata;
	size_t newsize, i;
	of_list_object_t *iter;

	if (hashsize < 8 || hashsize >= 28)
		@throw [OFInvalidArgumentException newWithClass: isa
						    andSelector: _cmd];
	@throw [OFNotImplementedException newWithClass: isa
					   andSelector: _cmd];

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

	for (i = 0; i < size; i++) {
		if (OF_LIKELY(data[i] == nil))
			continue;

		for (iter = [data[i] first]; iter != NULL;
		    iter = iter->next->next) {
			uint32_t hash = [iter->object hash] & (newsize - 1);

			if (newdata[hash] == nil)
				newdata[hash] = [[OFList alloc] init];

			[newdata[hash] append: iter->object];
			[newdata[hash] append: iter->next->object];
		}

		[data[i] release];
	}

	[self freeMem: data];
	data = newdata;
	size = newsize;

	return self;
}

/* FIXME: Implement this! */
/*
- (BOOL)isEqual
{
}

- (id)copy
{
}

- (id)mutableCopy
{
}
*/

- (void)dealloc
{
	size_t i;

	for (i = 0; i < size; i++)
		if (data[i] != nil)
			[data[i] release];

	[super dealloc];
}
@end

/*
 * Copyright (c) 2008 - 2009
 *   Jonathan Schleifer <js@webkeks.org>
 *
 * All rights reserved.
 *
 * This file is part of libobjfw. It may be distributed under the terms of the
 * Q Public License 1.0, which can be found in the file LICENSE included in
 * the packaging of this file.
 */

#import "OFDictionary.h"

/**
 * The OFMutableDictionary class provides a class for using mutable hash tables.
 */
@interface OFMutableDictionary: OFDictionary
@end

/*
 * Copyright (c) 2008 - 2009
 *   Jonathan Schleifer <js@webkeks.org>
 *
 * All rights reserved.
 *
 * This file is part of libobjfw. It may be distributed under the terms of the
 * Q Public License 1.0, which can be found in the file LICENSE included in
 * the packaging of this file.
 */

#import "config.h"

#include <string.h>

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

@implementation OFMutableDictionary
- set: (OFObject <OFCopying>*)key
   to: (OFObject*)obj
{
	uint32_t hash;
	of_list_object_t *iter, *key_obj;

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

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

	if (data[hash] == nil)
		data[hash] = [[OFList alloc] init];

	for (iter = [data[hash] first]; iter != NULL; iter = iter->next->next) {
		if ([iter->object isEqual: key]) {
			[iter->next->object release];
			[obj retain];
			iter->next->object = obj;

			return self;
		}
	}

	key = [key copy];
	@try {
		key_obj = [data[hash] append: key];
	} @finally {
		[key release];
	}

	@try {
		[data[hash] append: obj];
	} @catch (OFException *e) {
		[data[hash] remove: key_obj];
		@throw e;
	}

	return self;
}

- remove: (OFObject*)key
{
	uint32_t hash;
	of_list_object_t *iter;

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

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

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

	for (iter = [data[hash] first]; iter != NULL; iter = iter->next->next) {
		if ([iter->object isEqual: key]) {
			[data[hash] remove: iter->next];
			[data[hash] remove: iter];

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

			return self;
		}
	}

	return self;
}

- changeHashSize: (int)hashsize
{
	OFList **newdata;
	size_t newsize, i;
	of_list_object_t *iter;

	if (hashsize < 8 || hashsize >= 28)
		@throw [OFInvalidArgumentException newWithClass: isa
						    andSelector: _cmd];

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

	for (i = 0; i < size; i++) {
		if (OF_LIKELY(data[i] == nil))
			continue;

		for (iter = [data[i] first]; iter != NULL;
		    iter = iter->next->next) {
			uint32_t hash = [iter->object hash] & (newsize - 1);

			if (newdata[hash] == nil)
				newdata[hash] = [[OFList alloc] init];

			[newdata[hash] append: iter->object];
			[newdata[hash] append: iter->next->object];
		}

		[data[i] release];
	}

	[self freeMem: data];
	data = newdata;
	size = newsize;

	return self;
}

/* FIXME: Implement this! */
/*
- (id)copy
{
}

- (id)mutableCopy
{
}
*/
@end

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

int
main()
{
	OFDictionary *dict = [OFDictionary dictionaryWithHashSize: 16];
	OFDictionary *dict = [OFMutableDictionary dictionaryWithHashSize: 16];
	OFIterator *iter = [dict iterator];

	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"];