The data structures you will see in this class use as their type void *. This site tries to describe both the purpose and usefulness of such structures.

In previous classes, you may have created a linked list that stores integers; however, as you may guess, this is not always useful. If you wanted to create a linked list of a different type, you would have to make a complete copy of the source code with the only difference being that there is a change in the type. As you may guess, this would make maintainability exceptionally painful: if you discovered a bug in one version, you would have to correct that bug in all the different versions.

Macros

One alternative in C is to use macros. In the source directory is a file macro_stack.c that implements a stack using C-style macros. You will note that it replaces what appear to be function calls with other operations. The source is not very intuitive and it is likely to lead to programming and maintenance issues.

Use of Arbitrary Pointers

If a variable is declared to be of type

	void *ptr;

it is variable storing an address with no indication of what type is being stored there. Thus, it is never possible to dereference a void pointer; that is, the following code in void.c does not compile:

#include <stdio.h>

int main() {
	int i;
	void *ptr;

	ptr = &i;
	printf( "%d\n", *ptr );

	return 0;
}

Instead, you get the following error:

% gcc void.c 
void.c: In function in 'main'
void.c:8: warning: dereferencing 'void *' pointer
void.c:8: error: invalid use of void expression

This can, however, be useful in creating a data structure that stores pointers to arbitrary objects. Thus, if we create a data structure such as the following

struct stack {
	void *array;
	int array_size;
	int array_capacity;
};

we could then store pointers to arbitrary objects in the stack. For example, we may have the following structure representing process control blocks (PCBs):

struct pcb {
	int pid;
	int priority;
	int program_counter;
	// ...
};

Now, the memory for the PCBs would already be allocated in, for example, an array. Thus, if these PCBs had to be, for example, inserted into a stack, it would only be necessary to insert the addresses, as is shown in the code under pcb_stack.c:

#include <stdio.h>
#include "Stack.h"

struct pcb {
	int pid;
	int priority;
	int number_of_children;
};

int main() {
	struct pcb array[8] = {
		{0532, 4, 0}, {1945, 5, 0}, {2241, 9, 0}, {3893, 0, 0},
		{4523, 1, 0}, {5914, 0, 0}, {6235, 7, 0}, {7521, 5, 0}
	};

	int i;

	struct Stack s;
	init( &s, 10 );

	push( &s, &( array[3] ) );
	push( &s, &( array[7] ) );
	push( &s, &( array[4] ) );
	push( &s, &( array[2] ) );
	push( &s, &( array[6] ) );

	for ( i = 0; i < 5; ++i ) {
		struct pcb *ptr = top( &s );
		printf( "PID:  %d\n", ptr->pid );
		pop( &s );
	}

	deinit( &s );

	return 0;
}

The source directory also contains the source for Stack.h.

The output of this code, when compiled, is:

% gcc pcb_stack.c
% ./a.out 
PID:  6235
PID:  2241
PID:  4523
PID:  7521
PID:  3893

Thus, the stack data structure did not care it was storing pointers to PCBs: they were stored and returned when asked.

Note: if we wanted to combine the two lines

		struct pcb *ptr = top( &s );
		printf( "PID:  %d\n", ptr->pid );

into one, it is still necessary to indicate to the compiler what is being returned:

		printf( "PID:  %d\n", ((struct pcb *)top( &s ))->pid );

Thus, the return value of top is cast to a struct pcb *, and only after the casting do we access the field.

Problems with the C Model

Because C stores arbitrary pointers, it may be possible that incorrect casting may occur: for example, you could place a pointer to a different type or structure into a data structure. Then, when you take it out, you will mistake that memory location for something else. For example, the following code in casting.c assigns void *p the address of an integer and then the address of a double. In both cases, the value is assigned to int *q which has the compiler interpret both as if they were integers.

#include <stdio.h>
#include <math.h>

int main() {
	int i = 7;
	double d;
	void *p;
	int *q;

	p = &i;
	q = p;

	printf( "%d\n", *q );

	// This prints pi
	d = 4*atan( 1 );
	printf( "%f\n", d );

	p = &d;
	q = p;

	// Now C will interpret the floating-point
	// number as an integer

	printf( "%d\n", *q );

	return 0;
}

When this is executed, you get:

% gcc casting.c
% ./a.out 
7
3.141593
1413754136

Basically, the binary representation of π is 01000000 00001001 00100001 11111011 01010100 01000100 00101101 00011000. As this is run on an Intel chip, it is stored in little-endian format, or the eight bytes are stored in reverse order: 00011000 00101101 01000100 01010100 11111011 0010000 00001001 010000001. When the second printf statement, however, attempts to access this date, it is under the impression that these 0s and 1s represent a 32-bit integer. Thus, it takes the first four bytes and interprets them as the binary integer 01010100010001000010110100011000 (note the order is reversed) or .

Why reverse the bytes, or little endian? Recall that when you do any mathematical operation on integers, you are always starting with the least significant digits (or bits) first. Thus, if you are adding two 32-bit integers, you add the least-significant bytes in an 8-bit adder and with the resulting carry, add the next-least-significant bytes and and them, and so on. With a little consideration, you should see that it it actually quite reasonable that the bytes should be stored in reverse order.