ObjFW  Diff

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

#define MIN_CAPACITY 16

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

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

static void
defaultRelease(void *object)
{
}

static uint32_t
static unsigned long
defaultHash(void *object)
{
	return (uint32_t)(uintptr_t)object;
	return (unsigned long)(uintptr_t)object;
}

static bool
defaultEqual(void *object1, void *object2)
{
	return (object1 == object2);
}

OF_DIRECT_MEMBERS
@interface OFMapTable ()
- (void)of_setObject: (void *)object
	      forKey: (void *)key
		hash: (uint32_t)hash;
		hash: (unsigned long)hash;
@end

OF_DIRECT_MEMBERS
@interface OFMapTableEnumerator ()
- (instancetype)of_initWithMapTable: (OFMapTable *)mapTable
			    buckets: (struct of_map_table_bucket **)buckets
			   capacity: (uint32_t)capacity
			   capacity: (unsigned long)capacity
		   mutationsPointer: (unsigned long *)mutationsPtr
    OF_METHOD_FAMILY(init);
@end

@interface OFMapTableKeyEnumerator: OFMapTableEnumerator
@end

		SET_DEFAULT(_objectFunctions.retain, defaultRetain);
		SET_DEFAULT(_objectFunctions.release, defaultRelease);
		SET_DEFAULT(_objectFunctions.hash, defaultHash);
		SET_DEFAULT(_objectFunctions.equal, defaultEqual);

#undef SET_DEFAULT

		if (capacity > UINT32_MAX / sizeof(*_buckets) ||
		    capacity > UINT32_MAX / 8)
		if (capacity > ULONG_MAX / sizeof(*_buckets) ||
		    capacity > ULONG_MAX / 8)
			@throw [OFOutOfRangeException exception];

		for (_capacity = 1; _capacity < capacity;) {
			if (_capacity > UINT32_MAX / 2)
			if (_capacity > ULONG_MAX / 2)
				@throw [OFOutOfRangeException exception];

			_capacity *= 2;
		}

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

		if (_capacity < MIN_CAPACITY)
			_capacity = MIN_CAPACITY;

		_buckets = [self allocZeroedMemoryWithSize: sizeof(*_buckets)
		_buckets = of_calloc(_capacity, sizeof(*_buckets));
						     count: _capacity];

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

	return self;
}

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

			free(_buckets[i]);
		}
	}

	free(_buckets);

	[super dealloc];
}

- (bool)isEqual: (id)object
{
	OFMapTable *mapTable;

	mapTable = object;

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

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

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

	return true;
}

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

	for (uint32_t i = 0; i < _capacity; i++) {
	for (unsigned long i = 0; i < _capacity; i++) {
		if (_buckets[i] != NULL && _buckets[i] != &deleted) {
			hash += OF_ROR(_buckets[i]->hash, _rotate);
			hash += _objectFunctions.hash(_buckets[i]->object);
			hash ^= OF_ROR(_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 (uint32_t i = 0; i < _capacity; i++)
		for (unsigned long i = 0; i < _capacity; i++)
			if (_buckets[i] != NULL && _buckets[i] != &deleted)
				[copy of_setObject: _buckets[i]->object
					    forKey: _buckets[i]->key
					      hash: OF_ROR(_buckets[i]->hash,
							_rotate)];
	} @catch (id e) {
		[copy release];
		@throw e;
	}

	return copy;
}

- (size_t)count
{
	return _count;
}

- (void *)objectForKey: (void *)key
{
	uint32_t i, hash, last;
	unsigned long i, hash, last;

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

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

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

	return NULL;
}

- (void)of_resizeForCount: (uint32_t)count OF_DIRECT
- (void)of_resizeForCount: (unsigned long)count OF_DIRECT
{
	uint32_t fullness, capacity;
	unsigned long fullness, capacity;
	struct of_map_table_bucket **buckets;

	if (count > UINT32_MAX / sizeof(*_buckets) || count > UINT32_MAX / 8)
	if (count > ULONG_MAX / sizeof(*_buckets) || count > ULONG_MAX / 8)
		@throw [OFOutOfRangeException exception];

	fullness = count * 8 / _capacity;

	if (fullness >= 6) {
		if (_capacity > UINT32_MAX / 2)
		if (_capacity > ULONG_MAX / 2)
			return;

		capacity = _capacity * 2;
	} else if (fullness <= 1)
		capacity = _capacity / 2;
	else
		return;

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

	buckets = [self allocZeroedMemoryWithSize: sizeof(*buckets)
	buckets = of_calloc(capacity, sizeof(*buckets));
					    count: capacity];

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

			last = capacity;

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

			/* In case the last bucket is already used */

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

			buckets[j] = _buckets[i];
		}
	}

	[self freeMemory: _buckets];
	free(_buckets);
	_buckets = buckets;
	_capacity = capacity;
}

- (void)of_setObject: (void *)object
	      forKey: (void *)key
		hash: (uint32_t)hash
		hash: (unsigned long)hash
{
	uint32_t i, last;
	unsigned long i, last;
	void *old;

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

	hash = OF_ROL(hash, _rotate);
	last = _capacity;

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

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

		bucket = [self allocMemoryWithSize: sizeof(*bucket)];
		bucket = of_malloc(1, sizeof(*bucket));

		@try {
			bucket->key = _keyFunctions.retain(key);
		} @catch (id e) {
			[self freeMemory: bucket];
			free(bucket);
			@throw e;
		}

		@try {
			bucket->object = _objectFunctions.retain(object);
		} @catch (id e) {
			_keyFunctions.release(bucket->key);
			[self freeMemory: bucket];
			free(bucket);
			@throw e;
		}

		bucket->hash = hash;

		_buckets[i] = bucket;
		_count++;

	[self of_setObject: object
		    forKey: key
		      hash: _keyFunctions.hash(key)];
}

- (void)removeObjectForKey: (void *)key
{
	uint32_t i, hash, last;
	unsigned long i, hash, last;

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

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

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

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

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

			[self freeMemory: _buckets[i]];
			free(_buckets[i]);
			_buckets[i] = &deleted;

			_count--;
			[self of_resizeForCount: _count];

			return;
		}

		if (_buckets[i] == &deleted)
			continue;

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

			[self freeMemory: _buckets[i]];
			free(_buckets[i]);
			_buckets[i] = &deleted;

			_count--;
			_mutations++;
			[self of_resizeForCount: _count];

			return;
		}
	}
}

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

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

			[self freeMemory: _buckets[i]];
			free(_buckets[i]);
			_buckets[i] = NULL;
		}
	}

	_count = 0;
	_capacity = MIN_CAPACITY;
	_buckets = [self resizeMemory: _buckets
				 size: sizeof(*_buckets)
	_buckets = of_realloc(_buckets, _capacity, sizeof(*_buckets));
				count: _capacity];

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

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

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

	return false;
}

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

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

	return false;
}

	       mutationsPointer: &_mutations] autorelease];
}

- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t *)state
			   objects: (id *)objects
			     count: (int)count
{
	uint32_t j = (uint32_t)state->state;
	unsigned long j = state->state;
	int i;

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

		if (j < _capacity) {

- (instancetype)init
{
	OF_INVALID_INIT_METHOD
}

- (instancetype)of_initWithMapTable: (OFMapTable *)mapTable
			    buckets: (struct of_map_table_bucket **)buckets
			   capacity: (uint32_t)capacity
			   capacity: (unsigned long)capacity
		   mutationsPointer: (unsigned long *)mutationsPtr
{
	self = [super init];

	_mapTable = [mapTable retain];
	_buckets = buckets;
	_capacity = capacity;