Dynamic stack in C - new version

Question

Not long ago, I posted this dynamic stack for review. Now I wrote a new version, which is hopefully a better one.

Please take a look and let me know how I could improve performance and increase code quality.

It works by storing pointers to the content. If there's not enough memory, it will try to increase the allocated space.

header

#ifndef DYNAMIC_STACK
#define DYNAMIC_STACK

#define DSTACK_SUCCESS 1
#define DSTACK_ERROR 0

//The stack just stores pointers
typedef struct Dynamic_Stack Dynamic_Stack;
struct Dynamic_Stack {        
    void **start; //Array of pointer to void
    void **position;
    void **end;
};

//Set up stack
int dstack_init(Dynamic_Stack *stack, size_t slots);

void dstack_free(Dynamic_Stack *stack);
void dstack_clear(Dynamic_Stack *stack);
int dstack_push(Dynamic_Stack *stack, void *new_element);
void *dstack_pop(Dynamic_Stack *stack);

//0 is the top of the stack
void *dstack_peek(Dynamic_Stack *stack, size_t levels);
int dstack_increase_capacity(Dynamic_Stack *stack, size_t new_slots);
int dstack_decrease_capacity(Dynamic_Stack *stack, size_t remove_total);
void dstack_shrink_to_fit(Dynamic_Stack *stack);

#endif

c file

#include <stdlib.h>
#include "dynamic_stack.h"

#define MULTIPLIER 1.00 //Increase by 100% on every expansion
#define FIXED_EXPANSION 0 //Overrides multiplier


//Internal
//Must keep at least 1 slot or it will break
static int dstack_resize(Dynamic_Stack *stack, size_t new_slot_capacity)
{   
    size_t position = stack->position - stack->start;

    void *temp = realloc(stack->start, new_slot_capacity * sizeof(void *));
    if(temp == NULL)
        return DSTACK_ERROR;

    stack->start = temp;
    stack->end = stack->start + new_slot_capacity;

    //Put position back if needed
    stack->position = (position < new_slot_capacity)
                                ? stack->start + position
                                : stack->end;

    return DSTACK_SUCCESS;
}

#if FIXED_EXPANSION >= 1
static int expand(Dynamic_Stack *stack)
{   
    return dstack_resize(stack, stack->end - stack->start + FIXED_EXPANSION);
}

#else
static int expand(Dynamic_Stack *stack)
{
    //Check if multiplier is producing at least 1 new slot
    size_t old_slots = stack->end - stack->start;
    size_t new_slots = old_slots * MULTIPLIER;

    if(new_slots == 0)
        return DSTACK_ERROR;

    return dstack_resize(stack, old_slots + new_slots);
}
#endif


//Public
//Set up stack
int dstack_init(Dynamic_Stack *stack, size_t slots)
{
    if((stack->start = malloc(sizeof(void *) * slots)) == NULL)
        return DSTACK_ERROR;

    stack->position = stack->start;
    stack->end = stack->start + slots;
    return DSTACK_SUCCESS;
}

void dstack_free(Dynamic_Stack *stack)
{
    free(stack->start);
}

void dstack_clear(Dynamic_Stack *stack)
{
    stack->position = stack->start;
}

int dstack_push(Dynamic_Stack *stack, void *new_element)
{
    if(stack->position == stack->end && expand(stack) == DSTACK_ERROR)
        return DSTACK_ERROR;

    *stack->position = new_element;
    ++stack->position;
    return DSTACK_SUCCESS;
}

void *dstack_pop(Dynamic_Stack *stack)
{
    if(stack->position == stack->start)
        return NULL;

    return *--stack->position;
}

//0 is the top of the stack
void *dstack_peek(Dynamic_Stack *stack, size_t levels)
{
    if(levels >= stack->position - stack->start)
        return NULL;

    return *(stack->position - 1 - levels);
}

