Simple, generic and dynamically allocated array in C

C is a very good language. I have been using for quite some time for my opensource project. The flexibility C offers is really good. But sometimes, lack of simple datastructures like a dynamically growing array will slow down the programmer. There are tons of implementation available online, but most of them are overcomplicated, got lot of dependencies or tough to understand and incorporate with your application. In this post, I present a simple array which grows dynamically, reuses the memory, supports any pointer type and easy to copy to your code base.

Here is the code.


typedef struct varray_t
{
   void **memory;
   size_t allocated;
   size_t used;
   int index;
} varray;

void
varray_init(varray **array)
{
   *array = (varray*) malloc (sizeof(varray));
   (*array)->memory = NULL;
   (*array)->allocated = 0;
   (*array)->used = 0;
   (*array)->index = -1;
}

void
varray_push(varray *array, void *data)
{
   size_t toallocate;
   size_t size = sizeof(void*);
   if ((array->allocated - array->used) < size) {
      toallocate = array->allocated == 0 ? size : (array->allocated * 2);
      array->memory = realloc(array->memory, toallocate);
      array->allocated = toallocate;
   }

   array->memory[++array->index] = data;
   array->used = array->used + size;
}

int
varray_length(varray *array)
{
   return array->index + 1;
}

void
varray_clear(varray *array)
{
   int i;
   for(i = 0; i < varray_length(array); i++)
   {
      array->memory[i] = NULL;
   }
   array->used = 0;
   array->index = -1;
}

void
varray_free(varray *array)
{
   free(array->memory);
   free(array);
}

void*
varray_get(varray *array, int index)
{
   if (index < 0 || index > array->index)
      return NULL;

   return array->memory[index];
}

void
varray_insert(varray *array, int index, void *data)
{
   if (index < 0 || index > array->index)
      return;

   array->memory[index] = data;
}

This array doesn’t take ownership of the data it contains. Ownership has to be managed separately. When adding a new item, array grows in constant propotion yielding inserts in amortized constant time. I have omitted error checking for malloc and realloc for simplicity.

Hope you enjoy the post.

Advertisements

3 thoughts on “Simple, generic and dynamically allocated array in C

  1. That’s not a generic array really, but an array of void pointers; casting is needed on varray_get(), for example. Also it tends to be slow, since each element is (probably) allocated on the heap.

    • Yeah. But there is no real generics in C. The only way you can do is using void pointers. Regarding the performance, I am using this in a very high traffic website and it works just well. How can you handle dynamically growing memory without allocating to heap? You really can’t allocate them statically.

  2. I don’t understand when you add an element into the array you multiply by 2 the new memory needed by realloc. This make it growing as a power of 2! Wouldn’t be easier to just do (e.g: realloc( array->memory, (array->allocated+1) * sizeof(void*));) ???

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s