Created
March 11, 2016 06:21
-
-
Save Catfish-Man/d7a517c27d9c38f19531 to your computer and use it in GitHub Desktop.
Demonstrating the trick of using stack-allocated mimics and sets for lookup tables instead of heap allocated keys and dictionaries
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Is the idea to avoid "expansive" unnecessary construction of a real object by constructing a "cheap" (in terms of both side effects and stack allocation) a mimic with implementation sufficient only to participate in equality tests?