int dstack_increase_capacity(Dynamic_Stack *stack, size_t new_slots)
{
    return dstack_resize(stack, stack->end - stack->start + new_slots);
}

int dstack_decrease_capacity(Dynamic_Stack *stack, size_t remove_total)
{
    if(remove_total >= stack->end - stack->start)
        return DSTACK_ERROR;

    return dstack_resize(stack, stack->end - stack->start - remove_total);
}

//Always leave 1 extra slot so there's no risk of resizing to 0
void dstack_shrink_to_fit(Dynamic_Stack *stack)
{
    dstack_resize(stack, stack->position - stack->start + 1);
}

example

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

int main(void)
{
    char *words[] = {
        "One",
        "Two",
        "Three",
        "Four",
        "Five",
        "Six",
        "Seven",
        "Eight",
        "Nine",
        "Ten",
        "Eleven",
        "Twelve",
        ""
    };

    Dynamic_Stack stack;
    if(!dstack_init(&stack, 12))
        return 1;

    for(char **ite = words; **ite != '\0'; ++ite){
        dstack_push(&stack, *ite);
    }

    size_t i = 0;
    for(char **ite = words; **ite != '\0'; ++ite)
        puts(dstack_peek(&stack, i++));

    dstack_increase_capacity(&stack, 8);
    dstack_shrink_to_fit(&stack);

    for(char *ite; (ite = dstack_pop(&stack)) != NULL; ++ite)
        puts(ite);


    dstack_free(&stack);

    return 0;
}

Answer 1

Sorry, but I really don't like the use of raw void* and pointer arithmetic everywhere. The whole code would be simpler if you added a typedef:

typedef void* Slot;

and globally replace void * with Slot

I don't normally like hiding pointer types behind a typedef but in this case the void* is not really a pointer - it is just storage space.

Having done that, redefine the stack as follows:

struct Dynamic_Stack {
    Slot *slots;
    size_t position;
    size_t size;
};

So the current insertion point and the stack size are both just integers, not pointers. You can now replace all of your pointer arithmetic (each of which gives a compilation warning with -Wsign-conversion and -Wsign-compare) with simple indices. You must also replace accesses to the slots with array access:

int dstack_push(Dynamic_Stack *stack, Slot new_element)
{
    ...
    stack->slots[stack->position++] = new_element;

---

Some other issues:

The expansion mechanism is odd. Using a floating point size multiplier and then returning a runtime error when the compile-time multiplier turns out to have the wrong value (produces a zero expansion) in some circumstance is wrong. I'd suggest you keep it simple and just double the size of the stack when expanding unless it turns out that this is bad for your application (I can't see why it should be - you have facilities for shrinking the stack after all). You have made it more complicated than it needs to be.

In your dstack_pop and dstack_peep you have wrongly mixed the data and error return values. It is quite valid for me to push zero onto the stack and I expect to be able to pop zero too, but these two functions return zero on error. You need to separate the error return from the data:

Slot dstack_pop(Dynamic_Stack *stack, int *status);

or

int dstack_pop(Dynamic_Stack *stack, Slot *slot);

Also, the stack parameter to dstack_peek should be const

---

Minor point, in the code before my renaming etc, dstack_resize has the following line:

size_t position = stack->position - stack->start;

I would not reuse the name position for the index when stack->position is a pointer in the structure.

Answer 2

Regarding performance: as the major operations (push and pop) are O(1) and you wrote them in a straightforward way, it is hard to optimize them in a way which would not be annulled (or even reversed in effect) by compiler or CPU optimizations. OTOH, it is also hard to envision a situation where program performance would even be remotely depending on your stack code - as you are (in most cases) dealing with "something bigger than an int", every push/pop is accompanied by an operation on the data item which will very likely outweigh the stack operations by a factor.

(minor nitpick: in the pop-function you could and should use two operations to decrease the stackpointer and return the value a) to be symmetric to the code in push b) to save the programmer coming after you from needing to remember what *-- means exactly)