ObjFW  Check-in [6f081c14f9]

		4B325EDF1605F3A0007836CA /* OFTimer.h in Headers */ = {isa = PBXBuildFile; fileRef = 4B325EDB1605F3A0007836CA /* OFTimer.h */; settings = {ATTRIBUTES = (Public, ); }; };
		4B325EE01605F3A0007836CA /* OFTimer.m in Sources */ = {isa = PBXBuildFile; fileRef = 4B325EDC1605F3A0007836CA /* OFTimer.m */; };
		4B39844213D3A24600E6F825 /* OFSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 4B39844013D3A24600E6F825 /* OFSet.h */; settings = {ATTRIBUTES = (Public, ); }; };
		4B39844313D3A24600E6F825 /* OFSet.m in Sources */ = {isa = PBXBuildFile; fileRef = 4B39844113D3A24600E6F825 /* OFSet.m */; };
		4B39844713D3AFB400E6F825 /* OFMutableSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 4B39844513D3AFB400E6F825 /* OFMutableSet.h */; settings = {ATTRIBUTES = (Public, ); }; };
		4B39844813D3AFB400E6F825 /* OFMutableSet.m in Sources */ = {isa = PBXBuildFile; fileRef = 4B39844613D3AFB400E6F825 /* OFMutableSet.m */; };
		4B39844A13D3D03000E6F825 /* OFSet.m in Sources */ = {isa = PBXBuildFile; fileRef = 4B39844913D3D03000E6F825 /* OFSet.m */; };
		4B3B0798166978780044E634 /* OFMapTable.h in Headers */ = {isa = PBXBuildFile; fileRef = 4B3B0796166978780044E634 /* OFMapTable.h */; settings = {ATTRIBUTES = (Public, ); }; };
		4B3B0799166978780044E634 /* OFMapTable.m in Sources */ = {isa = PBXBuildFile; fileRef = 4B3B0797166978780044E634 /* OFMapTable.m */; };
		4B3D238B1337FC0D00DD29B8 /* OFApplication.m in Sources */ = {isa = PBXBuildFile; fileRef = 4B175C1E116D130B003C99CB /* OFApplication.m */; };
		4B3D238C1337FC0D00DD29B8 /* OFArray.m in Sources */ = {isa = PBXBuildFile; fileRef = 4B67995B1099E7C50041064A /* OFArray.m */; };
		4B3D238D1337FC0D00DD29B8 /* OFAutoreleasePool.m in Sources */ = {isa = PBXBuildFile; fileRef = 4B67995D1099E7C50041064A /* OFAutoreleasePool.m */; };
		4B3D238E1337FC0D00DD29B8 /* OFBlock.m in Sources */ = {isa = PBXBuildFile; fileRef = 4BD86D811237A6C600ED9912 /* OFBlock.m */; };
		4B3D238F1337FC0D00DD29B8 /* OFConstantString.m in Sources */ = {isa = PBXBuildFile; fileRef = 4BE5F0D812DF4225005C7A0C /* OFConstantString.m */; };
		4B3D23901337FC0D00DD29B8 /* OFDataArray.m in Sources */ = {isa = PBXBuildFile; fileRef = 4B6799611099E7C50041064A /* OFDataArray.m */; };
		4B3D23911337FC0D00DD29B8 /* OFDataArray+Hashing.m in Sources */ = {isa = PBXBuildFile; fileRef = 4BE17ADA12FD746D002CEB0B /* OFDataArray+Hashing.m */; };

		4B325EDB1605F3A0007836CA /* OFTimer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFTimer.h; path = src/OFTimer.h; sourceTree = "<group>"; };
		4B325EDC1605F3A0007836CA /* OFTimer.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFTimer.m; path = src/OFTimer.m; sourceTree = "<group>"; };
		4B39844013D3A24600E6F825 /* OFSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFSet.h; path = src/OFSet.h; sourceTree = "<group>"; };
		4B39844113D3A24600E6F825 /* OFSet.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFSet.m; path = src/OFSet.m; sourceTree = "<group>"; };
		4B39844513D3AFB400E6F825 /* OFMutableSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFMutableSet.h; path = src/OFMutableSet.h; sourceTree = "<group>"; };
		4B39844613D3AFB400E6F825 /* OFMutableSet.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFMutableSet.m; path = src/OFMutableSet.m; sourceTree = "<group>"; };
		4B39844913D3D03000E6F825 /* OFSet.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFSet.m; path = tests/OFSet.m; sourceTree = "<group>"; };
		4B3B0796166978780044E634 /* OFMapTable.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFMapTable.h; path = src/OFMapTable.h; sourceTree = "<group>"; };
		4B3B0797166978780044E634 /* OFMapTable.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFMapTable.m; path = src/OFMapTable.m; sourceTree = "<group>"; };
		4B3D236D1337FB5800DD29B8 /* base64.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = base64.h; path = src/base64.h; sourceTree = "<group>"; };
		4B3D236E1337FB5800DD29B8 /* base64.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = base64.m; path = src/base64.m; sourceTree = "<group>"; };
		4B3D23701337FB7500DD29B8 /* OFHTTPRequestTests.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFHTTPRequestTests.m; path = tests/OFHTTPRequestTests.m; sourceTree = "<group>"; };
		4B3D23761337FBC800DD29B8 /* ObjFW.framework */ = {isa = PBXFileReference; explicitFileType = wrapper.framework; includeInIndex = 0; path = ObjFW.framework; sourceTree = BUILT_PRODUCTS_DIR; };
		4B3D23BB1337FC5800DD29B8 /* Info.plist */ = {isa = PBXFileReference; lastKnownFileType = text.plist.xml; path = Info.plist; sourceTree = SOURCE_ROOT; };
		4B3D23EF1338008000DD29B8 /* mach_alias_list */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; name = mach_alias_list; path = src/mach_alias_list; sourceTree = SOURCE_ROOT; };
		4B3D5693139A617D0010A78F /* OFSerializationTests.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFSerializationTests.m; path = tests/OFSerializationTests.m; sourceTree = "<group>"; };

				4B99251012E0780000215DBE /* OFHTTPRequest.m */,
				4BA49D8E13DB113B00381CDB /* OFIntrospection.h */,
				4BA49D8F13DB113B00381CDB /* OFIntrospection.m */,
				4BA02B9F15041F5900002F84 /* OFJSONRepresentation.h */,
				4B67996C1099E7C50041064A /* OFList.h */,
				4B67996D1099E7C50041064A /* OFList.m */,
				4B6743F9163C395900EB1E59 /* OFLocking.h */,
				4B3B0796166978780044E634 /* OFMapTable.h */,
				4B3B0797166978780044E634 /* OFMapTable.m */,
				4BF1BCC211C9663F0025511F /* OFMD5Hash.h */,
				4BF1BCC311C9663F0025511F /* OFMD5Hash.m */,
				4B67996F1099E7C50041064A /* OFMutableArray.h */,
				4B6799701099E7C50041064A /* OFMutableArray.m */,
				4B2B3E77140D430500EC2F7C /* OFMutableArray_adjacent.h */,
				4B2B3E78140D430500EC2F7C /* OFMutableArray_adjacent.m */,
				4B6799711099E7C50041064A /* OFMutableDictionary.h */,

				4B3D23C81337FCB000DD29B8 /* OFFile.h in Headers */,
				4B3D23C91337FCB000DD29B8 /* OFHash.h in Headers */,
				4B3D23CA1337FCB000DD29B8 /* OFHTTPRequest.h in Headers */,
				4BA49D9013DB113B00381CDB /* OFIntrospection.h in Headers */,
				4BA02BA115041F5900002F84 /* OFJSONRepresentation.h in Headers */,
				4B3D23CB1337FCB000DD29B8 /* OFList.h in Headers */,
				4B674402163C395900EB1E59 /* OFLocking.h in Headers */,
				4B3B0798166978780044E634 /* OFMapTable.h in Headers */,
				4B3D23CC1337FCB000DD29B8 /* OFMD5Hash.h in Headers */,
				4B3D23CD1337FCB000DD29B8 /* OFMutableArray.h in Headers */,
				4B3D23CE1337FCB000DD29B8 /* OFMutableDictionary.h in Headers */,
				4B39844713D3AFB400E6F825 /* OFMutableSet.h in Headers */,
				4B3D23CF1337FCB000DD29B8 /* OFMutableString.h in Headers */,
				4B674403163C395900EB1E59 /* OFMutex.h in Headers */,
				4B511B7C139C0A34003764A5 /* OFNull.h in Headers */,

				4B3D238B1337FC0D00DD29B8 /* OFApplication.m in Sources */,
				4B3D238C1337FC0D00DD29B8 /* OFArray.m in Sources */,
				4B2B3E7E140D430500EC2F7C /* OFArray_adjacent.m in Sources */,
				4B9BB7BE141CDE2D000AD1CC /* OFArray_adjacentSubarray.m in Sources */,
				4B9BB7C0141CDE2D000AD1CC /* OFArray_subarray.m in Sources */,
				4B3D238D1337FC0D00DD29B8 /* OFAutoreleasePool.m in Sources */,
				4B3D238E1337FC0D00DD29B8 /* OFBlock.m in Sources */,
				4B674401163C395900EB1E59 /* OFCondition.m in Sources */,
				4B3D238F1337FC0D00DD29B8 /* OFConstantString.m in Sources */,
				4B45355413DCFE1E0037AB4D /* OFCountedSet.m in Sources */,
				4BA85BCB140ECCE800E91D51 /* OFCountedSet_hashtable.m in Sources */,
				4B3D23901337FC0D00DD29B8 /* OFDataArray.m in Sources */,
				4B3D23911337FC0D00DD29B8 /* OFDataArray+Hashing.m in Sources */,
				4B3D23921337FC0D00DD29B8 /* OFDate.m in Sources */,
				4B3D23931337FC0D00DD29B8 /* OFDictionary.m in Sources */,
				4B2B3E80140D430500EC2F7C /* OFDictionary_hashtable.m in Sources */,
				4B3D23941337FC0D00DD29B8 /* OFEnumerator.m in Sources */,
				4B3D23961337FC0D00DD29B8 /* OFFile.m in Sources */,
				4B3D23971337FC0D00DD29B8 /* OFHash.m in Sources */,
				4B3D23981337FC0D00DD29B8 /* OFHTTPRequest.m in Sources */,
				4BA49D9113DB113B00381CDB /* OFIntrospection.m in Sources */,
				4B3D23991337FC0D00DD29B8 /* OFList.m in Sources */,
				4B3B0799166978780044E634 /* OFMapTable.m in Sources */,
				4B3D239A1337FC0D00DD29B8 /* OFMD5Hash.m in Sources */,
				4B3D239B1337FC0D00DD29B8 /* OFMutableArray.m in Sources */,
				4B2B3E82140D430500EC2F7C /* OFMutableArray_adjacent.m in Sources */,
				4B3D239C1337FC0D00DD29B8 /* OFMutableDictionary.m in Sources */,
				4B2B3E84140D430500EC2F7C /* OFMutableDictionary_hashtable.m in Sources */,
				4B39844813D3AFB400E6F825 /* OFMutableSet.m in Sources */,
				4BA85BCD140ECCE800E91D51 /* OFMutableSet_hashtable.m in Sources */,
				4B3D239D1337FC0D00DD29B8 /* OFMutableString.m in Sources */,
				4B552553147AA5DB0003BF47 /* OFMutableString_UTF8.m in Sources */,
				4B674404163C395900EB1E59 /* OFMutex.m in Sources */,
				4B511B7D139C0A34003764A5 /* OFNull.m in Sources */,
				4B3D239E1337FC0D00DD29B8 /* OFNumber.m in Sources */,
				4B3D239F1337FC0D00DD29B8 /* OFObject.m in Sources */,
				4BB25E89139C388A00F574EA /* OFObject+Serialization.m in Sources */,
				4B3D23A01337FC0D00DD29B8 /* OFPlugin.m in Sources */,
				4BB524C2143D1E4E0085FBCC /* OFProcess.m in Sources */,
				4B674406163C395900EB1E59 /* OFRecursiveMutex.m in Sources */,
				4B325EDE1605F3A0007836CA /* OFRunLoop.m in Sources */,
				4B3D23A11337FC0D00DD29B8 /* OFSeekableStream.m in Sources */,
				4B39844313D3A24600E6F825 /* OFSet.m in Sources */,
				4BA85BCF140ECCE800E91D51 /* OFSet_hashtable.m in Sources */,
				4B3D23A21337FC0D00DD29B8 /* OFSHA1Hash.m in Sources */,
				4B141BA515FCDF74000C21A8 /* OFSortedList.m in Sources */,
				4B3D23A31337FC0D00DD29B8 /* OFStream.m in Sources */,

				4B3D23AA1337FC0D00DD29B8 /* OFString+XMLUnescaping.m in Sources */,
				4B552555147AA5DB0003BF47 /* OFString_UTF8.m in Sources */,
				4B3D23AB1337FC0D00DD29B8 /* OFTCPSocket.m in Sources */,
				4BD653C6143B8489006182F0 /* OFTCPSocket+SOCKS5.m in Sources */,
				4B3D23AC1337FC0D00DD29B8 /* OFThread.m in Sources */,
				4B9361A91511000C00DCD16B /* OFThreadPool.m in Sources */,
				4B325EE01605F3A0007836CA /* OFTimer.m in Sources */,
				4B674408163C395900EB1E59 /* OFTLSKey.m in Sources */,
				4B3D23AD1337FC0D00DD29B8 /* OFURL.m in Sources */,
				4B3D23AE1337FC0D00DD29B8 /* OFXMLAttribute.m in Sources */,
				4B49EA6E143B3A090005BBC6 /* OFXMLCDATA.m in Sources */,
				4B49EA70143B3A090005BBC6 /* OFXMLCharacters.m in Sources */,
				4B49EA72143B3A090005BBC6 /* OFXMLComment.m in Sources */,
				4B3D23AF1337FC0D00DD29B8 /* OFXMLElement.m in Sources */,
				4BB25E8D139C388A00F574EA /* OFXMLElement+Serialization.m in Sources */,

				4B17FFB6133A375B003E6DCD /* OFUnboundNamespaceException.m in Sources */,
				4B17FFB2133A3664003E6DCD /* OFUnsupportedProtocolException.m in Sources */,
				4BA4846315CC9F1E00D75360 /* OFUnsupportedVersionException.m in Sources */,
				4B55A117133AC24600B58A93 /* OFWriteFailedException.m in Sources */,
				4B6743F2163C384A00EB1E59 /* OFLockFailedException.m in Sources */,
				4B6743F4163C384A00EB1E59 /* OFStillLockedException.m in Sources */,
				4B6743F6163C384A00EB1E59 /* OFUnlockFailedException.m in Sources */,




			);
			runOnlyForDeploymentPostprocessing = 0;
		};
		4BF33AEC133807310059CEF7 /* Sources */ = {
			isa = PBXSourcesBuildPhase;
			buildActionMask = 2147483647;
			files = (

       OFDictionary.m			\
       OFEnumerator.m			\
       OFFile.m				\
       OFHash.m				\
       OFHTTPRequest.m			\
       OFIntrospection.m		\
       OFList.m				\
       OFMapTable.m			\
       OFMD5Hash.m			\
       OFMutableArray.m			\
       OFMutableDictionary.m		\
       OFMutableSet.m			\
       OFMutableString.m		\
       OFNull.m				\
       OFNumber.m			\

/*
 * Copyright (c) 2008, 2009, 2010, 2011, 2012
 *   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.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.
 */

#import "OFObject.h"
#import "OFEnumerator.h"

/**
 * @brief A struct describing the functions to be used by the map table.
 */
typedef struct of_map_table_functions_t {
	/// The function to retain keys / values
	void* (*retain)(void *value);
	/// The function to release keys / values
	void (*release)(void *value);
	/// The function to hash keys
	uint32_t (*hash)(void *value);
	/// The function to compare keys / values
	BOOL (*equal)(void *value1, void *value2);
} of_map_table_functions_t;

#ifdef OF_HAVE_BLOCKS
typedef void (^of_map_table_enumeration_block_t)(void *key, void *value,
    BOOL *stop);
typedef void* (^of_map_table_replace_block_t)(void *key, void *value,
    BOOL *stop);
#endif

@class OFMapTableEnumerator;

/**
 * @brief A class similar to OFDictionary, but providing more options how keys
 *	  and values should be retained, released, compared and hashed.
 */
@interface OFMapTable: OFObject <OFCopying, OFFastEnumeration>
{
	of_map_table_functions_t keyFunctions, valueFunctions;
	struct of_map_table_bucket **buckets;
	uint32_t minCapacity, capacity, count;
	unsigned long mutations;
}

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

/*!
 * @brief Creates a new OFMapTable with the specified key functions, value
 *	  functions and capacity.
 *
 * @param keyFunctions A structure of functions for handling keys
 * @param valueFunctions A structure of functions for handling values
 * @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
			  valueFunctions: (of_map_table_functions_t)
					      valueFunctions
				capacity: (size_t)capacity;

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

/*!
 * @brief Initializes an already allocated OFMapTable with the specified key
 *	  functions, value functions and capacity.
 *
 * @param keyFunctions A structure of functions for handling keys
 * @param valueFunctions A structure of functions for handling values
 * @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
	valueFunctions: (of_map_table_functions_t)valueFunctions
	      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 value for the given key or nil if the key was not found.
 *
 * @param key The key whose object should be returned
 * @return The value for the given key or nil if the key was not found
 */
- (void*)valueForKey: (void*)key;

- (void)OF_setValue: (void*)value
	     forKey: (void*)key
	       hash: (uint32_t)hash;

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

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

/*!
 * @brief Checks whether the map table contains a value equal to the specified
 *	  value.
 *
 * @param value The value which is checked for being in the map table
 * @return A boolean whether the map table contains the specified value
*/
- (BOOL)containsValue: (void*)value;

/*!
 * @brief Checks whether the map table contains a value with the specified
 *        address.
 *
 * @param value The value which is checked for being in the map table
 * @return A boolean whether the map table contains a value with the specified
 *	   address.
 */
- (BOOL)containsValueIdenticalTo: (void*)value;

/*!
 * @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
 *	  values.
 *
 * @return An OFMapTableEnumerator to enumerate through the map table's values
 */
- (OFMapTableEnumerator*)valueEnumerator;

#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)enumerateKeysAndValuesUsingBlock:
    (of_map_table_enumeration_block_t)block;

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

/**
 * @brief Returns the key functions used by the map table.
 *
 * @return The key functions used by the map table
 */
- (of_map_table_functions_t)keyFunctions;

/**
 * @brief Returns the value functions used by the map table.
 *
 * @return The value functions used by the map table
 */
- (of_map_table_functions_t)valueFunctions;
@end

/*!
 * @brief A class which provides methods to enumerate through an OFMapTable's
 *	  keys or values.
 */
@interface OFMapTableEnumerator: OFObject
{
	OFMapTable *mapTable;
	struct of_map_table_bucket **buckets;
	uint32_t capacity;
	unsigned long mutations;
	unsigned long *mutationsPtr;
	uint32_t position;
}

- OF_initWithMapTable: (OFMapTable*)mapTable_
	      buckets: (struct of_map_table_bucket**)buckets_
	     capacity: (uint32_t)capacity_
     mutationsPointer: (unsigned long*)mutationsPtr_;

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

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

/*
 * Copyright (c) 2008, 2009, 2010, 2011, 2012
 *   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.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.
 */

#include "config.h"

#include <string.h>

#import "OFMapTable.h"
#import "OFEnumerator.h"

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

#import "macros.h"

#define MIN_CAPACITY 16

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

static void*
default_retain(void *value)
{
	return value;
}

static void
default_release(void *value)
{
}

static uint32_t
default_hash(void *value)
{
	return (uint32_t)(uintptr_t)value;
}

static BOOL
default_equal(void *value1, void *value2)
{
	return (value1 == value2);
}

@interface OFMapTableKeyEnumerator: OFMapTableEnumerator
@end

@interface OFMapTableValueEnumerator: OFMapTableEnumerator
@end

@implementation OFMapTable
+ (instancetype)mapTableWithKeyFunctions: (of_map_table_functions_t)keyFunctions
			  valueFunctions: (of_map_table_functions_t)
					      valueFunctions
{
	return [[[self alloc]
	    initWithKeyFunctions: keyFunctions
		  valueFunctions: valueFunctions] autorelease];
}

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

- init
{
	Class c = [self class];
	[self release];
	@throw [OFNotImplementedException exceptionWithClass: c
						    selector: _cmd];
}

- initWithKeyFunctions: (of_map_table_functions_t)keyFunctions_
	valueFunctions: (of_map_table_functions_t)valueFunctions_
{
	return [self initWithKeyFunctions: keyFunctions_
			   valueFunctions: valueFunctions_
				 capacity: 0];
}

- initWithKeyFunctions: (of_map_table_functions_t)keyFunctions_
	valueFunctions: (of_map_table_functions_t)valueFunctions_
	      capacity: (size_t)capacity_
{
	self = [super init];

	@try {
		keyFunctions = keyFunctions_;
		valueFunctions = valueFunctions_;

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

		SET_DEFAULT(keyFunctions.retain, default_retain);
		SET_DEFAULT(keyFunctions.release, default_release);
		SET_DEFAULT(keyFunctions.hash, default_hash);
		SET_DEFAULT(keyFunctions.equal, default_equal);

		SET_DEFAULT(valueFunctions.retain, default_retain);
		SET_DEFAULT(valueFunctions.release, default_release);
		SET_DEFAULT(valueFunctions.hash, default_hash);
		SET_DEFAULT(valueFunctions.equal, default_equal);

#undef SET_DEFAULT

		if (capacity_ > UINT32_MAX ||
		    capacity_ > UINT32_MAX / sizeof(*buckets) ||
		    capacity_ > UINT32_MAX / 8)
			@throw [OFOutOfRangeException
			    exceptionWithClass: [self class]];

		for (capacity = 1; capacity < capacity_; capacity <<= 1);
		if (capacity_ * 8 / capacity >= 6)
			capacity <<= 1;

		if (capacity < MIN_CAPACITY)
			capacity = MIN_CAPACITY;

		minCapacity = capacity;

		buckets = [self allocMemoryWithSize: sizeof(*buckets)
					      count: capacity];

		memset(buckets, 0, capacity * sizeof(*buckets));
	} @catch (id e) {
		[self release];
		@throw e;
	}

	return self;
}

- (void)dealloc
{
	uint32_t i;

	for (i = 0; i < capacity; i++) {
		if (buckets[i] != NULL && buckets[i] != &deleted) {
			keyFunctions.release(buckets[i]->key);
			valueFunctions.release(buckets[i]->value);
		}
	}

	[super dealloc];
}

- (BOOL)isEqual: (id)mapTable_
{
	OFMapTable *mapTable;
	uint32_t i;

	if (![mapTable_ isKindOfClass: [OFMapTable class]])
		return NO;

	mapTable = mapTable_;

	if (mapTable->count != count ||
	    mapTable->keyFunctions.equal != keyFunctions.equal ||
	    mapTable->valueFunctions.equal != valueFunctions.equal)
		return NO;

	for (i = 0; i < capacity; i++) {
		if (buckets[i] != NULL && buckets[i] != &deleted) {
			void *value = [mapTable valueForKey: buckets[i]->key];

			if (!valueFunctions.equal(value, buckets[i]->value))
				return NO;
		}
	}

	return YES;
}

- (uint32_t)hash
{
	uint32_t i, hash = 0;

	for (i = 0; i < capacity; i++) {
		if (buckets[i] != NULL && buckets[i] != &deleted) {
			hash += buckets[i]->hash;
			hash += valueFunctions.hash(buckets[i]->value);
		}
	}

	return hash;
}

- (id)copy
{
	OFMapTable *copy = [[OFMapTable alloc]
	    initWithKeyFunctions: keyFunctions
		  valueFunctions: valueFunctions
			capacity: capacity];

	@try {
		uint32_t i;

		for (i = 0; i < capacity; i++)
			if (buckets[i] != NULL && buckets[i] != &deleted)
				[copy OF_setValue: buckets[i]->value
					   forKey: buckets[i]->key
					     hash: buckets[i]->hash];
	} @catch (id e) {
		[copy release];
		@throw e;
	}

	copy->minCapacity = MIN_CAPACITY;

	return copy;
}

- (size_t)count
{
	return count;
}

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

	if (key == NULL)
		@throw [OFInvalidArgumentException
		    exceptionWithClass: [self class]
			      selector: _cmd];

	hash = keyFunctions.hash(key);
	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]->value;
	}

	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]->value;
	}

	return NULL;
}

