ObjFW  Check-in [1ba9c051a6]

			count_ = [objectElement attributeForName: @"count"];

			if (object == nil || count_ == nil)
				@throw [OFInvalidFormatException exception];

			count = (size_t)[[count_ stringValue] decimalValue];

			[_mapTable setObject: (void*)(uintptr_t)count
				      forKey: [object objectByDeserializing]];

			objc_autoreleasePoolPop(pool2);
		}

		objc_autoreleasePoolPop(pool);
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- (size_t)countForObject: (id)object
{
	return (size_t)(uintptr_t)[_mapTable objectForKey: object];
}

#ifdef OF_HAVE_BLOCKS
- (void)enumerateObjectsAndCountUsingBlock:
    (of_counted_set_enumeration_block_t)block
{
	@try {
		[_mapTable enumerateKeysAndObjectsUsingBlock:
		    ^ (void *key, void *object, bool *stop) {
			block(key, (size_t)(uintptr_t)object, stop);
		}];
	} @catch (OFEnumerationMutationException *e) {
		@throw [OFEnumerationMutationException
		    exceptionWithObject: self];
	}
}
#endif

- (void)addObject: (id)object
{
	size_t count = (size_t)(uintptr_t)[_mapTable objectForKey: object];

	if (SIZE_MAX - count < 1 || UINTPTR_MAX - count < 1)
		@throw [OFOutOfRangeException exception];

	[_mapTable setObject: (void*)(uintptr_t)(count + 1)
		      forKey: object];
}

- (void)removeObject: (id)object
{
	size_t count = (size_t)(uintptr_t)[_mapTable objectForKey: object];

	if (count == 0)
		return;

	count--;

	if (count > 0)
		[_mapTable setObject: (void*)(uintptr_t)count
			      forKey: object];
	else
		[_mapTable removeObjectForKey: object];
}

- (void)makeImmutable
{
}
@end

#import "OFXMLElement.h"

#import "OFEnumerationMutationException.h"
#import "OFInvalidArgumentException.h"
#import "OFInvalidFormatException.h"

static void*
copy(void *object)
{
	return [(id)object copy];
}

static void*
retain(void *object)
{
	return [(id)object retain];
}

static void
release(void *object)
{
	[(id)object release];
}

static uint32_t
hash(void *object)
{
	return [(id)object hash];
}

static bool
equal(void *object1, void *object2)
{
	return [(id)object1 isEqual: (id)object2];
}

static const of_map_table_functions_t keyFunctions = {
	.retain = copy,
	.release = release,
	.hash = hash,
	.equal = equal
};
static const of_map_table_functions_t objectFunctions = {
	.retain = retain,
	.release = release,
	.hash = hash,
	.equal = equal
};

@implementation OFDictionary_hashtable
- init
{
	return [self initWithCapacity: 0];
}

