/* * Copyright (c) 2008 - 2010 * 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 included in * the packaging of this file. */ #include "config.h" #include <string.h> #import "OFDictionary.h" #import "OFEnumerator.h" #import "OFArray.h" #import "OFAutoreleasePool.h" #import "OFExceptions.h" #import "macros.h" const int of_dictionary_deleted_bucket = 0; #define BUCKET_SIZE sizeof(struct of_dictionary_bucket) #define DELETED (id)&of_dictionary_deleted_bucket @implementation OFDictionary + dictionary; { return [[[self alloc] init] autorelease]; } + dictionaryWithDictionary: (OFDictionary*)dict { return [[[self alloc] initWithDictionary: dict] autorelease]; } + dictionaryWithObject: (OFObject*)obj forKey: (OFObject <OFCopying>*)key { return [[[self alloc] initWithObject: obj forKey: key] autorelease]; } + dictionaryWithObjects: (OFArray*)objs forKeys: (OFArray*)keys { return [[[self alloc] initWithObjects: objs forKeys: keys] autorelease]; } + dictionaryWithKeysAndObjects: (OFObject <OFCopying>*)first, ... { id ret; va_list args; va_start(args, first); ret = [[[self alloc] initWithKey: first argList: args] autorelease]; va_end(args); return ret; } - init { self = [super init]; size = 1; @try { 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; } data[0].key = nil; return self; } - initWithDictionary: (OFDictionary*)dict { size_t i; self = [super init]; if (dict == nil) { Class c = isa; size = 0; [self dealloc]; @throw [OFInvalidArgumentException newWithClass: c selector: _cmd]; } @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; count = dict->count; for (i = 0; i < size; i++) { OFObject <OFCopying> *key; if (dict->data[i].key == nil || dict->data[i].key == DELETED) { data[i].key = nil; continue; } @try { key = [dict->data[i].key copy]; } @catch (OFException *e) { [self dealloc]; @throw e; } @try { [dict->data[i].object retain]; } @catch (OFException *e) { [key release]; [self dealloc]; @throw e; } data[i].key = key; data[i].object = dict->data[i].object; data[i].hash = dict->data[i].hash; } return self; } - initWithObject: (OFObject*)obj forKey: (OFObject <OFCopying>*)key { uint32_t i; self = [self init]; @try { data = [self allocMemoryForNItems: 2 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; } memset(data, 0, 2 * BUCKET_SIZE); size = 2; i = [key hash] & 1; @try { key = [key copy]; } @catch (OFException *e) { [self dealloc]; @throw e; } @try { [obj retain]; } @catch (OFException *e) { [key release]; [self dealloc]; @throw e; } data[i].key = key; data[i].object = obj; data[i].hash = [key hash]; count = 1; return self; } - initWithObjects: (OFArray*)objs forKeys: (OFArray*)keys { id *objs_carray, *keys_carray; size_t i; self = [super init]; @try { keys_carray = [keys cArray]; objs_carray = [objs cArray]; count = [keys count]; if (count > SIZE_MAX / 8) @throw [OFOutOfRangeException newWithClass: isa]; for (size = 1; size < count; size <<= 1); data = [self allocMemoryForNItems: size withSize: 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 * BUCKET_SIZE); for (i = 0; i < count; i++) { uint32_t j, hash, last; hash = [keys_carray[i] hash]; last = size; for (j = hash & (size - 1); j < last && data[j].key != nil && ![data[j].key isEqual: keys_carray[i]]; j++); /* In case the last bucket is already used */ if (j >= last) { last = hash & (size - 1); for (j = 0; j < last && data[j].key != nil && ![data[j].key isEqual: keys_carray[i]]; j++); } /* Key not in dictionary */ if (j >= last || ![data[j].key isEqual: keys_carray[i]]) { OFObject <OFCopying> *key; last = size; j = hash & (size - 1); for (; j < last && data[j].key != nil; j++); /* In case the last bucket is already used */ if (j >= last) { last = hash & (size - 1); for (j = 0; j < last && data[j].key != nil; j++); } if (j >= last) { Class c = isa; [self dealloc]; @throw [OFOutOfRangeException newWithClass: c]; } @try { key = [keys_carray[i] copy]; } @catch (OFException *e) { [self dealloc]; @throw e; } @try { [objs_carray[i] retain]; } @catch (OFException *e) { [key release]; [self dealloc]; @throw e; } data[j].key = key; data[j].object = objs_carray[i]; data[j].hash = hash; continue; } /* * They 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. */ @try { [objs_carray[i] retain]; } @catch (OFException *e) { [self dealloc]; @throw e; } @try { [data[j].object release]; } @catch (OFException *e) { [objs_carray[i] release]; [self dealloc]; @throw e; } data[j].object = objs_carray[i]; } return self; } - initWithKeysAndObjects: (OFObject <OFCopying>*)first, ... { id ret; va_list args; va_start(args, first); ret = [self initWithKey: first argList: args]; va_end(args); return ret; } - initWithKey: (OFObject <OFCopying>*)key argList: (va_list)args { OFObject *obj; size_t i; uint32_t j, hash; va_list args2; self = [super init]; count = 1; for (va_copy(args2, args); va_arg(args2, OFObject*) != nil; count++); count >>= 1; if (count > SIZE_MAX / 8) { Class c = isa; [self dealloc]; @throw [OFOutOfRangeException newWithClass: c]; } for (size = 1; size < count; size <<= 1); @try { data = [self allocMemoryForNItems: size withSize: 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 * BUCKET_SIZE); if (key == nil) return self; if ((obj = va_arg(args, OFObject*)) == nil) { Class c = isa; [self dealloc]; @throw [OFInvalidArgumentException newWithClass: c selector: _cmd]; } /* Add first key / object pair */ hash = [key hash]; j = hash & (size - 1); @try { key = [key copy]; } @catch (OFException *e) { [self dealloc]; @throw e; } @try { [obj retain]; } @catch (OFException *e) { [key release]; [self dealloc]; @throw e; } data[j].key = key; data[j].object = obj; data[j].hash = hash; for (i = 1; i < count; i++) { size_t last; key = va_arg(args, OFObject <OFCopying>*); obj = va_arg(args, OFObject*); if (key == nil || obj == nil) { Class c = isa; [self dealloc]; @throw [OFInvalidArgumentException newWithClass: c selector: _cmd]; } hash = [key hash]; last = size; for (j = hash & (size - 1); j < last && data[j].key != nil && ![data[j].key isEqual: key]; j++); /* In case the last bucket is already used */ if (j >= last) { last = hash & (size - 1); for (j = 0; j < last && data[j].key != nil && ![data[j].key isEqual: key]; j++); } /* Key not in dictionary */ if (j >= last || ![data[j].key isEqual: key]) { last = size; j = hash & (size - 1); for (; j < last && data[j].key != nil; j++); /* In case the last bucket is already used */ if (j >= last) { last = hash & (size - 1); for (j = 0; j < last && data[j].key != nil; j++); } if (j >= last) { Class c = isa; [self dealloc]; @throw [OFOutOfRangeException newWithClass: c]; } @try { key = [key copy]; } @catch (OFException *e) { [self dealloc]; @throw e; } @try { [obj retain]; } @catch (OFException *e) { [key release]; [self dealloc]; @throw e; } data[j].key = key; data[j].object = obj; data[j].hash = hash; continue; } /* * They 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. */ @try { [obj retain]; } @catch (OFException *e) { [self dealloc]; @throw e; } @try { [data[j].object release]; } @catch (OFException *e) { [obj release]; [self dealloc]; @throw e; } data[j].object = obj; } return self; } - (id)objectForKey: (OFObject <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].key != nil && (data[i].key == DELETED || ![data[i].key isEqual: key]); i++); if (i < last && (data[i].key == nil || data[i].key == DELETED)) return nil; /* In case the last bucket is already used */ if (i >= last) { last = hash & (size - 1); for (i = 0; i < last && data[i].key != nil && (data[i].key == DELETED || ![data[i].key isEqual: key]); i++); } /* Key not in dictionary */ if (i >= last || data[i].key == nil || data[i].key == DELETED || ![data[i].key isEqual: key]) return nil; return [[data[i].object retain] autorelease]; } - (size_t)count { return count; } - (id)copy { return [self retain]; } - (id)mutableCopy { return [[OFMutableDictionary alloc] initWithDictionary: self]; } - (BOOL)isEqual: (OFDictionary*)dict { size_t i; if ([dict count] != count) return NO; for (i = 0; i < size; i++) if (data[i].key != nil && data[i].key != DELETED && ![[dict objectForKey: data[i].key] isEqual: data[i].object]) return NO; return YES; } - (int)countByEnumeratingWithState: (of_fast_enumeration_state_t*)state objects: (id*)objects count: (int)count_ { size_t i; for (i = 0; i < count_; i++) { for (; state->state < size && (data[state->state].key == nil || data[state->state].key == 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] initWithData: data size: size mutationsPointer: NULL] autorelease]; } - (OFEnumerator*)keyEnumerator { return [[[OFDictionaryKeyEnumerator alloc] initWithData: data size: size mutationsPointer: NULL] autorelease]; } - (void)dealloc { size_t i; for (i = 0; i < size; i++) { if (data[i].key != nil && data[i].key != DELETED) { [data[i].key release]; [data[i].object release]; } } [super dealloc]; } - (uint32_t)hash { size_t i; uint32_t hash; OF_HASH_INIT(hash); for (i = 0; i < size; i++) { if (data[i].key != nil && data[i].key != DELETED) { uint32_t kh = [data[i].key hash]; OF_HASH_ADD(hash, kh >> 24); OF_HASH_ADD(hash, (kh >> 16) & 0xFF); OF_HASH_ADD(hash, (kh >> 8) & 0xFF); OF_HASH_ADD(hash, kh & 0xFF); 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_FINALIZE(hash); return hash; } @end /// \cond internal @implementation OFDictionaryEnumerator - initWithData: (struct of_dictionary_bucket*)data_ size: (size_t)size_ mutationsPointer: (unsigned long*)mutations_ptr_ { self = [super init]; data = data_; size = size_; mutations = *mutations_ptr_; mutations_ptr = mutations_ptr_; return self; } - reset { if (mutations_ptr != NULL && *mutations_ptr != mutations) @throw [OFEnumerationMutationException newWithClass: isa]; pos = 0; return self; } @end @implementation OFDictionaryObjectEnumerator - (id)nextObject { if (mutations_ptr != NULL && *mutations_ptr != mutations) @throw [OFEnumerationMutationException newWithClass: isa]; for (; pos < size && (data[pos].key == nil || data[pos].key == DELETED); pos++); if (pos < size) return data[pos++].object; else return nil; } @end @implementation OFDictionaryKeyEnumerator - (id)nextObject { if (mutations_ptr != NULL && *mutations_ptr != mutations) @throw [OFEnumerationMutationException newWithClass: isa]; for (; pos < size && (data[pos].key == nil || data[pos].key == DELETED); pos++); if (pos < size) return data[pos++].key; else return nil; } @end /// \endcond