- (void)OF_resizeForCount: (uint32_t)newCount
{
	uint32_t i, fullness, newCapacity;
	struct of_map_table_bucket **newBuckets;

	if (newCount > UINT32_MAX || newCount > UINT32_MAX / sizeof(*buckets) ||
	    newCount > UINT32_MAX / 8)
		@throw [OFOutOfRangeException exceptionWithClass: [self class]];

	fullness = newCount * 8 / capacity;

	if (fullness >= 6)
		newCapacity = capacity << 1;
	else if (fullness <= 1)
		newCapacity = capacity >> 1;
	else
		return;

	if (newCapacity < capacity && newCapacity < minCapacity)
		return;

	newBuckets = [self allocMemoryWithSize: sizeof(*newBuckets)
					 count: newCapacity];

	for (i = 0; i < newCapacity; i++)
		newBuckets[i] = NULL;

	for (i = 0; i < capacity; i++) {
		if (buckets[i] != NULL && buckets[i] != &deleted) {
			uint32_t j, last;

			last = newCapacity;

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

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

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

			if (j >= last) {
				[self freeMemory: newBuckets];
				@throw [OFOutOfRangeException
				    exceptionWithClass: [self class]];
			}

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

	[self freeMemory: buckets];
	buckets = newBuckets;
	capacity = newCapacity;
}

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

	if (key == NULL || value == NULL)
		@throw [OFInvalidArgumentException
		    exceptionWithClass: [self class]
			      selector: _cmd];

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

	/* In case the last bucket is already used */
	if (i >= last) {
		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))
				break;
		}
	}

	/* Key not in dictionary */
	if (i >= last || buckets[i] == NULL || buckets[i] == &deleted ||
	    !keyFunctions.equal(buckets[i]->key, key)) {
		struct of_map_table_bucket *bucket;

		[self OF_resizeForCount: count + 1];

		mutations++;
		last = capacity;

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

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

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

		if (i >= last)
			@throw [OFOutOfRangeException
			    exceptionWithClass: [self class]];

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

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

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

		bucket->hash = hash;

		buckets[i] = bucket;
		count++;

		return;
	}

	old = buckets[i]->value;
	buckets[i]->value = valueFunctions.retain(value);
	valueFunctions.release(old);
}

