Artifact 58ee7d242e0e38d9bc5671f487b71443b2f112f5cd90150bf645aa2106399ecc:
- File
src/OFDictionary.m
— part of check-in
[8ff55bf218]
at
2011-07-17 16:38:47
on branch trunk
— Remove -[containsObjectIdenticalTo:] from OFCopying.
It is still implemented by all classes implementing OFCollection so far,
but new classes are not required to implement it anymore.This is required to add OFCountedSet later, which can't support it. (user: js, size: 19689) [annotate] [blame] [check-ins using]
/* * Copyright (c) 2008, 2009, 2010, 2011 * Jonathan Schleifer <js@webkeks.org> * * All rights reserved. * * This file is part of ObjFW. It may be distributed under the terms of the * Q Public License 1.0, which can be found in the file LICENSE.QPL included in * the packaging of this file. * * Alternatively, it may be distributed under the terms of the GNU General * Public License, either version 2 or 3, which can be found in the file * LICENSE.GPLv2 or LICENSE.GPLv3 respectively included in the packaging of this * file. */ #include "config.h" #include <string.h> #import "OFDictionary.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 "OFOutOfRangeException.h" #import "macros.h" struct of_dictionary_bucket of_dictionary_deleted_bucket = {}; #define DELETED &of_dictionary_deleted_bucket @implementation OFDictionary + dictionary { return [[[self alloc] init] autorelease]; } + dictionaryWithDictionary: (OFDictionary*)dictionary { return [[[self alloc] initWithDictionary: dictionary] autorelease]; } + dictionaryWithObject: (id)object forKey: (id <OFCopying>)key { return [[[self alloc] initWithObject: object forKey: key] autorelease]; } + dictionaryWithObjects: (OFArray*)objects forKeys: (OFArray*)keys { return [[[self alloc] initWithObjects: objects forKeys: keys] autorelease]; } + dictionaryWithKeysAndObjects: (id <OFCopying>)firstKey, ... { id ret; va_list arguments; va_start(arguments, firstKey); ret = [[[self alloc] initWithKey: firstKey arguments: arguments] autorelease]; va_end(arguments); 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 { 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 <OFCopying> key; struct of_dictionary_bucket *bucket; if (dictionary->data[i] == NULL || dictionary->data[i] == DELETED) continue; bucket = [self allocMemoryWithSize: sizeof(*bucket)]; key = [dictionary->data[i]->key copy]; @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; } - initWithObject: (id)object forKey: (id <OFCopying>)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; } - 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 <OFCopying> 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; } - initWithKeysAndObjects: (id <OFCopying>)firstKey, ... { id ret; va_list arguments; va_start(arguments, firstKey); ret = [self initWithKey: firstKey arguments: arguments]; va_end(arguments); return ret; } - initWithKey: (id <OFCopying>)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 <OFCopying>); 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: [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; } - (id)objectForKey: (id <OFCopying>)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; } - copy { return [self retain]; } - mutableCopy { return [[OFMutableDictionary alloc] initWithDictionary: self]; } - (BOOL)isEqual: (id)dict { uint32_t i; if ([dict count] != 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]) 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; } - (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; } - (OFEnumerator*)objectEnumerator { return [[[OFDictionaryObjectEnumerator alloc] initWithDictionary: self data: data size: size mutationsPointer: NULL] autorelease]; } - (OFEnumerator*)keyEnumerator { return [[[OFDictionaryKeyEnumerator alloc] initWithDictionary: self data: data size: size mutationsPointer: NULL] autorelease]; } #ifdef OF_HAVE_BLOCKS - (void)enumerateKeysAndObjectsUsingBlock: (of_dictionary_enumeration_block_t)block { OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; 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); [pool releaseObjects]; } } [pool release]; } - (OFDictionary*)mappedDictionaryUsingBlock: (of_dictionary_map_block_t)block { OFMutableDictionary *new = [OFMutableDictionary dictionary]; size_t i; for (i = 0; i < size; i++) if (data[i] != NULL && data[i] != DELETED) [new setObject: block(data[i]->key, data[i]->object) forKey: data[i]->key]; /* * Class swizzle the dictionary to be immutable. We declared the return * type to be OFDictionary*, so it can't be modified anyway. But not * swizzling it would create a real copy each time -[copy] is called. */ new->isa = [OFDictionary class]; return new; } - (OFDictionary*)filteredDictionaryUsingBlock: (of_dictionary_filter_block_t)block { OFMutableDictionary *new = [OFMutableDictionary dictionary]; size_t i; for (i = 0; i < size; i++) if (data[i] != NULL && data[i] != DELETED) if (block(data[i]->key, data[i]->object)) [new setObject: data[i]->object forKey: data[i]->key]; /* * Class swizzle the dictionary to be immutable. We declared the return * type to be OFDictionary*, so it can't be modified anyway. But not * swizzling it would create a real copy each time -[copy] is called. */ new->isa = [OFDictionary class]; 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); return hash; } - (OFString*)description { OFMutableString *ret; OFAutoreleasePool *pool, *pool2; OFEnumerator *keyEnumerator, *objectEnumerator; id key, object; size_t i; if (count == 0) return @"{}"; ret = [OFMutableString stringWithString: @"{\n"]; pool = [[OFAutoreleasePool alloc] init]; keyEnumerator = [self keyEnumerator]; objectEnumerator = [self objectEnumerator]; i = 0; pool2 = [[OFAutoreleasePool alloc] init]; while ((key = [keyEnumerator nextObject]) != nil && (object = [objectEnumerator nextObject]) != nil) { [ret appendString: [key description]]; [ret appendString: @" = "]; [ret appendString: [object description]]; if (++i < count) [ret appendString: @";\n"]; [pool2 releaseObjects]; } [ret replaceOccurrencesOfString: @"\n" withString: @"\n\t"]; [ret appendString: @";\n}"]; [pool release]; /* * Class swizzle the string to be immutable. We declared the return type * to be OFString*, so it can't be modified anyway. But not swizzling it * would create a real copy each time -[copy] is called. */ ret->isa = [OFString class]; return ret; } - (OFXMLElement*)XMLElementBySerializing { OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; OFAutoreleasePool *pool2; OFXMLElement *element; OFEnumerator *keyEnumerator, *objectEnumerator; id <OFSerialization> key, object; element = [OFXMLElement elementWithName: [self className] namespace: OF_SERIALIZATION_NS]; keyEnumerator = [self keyEnumerator]; objectEnumerator = [self objectEnumerator]; pool2 = [[OFAutoreleasePool alloc] init]; while ((key = [keyEnumerator nextObject]) != nil && (object = [objectEnumerator nextObject]) != nil) { OFXMLElement *keyElement, *objectElement; keyElement = [OFXMLElement elementWithName: @"key" namespace: OF_SERIALIZATION_NS]; [keyElement addChild: [key XMLElementBySerializing]]; objectElement = [OFXMLElement elementWithName: @"object" namespace: OF_SERIALIZATION_NS]; [objectElement addChild: [object XMLElementBySerializing]]; [element addChild: keyElement]; [element addChild: objectElement]; [pool2 releaseObjects]; } [element retain]; @try { [pool release]; } @finally { [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