- initWithCapacity: (size_t)capacity
{
	self = [super init];

	@try {
		_mapTable = [[OFMapTable alloc]
		    initWithKeyFunctions: keyFunctions
			 objectFunctions: objectFunctions
				capacity: capacity];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;

		OFEnumerator *keyEnumerator, *objectEnumerator;
		id key, object;

		keyEnumerator = [dictionary keyEnumerator];
		objectEnumerator = [dictionary objectEnumerator];
		while ((key = [keyEnumerator nextObject]) != nil &&
		    (object = [objectEnumerator nextObject]) != nil)
			[_mapTable setObject: object
				      forKey: key];

		objc_autoreleasePoolPop(pool);
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithObject: (id)object
	  forKey: (id)key
{
	self = [self initWithCapacity: 1];

	@try {
		[_mapTable setObject: object
			      forKey: key];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithObjects: (id const*)objects
	  forKeys: (id const*)keys
	    count: (size_t)count
{
	self = [self initWithCapacity: count];

	@try {
		size_t i;

		for (i = 0; i < count; i++)
			[_mapTable setObject: objects[i]
				      forKey: keys[i]];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

		if (count % 2 != 0)
			@throw [OFInvalidArgumentException exception];

		count /= 2;

		_mapTable = [[OFMapTable alloc]
		    initWithKeyFunctions: keyFunctions
			 objectFunctions: objectFunctions
				capacity: count];

		[_mapTable setObject: object
			      forKey: key];

		for (i = 1; i < count; i++) {
			key = va_arg(arguments, id);
			object = va_arg(arguments, id);

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

			[_mapTable setObject: object
				      forKey: key];
		}
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;

					 namespace: OF_SERIALIZATION_NS];

		if ([keys count] != [objects count])
			@throw [OFInvalidFormatException exception];

		_mapTable = [[OFMapTable alloc]
		    initWithKeyFunctions: keyFunctions
			 objectFunctions: objectFunctions
				capacity: [keys count]];

		keyEnumerator = [keys objectEnumerator];
		objectEnumerator = [objects objectEnumerator];
		while ((keyElement = [keyEnumerator nextObject]) != nil &&
		    (objectElement = [objectEnumerator nextObject]) != nil) {
			void *pool2 = objc_autoreleasePoolPush();
			OFXMLElement *key, *object;

			key = [[keyElement elementsForNamespace:
			    OF_SERIALIZATION_NS] firstObject];
			object = [[objectElement elementsForNamespace:
			    OF_SERIALIZATION_NS] firstObject];

			if (key == nil || object == nil)
				@throw [OFInvalidFormatException exception];

			[_mapTable setObject: [object objectByDeserializing]
				      forKey: [key objectByDeserializing]];

			objc_autoreleasePoolPop(pool2);
		}

		objc_autoreleasePoolPop(pool);
	} @catch (id e) {
		[self release];

	[_mapTable release];

	[super dealloc];
}

- (id)objectForKey: (id)key
{
	return [_mapTable objectForKey: key];
}

- (size_t)count
{
	return [_mapTable count];
}

	dictionary_ = (OFDictionary_hashtable*)dictionary;

	return [dictionary_->_mapTable isEqual: _mapTable];
}

- (bool)containsObject: (id)object
{
	return [_mapTable containsObject: object];
}

- (bool)containsObjectIdenticalTo: (id)object
{
	return [_mapTable containsObjectIdenticalTo: object];
}

- (OFArray*)allKeys
{
	OFArray *ret;
	id *keys;
	size_t count;

	count = [_mapTable count];
	keys = [self allocMemoryWithSize: sizeof(*keys)
				   count: count];

	@try {
		void *pool = objc_autoreleasePoolPush();
		OFMapTableEnumerator *enumerator;
		id key;
		size_t i;

		i = 0;
		enumerator = [_mapTable keyEnumerator];
		while ((key = [enumerator nextObject]) != nil) {
			assert(i < count);

			keys[i++] = key;
		}

		objc_autoreleasePoolPop(pool);

	@try {
		void *pool = objc_autoreleasePoolPush();
		OFMapTableEnumerator *enumerator;
		id object;
		size_t i;

		i = 0;
		enumerator = [_mapTable objectEnumerator];
		while ((object = [enumerator nextObject]) != nil) {
			assert(i < count);

			objects[i++] = object;
		}

		objc_autoreleasePoolPop(pool);

	    initWithEnumerator: [_mapTable keyEnumerator]
			object: self] autorelease];
}

- (OFEnumerator*)objectEnumerator
{
	return [[[OFMapTable_EnumeratorWrapper alloc]
	    initWithEnumerator: [_mapTable objectEnumerator]
			object: self] autorelease];
}

- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state
			   objects: (id*)objects
			     count: (int)count
{
	return [_mapTable countByEnumeratingWithState: state
					      objects: objects
						count: count];
}

#ifdef OF_HAVE_BLOCKS
- (void)enumerateKeysAndObjectsUsingBlock:
    (of_dictionary_enumeration_block_t)block
{
	@try {
		[_mapTable enumerateKeysAndObjectsUsingBlock:
		    ^ (void *key, void *object, bool *stop) {
			block(key, object, stop);
		}];
	} @catch (OFEnumerationMutationException *e) {
		@throw [OFEnumerationMutationException
		    exceptionWithObject: self];
	}
}
#endif

- (uint32_t)hash
{
	return [_mapTable hash];
}
@end

		if ((flags = fcntl(_epfd, F_GETFD, 0)) != -1)
			fcntl(_epfd, F_SETFD, flags | FD_CLOEXEC);
#endif

		_FDToEvents = [[OFMapTable alloc]
		    initWithKeyFunctions: mapFunctions
			 objectFunctions: mapFunctions];

		memset(&event, 0, sizeof(event));
		event.events = EPOLLIN;
		event.data.ptr = [OFNull null];

		if (epoll_ctl(_epfd, EPOLL_CTL_ADD, _cancelFD[0], &event) == -1)
			@throw [OFInitializationFailedException exception];

- (void)OF_addObject: (id)object
      fileDescriptor: (int)fd
	      events: (int)addEvents
{
	struct epoll_event event;
	intptr_t events;

	events = (intptr_t)[_FDToEvents
	    objectForKey: (void*)((intptr_t)fd + 1)];

	memset(&event, 0, sizeof(event));
	event.events = (int)events | addEvents;
	event.data.ptr = object;

	if (epoll_ctl(_epfd, (events == 0 ? EPOLL_CTL_ADD : EPOLL_CTL_MOD),
	    fd, &event) == -1)
		@throw [OFObserveFailedException exceptionWithObserver: self
								 errNo: errno];

	[_FDToEvents setObject: (void*)(events | addEvents)
			forKey: (void*)((intptr_t)fd + 1)];
}

- (void)OF_removeObject: (id)object
	 fileDescriptor: (int)fd
		 events: (int)removeEvents
{
	intptr_t events;

	events = (intptr_t)[_FDToEvents
	    objectForKey: (void*)((intptr_t)fd + 1)];
	events &= ~removeEvents;

	if (events == 0) {
		if (epoll_ctl(_epfd, EPOLL_CTL_DEL, fd, NULL) == -1)
			@throw [OFObserveFailedException
			    exceptionWithObserver: self
					    errNo: errno];

		[_FDToEvents removeObjectForKey: (void*)((intptr_t)fd + 1)];
	} else {
		struct epoll_event event;

		memset(&event, 0, sizeof(event));
		event.events = (int)events;
		event.data.ptr = object;

		if (epoll_ctl(_epfd, EPOLL_CTL_MOD, fd, &event) == -1)
			@throw [OFObserveFailedException
			    exceptionWithObserver: self
					    errNo: errno];

		[_FDToEvents setObject: (void*)events
				forKey: (void*)((intptr_t)fd + 1)];
	}
}

- (void)OF_addObjectForReading: (id <OFReadyForReadingObserving>)object
{
	[self OF_addObject: object
	    fileDescriptor: [object fileDescriptorForReading]

/*!
 * @struct of_map_table_functions_t OFMapTable.h ObjFW/OFMapTable.h
 *
 * @brief A struct describing the functions to be used by the map table.
 */
typedef struct {
	/// The function to retain keys / objects
	void *_Nonnull (*_Nullable retain)(void *object);
	/// The function to release keys / objects
	void (*_Nullable release)(void *object);
	/// The function to hash keys
	uint32_t (*_Nullable hash)(void *object);
	/// The function to compare keys / objects
	bool (*_Nullable equal)(void *object1, void *object2);
} of_map_table_functions_t;

#ifdef OF_HAVE_BLOCKS
/*!
 * @brief A block for enumerating an OFMapTable.
 *
 * @param key The current key
 * @param object The current object
 * @param stop A pointer to a variable that can be set to true to stop the
 *	       enumeration
 */
typedef void (^of_map_table_enumeration_block_t)(void *key, void *object,
    bool *stop);

/*!
 * @brief A block for replacing objects in an OFMapTable.
 *
 * @param key The key of the object to replace
 * @param object The object to replace
 * @return The object to replace the object with
 */
typedef void *_Nonnull (^of_map_table_replace_block_t)(void *key, void *object);
#endif

@class OFMapTableEnumerator;

/*!
 * @class OFMapTable OFMapTable.h ObjFW/OFMapTable.h
 *
 * @brief A class similar to OFDictionary, but providing more options how keys
 *	  and objects should be retained, released, compared and hashed.
 */
@interface OFMapTable: OFObject <OFCopying, OFFastEnumeration>
{
	of_map_table_functions_t _keyFunctions, _objectFunctions;
	struct of_map_table_bucket **_buckets;
	uint32_t _count, _capacity;
	uint8_t _rotate;
	unsigned long _mutations;
}

/*!
 * The key functions used by the map table.
 */
@property (readonly) of_map_table_functions_t keyFunctions;

/*!
 * The object functions used by the map table.
 */
@property (readonly) of_map_table_functions_t objectFunctions;

/*!
 * @brief Creates a new OFMapTable with the specified key and object functions.
 *
 * @param keyFunctions A structure of functions for handling keys
 * @param objectFunctions A structure of functions for handling objects
 * @return A new autoreleased OFMapTable
 */
+ (instancetype)mapTableWithKeyFunctions: (of_map_table_functions_t)keyFunctions
			 objectFunctions: (of_map_table_functions_t)
					      objectFunctions;

/*!
 * @brief Creates a new OFMapTable with the specified key functions, object
 *	  functions and capacity.
 *
 * @param keyFunctions A structure of functions for handling keys
 * @param objectFunctions A structure of functions for handling objects
 * @param capacity A hint about the count of elements expected to be in the map
 *	  table
 * @return A new autoreleased OFMapTable
 */
+ (instancetype)mapTableWithKeyFunctions: (of_map_table_functions_t)keyFunctions
			 objectFunctions: (of_map_table_functions_t)
					      objectFunctions
				capacity: (size_t)capacity;

/*!
 * @brief Initializes an already allocated OFMapTable with the specified key
 *	  and object functions.
 *
 * @param keyFunctions A structure of functions for handling keys
 * @param objectFunctions A structure of functions for handling objects
 * @return An initialized OFMapTable
 */
- initWithKeyFunctions: (of_map_table_functions_t)keyFunctions
       objectFunctions: (of_map_table_functions_t)objectFunctions;

/*!
 * @brief Initializes an already allocated OFMapTable with the specified key
 *	  functions, object functions and capacity.
 *
 * @param keyFunctions A structure of functions for handling keys
 * @param objectFunctions A structure of functions for handling objects
 * @param capacity A hint about the count of elements expected to be in the map
 *	  table
 * @return An initialized OFMapTable
 */
- initWithKeyFunctions: (of_map_table_functions_t)keyFunctions
       objectFunctions: (of_map_table_functions_t)objectFunctions
	      capacity: (size_t)capacity;

/*!
 * @brief Returns the number of objects in the map table.
 *
 * @return The number of objects in the map table
 */
- (size_t)count;

/*!
 * @brief Returns the object for the given key or NULL if the key was not found.
 *
 * @param key The key whose object should be returned
 * @return The object for the given key or NULL if the key was not found
 */
- (nullable void*)objectForKey: (void*)key;

/*!
 * @brief Sets an object for a key.
 *
 * @param key The key to set
 * @param object The object to set the key to
 */
- (void)setObject: (void*)object
	   forKey: (void*)key;

/*!
 * @brief Removes the object for the specified key from the map table.
 *
 * @param key The key whose object should be removed
 */
- (void)removeObjectForKey: (void*)key;

/*!
 * @brief Removes all objects.
 */
- (void)removeAllObjects;

/*!
 * @brief Checks whether the map table contains an object equal to the
 *	  specified object.
 *
 * @param object The object which is checked for being in the map table
 * @return A boolean whether the map table contains the specified object
*/
- (bool)containsObject: (nullable void*)object;

/*!
 * @brief Checks whether the map table contains an object with the specified
 *        address.
 *
 * @param object The object which is checked for being in the map table
 * @return A boolean whether the map table contains an object with the
 *	   specified address.
 */
- (bool)containsObjectIdenticalTo: (nullable void*)object;

/*!
 * @brief Returns an OFMapTableEnumerator to enumerate through the map table's
 *	  keys.
 *
 * @return An OFMapTableEnumerator to enumerate through the map table's keys
 */
- (OFMapTableEnumerator*)keyEnumerator;

/*!
 * @brief Returns an OFMapTableEnumerator to enumerate through the map table's
 *	  objects.
 *
 * @return An OFMapTableEnumerator to enumerate through the map table's objects
 */
- (OFMapTableEnumerator*)objectEnumerator;

#ifdef OF_HAVE_BLOCKS
/*!
 * @brief Executes a block for each key / object pair.
 *
 * @param block The block to execute for each key / object pair.
 */
- (void)enumerateKeysAndObjectsUsingBlock:
    (of_map_table_enumeration_block_t)block;

/*!
 * @brief Replaces each object with the object returned by the block.
 *
 * @param block The block which returns a new object for each object
 */
- (void)replaceObjectsUsingBlock: (of_map_table_replace_block_t)block;
#endif
@end

/*!
 * @class OFMapTableEnumerator OFMapTable.h ObjFW/OFMapTable.h
 *
 * @brief A class which provides methods to enumerate through an OFMapTable's
 *	  keys or objects.
 */
@interface OFMapTableEnumerator: OFObject
{
	OFMapTable *_mapTable;
	struct of_map_table_bucket **_buckets;
	uint32_t _capacity;
	unsigned long _mutations;
	unsigned long *_mutationsPtr;
	uint32_t _position;
}

/*!
 * @brief Returns the next object.
 *
 * @return The next object
 */
- (void*)nextObject;

/*!
 * @brief Resets the enumerator, so the next call to nextKey returns the first
 *	  key again.
 */
- (void)reset;
@end

OF_ASSUME_NONNULL_END

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

#define MIN_CAPACITY 16

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

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

static void
defaultRelease(void *object)
{
}

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

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

@interface OFMapTable ()
- (void)OF_setObject: (void*)object
	      forKey: (void*)key
		hash: (uint32_t)hash;
@end

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

@interface OFMapTableKeyEnumerator: OFMapTableEnumerator
@end

@interface OFMapTableObjectEnumerator: OFMapTableEnumerator
@end

@implementation OFMapTable
@synthesize keyFunctions = _keyFunctions, objectFunctions = _objectFunctions;

+ (instancetype)mapTableWithKeyFunctions: (of_map_table_functions_t)keyFunctions
			 objectFunctions: (of_map_table_functions_t)
					      objectFunctions
{
	return [[[self alloc]
	    initWithKeyFunctions: keyFunctions
		  objectFunctions: objectFunctions] autorelease];
}

+ (instancetype)mapTableWithKeyFunctions: (of_map_table_functions_t)keyFunctions
			 objectFunctions: (of_map_table_functions_t)
					      objectFunctions
				capacity: (size_t)capacity
{
	return [[[self alloc]
	    initWithKeyFunctions: keyFunctions
		 objectFunctions: objectFunctions
			capacity: capacity] autorelease];
}

- init
{
	OF_INVALID_INIT_METHOD
}

- initWithKeyFunctions: (of_map_table_functions_t)keyFunctions
       objectFunctions: (of_map_table_functions_t)objectFunctions
{
	return [self initWithKeyFunctions: keyFunctions
			  objectFunctions: objectFunctions
				 capacity: 0];
}

- initWithKeyFunctions: (of_map_table_functions_t)keyFunctions
       objectFunctions: (of_map_table_functions_t)objectFunctions
	      capacity: (size_t)capacity
{
	self = [super init];

	@try {
		_keyFunctions = keyFunctions;
		_objectFunctions = objectFunctions;

#define SET_DEFAULT(var, value) \
	if (var == NULL)	\
		var = value;

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

		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)
			@throw [OFOutOfRangeException exception];

}

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

	[super dealloc];
}

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

	if (![object isKindOfClass: [OFMapTable class]])
		return false;

	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++) {
		if (_buckets[i] != NULL && _buckets[i] != &deleted) {
			void *object =
			    [mapTable objectForKey: _buckets[i]->key];

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

	return true;
}

- (uint32_t)hash
{
	uint32_t hash = 0;

	for (uint32_t 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);
		}
	}

	return hash;
}

- 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] != &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;

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

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

	return NULL;
}