- (void)setValue: (void*)value
	  forKey: (void*)key
{
	[self OF_setValue: value
		   forKey: key
		     hash: keyFunctions.hash(key)];
}

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

	if (key == NULL)
		@throw [OFInvalidArgumentException
		    exceptionWithClass: [self class]
			      selector: _cmd];

	hash = keyFunctions.hash(key);
	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)) {
			keyFunctions.release(buckets[i]->key);
			valueFunctions.release(buckets[i]->value);

			[self freeMemory: buckets[i]];
			buckets[i] = &deleted;

			count--;
			mutations++;
			[self OF_resizeForCount: 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)
			continue;

		if (keyFunctions.equal(buckets[i]->key, key)) {
			keyFunctions.release(buckets[i]->key);
			valueFunctions.release(buckets[i]->value);

			[self freeMemory: buckets[i]];
			buckets[i] = &deleted;

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

			return;
		}
	}
}

- (BOOL)containsValue: (void*)value
{
	uint32_t i;

	if (value == NULL || count == 0)
		return NO;

	for (i = 0; i < capacity; i++)
		if (buckets[i] != NULL && buckets[i] != &deleted)
			if (valueFunctions.equal(buckets[i]->value, value))
				return YES;

	return NO;
}

- (BOOL)containsValueIdenticalTo: (void*)value
{
	uint32_t i;

	if (value == NULL || count == 0)
		return NO;

	for (i = 0; i < capacity; i++)
		if (buckets[i] != NULL && buckets[i] != &deleted)
			if (buckets[i]->value == value)
				return YES;

	return NO;
}

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

