ObjFW  Diff

#import "OFMapTable+Private.h"
#import "OFEnumerator.h"

#import "OFEnumerationMutationException.h"
#import "OFInvalidArgumentException.h"
#import "OFOutOfRangeException.h"

#define MIN_CAPACITY 16
static const unsigned long minCapacity = 16;

struct OFMapTableBucket {
	void *key, *object;
	unsigned long hash;
};
static struct OFMapTableBucket deleted = { 0 };
static struct OFMapTableBucket deletedBucket = { 0 };

static void *
defaultRetain(void *object)
{
	return object;
}

			_capacity *= 2;
		}

		if (capacity * 8 / _capacity >= 6)
			if (_capacity <= ULONG_MAX / 2)
				_capacity *= 2;

		if (_capacity < MIN_CAPACITY)
			_capacity = MIN_CAPACITY;
		if (_capacity < minCapacity)
			_capacity = minCapacity;

		_buckets = OFAllocZeroedMemory(_capacity, sizeof(*_buckets));

		if (OFHashSeed != 0)
			_rotate = OFRandom16() & 31;
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- (void)dealloc
{
	for (unsigned long i = 0; i < _capacity; i++) {
		if (_buckets[i] != NULL && _buckets[i] != &deleted) {
		if (_buckets[i] != NULL && _buckets[i] != &deletedBucket) {
			_keyFunctions.release(_buckets[i]->key);
			_objectFunctions.release(_buckets[i]->object);

			OFFreeMemory(_buckets[i]);
		}
	}

		return;

	/*
	 * Don't downsize if we have an initial capacity or if we would fall
	 * below the minimum capacity.
	 */
	if ((capacity < self->_capacity && count > self->_count) ||
	    capacity < MIN_CAPACITY)
	    capacity < minCapacity)
		return;

	buckets = OFAllocZeroedMemory(capacity, sizeof(*buckets));

	for (unsigned long i = 0; i < self->_capacity; i++) {
		if (self->_buckets[i] != NULL &&
		    self->_buckets[i] != &deleted) {
		    self->_buckets[i] != &deletedBucket) {
			unsigned long j, last;

			last = capacity;

			for (j = self->_buckets[i]->hash & (capacity - 1);
			    j < last && buckets[j] != NULL; j++);

		@throw [OFInvalidArgumentException exception];

	hash = OFRotateLeft(hash, self->_rotate);
	last = self->_capacity;

	for (i = hash & (self->_capacity - 1);
	    i < last && self->_buckets[i] != NULL; i++) {
		if (self->_buckets[i] == &deleted)
		if (self->_buckets[i] == &deletedBucket)
			continue;

		if (self->_keyFunctions.equal(self->_buckets[i]->key, key))
			break;
	}

	/* In case the last bucket is already used */
	if (i >= last) {
		last = hash & (self->_capacity - 1);

		for (i = 0; i < last && self->_buckets[i] != NULL; i++) {
			if (self->_buckets[i] == &deleted)
			if (self->_buckets[i] == &deletedBucket)
				continue;

			if (self->_keyFunctions.equal(
			    self->_buckets[i]->key, key))
				break;
		}
	}

	/* Key not in map table */
	if (i >= last || self->_buckets[i] == NULL ||
	    self->_buckets[i] == &deleted ||
	    self->_buckets[i] == &deletedBucket ||
	    !self->_keyFunctions.equal(self->_buckets[i]->key, key)) {
		struct OFMapTableBucket *bucket;

		resizeForCount(self, self->_count + 1);

		self->_mutations++;
		last = self->_capacity;

		for (i = hash & (self->_capacity - 1); i < last &&
		    self->_buckets[i] != NULL && self->_buckets[i] != &deleted;
		    i++);
		    self->_buckets[i] != NULL &&
		    self->_buckets[i] != &deletedBucket; i++);

		/* In case the last bucket is already used */
		if (i >= last) {
			last = hash & (self->_capacity - 1);

			for (i = 0; i < last && self->_buckets[i] != NULL &&
			    self->_buckets[i] != &deleted; i++);
			    self->_buckets[i] != &deletedBucket; i++);
		}

		if (i >= last)
			@throw [OFOutOfRangeException exception];

		bucket = OFAllocMemory(1, sizeof(*bucket));

	if (mapTable->_count != _count ||
	    mapTable->_keyFunctions.equal != _keyFunctions.equal ||
	    mapTable->_objectFunctions.equal != _objectFunctions.equal)
		return false;

	for (unsigned long i = 0; i < _capacity; i++) {
		if (_buckets[i] != NULL && _buckets[i] != &deleted) {
		if (_buckets[i] != NULL && _buckets[i] != &deletedBucket) {
			void *objectIter =
			    [mapTable objectForKey: _buckets[i]->key];

			if (!_objectFunctions.equal(objectIter,
			    _buckets[i]->object))
				return false;
		}
	}

	return true;
}

- (unsigned long)hash
{
	unsigned long hash = 0;

	for (unsigned long i = 0; i < _capacity; i++) {
		if (_buckets[i] != NULL && _buckets[i] != &deleted) {
		if (_buckets[i] != NULL && _buckets[i] != &deletedBucket) {
			hash ^= OFRotateRight(_buckets[i]->hash, _rotate);
			hash ^= _objectFunctions.hash(_buckets[i]->object);
		}
	}

	return hash;
}

- (id)copy
{
	OFMapTable *copy = [[OFMapTable alloc]
	    initWithKeyFunctions: _keyFunctions
		 objectFunctions: _objectFunctions
			capacity: _capacity];

	@try {
		for (unsigned long i = 0; i < _capacity; i++)
			if (_buckets[i] != NULL && _buckets[i] != &deleted)
			if (_buckets[i] != NULL &&
			    _buckets[i] != &deletedBucket)
				setObject(copy, _buckets[i]->key,
				    _buckets[i]->object,
				    OFRotateRight(_buckets[i]->hash, _rotate));
	} @catch (id e) {
		[copy release];
		@throw e;
	}

	if (key == NULL)
		@throw [OFInvalidArgumentException exception];

	hash = OFRotateLeft(_keyFunctions.hash(key), _rotate);
	last = _capacity;

	for (i = hash & (_capacity - 1); i < last && _buckets[i] != NULL; i++) {
		if (_buckets[i] == &deleted)
		if (_buckets[i] == &deletedBucket)
			continue;

		if (_keyFunctions.equal(_buckets[i]->key, key))
			return _buckets[i]->object;
	}

	if (i < last)
		return nil;

	/* In case the last bucket is already used */
	last = hash & (_capacity - 1);

	for (i = 0; i < last && _buckets[i] != NULL; i++) {
		if (_buckets[i] == &deleted)
		if (_buckets[i] == &deletedBucket)
			continue;

		if (_keyFunctions.equal(_buckets[i]->key, key))
			return _buckets[i]->object;
	}

	return NULL;

	if (key == NULL)
		@throw [OFInvalidArgumentException exception];

	hash = OFRotateLeft(_keyFunctions.hash(key), _rotate);
	last = _capacity;

	for (i = hash & (_capacity - 1); i < last && _buckets[i] != NULL; i++) {
		if (_buckets[i] == &deleted)
		if (_buckets[i] == &deletedBucket)
			continue;

		if (_keyFunctions.equal(_buckets[i]->key, key)) {
			_mutations++;

			_keyFunctions.release(_buckets[i]->key);
			_objectFunctions.release(_buckets[i]->object);

			OFFreeMemory(_buckets[i]);
			_buckets[i] = &deleted;
			_buckets[i] = &deletedBucket;

			_count--;
			resizeForCount(self, _count);

			return;
		}
	}

	if (i < last)
		return;

	/* In case the last bucket is already used */
	last = hash & (_capacity - 1);

	for (i = 0; i < last && _buckets[i] != NULL; i++) {
		if (_buckets[i] == &deleted)
		if (_buckets[i] == &deletedBucket)
			continue;

		if (_keyFunctions.equal(_buckets[i]->key, key)) {
			_keyFunctions.release(_buckets[i]->key);
			_objectFunctions.release(_buckets[i]->object);

			OFFreeMemory(_buckets[i]);
			_buckets[i] = &deleted;
			_buckets[i] = &deletedBucket;

			_count--;
			_mutations++;
			resizeForCount(self, _count);

			return;
		}
	}
}

- (void)removeAllObjects
{
	for (unsigned long i = 0; i < _capacity; i++) {
		if (_buckets[i] != NULL) {
			if (_buckets[i] == &deleted) {
			if (_buckets[i] == &deletedBucket) {
				_buckets[i] = NULL;
				continue;
			}

			_keyFunctions.release(_buckets[i]->key);
			_objectFunctions.release(_buckets[i]->object);

			OFFreeMemory(_buckets[i]);
			_buckets[i] = NULL;
		}
	}

	_count = 0;
	_capacity = MIN_CAPACITY;
	_capacity = minCapacity;
	_buckets = OFResizeMemory(_buckets, _capacity, sizeof(*_buckets));

	/*
	 * Get a new random value for _rotate, so that it is not less secure
	 * than creating a new hash map.
	 */
	if (OFHashSeed != 0)
		_rotate = OFRandom16() & 31;
}

- (bool)containsObject: (void *)object
{
	if (object == NULL || _count == 0)
		return false;

	for (unsigned long i = 0; i < _capacity; i++)
		if (_buckets[i] != NULL && _buckets[i] != &deleted)
		if (_buckets[i] != NULL && _buckets[i] != &deletedBucket)
			if (_objectFunctions.equal(_buckets[i]->object, object))
				return true;

	return false;
}

- (bool)containsObjectIdenticalTo: (void *)object
{
	if (object == NULL || _count == 0)
		return false;

	for (unsigned long i = 0; i < _capacity; i++)
		if (_buckets[i] != NULL && _buckets[i] != &deleted)
		if (_buckets[i] != NULL && _buckets[i] != &deletedBucket)
			if (_buckets[i]->object == object)
				return true;

	return false;
}

- (OFMapTableEnumerator *)keyEnumerator

			     count: (int)count
{
	unsigned long j = state->state;
	int i;

	for (i = 0; i < count; i++) {
		for (; j < _capacity && (_buckets[j] == NULL ||
		    _buckets[j] == &deleted); j++);
		    _buckets[j] == &deletedBucket); j++);

		if (j < _capacity) {
			objects[i] = _buckets[j]->key;
			j++;
		} else
			break;
	}

	unsigned long mutations = _mutations;

	for (size_t i = 0; i < _capacity && !stop; i++) {
		if (_mutations != mutations)
			@throw [OFEnumerationMutationException
			    exceptionWithObject: self];

		if (_buckets[i] != NULL && _buckets[i] != &deleted)
		if (_buckets[i] != NULL && _buckets[i] != &deletedBucket)
			block(_buckets[i]->key, _buckets[i]->object, &stop);
	}
}

- (void)replaceObjectsUsingBlock: (OFMapTableReplaceBlock)block
{
	unsigned long mutations = _mutations;

	for (size_t i = 0; i < _capacity; i++) {
		if (_mutations != mutations)
			@throw [OFEnumerationMutationException
			    exceptionWithObject: self];

		if (_buckets[i] != NULL && _buckets[i] != &deleted) {
		if (_buckets[i] != NULL && _buckets[i] != &deletedBucket) {
			void *new;

			new = block(_buckets[i]->key, _buckets[i]->object);
			if (new == NULL)
				@throw [OFInvalidArgumentException exception];

			if (new != _buckets[i]->object) {

- (void **)nextObject
{
	if (*_mutationsPtr != _mutations)
		@throw [OFEnumerationMutationException
		    exceptionWithObject: _mapTable];

	for (; _position < _capacity && (_buckets[_position] == NULL ||
	    _buckets[_position] == &deleted); _position++);
	    _buckets[_position] == &deletedBucket); _position++);

	if (_position < _capacity)
		return &_buckets[_position++]->key;
	else
		return NULL;
}
@end

@implementation OFMapTableObjectEnumerator
- (void **)nextObject
{
	if (*_mutationsPtr != _mutations)
		@throw [OFEnumerationMutationException
		    exceptionWithObject: _mapTable];

	for (; _position < _capacity && (_buckets[_position] == NULL ||
	    _buckets[_position] == &deleted); _position++);
	    _buckets[_position] == &deletedBucket); _position++);

	if (_position < _capacity)
		return &_buckets[_position++]->object;
	else
		return NULL;
}
@end