Index: src/OFDictionary.h ================================================================== --- src/OFDictionary.h +++ src/OFDictionary.h @@ -12,10 +12,21 @@ #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; /** * The OFDictionary class provides a class for using hash tables. */ @interface OFDictionary: OFObject Index: src/OFDictionary.m ================================================================== --- src/OFDictionary.m +++ src/OFDictionary.m @@ -116,11 +116,11 @@ - initWithKey: (OFObject *)key andObject: (OFObject*)obj { Class c; - uint32_t hash; + uint32_t fullhash, hash; self = [self init]; if (key == nil || obj == nil) { c = isa; @@ -127,29 +127,33 @@ [self dealloc]; @throw [OFInvalidArgumentException newWithClass: isa andSelector: _cmd]; } - hash = [key hash] & (size - 1); + fullhash = [key hash]; + hash = fullhash & (size - 1); @try { key = [key copy]; } @catch (OFException *e) { [self dealloc]; @throw e; } @try { - data[hash] = [[OFList alloc] init]; + of_dictionary_list_object_t *o; + + data[hash] = [[OFList alloc] initWithListObjectSize: + sizeof(of_dictionary_list_object_t)]; - [data[hash] append: key]; - [data[hash] append: obj]; + 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; - } @finally { - [key release]; } return self; } @@ -173,40 +177,46 @@ keys_data = [keys data]; objs_data = [objs data]; for (i = 0; i < count; i++) { - uint32_t hash; + uint32_t fullhash, hash; OFObject *key; if (keys_data[i] == nil || objs_data[i] == nil) { c = isa; [self dealloc]; @throw [OFInvalidArgumentException newWithClass: isa andSelector: _cmd]; } - hash = [keys_data[i] hash] & (size - 1); + 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] init]; + data[hash] = [[OFList alloc] + initWithListObjectSize: + sizeof(of_dictionary_list_object_t)]; - [data[hash] append: key]; - [data[hash] append: objs_data[i]]; + 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; - } @finally { - [key release]; } } return self; } @@ -228,11 +238,11 @@ andArgList: (va_list)args { OFObject *key; OFObject *obj; Class c; - uint32_t hash; + uint32_t fullhash, hash; self = [self init]; obj = va_arg(args, OFObject*); if (first == nil || obj == nil) { @@ -240,30 +250,34 @@ [self dealloc]; @throw [OFInvalidArgumentException newWithClass: isa andSelector: _cmd]; } - hash = [first hash] & (size - 1); + 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] init]; + data[hash] = [[OFList alloc] initWithListObjectSize: + sizeof(of_dictionary_list_object_t)]; - [data[hash] append: key]; - [data[hash] append: obj]; + 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; - } @finally { - [key release]; } while ((key = va_arg(args, OFObject *)) != nil) { if ((obj = va_arg(args, OFObject*)) == nil) { c = isa; @@ -270,30 +284,36 @@ [self dealloc]; @throw [OFInvalidArgumentException newWithClass: isa andSelector: _cmd]; } - hash = [key hash] & (size - 1); + 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] init]; + data[hash] = [[OFList alloc] + initWithListObjectSize: + sizeof(of_dictionary_list_object_t)]; - [data[hash] append: key]; - [data[hash] append: obj]; + 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; - } @finally { - [key release]; } } return self; } @@ -305,11 +325,11 @@ items = 0; buckets = 0; for (i = 0; i < size; i++) { if (data[i] != nil) { - items += [data[i] count] / 2; + items += [data[i] count]; buckets++; } } return (float)items / buckets; @@ -316,11 +336,11 @@ } - (id)objectForKey: (OFObject*)key { uint32_t hash; - of_list_object_t *iter; + of_dictionary_list_object_t *iter; if (key == nil) @throw [OFInvalidArgumentException newWithClass: isa andSelector: _cmd]; @@ -327,13 +347,14 @@ hash = [key hash] & (size - 1); if (data[hash] == nil) return nil; - for (iter = [data[hash] first]; iter != NULL; iter = iter->next->next) - if ([iter->object isEqual: key]) - return iter->next->object; + 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; } /* FIXME: Implement this! */ @@ -353,13 +374,21 @@ - (void)dealloc { size_t i; - for (i = 0; i < size; i++) - if (data[i] != nil) + 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]; + } + } [super dealloc]; } - setObject: (OFObject*)obj Index: src/OFIterator.h ================================================================== --- src/OFIterator.h +++ src/OFIterator.h @@ -10,10 +10,15 @@ */ #import "OFObject.h" #import "OFList.h" #import "OFDictionary.h" + +typedef struct __of_iterator_pair { + id key; + id object; +} of_iterator_pair_t; extern int _OFIterator_reference; /** * The OFIterator class provides methods to iterate through objects. @@ -20,32 +25,21 @@ */ @interface OFIterator: OFObject { OFList **data; size_t size; - size_t pos; - of_list_object_t *last; + size_t pos; + of_dictionary_list_object_t *last; } - initWithData: (OFList**)data andSize: (size_t)size; /** - * Returns the next object in the dictionary. - * - * Always call it twice in a row, as it returns the key on the first call and - * the value on the second. Therefore, if you want a key value pair, you have - * to call: - * - * key = [iter nextObject];\n - * value = [iter nextObject]; - * - * When there is no more object left, an OFNotInSetException is thrown. - * - * \return The key on the first call and the value on the second + * \return A struct containing the next key and object */ -- (id)nextObject; +- (of_iterator_pair_t)nextKeyObjectPair; /** * Resets the iterator, so the next call to nextObject returns the first again. */ - reset; Index: src/OFIterator.m ================================================================== --- src/OFIterator.m +++ src/OFIterator.m @@ -30,24 +30,36 @@ last = NULL; return self; } -- (id)nextObject -{ - if (last == NULL) { - for (; pos < size && data[pos] == nil; pos++); - if (pos == size) - return nil; - - return (last = [data[pos++] first])->object; - } - - if ((last = last->next) != NULL) - return last->object; - - return [self nextObject]; +- (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; + return next; + } + + last = (of_dictionary_list_object_t*) + [data[pos++] first]; + next.key = last->key; + next.object = last->object; + return next; + } + + if ((last = last->next) != NULL) { + next.key = last->key; + next.object = last->object; + return next; + } + } } - reset { pos = 0; Index: src/OFList.h ================================================================== --- src/OFList.h +++ src/OFList.h @@ -11,29 +11,44 @@ #import "OFObject.h" typedef struct __of_list_object { - id object; struct __of_list_object *next; struct __of_list_object *prev; + id object; } of_list_object_t; /** * The OFList class provides easy to use double-linked lists. */ @interface OFList: OFObject { of_list_object_t *first; of_list_object_t *last; + size_t listobj_size; 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/releas objects * added to it.. * * \return An initialized OFList Index: src/OFList.m ================================================================== --- src/OFList.m +++ src/OFList.m @@ -17,17 +17,36 @@ @implementation OFList + 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; } @@ -35,10 +54,11 @@ { self = [super init]; first = NULL; last = NULL; + listobj_size = sizeof(of_list_object_t); return self; } - (void)dealloc @@ -63,11 +83,11 @@ - (of_list_object_t*)append: (id)obj { of_list_object_t *o; - o = [self allocMemoryWithSize: sizeof(of_list_object_t)]; + o = [self allocMemoryWithSize: listobj_size]; o->object = obj; o->next = NULL; o->prev = last; if (last != NULL) @@ -85,11 +105,11 @@ - (of_list_object_t*)prepend: (id)obj { of_list_object_t *o; - o = [self allocMemoryWithSize: sizeof(of_list_object_t)]; + o = [self allocMemoryWithSize: listobj_size]; o->object = obj; o->next = first; o->prev = NULL; if (first != NULL) @@ -108,11 +128,11 @@ - (of_list_object_t*)insert: (id)obj before: (of_list_object_t*)listobj { of_list_object_t *o; - o = [self allocMemoryWithSize: sizeof(of_list_object_t)]; + o = [self allocMemoryWithSize: listobj_size]; o->object = obj; o->next = listobj; o->prev = listobj->prev; if (listobj->prev != NULL) @@ -132,11 +152,11 @@ - (of_list_object_t*)insert: (id)obj after: (of_list_object_t*)listobj { of_list_object_t *o; - o = [self allocMemoryWithSize: sizeof(of_list_object_t)]; + o = [self allocMemoryWithSize: listobj_size]; o->object = obj; o->next = listobj->next; o->prev = listobj; if (listobj->next != NULL) @@ -216,11 +236,11 @@ o = NULL; prev = NULL; @try { for (iter = first; iter != NULL; iter = iter->next) { - o = [new allocMemoryWithSize: sizeof(of_list_object_t)]; + o = [new allocMemoryWithSize: listobj_size]; o->object = iter->object; o->next = NULL; o->prev = prev; if (new->first == NULL) Index: src/OFMutableDictionary.m ================================================================== --- src/OFMutableDictionary.m +++ src/OFMutableDictionary.m @@ -19,53 +19,54 @@ @implementation OFMutableDictionary - setObject: (OFObject*)obj forKey: (OFObject *)key { - uint32_t hash; - of_list_object_t *iter, *key_obj; + uint32_t fullhash, hash; + of_dictionary_list_object_t *iter; if (key == nil || obj == nil) @throw [OFInvalidArgumentException newWithClass: isa andSelector: _cmd]; - hash = [key hash] & (size - 1); + fullhash = [key hash]; + hash = fullhash & (size - 1); if (data[hash] == nil) - data[hash] = [[OFList alloc] init]; + data[hash] = [[OFList alloc] initWithListObjectSize: + sizeof(of_dictionary_list_object_t)]; - 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; + for (iter = (of_dictionary_list_object_t*)[data[hash] first]; + iter != NULL; iter = iter->next) { + if ([iter->key isEqual: key]) { + [iter->object release]; + iter->object = [obj retain]; return self; } } key = [key copy]; - @try { - key_obj = [data[hash] append: key]; - } @finally { - [key release]; - } @try { - [data[hash] append: obj]; + 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) { - [data[hash] remove: key_obj]; + [key release]; @throw e; } return self; } - removeObjectForKey: (OFObject*)key { uint32_t hash; - of_list_object_t *iter; + of_dictionary_list_object_t *iter; if (key == nil) @throw [OFInvalidArgumentException newWithClass: isa andSelector: _cmd]; @@ -72,14 +73,15 @@ hash = [key hash] & (size - 1); if (data[hash] == nil) return self; - for (iter = [data[hash] first]; iter != NULL; iter = iter->next->next) { + for (iter = (of_dictionary_list_object_t*)[data[hash] first]; + iter != NULL; iter = iter->next) { if ([iter->object isEqual: key]) { - [data[hash] remove: iter->next]; - [data[hash] remove: iter]; + [iter->key release]; + [data[hash] remove: (of_list_object_t*)iter]; if ([data[hash] first] == NULL) { [data[hash] release]; data[hash] = nil; } @@ -93,11 +95,11 @@ - changeHashSize: (int)hashsize { OFList **newdata; size_t newsize, i; - of_list_object_t *iter; + of_dictionary_list_object_t *iter; if (hashsize < 8 || hashsize >= 28) @throw [OFInvalidArgumentException newWithClass: isa andSelector: _cmd]; @@ -108,19 +110,24 @@ 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); + 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] init]; + newdata[hash] = [[OFList alloc] + initWithListObjectSize: + sizeof(of_dictionary_list_object_t)]; - [newdata[hash] append: iter->object]; - [newdata[hash] append: iter->next->object]; + o = (of_dictionary_list_object_t*) + [newdata[hash] append: iter->object]; + o->key = iter->key; + o->hash = iter->hash; } [data[i] release]; } Index: src/OFXMLElement.m ================================================================== --- src/OFXMLElement.m +++ src/OFXMLElement.m @@ -58,11 +58,10 @@ { OFAutoreleasePool *pool = [[OFAutoreleasePool alloc] init]; char *str_c; size_t len, i, j; OFString *ret, *tmp; - OFIterator *iter; len = [name length] + 4; str_c = [self allocMemoryWithSize: len]; /* Start of tag */ @@ -69,41 +68,44 @@ *str_c = '<'; memcpy(str_c + 1, [name cString], [name length]); i = [name length] + 1; /* Attributes */ - iter = [attrs iterator]; - for (;;) { - OFString *key, *val; - - key = [iter nextObject]; - val = [iter nextObject]; - - if (key == nil || val == nil) - break; - - tmp = [val stringByXMLEscaping]; - - len += [key length] + [tmp length] + 4; - @try { - str_c = [self resizeMemory: str_c - toSize: len]; - } @catch (OFException *e) { - [self freeMemory: str_c]; - @throw e; - } - - str_c[i++] = ' '; - memcpy(str_c + i, [key cString], [key length]); - i += [key length]; - str_c[i++] = '='; - str_c[i++] = '\''; - memcpy(str_c + i, [tmp cString], [tmp length]); - i += [tmp length]; - str_c[i++] = '\''; - - [pool releaseObjects]; + if (attrs != nil) { + OFIterator *iter = [attrs iterator]; + + for (;;) { + of_iterator_pair_t pair; + + pair = [iter nextKeyObjectPair]; + + if (pair.key == nil || pair.object == nil) + break; + + tmp = [pair.object stringByXMLEscaping]; + + len += [pair.key length] + [tmp length] + 4; + @try { + str_c = [self resizeMemory: str_c + toSize: len]; + } @catch (OFException *e) { + [self freeMemory: str_c]; + @throw e; + } + + str_c[i++] = ' '; + memcpy(str_c + i, [pair.key cString], + [pair.key length]); + i += [pair.key length]; + str_c[i++] = '='; + str_c[i++] = '\''; + memcpy(str_c + i, [tmp cString], [tmp length]); + i += [tmp length]; + str_c[i++] = '\''; + + [pool releaseObjects]; + } } /* Childen */ if (stringval != nil || children != nil) { if (stringval != nil) Index: tests/OFDictionary/OFDictionary.m ================================================================== --- tests/OFDictionary/OFDictionary.m +++ tests/OFDictionary/OFDictionary.m @@ -26,10 +26,11 @@ { int i = 0; OFDictionary *dict = [OFMutableDictionary dictionaryWithHashSize: 16]; OFIterator *iter = [dict iterator]; + 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"]; @@ -52,25 +53,29 @@ printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS); return 1; } i++; - if (![[iter nextObject] isEqual: @"key2"] || - ![[iter nextObject] isEqual: @"value2"] || - ![[iter nextObject] isEqual: @"key1"] || - ![[iter nextObject] isEqual: @"value1"]) { + 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]; - if (![[iter nextObject] isEqual: @"key1"] || - ![[iter nextObject] isEqual: @"value1"] || - ![[iter nextObject] isEqual: @"key2"] || - ![[iter nextObject] isEqual: @"value2"]) { + pair[0] = [iter nextKeyObjectPair]; + pair[1] = [iter nextKeyObjectPair]; + if (![pair[0].key isEqual: @"key1"] || + ![pair[0].object isEqual: @"value1"] || + ![pair[1].key isEqual: @"key2"] || + ![pair[1].object isEqual: @"value2"]) { printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS); return 1; } i++; @@ -78,11 +83,11 @@ printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS); return 1; } i++; - if ([iter nextObject] != nil) { + if ([iter nextKeyObjectPair].object != nil) { printf("\033[K\033[1;31mTest %d/%d failed!\033[m\n", i, TESTS); return 1; } i++;