ObjFW  Diff

/*
 * Copyright (c) 2008-2022 Jonathan Schleifer <js@nil.im>
 * Copyright (c) 2008-2023 Jonathan Schleifer <js@nil.im>
 *
 * 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.QPL included in
 * the packaging of this file.
 *
 * Alternatively, it may be distributed under the terms of the GNU General
 * Public License, either version 2 or 3, which can be found in the file
 * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this
 * file.
 */

#define OF_MAP_TABLE_M

#include "config.h"

#include <stdlib.h>
#include <string.h>

#include <assert.h>

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

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

		if (_capacity < minCapacity)
			_capacity = minCapacity;

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

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

	return self;
}

}

static void
resizeForCount(OFMapTable *self, uint32_t count)
{
	uint32_t fullness, capacity;
	struct OFMapTableBucket **buckets;
	unsigned char newRotation;

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

	fullness = count * 8 / self->_capacity;

	 * below the minimum capacity.
	 */
	if ((capacity < self->_capacity && count > self->_count) ||
	    capacity < minCapacity)
		return;

	buckets = OFAllocZeroedMemory(capacity, sizeof(*buckets));
	newRotation = (OFHashSeed != 0 ? OFRandom16() & 31 : 0);

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

			rotatedHash = OFRotateLeft(self->_buckets[i]->hash,
			    newRotation);
			last = capacity;

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

			/* In case the last bucket is already used */
			if (j >= last) {
				last = self->_buckets[i]->hash & (capacity - 1);
				last = rotatedHash & (capacity - 1);

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

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

			buckets[j] = self->_buckets[i];
		}
	}

	OFFreeMemory(self->_buckets);
	self->_buckets = buckets;
	self->_capacity = capacity;
	self->_rotation = newRotation;
}

static void
setObject(OFMapTable *restrict self, void *key, void *object, uint32_t hash)
{
	uint32_t i, last;
	uint32_t rotatedHash, i, last;
	void *old;

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

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

	for (i = hash & (self->_capacity - 1);
	for (i = rotatedHash & (self->_capacity - 1);
	    i < last && self->_buckets[i] != NULL; i++) {
		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);
		last = rotatedHash & (self->_capacity - 1);

		for (i = 0; i < last && self->_buckets[i] != NULL; i++) {
			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] == &deletedBucket ||
	    !self->_keyFunctions.equal(self->_buckets[i]->key, key)) {
		struct OFMapTableBucket *bucket;

		resizeForCount(self, self->_count + 1);
		/* Resizing can change the rotation */
		rotatedHash = OFRotateLeft(hash, self->_rotation);

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

		for (i = hash & (self->_capacity - 1); i < last &&
		for (i = rotatedHash & (self->_capacity - 1); i < last &&
		    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);
			last = rotatedHash & (self->_capacity - 1);

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

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

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

	for (unsigned long i = 0; i < _capacity; i++) {
		if (_buckets[i] != NULL && _buckets[i] != &deletedBucket) {
			hash ^= OFRotateRight(_buckets[i]->hash, _rotate);
			hash ^= _buckets[i]->hash;
			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++)
			if (_buckets[i] != NULL &&
			    _buckets[i] != &deletedBucket)
				setObject(copy, _buckets[i]->key,
				    _buckets[i]->object,
				    _buckets[i]->object, _buckets[i]->hash);
				    OFRotateRight(_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;
	uint32_t i, rotatedHash, last;

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

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

	for (i = rotatedHash & (_capacity - 1);
	for (i = hash & (_capacity - 1); i < last && _buckets[i] != NULL; i++) {
	    i < last && _buckets[i] != NULL; i++) {
		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);
	last = rotatedHash & (_capacity - 1);

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

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

	return NULL;
}

- (void)setObject: (void *)object forKey: (void *)key
{
	setObject(self, key, object, (uint32_t)_keyFunctions.hash(key));
}

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

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

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

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

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

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

		}
	}

	if (i < last)
		return;

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

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

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

	}

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

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

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