Objective-C Tuesdays: more about dynamic arrays

Welcome back to Objective-C Tuesdays. Last time we were talking about dynamic arrays in C and NSMutableArray in Objective-C. We'll continue looking at both today.

We looked at using malloc() or calloc() to dynamically allocate a block of memory that you can treat like an array. This is very useful when you don't know the number of items you need to store until run time or when you need the array to exist longer than the current function call.

But what happens when you need to grow or shrink the memory block? Well, the straightforward way would be to allocate a new memory block, copy over the contents and free the old block. You use the memcpy() function in the C standard library to do the copying.

// resizing a memory blockint *lotteryNumbers = malloc(sizeof(int) * 6);if ( ! lotteryNumbers) {  // memory allocation failed  exit(EXIT_FAILURE);}lotteryNumbers[0] = 7;// ...lotteryNumbers[5] = 29;// now we need to store more numbers// so allocate a bigger memory blockint *biggerMemoryBlock = malloc(sizeof(int) * 12);if ( ! biggerMemoryBlock) {  // memory allocation failed  exit(EXIT_FAILURE);}// copy lotteryNumbers into biggerMemoryBlockmemcpy(biggerMemoryBlock, lotteryNumbers, sizeof(int) * 6);// free old memory blockfree(lotteryNumbers);// replace old memory block pointer with new onelotteryNumbers = biggerMemoryBlock;lotteryNumbers[6] = 31;// ...lotteryNumbers[11] = 49;

