Index: src/OFDictionary.h ================================================================== --- src/OFDictionary.h +++ src/OFDictionary.h @@ -10,35 +10,31 @@ */ #include #import "OFObject.h" -#import "OFList.h" #import "OFArray.h" -typedef struct __of_dictionary_list_object -{ - /* of_list_object_t */ - struct __of_dictionary_list_object *next; - struct __of_dictionary_list_object *prev; - id object; - /* OFDictionary additions */ - id key; - uint32_t hash; -} of_dictionary_list_object_t; +struct of_dictionary_bucket +{ + OFObject *key; + OFObject *object; + uint32_t hash; +}; /** * The OFDictionary class provides a class for using hash tables. */ @interface OFDictionary: OFObject { - OFList **data; - size_t size; + struct of_dictionary_bucket *data; + size_t size; + size_t count; } /** - * Creates a new OFDictionary, defaulting to a 12 bit hash. + * Creates a new OFDictionary. * * \return A new autoreleased OFDictionary */ + dictionary; @@ -48,18 +44,10 @@ * \param dict An OFDictionary * \return A new autoreleased OFDictionary */ + dictionaryWithDictionary: (OFDictionary*)dict; -/** - * Creates a new OFDictionary with a hash of N bits. - * - * \param bits The size of the hash to use - * \return A new autoreleased OFDictionary - */ -+ dictionaryWithHashSize: (int)hashsize; - /** * Creates a new OFDictionary with the specified key and object. * * \param key The key * \param obj The object @@ -79,17 +67,17 @@ forKeys: (OFArray*)keys; /** * Creates a new OFDictionary with the specified keys objects. * - * \param first The first key + * \param key The first key * \return A new autoreleased OFDictionary */ -+ dictionaryWithKeysAndObjects: (OFObject *)first, ...; ++ dictionaryWithKeysAndObjects: (OFObject *)key, ...; /** - * Initializes an already allocated OFDictionary, defaulting to a 12 bit hash. + * Initializes an already allocated OFDictionary. * * \return An initialized OFDictionary */ - init; @@ -100,18 +88,10 @@ * \param dict An OFDictionary * \return An initialized OFDictionary */ - initWithDictionary: (OFDictionary*)dict; -/** - * Initializes an already allocated OFDictionary with a hash of N bits. - * - * \param bits The size of the hash to use - * \return An initialized OFDictionary - */ -- initWithHashSize: (int)hashsize; - /** * Initializes an already allocated OFDictionary with the specified key and * object. * * \param key The key @@ -149,26 +129,23 @@ * \return A new initialized OFDictionary */ - initWithKey: (OFObject *)first argList: (va_list)args; -/** - * \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)objectForKey: (OFObject*)key; +- (id)objectForKey: (OFObject *)key; + +/** + * \return The number of objects in the dictionary + */ +- (size_t)count; - setObject: (OFObject*)obj forKey: (OFObject *)key; - removeObjectForKey: (OFObject*)key; -- changeHashSize: (int)hashsize; @end #import "OFIterator.h" #import "OFMutableDictionary.h" Index: src/OFDictionary.m ================================================================== --- src/OFDictionary.m +++ src/OFDictionary.m @@ -16,10 +16,12 @@ #import "OFDictionary.h" #import "OFIterator.h" #import "OFAutoreleasePool.h" #import "OFExceptions.h" +#define BUCKET_SIZE sizeof(struct of_dictionary_bucket) + /* References for static linking */ void _references_to_categories_of_OFDictionary() { _OFIterator_reference = 1; } @@ -33,15 +35,10 @@ + dictionaryWithDictionary: (OFDictionary*)dict { return [[[self alloc] initWithDictionary: dict] autorelease]; } -+ dictionaryWithHashSize: (int)hashsize -{ - return [[[self alloc] initWithHashSize: hashsize] autorelease]; -} - + dictionaryWithObject: (OFObject*)obj forKey: (OFObject *)key { return [[[self alloc] initWithObject: obj forKey: key] autorelease]; @@ -69,35 +66,31 @@ - init { self = [super init]; - size = 4096; + size = 1; @try { - data = [self allocMemoryForNItems: size - withSize: sizeof(OFList*)]; + data = [self allocMemoryWithSize: BUCKET_SIZE]; } @catch (OFException *e) { /* * We can't use [super dealloc] on OS X here. Compiler bug? * Anyway, set size to 0 so that [self dealloc] works. */ size = 0; [self dealloc]; @throw e; } - memset(data, 0, size * sizeof(OFList*)); + data[0].key = nil; return self; } - initWithDictionary: (OFDictionary*)dict { - OFAutoreleasePool *pool; - OFIterator *iter; - of_iterator_pair_t pair; - of_iterator_pair_t (*next)(id, SEL); + size_t i; self = [super init]; if (dict == nil) { Class c = isa; @@ -105,139 +98,47 @@ [self dealloc]; @throw [OFInvalidArgumentException newWithClass: c selector: _cmd]; } - size = dict->size; - - @try { - data = [self allocMemoryForNItems: size - withSize: sizeof(OFList*)]; - memset(data, 0, size * sizeof(OFList*)); - - pool = [[OFAutoreleasePool alloc] init]; - iter = [dict iterator]; - next = (of_iterator_pair_t(*)(id, SEL)) - [iter methodForSelector: @selector(nextKeyObjectPair)]; - } @catch (OFException *e) { - /* - * We can't use [super dealloc] on OS X here. Compiler bug? - * Anyway, set size to 0 so that [self dealloc] works. - */ - size = 0; - [self dealloc]; - @throw e; - } - - for (;;) { - uint32_t hash; - OFObject *key; - - pair = next(iter, @selector(nextKeyObjectPair)); - - if (pair.key == nil || pair.object == nil) - break; - - hash = pair.hash & (size - 1); - - @try { - key = [pair.key copy]; - } @catch (OFException *e) { - [self dealloc]; - @throw e; - } - - @try { - of_dictionary_list_object_t *o; - - if (data[hash] == nil) - data[hash] = [[OFList alloc] - initWithListObjectSize: - sizeof(of_dictionary_list_object_t)]; - - o = (of_dictionary_list_object_t*) - [data[hash] append: pair.object]; - o->key = key; - o->hash = pair.hash; - } @catch (OFException *e) { - [key release]; - [self dealloc]; - @throw e; - } - } - - [pool release]; - - return self; -} - -- initWithHashSize: (int)hashsize -{ - self = [super init]; - - if (hashsize < 8 || hashsize >= 28) { - Class c = isa; - [super dealloc]; - @throw [OFInvalidArgumentException newWithClass: c - selector: _cmd]; - } - - size = (size_t)1 << hashsize; - - @try { - data = [self allocMemoryForNItems: size - withSize: sizeof(OFList*)]; - } @catch (OFException *e) { - /* - * We can't use [super dealloc] on OS X here. Compiler bug? - * Anyway, set size to 0 so that [self dealloc] works. - */ - size = 0; - [self dealloc]; - @throw e; - } - memset(data, 0, size * sizeof(OFList*)); + @try { + data = [self allocMemoryForNItems: dict->size + withSize: BUCKET_SIZE]; + } @catch (OFException *e) { + /* + * We can't use [super dealloc] on OS X here. Compiler bug? + * Anyway, we didn't do anything yet anyway, so [self dealloc] + * works. + */ + [self dealloc]; + @throw e; + } + size = dict->size; + + for (i = 0; i < size; i++) { + if (dict->data[i].key != nil) { + data[i].key = [dict->data[i].key copy]; + data[i].object = [dict->data[i].object retain]; + data[i].hash = dict->data[i].hash; + } else + data[i].key = nil; + } return self; } - initWithObject: (OFObject*)obj forKey: (OFObject *)key { - Class c; - uint32_t fullhash, hash; + const SEL sel = @selector(setObject:forKey:); + IMP set = [OFMutableDictionary instanceMethodForSelector: sel]; self = [self init]; - if (key == nil || obj == nil) { - c = isa; - [self dealloc]; - @throw [OFInvalidArgumentException newWithClass: isa - selector: _cmd]; - } - - fullhash = [key hash]; - hash = fullhash & (size - 1); - - @try { - key = [key copy]; - } @catch (OFException *e) { - [self dealloc]; - @throw e; - } - - @try { - of_dictionary_list_object_t *o; - - data[hash] = [[OFList alloc] initWithListObjectSize: - sizeof(of_dictionary_list_object_t)]; - - o = (of_dictionary_list_object_t*)[data[hash] append: obj]; - o->key = key; - o->hash = fullhash; - } @catch (OFException *e) { - [key release]; + @try { + set(self, sel, obj, key); + } @catch (OFException *e) { [self dealloc]; @throw e; } return self; @@ -244,66 +145,34 @@ } - initWithObjects: (OFArray*)objs forKeys: (OFArray*)keys { - Class c; - OFObject **keys_data; - OFObject **objs_data; - size_t count, i; - - self = [self init]; - count = [keys count]; - - if (keys == nil || objs == nil || count != [objs count]) { - c = isa; - [self dealloc]; - @throw [OFInvalidArgumentException newWithClass: isa - selector: _cmd]; - } - - keys_data = [keys data]; - objs_data = [objs data]; - - for (i = 0; i < count; i++) { - uint32_t fullhash, hash; - OFObject *key; - - if (keys_data[i] == nil || objs_data[i] == nil) { - c = isa; - [self dealloc]; - @throw [OFInvalidArgumentException newWithClass: isa - selector: _cmd]; - } - - fullhash = [keys_data[i] hash]; - hash = fullhash & (size - 1); - - @try { - key = [keys_data[i] copy]; - } @catch (OFException *e) { - [self dealloc]; - @throw e; - } - - @try { - of_dictionary_list_object_t *o; - - if (data[hash] == nil) - data[hash] = [[OFList alloc] - initWithListObjectSize: - sizeof(of_dictionary_list_object_t)]; - - o = (of_dictionary_list_object_t*) - [data[hash] append: objs_data[i]]; - o->key = key; - o->hash = fullhash; - } @catch (OFException *e) { - [key release]; - [self dealloc]; - @throw e; - } + id *objs_data, *keys_data; + size_t objs_count, i; + const SEL sel = @selector(setObject:forKey:); + IMP set = [OFMutableDictionary instanceMethodForSelector: sel]; + + self = [self init]; + + objs_data = [objs data]; + keys_data = [keys data]; + objs_count = [objs count]; + + if (objs == nil || keys == nil || objs_count != [keys count]) { + Class c = isa; + [self dealloc]; + @throw [OFInvalidArgumentException newWithClass: c + selector: _cmd]; + } + + @try { + for (i = 0; i < objs_count; i++) + set(self, sel, objs_data[i], keys_data[i]); + } @catch (OFException *e) { + [self dealloc]; + @throw e; } return self; } @@ -318,131 +187,58 @@ va_end(args); return ret; } -- initWithKey: (OFObject *)first - argList: (va_list)args -{ - OFObject *key; - OFObject *obj; - Class c; - uint32_t fullhash, hash; - - self = [self init]; - obj = va_arg(args, OFObject*); - - if (first == nil || obj == nil) { - c = isa; - [self dealloc]; - @throw [OFInvalidArgumentException newWithClass: isa - selector: _cmd]; - } - - fullhash = [first hash]; - hash = fullhash & (size - 1); - - @try { - key = [first copy]; - } @catch (OFException *e) { - [self dealloc]; - @throw e; - } - - @try { - of_dictionary_list_object_t *o; - - if (data[hash] == nil) - data[hash] = [[OFList alloc] initWithListObjectSize: - sizeof(of_dictionary_list_object_t)]; - - o = (of_dictionary_list_object_t*)[data[hash] append: obj]; - o->key = key; - o->hash = fullhash; - } @catch (OFException *e) { - [key release]; - [self dealloc]; - @throw e; - } - - while ((key = va_arg(args, OFObject *)) != nil) { - if ((obj = va_arg(args, OFObject*)) == nil) { - c = isa; - [self dealloc]; - @throw [OFInvalidArgumentException newWithClass: isa - selector: _cmd]; - } - - fullhash = [key hash]; - hash = fullhash & (size - 1); - - @try { - key = [key copy]; - } @catch (OFException *e) { - [self dealloc]; - @throw e; - } - - @try { - of_dictionary_list_object_t *o; - - if (data[hash] == nil) - data[hash] = [[OFList alloc] - initWithListObjectSize: - sizeof(of_dictionary_list_object_t)]; - - o = (of_dictionary_list_object_t*) - [data[hash] append: obj]; - o->key = key; - o->hash = fullhash; - } @catch (OFException *e) { - [key release]; - [self dealloc]; - @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] count]; - buckets++; - } - } - - return (float)items / buckets; -} - -- (id)objectForKey: (OFObject*)key -{ - uint32_t hash; - of_dictionary_list_object_t *iter; - - if (key == nil) - @throw [OFInvalidArgumentException newWithClass: isa - selector: _cmd]; - - hash = [key hash] & (size - 1); - - if (data[hash] == nil) - return nil; - - for (iter = (of_dictionary_list_object_t*)[data[hash] first]; - iter != NULL; iter = iter->next) - if ([iter->key isEqual: key]) - return iter->object; - - return nil; +- initWithKey: (OFObject *)key + argList: (va_list)args +{ + const SEL sel = @selector(setObject:forKey:); + IMP set = [OFMutableDictionary instanceMethodForSelector: sel]; + + self = [self init]; + + @try { + set(self, sel, va_arg(args, OFObject*), key); + while ((key = va_arg(args, OFObject *)) != nil) + set(self, sel, va_arg(args, OFObject*), key); + } @catch (OFException *e) { + [self dealloc]; + @throw e; + } + + return self; +} + +- (id)objectForKey: (OFObject *)key +{ + uint32_t i, hash; + + if (key == nil) + @throw [OFInvalidArgumentException newWithClass: isa + selector: _cmd]; + + hash = [key hash]; + + for (i = hash & (size - 1); i < size && data[i].key != nil && + ![data[i].key isEqual: key]; i++); + + /* In case the last bucket is already used */ + if (i >= size) + for (i = 0; i < size && data[i].key != nil && + ![data[i].key isEqual: key]; i++); + + /* Key not in dictionary */ + if (i >= size || data[i].key == nil) + return nil; + + return data[i].object; +} + +- (size_t)count +{ + return count; } - (id)copy { return [self retain]; @@ -462,18 +258,13 @@ - (void)dealloc { size_t i; for (i = 0; i < size; i++) { - if (data[i] != nil) { - of_dictionary_list_object_t *iter; - - for (iter = (of_dictionary_list_object_t*) - [data[i] first]; iter != NULL; iter = iter->next) - [iter->key release]; - - [data[i] release]; + if (data[i].key != nil) { + [data[i].key release]; + [data[i].object release]; } } [super dealloc]; } @@ -485,15 +276,9 @@ selector: _cmd]; } - removeObjectForKey: (OFObject*)key { - @throw [OFNotImplementedException newWithClass: isa - selector: _cmd]; -} - -- changeHashSize: (int)hashsize -{ @throw [OFNotImplementedException newWithClass: isa selector: _cmd]; } @end Index: src/OFIterator.h ================================================================== --- src/OFIterator.h +++ src/OFIterator.h @@ -19,28 +19,25 @@ typedef struct __of_iterator_pair { /// The key id key; /// The object for the key id object; - /// The hash of the key - uint32_t hash; } of_iterator_pair_t; extern int _OFIterator_reference; /** * The OFIterator class provides methods to iterate through objects. */ @interface OFIterator: OFObject { - OFList **data; - size_t size; + struct of_dictionary_bucket *data; + size_t size; size_t pos; - of_dictionary_list_object_t *last; } -- initWithData: (OFList**)data +- initWithData: (struct of_dictionary_bucket*)data size: (size_t)size; /** * \return A struct containing the next key and object */ @@ -52,9 +49,20 @@ - reset; @end @interface OFDictionary (OFIterator) /** + * Creates an OFIterator for the dictionary. + * + * It will copy the data of the OFDictionary so that OFIterator will always + * operate on the data that was present when it was created. If you changed the + * OFDictionary and want to operate on the new data, you need to create a new + * OFIterator, as using reset will only reset the OFIterator, but won't update + * the data. It will also retain the data inside the OFDictionary so the + * OFIterator still works after you released the OFDictionary. Thus, if you want + * to get rid of the objects in the OFDictionary, you also need to release the + * OFIterator. + * * \return An OFIterator for the OFDictionary */ - (OFIterator*)iterator; @end Index: src/OFIterator.m ================================================================== --- src/OFIterator.m +++ src/OFIterator.m @@ -23,58 +23,67 @@ { @throw [OFNotImplementedException newWithClass: isa selector: _cmd]; } -- initWithData: (OFList**)data_ +- initWithData: (struct of_dictionary_bucket*)data_ size: (size_t)size_ { + size_t i; + self = [super init]; - data = data_; size = size_; + data = [self allocMemoryForNItems: size + withSize: sizeof(struct of_dictionary_bucket)]; - last = NULL; + for (i = 0; i < size; i++) { + if (data_[i].key != nil) { + data[i].key = [data_[i].key copy]; + data[i].object = [data_[i].object retain]; + } else + data[i].key = nil; + } return self; } + +- (void)dealloc +{ + size_t i; + + for (i = 0; i < size; i++) { + if (data[i].key != nil) { + [data[i].key release]; + [data[i].object release]; + } + } + + [super dealloc]; +} - (of_iterator_pair_t)nextKeyObjectPair { of_iterator_pair_t next; - for (;;) { - if (last == NULL) { - for (; pos < size && data[pos] == nil; pos++); - if (pos == size) { - next.key = nil; - next.object = nil; - next.hash = 0; - return next; - } - - last = (of_dictionary_list_object_t*) - [data[pos++] first]; - next.key = last->key; - next.object = last->object; - next.hash = last->hash; - return next; - } - - if ((last = last->next) != NULL) { - next.key = last->key; - next.object = last->object; - next.hash = last->hash; - return next; - } - } + for (; pos < size && data[pos].key == nil; pos++); + + if (pos < size) { + next.key = data[pos].key; + next.object = data[pos].object; + pos++; + } else { + next.key = nil; + next.object = nil; + } + + return next; } - reset { pos = 0; - last = NULL; return self; } @end Index: src/OFList.h ================================================================== --- src/OFList.h +++ src/OFList.h @@ -30,33 +30,19 @@ */ @interface OFList: OFObject { of_list_object_t *first; of_list_object_t *last; - size_t listobj_size; size_t count; BOOL retain_and_release; } + /** * \return A new autoreleased OFList */ + list; -/** - * \param listobj_size The size of a list object - * \return A new autoreleased OFList with the specified list object size - */ -+ listWithListObjectSize: (size_t)listobj_size; - -/** - * Initializes an already allocated OFList with the specified list object size. - * - * \param listobj_size The size of a list object - * \return An initialized OFList with the specified list object size - */ -- initWithListObjectSize: (size_t)listobj_size; - /** * Initializes an already allocated OFList that does not retain/release objects * added to it. * * \return An initialized OFList Index: src/OFList.m ================================================================== --- src/OFList.m +++ src/OFList.m @@ -20,35 +20,16 @@ + list { return [[[self alloc] init] autorelease]; } -+ listWithListObjectSize: (size_t)listobj_size_ -{ - return [[[self alloc] - initWithListObjectSize: listobj_size_] autorelease]; -} - - init { self = [super init]; first = NULL; last = NULL; - listobj_size = sizeof(of_list_object_t); - retain_and_release = YES; - - return self; -} - -- initWithListObjectSize: (size_t)listobj_size_; -{ - self = [super init]; - - first = NULL; - last = NULL; - listobj_size = listobj_size_; retain_and_release = YES; return self; } @@ -56,11 +37,10 @@ { self = [super init]; first = NULL; last = NULL; - listobj_size = sizeof(of_list_object_t); return self; } - (void)dealloc @@ -85,11 +65,11 @@ - (of_list_object_t*)append: (id)obj { of_list_object_t *o; - o = [self allocMemoryWithSize: listobj_size]; + o = [self allocMemoryWithSize: sizeof(of_list_object_t)]; o->object = obj; o->next = NULL; o->prev = last; if (last != NULL) @@ -109,11 +89,11 @@ - (of_list_object_t*)prepend: (id)obj { of_list_object_t *o; - o = [self allocMemoryWithSize: listobj_size]; + o = [self allocMemoryWithSize: sizeof(of_list_object_t)]; o->object = obj; o->next = first; o->prev = NULL; if (first != NULL) @@ -134,11 +114,11 @@ - (of_list_object_t*)insert: (id)obj before: (of_list_object_t*)listobj { of_list_object_t *o; - o = [self allocMemoryWithSize: listobj_size]; + o = [self allocMemoryWithSize: sizeof(of_list_object_t)]; o->object = obj; o->next = listobj; o->prev = listobj->prev; if (listobj->prev != NULL) @@ -160,11 +140,11 @@ - (of_list_object_t*)insert: (id)obj after: (of_list_object_t*)listobj { of_list_object_t *o; - o = [self allocMemoryWithSize: listobj_size]; + o = [self allocMemoryWithSize: sizeof(of_list_object_t)]; o->object = obj; o->next = listobj->next; o->prev = listobj; if (listobj->next != NULL) @@ -244,11 +224,11 @@ o = NULL; prev = NULL; @try { for (iter = first; iter != NULL; iter = iter->next) { - o = [new allocMemoryWithSize: listobj_size]; + o = [new allocMemoryWithSize: sizeof(of_list_object_t)]; o->object = iter->object; o->next = NULL; o->prev = prev; if (new->first == NULL) Index: src/OFMutableDictionary.h ================================================================== --- src/OFMutableDictionary.h +++ src/OFMutableDictionary.h @@ -28,13 +28,6 @@ * Remove the object with the given key from the dictionary. * * \param key The key whose object should be removed */ - removeObjectForKey: (OFObject*)key; - -/** - * Changes the hash size of the dictionary. - * - * \param hashsize The new hash size for the dictionary - */ -- changeHashSize: (int)hashsize; @end Index: src/OFMutableDictionary.m ================================================================== --- src/OFMutableDictionary.m +++ src/OFMutableDictionary.m @@ -14,133 +14,142 @@ #include #import "OFMutableDictionary.h" #import "OFExceptions.h" #import "OFMacros.h" + +#define BUCKET_SIZE sizeof(struct of_dictionary_bucket) + +static OF_INLINE void +resize(id self, size_t count, struct of_dictionary_bucket **data, size_t *size) +{ + float fill = (float)count / *size; + size_t newsize; + struct of_dictionary_bucket *newdata; + uint32_t i; + + /* + * FIXME: + * + * Throw an OFOutOfRangeException if it would overflow (unlikely to + * happen). + */ + if (fill > 0.75) + newsize = *size * 2; + else if (fill < 0.25) + newsize = *size / 2; + else + return; + + newdata = [self allocMemoryForNItems: newsize + withSize: BUCKET_SIZE]; + memset(newdata, 0, newsize * BUCKET_SIZE); + + for (i = 0; i < *size; i++) { + if ((*data)[i].key != nil) { + uint32_t j = (*data)[i].hash & (newsize - 1); + for (; j < newsize && newdata[j].key != nil; j++); + + /* In case the last bucket is already used */ + if (j >= newsize) + for (j = 0; j < newsize && + newdata[j].key != nil; i++); + if (j >= newsize) + @throw [OFOutOfRangeException + newWithClass: [self class]]; + + newdata[j].key = (*data)[i].key; + newdata[j].object = (*data)[i].object; + newdata[j].hash = (*data)[i].hash; + } + } + + [self freeMemory: *data]; + *data = newdata; + *size = newsize; +} @implementation OFMutableDictionary - setObject: (OFObject*)obj forKey: (OFObject *)key { - uint32_t fullhash, hash; - of_dictionary_list_object_t *iter; + uint32_t i, hash; if (key == nil || obj == nil) @throw [OFInvalidArgumentException newWithClass: isa selector: _cmd]; - fullhash = [key hash]; - hash = fullhash & (size - 1); - - if (data[hash] == nil) - data[hash] = [[OFList alloc] initWithListObjectSize: - sizeof(of_dictionary_list_object_t)]; - - for (iter = (of_dictionary_list_object_t*)[data[hash] first]; - iter != NULL; iter = iter->next) { - if ([iter->key isEqual: key]) { - [obj retain]; - [iter->object release]; - iter->object = obj; - - return self; - } - } - - key = [key copy]; - - @try { - of_dictionary_list_object_t *o; - - o = (of_dictionary_list_object_t*)[data[hash] append: obj]; - o->key = key; - o->hash = fullhash; - } @catch (OFException *e) { - [key release]; - @throw e; - } + hash = [key hash]; + + for (i = hash & (size - 1); i < size && data[i].key != nil && + ![data[i].key isEqual: key]; i++); + + /* In case the last bucket is already used */ + if (i >= size) + for (i = 0; i < size && data[i].key != nil && + ![data[i].key isEqual: key]; i++); + + /* Key not in dictionary */ + if (i >= size || data[i].key == nil) { + resize(self, count + 1, &data, &size); + + i = hash & (size - 1); + for (; i < size && data[i].key != nil; i++); + + /* In case the last bucket is already used */ + if (i >= size) + for (i = 0; i < size && data[i].key != nil; i++); + if (i >= size) + @throw [OFOutOfRangeException newWithClass: isa]; + + data[i].key = [key copy]; + data[i].object = [obj retain]; + data[i].hash = hash; + count++; + + return self; + } + + [obj retain]; + [data[i].object release]; + data[i].object = obj; return self; } - removeObjectForKey: (OFObject*)key { - uint32_t hash; - of_dictionary_list_object_t *iter; + uint32_t i, hash; if (key == nil) @throw [OFInvalidArgumentException newWithClass: isa selector: _cmd]; - hash = [key hash] & (size - 1); - - if (data[hash] == nil) - return self; - - for (iter = (of_dictionary_list_object_t*)[data[hash] first]; - iter != NULL; iter = iter->next) { - if ([iter->object isEqual: key]) { - [iter->key release]; - [data[hash] remove: (of_list_object_t*)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_dictionary_list_object_t *iter; - - if (hashsize < 8 || hashsize >= 28) - @throw [OFInvalidArgumentException newWithClass: isa - selector: _cmd]; - - newsize = (size_t)1 << hashsize; - newdata = [self allocMemoryForNItems: newsize - withSize: sizeof(OFList*)]; - memset(newdata, 0, newsize * sizeof(OFList*)); - - for (i = 0; i < size; i++) { - if (OF_LIKELY(data[i] == nil)) - continue; - - for (iter = (of_dictionary_list_object_t*)[data[i] first]; - iter != NULL; iter = iter->next) { - uint32_t hash = iter->hash & (newsize - 1); - of_dictionary_list_object_t *o; - - if (newdata[hash] == nil) - newdata[hash] = [[OFList alloc] - initWithListObjectSize: - sizeof(of_dictionary_list_object_t)]; - - o = (of_dictionary_list_object_t*) - [newdata[hash] append: iter->object]; - o->key = iter->key; - o->hash = iter->hash; - } - - [data[i] release]; - } - - [self freeMemory: data]; - data = newdata; - size = newsize; + hash = [key hash]; + + for (i = hash & (size - 1); i < size && data[i].key != nil && + ![data[i].key isEqual: key]; i++); + + /* In case the last bucket is already used */ + if (i >= size) + for (i = 0; i < size && data[i].key != nil && + ![data[i].key isEqual: key]; i++); + + /* Key not in dictionary */ + if (i >= size || data[i].key == nil) + return self; + + [data[i].key release]; + [data[i].object release]; + data[i].key = nil; + + count--; + resize(self, count, &data, &size); return self; } - (id)copy { return [[OFDictionary alloc] initWithDictionary: self]; } @end Index: tests/OFDictionary/OFDictionary.m ================================================================== --- tests/OFDictionary/OFDictionary.m +++ tests/OFDictionary/OFDictionary.m @@ -17,28 +17,28 @@ #import "OFAutoreleasePool.h" #import "OFDictionary.h" #import "OFString.h" #import "OFExceptions.h" -#define TESTS 15 +#define TESTS 14 int main() { int i = 0; - OFDictionary *dict = [OFMutableDictionary dictionaryWithHashSize: 16]; + OFDictionary *dict = [OFMutableDictionary dictionary]; OFDictionary *dict2; OFArray *keys, *objs; - OFIterator *iter = [dict iterator]; + OFIterator *iter; of_iterator_pair_t pair[2]; OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; - OFString *key1 = [OFString stringWithCString: "key1"]; - OFString *key2 = [OFString stringWithCString: "key2"]; - OFString *value1 = [OFString stringWithCString: "value1"]; - OFString *value2 = [OFString stringWithCString: "value2"]; + OFString *key1 = [OFString stringWithString: @"key1"]; + OFString *key2 = [OFString stringWithString: @"key2"]; + OFString *value1 = [OFString stringWithString: @"value1"]; + OFString *value2 = [OFString stringWithString: @"value2"]; [dict setObject: value1 forKey: key1]; [dict setObject: value2 forKey: key2]; @@ -55,22 +55,10 @@ printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS); return 1; } i++; - pair[0] = [iter nextKeyObjectPair]; - pair[1] = [iter nextKeyObjectPair]; - if (![pair[0].key isEqual: @"key2"] || - ![pair[0].object isEqual: @"value2"] || - ![pair[1].key isEqual: @"key1"] || - ![pair[1].object isEqual: @"value1"]) { - printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS); - return 1; - } - - i++; - [dict changeHashSize: 8]; iter = [dict iterator]; pair[0] = [iter nextKeyObjectPair]; pair[1] = [iter nextKeyObjectPair]; if (![pair[0].key isEqual: @"key1"] || ![pair[0].object isEqual: @"value1"] || @@ -79,11 +67,11 @@ printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS); return 1; } i++; - if ([dict averageItemsPerBucket] != 1.0) { + if ([dict count] != 2) { printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS); return 1; } i++; @@ -99,12 +87,12 @@ } i++; [dict release]; dict = [OFDictionary dictionaryWithKeysAndObjects: @"foo", @"bar", - @"baz", @"qux", - nil]; + @"baz", @"qux", + nil]; if (![[dict objectForKey: @"foo"] isEqual: @"bar"]) { printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS); return 1; }