Skip to content

Instantly share code, notes, and snippets.

@Catfish-Man
Created March 11, 2016 06:21
Show Gist options
  • Save Catfish-Man/d7a517c27d9c38f19531 to your computer and use it in GitHub Desktop.
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
// 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;
}
@Kentzo
Copy link

Kentzo commented Jul 29, 2020

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?

@Catfish-Man
Copy link
Author

yup!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment