handmade.network » Wiki » Dynamic Arrays

Introduction

Sometimes it's hard to know how large an array will need to be. Depending on how your program is used, the array might need to grow or shrink. To solve this issue, we can dynamically allocate the memory for an array, as needed.

Simple Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#define ARRAY_INSERT(array, item) \
    ArrayInsert((void **) &array, sizeof(*array), &array ## Count, &array ## Allocated, item)

void *ArrayInsert(void **array, size_t elementSize, 
        size_t *arrayCount, size_t *arrayAllocated, void *item) {
    // Increment the item count.
    *arrayCount = *arrayCount + 1;

    // If the count is greater than the allocated space, reallocate the memory.
    if (*arrayCount > *arrayAllocated) {
        // Add 64 to the allocated space. This could be any constant you want.
        *array = realloc(*array, (*arrayAllocated = *arrayCount + 64) * elementSize);
    }

    // Calculate a pointer to the item.
    void *pointer = (char *) *array + elementSize * (*arrayCount - 1);

    // Copy the item into the array.
    if (item) memcpy(pointer, item, elementSize);

    // Return the pointer to the item.
    return pointer;
}

...

// Create the empty array.
int *myArray = NULL;
size_t myArrayCount = 0, myArrayAllocated = 0;

// Insert some numbers into the array.
int item1 = 5;
ARRAY_INSERT(myArray, &item1);
int item2 = 3;    
ARRAY_INSERT(myArray, &item2);
int item3 = 6;     
ARRAY_INSERT(myArray, &item3);

// Print out the contents of the array.
printf("myArray[0] = %d\n", myArray[0]); // Prints 5.
printf("myArray[1] = %d\n", myArray[1]); // Prints 3.
printf("myArray[2] = %d\n", myArray[2]); // Prints 6.
printf("myArrayCount = %zd; myArrayAllocated = %zd\n", myArrayCount, myArrayAllocated); 

Problems

Pointers

You cannot safely store a pointer to an item in the array. This is because the memory could be reallocated when another item is inserted, causing the pointer to be incorrect. You can partially get around this by storing an index into the array.

Item Removal

With this method it's difficult to remove an item from the array. Item removal would leave gaps in the array; you could try to keep track of the gaps and fill them when inserting items - but this means every iteration over the array requires checking if each item is in use, and can slow down item insertion. Alternatively, you could move the last item in the array to fill the empty gap, but this prevents storing indices of items in the array as they could be modified.

Thread-Safety

The above code is not thread-safe. You would have to add a mutex to enable multiple threads to use it. But even if you did, any accesses to items in the array would have to be done under the same mutex used to insert items into the array. This is because of the memory reallocation and pointers problem described above.

Alternatives

On 64-bit systems virtual address space is essentially infinite. This means you can over-allocate space for arrays without consuming physical memory or worrying about wasting your process' address space. For example, even if every array you make was given 256MB of address space, you'd still be able to have hundreds of thousands of arrays before beginning to actually deplete the address space.