ObjFW  Check-in [24ecf55297]

 */

#include <stdarg.h>

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

typedef struct __of_dictionary_list_object
{
	/* of_list_object_t */
	struct __of_dictionary_list_object *next;
	struct __of_dictionary_list_object *prev;
	id				   object;
	/* OFDictionary additions */
	id				   key;
	uint32_t			   hash;
} of_dictionary_list_object_t;

/**
 * The OFDictionary class provides a class for using hash tables.
 */
@interface OFDictionary: OFObject
{
	OFList **data;

	return self;
}

- initWithKey: (OFObject <OFCopying>*)key
    andObject: (OFObject*)obj
{
	Class c;
	uint32_t hash;
	uint32_t fullhash, hash;

	self = [self init];

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

	hash = [key hash] & (size - 1);
	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;

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

		[data[hash] append: key];
		[data[hash] append: obj];
		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;
	} @finally {
		[key release];
	}

	return self;
}

- initWithKeys: (OFArray*)keys
    andObjects: (OFArray*)objs

						    andSelector: _cmd];
	}

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

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

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

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

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

		@try {
			of_dictionary_list_object_t *o;

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

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

	return self;
}

- initWithKeysAndObjects: (OFObject <OFCopying>*)first, ...

- initWithKey: (OFObject <OFCopying>*)first
   andArgList: (va_list)args
{
	OFObject <OFCopying> *key;
	OFObject *obj;
	Class c;
	uint32_t hash;
	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
						    andSelector: _cmd];
	}

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

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

	@try {
		of_dictionary_list_object_t *o;

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

		[data[hash] append: key];
		[data[hash] append: obj];
		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;
	} @finally {
		[key release];
	}

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

		hash = [key hash] & (size - 1);
		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] init];
				data[hash] = [[OFList alloc]
				    initWithListObjectSize:
				    sizeof(of_dictionary_list_object_t)];

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

	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] / 2;
			items += [data[i] count];
			buckets++;
		}
	}

	return (float)items / buckets;
}

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

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

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

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

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

	return nil;
}

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

}
*/

- (void)dealloc
{
	size_t i;

	for (i = 0; i < size; i++)
		if (data[i] != nil)
	for (i = 0; i < size; i++) {
		if (data[i] != 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] release];
		}
	}

	[super dealloc];
}

- setObject: (OFObject*)obj
     forKey: (OFObject <OFCopying>*)key
{

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

#import "OFObject.h"
#import "OFList.h"
#import "OFDictionary.h"

typedef struct __of_iterator_pair {
	id key;
	id object;
} 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;
	size_t		 pos;
	of_list_object_t *last;
	size_t			    pos;
	of_dictionary_list_object_t *last;
}

- initWithData: (OFList**)data
       andSize: (size_t)size;

/**
 * Returns the next object in the dictionary.
 *
 * Always call it twice in a row, as it returns the key on the first call and
 * the value on the second. Therefore, if you want a key value pair, you have
 * to call:
 *
 * key = [iter nextObject];\n
 * value = [iter nextObject];
 *
 * When there is no more object left, an OFNotInSetException is thrown.
 *
 * \return The key on the first call and the value on the second
 * \return A struct containing the next key and object
 */
- (id)nextObject;
- (of_iterator_pair_t)nextKeyObjectPair;

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

@interface OFDictionary (OFIterator)
/**
 * \return An OFIterator for the OFDictionary
 */
- (OFIterator*)iterator;
@end

	size = size_;

	last = NULL;

	return self;
}

- (id)nextObject
- (of_iterator_pair_t)nextKeyObjectPair
{
	of_iterator_pair_t next;

	for (;;) {
	if (last == NULL) {
		for (; pos < size && data[pos] == nil; pos++);
		if (pos == size)
			return nil;

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

			last = (of_dictionary_list_object_t*)
			    [data[pos++] first];
			next.key = last->key;
			next.object = last->object;
			return next;
		}

	if ((last = last->next) != NULL)
		return last->object;

		if ((last = last->next) != NULL) {
			next.key = last->key;
			next.object = last->object;
			return next;
		}
	return [self nextObject];
	}
}

- reset
{
	pos = 0;
	last = NULL;

 * the packaging of this file.
 */

#import "OFObject.h"

typedef struct __of_list_object
{
	id			object;
	struct __of_list_object *next;
	struct __of_list_object *prev;
	id			object;
} of_list_object_t;

/**
 * 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;
	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/releas objects
 * added to it..
 *
 * \return An initialized OFList
 */
- initWithoutRetainAndRelease;

#import "OFExceptions.h"

@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: sizeof(of_list_object_t)];
	o = [self allocMemoryWithSize: listobj_size];
	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: sizeof(of_list_object_t)];
	o = [self allocMemoryWithSize: listobj_size];
	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: sizeof(of_list_object_t)];
	o = [self allocMemoryWithSize: listobj_size];
	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: sizeof(of_list_object_t)];
	o = [self allocMemoryWithSize: listobj_size];
	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: sizeof(of_list_object_t)];
			o = [new allocMemoryWithSize: listobj_size];
			o->object = iter->object;
			o->next = NULL;
			o->prev = prev;

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

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

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

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

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

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

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

			return self;
		}
	}

	key = [key copy];

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

	@try {
		[data[hash] append: obj];

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

	return self;
}