- (void)OF_resizeForCount: (uint32_t)count
{

	}

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

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

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

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

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

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

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

		bucket->hash = hash;

		_buckets[i] = bucket;
		_count++;

		return;
	}

	old = _buckets[i]->object;
	_buckets[i]->object = _objectFunctions.retain(object);
	_objectFunctions.release(old);
}

- (void)setObject: (void*)object
	   forKey: (void*)key
{
	[self OF_setObject: object
		    forKey: key
		      hash: _keyFunctions.hash(key)];
}

- (void)removeObjectForKey: (void*)key
{
	uint32_t 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]];
			_buckets[i] = &deleted;

			_count--;
			[self OF_resizeForCount: _count];

	for (i = 0; i < last && _buckets[i] != NULL; i++) {
		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]];
			_buckets[i] = &deleted;

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

			return;
		}
	}
}

- (void)removeAllObjects
{
	for (uint32_t 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]];
			_buckets[i] = NULL;
		}
	}

	_count = 0;

#elif defined(HAVE_RANDOM)
		_rotate = random() & 31;
#else
		_rotate = rand() & 31;
#endif
}

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

	for (uint32_t 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++)
		if (_buckets[i] != NULL && _buckets[i] != &deleted)
			if (_buckets[i]->object == object)
				return true;

	return false;
}

