This chapter is from the book
This chapter is from the book
This chapter is from the book
4.5 Enumeration
The traditional way of performing enumeration on Foundation collections is via the NSEnumerator. This is a very simple object that responds to a -nextObject message and returns either the next object, or nil if there is no next object. To enumerate a collection using an enumerator, you simply call a method like -objectEnumerator on the collection and then loop sending -nextObject to the returned enumerator until it returns nil.
With 10.5, Apple added a fast enumeration system. This uses a new for loop construct, part of Objective-C 2.0, which handles collections.
A lot of the time, however, you don't need to use enumeration directly at all. You can use something like NSArray's -makeObjectsPerformSelector: method. Listing 4.7 shows an example of all three ways of sending a single message to all objects in an array.
Listing 4.7. The three ways of sending a message to an object in Cocoa. [from: examples/Enumeration/enum.m]
1| #import <Foundation/Foundation.h>
2|
3| @interface NSString (printing)
4| - (void) print;
5| @end
6| @implementation NSString (printing)
7| - (void) print
8| {
9| fprintf(stderr, "%s\n", [self UTF8String]);
10| }
11| @end
12|
13| int main(void)
14| {
15| [NSAutoreleasePool new];
16| NSArray* a =
17| [NSArray arrayWithObjects: @"this", @"is", @"an", @"array", nil];
18|
19| NSLog(@"The_Objective-C_1_way:");
20| NSEnumerator *e=[a objectEnumerator];
21| for (id obj=[e nextObject]; nil!=obj ; obj=[e nextObject])
22| {
23| [obj print];
24| }
25| NSLog(@"The_Leopard_way:");
26| for (id obj in a)
27| {
28| [obj print];
29| }
30| NSLog(@"The_simplest_way:");
31| [a makeObjectsPerformSelector: @selector(print)];
32| return 0;
33| }
Lines 20–24 show how to use an enumerator. This is quite complex and easy to make typos in, so in Étoilé we hide this pattern in a FOREACH macro (which also does some caching to speed things up slightly). A simpler version is shown in lines 26–29, using the fast enumeration pattern. This is both simpler code and faster, which is quite a rare achievement. The final version, on line 31, is even simpler. This is a single line. If you want to send more than one message, or messages with more than one argument, then this mechanism is unavailable.
Running this code, we get
$ gcc -std=c99 -framework Foundation enum.m && ./a.out 2009-01-07 18:06:41.014 a.out[30527:10b] The Objective-C 1 way: this is an array 2009-01-07 18:06:41.020 a.out[30527:10b] The Leopard way: this is an array 2009-01-07 18:06:41.021 a.out[30527:10b] The simplest way: this is an array
4.5.1 Enumerating with Higher-Order Messaging
An additional way of performing enumeration, among other things, was proposed by Marcel Weiher. The mechanism, called higher-order messaging (HOM) uses the proxy capabilities of Objective-C. It adds methods like -map to the collection classes. When these are called, they return a proxy object that bounces every message sent to them to every object in the array.
Listing 4.8 shows a -map method added as a category on NSArray. This is taken from the EtoileFoundation framework, with the Étoilé-specific macros removed. This framework is available under a BSD license, and so you can use it in your own projects if you wish.
Listing 4.8. A example of a map method implemented using higher-order messaging. [from: examples/HOM/NSArray+map.m]
3| @interface NSArrayMapProxy : NSProxy {
4| NSArray * array;
5| }
6| - (id) initWithArray:(NSArray*)anArray;
7| @end
8|
9| @implementation NSArrayMapProxy
10| - (id) initWithArray:(NSArray*)anArray
11| {
12| if (nil == (self = [self init])) { return nil; }
13| array = [anArray retain];
14| return self;
15| }
16| - (id) methodSignatureForSelector:(SEL)aSelector
17| {
18| for (object in array)
19| {
20| if([object respondsToSelector:aSelector])
21| {
22| return [object methodSignatureForSelector:aSelector];
23| }
24| }
25| return [super methodSignatureForSelector:aSelector];
26| }
27| - (void) forwardInvocation:(NSInvocation*)anInvocation
28| {
29| SEL selector = [anInvocation selector];
30| NSMutableArray * mappedArray =
31| [NSMutableArray arrayWithCapacity:[array count]];
32| for (object in array)
33| {
34| if([object respondsToSelector:selector])
35| {
36| [anInvocation invokeWithTarget:object];
37| id mapped;
38| [anInvocation getReturnValue:&mapped];
39| [mappedArray addObject:mapped];
40| }
41| }
42| [anInvocation setReturnValue:mappedArray];
43| }
44| - (void) dealloc
45| {
46| [array release];
47| [super dealloc];
48| }
49| @end
50|
51| @implementation NSArray (AllElements)
52| - (id) map
53| {
54| return [[[NSArrayMapProxy alloc] initWithArray:self] autorelease];
55| }
56| @end
The -map method itself is relatively simple; it just creates an instance of the proxy, associates it with the array, and returns it. You would use this category like this:
[[array map] stringValue];
This would return an array containing the result of sending -stringValue to every element in array. When you send the -stringValue message to the proxy, the runtime calls the -methodSignatureForSelector: method. This is used to find out the types of the method. This implementation simply calls the same method on every object in the array until it finds one which returns a value.
Next, the -forwardInvocation: method will be called. This has an encapsulated message as the argument. The body of this method sends this message to every object in the array and then adds the result to a new array.
Unlike the -makeObjectsPerformSelector:, messages sent to objects using higher-order messaging can have an arbitrary number of arguments. Exactly the same mechanism can be used to implement a variety of other high-level operations on collections, such as folding or selecting.
Although the use of the forwarding mechanism makes this relatively slow, compared with other enumeration mechanisms, the fact that it preserves high-level information in the source code can make it attractive. It results in less duplicated code and code that is easier to write. HOM is used a lot in modern Smalltalk implementations, although the initial implementation was in Objective-C.
Higher-order messaging is not limited to enumeration. It is also used for a wide number of other tasks, including sending messages between threads. We'll look more at how to use it for asynchronous messaging in Chapter 23.
4.5.2 Enumerating with Blocks
OS X 10.6 added blocks, which we looked at in the last chapter, to the C family of languages. Blocks by themselves are quite useful, but their real power comes from their integration with the rest of the Foundation framework. This integration comes from a number of new methods, such as this one on NSArray:
- (void)enumerateObjectsUsingBlock:
(void (^)(id obj, NSUInteger idx, BOOL *stop))block;
The argument is a block taking three arguments: an object, the index at which that object appears in the array, and a pointer to a boolean value to set if enumeration should stop. We could rewrite the same enumeration example that we used earlier with a block as:
[a enumerateObjectsUsingBlock:
^(id obj, NSUInteger idx, BOOL *stop) { [obj print]; } ];
The requirement to put the types of the block arguments inline makes this quite difficult to read, but you could split it up a bit by declaring the block separately and then calling it. In this example, the block doesn't refer to anything other than its arguments, so using a block is equivalent to using a function pointer, with the exception that a block can be declared inline.
The method shown above is a simplified version. The more complex variant includes an options parameter that is an NSEnumerationOptions value. This is an enumerated type that specifies whether the enumeration should proceed forward, in reverse, or in parallel. If you specify NSEnumerationConcurrent, then the array may spawn a new thread or use a thread from a pool to split the enumeration across multiple processors. This is usually only a good idea for large arrays or blocks that take a long time to execute.
Foundation defines two other kinds of blocks for use with collections: test blocks and comparator blocks. A test block returns a BOOL, while a comparator is defined by the NSComparator typedef:
typedef NSComparisonResult (^NSComparator)(id obj1, id obj2);
Comparator blocks are used everywhere that sorting might be performed. Both mutable and immutable arrays can be sorted with comparators but so can sets and dictionaries. This includes some quite complex methods, such as this one from NSDictionary:
- (NSArray*)keysSortedByValueUsingComparator: (NSComparator)cmptr;
The argument to this method is a comparator block that defines the ordering of two objects. This will be called with all of the values in the dictionary, and the method will return an array containing all of the keys in the order that their values are listed. This can then be used to visit the values in this order by sending -valueForKey: messages to the dictionary.
Test blocks are used for filtering. Unlike comparators, they do not have a specific type associated with them because each class defines the arguments that a test block takes. For example, NSIndexSet test blocks take an NSUInteger argument, while tests for NSDictionary take both the key and value as arguments.
Most collection classes, including those outside of Foundation, such as those managed by the Core Data framework support NSPredicate as a means of filtering. As of OS X 10.6, you can also create NSPredicate instances from test blocks. You can also create NSSortDescriptor instances, which are heavily used in conjunction with Cocoa bindings from comparator blocks and, using the -comparator method turn an NSSortDescriptor object into a comparator block.
4.5.3 Supporting Fast Enumeration
From time to time, you will want to implement your own collection classes, and want to use them with the new for...in loops. If your collection can create enumerators, then you can use the enumerator as the enumerator's support for fast enumeration, but this is slightly unwieldy and slow. Full support requires collections to conform to the NSFastEnumeration protocol and implement the following method:
- (NSUInteger)countByEnumeratingWithState: (NSFastEnumerationState*)state
objects: (id*)stackbuf
count: (NSUInteger)len;
Understanding this method requires understanding the NSFastEnumerationState structure. This is defined in the NSEnumerator.h Foundation header, as shown in Listing 4.9.
Listing 4.9. The fast enumeration state structure. [from: NSEnumerator.h]
19| typedef struct {
20| unsigned long state;
21| id *itemsPtr;
22| unsigned long *mutationsPtr;
23| unsigned long extra[5];
24| } NSFastEnumerationState;
The first time this method is called, it should initialize the mutationsPtr field of this structure. This must be a valid pointer to something at least as big as a long. The caller will automatically cache the pointed-to value when the method is first called and then compare this on every subsequent iteration through the loop. If it has changed, then an exception will be thrown. In contrast, an NSEnumerator has no way of knowing if the collection it is enumerating has changed.
The second argument is a pointer to a buffer allocated by the caller, and the third is the size of this buffer. If the collection stores objects internally in a C array, it can return a pointer to this directly by setting state->itemsPtr to the array and returning the number of elements. Otherwise, it copies up to len elements into stackbuf and returns the number it copies. The compiler currently sets len to 16, and so only a single message send is required for every 16 items enumerated. In contrast, at least 32 will be required when using an enumerator (one to the enumerator and one from the enumerator to the collection). It is easy to see why Apple calls this the 'fast enumeration' system.
To see how you can support fast enumeration in your own collections, we will create two new classes, as shown in Listing 4.10. These both conform to the NSFastEnumeration protocol. One is mutable and the other immutable. Supporting fast enumeration is done slightly differently for mutable and immutable objects.
Listing 4.10. Integer array interfaces. [from: examples/FastEnumeration/IntegerArray.h]
1| #import <Foundation/Foundation.h>
2|
3| @interface IntegerArray : NSObject<NSFastEnumeration> {
4| NSUInteger count;
5| NSInteger *values;
6| }
7| - (id)initWithValues: (NSInteger*)array count: (NSUInteger)size;
8| - (NSInteger)integerAtIndex: (NSUInteger)index;
9| @end
10|
11| @interface MutableIntegerArray : IntegerArray {
12| unsigned long version;
13| }
14| - (void)setInteger: (NSInteger)newValue atIndex: (NSUInteger)index;
15| @end
The most noticeable difference in the interface is that the mutable version has a version instance variable. This is used to track whether the object has changed during enumeration.
The immutable version is shown in Listing 4.11. The first two methods are very simple; they just initialize the array and allow values to be accessed. The array is a simple C buffer, created with malloc(). The -dealloc method frees the buffer when the object is destroyed.
Listing 4.11. A simple immutable integer array supporting fast enumeration. [from: examples/FastEnumeration/IntegerArray.m]
3| @implementation IntegerArray
4| - (id)initWithValues: (NSInteger*)array count: (NSUInteger)size
5| {
6| if (nil == (self = [self init])) { return nil; }
7| count = size;
8| NSInteger arraySize = size * sizeof(NSInteger);
9| values = malloc(arraySize);
10| memcpy(values, array, arraySize);
11| return self;
12| }
13| - (NSInteger)integerAtIndex: (NSUInteger)index
14| {
15| if (index >= count)
16| {
17| [NSException raise: NSRangeException
18| format: @"Invalid_index"];
19| }
20| return values[index];
21| }
22| - (NSUInteger)countByEnumeratingWithState: (NSFastEnumerationState*)state
23| objects: (id*)stackbuf
24| count: (NSUInteger)len
25| {
26| NSUInteger n = count - state->state;
27| state->mutationsPtr = (unsigned long *)self;
28| state->itemsPtr = (id*)(values + state->state);
29| state->state += n;
30| return n;
31| }
32| - (void)dealloc
33| {
34| free(values);
35| [super dealloc];
36| }
37| @end
The fast enumeration implementation here returns a pointer to the instance variable, on line 28. This code is written to support partial enumeration, where the caller only requests some subset of the total collection. This is not currently supported by the compiler, but, because this is just an Objective-C method, you cannot guarantee that it will not be called directly by some code wanting just the values after a certain element. The state field will be set to the first element that the caller wants. In normal use, this will be either 0 or count. The items pointer is set to the correct offset in the instance variable array using some simple pointer arithmetic.
The state field is updated to equal the index of the last value and the array is returned. Any for...in loop will call this method twice. After the first call the state field will have been set to count. In the second call, the value of n will be set to 0 and the loop will terminate.
Note that the mutations pointer is set to self. Dereferencing this will give the isa pointer. This class does not support modifying the values, but some other code may change the class of this object to a subclass that does. In this case, the mutation pointer will change. This is very unlikely; for most cases the self pointer is a convenient value because it is a pointer that is going to remain both valid and constant for the duration of the loop.
The mutable case is a bit more complicated. This is shown in Listing 4.12. This class adds a method, allowing values in the array to be set. Note that on line 42 the version is incremented. This is used to abort enumeration when the array is modified.
The enumeration method in this class sets the mutation pointer to the address of the version instance variable. The initial value of this is cached by the code generated from the loop construct, and every loop iteration will be compared against the current value to detect changes.
Listing 4.12. A simple mutable integer array supporting fast enumeration. [from: examples/FastEnumeration/IntegerArray.m]
39| @implementation MutableIntegerArray
40| - (void)setInteger: (NSInteger)newValue atIndex: (NSUInteger)index
41| {
42| version++;
43| if (index >= count)
44| {
45| values = realloc(values, (index+1) * sizeof(NSInteger));
46| count = index + 1;
47| }
48| values[index] = newValue;
49| }
50| - (NSUInteger)countByEnumeratingWithState: (NSFastEnumerationState*)state
51| objects: (id*)stackbuf
52| count: (NSUInteger)len
53| {
54| NSInteger n;
55| state->mutationsPtr = &version;
56| n = MIN(len, count - state->state);
57| if (n >= 0)
58| {
59| memcpy(stackbuf, values + state->state, n * sizeof(NSInteger));
60| state->state += n;
61| }
62| else
63| {
64| n = 0;
65| }
66| state->itemsPtr = stackbuf;
67| return n;
68| }
69| @end
Because the mutable array's internal array can be reallocated and become invalid, we copy values out onto the stack buffer. This is not technically required; the collection is not thread-safe anyway, and so the array cannot be accessed in a way that would cause problems, but it's done here as an example of how to use the stack buffer.
The stack buffer has a fixed size. This is typically 16 entries. On line 56, we find which is smaller out of the number of slots in the stack buffer and the number of elements left to return. We then copy this many elements on line 59. The items pointer is then set to the stack buffer's address.
Using the stack buffer is entirely optional. Our immutable array didn't use it, while this one does. It is there simply as a convenient place to put elements if the class doesn't use an array internally.
To test these two classes, we use the simple program shown in Listing 4.13. This creates two integer arrays, one mutable and one immutable, and iterates over both of them using the fast enumeration for...in loop construct.
Listing 4.13. Testing the fast enumeration implementation. [from: examples/FastEnumeration/test.m]
1| #import "IntegerArray.h"
2|
3| int main(void)
4| {
5| [NSAutoreleasePool new];
6| NSInteger cArray[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
15, 16, 17, 18, 19, 20};
7| IntegerArray *array = [[IntegerArray alloc] initWithValues: cArray
8| count: 20];
9| NSInteger total = 0;
10| for (id i in array)
11| {
12| total += (NSInteger)i;
13| }
14| printf("total:_%d\n", (int)total);
15| MutableIntegerArray *mutablearray =
16| [[MutableIntegerArray alloc] initWithValues: cArray
17| count: 20];
18| [mutablearray setInteger: 21 atIndex: 20];
19| for (id i in mutablearray)
20| {
21| total += (NSInteger)i;
22| }
23| printf("total:_%d\n", (int)total);
24| for (id i in mutablearray)
25| {
26| total += (NSInteger)i;
27| printf("value:_%d\n", (int)(NSInteger)i);
28| [mutablearray setInteger: 22 atIndex: 21];
29| }
30| return 0;
31| }
Note that the type of the element in these loops has to be an id. This is only a requirement of the type checker. The compiler does not insert any message sends to the returned objects, so as long as they are the same size as an id they can be returned.
On line 28, we modify the collection inside a loop. This is exactly the kind of thing that the fast enumeration structure's mutation pointer field is intended to detect. If we have written the implementation correctly, then an exception will be thrown. Running the program, we see that this does happen:
$ gcc -framework Foundation *.m && ./a.out total: 210 total: 441 value: 1 2009-02-21 16:24:56.278 a.out[4506:10b] *** Terminating app due to uncaught exception 'NSGenericException', reason: '*** Collection <MutableIntegerArray: 0x1004bb0> was mutated while being enumerated.'
We didn't have to do anything explicit here to raise the exception. Just modifying the version instance variable did it. Note that the exception was raised after the first loop iteration, even though the first 16 values were all returned at once. This is why the mutation pointer is a pointer and not just a value. If it had been a simple value that we had set to the value of the version ivar in each call, the loop would not have been able to detect the mutation until the next call. Because it is a pointer, it can be dereferenced and tested very cheaply at each loop iteration and so the mutation is caught the first time the caller tries to load a value from the array that has since changed.
Because we modified the version counter before making any changes to the array, we guaranteed that the mutation will always be caught. If you add any other mutation methods to the class, just remember to add version++ at the start, and this will keep working.