Idea

I’ve been working on a few small programming projects over the past few weeks. C++ and it’s object oriented model makes generic data structures a lot simpler, but the syntax and bloat of everything gets a little complex. Recently I’ve been using C for most everything besides small web projects. I decided to build up my own little library of generic data structures so that I can just pull these into any projects moving forward. This should help prevent me from reinventing the wheel every time, but it has been fun to get back to the basics with this. Definitely not optimal solutions (I’ll discuss that below), but they hit the gist of what I need.

Implementation

I opted to use void pointers and copy the contents of elements directly into the structure. This keeps the data nearby in most structures so I reduce page faults from following pointers around the heap, but adds a memory copy during the initialization of a new element. I am willing to make that sacrifice since most of my projects will be accessing memory much more often than modifying it. But if I need to do things the other way then I’ll make adjustments as necessary.

The other disadvantage of using these void pointers is that it could get confusing if you try to access things without saving function pointers to print or compare elements. I wrote the code so I know that if I just stick to the public functions things should be fine. But trying to make direct accesses to the internals of these structures could cause a lot of problems.

Overall this experience has definitely highlighted the advantage of using a language like C++ for stronger types and operator overloading. But I’m happy I gave it a shot and know that it will come in handy moving forward. I will post the more complete set of code on my GitHub, but below is a short example of how I was managing the generics in my structures. I plan on providing a useful and working implementation of Array List, Linked List, Binary Search Tree, AVL Tree, B-Tree, and Hash Table.

struct alist{
    size_t elementsize;
    size_t maxsize;
    size_t size;
    void *list;
};

struct alist *alist_init(size_t elementsize, size_t maxsize){
    struct alist *list = malloc(sizeof(*list));
    list->elementsize = elementsize;
    list->maxsize = maxsize;
    list->size = 0;
    list->list = malloc(elementsize * maxsize);
    if(list->list == NULL){
        return NULL;
    }
    return list;
}

void *alist_insert(struct alist *list, unsigned int position, void *valptr){
    ...
    uint8_t *array = list->list;
    memcpy(&array[position * list->elementsize], valptr, list->elementsize);
    ...
}