Tuesday, July 26, 2011

Objective-C Tuesdays: Dynamic arrays

Another week, another Objective-C Tuesdays. Last week we began our series on data structures with a look at arrays in C and the NSArray class. Both C arrays and NSArray objects have serious limitations: C arrays are fixed in size and NSArrays are immutable. Today we will look at overcoming those limitations.

Dynamically allocated memory
C arrays are fixed in size when they are declared:
int lotteryNumbers[6];
Here we declare an array that can hold six ints. We can freely change the six int values we store in the array, but we can't make the array larger or smaller once it's declared. But there's nothing really magical about arrays in C: in essence they're blocks of memory managed by the compiler. When we declare an array, we tell the compiler the number of items we need to store and the type of item and it calculates the number of bytes of memory it needs to set aside for the array. We can do the same thing with a dynamically allocated memory block. Let's dynamically allocate the same amount of storage using malloc():
// dynamically allocating an array
#include <stdlib.h>

int *lotteryNumbers = malloc(sizeof(int) * 6);
if (lotteryNumbers) {
  lotteryNumbers[0] = 7;
  lotteryNumbers[1] = 11;
  // ...
}
The malloc() function is part of the standard C library, and it allocates a memory block on the heap. As we saw last time, you can use the same square bracket index notation with an array variable or a pointer to a block of memory.

Unlike global variables (which persist for the whole life span of your program) and local variables (which live only as long as the current function call), you control the life span of memory you allocate on the heap. Just as you need to match -retain with -release in Objective-C, you need to match calls to malloc() with corresponding calls to free():
// always free dynamically allocating arrays
#include <stdlib.h>
// ...

int *lotteryNumbers = malloc(sizeof(int) * 6);

// use lotteryNumbers for a while...

free(lotteryNumbers);
The malloc() function takes one argument: the number of bytes to allocate. Since most useful items require more than one byte each, you need to use the sizeof() operator to get the size of the item type and multiply it by the number of items required.
// calculate the number of bytes required
// using the sizeof() operator
int *lotteryNumbers = malloc(sizeof(int) * 6);
if (lotteryNumbers) {
  // ...
The malloc() function returns a pointer to the newly allocated memory block on success. If malloc() fails, it returns NULL. You should always check the result of memory allocation and take appropriate action. The typical C idiom is to use the returned pointer as a boolean value, since NULL pointers in C evaluate to false while non-NULL pointers are true, similar to nil values in Objective-C.
// always test the returned pointer
int *lotteryNumbers = malloc(sizeof(int) * 6);
if (lotteryNumbers) {
  // okay to use...
} else {
  // we're out of memory...
}

Handling malloc() failures
If a call to malloc() fails and returns NULL, it's almost always because you've run out of available memory. There are two broad strategies for coping with a memory allocation failure: fail fast or abort the operation. In general, I recommend that you fail fast by doing something like this:
// fail fast when out of memory

int *lotteryNumbers = malloc(sizeof(int) * 6);
if ( ! lotteryNumbers) {
  fprintf(stderr, "%s:%i: Out of memory\n", __FILE__, __LINE__);
  exit(EXIT_FAILURE);
}
// okay to use memory
lotteryNumbers[0] = 7;
// ...
In an Objective-C program, you would use NSLog() instead of fprintf(). When small to medium size memory allocations fail, the system is seriously constrained and there's not much else your program can do to cope. In fact, iOS will likely terminate your app before you ever reach this condition.

Sometimes your program is trying to do something particularly memory intensive, like editing a large image or sound file. In cases like this, you should be prepared for large memory allocations to fail and try to abort the operation gracefully. The strategy in this case is to free all resources allocated for the operation so far and alert the user.

Using calloc() instead of malloc()
When you dynamically allocate a memory block, you frequently want to set all the items to zero. malloc() doesn't do any initialization to the memory block, so the initial contents are effectively random garbage. The calloc() function is similar to malloc(), but also clears the bytes in the memory block to zeros before returning.
// using calloc()
size_t itemCount = 6;
size_t itemSize = sizeof(int);
int *lotteryNumbers = calloc(itemCount, itemSize);
if (lotteryNumbers) {
  // okay to use...
Unlike malloc() which takes the size of the memory block in bytes, calloc() takes the number of items and the size of each item and does the math for you. Under the covers, calloc() allocates memory from the same heap that malloc() uses, so you need to call free() on the memory block when you're done.

There's a lot more to managing dynamically allocated memory blocks. We'll look at resizing a memory block using realloc() next time but for now let's move on to a more pleasant topic: NSMutableArray.

NSMutableArray
Like its immutable super class NSArray, the NSMutableArray class takes mutable array management to a higher level. You can create an NSMutableArray the same way you create an NSArray:
NSMutableArray *colors = [NSMutableArray arrayWithObjects:@"red", 
                                                          @"green", 
                                                          @"blue", 
                                                          nil];
Another common creation technique is to duplicate an existing immutable NSArray using the +arrayWithArray: or -initWithArray: methods.
NSArray *rgbColors = [NSArray arrayWithObjects:@"red", 
                                               @"green", 
                                               @"blue", 
                                               nil];
NSMutableArray *colors = [NSMutableArray arrayWithArray:rgbColors];
Often, you simply want an empty array to start with. The +array or -init methods from NSArray will do the trick here. (You can create empty immutable NSArray objects this way too, they're just usually not very useful.)

Adding items to the end of the array is easily done with -addObject: and -addObjectsFromArray:
NSMutableArray *colors = [NSMutableArray array];
// colors is empty

[colors addObject:@"yellow"];
[colors addObject:@"purple"];
// colors holds yellow, purple

NSArray *designerColors = [NSArray arrayWithObjects:@"mauve", 
                                                    @"chartreuse", 
                                                    @"seafoam", 
                                                    nil];
[colors addObjectsFromArray:designerColors];
// colors now holds yellow, purple, mauve, chartreuse and seafoam

NSMutableArray has many ways to remove objects. The -removeLastObject method is the inverse of -addObject:. The -removeObjectAtIndex: method removes an item at a particular index. Continuing with our array of colors:
// colors holds yellow, purple, mauve, chartreuse and seafoam
[colors removeLastObject];
// colors holds yellow, purple, mauve and chartreuse
[colors removeObjectAtIndex:0];
// colors holds purple, mauve and chartreuse

That covers the basics of adding and removing objects from an NSMutableArray. Next time, we'll cover more ways to manipulate the mutable array contents.

2 comments:

jinru said...

Thanks for this great post! It is very helpful. Could you talk a little bit more about how to use c arrays as instance variables in a Objective C object? Like how do you synthesize the pointer to the array and alloc it in the implementation? Thanks!!

Don McCaughey said...

Thanks! I'm planning to talk about using NSMutableData to do that in a couple of weeks. Stay tuned!