The following is a brief overview of Lecture 6 of the ‘Programming Paradigms,” a programming class taught at Standford University. Screenshots and Code are included from the lecture. The ‘Programming Paradigms’ lectures can be found in iTunes. The link is on the Open Standford Website. The following lecture covers Implementing an Int Specific and Generic Stack in C/C++.

Int Specific Stack

stack.h
 
typedef struct{
	int * elems;
	int loglength;
	int alloclength;
} stack;
 
void StackNew(stack * s)
void StackDispose(stack * s)
void StackPush(stack * s, int value)
int  StackPop(stack * s)

The last lecture was left off with header file for a int specific stack being defined which includes a strcut called 'stack' and four functions. This lecture begins with defining StackNew and StackDispose for an int specific stack.

void StackNew(stack * s)
{
	s->loglength = 0;
	s->alloclength = 4
	s->elems = malloc(4 * sizeof(int))
	assert(s->elems != NULL);
}

When a new stack is allocated, the length is set originally to zero (because the stack is empty). Space is made for 4 elements, then malloc is used to allocate memory for those four elements. Malloc goes to the heap and finds 16 bytes of space, puts a "little halo" around the space, and then returns the base address of the memory. Assert confirms that elem is not equal to NULL just incase malloc fails for some reason. Asserts should be used to you clearly know where the program failed.

void StackDispose(stack * s)
{
	free(s);
}

StackDispose is trivial. The opposite of malloc, free is used. This gives the memory back to the heap.

void StackPush(stack * s, int value)
{
	if(s->loglength == s->alloclength){
		s->alloclength *= 2;
		s->elems = realloc(s->elems, s->alloclength * sizeof(int));
		assert(s->elems != NULL);
	}
 
	s->elemns[s->loglength] = value;
	s->loglength++;
}

In the function StackPush, you first want to check if you are out of memory to actually push value onto the Stack. If the current length of the stack is already equal to the allocated length, more memory will have to be allocated for the stack, else bad things will happen.

Actually, we want to go ahead and re-allocate the array. The previously allocated amount of memory is doubled. Then realloc is called. Realloc only exists in C, it doesn't exist in C++. Jerry says that he'll explain in a few weeks why realloc doesn't exist in C++. Realloc first sees if the memory can be allocated in place, meaning that realloc checks to see if the memory that comes after the previously allocated space in the heap is in use. If it isn't, it uses that memory. If it can't resize it in place, it copies all the elements over to a different block of memory, frees the old memory, and returns the address of the new memory.

If realloc is called with the first parameter being equal to NULL, it functions the same as a malloc command. This is useful if you don't want to call malloc once, then realloc every single time after that.

The doubling strategy is really popular because it only comes up once every 2^n times. 512 bytes of memory not big enough? Ok, let's allocate 1024. And so on.

int StackPop(stack *s)
{
	assert(s->loglength> 0);
	s->loglength--;
	return s->elems[s->loglength];
}

First, make sure that their is at least one object on the stack. Subtract one for loglength (the length of the stack), then return the new address of the stack which simulates the discarding of the last element on the stack.

Stack Using Generics

Next, the exact same stack functions will be implemented generically, not just for stack integers.

stack.h
typdef struct {
    void * elems;
    int elemSize;
    int loglength;
    int alloclength;
    ?? - Suspense Element
} stack;
 
void StackNew(stack * s, int elemSize);
void StackDispose(stack * s);
void StackPush(stack * s, void * elemAddr);
void StackPop(stack * s, void * elemAddr);

The above is the setup for the stack functions that will be implemented generically. Note that not all the information has yet been given as suspense element will be added later to the stack struct. 70% of the code for the generic stack functions is the same as the int specific stack functions.

void StackNew(stack * s, int elemSize)
{
	assert(s->elemSize > 0);
	s->length = 0;
	s->alloclength = 4;
	s->elemSize = elemSize;
	s->elems = malloc(4 * elemSize);
	assert(s->elems != NULL);
}

The second parameter (elemSize) tells the length of a single element, so malloc is used to pre-allocate 4 elements on the stack of size elemSize. Assert is used to make your life easier. It checks to make sure actual memory was allocated and to make sure elemSize was not accidentally set to zero.

void StackDispose(stack * s)
{
	free(s->elems);
 
}

StackDispose is again trivial.

void StackPush(stack *s, void * elemAddr)
{
	if(s->loglength == s->alloclength)
		StackGrow(s);
 
	void * target = (char *) s->elems + s->loglength * s->elemSize;
	memcpy(target, elemAddr, s->elemSize);
	s->loglength++;
 
}

In StackPush, if the stack needs more memory allocated, StackGrow() is called to allocate that memory. Target points to the block of memory already pre-allocated in the stack where the element will be copied.. Memcpy is used to do the actual copying of the element to that address. Remember to cast s->elems as a char * to trick the compiler because it cannot cast as a void *.

The word static has like 80 or 85 meanings in C++. Here is one more. When you see the word static decorating the prototype of a c or c++ function such as:

stack void StackGrow(stack *s)

This means that it is a private function that should not be advertised outside this file. In companies like Microsoft which deal with programs with tens of thousands of files, many times function names will conflict with each other if not made static.

static void StackGrow(stack *s)
{
	s->alloclength *=2;
	s->elems = realloc(s->elems, s->alloclength * s->elemSize);
}

StackGrow re-allocates double the amount of memory just like the int specific version.

void StackPop(stack *s, void * elemAddr)
{
	void * source = (char*) s->elems + (s->loglength - 1) * s->elemSize;
	memcpy(elemAddr, source, s->elemSize)
	s->loglength--;
}

In StackPop(), source points to the last chunk of data in memory on the stack. Memcpy copies that memory to the memory address, then the length of the stack is decremented thus "popping" off the memory from the stack.

When dealing with generics, it is very easy to get the program to compile because the compiler looks at all the void * declarations and stamps them as "good." However, when running a program implementing generics, it is very likely to crash.