tags:

views:

174

answers:

6

What is the best correct way of implementing a dynamically resizing stack in C?

For example, i want to allocate an amount of memory to a stack but when that stack gets full, the memory allocated is doubled to accomodate new data, etc.

I have a stack implemented at the minute using a simple array of void pointers, this way i can store pointers of all types so it's quite reusable. When i try to implement this using malloc()/realloc() i run into errors while doing pointer math due to void pointers not having a size assigned.

What is the best correct way to implement a dynamically resizable stack in C?

EDIT:

I was trying something like this code (error checking removed) but i now understand that i can not interact with void pointers like this. So i'm just having a think how to do something like this legally. This is a big learning exercise for me as i've never really been exposed to C.

#include <stdio.h>
#include <stdlib.h>

#include "stack.h"

static int index = 0;

void* CreateStack(void)
{
    void *stack = malloc(INITIAL_STACK_SIZE);
    return stack;
}

void* Pop(void *stack)
{
    return stack + index--;
}

void Push(void *stack, void *value)
{
    *(stack + index) = value;
}

void FreeStack(void *stack)
{
    free(stack);
}
+4  A: 

I think the problem is you're using the wrong size in your calls. You don't want the size of the pointee - you want the size of the pointer itself.

Anon.
+1  A: 

One method is to use an array for the stack. Keep track of the array capacity. If the array becomes full, allocate a new array, copy old elements to new array, then delete the old array.

Another option is to use a linked-list as the foundation for the stack. This allows dynamic allocation on every new element.

Thomas Matthews
+3  A: 

sounds like you are doing

malloc(n * sizeof(void)) 

directly or indirectly, you need

malloc(n * sizeof(void*))

of course the real answer is std::stack (in c++)

pm100
Nah, the "real" answer is java.util.Stack (in Java). Or even better, a Lisp list.
Steve Jessop
The real answer is ... practice!
Aiden Bell
C++ is never the real answer to a C question aside from "What do you get if you append two plus signs to a C?"
Chuck
+1  A: 

I've answered this before, as a subset of a previous question:

http://stackoverflow.com/questions/2006726/which-would-you-prefer-to-have-to-maintain/2007647#2007647

You'd have to adapt things slightly - replace char* with void* throughout, rename "addString" to "push" and write a "pop" function. Oh, and add error-checking on the calls to malloc and realloc, which was omitted in that answer because it was omitted in the questioner's code.

Like Neil says, though "best" is very subjective. A growing array is only one way to implement a stack. Depending on the usage pattern and your requirements on code complexity, speed and memory use, you might want a linked list, or you might want a hybrid list/array strategy similar to the std::deque class in C++.

Steve Jessop
A: 

Using malloc/realloc is how you should do this. If your doing something dynamic in C it normally requires it. I'm not sure if your issue is a big issue. Void pointers don't have a size and cannot be dereferenced, therefore in order to used with pointer arithmetic or dereference they must be type caste. I'm not sure what your storing in your stack, anything of any size? If so you're going to need to keep track of this by including some meta data inside of your stack.

If you're just having trouble with void pointers maybe we need some code to help you out.

Derek Litz
A: 

Use Dave Hanson's code from C Interfaces and Implementations. It's a great book, and you'll see just how to do the dynamic-array trick. Elegant and efficient, and highly reusable! The code is free to download.

Norman Ramsey