You Are Here Home > Low Level

Low Level

Implementation of a Vector data structure in C

I use Python a lot but it’s very slow in some cases which I then use C because it can be 1,000s X faster than Python.

Here is a Vector that I just wrote to use in my new project:

vector.h

/**
 * Hamid Alipour
 */
 
#ifndef __VECTORH__
#define __VECTORH__
 
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>
 
#define VECTOR_INIT_SIZE    4
#define VECTOR_HASSPACE(v)  (((v)->num_elems + 1) <= (v)->num_alloc_elems)
#define VECTOR_INBOUNDS(i)	(((int) i) >= 0 && (i) < (v)->num_elems)
#define VECTOR_INDEX(i)		((char *) (v)->elems + ((v)->elem_size * (i)))
 
typedef struct _vector {
	void *elems;
	size_t elem_size;
	size_t num_elems;
	size_t num_alloc_elems;
    void (*free_func)(void *);
} vector;
 
extern void vector_init(vector *, size_t, size_t, void (*free_func)(void *));
extern void vector_dispose(vector *);
extern void vector_copy(vector *, vector *);
extern void vector_insert(vector *, void *, size_t index);
extern void vector_insert_at(vector *, void *, size_t index);
extern void vector_push(vector *, void *);
extern void vector_pop(vector *, void *);
extern void vector_shift(vector *, void *);
extern void vector_unshift(vector *, void *);
extern void vector_get(vector *, size_t, void *);
extern void vector_remove(vector *, size_t);
extern void vector_transpose(vector *, size_t, size_t);
extern size_t vector_length(vector *);
extern size_t vector_size(vector *);
extern void vector_get_all(vector *, void *);
extern void vector_cmp_all(vector *, void *, int (*cmp_func)(const void *, const void *));
extern void vector_qsort(vector *, int (*cmp_func)(const void *, const void *));
static void vector_grow(vector *, size_t);
static void vector_swap(void *, void *, size_t);
 
#endif

And vector.c

/**
 * Hamid Alipour
 */
 
#include "vector.h"
 
extern void vector_init(vector *v, size_t elem_size, size_t init_size, void (*free_func)(void *))
{
	v->elem_size = elem_size;
	v->num_alloc_elems = (int) init_size > 0 ? init_size : VECTOR_INIT_SIZE;
	v->num_elems = 0;
	v->elems = malloc(elem_size * v->num_alloc_elems);
	assert(v->elems != NULL);
	v->free_func = free_func != NULL ? free_func : NULL;
}
 
extern void vector_dispose(vector *v)
{
	size_t i;
 
	if (v->free_func != NULL) {
		for (i = 0; i < v->num_elems; i++) {
			v->free_func(VECTOR_INDEX(i));
		}
	}
 
	free(v->elems);
}
 
 
extern void vector_copy(vector *v1, vector *v2)
{
	v2->num_elems = v1->num_elems;
	v2->num_alloc_elems = v1->num_alloc_elems;
	v2->elem_size = v1->elem_size;
 
	v2->elems = realloc(v2->elems, v2->num_alloc_elems * v2->elem_size);
	assert(v2->elems != NULL);
 
	memcpy(v2->elems, v1->elems, v2->num_elems * v2->elem_size);
}
 
extern void vector_insert(vector *v, void *elem, size_t index)
{
	void *target;
 
	if ((int) index > -1) {
		if (!VECTOR_INBOUNDS(index))
			return;
		target = VECTOR_INDEX(index);
	} else {
		if (!VECTOR_HASSPACE(v))
			vector_grow(v, 0);
		target = VECTOR_INDEX(v->num_elems);
		v->num_elems++; /* Only grow when adding a new item not when inserting in a spec indx */
	}
 
	memcpy(target, elem, v->elem_size);
}
 
extern void vector_insert_at(vector *v, void *elem, size_t index)
{
	if ((int) index < 0)
		return;
 
	if (!VECTOR_HASSPACE(v))
		vector_grow(v, 0);
 
	if (index < v->num_elems)
		memmove(VECTOR_INDEX(index + 1), VECTOR_INDEX(index), (v->num_elems - index) * v->elem_size);
 
	/* 1: we are passing index so insert won't increment this 2: insert checks INBONDS... */
	v->num_elems++;
 
	vector_insert(v, elem, index);
}
 
extern void vector_push(vector *v, void *elem)
{
	vector_insert(v, elem, -1);
}
 
extern void vector_pop(vector *v, void *elem)
{
	memcpy(elem, VECTOR_INDEX(v->num_elems - 1), v->elem_size);
	v->num_elems--;
}
 
extern void vector_shift(vector *v, void *elem)
{
	memcpy(elem, v->elems, v->elem_size);
	memmove(VECTOR_INDEX(0), VECTOR_INDEX(1), v->num_elems * v->elem_size);
 
	v->num_elems--;
}
 