- (OFMapTableEnumerator*)keyEnumerator
{
	return [[[OFMapTableKeyEnumerator alloc]
	    OF_initWithMapTable: self
			buckets: _buckets
		       capacity: _capacity
	       mutationsPointer: &_mutations] autorelease];
}

- (OFMapTableEnumerator*)objectEnumerator
{
	return [[[OFMapTableObjectEnumerator alloc]
	    OF_initWithMapTable: self
			buckets: _buckets
		       capacity: _capacity
	       mutationsPointer: &_mutations] autorelease];
}

- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state

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

	return i;
}

#ifdef OF_HAVE_BLOCKS
- (void)enumerateKeysAndObjectsUsingBlock:
    (of_map_table_enumeration_block_t)block
{
	bool stop = false;
	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)
			block(_buckets[i]->key, _buckets[i]->object, &stop);
	}
}

- (void)replaceObjectsUsingBlock: (of_map_table_replace_block_t)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) {
			void *new;

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

			if (new != _buckets[i]->object) {
				_objectFunctions.release(_buckets[i]->object);
				_buckets[i]->object =
				    _objectFunctions.retain(new);
			}
		}
	}
}
#endif
@end

- (void)dealloc
{
	[_mapTable release];

	[super dealloc];
}

- (void*)nextObject
{
	OF_UNRECOGNIZED_SELECTOR
}

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

	_position = 0;
}
@end

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

	for (; _position < _capacity && (_buckets[_position] == NULL ||
	    _buckets[_position] == &deleted); _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++);

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

