Index: ObjFW.xcodeproj/project.pbxproj ================================================================== --- ObjFW.xcodeproj/project.pbxproj +++ ObjFW.xcodeproj/project.pbxproj @@ -150,10 +150,12 @@ 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 */; }; @@ -563,10 +565,12 @@ 4B39844013D3A24600E6F825 /* OFSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFSet.h; path = src/OFSet.h; sourceTree = ""; }; 4B39844113D3A24600E6F825 /* OFSet.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFSet.m; path = src/OFSet.m; sourceTree = ""; }; 4B39844513D3AFB400E6F825 /* OFMutableSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFMutableSet.h; path = src/OFMutableSet.h; sourceTree = ""; }; 4B39844613D3AFB400E6F825 /* OFMutableSet.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFMutableSet.m; path = src/OFMutableSet.m; sourceTree = ""; }; 4B39844913D3D03000E6F825 /* OFSet.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFSet.m; path = tests/OFSet.m; sourceTree = ""; }; + 4B3B0796166978780044E634 /* OFMapTable.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = OFMapTable.h; path = src/OFMapTable.h; sourceTree = ""; }; + 4B3B0797166978780044E634 /* OFMapTable.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFMapTable.m; path = src/OFMapTable.m; sourceTree = ""; }; 4B3D236D1337FB5800DD29B8 /* base64.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = base64.h; path = src/base64.h; sourceTree = ""; }; 4B3D236E1337FB5800DD29B8 /* base64.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = base64.m; path = src/base64.m; sourceTree = ""; }; 4B3D23701337FB7500DD29B8 /* OFHTTPRequestTests.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; name = OFHTTPRequestTests.m; path = tests/OFHTTPRequestTests.m; sourceTree = ""; }; 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; }; @@ -1089,10 +1093,12 @@ 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 */, @@ -1351,10 +1357,11 @@ 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 */, @@ -1676,10 +1683,11 @@ 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 */, @@ -1690,25 +1698,28 @@ 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 */, @@ -1730,10 +1741,11 @@ 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 */, @@ -1801,14 +1813,10 @@ 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 */, - 4B674401163C395900EB1E59 /* OFCondition.m in Sources */, - 4B674404163C395900EB1E59 /* OFMutex.m in Sources */, - 4B674406163C395900EB1E59 /* OFRecursiveMutex.m in Sources */, - 4B674408163C395900EB1E59 /* OFTLSKey.m in Sources */, ); runOnlyForDeploymentPostprocessing = 0; }; 4BF33AEC133807310059CEF7 /* Sources */ = { isa = PBXSourcesBuildPhase; Index: src/Makefile ================================================================== --- src/Makefile +++ src/Makefile @@ -22,10 +22,11 @@ OFFile.m \ OFHash.m \ OFHTTPRequest.m \ OFIntrospection.m \ OFList.m \ + OFMapTable.m \ OFMD5Hash.m \ OFMutableArray.m \ OFMutableDictionary.m \ OFMutableSet.m \ OFMutableString.m \ ADDED src/OFMapTable.h Index: src/OFMapTable.h ================================================================== --- src/OFMapTable.h +++ src/OFMapTable.h @@ -0,0 +1,239 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011, 2012 + * Jonathan Schleifer + * + * 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 +{ + 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 ADDED src/OFMapTable.m Index: src/OFMapTable.m ================================================================== --- src/OFMapTable.m +++ src/OFMapTable.m @@ -0,0 +1,709 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011, 2012 + * Jonathan Schleifer + * + * 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 + +#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 Index: src/ObjFW.h ================================================================== --- src/ObjFW.h +++ src/ObjFW.h @@ -20,17 +20,18 @@ #import "OFBlock.h" #import "OFAutoreleasePool.h" #import "OFString.h" -#import "OFDataArray.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"