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

How overriding Object.ToString() helps

System.Object provides a ToString() method which gives a human readable string about the object. Many people haven’t realized how useful is this tiny method.

Consider the following code:

namespace PersonDetails
{
    class Person
    {
        public Person(string firstName, string lastName, int age)
        {
            this.FirstName = firstName;
            this.LastName = lastName;
            this.Age = age;
        }

        public string FirstName { get; set; }
        public string LastName { get; set; }
        public int Age { get; set; }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Person chuckNorris = new Person("Chuck", "Norris", 20);
            Console.WriteLine(chuckNorris.ToString()); // Prints PersonDetails.Person
        }
    }
}

The information printed is not at all helpful. Let us override ToString() and see the difference. Continue reading

Understanding equality and object comparison in .NET framework

.NET framework provides several methods to do comparison and equality check for objects. It can be pretty confusing at the beginning by looking at the documentations for each interfaces that framework offers. In this post, I will try explain the possibilities with examples.

Basically, there are two kinds of equality in .NET. Reference Equality and Value Equality. Default is reference equality. To understand reference equality, consider the following class: Continue reading

Circular linked list – An implementation using C#

In this post, I will explain about creating a circular doubly linked list using C#. .NET framework provides a doubly linked list implementation in System.Collections.Generic.LinkedList<T> class . But this class is not providing the behavior of a circular linked list and it is very tough to extend for supporting circular linked list requirements.

In a normal doubly linked list, each node will have a link to its previous and next nodes. In a circular doubly linked list, tail node’s next node will be head and head node’s previous node will be tail. Here is an image taken from wikipedia which visualizes circular linked list.

Circular linked list
Continue reading

Thought process for writing recursive methods

I was interviewing one candidate the other day and found that he is facing difficulties in writing a recursive method. This is not the first time I am seeing people facing problems with recursion. In this post, I will try to explain the thought process to write recursive methods.

This post is intended for beginners who don’t have any idea about recursion. If you are an intermediate or above level, you don’t find this as useful. Continue reading

Single click builds for different environments using Visual Studio

A neat build system is vital for all projects. Good build system should be capable to work without *any* user intervention. Here is what Joel Spolsky says on his post

Can you make a build in one step?

By this I mean: how many steps does it take to make a shipping build from the latest source snapshot? On good teams, there’s a single script you can run that does a full checkout from scratch, rebuilds every line of code, makes the EXEs, in all their various versions, languages, and #ifdef combinations, creates the installation package, and creates the final media — CDROM layout, download website, whatever.

Ask yourself the same question – Can you build your application in one step? Continue reading

ADO.NET best practices – Reading data from data reader

I have seen many people using DataReader incorrectly. In this post, I will try to explain some good practices that can be followed when reading from a data reader. Consider the following problematic code,

SqlDataReader reader = /* ... */;
while (reader.Read())
{
    string userName = reader["user_name"].ToString();
    int age = int.Parse( reader["age"].ToString() );
    /* ... */
}
reader.Close();

How many problems can you figure out from the above code? There are many problems with this code, Continue reading