extern void vector_unshift(vector *v, void *elem)
{
	if (!VECTOR_HASSPACE(v))
		vector_grow(v, v->num_elems + 1);
 
	memmove(VECTOR_INDEX(1), v->elems, v->num_elems * v->elem_size);
	memcpy(v->elems, elem, v->elem_size);
 
	v->num_elems++;
}
 
extern void vector_transpose(vector *v, size_t index1, size_t index2)
{
	vector_swap(VECTOR_INDEX(index1), VECTOR_INDEX(index2), v->elem_size);
}
 
static void vector_grow(vector *v, size_t size)
{
	if (size > v->num_alloc_elems)
		v->num_alloc_elems = size;
	else
		v->num_alloc_elems *= 2;
 
	v->elems = realloc(v->elems, v->elem_size * v->num_alloc_elems);
	assert(v->elems != NULL);
}
 
extern void vector_get(vector *v, size_t index, void *elem)
{
	assert((int) index >= 0);
 
	if (!VECTOR_INBOUNDS(index)) {
		elem = NULL;
		return;
	}
 
	memcpy(elem, VECTOR_INDEX(index), v->elem_size);
}
 
extern void vector_get_all(vector *v, void *elems)
{
	memcpy(elems, v->elems, v->num_elems * v->elem_size);
}
 
extern void vector_remove(vector *v, size_t index)
{
	assert((int) index > 0);
 
	if (!VECTOR_INBOUNDS(index))
		return;
 
	memmove(VECTOR_INDEX(index), VECTOR_INDEX(index + 1), v->elem_size);
	v->num_elems--;
}
 
extern void vector_remove_all(vector *v)
{
	v->num_elems = 0;
	v->elems = realloc(v->elems, v->num_alloc_elems);
	assert(v->elems != NULL);
}
 
extern size_t vector_length(vector *v)
{
	return v->num_elems;
}
 
extern size_t vector_size(vector *v)
{
	return v->num_elems * v->elem_size;
}
 
extern void vector_cmp_all(vector *v, void *elem, int (*cmp_func)(const void *, const void *))
{
	size_t i;
	void *best_match = VECTOR_INDEX(0);
 
	for (i = 1; i < v->num_elems; i++)
		if (cmp_func(VECTOR_INDEX(i), best_match) > 0)
			best_match = VECTOR_INDEX(i);
 
	memcpy(elem, best_match, v->elem_size);
}
 
extern void vector_qsort(vector *v, int (*cmp_func)(const void *, const void *))
{
	qsort(v->elems, v->num_elems, v->elem_size, cmp_func);
}
 
static void vector_swap(void *elemp1, void *elemp2, size_t elem_size)
{
	void *tmp = malloc(elem_size);
 
	memcpy(tmp, elemp1, elem_size);
	memcpy(elemp1, elemp2, elem_size);
	memcpy(elemp2, tmp, elem_size);
 
             free(tmp); /* Thanks to gromit */
}

It works :) I will write another post with some example usage soon…

Notice that, all the functions that return a value, return it through their arguments and not the “return” statement, this is because I wanted the client to be responsible for allocating/freeing memory for these variables and that makes everyone’s job easier.

As always, I’m open to criticism/ideas and please use it at your own risk.

Implementation of a Vector data structure in C
Comments (5)   Filed under: C Programming, Data Structures, Low Level, Programming   Posted by: Codehead

C++ needs a higher level standard library

I’m sure I’m not the only one who thought about this but I think one of the things that holds me back from using it more is the fact that C++ doesn’t have a higher level standard library.

A while back I was thinking of writing a thread library that works both on Windows (my desktop) and Linux (my server) and I gave up and used Python for the project.

The problem is that Python is not fast enough for parts of my project and I have to use either C or C++ but I will go with C++ because of it’s Map and Vector containers etc.

I’m not sure why they didn’t implement all the good stuff that are in Python standard library in C++ but I think it’s really time.

I also found this great set of tools that might be in the next C++ standard library:
http://www.boost.org/

This is exactly what C++ needs; I don’t see why cross platform libraries for threading, database access etc. shouldn’t be included in C++ standard library.

It has a lot of great features; objects, operator overloading, many kinds of containers, templates, namespaces and it’s very fast.

C++ needs a higher level standard library
Comments (0)   Filed under: C Programming, Low Level, Programming   Posted by: Codehead

A binary tree node insertion function

I was working on this for a few days and came up with 3 versions of this function, don’t even ask for the first one.
Here is the second version which is inspired by K&R’s example:

(Just read BTree as Binary Tree)

/** First Version **/
void BTree_Store(BTree *t, char *key, void *elem)
{
       t->root = BTree_Install(t, t->root, key, elem);
}
 