When copying blocks of memory, be careful to specify the correct size in bytes. In the example above, we use the same expression to calculate the size, sizeof(int) * 6 for both the original call to malloc() and to memcpy(). Using the sizeof operator like this serves two purposes. It makes the code portable, since the size of an int may be different on some systems (it's four bytes on iOS). More importantly, it tells anyone reading the code that you intended to allocate six ints. If you had specified simply malloc(24) or even malloc(6 * 4), your intention is not as clear.

Resizing a memory block with realloc()
Allocating a larger or smaller memory block and copying over the contents works perfectly, but it is tedious. Fortunately, the C standard library includes the realloc() function which does exactly this for you in one function call. It can operate on any memory block allocated with malloc() or calloc(). In addition, because it's part of the standard library, realloc() can do things that you can't: it will try to grow or shrink the memory block in place, skipping the copy step. Sometimes the memory manager will give you a block of memory somewhat bigger than you requested, other times the memory area after your memory block is currently unused. Because realloc() is privy to the implementation details of the memory manager, it can figure out when it's safe to grow your memory block in place.

The realloc() function returns a pointer to either the original memory block or a new memory block on success, or NULL if memory allocation fails. If the new memory block is bigger than the original, the new items will be set to zero, just as if you allocated the memory block with calloc(). Like malloc(), realloc() requires you to calculate the size of the memory block in bytes.

// using realloc()int *lotteryNumbers = malloc(sizeof(int) * 2);if ( ! lotteryNumbers) {  // out of memory  exit(EXIT_FAILURE);}lotteryNumbers[0] = 7;lotteryNumbers[1] = 11;// ...int *resizedLotteryNumbers = realloc(lotteryNumbers, sizeof(int) * 6);if ( ! resizedLotteryNumbers) {  // out of memory but lotteryNumbers memory block  // is still valid and unchanged  exit(EXIT_FAILURE);}// replace the old pointer with the new onelotteryNumbers = resizedLotteryNumbers;lotteryNumbers[2] = 19;// ...

If realloc() fails, it leaves the original memory block unchanged. Just as for calloc() and malloc(), you must remember to call free() on the memory block when you're done with it.

Inserting items into a C array
It should be obvious by now how to add items to the end of a C array (if it's big enough) or a dynamically allocated memory block that you've enlarged using realloc(). But how do you insert an item at the beginning or middle of an array while keeping all of the current items? There's no magic here, you have to shift items to higher indices to make space for the new one.

// insert an item at the start of a C arrayint lotteryNumbers[6] = { 11, 17 }; // has room for six items// shift current items uplotteryNumbers[2] = lotteryNumbers[1];lotteryNumbers[1] = lotteryNumbers[0];// array now holds { 11, 11, 17 }lotteryNumbers[0] = 7; // insert new item// array now holds { 7, 11, 17 }

Note that you need to shift items starting at the end of the array, otherwise you'll overwrite items you want to preserve. Obviously writing a line of code for each item you need to shift isn't a practical solution. You might be tempted to use the memcpy() function to shift items, but memcpy() has an important restriction: the source and destination memory blocks may not overlap. (This is because memcpy() may copy items front to back and thus overwrite items you want to preserve.) The memmove() function is meant to be used when the memory blocks overlap and will always shift items in the correct order to preserve the contents.

// using memmove() to insert an itemint lotteryNumbers[6] = { 11, 17 }; // has room for six items// shift current items upint *destination = lotteryNumbers + 1;int *source = lotteryNumbers;size_t size = sizeof(int) * 2;memmove(destination, source, size);// array now holds { 11, 11, 17 }lotteryNumbers[0] = 7; // insert new item// array now holds { 7, 11, 17 }

Because memmove() can operate on any kind of array or memory block, we need to do some pointer arithmetic to determine the source and destination addresses and the number of bytes to move. Again, the sizeof operator helps make our intentions clear. An alternate way specify the source and destination addresses is to use the address of operator (&) on indexed items in the array.

// determine source and destination using address of// ...int *destination = &lotteryNumbers[1];int *source = &lotteryNumbers[0];size_t size = sizeof(int) * 2;memmove(destination, source, size);// array now holds { 11, 11, 17 }// ...

These are equivalent notations and choosing one over the other is a matter of style.

You can use this technique to insert items into both C arrays and dynamically allocated memory blocks. Just make sure that there is enough space to move items around and that you don't write items past the end of your array or memory. As with all things in C, there is no safety net. To remove items from the beginning or middle of an array, follow the same procedure using memmove(), only shift items down and intentionally overwrite the items you want to delete. I'll leave this one as an exercise for the reader ☺.

Inserting items into an NSMutableArray
While using memmove() to shift items around isn't too terrible, the equivalent operations using NSMutableArray are naturally much more direct. To insert a single item at a particular index, you naturally use -insertObject:atIndex:

// inserting an item into an NSMutableArrayNSMutableArray *colors = [NSMutableArray arrayWithObjects:@"red",                                                           @"green",                                                           @"blue",                                                           nil];[colors insertObject:@"orange" atIndex:1];// colors now holds "red", "orange", "green" and "blue"

Inserting multiple items at one time is trickier. With the -insertObjects:atIndexes: method, you can insert items from an NSArray into your NSMutableArray. The tricky part here is that you need to also pass in an NSIndexSet (or NSMutableIndexSet) along with the array. Here's how you would insert an NSArray containing one item.

// inserting an item into an NSMutableArrayNSMutableArray *colors = [NSMutableArray arrayWithObjects:@"red",                                                           @"green",                                                           @"blue",                                                           nil];NSArray *newColors = [NSArray arrayWithObject:@"orange"];NSIndexSet *indexSet = [NSIndexSet indexSetWithIndex:1];[colors insertObjects:newColors atIndexes:indexSet];// colors now holds "red", "orange", "green" and "blue"

You must make sure that there is an index in the NSIndexSet for each item you are inserting. If you want to insert the new items all in one spot, the +indexSetWithIndexesInRange: method of NSIndexSet makes this easy.

// inserting multiple items into an NSMutableArrayNSMutableArray *colors = [NSMutableArray arrayWithObjects:@"red",                                                           @"green",                                                           @"blue",                                                           nil];NSArray *rainbowColors = [NSArray arrayWithObjects:@"orange",                                                    @"yellow",                                                    @"indigo",                                                    @"violet",                                                    nil];NSIndexSet *indexSet = [NSIndexSet indexSetWithIndexesInRange:NSMakeRange(1, 4)];[colors insertObjects:rainbowColors atIndexes:indexSet];// colors now holds "red", "orange", "yellow", "indigo", "violet", "green" and "blue"

Sometimes you want to insert different items at different points in your NSMutableArray. This is where -insertObjects:atIndexes: really shines. You'll want to use NSMutableIndexSet to create the index set in this case. Lets modify the previous example to insert the colors in standard rainbow order.

// inserting multiple items into an NSMutableArrayNSMutableArray *colors = [NSMutableArray arrayWithObjects:@"red",                                                           @"green",                                                           @"blue",                                                           nil];NSArray *rainbowColors = [NSArray arrayWithObjects:@"orange",                                                    @"yellow",                                                    @"indigo",                                                    @"violet",                                                    nil];NSMutableIndexSet *indexSet = [NSMutableIndexSet indexSet];[indexSet addIndex:1];[indexSet addIndex:2];[indexSet addIndex:5];[indexSet addIndex:6];[colors insertObjects:rainbowColors atIndexes:indexSet];// colors now holds "red", "orange", "yellow", "green", "blue", "indigo" and "violet"

To figure out the correct indices can be tricky. Inside the -insertObjects:atIndexes: method, new items will be inserted one at a time, starting with the lowest index in the index set. While inserting a group of items is a very powerful capability of NSMutableArray, often times I think it's easier and faster to write correct code that uses -subarrayWithRange: to break the items up into contiguous blocks before inserting them, or even to use -insertObject:atIndex: repeatedly to insert items one by one. But when it is straightforward to figure out the index set, -insertObjects:atIndexes: makes your code very succinct.

Next time, we'll look at sorting C arrays, NSArrays and NSMutableArrays.