- removeObjectForKey: (OFObject*)key
{
	uint32_t hash;
	of_list_object_t *iter;
	of_dictionary_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 = (of_dictionary_list_object_t*)[data[hash] first];
	for (iter = [data[hash] first]; iter != NULL; iter = iter->next->next) {
	    iter != NULL; iter = iter->next) {
		if ([iter->object isEqual: key]) {
			[data[hash] remove: iter->next];
			[data[hash] remove: iter];
			[iter->key release];
			[data[hash] remove: (of_list_object_t*)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;
	of_dictionary_list_object_t *iter;

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

	newsize = (size_t)1 << hashsize;
	newdata = [self allocMemoryForNItems: newsize
				    withSize: sizeof(OFList*)];
	memset(newdata, 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);
		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)
				newdata[hash] = [[OFList alloc] init];
				newdata[hash] = [[OFList alloc]
				    initWithListObjectSize:
				    sizeof(of_dictionary_list_object_t)];

			o = (of_dictionary_list_object_t*)
			[newdata[hash] append: iter->object];
			[newdata[hash] append: iter->next->object];
			    [newdata[hash] append: iter->object];
			o->key = iter->key;
			o->hash = iter->hash;
		}

		[data[i] release];
	}

	[self freeMemory: data];
	data = newdata;

- (OFString*)string
{
	OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init];
	char *str_c;
	size_t len, i, j;
	OFString *ret, *tmp;
	OFIterator *iter;

	len = [name length] + 4;
	str_c = [self allocMemoryWithSize: len];

	/* Start of tag */
	*str_c = '<';
	memcpy(str_c + 1, [name cString], [name length]);
	i = [name length] + 1;

	/* Attributes */
	if (attrs != nil) {
	iter = [attrs iterator];
	for (;;) {
		OFIterator *iter = [attrs iterator];

		for (;;) {
		OFString *key, *val;
			of_iterator_pair_t pair;

		key = [iter nextObject];
			pair = [iter nextKeyObjectPair];
		val = [iter nextObject];

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

		tmp = [val stringByXMLEscaping];
			tmp = [pair.object stringByXMLEscaping];

		len += [key length] + [tmp length] + 4;
		@try {
			str_c = [self resizeMemory: str_c
					    toSize: len];
		} @catch (OFException *e) {
			[self freeMemory: str_c];
			@throw e;
		}
			len += [pair.key length] + [tmp length] + 4;
			@try {
				str_c = [self resizeMemory: str_c
						    toSize: len];
			} @catch (OFException *e) {
				[self freeMemory: str_c];
				@throw e;
			}

		str_c[i++] = ' ';
		memcpy(str_c + i, [key cString], [key length]);
		i += [key length];
		str_c[i++] = '=';
		str_c[i++] = '\'';
		memcpy(str_c + i, [tmp cString], [tmp length]);
		i += [tmp length];
		str_c[i++] = '\'';
			str_c[i++] = ' ';
			memcpy(str_c + i, [pair.key cString],
			    [pair.key length]);
			i += [pair.key length];
			str_c[i++] = '=';
			str_c[i++] = '\'';
			memcpy(str_c + i, [tmp cString], [tmp length]);
			i += [tmp length];
			str_c[i++] = '\'';

		[pool releaseObjects];
			[pool releaseObjects];
		}
	}

	/* Childen */
	if (stringval != nil || children != nil) {
		if (stringval != nil)
			tmp = [stringval stringByXMLEscaping];
		else if (children != nil) {

int
main()
{
	int i = 0;

	OFDictionary *dict = [OFMutableDictionary dictionaryWithHashSize: 16];
	OFIterator *iter = [dict iterator];
	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"];

	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 (![[iter nextObject] isEqual: @"key2"] ||
	    ![[iter nextObject] isEqual: @"value2"] ||
	    ![[iter nextObject] isEqual: @"key1"] ||
	    ![[iter nextObject] isEqual: @"value1"]) {
	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 (![[iter nextObject] isEqual: @"key1"] ||
	    ![[iter nextObject] isEqual: @"value1"] ||
	    ![[iter nextObject] isEqual: @"key2"] ||
	    ![[iter nextObject] isEqual: @"value2"]) {
	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) {
		printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS);
		return 1;
	}

	i++;
	if ([iter nextObject] != nil) {
	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);