Node *BTree_Install(BTree *t, Node *parent, char *key, void *elem)
{
       int cmpResult;
 
       if (parent == NULL)
              parent        = BTree_NewNode(t, key, elem);
       else {
              cmpResult = t->cmpfn(parent->key, key, BTREE_MAX_KEY_SIZE);
              if (cmpResult == 0)
                     memcpy(parent->elem, elem, t->elemSize);
              else if (cmpResult < 0)
                     parent->lnode = BTree_Install(t, parent->lnode, key, elem);
              else
                     parent->rnode = BTree_Install(t, parent->rnode, key, elem);
       }
       return parent;
}

The problem with this (or my problem ;) ) is that I don’t like creation of stack frames and local variables over and over here, it might need like 40 of them and I knew I could do better so I came up with this version:

/** Second Version **/
void BTree_Store(BTree *t, char *key, void *elem)
{
       Node **n;
       int cmpResult;
 
       n = &t->root;
       while (*n != NULL) {
              cmpResult = t->cmpfn((*n)->key, key, BTREE_MAX_KEY_SIZE);
              if (cmpResult == 0)
                     break;
              else if (cmpResult < 0)
                     n = &((*n)->lnode);
              else
                     n = &((*n)->rnode);
       }
 
       if (cmpResult == 0)
              memcpy((*n)->elem, elem, t->elemSize);
       else
              *n = BTree_NewNode(t, key, elem);
}

I actually love this version, it’s quick, compact and right to the point.
Here is how the node and the tree structures look like:

struct node {
       char   *key;         /* Owned by tree */
       void   *elem;        /* Owned by tree */
       struct node *lnode;
       struct node *rnode;
};
 
typedef struct node Node;
 
struct btree {
       Node   *root;
       int    elemSize;
       int    numNodes;
       int    memUsed;
       int    (*cmpfn)(const char *, const char *, size_t);
};
 
typedef struct btree BTree;

The cmpfn is strncmp by defaults because keys are char *, here are the tree & node construction and destruction functions:

void BTree_Init(BTree *t, int elemSize, int (*cmpfn)(const char *, const char *, size_t))
{
       t->elemSize = elemSize;
       t->cmpfn    = cmpfn != NULL ? cmpfn : BTREE_DFLT_CMP_FN;
       t->numNodes = 0;
       t->memUsed  = 0;
       t->root     = NULL;
}
 
void BTree_Dispose(BTree *t)
{
       BTree_DisposeNodeRecursive(t, t->root);
}
 
static Node *BTree_NewNode(BTree *t, char *key, void *elem)
{
       Node *n;
 
       n             = (Node *) malloc(sizeof(Node));
       n->elem       = malloc(t->elemSize);
       memcpy(n->elem, elem, t->elemSize);
 
       n->key        = (char *) malloc(strlen(key) + 1); /* +1 for '\0' */
       strcpy(n->key, key);
 
       n->lnode      = NULL;
       n->rnode      = NULL;
 
       t->memUsed   += BTREE_NODE_SIZE(t, key);
       t->numNodes++;
 
       return n;
}
 
static void BTree_DisposeNode(BTree * t, Node *n)
{
       t->memUsed  -= BTREE_NODE_SIZE(t, n->key);
       t->numNodes--;
       free(n->key);
       free(n->elem);
       free(n);
}
 
static void BTree_DisposeNodeRecursive(BTree *t, Node *n)
{
       if (n->lnode != NULL)
              BTree_DisposeNodeRecursive(t, n->lnode);
 
       if (n->rnode != NULL)
              BTree_DisposeNodeRecursive(t, n->rnode);
 
       BTree_DisposeNode(t, n);
}

Here is the BTREE_NODE_SIZE macro:

#define BTREE_NODE_SIZE(t, k)      sizeof(Node) + strlen(k) + 1 + t->elemSize

And here is the search function:

Node *BTree_FindNode(BTree *t, char *key)
{
       Node *n;
       int cmpResult;
 
       n = t->root;
       while (n != NULL) {
              cmpResult = t->cmpfn(n->key, key, BTREE_MAX_KEY_SIZE);
              if (cmpResult == 0)
                     return n;
              else if (cmpResult < 0 && n->lnode != NULL)
                     n = n->lnode;
              else if (n->rnode != NULL)
                     n = n->rnode;
              else
                     break;
       }
 
       return BTREE_KEY_NOT_FOUND;
}
 
void *BTree_Get(BTree *t, char *key)
{
       Node *n;
       n = BTree_FindNode(t, key);
       return n != BTREE_KEY_NOT_FOUND ? n->elem : BTREE_KEY_NOT_FOUND;
}

The only problem with this tree is that if you store sorted data you will end up with a linked list rather than a binary search tree so I’m working on a self balancing binary search tree which is very chalanging but I love chalanges ;)

A binary tree node insertion function
Comments (1)   Filed under: C Programming, Low Level   Posted by: Codehead