@implementation OFMapTable_EnumeratorWrapper
- initWithEnumerator: (OFMapTableEnumerator*)enumerator

}

- (id)nextObject
{
	id ret;

	@try {
		ret = [_enumerator nextObject];
	} @catch (OFEnumerationMutationException *e) {
		@throw [OFEnumerationMutationException
		    exceptionWithObject: _object];
	}

	return ret;
}

	if (self == [OFMutableDictionary_hashtable class])
		[self inheritMethodsFromClass: [OFDictionary_hashtable class]];
}

- (void)setObject: (id)object
	   forKey: (id)key
{
	[_mapTable setObject: object
		      forKey: key];
}

- (void)removeObjectForKey: (id)key
{
	[_mapTable removeObjectForKey: key];
}

- (void)removeAllObjects
{
	[_mapTable removeAllObjects];
}

#ifdef OF_HAVE_BLOCKS
- (void)replaceObjectsUsingBlock: (of_dictionary_replace_block_t)block
{
	@try {
		[_mapTable replaceObjectsUsingBlock:
		    ^ void* (void *key, void *object) {
			return block(key, object);
		}];
	} @catch (OFEnumerationMutationException *e) {
		@throw [OFEnumerationMutationException
		    exceptionWithObject: self];
	}
}
#endif

