ObjFW  Artifact [c74680827d]

Artifact c74680827d230905dc9a98a33065d673dbc6274250664cd147fc01466db77faf:

• File src/OFMutableDictionary.m — part of check-in [3bccfadcc1] at 2010-06-01 18:00:12 on branch trunk — Fix a very nasty typo in OFMutableDictionary.

  This typo would prevent termination in the very rare case that the last
  bucket is already used. (user: js, size: 5237) [annotate] [blame] [check-ins using] [more...]

/*
 * Copyright (c) 2008 - 2010
 *   Jonathan Schleifer <js@webkeks.org>
 *
 * All rights reserved.
 *
 * This file is part of ObjFW. 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 "macros.h"

#define BUCKET struct of_dictionary_bucket
#define DELETED &of_dictionary_deleted_bucket

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

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

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

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

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

	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;

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

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

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

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

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

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

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

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

		[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)];

		@try {
			key = [key copy];
		} @catch (OFException *e) {
			[self freeMemory: b];
		}

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

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

		return nil;
	}

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

	return [old autorelease];
}

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

	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 ([data[i]->key isEqual: key]) {
			old = data[i]->object;

			[data[i]->key release];
			[self freeMemory: data[i]];
			data[i] = DELETED;

			count--;
			mutations++;
			[self _resizeForCount: count];

			return [old autorelease];
		}
	}

	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 ([data[i]->key isEqual: key]) {
			old = data[i]->object;

			[data[i]->key release];
			[self freeMemory: data[i]];
			data[i] = DELETED;

			count--;
			mutations++;
			[self _resizeForCount: count];

			return [old autorelease];
		}
	}

	return nil;
}

- copy
{
	return [[OFDictionary alloc] initWithDictionary: self];
}

- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state
			   objects: (id*)objects
			     count: (int)count_
{
	int i;

	for (i = 0; i < count_; i++) {
		for (; state->state < size && (data[state->state] == NULL ||
		    data[state->state] == DELETED); state->state++);

		if (state->state < size) {
			objects[i] = data[state->state]->key;
			state->state++;
		} else
			break;
	}

	state->itemsPtr = objects;
	state->mutationsPtr = &mutations;

	return i;
}

- (OFEnumerator*)objectEnumerator
{
	return [[[OFDictionaryObjectEnumerator alloc]
		initWithData: data
			size: size
	    mutationsPointer: &mutations] autorelease];
}

- (OFEnumerator*)keyEnumerator
{
	return [[[OFDictionaryKeyEnumerator alloc]
		initWithData: data
			size: size
	    mutationsPointer: &mutations] autorelease];
}
@end