Creating dynamic array in C
Arrays are really nice data structure which allows us to quickly access data in a constant time by using index. The problem with array is that they require a fixed size which sometimes may not be available and might come as input from the user of the program or library you are coding.
In Order to resolve this issue we’ve some library functions viz malloc and calloc which are usually wrappers over the brk system call in addition to some book keeping to be able to allocate non paged size chunks of memory.
Let’s now take a look at how a statically created array looks like in memory,
char array[2]; | Element 0 Address | Element 1 Address |
|---|---|---|
Let's say array starts at 0x1234 | 0x1234 | 0x1235 |
Taking an example of a integer array, assuming an integer is 32 bit the statically created array would like the following in memory
int array[2]; | Element 0 Address | Element 1 Address |
|---|---|---|
Let's say array starts at 0x1200 | 0x1200 | 0x1204 |
Thus each element is spaced after the previous exactly sizeof(type) bytes. Not with this information let’s take a look at how we can create a one dimensional array first dynamically
- We need the data type so we can figure out the size.
- If the data type isn’t present we need to know the size of one element that the array is going to hold.
#include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { int size, count; void *new_array; if (argc != 3) { printf("Usage %s \n", argv[0]); exit(EXIT_FAILURE); } if (sscanf(argv[1], "%d", &count) || count <= 0) { printf("Require positive integer value of count argument \n"); exit(EXIT_FAILURE); } if (sscanf(argv[2], "%d", &size) || size <= 0) { printf("Require positive integer value of size argument \n"); exit(EXIT_FAILURE); } /* *Since we don't know the data type, a void data type works. Since calloc *returns a pointer to the newly allocated memory of a generic type, void *we can assign it's value to new_array. */ new_array = calloc(count , size); /* *calloc returns NULL if memory allocation failed. */ if (!new_array) { printf("Failed to allocated memory...\n"); exit(EXIT_FAILURE); } return 0; }
In order to use the above array there are two options,
- Use the size and move over each of the elements
- Cast the allocated pointer from void* to appropriate type
The first options is a bit tedious to work with for example it’s most common to just create a temporary walker pointer and increment it. Or we might want to directly access ithelement, which won’t be possible using a void*.
Let’s try to create a generic function which can return us an appropriately casted pointer so we won’t have to cast it everywhere we allocate memory,
/* * Create a wrapper over calloc with our checks * which does nothing but still returns a void* */ void *__allocate_array(int count, int size) { if (count <= 0 || size <= 0) return NULL; return calloc(count, size); } /* * To make it generic let's create a macro which * will replace the above call with appropriate * type returned. * * Obviously we won't need the size explicitly now * as we intend to cast it to the appropriate type. * thus, */ #define allocate_array(count, type)\ (type*)__allocate_array(count, sizeof(type))
Allocating a 2D array
A 2 dimensional array is nothing but an array of arrays. For example consider the following 2 dimensional array
char[][3] array2d; | Element 0 | Element 1 | Element 2 |
|---|---|---|---|
Let's say array2d[0] starts at 0x1200 | [0][0] 0x1200 | [0][1] 0x1201 | [0][2] 0x1202 |
array2d[1] will start at 0x1203 | [1][0] 0x1203 | [1][1] 0x1204 | [1][2] 0x1205 |
From the above we see that in order to allocate a 2 dimensional array we need to do the following,
- Allocate space for rows first, i.e. so that we can index the rows easily.
- Allocate the space for actual element for each of the rows so we can index the columns easily.
The rows are actually array of pointers as shown below
| Row Array ↓ | array[][2]; | Column Element 0 | Column Element 1 |
|---|---|---|---|
| Array of columns for row[0] → | array[0][0] | array[0][1] | |
| Array of columns for row[1] → | array[1][0] | array[1][1] |
Code to allocate a two dimensional array is shown below
void **__allocate_2d_array(int rows, int cols, int size) { void **new_array = NULL; if (rows <= 0 || cols <=0 || size <=0) { return NULL; } /* * First allocate rows using our allocate array * function. Since it's an array of pointers we * can use the generic void* for creating an array * of void*. */ new_array = allocate_array(rows, void*); if (new_array) { int r; for ( r = 0; r < rows; r++) { new_array[r] = calloc(cols, size); if (!new_array[r]) { /* * Free the columns for previous * rows. */ while (r > 0) { r--; free(new_array[r]); } /* * Free all the rows, i.e. * the array of pointers. */ free((void*)new_array); new_array = NULL; break; } } } return new_array; }
We can also make the above function generic using the same macro definition as with one dimensional array
#define allocate_2d_array(rows, cols, type)\
(type**) __allocate_2d_array(rows, cols, sizeof(type))Freeing a dynamic 2d array
When trying to free a 2 dimensional array, it’s necessary that we make our way backwards. Also it would be nice if we could make a generic function for it. So let’s take a look at the things we need to do in order to free a dynamically allocated 2D array.
- The columns array are the actual data and since we don’t know what exactly the type of data we can’t really free the columns straight away.
- We can only free a row if all it’s columns are freed properly.
/* * We ask the caller to provide free function for every * element we see. */ void free_2d_array(void **array, int rows, int cols, int size, void (*on_free)(void *)) { int j = 0; int k = 0; for (j = 0 ; j < rows; j++ ) { char **col_array = (char**)array + (j * size * cols); if (on_free) { for (k = 0; k < cols; k++) { char *element = col_array + (k * size); on_free((void*)element); } } /* * Free the columns (row array) now. */ free( (void*)col_array); } /* * Free all the rows at the end. */ free(array); }