You Are Here Home > Data Structures

Data Structures

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.

Understanding Pointers In C – C Pointers Tutorial
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.

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