- (OFMapTableEnumerator*)valueEnumerator
{
	return [[[OFMapTableValueEnumerator alloc]
	    OF_initWithMapTable: self
			buckets: buckets
		       capacity: capacity
	       mutationsPointer: &mutations] autorelease];
}

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

	for (i = 0; i < count_; i++) {
		for (; j < capacity && (buckets[j] == NULL ||
		    buckets[j] == &deleted); j++);

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

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

	return i;
}

#ifdef OF_HAVE_BLOCKS
- (void)enumerateKeysAndValuesUsingBlock:
    (of_map_table_enumeration_block_t)block
{
	size_t i;
	BOOL stop = NO;
	unsigned long mutations_ = mutations;

	for (i = 0; i < capacity && !stop; i++) {
		if (mutations != mutations_)
			@throw [OFEnumerationMutationException
			    exceptionWithClass: [self class]
					object: self];

		if (buckets[i] != NULL && buckets[i] != &deleted)
			block(buckets[i]->key, buckets[i]->value, &stop);
	}
}

- (void)replaceValuesUsingBlock: (of_map_table_replace_block_t)block
{
	size_t i;
	BOOL stop = NO;
	unsigned long mutations_ = mutations;

	for (i = 0; i < capacity && !stop; i++) {
		if (mutations != mutations_)
			@throw [OFEnumerationMutationException
			    exceptionWithClass: [self class]
					object: self];

		if (buckets[i] != NULL && buckets[i] != &deleted) {
			void *old, *new;

			new = block(buckets[i]->key, buckets[i]->value, &stop);
			if (new == NULL)
				@throw [OFInvalidArgumentException
				    exceptionWithClass: [self class]
					      selector: _cmd];

			old = buckets[i]->value;
			buckets[i]->value = valueFunctions.retain(new);
			valueFunctions.release(old);
		}
	}
}
#endif

