Fast enumeration example

fast-enum.m

#import <Foundation/Foundation.h>

// clang -g -fobjc-arc -Weverything -framework Foundation -o fast-enum fast-enum.m
#pragma clang diagnostic ignored "-Wobjc-missing-property-synthesis"


// --------------------------------------------------
// Code to iterate a non-array based collection and use fast
// enumeration's stack buffer
// This is a linked list that holds strings.  Pretty uninspired.

// Linked list node - holds the string, and a pointer to the next node
@interface Node : NSObject
@property (copy, nonatomic) NSString *string;
@property (strong, nonatomic) Node *next;
@end // Node

@implementation Node
@end // Node


// The collection.  Add new strings to the end of the collection,
// and access by index.
@interface LifoList : NSObject <NSFastEnumeration>

@property (readonly, nonatomic) NSUInteger count;

- (void) addString: (NSString *) string;
- (NSString *) stringAtIndex: (NSUInteger) index;

@end // LifoList


@implementation LifoList {
    Node *_head;
    NSUInteger _count;
    unsigned long _mutations;
}

- (NSUInteger) countByEnumeratingWithState: (NSFastEnumerationState *) enumerationState
                                   objects: (id __unsafe_unretained []) stackBuffer 
                                     count: (NSUInteger) len {
    // Sanity check.  I know sizeof(unsigned long) >= sizeof(pointer), but be
    // a little paranoid.
    assert (sizeof(Node *) <= sizeof(unsigned long));

    // Using the enumerationState's extra[0] as the scan pointer.

    if (enumerationState->state == 0) { // first time
        enumerationState->state = 1; // Must set to non-zero
        enumerationState->mutationsPtr = &_mutations;  // Can't be NULL.
        enumerationState->extra[0] = (unsigned long)_head;
    }

    Node *scan = (__bridge Node *)((void *)enumerationState->extra[0]);

    // Fill up as much of the stack buffer as we can.
    NSUInteger i;
    for (i = 0; i < len && scan != nil; i++) {
        stackBuffer[i] = scan.string;
        scan = scan.next;
    }
    enumerationState->extra[0] = (unsigned long) scan;

    // Point the returned items pointer to the stack buffer.  We could pass our
    // own internal buffer pointers here, or allocate memory and fill it.
    enumerationState->itemsPtr = stackBuffer;

    return i;

} // countByEnumeratingWithState



- (void) addString: (NSString *) string {
    // New node
    Node *node = [[Node alloc] init];

    // Put it at the start of the list.
    node.string = string;
    node.next = _head;
    _head = node;

    // Necessary bookkeeping.
    _count++;
    _mutations++;

} // addString


- (NSString *) stringAtIndex: (NSUInteger) index {

    // Holy O(N) algorithms, BatMan
    Node *scan = _head;
    for (NSUInteger i = 0; i < index; i++) {
        scan = scan.next;
    }

    return scan.string;

} // stringAtIndex

@end // LifoList



// --------------------------------------------------
// Some timing tests.

// http://weblog.bignerdranch.com/316-a-timing-utility/

#import <mach/mach_time.h>  // for mach_absolute_time() and friends

static CGFloat BNRTimeBlock (void (^block)(void)) {
    mach_timebase_info_data_t info;
    if (mach_timebase_info(&info) != KERN_SUCCESS) return -1.0;

    uint64_t start = mach_absolute_time ();
    block ();
    uint64_t end = mach_absolute_time ();
    uint64_t elapsed = end - start;

    uint64_t nanos = elapsed * info.numer / info.denom;
    return (CGFloat)nanos / NSEC_PER_SEC;

} // BNRTimeBlock


#define LIFO_COUNT 10000

static void TimeLifoList () {
    NSLog (@"Timing iteration of %d elements", LIFO_COUNT);

    // Build up the list with a bunch of nodes.
    LifoList *lifolist = [[LifoList alloc] init];

    NSString *value = @"hi";
    
    for (NSUInteger i = 0; i < LIFO_COUNT; i++) {
        [lifolist addString: value];
    }

    // See how long it takes to iterate using stringAtIndex.  This is
    // O(N^2), so will take a long time.
    __block NSUInteger count = 0;

    CGFloat indexingTime = BNRTimeBlock (^{
            for (NSUInteger i = 0; i < lifolist.count; i++) {
                (void)[lifolist stringAtIndex: i];
                count++;
            }
        });
    assert (count == LIFO_COUNT);  // paranoia
    assert (count == lifolist.count);

    NSLog (@"lifo list indexing time: %f", indexingTime);


    // Now with fast indexing.  This is O(N), so will be much, much faster.
    // Most sane people won't be using a linked list for indexed access.
    count = 0;
    CGFloat fastEnumerationTime = BNRTimeBlock (^{
            for (NSString *string in lifolist) {
                count++;
            }
        });
    assert (count == LIFO_COUNT);
    assert (count == lifolist.count);

    NSLog (@"fast enumeration time: %f", fastEnumerationTime);

} // timeLifoList



int main (void) {
    LifoList *lifolist = [[LifoList alloc] init];

    // Exhaustive unit test.

    [lifolist addString: @"hello"];
    [lifolist addString: @"there"];
    [lifolist addString: @"greeble"];

    for (NSUInteger i = 0; i < lifolist.count; i++) {
        NSLog (@"%ld : %@", i, [lifolist stringAtIndex: i]);
    }

    TimeLifoList ();

    return 0;

} // main


#if 0

% clang -g -fobjc-arc -Weverything -framework Foundation -o fast-enum fast-enum.m

% ./fast-enum
0 : greeble
1 : there
2 : hello
lifo list indexing time: 3.352057
fast enumeration time: 0.001404

#endif