@@ -26,17 +26,19 @@ #import "OFEnumerationMutationException.h" #import "OFInvalidArgumentException.h" #import "OFOutOfRangeException.h" -#define MIN_CAPACITY 16 +extern unsigned long OFHashSeed; -struct of_map_table_bucket { +static const unsigned long minCapacity = 16; + +struct OFMapTableBucket { void *key, *object; unsigned long hash; }; -static struct of_map_table_bucket deleted = { 0 }; +static struct OFMapTableBucket deletedBucket = { 0 }; static void * defaultRetain(void *object) { return object; @@ -57,21 +59,14 @@ defaultEqual(void *object1, void *object2) { return (object1 == object2); } -OF_DIRECT_MEMBERS -@interface OFMapTable () -- (void)of_setObject: (void *)object - forKey: (void *)key - hash: (unsigned long)hash; -@end - OF_DIRECT_MEMBERS @interface OFMapTableEnumerator () - (instancetype)of_initWithMapTable: (OFMapTable *)mapTable - buckets: (struct of_map_table_bucket **)buckets + buckets: (struct OFMapTableBucket **)buckets capacity: (unsigned long)capacity mutationsPointer: (unsigned long *)mutationsPtr OF_METHOD_FAMILY(init); @end @@ -82,22 +77,20 @@ @end @implementation OFMapTable @synthesize keyFunctions = _keyFunctions, objectFunctions = _objectFunctions; -+ (instancetype)mapTableWithKeyFunctions: (of_map_table_functions_t)keyFunctions - objectFunctions: (of_map_table_functions_t) - objectFunctions ++ (instancetype)mapTableWithKeyFunctions: (OFMapTableFunctions)keyFunctions + objectFunctions: (OFMapTableFunctions)objectFunctions { return [[[self alloc] initWithKeyFunctions: keyFunctions objectFunctions: objectFunctions] autorelease]; } -+ (instancetype)mapTableWithKeyFunctions: (of_map_table_functions_t)keyFunctions - objectFunctions: (of_map_table_functions_t) - objectFunctions ++ (instancetype)mapTableWithKeyFunctions: (OFMapTableFunctions)keyFunctions + objectFunctions: (OFMapTableFunctions)objectFunctions capacity: (size_t)capacity { return [[[self alloc] initWithKeyFunctions: keyFunctions objectFunctions: objectFunctions @@ -107,20 +100,20 @@ - (instancetype)init { OF_INVALID_INIT_METHOD } -- (instancetype)initWithKeyFunctions: (of_map_table_functions_t)keyFunctions - objectFunctions: (of_map_table_functions_t)objectFunctions +- (instancetype)initWithKeyFunctions: (OFMapTableFunctions)keyFunctions + objectFunctions: (OFMapTableFunctions)objectFunctions { return [self initWithKeyFunctions: keyFunctions objectFunctions: objectFunctions capacity: 0]; } -- (instancetype)initWithKeyFunctions: (of_map_table_functions_t)keyFunctions - objectFunctions: (of_map_table_functions_t)objectFunctions +- (instancetype)initWithKeyFunctions: (OFMapTableFunctions)keyFunctions + objectFunctions: (OFMapTableFunctions)objectFunctions capacity: (size_t)capacity { self = [super init]; @try { @@ -156,17 +149,17 @@ if (capacity * 8 / _capacity >= 6) if (_capacity <= ULONG_MAX / 2) _capacity *= 2; - if (_capacity < MIN_CAPACITY) - _capacity = MIN_CAPACITY; + if (_capacity < minCapacity) + _capacity = minCapacity; - _buckets = of_alloc_zeroed(_capacity, sizeof(*_buckets)); + _buckets = OFAllocZeroedMemory(_capacity, sizeof(*_buckets)); - if (of_hash_seed != 0) - _rotate = of_random16() & 31; + if (OFHashSeed != 0) + _rotate = OFRandom16() & 31; } @catch (id e) { [self release]; @throw e; } @@ -174,22 +167,176 @@ } - (void)dealloc { for (unsigned long i = 0; i < _capacity; i++) { - if (_buckets[i] != NULL && _buckets[i] != &deleted) { + if (_buckets[i] != NULL && _buckets[i] != &deletedBucket) { _keyFunctions.release(_buckets[i]->key); _objectFunctions.release(_buckets[i]->object); - free(_buckets[i]); + OFFreeMemory(_buckets[i]); } } - free(_buckets); + OFFreeMemory(_buckets); [super dealloc]; } + +static void +resizeForCount(OFMapTable *self, unsigned long count) +{ + unsigned long fullness, capacity; + struct OFMapTableBucket **buckets; + + if (count > ULONG_MAX / sizeof(*self->_buckets) || + count > ULONG_MAX / 8) + @throw [OFOutOfRangeException exception]; + + fullness = count * 8 / self->_capacity; + + if (fullness >= 6) { + if (self->_capacity > ULONG_MAX / 2) + return; + + capacity = self->_capacity * 2; + } else if (fullness <= 1) + capacity = self->_capacity / 2; + else + return; + + /* + * Don't downsize if we have an initial capacity or if we would fall + * below the minimum capacity. + */ + if ((capacity < self->_capacity && count > self->_count) || + capacity < minCapacity) + return; + + buckets = OFAllocZeroedMemory(capacity, sizeof(*buckets)); + + for (unsigned long i = 0; i < self->_capacity; i++) { + if (self->_buckets[i] != NULL && + self->_buckets[i] != &deletedBucket) { + unsigned long j, last; + + last = capacity; + + for (j = self->_buckets[i]->hash & (capacity - 1); + j < last && buckets[j] != NULL; j++); + + /* In case the last bucket is already used */ + if (j >= last) { + last = self->_buckets[i]->hash & (capacity - 1); + + for (j = 0; j < last && + buckets[j] != NULL; j++); + } + + if (j >= last) + @throw [OFOutOfRangeException exception]; + + buckets[j] = self->_buckets[i]; + } + } + + OFFreeMemory(self->_buckets); + self->_buckets = buckets; + self->_capacity = capacity; +} + +static void +setObject(OFMapTable *restrict self, void *key, void *object, + unsigned long hash) +{ + unsigned long i, last; + void *old; + + if (key == NULL || object == NULL) + @throw [OFInvalidArgumentException exception]; + + hash = OFRotateLeft(hash, self->_rotate); + last = self->_capacity; + + for (i = hash & (self->_capacity - 1); + i < last && self->_buckets[i] != NULL; i++) { + if (self->_buckets[i] == &deletedBucket) + continue; + + if (self->_keyFunctions.equal(self->_buckets[i]->key, key)) + break; + } + + /* In case the last bucket is already used */ + if (i >= last) { + last = hash & (self->_capacity - 1); + + for (i = 0; i < last && self->_buckets[i] != NULL; i++) { + if (self->_buckets[i] == &deletedBucket) + continue; + + if (self->_keyFunctions.equal( + self->_buckets[i]->key, key)) + break; + } + } + + /* Key not in map table */ + if (i >= last || self->_buckets[i] == NULL || + self->_buckets[i] == &deletedBucket || + !self->_keyFunctions.equal(self->_buckets[i]->key, key)) { + struct OFMapTableBucket *bucket; + + resizeForCount(self, self->_count + 1); + + self->_mutations++; + last = self->_capacity; + + for (i = hash & (self->_capacity - 1); i < last && + self->_buckets[i] != NULL && + self->_buckets[i] != &deletedBucket; i++); + + /* In case the last bucket is already used */ + if (i >= last) { + last = hash & (self->_capacity - 1); + + for (i = 0; i < last && self->_buckets[i] != NULL && + self->_buckets[i] != &deletedBucket; i++); + } + + if (i >= last) + @throw [OFOutOfRangeException exception]; + + bucket = OFAllocMemory(1, sizeof(*bucket)); + + @try { + bucket->key = self->_keyFunctions.retain(key); + } @catch (id e) { + OFFreeMemory(bucket); + @throw e; + } + + @try { + bucket->object = self->_objectFunctions.retain(object); + } @catch (id e) { + self->_keyFunctions.release(bucket->key); + OFFreeMemory(bucket); + @throw e; + } + + bucket->hash = hash; + + self->_buckets[i] = bucket; + self->_count++; + + return; + } + + old = self->_buckets[i]->object; + self->_buckets[i]->object = self->_objectFunctions.retain(object); + self->_objectFunctions.release(old); +} - (bool)isEqual: (id)object { OFMapTable *mapTable; @@ -205,11 +352,11 @@ mapTable->_keyFunctions.equal != _keyFunctions.equal || mapTable->_objectFunctions.equal != _objectFunctions.equal) return false; for (unsigned long i = 0; i < _capacity; i++) { - if (_buckets[i] != NULL && _buckets[i] != &deleted) { + if (_buckets[i] != NULL && _buckets[i] != &deletedBucket) { void *objectIter = [mapTable objectForKey: _buckets[i]->key]; if (!_objectFunctions.equal(objectIter, _buckets[i]->object)) @@ -223,12 +370,12 @@ - (unsigned long)hash { unsigned long hash = 0; for (unsigned long i = 0; i < _capacity; i++) { - if (_buckets[i] != NULL && _buckets[i] != &deleted) { - hash ^= OF_ROR(_buckets[i]->hash, _rotate); + if (_buckets[i] != NULL && _buckets[i] != &deletedBucket) { + hash ^= OFRotateRight(_buckets[i]->hash, _rotate); hash ^= _objectFunctions.hash(_buckets[i]->object); } } return hash; @@ -241,15 +388,15 @@ objectFunctions: _objectFunctions capacity: _capacity]; @try { for (unsigned long i = 0; i < _capacity; i++) - if (_buckets[i] != NULL && _buckets[i] != &deleted) - [copy of_setObject: _buckets[i]->object - forKey: _buckets[i]->key - hash: OF_ROR(_buckets[i]->hash, - _rotate)]; + if (_buckets[i] != NULL && + _buckets[i] != &deletedBucket) + setObject(copy, _buckets[i]->key, + _buckets[i]->object, + OFRotateRight(_buckets[i]->hash, _rotate)); } @catch (id e) { [copy release]; @throw e; } @@ -266,15 +413,15 @@ unsigned long i, hash, last; if (key == NULL) @throw [OFInvalidArgumentException exception]; - hash = OF_ROL(_keyFunctions.hash(key), _rotate); + hash = OFRotateLeft(_keyFunctions.hash(key), _rotate); last = _capacity; for (i = hash & (_capacity - 1); i < last && _buckets[i] != NULL; i++) { - if (_buckets[i] == &deleted) + if (_buckets[i] == &deletedBucket) continue; if (_keyFunctions.equal(_buckets[i]->key, key)) return _buckets[i]->object; } @@ -284,199 +431,50 @@ /* In case the last bucket is already used */ last = hash & (_capacity - 1); for (i = 0; i < last && _buckets[i] != NULL; i++) { - if (_buckets[i] == &deleted) + if (_buckets[i] == &deletedBucket) continue; if (_keyFunctions.equal(_buckets[i]->key, key)) return _buckets[i]->object; } return NULL; } -- (void)of_resizeForCount: (unsigned long)count OF_DIRECT -{ - unsigned long fullness, capacity; - struct of_map_table_bucket **buckets; - - if (count > ULONG_MAX / sizeof(*_buckets) || count > ULONG_MAX / 8) - @throw [OFOutOfRangeException exception]; - - fullness = count * 8 / _capacity; - - if (fullness >= 6) { - if (_capacity > ULONG_MAX / 2) - return; - - capacity = _capacity * 2; - } else if (fullness <= 1) - capacity = _capacity / 2; - else - return; - - /* - * Don't downsize if we have an initial capacity or if we would fall - * below the minimum capacity. - */ - if ((capacity < _capacity && count > _count) || capacity < MIN_CAPACITY) - return; - - buckets = of_alloc_zeroed(capacity, sizeof(*buckets)); - - for (unsigned long i = 0; i < _capacity; i++) { - if (_buckets[i] != NULL && _buckets[i] != &deleted) { - unsigned long j, last; - - last = capacity; - - for (j = _buckets[i]->hash & (capacity - 1); - j < last && buckets[j] != NULL; j++); - - /* In case the last bucket is already used */ - if (j >= last) { - last = _buckets[i]->hash & (capacity - 1); - - for (j = 0; j < last && - buckets[j] != NULL; j++); - } - - if (j >= last) - @throw [OFOutOfRangeException exception]; - - buckets[j] = _buckets[i]; - } - } - - free(_buckets); - _buckets = buckets; - _capacity = capacity; -} - -- (void)of_setObject: (void *)object - forKey: (void *)key - hash: (unsigned long)hash -{ - unsigned long i, last; - void *old; - - if (key == NULL || object == NULL) - @throw [OFInvalidArgumentException exception]; - - hash = OF_ROL(hash, _rotate); - last = _capacity; - - for (i = hash & (_capacity - 1); i < last && _buckets[i] != NULL; i++) { - if (_buckets[i] == &deleted) - continue; - - if (_keyFunctions.equal(_buckets[i]->key, key)) - break; - } - - /* In case the last bucket is already used */ - if (i >= last) { - last = hash & (_capacity - 1); - - for (i = 0; i < last && _buckets[i] != NULL; i++) { - if (_buckets[i] == &deleted) - continue; - - if (_keyFunctions.equal(_buckets[i]->key, key)) - break; - } - } - - /* Key not in map table */ - if (i >= last || _buckets[i] == NULL || _buckets[i] == &deleted || - !_keyFunctions.equal(_buckets[i]->key, key)) { - struct of_map_table_bucket *bucket; - - [self of_resizeForCount: _count + 1]; - - _mutations++; - last = _capacity; - - for (i = hash & (_capacity - 1); i < last && - _buckets[i] != NULL && _buckets[i] != &deleted; i++); - - /* In case the last bucket is already used */ - if (i >= last) { - last = hash & (_capacity - 1); - - for (i = 0; i < last && _buckets[i] != NULL && - _buckets[i] != &deleted; i++); - } - - if (i >= last) - @throw [OFOutOfRangeException exception]; - - bucket = of_alloc(1, sizeof(*bucket)); - - @try { - bucket->key = _keyFunctions.retain(key); - } @catch (id e) { - free(bucket); - @throw e; - } - - @try { - bucket->object = _objectFunctions.retain(object); - } @catch (id e) { - _keyFunctions.release(bucket->key); - free(bucket); - @throw e; - } - - bucket->hash = hash; - - _buckets[i] = bucket; - _count++; - - return; - } - - old = _buckets[i]->object; - _buckets[i]->object = _objectFunctions.retain(object); - _objectFunctions.release(old); -} - -- (void)setObject: (void *)object - forKey: (void *)key -{ - [self of_setObject: object - forKey: key - hash: _keyFunctions.hash(key)]; +- (void)setObject: (void *)object forKey: (void *)key +{ + setObject(self, key, object,_keyFunctions.hash(key)); } - (void)removeObjectForKey: (void *)key { unsigned long i, hash, last; if (key == NULL) @throw [OFInvalidArgumentException exception]; - hash = OF_ROL(_keyFunctions.hash(key), _rotate); + hash = OFRotateLeft(_keyFunctions.hash(key), _rotate); last = _capacity; for (i = hash & (_capacity - 1); i < last && _buckets[i] != NULL; i++) { - if (_buckets[i] == &deleted) + if (_buckets[i] == &deletedBucket) continue; if (_keyFunctions.equal(_buckets[i]->key, key)) { _mutations++; _keyFunctions.release(_buckets[i]->key); _objectFunctions.release(_buckets[i]->object); - free(_buckets[i]); - _buckets[i] = &deleted; + OFFreeMemory(_buckets[i]); + _buckets[i] = &deletedBucket; _count--; - [self of_resizeForCount: _count]; + resizeForCount(self, _count); return; } } @@ -485,23 +483,23 @@ /* In case the last bucket is already used */ last = hash & (_capacity - 1); for (i = 0; i < last && _buckets[i] != NULL; i++) { - if (_buckets[i] == &deleted) + if (_buckets[i] == &deletedBucket) continue; if (_keyFunctions.equal(_buckets[i]->key, key)) { _keyFunctions.release(_buckets[i]->key); _objectFunctions.release(_buckets[i]->object); - free(_buckets[i]); - _buckets[i] = &deleted; + OFFreeMemory(_buckets[i]); + _buckets[i] = &deletedBucket; _count--; _mutations++; - [self of_resizeForCount: _count]; + resizeForCount(self, _count); return; } } } @@ -508,42 +506,42 @@ - (void)removeAllObjects { for (unsigned long i = 0; i < _capacity; i++) { if (_buckets[i] != NULL) { - if (_buckets[i] == &deleted) { + if (_buckets[i] == &deletedBucket) { _buckets[i] = NULL; continue; } _keyFunctions.release(_buckets[i]->key); _objectFunctions.release(_buckets[i]->object); - free(_buckets[i]); + OFFreeMemory(_buckets[i]); _buckets[i] = NULL; } } _count = 0; - _capacity = MIN_CAPACITY; - _buckets = of_realloc(_buckets, _capacity, sizeof(*_buckets)); + _capacity = minCapacity; + _buckets = OFResizeMemory(_buckets, _capacity, sizeof(*_buckets)); /* * Get a new random value for _rotate, so that it is not less secure * than creating a new hash map. */ - if (of_hash_seed != 0) - _rotate = of_random16() & 31; + if (OFHashSeed != 0) + _rotate = OFRandom16() & 31; } - (bool)containsObject: (void *)object { if (object == NULL || _count == 0) return false; for (unsigned long i = 0; i < _capacity; i++) - if (_buckets[i] != NULL && _buckets[i] != &deleted) + if (_buckets[i] != NULL && _buckets[i] != &deletedBucket) if (_objectFunctions.equal(_buckets[i]->object, object)) return true; return false; } @@ -552,11 +550,11 @@ { if (object == NULL || _count == 0) return false; for (unsigned long i = 0; i < _capacity; i++) - if (_buckets[i] != NULL && _buckets[i] != &deleted) + if (_buckets[i] != NULL && _buckets[i] != &deletedBucket) if (_buckets[i]->object == object) return true; return false; } @@ -577,20 +575,20 @@ buckets: _buckets capacity: _capacity mutationsPointer: &_mutations] autorelease]; } -- (int)countByEnumeratingWithState: (of_fast_enumeration_state_t *)state +- (int)countByEnumeratingWithState: (OFFastEnumerationState *)state objects: (id *)objects count: (int)count { unsigned long j = state->state; int i; for (i = 0; i < count; i++) { for (; j < _capacity && (_buckets[j] == NULL || - _buckets[j] == &deleted); j++); + _buckets[j] == &deletedBucket); j++); if (j < _capacity) { objects[i] = _buckets[j]->key; j++; } else @@ -603,36 +601,35 @@ return i; } #ifdef OF_HAVE_BLOCKS -- (void)enumerateKeysAndObjectsUsingBlock: - (of_map_table_enumeration_block_t)block +- (void)enumerateKeysAndObjectsUsingBlock: (OFMapTableEnumerationBlock)block { bool stop = false; unsigned long mutations = _mutations; for (size_t i = 0; i < _capacity && !stop; i++) { if (_mutations != mutations) @throw [OFEnumerationMutationException exceptionWithObject: self]; - if (_buckets[i] != NULL && _buckets[i] != &deleted) + if (_buckets[i] != NULL && _buckets[i] != &deletedBucket) block(_buckets[i]->key, _buckets[i]->object, &stop); } } -- (void)replaceObjectsUsingBlock: (of_map_table_replace_block_t)block +- (void)replaceObjectsUsingBlock: (OFMapTableReplaceBlock)block { unsigned long mutations = _mutations; for (size_t i = 0; i < _capacity; i++) { if (_mutations != mutations) @throw [OFEnumerationMutationException exceptionWithObject: self]; - if (_buckets[i] != NULL && _buckets[i] != &deleted) { + if (_buckets[i] != NULL && _buckets[i] != &deletedBucket) { void *new; new = block(_buckets[i]->key, _buckets[i]->object); if (new == NULL) @throw [OFInvalidArgumentException exception]; @@ -653,11 +650,11 @@ { OF_INVALID_INIT_METHOD } - (instancetype)of_initWithMapTable: (OFMapTable *)mapTable - buckets: (struct of_map_table_bucket **)buckets + buckets: (struct OFMapTableBucket **)buckets capacity: (unsigned long)capacity mutationsPointer: (unsigned long *)mutationsPtr { self = [super init]; @@ -689,11 +686,11 @@ if (*_mutationsPtr != _mutations) @throw [OFEnumerationMutationException exceptionWithObject: _mapTable]; for (; _position < _capacity && (_buckets[_position] == NULL || - _buckets[_position] == &deleted); _position++); + _buckets[_position] == &deletedBucket); _position++); if (_position < _capacity) return &_buckets[_position++]->key; else return NULL; @@ -706,11 +703,11 @@ if (*_mutationsPtr != _mutations) @throw [OFEnumerationMutationException exceptionWithObject: _mapTable]; for (; _position < _capacity && (_buckets[_position] == NULL || - _buckets[_position] == &deleted); _position++); + _buckets[_position] == &deletedBucket); _position++); if (_position < _capacity) return &_buckets[_position++]->object; else return NULL;