Home > C Programming

C Programming

Understanding Pointers In C – C Pointers Tutorial

We need to cover some ground so be patient and you will learn all about pointers.

A computer stores variables in it’s memory and the memory is basically a series of zeros and ones.

So if you could see the raw contents of your RAM you would see something similar to this:

010010010111111101010010101001010100101111001010100111001

Although your memory will have much more number of zeros and ones but it’s basically laid out like this.

In C when you say:

int x = 5;

This line basically telling the compiler to store 5 in variable x that is of type int.

The int datatype is 2 or 4 bytes depending on the implementation – and on my computer it’s 4

bytes but I assume 2 bytes here – so the compiler allocates 2 bytes of memory to store the number 5.

It will convert it to binary for you and 5 is 101 in binary but your compiler will store this in 2 bites so it will look like this:

0000000000000101

Note that it’s just padded with zeros so it can fit in a 2 byte space.

Depending on your operating system this could look like this:

1010000000000000

The first one looks more intuitive and mathematically correct so we use the first type in our examples. It is also called big endian architecture.

So if you were to map the memory, it would look something like this:

0100100101111111010100100000000000001010101001010100101111001010100111001

Can you see our number in there? How about now:

01001001011111110101001|0000000000000101|0101001010100101111001010100111001

Let’s define a pointer and set it to point to our number in memory:

int x = 5;
int *y = &x;

The second line is telling the compiler that y is a pinter to int, pointer is the address of our

variable in memory so y is basically this:

01001001011111110101001->|0000000000000101|0101001010100101111001010100111001

The & operator behind x returns it’s position in memory, if you count it’s 23.

So if you print y it will print the address of the variable which in our simple example is 23 so:

printf("%d", y);

Would print 23, but the cool thing is that you can do this:

printf("%d", *y);

The * is derefrancing operator, what it does is simple asks the compiler to dereference y and find the variable it’s pointing to and print that, so the program won’t print the number 23 anymore, instead it goes to the address 23 and grabs the value that is sitting there and prints that:

01001001011111110101001->|0000000000000101|0101001010100101111001010100111001

But you see, there are so many zeros and ones there, how does the compiler know how many of them

are actually part of our variable, because it picks only 5 of them:

01001001011111110101001->|00000|<-00000000101|0101001010100101111001010100111001

They will all be zeros and we know that this is wrong, our value was 5 not zero.

That’s why you defined a pointer to int, the compiler knows that it’s looking for an int so when you say *y – or derefrence y – the compiler goes to address 23 and grabs 2 bytes from there:

01001001011111110101001->|0000000000000101|<-0101001010100101111001010100111001

This is basically what a pointer is and one of the thing that can be done with a pointer is to modify the original variable without touching the original variable, so if you where to do this:

int x = 5;
int *y = &x;
*y = 20;

The compiler would look at y and go to address 23 and modify the contents in there to 20 rather than 5, so if you print x, you will get 20 rather than 5.

Pointers enable us to do some advanced stuff using C, that would be the subject of my next post.

Note: this tutorials are meant to be as simple as possible so a lot of details such as how pointers are stored are omitted to prevent confusion and will be discussed at some future point.

Comments (0) Filed under: C Programming, Data Structures, Programming Posted by: Codehead

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.

Comments (5) Filed under: C Programming, Data Structures, Low Level, Programming Posted by: Codehead

Eclipse “Launch Failed. Binary Not Found.” and Netbeans

Last night I needed a C++ IDE right away; I had Eclipse for writing Python and knew that it had a C/C++ extension called CDT.

So I installed this CDT and I also had MingW and Cygwin installed but the only project I could compile was the sample Hello World project.

Whenever I made an empty project, Eclipse responded with “Launch Failed. Binary Not Found.”.

I read a few articles online but no luck and I didn’t want to spend a lot of time on it so I decided to try Netbeans.

After I installed Netbeans, BAM, it detected Cygwin and compiled everything right away!!!

That is what I wanted, I wanted an IDE that I can just make a CPP file and compile without any extra steps and Netbeans did that for me!

I’m not a C++ or Eclipse guru but I’m a normal user who is searching for simplicity and doesn’t have a lot of time to waste on things like this.

Update:

Read the comments bellow for some possible solutions…

Comments (61) Filed under: C Programming, IDEs, 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.

Comments (0) Filed under: C Programming, Low Level, Programming Posted by: Codehead

Comparing Programming Languages

I just found this great tool and I thought I’d share it, it compares performance and memory usage in any two programming languages, it has a good list of languages too.

For example, this is the comparison between PHP and C:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=gcc&lang2=php

PHP vs Python:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=python&lang2=php

Python vs Ruby:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=python&lang2=ruby

C vs Java:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=gcc&lang2=java

And finally C vs C++:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=gcc&lang2=gpp

Comments (2) Filed under: C Programming, Fun, General, 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

Comments (1) Filed under: C Programming, Low Level Posted by: Codehead