Dynamic Stack Allocation
Wanting to re-familiarize myself with Objective-C, I wrote a mergesort method in an NSArray category:
- (NSArray*)mergeSortArrayUsingSelector:(SEL)comparator
{
id buf[[self count]];
[self getObjects:buf];
mergesort_(buf, [self count], comparator);
return [NSArray arrayWithObjects:buf count:[self count]];
}
I was pleasantly surprised to find that gcc now allows dynamic stack allocation (line 3). Implementing a generic sort in Objective-C felt clunky at first, but I was pleased with the result - a new instance method on NSArray returning a newly-allocated, sorted copy of the receiver.
void mergesort_(id* objs, size_t count, SEL cmp)
{
// Base case.
if (count < 2) return;
size_t left_count = count / 2;
size_t right_count = count - left_count;
id left_objs[left_count];
id right_objs[right_count];
// Function pointer for comparison IMP.
compare_IMP_ cmp_IMP = (compare_IMP_)[*objs methodForSelector:cmp];
// Divide and conquer.
memcpy(left_objs, objs, sizeof(id) * left_count);
memcpy(right_objs, &objs[left_count], sizeof(id) * right_count);
mergesort_(left_objs, left_count, cmp);
mergesort_(right_objs, right_count, cmp);
size_t cur_left = 0;
size_t cur_right = 0;
while (cur_left < left_count || cur_right < right_count)
{
id left = left_objs[cur_left];
id right = right_objs[cur_right];
// Special case where right side has element(s) remaining after
// all left-side elements have been merged.
if (cur_left == left_count) {
objs[cur_left+cur_right] = right;
cur_right++;
}
// Special case where left side has element(s) remaining after
// all right-side elements have been merged.
else if (cur_right == right_count) {
objs[cur_left+cur_right] = left;
cur_left++;
}
// Normal merge case: left > right
else if (cmp_IMP(left, cmp, right) == NSOrderedDescending) {
objs[cur_left+cur_right] = right;
cur_right++;
// Normal merge case: left <= right
} else {
objs[cur_left+cur_right] = left;
cur_left++;
}
}
}
{
// Base case.
if (count < 2) return;
size_t left_count = count / 2;
size_t right_count = count - left_count;
id left_objs[left_count];
id right_objs[right_count];
// Function pointer for comparison IMP.
compare_IMP_ cmp_IMP = (compare_IMP_)[*objs methodForSelector:cmp];
// Divide and conquer.
memcpy(left_objs, objs, sizeof(id) * left_count);
memcpy(right_objs, &objs[left_count], sizeof(id) * right_count);
mergesort_(left_objs, left_count, cmp);
mergesort_(right_objs, right_count, cmp);
size_t cur_left = 0;
size_t cur_right = 0;
while (cur_left < left_count || cur_right < right_count)
{
id left = left_objs[cur_left];
id right = right_objs[cur_right];
// Special case where right side has element(s) remaining after
// all left-side elements have been merged.
if (cur_left == left_count) {
objs[cur_left+cur_right] = right;
cur_right++;
}
// Special case where left side has element(s) remaining after
// all right-side elements have been merged.
else if (cur_right == right_count) {
objs[cur_left+cur_right] = left;
cur_left++;
}
// Normal merge case: left > right
else if (cmp_IMP(left, cmp, right) == NSOrderedDescending) {
objs[cur_left+cur_right] = right;
cur_right++;
// Normal merge case: left <= right
} else {
objs[cur_left+cur_right] = left;
cur_left++;
}
}
}
Leave a Reply