Index: src/Makefile ================================================================== --- src/Makefile +++ src/Makefile @@ -13,10 +13,11 @@ OFFile.m \ OFHashes.m \ OFIterator.m \ OFList.m \ OFMutableArray.m \ + OFMutableDictionary.m \ OFMutableString.m \ OFNumber.m \ OFObject.m \ ${OFPLUGIN_M} \ OFSocket.m \ Index: src/OFDictionary.h ================================================================== --- src/OFDictionary.h +++ src/OFDictionary.h @@ -49,43 +49,44 @@ * \param bits The size of the hash to use * \return An initialized OFDictionary */ - initWithHashSize: (int)hashsize; +/** + * \return The average number of items in a used bucket. Buckets that are + * completely empty are not in the calculation. If this value is >= 2.0, + * you should resize the dictionary, in most cases even earlier! + */ +- (float)averageItemsPerBucket; + +/** + * \param key The key whose object should be returned + * \return The object for the given key or nil if the key was not found + */ +- (id)get: (OFObject*)key; + /** * Sets a key to an object. A key can be any object. * * \param key The key to set * \param obj The object to set the key to */ - set: (OFObject *)key to: (OFObject*)obj; -/** - * \param key The key whose object should be returned - * \return The object for the given key or nil if the key was not found - */ -- (id)get: (OFObject*)key; - /** * Remove the object with the given key from the dictionary. * * \param key The key whose object should be removed */ - remove: (OFObject*)key; -/** - * \return The average number of items in a used bucket. Buckets that are - * completely empty are not in the calculation. If this value is >= 2.0, - * you should resize the dictionary, in most cases even earlier! - */ -- (float)averageItemsPerBucket; - /** * Changes the hash size of the dictionary. * * \param hashsize The new hash size for the dictionary */ - changeHashSize: (int)hashsize; @end #import "OFIterator.h" +#import "OFMutableDictionary.h" Index: src/OFDictionary.m ================================================================== --- src/OFDictionary.m +++ src/OFDictionary.m @@ -14,11 +14,10 @@ #include #import "OFDictionary.h" #import "OFIterator.h" #import "OFExceptions.h" -#import "OFMacros.h" /* Reference for static linking */ void _reference_to_OFIterator_in_OFDictionary() { _OFIterator_reference = 1; @@ -25,16 +24,16 @@ } @implementation OFDictionary + dictionary; { - return [[[OFDictionary alloc] init] autorelease]; + return [[[self alloc] init] autorelease]; } + dictionaryWithHashSize: (int)hashsize { - return [[[OFDictionary alloc] initWithHashSize: hashsize] autorelease]; + return [[[self alloc] initWithHashSize: hashsize] autorelease]; } - init { self = [super init]; @@ -86,61 +85,25 @@ memset(data, 0, size * sizeof(OFList*)); return self; } -- (void)dealloc -{ - size_t i; - - for (i = 0; i < size; i++) - if (data[i] != nil) - [data[i] release]; - - [super dealloc]; -} - -- set: (OFObject *)key - to: (OFObject*)obj -{ - uint32_t hash; - of_list_object_t *iter, *key_obj; - - if (key == nil || obj == nil) - @throw [OFInvalidArgumentException newWithClass: isa - andSelector: _cmd]; - - hash = [key hash] & (size - 1); - - if (data[hash] == nil) - data[hash] = [[OFList alloc] init]; - - for (iter = [data[hash] first]; iter != NULL; iter = iter->next->next) { - if ([iter->object isEqual: key]) { - [iter->next->object release]; - [obj retain]; - iter->next->object = obj; - - return self; - } - } - - key = [key copy]; - @try { - key_obj = [data[hash] append: key]; - } @finally { - [key release]; - } - - @try { - [data[hash] append: obj]; - } @catch (OFException *e) { - [data[hash] remove: key_obj]; - @throw e; - } - - return self; +- (float)averageItemsPerBucket +{ + size_t items, buckets, i; + + items = 0; + buckets = 0; + + for (i = 0; i < size; i++) { + if (data[i] != nil) { + items += [data[i] items] / 2; + buckets++; + } + } + + return (float)items / buckets; } - (id)get: (OFObject*)key { uint32_t hash; @@ -159,101 +122,51 @@ if ([iter->object isEqual: key]) return iter->next->object; return nil; } + +- set: (OFObject *)key + to: (OFObject*)obj +{ + @throw [OFNotImplementedException newWithClass: isa + andSelector: _cmd]; +} - remove: (OFObject*)key { - uint32_t hash; - of_list_object_t *iter; - - if (key == nil) - @throw [OFInvalidArgumentException newWithClass: isa - andSelector: _cmd]; - - hash = [key hash] & (size - 1); - - if (data[hash] == nil) - return self; - - for (iter = [data[hash] first]; iter != NULL; iter = iter->next->next) { - if ([iter->object isEqual: key]) { - [data[hash] remove: iter->next]; - [data[hash] remove: iter]; - - if ([data[hash] first] == NULL) { - [data[hash] release]; - data[hash] = nil; - } - - return self; - } - } - - return self; -} - -- (float)averageItemsPerBucket -{ - size_t items, buckets, i; - - items = 0; - buckets = 0; - - for (i = 0; i < size; i++) { - if (data[i] != nil) { - items += [data[i] items] / 2; - buckets++; - } - } - - return (float)items / buckets; + @throw [OFNotImplementedException newWithClass: isa + andSelector: _cmd]; } - changeHashSize: (int)hashsize { - OFList **newdata; - size_t newsize, i; - of_list_object_t *iter; - - if (hashsize < 8 || hashsize >= 28) - @throw [OFInvalidArgumentException newWithClass: isa - andSelector: _cmd]; - - newsize = (size_t)1 << hashsize; - newdata = [self allocNItems: newsize - withSize: sizeof(OFList*)]; - memset(data, 0, newsize * sizeof(OFList*)); - - for (i = 0; i < size; i++) { - if (OF_LIKELY(data[i] == nil)) - continue; - - for (iter = [data[i] first]; iter != NULL; - iter = iter->next->next) { - uint32_t hash = [iter->object hash] & (newsize - 1); - - if (newdata[hash] == nil) - newdata[hash] = [[OFList alloc] init]; - - [newdata[hash] append: iter->object]; - [newdata[hash] append: iter->next->object]; - } - - [data[i] release]; - } - - [self freeMem: data]; - data = newdata; - size = newsize; - - return self; + @throw [OFNotImplementedException newWithClass: isa + andSelector: _cmd]; } /* FIXME: Implement this! */ /* - (BOOL)isEqual { } + +- (id)copy +{ +} + +- (id)mutableCopy +{ +} */ + +- (void)dealloc +{ + size_t i; + + for (i = 0; i < size; i++) + if (data[i] != nil) + [data[i] release]; + + [super dealloc]; +} @end ADDED src/OFMutableDictionary.h Index: src/OFMutableDictionary.h ================================================================== --- src/OFMutableDictionary.h +++ src/OFMutableDictionary.h @@ -0,0 +1,18 @@ +/* + * Copyright (c) 2008 - 2009 + * Jonathan Schleifer + * + * All rights reserved. + * + * This file is part of libobjfw. It may be distributed under the terms of the + * Q Public License 1.0, which can be found in the file LICENSE included in + * the packaging of this file. + */ + +#import "OFDictionary.h" + +/** + * The OFMutableDictionary class provides a class for using mutable hash tables. + */ +@interface OFMutableDictionary: OFDictionary +@end ADDED src/OFMutableDictionary.m Index: src/OFMutableDictionary.m ================================================================== --- src/OFMutableDictionary.m +++ src/OFMutableDictionary.m @@ -0,0 +1,144 @@ +/* + * Copyright (c) 2008 - 2009 + * Jonathan Schleifer + * + * All rights reserved. + * + * This file is part of libobjfw. It may be distributed under the terms of the + * Q Public License 1.0, which can be found in the file LICENSE included in + * the packaging of this file. + */ + +#import "config.h" + +#include + +#import "OFMutableDictionary.h" +#import "OFExceptions.h" +#import "OFMacros.h" + +@implementation OFMutableDictionary +- set: (OFObject *)key + to: (OFObject*)obj +{ + uint32_t hash; + of_list_object_t *iter, *key_obj; + + if (key == nil || obj == nil) + @throw [OFInvalidArgumentException newWithClass: isa + andSelector: _cmd]; + + hash = [key hash] & (size - 1); + + if (data[hash] == nil) + data[hash] = [[OFList alloc] init]; + + for (iter = [data[hash] first]; iter != NULL; iter = iter->next->next) { + if ([iter->object isEqual: key]) { + [iter->next->object release]; + [obj retain]; + iter->next->object = obj; + + return self; + } + } + + key = [key copy]; + @try { + key_obj = [data[hash] append: key]; + } @finally { + [key release]; + } + + @try { + [data[hash] append: obj]; + } @catch (OFException *e) { + [data[hash] remove: key_obj]; + @throw e; + } + + return self; +} + +- remove: (OFObject*)key +{ + uint32_t hash; + of_list_object_t *iter; + + if (key == nil) + @throw [OFInvalidArgumentException newWithClass: isa + andSelector: _cmd]; + + hash = [key hash] & (size - 1); + + if (data[hash] == nil) + return self; + + for (iter = [data[hash] first]; iter != NULL; iter = iter->next->next) { + if ([iter->object isEqual: key]) { + [data[hash] remove: iter->next]; + [data[hash] remove: iter]; + + if ([data[hash] first] == NULL) { + [data[hash] release]; + data[hash] = nil; + } + + return self; + } + } + + return self; +} + +- changeHashSize: (int)hashsize +{ + OFList **newdata; + size_t newsize, i; + of_list_object_t *iter; + + if (hashsize < 8 || hashsize >= 28) + @throw [OFInvalidArgumentException newWithClass: isa + andSelector: _cmd]; + + newsize = (size_t)1 << hashsize; + newdata = [self allocNItems: newsize + withSize: sizeof(OFList*)]; + memset(data, 0, newsize * sizeof(OFList*)); + + for (i = 0; i < size; i++) { + if (OF_LIKELY(data[i] == nil)) + continue; + + for (iter = [data[i] first]; iter != NULL; + iter = iter->next->next) { + uint32_t hash = [iter->object hash] & (newsize - 1); + + if (newdata[hash] == nil) + newdata[hash] = [[OFList alloc] init]; + + [newdata[hash] append: iter->object]; + [newdata[hash] append: iter->next->object]; + } + + [data[i] release]; + } + + [self freeMem: data]; + data = newdata; + size = newsize; + + return self; +} + +/* FIXME: Implement this! */ +/* +- (id)copy +{ +} + +- (id)mutableCopy +{ +} +*/ +@end Index: tests/OFDictionary/OFDictionary.m ================================================================== --- tests/OFDictionary/OFDictionary.m +++ tests/OFDictionary/OFDictionary.m @@ -20,11 +20,11 @@ #import "OFExceptions.h" int main() { - OFDictionary *dict = [OFDictionary dictionaryWithHashSize: 16]; + OFDictionary *dict = [OFMutableDictionary dictionaryWithHashSize: 16]; OFIterator *iter = [dict iterator]; OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; OFString *key1 = [OFString stringWithCString: "key1"]; OFString *key2 = [OFString stringWithCString: "key2"];