Index: src/Makefile ================================================================== --- src/Makefile +++ src/Makefile @@ -16,10 +16,11 @@ OFCountedSet.m \ OFDataArray.m \ OFDataArray+Hashing.m \ OFDate.m \ OFDictionary.m \ + OFDictionary_hashtable.m \ OFDoubleMatrix.m \ OFDoubleVector.m \ OFEnumerator.m \ OFFile.m \ OFFloatMatrix.m \ @@ -30,10 +31,11 @@ OFList.m \ OFMD5Hash.m \ OFMutableArray.m \ OFMutableArray_adjacent.m \ OFMutableDictionary.m \ + OFMutableDictionary_hashtable.m \ OFMutableSet.m \ OFMutableString.m \ OFNull.m \ OFNumber.m \ OFObject.m \ Index: src/OFArray.h ================================================================== --- src/OFArray.h +++ src/OFArray.h @@ -30,11 +30,11 @@ typedef id (^of_array_map_block_t)(id object, size_t index); typedef id (^of_array_fold_block_t)(id left, id right); #endif /** - * \brief A class for storing objects in an array. + * \brief An abstract class for storing objects in an array. */ @interface OFArray: OFObject /** * \brief Creates a new OFArray. Index: src/OFArray.m ================================================================== --- src/OFArray.m +++ src/OFArray.m @@ -162,10 +162,23 @@ length: (size_t)length { return [[[self alloc] initWithCArray: objects length: length] autorelease]; } + +- init +{ + if ([self class] == [OFArray class] || + [self class] == [OFMutableArray class]) { + Class c = isa; + [self release]; + @throw [OFNotImplementedException newWithClass: c + selector: _cmd]; + } + + return [super init]; +} - initWithObject: (id)object { return [self initWithObjects: object, nil]; } Index: src/OFCountedSet.m ================================================================== --- src/OFCountedSet.m +++ src/OFCountedSet.m @@ -17,11 +17,11 @@ #include "config.h" #define OF_COUNTED_SET_M #import "OFCountedSet.h" -#import "OFDictionary.h" +#import "OFMutableDictionary_hashtable.h" #import "OFNumber.h" #import "OFArray.h" #import "OFString.h" #import "OFAutoreleasePool.h" @@ -31,11 +31,11 @@ self = [super init]; @try { [dictionary release]; dictionary = nil; - dictionary = [[OFMutableDictionary alloc] + dictionary = [[OFMutableDictionary_hashtable alloc] _initWithDictionary: set->dictionary copyKeys: NO]; } @catch (id e) { [self release]; @throw e; Index: src/OFDictionary.h ================================================================== --- src/OFDictionary.h +++ src/OFDictionary.h @@ -28,31 +28,18 @@ BOOL *stop); typedef BOOL (^of_dictionary_filter_block_t)(id key, id object); typedef id (^of_dictionary_map_block_t)(id key, id object); #endif -struct of_dictionary_bucket -{ - id key; - id object; - uint32_t hash; -}; - /** - * \brief A class for storing objects in a hash table. + * \brief An abstract class for storing objects in a dictionary. * * Note: Fast enumeration on a dictionary enumerates through the keys of the * dictionary. */ @interface OFDictionary: OFObject -{ - struct of_dictionary_bucket **data; - uint32_t size; - size_t count; -} - /** * \brief Creates a new OFDictionary. * * \return A new autoreleased OFDictionary */ @@ -228,36 +215,9 @@ - _initWithDictionary: (OFDictionary*)dictionary copyKeys: (BOOL)copyKeys; #endif @end -@interface OFDictionaryEnumerator: OFEnumerator -{ - OFDictionary *dictionary; - struct of_dictionary_bucket **data; - uint32_t size; - unsigned long mutations; - unsigned long *mutationsPtr; - uint32_t pos; -} - -- initWithDictionary: (OFDictionary*)dictionary - data: (struct of_dictionary_bucket**)data - size: (uint32_t)size - mutationsPointer: (unsigned long*)mutationsPtr; -@end - -@interface OFDictionaryObjectEnumerator: OFDictionaryEnumerator -@end - -@interface OFDictionaryKeyEnumerator: OFDictionaryEnumerator +@interface OFDictionary_placeholder: OFDictionary @end #import "OFMutableDictionary.h" - -#ifdef __cplusplus -extern "C" { -#endif -extern struct of_dictionary_bucket of_dictionary_deleted_bucket; -#ifdef __cplusplus -} -#endif Index: src/OFDictionary.m ================================================================== --- src/OFDictionary.m +++ src/OFDictionary.m @@ -14,33 +14,116 @@ * file. */ #include "config.h" -#include - #include #import "OFDictionary.h" -#import "OFEnumerator.h" +#import "OFDictionary_hashtable.h" #import "OFArray.h" #import "OFString.h" #import "OFXMLElement.h" #import "OFAutoreleasePool.h" -#import "OFEnumerationMutationException.h" -#import "OFInvalidArgumentException.h" -#import "OFInvalidFormatException.h" -#import "OFOutOfRangeException.h" +#import "OFNotImplementedException.h" #import "macros.h" -struct of_dictionary_bucket of_dictionary_deleted_bucket = {}; +static struct { + Class isa; +} placeholder; -#define DELETED &of_dictionary_deleted_bucket +@implementation OFDictionary_placeholder +- init +{ + return (id)[[OFDictionary_hashtable alloc] init]; +} + +- initWithDictionary: (OFDictionary*)dictionary +{ + return (id)[[OFDictionary_hashtable alloc] + initWithDictionary: dictionary]; +} + +- initWithObject: (id)object + forKey: (id )key +{ + return (id)[[OFDictionary_hashtable alloc] initWithObject: object + forKey: key]; +} + +- initWithObjects: (OFArray*)objects + forKeys: (OFArray*)keys +{ + return (id)[[OFDictionary_hashtable alloc] initWithObjects: objects + forKeys: keys]; +} + +- initWithKeysAndObjects: (id )firstKey, ... +{ + id ret; + va_list arguments; + + va_start(arguments, firstKey); + ret = [[OFDictionary_hashtable alloc] initWithKey: firstKey + arguments: arguments]; + va_end(arguments); + + return ret; +} + +- initWithKey: (id )firstKey + arguments: (va_list)arguments +{ + return (id)[[OFDictionary_hashtable alloc] initWithKey: firstKey + arguments: arguments]; +} + +- initWithSerialization: (OFXMLElement*)element +{ + return (id)[[OFDictionary_hashtable alloc] + initWithSerialization: element]; +} + +- retain +{ + return self; +} + +- autorelease +{ + return self; +} + +- (void)release +{ +} + +- (void)dealloc +{ + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; + [super dealloc]; /* Get rid of a stupid warning */ +} +@end @implementation OFDictionary ++ (void)initialize +{ + if (self == [OFDictionary class]) + placeholder.isa = [OFDictionary_placeholder class]; +} + ++ alloc +{ + if (self == [OFDictionary class]) + return (id)&placeholder; + + return [super alloc]; +} + + dictionary { return [[[self alloc] init] autorelease]; } @@ -76,247 +159,42 @@ return ret; } - init { - self = [super init]; - - @try { - data = [self allocMemoryWithSize: - sizeof(struct of_dictionary_bucket)]; - size = 1; - data[0] = NULL; - } @catch (id e) { - [self release]; - @throw e; - } - - return self; -} - -- _initWithDictionary: (OFDictionary*)dictionary - copyKeys: (BOOL)copyKeys -{ - self = [super init]; - - @try { - uint32_t i; - - if (dictionary == nil) - @throw [OFInvalidArgumentException newWithClass: isa - selector: _cmd]; - - data = [self allocMemoryForNItems: dictionary->size - withSize: sizeof(*data)]; - - for (i = 0; i < dictionary->size; i++) - data[i] = NULL; - - size = dictionary->size; - count = dictionary->count; - - for (i = 0; i < size; i++) { - id key; - struct of_dictionary_bucket *bucket; - - if (dictionary->data[i] == NULL || - dictionary->data[i] == DELETED) - continue; - - bucket = [self allocMemoryWithSize: sizeof(*bucket)]; - key = (copyKeys - ? [dictionary->data[i]->key copy] - : [dictionary->data[i]->key retain]); - - @try { - [dictionary->data[i]->object retain]; - } @catch (id e) { - [key release]; - @throw e; - } - - bucket->key = key; - bucket->object = dictionary->data[i]->object; - bucket->hash = dictionary->data[i]->hash; - - data[i] = bucket; - } - } @catch (id e) { - [self release]; - @throw e; - } - - return self; + if ([self class] == [OFDictionary class] || + [self class] == [OFMutableDictionary class]) { + Class c = isa; + [self release]; + @throw [OFNotImplementedException newWithClass: c + selector: _cmd]; + } + + return [super init]; } - initWithDictionary: (OFDictionary*)dictionary { - return [self _initWithDictionary: dictionary - copyKeys: YES]; + Class c = isa; + [self release]; + @throw [OFNotImplementedException newWithClass: c + selector: _cmd]; } - initWithObject: (id)object forKey: (id )key { - self = [super init]; - - @try { - uint32_t i; - struct of_dictionary_bucket *bucket; - - if (key == nil || object == nil) - @throw [OFInvalidArgumentException newWithClass: isa - selector: _cmd]; - - data = [self allocMemoryForNItems: 2 - withSize: sizeof(*data)]; - - size = 2; - for (i = 0; i < size; i++) - data[i] = NULL; - - i = [key hash] & 1; - bucket = [self allocMemoryWithSize: sizeof(*bucket)]; - key = [key copy]; - - @try { - [object retain]; - } @catch (id e) { - [key release]; - @throw e; - } - - bucket->key = key; - bucket->object = object; - bucket->hash = [key hash]; - - data[i] = bucket; - count = 1; - } @catch (id e) { - [self release]; - @throw e; - } - - return self; + return [self initWithKeysAndObjects: key, object, nil]; } - initWithObjects: (OFArray*)objects forKeys: (OFArray*)keys { - self = [super init]; - - @try { - id *objectsCArray, *keysCArray; - uint32_t i, j, newSize; - - keysCArray = [keys cArray]; - objectsCArray = [objects cArray]; - count = [keys count]; - - if (count > UINT32_MAX) - @throw [OFOutOfRangeException newWithClass: isa]; - - for (newSize = 1; newSize < count; newSize <<= 1); - - if (newSize == 0) - @throw [OFOutOfRangeException newWithClass: isa]; - - data = [self allocMemoryForNItems: newSize - withSize: sizeof(*data)]; - - for (j = 0; j < newSize; j++) - data[j] = NULL; - - size = newSize; - - for (i = 0; i < count; i++) { - uint32_t hash, last; - - hash = [keysCArray[i] hash]; - last = size; - - for (j = hash & (size - 1); j < last && data[j] != NULL; - j++) - if ([data[j]->key isEqual: keysCArray[i]]) - break; - - /* In case the last bucket is already used */ - if (j >= last) { - last = hash & (size - 1); - - for (j = 0; j < last && data[j] != NULL; j++) - if ([data[j]->key - isEqual: keysCArray[i]]) - break; - } - - /* Key not in dictionary */ - if (j >= last || data[j] == NULL || - ![data[j]->key isEqual: keysCArray[i]]) { - struct of_dictionary_bucket *bucket; - id key; - - last = size; - - j = hash & (size - 1); - for (; j < last && data[j] != NULL; j++); - - /* In case the last bucket is already used */ - if (j >= last) { - last = hash & (size - 1); - - for (j = 0; j < last && data[j] != NULL; - j++); - } - - if (j >= last) - @throw [OFOutOfRangeException - newWithClass: isa]; - - bucket = - [self allocMemoryWithSize: sizeof(*bucket)]; - key = [keysCArray[i] copy]; - - @try { - [objectsCArray[i] retain]; - } @catch (id e) { - [key release]; - @throw e; - } - - bucket->key = key; - bucket->object = objectsCArray[i]; - bucket->hash = hash; - - data[j] = bucket; - - continue; - } - - /* - * The key is already in the dictionary. However, we - * just replace it so that the programmer gets the same - * behavior as if he'd call setObject:forKey: for each - * key/object pair. - */ - [objectsCArray[i] retain]; - - @try { - [data[j]->object release]; - } @catch (id e) { - [objectsCArray[i] release]; - @throw e; - } - - data[j]->object = objectsCArray[i]; - } - } @catch (id e) { - [self release]; - @throw e; - } - - return self; + Class c = isa; + [self release]; + @throw [OFNotImplementedException newWithClass: c + selector: _cmd]; } - initWithKeysAndObjects: (id )firstKey, ... { id ret; @@ -331,262 +209,34 @@ } - initWithKey: (id )firstKey arguments: (va_list)arguments { - self = [super init]; - - @try { - id key, object; - uint32_t i, j, hash, newSize; - va_list argumentsCopy; - struct of_dictionary_bucket *bucket; - - va_copy(argumentsCopy, arguments); - - if (firstKey == nil) - @throw [OFInvalidArgumentException newWithClass: isa - selector: _cmd]; - - key = firstKey; - - if ((object = va_arg(arguments, id)) == nil) - @throw [OFInvalidArgumentException newWithClass: isa - selector: _cmd]; - - count = 1; - for (; va_arg(argumentsCopy, id) != nil; count++); - count >>= 1; - - if (count > UINT32_MAX) - @throw [OFOutOfRangeException newWithClass: isa]; - - for (newSize = 1; newSize < count; newSize <<= 1); - - if (newSize == 0) - @throw [OFOutOfRangeException newWithClass: isa]; - - data = [self allocMemoryForNItems: newSize - withSize: sizeof(*data)]; - - for (j = 0; j < newSize; j++) - data[j] = NULL; - - size = newSize; - - /* Add first key / object pair */ - hash = [key hash]; - j = hash & (size - 1); - - bucket = [self allocMemoryWithSize: sizeof(*bucket)]; - key = [key copy]; - - @try { - [object retain]; - } @catch (id e) { - [key release]; - @throw e; - } - - bucket->key = key; - bucket->object = object; - bucket->hash = hash; - - data[j] = bucket; - - for (i = 1; i < count; i++) { - uint32_t last; - - key = va_arg(arguments, id ); - object = va_arg(arguments, id); - - if (key == nil || object == nil) - @throw [OFInvalidArgumentException - newWithClass: isa - selector: _cmd]; - - hash = [key hash]; - last = size; - - for (j = hash & (size - 1); j < last && data[j] != NULL; - j++) - if ([data[j]->key isEqual: key]) - break; - - /* In case the last bucket is already used */ - if (j >= last) { - last = hash & (size - 1); - - for (j = 0; j < last && data[j] != NULL; j++) - if ([data[j]->key isEqual: key]) - break; - } - - /* Key not in dictionary */ - if (j >= last || data[j] == NULL || - ![data[j]->key isEqual: key]) { - last = size; - - j = hash & (size - 1); - for (; j < last && data[j] != NULL; j++); - - /* In case the last bucket is already used */ - if (j >= last) { - last = hash & (size - 1); - - for (j = 0; j < last && data[j] != NULL; - j++); - } - - if (j >= last) - @throw [OFOutOfRangeException - newWithClass: isa]; - - bucket = - [self allocMemoryWithSize: sizeof(*bucket)]; - key = [key copy]; - - @try { - [object retain]; - } @catch (id e) { - [key release]; - @throw e; - } - - bucket->key = key; - bucket->object = object; - bucket->hash = hash; - - data[j] = bucket; - - continue; - } - - /* - * The key is already in the dictionary. However, we - * just replace it so that the programmer gets the same - * behavior as if he'd call setObject:forKey: for each - * key/object pair. - */ - [object retain]; - - @try { - [data[j]->object release]; - } @catch (id e) { - [object release]; - @throw e; - } - - data[j]->object = object; - count--; - } - } @catch (id e) { - [self release]; - @throw e; - } - - return self; + Class c = isa; + [self release]; + @throw [OFNotImplementedException newWithClass: c + selector: _cmd]; } - initWithSerialization: (OFXMLElement*)element { - @try { - OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; - OFAutoreleasePool *pool2; - OFMutableDictionary *dictionary; - OFArray *keys, *objects; - OFEnumerator *keyEnumerator, *objectEnumerator; - OFXMLElement *keyElement, *objectElement; - - if (![[element name] isEqual: [self className]] || - ![[element namespace] isEqual: OF_SERIALIZATION_NS]) - @throw [OFInvalidArgumentException newWithClass: isa - selector: _cmd]; - - dictionary = [OFMutableDictionary dictionary]; - - keys = [element elementsForName: @"key" - namespace: OF_SERIALIZATION_NS]; - objects = [element elementsForName: @"object" - namespace: OF_SERIALIZATION_NS]; - - if ([keys count] != [objects count]) - @throw [OFInvalidFormatException newWithClass: isa]; - - keyEnumerator = [keys objectEnumerator]; - objectEnumerator = [objects objectEnumerator]; - pool2 = [[OFAutoreleasePool alloc] init]; - - while ((keyElement = [keyEnumerator nextObject]) != nil && - (objectElement = [objectEnumerator nextObject]) != nil) { - OFXMLElement *key, *object; - - key = [[keyElement elementsForNamespace: - OF_SERIALIZATION_NS] firstObject]; - object = [[objectElement elementsForNamespace: - OF_SERIALIZATION_NS] firstObject]; - - if (key == nil || object == nil) - @throw [OFInvalidFormatException - newWithClass: isa]; - - [dictionary setObject: [object objectByDeserializing] - forKey: [key objectByDeserializing]]; - - [pool2 releaseObjects]; - } - - self = [self initWithDictionary: dictionary]; - - [pool release]; - } @catch (id e) { - [self release]; - @throw e; - } - - return self; + Class c = isa; + [self release]; + @throw [OFNotImplementedException newWithClass: c + selector: _cmd]; } - (id)objectForKey: (id )key { - uint32_t i, hash, last; - - if (key == nil) - @throw [OFInvalidArgumentException newWithClass: isa - selector: _cmd]; - - hash = [key hash]; - last = size; - - for (i = hash & (size - 1); i < last && data[i] != NULL; i++) { - if (data[i] == DELETED) - continue; - - if ([data[i]->key isEqual: key]) - return data[i]->object; - } - - if (i < last) - return nil; - - /* In case the last bucket is already used */ - last = hash & (size - 1); - - for (i = 0; i < last && data[i] != NULL; i++) { - if (data[i] == DELETED) - continue; - - if ([data[i]->key isEqual: key]) - return data[i]->object; - } - - return nil; + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; } - (size_t)count { - return count; + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; } - copy { return [self retain]; @@ -595,153 +245,166 @@ - mutableCopy { return [[OFMutableDictionary alloc] initWithDictionary: self]; } -- (BOOL)isEqual: (id)dict +- (BOOL)isEqual: (id)dictionary { - uint32_t i; + OFAutoreleasePool *pool; + OFEnumerator *enumerator; + id key; - if ([dict count] != count) + if ([dictionary count] != [self count]) return NO; - for (i = 0; i < size; i++) - if (data[i] != NULL && data[i] != DELETED && - ![[dict objectForKey: data[i]->key] - isEqual: data[i]->object]) + pool = [[OFAutoreleasePool alloc] init]; + + enumerator = [self keyEnumerator]; + while ((key = [enumerator nextObject]) != nil) { + id object = [dictionary objectForKey: key]; + + if (object == nil || + ![object isEqual: [self objectForKey: key]]) { + [pool release]; return NO; + } + } + + [pool release]; return YES; } - (BOOL)containsObject: (id)object { - uint32_t i; - - if (count == 0) - return NO; - - for (i = 0; i < size; i++) - if (data[i] != NULL && data[i] != DELETED && - [data[i]->object isEqual: object]) + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + OFEnumerator *enumerator = [self objectEnumerator]; + id currentObject; + + while ((currentObject = [enumerator nextObject]) != nil) { + if ([currentObject isEqual: object]) { + [pool release]; return YES; + } + } + + [pool release]; return NO; } - (BOOL)containsObjectIdenticalTo: (id)object { - uint32_t i; - - if (count == 0) - return NO; - - for (i = 0; i < size; i++) - if (data[i] != NULL && data[i] != DELETED && - data[i]->object == object) + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + OFEnumerator *enumerator = [self objectEnumerator]; + id currentObject; + + while ((currentObject = [enumerator nextObject]) != nil) { + if (currentObject == object) { + [pool release]; return YES; + } + } + + [pool release]; return NO; } - (OFArray*)allKeys { - OFArray *ret; - id *cArray = [self allocMemoryForNItems: count + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + id *cArray = [self allocMemoryForNItems: [self count] withSize: sizeof(id)]; - size_t i, j; + OFEnumerator *enumerator; + id key; + OFArray *ret; + size_t i = 0; + + pool = [[OFAutoreleasePool alloc] init]; + enumerator = [self keyEnumerator]; + + while ((key = [enumerator nextObject]) != nil) + cArray[i++] = key; - for (i = j = 0; i < size; i++) - if (data[i] != NULL && data[i] != DELETED) - cArray[j++] = data[i]->key; + assert(i == [self count]); - assert(j == count); + [pool release]; @try { ret = [OFArray arrayWithCArray: cArray - length: count]; + length: [self count]]; } @finally { [self freeMemory: cArray]; } return ret; } - (OFArray*)allObjects { - OFArray *ret; - id *cArray = [self allocMemoryForNItems: count + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + id *cArray = [self allocMemoryForNItems: [self count] withSize: sizeof(id)]; - size_t i, j; + OFEnumerator *enumerator; + id object; + OFArray *ret; + size_t i = 0; + + pool = [[OFAutoreleasePool alloc] init]; + enumerator = [self objectEnumerator]; + + while ((object = [enumerator nextObject]) != nil) + cArray[i++] = object; - for (i = j = 0; i < size; i++) - if (data[i] != NULL && data[i] != DELETED) - cArray[j++] = data[i]->object; + assert(i == [self count]); - assert(j == count); + [pool release]; @try { ret = [OFArray arrayWithCArray: cArray - length: count]; + length: [self count]]; } @finally { [self freeMemory: cArray]; } return ret; } - (OFEnumerator*)objectEnumerator { - return [[[OFDictionaryObjectEnumerator alloc] - initWithDictionary: self - data: data - size: size - mutationsPointer: NULL] autorelease]; + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; } - (OFEnumerator*)keyEnumerator { - return [[[OFDictionaryKeyEnumerator alloc] - initWithDictionary: self - data: data - size: size - mutationsPointer: NULL] autorelease]; + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; } - (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state objects: (id*)objects count: (int)count_ { - int i; - - for (i = 0; i < count_; i++) { - for (; state->state < size && (data[state->state] == NULL || - data[state->state] == DELETED); state->state++); - - if (state->state < size) { - objects[i] = data[state->state]->key; - state->state++; - } else - break; - } - - state->itemsPtr = objects; - state->mutationsPtr = (unsigned long*)self; - - return i; + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; } #ifdef OF_HAVE_BLOCKS - (void)enumerateKeysAndObjectsUsingBlock: (of_dictionary_enumeration_block_t)block { - size_t i; + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + OFEnumerator *enumerator = [self keyEnumerator]; + id key; BOOL stop = NO; - for (i = 0; i < size && !stop; i++) - if (data[i] != NULL && data[i] != DELETED) - block(data[i]->key, data[i]->object, &stop); + while (!stop && (key = [enumerator nextObject]) != nil) + block(key, [self objectForKey: key], &stop); + + [pool release]; } - (OFDictionary*)mappedDictionaryUsingBlock: (of_dictionary_map_block_t)block { OFMutableDictionary *new = [OFMutableDictionary dictionary]; @@ -773,48 +436,23 @@ return new; } #endif -- (void)dealloc -{ - uint32_t i; - - for (i = 0; i < size; i++) { - if (data[i] != NULL && data[i] != DELETED) { - [data[i]->key release]; - [data[i]->object release]; - } - } - - [super dealloc]; -} - -- (uint32_t)hash -{ - uint32_t i; - uint32_t hash; - - OF_HASH_INIT(hash); - - for (i = 0; i < size; i++) { - if (data[i] != NULL && data[i] != DELETED) { - uint32_t h = [data[i]->object hash]; - - OF_HASH_ADD(hash, data[i]->hash >> 24); - OF_HASH_ADD(hash, (data[i]->hash >> 16) & 0xFF); - OF_HASH_ADD(hash, (data[i]->hash >> 8) & 0xFF); - OF_HASH_ADD(hash, data[i]->hash & 0xFF); - - OF_HASH_ADD(hash, h >> 24); - OF_HASH_ADD(hash, (h >> 16) & 0xFF); - OF_HASH_ADD(hash, (h >> 8) & 0xFF); - OF_HASH_ADD(hash, h & 0xFF); - } - } - - OF_HASH_FINALIZE(hash); +- (uint32_t)hash +{ + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + OFEnumerator *enumerator = [self keyEnumerator]; + id key; + uint32_t hash = 0; + + while ((key = [enumerator nextObject]) != nil) { + hash += [key hash]; + hash += [[self objectForKey: key] hash]; + } + + [pool release]; return hash; } - (OFString*)description @@ -821,11 +459,11 @@ { OFMutableString *ret; OFAutoreleasePool *pool, *pool2; OFEnumerator *keyEnumerator, *objectEnumerator; id key, object; - size_t i; + size_t i, count = [self count]; if (count == 0) return @"{()}"; ret = [OFMutableString stringWithString: @"{\n"]; @@ -864,12 +502,16 @@ OFAutoreleasePool *pool2; OFXMLElement *element; OFEnumerator *keyEnumerator, *objectEnumerator; id key, object; - element = [OFXMLElement elementWithName: [self className] - namespace: OF_SERIALIZATION_NS]; + if ([self isKindOfClass: [OFMutableDictionary class]]) + element = [OFXMLElement elementWithName: @"OFMutableDictionary" + namespace: OF_SERIALIZATION_NS]; + else + element = [OFXMLElement elementWithName: @"OFDictionary" + namespace: OF_SERIALIZATION_NS]; keyEnumerator = [self keyEnumerator]; objectEnumerator = [self objectEnumerator]; pool2 = [[OFAutoreleasePool alloc] init]; @@ -900,77 +542,6 @@ [element autorelease]; } return element; } -@end - -@implementation OFDictionaryEnumerator -- initWithDictionary: (OFDictionary*)dictionary_ - data: (struct of_dictionary_bucket**)data_ - size: (uint32_t)size_ - mutationsPointer: (unsigned long*)mutationsPtr_ -{ - self = [super init]; - - dictionary = [dictionary_ retain]; - data = data_; - size = size_; - mutations = (mutationsPtr_ != NULL ? *mutationsPtr_ : 0); - mutationsPtr = mutationsPtr_; - - return self; -} - -- (void)dealloc -{ - [dictionary release]; - - [super dealloc]; -} - -- (void)reset -{ - if (mutationsPtr != NULL && *mutationsPtr != mutations) - @throw [OFEnumerationMutationException - newWithClass: isa - object: dictionary]; - - pos = 0; -} -@end - -@implementation OFDictionaryObjectEnumerator -- (id)nextObject -{ - if (mutationsPtr != NULL && *mutationsPtr != mutations) - @throw [OFEnumerationMutationException - newWithClass: isa - object: dictionary]; - - for (; pos < size && (data[pos] == NULL || - data[pos] == DELETED); pos++); - - if (pos < size) - return data[pos++]->object; - else - return nil; -} -@end - -@implementation OFDictionaryKeyEnumerator -- (id)nextObject -{ - if (mutationsPtr != NULL && *mutationsPtr != mutations) - @throw [OFEnumerationMutationException - newWithClass: isa - object: dictionary]; - - for (; pos < size && (data[pos] == NULL || - data[pos] == DELETED); pos++); - - if (pos < size) - return data[pos++]->key; - else - return nil; -} @end ADDED src/OFDictionary_hashtable.h Index: src/OFDictionary_hashtable.h ================================================================== --- src/OFDictionary_hashtable.h +++ src/OFDictionary_hashtable.h @@ -0,0 +1,69 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011 + * 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 "OFDictionary.h" + +struct of_dictionary_hashtable_bucket +{ + id key; + id object; + uint32_t hash; +}; + +@interface OFDictionary_hashtable: OFDictionary +{ + struct of_dictionary_hashtable_bucket **data; + uint32_t size; + size_t count; +} + +#if defined(OF_SET_M) || defined(OF_COUNTED_SET_M) +- _initWithDictionary: (OFDictionary*)dictionary + copyKeys: (BOOL)copyKeys; +#endif +@end + +@interface OFDictionaryEnumerator_hashtable: OFEnumerator +{ + OFDictionary_hashtable *dictionary; + struct of_dictionary_hashtable_bucket **data; + uint32_t size; + unsigned long mutations; + unsigned long *mutationsPtr; + uint32_t pos; +} + +- initWithDictionary: (OFDictionary_hashtable*)dictionary + data: (struct of_dictionary_hashtable_bucket**)data + size: (uint32_t)size + mutationsPointer: (unsigned long*)mutationsPtr; +@end + +@interface OFDictionaryKeyEnumerator_hashtable: OFDictionaryEnumerator_hashtable +@end + +@interface OFDictionaryObjectEnumerator_hashtable: + OFDictionaryEnumerator_hashtable +@end + +#ifdef __cplusplus +extern "C" { +#endif +extern struct of_dictionary_hashtable_bucket + of_dictionary_hashtable_deleted_bucket; +#ifdef __cplusplus +} +#endif ADDED src/OFDictionary_hashtable.m Index: src/OFDictionary_hashtable.m ================================================================== --- src/OFDictionary_hashtable.m +++ src/OFDictionary_hashtable.m @@ -0,0 +1,874 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011 + * 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 + +#include + +#import "OFDictionary_hashtable.h" +#import "OFMutableDictionary_hashtable.h" +#import "OFEnumerator.h" +#import "OFArray.h" +#import "OFString.h" +#import "OFXMLElement.h" +#import "OFAutoreleasePool.h" + +#import "OFEnumerationMutationException.h" +#import "OFInvalidArgumentException.h" +#import "OFInvalidFormatException.h" +#import "OFNotImplementedException.h" +#import "OFOutOfRangeException.h" + +#import "macros.h" + +struct of_dictionary_hashtable_bucket + of_dictionary_hashtable_deleted_bucket = {}; +#define DELETED &of_dictionary_hashtable_deleted_bucket + +@implementation OFDictionary_hashtable +- init +{ + self = [super init]; + + @try { + data = [self allocMemoryWithSize: sizeof(*data)]; + size = 1; + data[0] = NULL; + } @catch (id e) { + [self release]; + @throw e; + } + + return self; +} + +- _initWithDictionary: (OFDictionary*)dictionary + copyKeys: (BOOL)copyKeys +{ + self = [super init]; + + @try { + uint32_t i; + OFDictionary_hashtable *hashtable; + + if (dictionary == nil) + @throw [OFInvalidArgumentException newWithClass: isa + selector: _cmd]; + + if (![dictionary isKindOfClass: + [OFDictionary_hashtable class]] && + ![dictionary isKindOfClass: + [OFMutableDictionary_hashtable class]]) + @throw [OFInvalidArgumentException newWithClass: isa + selector: _cmd]; + + hashtable = (OFDictionary_hashtable*)dictionary; + + data = [self allocMemoryForNItems: hashtable->size + withSize: sizeof(*data)]; + + for (i = 0; i < hashtable->size; i++) + data[i] = NULL; + + size = hashtable->size; + count = hashtable->count; + + for (i = 0; i < size; i++) { + id key; + struct of_dictionary_hashtable_bucket *bucket; + + if (hashtable->data[i] == NULL || + hashtable->data[i] == DELETED) + continue; + + bucket = [self allocMemoryWithSize: sizeof(*bucket)]; + key = (copyKeys + ? [hashtable->data[i]->key copy] + : [hashtable->data[i]->key retain]); + + @try { + [hashtable->data[i]->object retain]; + } @catch (id e) { + [key release]; + @throw e; + } + + bucket->key = key; + bucket->object = hashtable->data[i]->object; + bucket->hash = hashtable->data[i]->hash; + + data[i] = bucket; + } + } @catch (id e) { + [self release]; + @throw e; + } + + return self; +} + +- initWithDictionary: (OFDictionary*)dictionary +{ + self = [super init]; + + @try { + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + OFEnumerator *enumerator; + id key; + uint32_t i, newSize; + + count = [dictionary count]; + + if (count > UINT32_MAX) + @throw [OFOutOfRangeException newWithClass: isa]; + + for (newSize = 1; newSize < count; newSize <<= 1); + + if (newSize == 0) + @throw [OFOutOfRangeException newWithClass: isa]; + + data = [self allocMemoryForNItems: newSize + withSize: sizeof(*data)]; + + for (i = 0; i < newSize; i++) + data[i] = NULL; + + size = newSize; + + pool = [[OFAutoreleasePool alloc] init]; + enumerator = [dictionary keyEnumerator]; + + while ((key = [enumerator nextObject]) != nil) { + uint32_t hash, last; + struct of_dictionary_hashtable_bucket *bucket; + id object; + + hash = [key hash]; + last = size; + + for (i = hash & (size - 1); i < last && data[i] != NULL; + i++); + + /* In case the last bucket is already used */ + if (i >= last) { + last = hash & (size - 1); + + for (i = 0; i < last && data[i] != NULL; i++); + } + + if (data[i] != NULL) + @throw [OFOutOfRangeException + newWithClass: isa]; + + bucket = [self allocMemoryWithSize: sizeof(*bucket)]; + key = [key copy]; + + @try { + object = [dictionary objectForKey: key]; + [object retain]; + } @catch (id e) { + [key release]; + @throw e; + } + + bucket->key = key; + bucket->object = object; + bucket->hash = hash; + + data[i] = bucket; + } + + [pool release]; + } @catch (id e) { + [self release]; + @throw e; + } + + return self; +} + +- initWithObject: (id)object + forKey: (id )key +{ + self = [super init]; + + @try { + uint32_t i; + struct of_dictionary_hashtable_bucket *bucket; + + if (key == nil || object == nil) + @throw [OFInvalidArgumentException newWithClass: isa + selector: _cmd]; + + data = [self allocMemoryForNItems: 2 + withSize: sizeof(*data)]; + + size = 2; + for (i = 0; i < size; i++) + data[i] = NULL; + + i = [key hash] & 1; + bucket = [self allocMemoryWithSize: sizeof(*bucket)]; + key = [key copy]; + + @try { + [object retain]; + } @catch (id e) { + [key release]; + @throw e; + } + + bucket->key = key; + bucket->object = object; + bucket->hash = [key hash]; + + data[i] = bucket; + count = 1; + } @catch (id e) { + [self release]; + @throw e; + } + + return self; +} + +- initWithObjects: (OFArray*)objects + forKeys: (OFArray*)keys +{ + self = [super init]; + + @try { + id *objectsCArray, *keysCArray; + uint32_t i, j, newSize; + + keysCArray = [keys cArray]; + objectsCArray = [objects cArray]; + count = [keys count]; + + if (count > UINT32_MAX) + @throw [OFOutOfRangeException newWithClass: isa]; + + for (newSize = 1; newSize < count; newSize <<= 1); + + if (newSize == 0) + @throw [OFOutOfRangeException newWithClass: isa]; + + data = [self allocMemoryForNItems: newSize + withSize: sizeof(*data)]; + + for (j = 0; j < newSize; j++) + data[j] = NULL; + + size = newSize; + + for (i = 0; i < count; i++) { + uint32_t hash, last; + + hash = [keysCArray[i] hash]; + last = size; + + for (j = hash & (size - 1); j < last && data[j] != NULL; + j++) + if ([data[j]->key isEqual: keysCArray[i]]) + break; + + /* In case the last bucket is already used */ + if (j >= last) { + last = hash & (size - 1); + + for (j = 0; j < last && data[j] != NULL; j++) + if ([data[j]->key + isEqual: keysCArray[i]]) + break; + } + + /* Key not in dictionary */ + if (j >= last || data[j] == NULL || + ![data[j]->key isEqual: keysCArray[i]]) { + struct of_dictionary_hashtable_bucket *bucket; + id key; + + last = size; + + j = hash & (size - 1); + for (; j < last && data[j] != NULL; j++); + + /* In case the last bucket is already used */ + if (j >= last) { + last = hash & (size - 1); + + for (j = 0; j < last && data[j] != NULL; + j++); + } + + if (j >= last) + @throw [OFOutOfRangeException + newWithClass: isa]; + + bucket = + [self allocMemoryWithSize: sizeof(*bucket)]; + key = [keysCArray[i] copy]; + + @try { + [objectsCArray[i] retain]; + } @catch (id e) { + [key release]; + @throw e; + } + + bucket->key = key; + bucket->object = objectsCArray[i]; + bucket->hash = hash; + + data[j] = bucket; + + continue; + } + + /* + * The key is already in the dictionary. However, we + * just replace it so that the programmer gets the same + * behavior as if he'd call setObject:forKey: for each + * key/object pair. + */ + [objectsCArray[i] retain]; + + @try { + [data[j]->object release]; + } @catch (id e) { + [objectsCArray[i] release]; + @throw e; + } + + data[j]->object = objectsCArray[i]; + } + } @catch (id e) { + [self release]; + @throw e; + } + + return self; +} + +- initWithKey: (id )firstKey + arguments: (va_list)arguments +{ + self = [super init]; + + @try { + id key, object; + uint32_t i, j, hash, newSize; + va_list argumentsCopy; + struct of_dictionary_hashtable_bucket *bucket; + + va_copy(argumentsCopy, arguments); + + if (firstKey == nil) + @throw [OFInvalidArgumentException newWithClass: isa + selector: _cmd]; + + key = firstKey; + + if ((object = va_arg(arguments, id)) == nil) + @throw [OFInvalidArgumentException newWithClass: isa + selector: _cmd]; + + count = 1; + for (; va_arg(argumentsCopy, id) != nil; count++); + count >>= 1; + + if (count > UINT32_MAX) + @throw [OFOutOfRangeException newWithClass: isa]; + + for (newSize = 1; newSize < count; newSize <<= 1); + + if (newSize == 0) + @throw [OFOutOfRangeException newWithClass: isa]; + + data = [self allocMemoryForNItems: newSize + withSize: sizeof(*data)]; + + for (j = 0; j < newSize; j++) + data[j] = NULL; + + size = newSize; + + /* Add first key / object pair */ + hash = [key hash]; + j = hash & (size - 1); + + bucket = [self allocMemoryWithSize: sizeof(*bucket)]; + key = [key copy]; + + @try { + [object retain]; + } @catch (id e) { + [key release]; + @throw e; + } + + bucket->key = key; + bucket->object = object; + bucket->hash = hash; + + data[j] = bucket; + + for (i = 1; i < count; i++) { + uint32_t last; + + key = va_arg(arguments, id ); + object = va_arg(arguments, id); + + if (key == nil || object == nil) + @throw [OFInvalidArgumentException + newWithClass: isa + selector: _cmd]; + + hash = [key hash]; + last = size; + + for (j = hash & (size - 1); j < last && data[j] != NULL; + j++) + if ([data[j]->key isEqual: key]) + break; + + /* In case the last bucket is already used */ + if (j >= last) { + last = hash & (size - 1); + + for (j = 0; j < last && data[j] != NULL; j++) + if ([data[j]->key isEqual: key]) + break; + } + + /* Key not in dictionary */ + if (j >= last || data[j] == NULL || + ![data[j]->key isEqual: key]) { + last = size; + + j = hash & (size - 1); + for (; j < last && data[j] != NULL; j++); + + /* In case the last bucket is already used */ + if (j >= last) { + last = hash & (size - 1); + + for (j = 0; j < last && data[j] != NULL; + j++); + } + + if (j >= last) + @throw [OFOutOfRangeException + newWithClass: isa]; + + bucket = + [self allocMemoryWithSize: sizeof(*bucket)]; + key = [key copy]; + + @try { + [object retain]; + } @catch (id e) { + [key release]; + @throw e; + } + + bucket->key = key; + bucket->object = object; + bucket->hash = hash; + + data[j] = bucket; + + continue; + } + + /* + * The key is already in the dictionary. However, we + * just replace it so that the programmer gets the same + * behavior as if he'd call setObject:forKey: for each + * key/object pair. + */ + [object retain]; + + @try { + [data[j]->object release]; + } @catch (id e) { + [object release]; + @throw e; + } + + data[j]->object = object; + count--; + } + } @catch (id e) { + [self release]; + @throw e; + } + + return self; +} + +- initWithSerialization: (OFXMLElement*)element +{ + @try { + OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; + OFAutoreleasePool *pool2; + OFMutableDictionary *dictionary; + OFArray *keys, *objects; + OFEnumerator *keyEnumerator, *objectEnumerator; + OFXMLElement *keyElement, *objectElement; + + if ((![[element name] isEqual: @"OFDictionary"] && + ![[element name] isEqual: @"OFMutableDictionary"]) || + ![[element namespace] isEqual: OF_SERIALIZATION_NS]) + @throw [OFInvalidArgumentException newWithClass: isa + selector: _cmd]; + + dictionary = [OFMutableDictionary dictionary]; + + keys = [element elementsForName: @"key" + namespace: OF_SERIALIZATION_NS]; + objects = [element elementsForName: @"object" + namespace: OF_SERIALIZATION_NS]; + + if ([keys count] != [objects count]) + @throw [OFInvalidFormatException newWithClass: isa]; + + keyEnumerator = [keys objectEnumerator]; + objectEnumerator = [objects objectEnumerator]; + pool2 = [[OFAutoreleasePool alloc] init]; + + while ((keyElement = [keyEnumerator nextObject]) != nil && + (objectElement = [objectEnumerator nextObject]) != nil) { + OFXMLElement *key, *object; + + key = [[keyElement elementsForNamespace: + OF_SERIALIZATION_NS] firstObject]; + object = [[objectElement elementsForNamespace: + OF_SERIALIZATION_NS] firstObject]; + + if (key == nil || object == nil) + @throw [OFInvalidFormatException + newWithClass: isa]; + + [dictionary setObject: [object objectByDeserializing] + forKey: [key objectByDeserializing]]; + + [pool2 releaseObjects]; + } + + self = [self initWithDictionary: dictionary]; + + [pool release]; + } @catch (id e) { + [self release]; + @throw e; + } + + return self; +} + +- (id)objectForKey: (id )key +{ + uint32_t i, hash, last; + + if (key == nil) + @throw [OFInvalidArgumentException newWithClass: isa + selector: _cmd]; + + hash = [key hash]; + last = size; + + for (i = hash & (size - 1); i < last && data[i] != NULL; i++) { + if (data[i] == DELETED) + continue; + + if ([data[i]->key isEqual: key]) + return data[i]->object; + } + + if (i < last) + return nil; + + /* In case the last bucket is already used */ + last = hash & (size - 1); + + for (i = 0; i < last && data[i] != NULL; i++) { + if (data[i] == DELETED) + continue; + + if ([data[i]->key isEqual: key]) + return data[i]->object; + } + + return nil; +} + +- (size_t)count +{ + return count; +} + +- (BOOL)isEqual: (id)dictionary +{ + uint32_t i; + + if ([self class] != [OFDictionary_hashtable class] && + [self class] != [OFMutableDictionary_hashtable class]) + return [super isEqual: dictionary]; + + if ([dictionary count] != count) + return NO; + + for (i = 0; i < size; i++) + if (data[i] != NULL && data[i] != DELETED && + ![[dictionary objectForKey: data[i]->key] + isEqual: data[i]->object]) + return NO; + + return YES; +} + +- (BOOL)containsObject: (id)object +{ + uint32_t i; + + if (count == 0) + return NO; + + for (i = 0; i < size; i++) + if (data[i] != NULL && data[i] != DELETED && + [data[i]->object isEqual: object]) + return YES; + + return NO; +} + +- (BOOL)containsObjectIdenticalTo: (id)object +{ + uint32_t i; + + if (count == 0) + return NO; + + for (i = 0; i < size; i++) + if (data[i] != NULL && data[i] != DELETED && + data[i]->object == object) + return YES; + + return NO; +} + +- (OFArray*)allKeys +{ + OFArray *ret; + id *cArray = [self allocMemoryForNItems: count + withSize: sizeof(id)]; + size_t i, j; + + for (i = j = 0; i < size; i++) + if (data[i] != NULL && data[i] != DELETED) + cArray[j++] = data[i]->key; + + assert(j == count); + + @try { + ret = [OFArray arrayWithCArray: cArray + length: count]; + } @finally { + [self freeMemory: cArray]; + } + + return ret; +} + +- (OFArray*)allObjects +{ + OFArray *ret; + id *cArray = [self allocMemoryForNItems: count + withSize: sizeof(id)]; + size_t i, j; + + for (i = j = 0; i < size; i++) + if (data[i] != NULL && data[i] != DELETED) + cArray[j++] = data[i]->object; + + assert(j == count); + + @try { + ret = [OFArray arrayWithCArray: cArray + length: count]; + } @finally { + [self freeMemory: cArray]; + } + + return ret; +} + +- (OFEnumerator*)keyEnumerator +{ + return [[[OFDictionaryKeyEnumerator_hashtable alloc] + initWithDictionary: self + data: data + size: size + mutationsPointer: NULL] autorelease]; +} + +- (OFEnumerator*)objectEnumerator +{ + return [[[OFDictionaryObjectEnumerator_hashtable alloc] + initWithDictionary: self + data: data + size: size + mutationsPointer: NULL] autorelease]; +} + +- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state + objects: (id*)objects + count: (int)count_ +{ + int i; + + for (i = 0; i < count_; i++) { + for (; state->state < size && (data[state->state] == NULL || + data[state->state] == DELETED); state->state++); + + if (state->state < size) { + objects[i] = data[state->state]->key; + state->state++; + } else + break; + } + + state->itemsPtr = objects; + state->mutationsPtr = (unsigned long*)self; + + return i; +} + +#ifdef OF_HAVE_BLOCKS +- (void)enumerateKeysAndObjectsUsingBlock: + (of_dictionary_enumeration_block_t)block +{ + size_t i; + BOOL stop = NO; + + for (i = 0; i < size && !stop; i++) + if (data[i] != NULL && data[i] != DELETED) + block(data[i]->key, data[i]->object, &stop); +} +#endif + +- (void)dealloc +{ + uint32_t i; + + for (i = 0; i < size; i++) { + if (data[i] != NULL && data[i] != DELETED) { + [data[i]->key release]; + [data[i]->object release]; + } + } + + [super dealloc]; +} + +- (uint32_t)hash +{ + uint32_t i, hash = 0; + + for (i = 0; i < size; i++) { + if (data[i] != NULL && data[i] != DELETED) { + hash += data[i]->hash; + hash += [data[i]->object hash]; + } + } + + return hash; +} +@end + +@implementation OFDictionaryEnumerator_hashtable +- initWithDictionary: (OFDictionary_hashtable*)dictionary_ + data: (struct of_dictionary_hashtable_bucket**)data_ + size: (uint32_t)size_ + mutationsPointer: (unsigned long*)mutationsPtr_ +{ + self = [super init]; + + dictionary = [dictionary_ retain]; + data = data_; + size = size_; + mutations = (mutationsPtr_ != NULL ? *mutationsPtr_ : 0); + mutationsPtr = mutationsPtr_; + + return self; +} + +- (void)dealloc +{ + [dictionary release]; + + [super dealloc]; +} + +- (void)reset +{ + if (mutationsPtr != NULL && *mutationsPtr != mutations) + @throw [OFEnumerationMutationException + newWithClass: isa + object: dictionary]; + + pos = 0; +} +@end + +@implementation OFDictionaryObjectEnumerator_hashtable +- (id)nextObject +{ + if (mutationsPtr != NULL && *mutationsPtr != mutations) + @throw [OFEnumerationMutationException + newWithClass: isa + object: dictionary]; + + for (; pos < size && (data[pos] == NULL || + data[pos] == DELETED); pos++); + + if (pos < size) + return data[pos++]->object; + else + return nil; +} +@end + +@implementation OFDictionaryKeyEnumerator_hashtable +- (id)nextObject +{ + if (mutationsPtr != NULL && *mutationsPtr != mutations) + @throw [OFEnumerationMutationException + newWithClass: isa + object: dictionary]; + + for (; pos < size && (data[pos] == NULL || + data[pos] == DELETED); pos++); + + if (pos < size) + return data[pos++]->key; + else + return nil; +} +@end Index: src/OFMutableDictionary.h ================================================================== --- src/OFMutableDictionary.h +++ src/OFMutableDictionary.h @@ -19,17 +19,13 @@ #ifdef OF_HAVE_BLOCKS typedef id (^of_dictionary_replace_block_t)(id key, id object, BOOL *stop); #endif /** - * \brief A class for using mutable hash tables. + * \brief An abstract class for using mutable dictionaries. */ @interface OFMutableDictionary: OFDictionary -{ - unsigned long mutations; -} - /** * \brief Sets an object for a key. * * A key can be any object that conforms to the OFCopying protocol. * @@ -53,16 +49,13 @@ * \param block The block which returns a new object for each object */ - (void)replaceObjectsUsingBlock: (of_dictionary_replace_block_t)block; #endif -#if defined(OF_SET_M) || defined(OF_MUTABLE_SET_M) || defined(OF_COUNTED_SET_M) -- (void)_setObject: (id)object - forKey: (id)key - copyKey: (BOOL)copyKey; -#endif - /** * \brief Converts the mutable dictionary to an immutable dictionary. */ - (void)makeImmutable; @end + +@interface OFMutableDictionary_placeholder: OFDictionary +@end Index: src/OFMutableDictionary.m ================================================================== --- src/OFMutableDictionary.m +++ src/OFMutableDictionary.m @@ -14,316 +14,141 @@ * file. */ #include "config.h" -#include - -#import "OFMutableDictionary.h" +#import "OFMutableDictionary_hashtable.h" #import "OFAutoreleasePool.h" -#import "OFEnumerationMutationException.h" -#import "OFInvalidArgumentException.h" -#import "OFOutOfRangeException.h" +#import "OFNotImplementedException.h" #import "macros.h" -#define DELETED &of_dictionary_deleted_bucket +static struct { + Class isa; +} placeholder; + +@implementation OFMutableDictionary_placeholder +- init +{ + return (id)[[OFMutableDictionary_hashtable alloc] init]; +} + +- initWithDictionary: (OFDictionary*)dictionary +{ + return (id)[[OFMutableDictionary_hashtable alloc] + initWithDictionary: dictionary]; +} + +- initWithObject: (id)object + forKey: (id )key +{ + return (id)[[OFMutableDictionary_hashtable alloc] initWithObject: object + forKey: key]; +} + +- initWithObjects: (OFArray*)objects + forKeys: (OFArray*)keys +{ + return (id)[[OFMutableDictionary_hashtable alloc] + initWithObjects: objects + forKeys: keys]; +} + +- initWithKeysAndObjects: (id )firstKey, ... +{ + id ret; + va_list arguments; + + va_start(arguments, firstKey); + ret = (id)[[OFMutableDictionary_hashtable alloc] + initWithKey: firstKey + arguments: arguments]; + va_end(arguments); + + return ret; +} + +- initWithKey: (id )firstKey + arguments: (va_list)arguments +{ + return (id)[[OFMutableDictionary_hashtable alloc] + initWithKey: firstKey + arguments: arguments]; +} + +- initWithSerialization: (OFXMLElement*)element +{ + return (id)[[OFMutableDictionary_hashtable alloc] + initWithSerialization: element]; +} + +- retain +{ + return self; +} + +- autorelease +{ + return self; +} + +- (void)release +{ +} + +- (void)dealloc +{ + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; + [super dealloc]; /* Get rid of a stupid warning */ +} +@end @implementation OFMutableDictionary -- (void)_resizeForCount: (size_t)newCount -{ - size_t fullness = newCount * 4 / size; - struct of_dictionary_bucket **newData; - uint32_t i, newSize; - - if (newCount > UINT32_MAX) - @throw [OFOutOfRangeException newWithClass: isa]; - - if (fullness >= 3) - newSize = size << 1; - else if (fullness <= 1) - newSize = size >> 1; - else - return; - - if (newSize == 0) - @throw [OFOutOfRangeException newWithClass: isa]; - - newData = [self allocMemoryForNItems: newSize - withSize: sizeof(*newData)]; - - for (i = 0; i < newSize; i++) - newData[i] = NULL; - - for (i = 0; i < size; i++) { - if (data[i] != NULL && data[i] != DELETED) { - uint32_t j, last; - - last = newSize; - - j = data[i]->hash & (newSize - 1); - for (; j < last && newData[j] != NULL; j++); - - /* In case the last bucket is already used */ - if (j >= last) { - last = data[i]->hash & (newSize - 1); - - for (j = 0; j < last && - newData[j] != NULL; j++); - } - - if (j >= last) { - [self freeMemory: newData]; - @throw [OFOutOfRangeException - newWithClass: isa]; - } - - newData[j] = data[i]; - } - } - - [self freeMemory: data]; - data = newData; - size = newSize; -} - -- (void)_setObject: (id)object - forKey: (id)key - copyKey: (BOOL)copyKey -{ - uint32_t i, hash, last; - id old; - - if (key == nil || object == nil) - @throw [OFInvalidArgumentException newWithClass: isa - selector: _cmd]; - - hash = [key hash]; - last = size; - - for (i = hash & (size - 1); i < last && data[i] != NULL; i++) { - if (data[i] == DELETED) - continue; - - if ([data[i]->key isEqual: key]) - break; - } - - /* In case the last bucket is already used */ - if (i >= last) { - last = hash & (size - 1); - - for (i = 0; i < last && data[i] != NULL; i++) { - if (data[i] == DELETED) - continue; - - if ([data[i]->key isEqual: key]) - break; - } - } - - /* Key not in dictionary */ - if (i >= last || data[i] == NULL || data[i] == DELETED || - ![data[i]->key isEqual: key]) { - struct of_dictionary_bucket *bucket; - - [self _resizeForCount: count + 1]; - - mutations++; - last = size; - - for (i = hash & (size - 1); i < last && data[i] != NULL && - data[i] != DELETED; i++); - - /* In case the last bucket is already used */ - if (i >= last) { - last = hash & (size - 1); - - for (i = 0; i < last && data[i] != NULL && - data[i] != DELETED; i++); - } - - if (i >= last) - @throw [OFOutOfRangeException newWithClass: isa]; - - bucket = [self allocMemoryWithSize: sizeof(*bucket)]; - - @try { - key = (copyKey ? [key copy] : [key retain]); - } @catch (id e) { - [self freeMemory: bucket]; - @throw e; - } - - @try { - [object retain]; - } @catch (id e) { - [self freeMemory: bucket]; - [key release]; - @throw e; - } - - bucket->key = key; - bucket->object = object; - bucket->hash = hash; - data[i] = bucket; - count++; - - return; - } - - old = data[i]->object; - data[i]->object = [object retain]; - [old release]; ++ (void)initialize +{ + if (self == [OFMutableDictionary class]) + placeholder.isa = [OFMutableDictionary_placeholder class]; +} + ++ alloc +{ + if (self == [OFMutableDictionary class]) + return (id)&placeholder; + + return [super alloc]; } - (void)setObject: (id)object forKey: (id )key { - [self _setObject: object - forKey: key - copyKey: YES]; + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; } - (void)removeObjectForKey: (id )key { - uint32_t i, hash, last; - - if (key == nil) - @throw [OFInvalidArgumentException newWithClass: isa - selector: _cmd]; - - hash = [key hash]; - last = size; - - for (i = hash & (size - 1); i < last && data[i] != NULL; i++) { - if (data[i] == DELETED) - continue; - - if ([data[i]->key isEqual: key]) { - [data[i]->key release]; - [data[i]->object release]; - [self freeMemory: data[i]]; - data[i] = DELETED; - - count--; - mutations++; - [self _resizeForCount: count]; - - return; - } - } - - if (i < last) - return; - - /* In case the last bucket is already used */ - last = hash & (size - 1); - - for (i = 0; i < last && data[i] != NULL; i++) { - if (data[i] == DELETED) - continue; - - if ([data[i]->key isEqual: key]) { - [data[i]->key release]; - [data[i]->object release]; - [self freeMemory: data[i]]; - data[i] = DELETED; - - count--; - mutations++; - [self _resizeForCount: count]; - - return; - } - } + @throw [OFNotImplementedException newWithClass: isa + selector: _cmd]; } - copy { return [[OFDictionary alloc] initWithDictionary: self]; } -- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state - objects: (id*)objects - count: (int)count_ -{ - int ret = [super countByEnumeratingWithState: state - objects: objects - count: count_]; - - state->mutationsPtr = &mutations; - - return ret; -} - -- (OFEnumerator*)objectEnumerator -{ - return [[[OFDictionaryObjectEnumerator alloc] - initWithDictionary: self - data: data - size: size - mutationsPointer: &mutations] autorelease]; -} - -- (OFEnumerator*)keyEnumerator -{ - return [[[OFDictionaryKeyEnumerator alloc] - initWithDictionary: self - data: data - size: size - mutationsPointer: &mutations] autorelease]; -} - #ifdef OF_HAVE_BLOCKS -- (void)enumerateKeysAndObjectsUsingBlock: - (of_dictionary_enumeration_block_t)block -{ - size_t i; - BOOL stop = NO; - unsigned long mutations2 = mutations; - - for (i = 0; i < size && !stop; i++) { - if (mutations != mutations2) - @throw [OFEnumerationMutationException - newWithClass: isa - object: self]; - - if (data[i] != NULL && data[i] != DELETED) - block(data[i]->key, data[i]->object, &stop); - } -} - - (void)replaceObjectsUsingBlock: (of_dictionary_replace_block_t)block { - size_t i; - BOOL stop = NO; - unsigned long mutations2 = mutations; - - for (i = 0; i < size && !stop; i++) { - if (mutations != mutations2) - @throw [OFEnumerationMutationException - newWithClass: isa - object: self]; - - if (data[i] != NULL && data[i] != DELETED) { - id new = block(data[i]->key, data[i]->object, &stop); - - if (new == nil) - @throw [OFInvalidArgumentException - newWithClass: isa - selector: _cmd]; - - [new retain]; - [data[i]->object release]; - data[i]->object = new; - } - } + [self enumerateKeysAndObjectsUsingBlock: ^ (id key, id object, + BOOL *stop) { + [self setObject: block(key, object, stop) + forKey: key]; + }]; } #endif - (void)makeImmutable { - isa = [OFDictionary class]; } @end ADDED src/OFMutableDictionary_hashtable.h Index: src/OFMutableDictionary_hashtable.h ================================================================== --- src/OFMutableDictionary_hashtable.h +++ src/OFMutableDictionary_hashtable.h @@ -0,0 +1,37 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011 + * 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 "OFDictionary.h" + +@interface OFMutableDictionary_hashtable: OFMutableDictionary +{ + struct of_dictionary_hashtable_bucket **data; + uint32_t size; + size_t count; + unsigned long mutations; +} + +#if defined(OF_SET_M) || defined(OF_COUNTED_SET_M) +- _initWithDictionary: (OFDictionary*)dictionary + copyKeys: (BOOL)copyKeys; +#endif + +#if defined(OF_SET_M) || defined(OF_MUTABLE_SET_M) || defined(OF_COUNTED_SET_M) +- (void)_setObject: (id)object + forKey: (id)key + copyKey: (BOOL)copyKey; +#endif +@end ADDED src/OFMutableDictionary_hashtable.m Index: src/OFMutableDictionary_hashtable.m ================================================================== --- src/OFMutableDictionary_hashtable.m +++ src/OFMutableDictionary_hashtable.m @@ -0,0 +1,339 @@ +/* + * Copyright (c) 2008, 2009, 2010, 2011 + * 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 "OFMutableDictionary_hashtable.h" +#import "OFDictionary_hashtable.h" +#import "OFAutoreleasePool.h" + +#import "OFEnumerationMutationException.h" +#import "OFInvalidArgumentException.h" +#import "OFOutOfRangeException.h" + +#import "macros.h" + +#define DELETED &of_dictionary_hashtable_deleted_bucket + +static Class dictionary = Nil; + +@implementation OFMutableDictionary_hashtable ++ (void)initialize +{ + if (self == [OFMutableDictionary_hashtable class]) { + dictionary = [OFDictionary_hashtable class]; + [self inheritMethodsFromClass: dictionary]; + } +} + +- (void)_resizeForCount: (size_t)newCount +{ + size_t fullness = newCount * 4 / size; + struct of_dictionary_hashtable_bucket **newData; + uint32_t i, newSize; + + if (newCount > UINT32_MAX) + @throw [OFOutOfRangeException newWithClass: isa]; + + if (fullness >= 3) + newSize = size << 1; + else if (fullness <= 1) + newSize = size >> 1; + else + return; + + if (newSize == 0) + @throw [OFOutOfRangeException newWithClass: isa]; + + newData = [self allocMemoryForNItems: newSize + withSize: sizeof(*newData)]; + + for (i = 0; i < newSize; i++) + newData[i] = NULL; + + for (i = 0; i < size; i++) { + if (data[i] != NULL && data[i] != DELETED) { + uint32_t j, last; + + last = newSize; + + j = data[i]->hash & (newSize - 1); + for (; j < last && newData[j] != NULL; j++); + + /* In case the last bucket is already used */ + if (j >= last) { + last = data[i]->hash & (newSize - 1); + + for (j = 0; j < last && + newData[j] != NULL; j++); + } + + if (j >= last) { + [self freeMemory: newData]; + @throw [OFOutOfRangeException + newWithClass: isa]; + } + + newData[j] = data[i]; + } + } + + [self freeMemory: data]; + data = newData; + size = newSize; +} + +- (void)_setObject: (id)object + forKey: (id)key + copyKey: (BOOL)copyKey +{ + uint32_t i, hash, last; + id old; + + if (key == nil || object == nil) + @throw [OFInvalidArgumentException newWithClass: isa + selector: _cmd]; + + hash = [key hash]; + last = size; + + for (i = hash & (size - 1); i < last && data[i] != NULL; i++) { + if (data[i] == DELETED) + continue; + + if ([data[i]->key isEqual: key]) + break; + } + + /* In case the last bucket is already used */ + if (i >= last) { + last = hash & (size - 1); + + for (i = 0; i < last && data[i] != NULL; i++) { + if (data[i] == DELETED) + continue; + + if ([data[i]->key isEqual: key]) + break; + } + } + + /* Key not in dictionary */ + if (i >= last || data[i] == NULL || data[i] == DELETED || + ![data[i]->key isEqual: key]) { + struct of_dictionary_hashtable_bucket *bucket; + + [self _resizeForCount: count + 1]; + + mutations++; + last = size; + + for (i = hash & (size - 1); i < last && data[i] != NULL && + data[i] != DELETED; i++); + + /* In case the last bucket is already used */ + if (i >= last) { + last = hash & (size - 1); + + for (i = 0; i < last && data[i] != NULL && + data[i] != DELETED; i++); + } + + if (i >= last) + @throw [OFOutOfRangeException newWithClass: isa]; + + bucket = [self allocMemoryWithSize: sizeof(*bucket)]; + + @try { + key = (copyKey ? [key copy] : [key retain]); + } @catch (id e) { + [self freeMemory: bucket]; + @throw e; + } + + @try { + [object retain]; + } @catch (id e) { + [self freeMemory: bucket]; + [key release]; + @throw e; + } + + bucket->key = key; + bucket->object = object; + bucket->hash = hash; + data[i] = bucket; + count++; + + return; + } + + old = data[i]->object; + data[i]->object = [object retain]; + [old release]; +} + +- (void)setObject: (id)object + forKey: (id )key +{ + [self _setObject: object + forKey: key + copyKey: YES]; +} + +- (void)removeObjectForKey: (id )key +{ + uint32_t i, hash, last; + + if (key == nil) + @throw [OFInvalidArgumentException newWithClass: isa + selector: _cmd]; + + hash = [key hash]; + last = size; + + for (i = hash & (size - 1); i < last && data[i] != NULL; i++) { + if (data[i] == DELETED) + continue; + + if ([data[i]->key isEqual: key]) { + [data[i]->key release]; + [data[i]->object release]; + [self freeMemory: data[i]]; + data[i] = DELETED; + + count--; + mutations++; + [self _resizeForCount: count]; + + return; + } + } + + if (i < last) + return; + + /* In case the last bucket is already used */ + last = hash & (size - 1); + + for (i = 0; i < last && data[i] != NULL; i++) { + if (data[i] == DELETED) + continue; + + if ([data[i]->key isEqual: key]) { + [data[i]->key release]; + [data[i]->object release]; + [self freeMemory: data[i]]; + data[i] = DELETED; + + count--; + mutations++; + [self _resizeForCount: count]; + + return; + } + } +} + +- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state + objects: (id*)objects + count: (int)count_ +{ + const SEL selector = + @selector(countByEnumeratingWithState:objects:count:); + int (*imp)(id, SEL, of_fast_enumeration_state_t*, id*, int) = + (int(*)(id, SEL, of_fast_enumeration_state_t*, id*, int)) + [dictionary instanceMethodForSelector: selector]; + + int ret = imp(self, selector, state, objects, count_); + + state->mutationsPtr = &mutations; + + return ret; +} + +- (OFEnumerator*)objectEnumerator +{ + return [[[OFDictionaryObjectEnumerator_hashtable alloc] + initWithDictionary: (OFDictionary_hashtable*)self + data: data + size: size + mutationsPointer: &mutations] autorelease]; +} + +- (OFEnumerator*)keyEnumerator +{ + return [[[OFDictionaryKeyEnumerator_hashtable alloc] + initWithDictionary: (OFDictionary_hashtable*)self + data: data + size: size + mutationsPointer: &mutations] autorelease]; +} + +#ifdef OF_HAVE_BLOCKS +- (void)enumerateKeysAndObjectsUsingBlock: + (of_dictionary_enumeration_block_t)block +{ + size_t i; + BOOL stop = NO; + unsigned long mutations2 = mutations; + + for (i = 0; i < size && !stop; i++) { + if (mutations != mutations2) + @throw [OFEnumerationMutationException + newWithClass: isa + object: self]; + + if (data[i] != NULL && data[i] != DELETED) + block(data[i]->key, data[i]->object, &stop); + } +} + +- (void)replaceObjectsUsingBlock: (of_dictionary_replace_block_t)block +{ + size_t i; + BOOL stop = NO; + unsigned long mutations2 = mutations; + + for (i = 0; i < size && !stop; i++) { + if (mutations != mutations2) + @throw [OFEnumerationMutationException + newWithClass: isa + object: self]; + + if (data[i] != NULL && data[i] != DELETED) { + id new = block(data[i]->key, data[i]->object, &stop); + + if (new == nil) + @throw [OFInvalidArgumentException + newWithClass: isa + selector: _cmd]; + + [new retain]; + [data[i]->object release]; + data[i]->object = new; + } + } +} +#endif + +- (void)makeImmutable +{ + isa = [OFDictionary_hashtable class]; +} +@end Index: src/OFMutableSet.m ================================================================== --- src/OFMutableSet.m +++ src/OFMutableSet.m @@ -17,11 +17,11 @@ #include "config.h" #define OF_MUTABLE_SET_M #import "OFMutableSet.h" -#import "OFDictionary.h" +#import "OFMutableDictionary_hashtable.h" #import "OFArray.h" #import "OFNumber.h" #import "OFAutoreleasePool.h" @implementation OFMutableSet Index: src/OFSet.h ================================================================== --- src/OFSet.h +++ src/OFSet.h @@ -17,11 +17,11 @@ #include #import "OFObject.h" #import "OFCollection.h" -@class OFMutableDictionary; +@class OFMutableDictionary_hashtable; @class OFArray; #ifdef OF_HAVE_BLOCKS typedef void (^of_set_enumeration_block_t)(id object, BOOL *stop); typedef BOOL (^of_set_filter_block_t)(id object); @@ -30,11 +30,11 @@ /** * \brief An unordered set of unique objects. */ @interface OFSet: OFObject { - OFMutableDictionary *dictionary; + OFMutableDictionary_hashtable *dictionary; } /** * \brief Returns a new, autoreleased set. * Index: src/OFSet.m ================================================================== --- src/OFSet.m +++ src/OFSet.m @@ -17,11 +17,11 @@ #include "config.h" #define OF_SET_M #import "OFSet.h" -#import "OFDictionary.h" +#import "OFMutableDictionary_hashtable.h" #import "OFArray.h" #import "OFString.h" #import "OFNumber.h" #import "OFAutoreleasePool.h" @@ -57,11 +57,11 @@ - init { self = [super init]; @try { - dictionary = [[OFMutableDictionary alloc] init]; + dictionary = [[OFMutableDictionary_hashtable alloc] init]; } @catch (id e) { [self release]; @throw e; } Index: tests/serialization.xml ================================================================== --- tests/serialization.xml +++ tests/serialization.xml @@ -1,21 +1,9 @@ - - Qu"xbar -test - 1234 - asd - - - - - Hello - - Hello Wo ld! How are you? https://webkeks.org/ @@ -65,10 +53,22 @@ list + + + Qu"xbar +test + 1234 + asd + + + + + Hello + Blub B"la