- (void)makeImmutable
{
	object_setClass(self, [OFDictionary_hashtable class]);
}
@end

{
	if (self == [OFMutableSet_hashtable class])
		[self inheritMethodsFromClass: [OFSet_hashtable class]];
}

- (void)addObject: (id)object
{
	[_mapTable setObject: (void*)1
		      forKey: object];
}

- (void)removeObject: (id)object
{
	[_mapTable removeObjectForKey: object];
}

- (void)makeImmutable
{
	object_setClass(self, [OFSet_hashtable class]);
}
@end

#import "OFApplication.h"
#import "OFArray.h"
#import "OFMapTable.h"

#import "OFInvalidArgumentException.h"

static uint32_t
stringHash(void *object)
{
	return [(OFString*)object hash];
}

static bool
stringEqual(void *object1, void *object2)
{
	return [(OFString*)object1 isEqual: (OFString*)object2];
}

@implementation OFOptionsParser
@synthesize lastOption = _lastOption, lastLongOption = _lastLongOption;
@synthesize argument = _argument;

+ (instancetype)parserWithOptions: (const of_options_parser_option_t*)options

		size_t count = 0;
		const of_options_parser_option_t *iter;
		of_options_parser_option_t *iter2;
		const of_map_table_functions_t keyFunctions = {
			.hash = stringHash,
			.equal = stringEqual
		};
		const of_map_table_functions_t objectFunctions = { NULL };

		/* Count, sanity check, initialize pointers */
		for (iter = options;
		    iter->shortOption != '\0' || iter->longOption != nil;
		    iter++) {
			if (iter->hasArgument < -1 || iter->hasArgument > 1)
				@throw [OFInvalidArgumentException exception];

				*iter->argumentPtr = nil;

			count++;
		}

		_longOptions = [[OFMapTable alloc]
		    initWithKeyFunctions: keyFunctions
			 objectFunctions: objectFunctions];
		_options = [self
		    allocMemoryWithSize: sizeof(*_options)
				  count: count + 1];

		for (iter = options, iter2 = _options;
		    iter->shortOption != '\0' || iter->longOption != nil;
		    iter++, iter2++) {
			iter2->shortOption = iter->shortOption;
			iter2->longOption = nil;
			iter2->hasArgument = iter->hasArgument;
			iter2->isSpecifiedPtr = iter->isSpecifiedPtr;
			iter2->argumentPtr = iter->argumentPtr;

			if (iter->longOption != nil) {
				@try {
					iter2->longOption =
					    [iter->longOption copy];

					if ([_longOptions objectForKey:
					    iter2->longOption] != NULL)
						@throw
						    [OFInvalidArgumentException
						    exception];

					[_longOptions
					    setObject: iter2
					       forKey: iter2->longOption];
				} @catch (id e) {
					/*
					 * Make sure we are in a consistent
					 * state where dealloc works.
					 */
					[iter2->longOption release];

				pos = [argument length];

			_lastLongOption = [[argument substringWithRange:
			    of_range(2, pos - 2)] copy];

			objc_autoreleasePoolPop(pool);

			option = [_longOptions objectForKey: _lastLongOption];
			if (option == NULL)
				return '?';

			if (option->hasArgument == 1 && _argument == nil)
				return ':';
			if (option->hasArgument == 0 && _argument != nil)
				return '=';

#import "OFString.h"
#import "OFXMLElement.h"

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

static void*
retain(void *object)
{
	return [(id)object retain];
}

static void
release(void *object)
{
	[(id)object release];
}

static uint32_t
hash(void *object)
{
	return [(id)object hash];
}

static bool
equal(void *object1, void *object2)
{
	return [(id)object1 isEqual: (id)object2];
}

static const of_map_table_functions_t keyFunctions = {
	.retain = retain,
	.release = release,
	.hash = hash,
	.equal = equal
};
static const of_map_table_functions_t objectFunctions = { NULL };

@implementation OFSet_hashtable
- init
{
	return [self initWithCapacity: 0];
}

- initWithCapacity: (size_t)capacity
{
	self = [super init];

	@try {
		_mapTable = [[OFMapTable alloc]
		    initWithKeyFunctions: keyFunctions
			 objectFunctions: objectFunctions
				capacity: capacity];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;

		@throw e;
	}

	self = [self initWithCapacity: count];

	@try {
		for (id object in set)
			[_mapTable setObject: (void*)1
				      forKey: object];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

		@throw e;
	}

	self = [self initWithCapacity: count];

	@try {
		for (id object in array)
			[_mapTable setObject: (void*)1
				      forKey: object];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- initWithObjects: (id const*)objects
	    count: (size_t)count
{
	self = [self initWithCapacity: count];

	@try {
		for (size_t i = 0; i < count; i++)
			[_mapTable setObject: (void*)1
				      forKey: objects[i]];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

		va_copy(argumentsCopy, arguments);

		for (count = 1; va_arg(argumentsCopy, id) != nil; count++);

		_mapTable = [[OFMapTable alloc]
		    initWithKeyFunctions: keyFunctions
			 objectFunctions: objectFunctions
				capacity: count];

		[_mapTable setObject: (void*)1
			      forKey: firstObject];

		while ((object = va_arg(arguments, id)) != nil)
			[_mapTable setObject: (void*)1
				      forKey: object];
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

		    ![[element namespace] isEqual: OF_SERIALIZATION_NS])
			@throw [OFInvalidArgumentException exception];

		for (OFXMLElement *child in
		    [element elementsForNamespace: OF_SERIALIZATION_NS]) {
			void *pool2  = objc_autoreleasePoolPush();

			[_mapTable setObject: (void*)1
				      forKey: [child objectByDeserializing]];

			objc_autoreleasePoolPop(pool2);
		}

		objc_autoreleasePoolPop(pool);
	} @catch (id e) {
		[self release];

}

- (bool)containsObject: (id)object
{
	if (object == nil)
		return false;

	return ([_mapTable objectForKey: object] != nil);
}

- (bool)isEqual: (id)object
{
	OFSet_hashtable *set;

	if (![object isKindOfClass: [OFSet_hashtable class]] &&

}

- (id)anyObject
{
	void *pool = objc_autoreleasePoolPush();
	id object;

	object = [[_mapTable keyEnumerator] nextObject];
	object = [object retain];

	objc_autoreleasePoolPop(pool);

	return [object autorelease];
}

						count: count];
}

#ifdef OF_HAVE_BLOCKS
- (void)enumerateObjectsUsingBlock: (of_set_enumeration_block_t)block
{
	@try {
		[_mapTable enumerateKeysAndObjectsUsingBlock:
		    ^ (void *key, void *object, bool *stop) {
			block(key, stop);
		}];
	} @catch (OFEnumerationMutationException *e) {
		@throw [OFEnumerationMutationException
		    exceptionWithObject: self];
	}
}
#endif
@end