Demonstrating the trick of using stack-allocated mimics and sets for lookup tables instead of heap allocated keys and dictionaries

sethack.m

// Compile with clang -framework Foundation sethack.m

#import <Foundation/Foundation.h>
#import <objc/runtime.h>

/*
 CFHashBytes from http://www.opensource.apple.com/source/CF/CF-1153.18/CFUtilities.c
 */
#define ELF_STEP(B) T1 = (H << 4) + B; T2 = T1 & 0xF0000000; if (T2) T1 ^= (T2 >> 24); T1 &= (~T2); H = T1;

CFHashCode CFHashBytes(uint8_t *bytes, CFIndex length) {
    /* The ELF hash algorithm, used in the ELF object file format */
    UInt32 H = 0, T1, T2;
    SInt32 rem = (SInt32)length;
    while (3 < rem) {
        ELF_STEP(bytes[length - rem]);
        ELF_STEP(bytes[length - rem + 1]);
        ELF_STEP(bytes[length - rem + 2]);
        ELF_STEP(bytes[length - rem + 3]);
        rem -= 4;
    }
    switch (rem) {
        case 3:  ELF_STEP(bytes[length - 3]);
        case 2:  ELF_STEP(bytes[length - 2]);
        case 1:  ELF_STEP(bytes[length - 1]);
        case 0:  ;
    }
    return H;
}

#undef ELF_STEP

@interface Employee : NSObject
@property (readonly) NSString *name;
@property (readonly) NSDate *birthDate;
@property (readonly) NSNumber *bugCount;
@property (readonly) NSImage *photo;

- (instancetype) initWithName:(NSString *)name birthDate:(NSDate *)birthDate bugCount:(NSNumber *)bugCount photo:(NSImage *)photo;

@end

@interface FakeEmployee : NSObject
@property (readonly) NSString *name;
@property (readonly) NSDate *birthDate;
@property (readonly) NSNumber *bugCount;
@end

static BOOL employeeEqual(id inObj1, id inObj2) {
    if (inObj1 == inObj2) return YES;
    Employee *employee1 = (Employee *)inObj1;
    Employee *employee2 = (Employee *)inObj2;
    if (![employee1.birthDate isEqual: employee2.birthDate]) return NO;
    if (![employee1.bugCount isEqual: employee2.bugCount]) return NO;
    if (![employee1.name isEqualToString: employee2.name]) return NO;
    return YES;
}

static NSUInteger employeeHash(id obj) {
    Employee *employee = (Employee *)obj;
    static const int componentCount = 3;
    NSUInteger components[componentCount] = { [employee.name hash], [employee.birthDate hash], [employee.bugCount hash] };
    return CFHashBytes((uint8_t *)components, componentCount * sizeof(NSUInteger));
}

@implementation Employee

- (BOOL) isEqual:(id)object {
    return employeeEqual(self, object);
}

- (NSUInteger) hash {
    return employeeHash(self);
}

- (instancetype) initWithName:(NSString *)name birthDate:(NSDate *)birthDate bugCount:(NSNumber *)bugCount photo:(NSImage *)photo {
    if ((self = [super init])) {
        _name = [name copy];
        _birthDate = [birthDate copy];
        _bugCount = [bugCount copy];
        _photo = [photo retain];
    }
    return self;
}

- (void) dealloc {
    [_name release];
    [_birthDate release];
    [_bugCount release];
    [_photo release];
    [super dealloc];
}

@end

@implementation FakeEmployee

- (BOOL) isEqual:(id)object {
    return employeeEqual(self, object);
}

- (NSUInteger) hash {
    return employeeHash(self);
}

static void withKey(NSString *name, NSDate *birthDate, NSNumber *bugCount, void(^work)(FakeEmployee *)) {
    static size_t size;
    static Class fakeClass;
    static dispatch_once_t onceToken;
    dispatch_once(&onceToken, ^{
        fakeClass = [FakeEmployee class];
        size = class_getInstanceSize(fakeClass);
    });
    uint8_t buffer[size];
    FakeEmployee *key = objc_constructInstance(fakeClass, buffer);
    key->_name = name;
    key->_bugCount = bugCount;
    key->_birthDate = birthDate;
    work(key); //have to pass 'key' to a block or another function because we can't return pointers to local stack values
    //no release of 'key' because stack values don't participate in normal allocation/deallocation
}

@end

Employee *getEmployee(NSString *name, NSDate *birthDate, NSNumber *bugCount) {
    static NSMutableSet *table;
    static dispatch_once_t onceToken;
    dispatch_once(&onceToken, ^{
        table = [[NSMutableSet alloc] init];
    });
    
    __block Employee *result = nil;
    withKey(name, birthDate, bugCount, ^(FakeEmployee *key) {
        result = [table member:key];
        if (!result) {
            result = [[Employee alloc] initWithName:name birthDate:birthDate bugCount:bugCount photo:nil];
            [table addObject:result];
        }
    });
    
    return [[result retain] autorelease];
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        NSNumber *bugCount = @((NSUInteger)HUGE_VAL);
        Employee *me1 = getEmployee(@"David", [NSDate distantFuture], bugCount);
        Employee *me2 = getEmployee(@"David", [NSDate distantFuture], bugCount);
        assert(me1 == me2); //make sure we're able to look up the first employee we created in the table so we don't have clones wandering around
    }
    return 0;
}