- (of_map_table_functions_t)keyFunctions
{
	return keyFunctions;
}

- (of_map_table_functions_t)valueFunctions
{
	return valueFunctions;
}
@end

@implementation OFMapTableEnumerator
- init
{
	Class c = [self class];
	[self release];
	@throw [OFNotImplementedException exceptionWithClass: c
						    selector: _cmd];
}

- OF_initWithMapTable: (OFMapTable*)mapTable_
	      buckets: (struct of_map_table_bucket**)buckets_
	     capacity: (uint32_t)capacity_
     mutationsPointer: (unsigned long*)mutationsPtr_
{
	self = [super init];

	mapTable = [mapTable_ retain];
	buckets = buckets_;
	capacity = capacity_;
	mutations = *mutationsPtr_;
	mutationsPtr = mutationsPtr_;

	return self;
}

- (void)dealloc
{
	[mapTable release];

	[super dealloc];
}

- (void*)nextValue
{
	@throw [OFNotImplementedException exceptionWithClass: [self class]
						    selector: _cmd];
}

- (void)reset
{
	if (*mutationsPtr != mutations)
		@throw [OFEnumerationMutationException
		    exceptionWithClass: [mapTable class]
				object: mapTable];

	position = 0;
}
@end

@implementation OFMapTableKeyEnumerator
- (void*)nextValue
{
	if (*mutationsPtr != mutations)
		@throw [OFEnumerationMutationException
		    exceptionWithClass: [mapTable class]
				object: mapTable];

	for (; position < capacity && (buckets[position] == NULL ||
	    buckets[position] == &deleted); position++);

	if (position < capacity)
		return buckets[position++]->key;
	else
		return NULL;
}
@end

@implementation OFMapTableValueEnumerator
- (void*)nextValue
{
	if (*mutationsPtr != mutations)
		@throw [OFEnumerationMutationException
		    exceptionWithClass: [mapTable class]
				object: mapTable];

	for (; position < capacity && (buckets[position] == NULL ||
	    buckets[position] == &deleted); position++);

	if (position < capacity)
		return buckets[position++]->value;
	else
		return NULL;
}
@end

#import "OFObject.h"
#import "OFBlock.h"

#import "OFAutoreleasePool.h"
#import "OFString.h"

#import "OFArray.h"
#import "OFDataArray.h"

#import "OFList.h"
#import "OFSortedList.h"

#import "OFDictionary.h"
#import "OFMapTable.h"

#import "OFSet.h"
#import "OFCountedSet.h"

#import "OFEnumerator.h"

#import "OFNull.h"