ObjFW  Artifact [436bcef63e]

Artifact 436bcef63eaf8360af6e85a75d4e53ae1076bc6bf07e5eb0315c7ef6aab4b191:

• File src/OFMutableDictionary.m — part of check-in [bbf1f79b8f] at 2009-09-08 16:06:10 on branch trunk — New OFDictionary implementation and removal of a hack in OFList.

  The new implementation is easier to use as it does automatic resizing,
  but therefore it's not realtime-capable anymore. The new implementation
  should also be a little bit faster.

  I decided to change the implementation as only very few need a
  realtime-capable dictionary and those few will most likely write their
  own implementation for their specific case anyway.

  As the new implementation no longer uses OFList, this also made it
  possible to remove a hack from OFList. (user: js, size: 3431) [annotate] [blame] [check-ins using]

/*
 * 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.
 */

#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 i, hash;

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

	hash = [key hash];

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

	/* 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) {
		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];

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

		return self;
	}

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

	return self;
}

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

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

	hash = [key hash];

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

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

	[data[i].key release];
	[data[i].object release];
	data[i].key = nil;

	count--;
	resize(self, count, &data, &size);

	return self;
}

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