Dynamic array

Introduction
Creation
Adding elements
Removing elements
Accessing elements
Example program
Source code
Download

Introduction

The problem with built-in arrays is that they are fixed-size, so you need to decide in advance how big they need to be, and they are often not filled completely. Overrunning the bounds of an array is a serious programming error.

A solution is to allocate the array dynamically, double its size when it becomes full, and check for out-of-bounds access.

Creation

An array is created with MBdynarray_create. A size can be specified when creating the array. This prevents many reallocations happening early on when the array is being populated. If no size is specified, the buffer is allocated with a default size when an element is first added.

Adding elements

Elements can be added at either end of the array with MBdynarray_add_head and MBdynarray_add_tail, or inserted between existing elements with MBdynarray_insert. When elements are added anywhere other than at the tail end, the succeeding elements are shifted to the right. The range of indices that may be given to MBdynarray_insert run from 0 to count the count of elements in the array returned by MBdynarray_get_count. If the index given is count, this is equivalent to calling MBdynarray_add_tail.

Removing elements

Elements can be removed with MBdynarray_remove_head, MBdynarray_remove_tail and MBdynarray_remove, in which case the succeeding elements are shifted to the left.

Accessing elements

Elements are accessed with MBdynarray_get and MBdynarray_set.

Example

#include <stdio.h>

#include <dynarray.h>

int main(void)
{
    MBdynarray *array = MBdynarray_create(0); /* No preferred size */
    unsigned int i;
    void * data;
    char *elements[] = {"A", "B", "C", "D", "E", "F"};
    const unsigned int n = sizeof(elements) / sizeof(const char*);

    for (i = 0; i < n; i++) {
        if (i % 2 == 0) {
            MBdynarray_add_head(array, elements[i]);
        }
        else {
            MBdynarray_add_tail(array, elements[i]);
        }
    }

    MBdynarray_insert(array, 0, "X");                              /* Same as MBdynarray_addhead */
    MBdynarray_insert(array, MBdynarray_get_count(array) / 2, "Y");    /* Insert in the middle */
    MBdynarray_insert(array, MBdynarray_get_count(array), "Z");        /* Same as MBdynarray_add_tail */

    MBdynarray_set(array, MBdynarray_get_count(array) / 2, "P");
    MBdynarray_set(array, MBdynarray_get_count(array), "Q");           /* Same as MBdynarray_add_tail */

    for (i = 0; i < MBdynarray_get_count(array); i++) {
        printf("%d: %s\n", i, (const char*)MBdynarray_get(array, i));
    }
    putchar('\n');

    for (i = 0; MBdynarray_get_count(array); i++) {
        const unsigned int action = i % 3;
        if (action == 0) {
            data = MBdynarray_remove_head(array);
        }
        else if (action == 1) {
            data = MBdynarray_remove_tail(array);
        }
        else {
            data = MBdynarray_remove(array, MBdynarray_get_count(array) / 2);
        }
        printf("Removed: %s\n", (const char*)data);
    }

    MBdynarray_delete(array);

    return 0;
}

Source code

Download

The following archives contain the full source code, example programs and build instructions for all of the data structures:

mbds.tar.gz (27 KB, Linux)
mbds.zip (55 KB, Windows)