10
\$\begingroup\$

I'm a C beginner. I'm studying and implementing some data structures. I'd like to get feedback.

This is a stack implemented with an dynamic array.

In main there is some test code which use a basic testing function.

INITIAL_CAPACITY is set to 1 to "stress test" the API.

All the code is in one file because I'd like to store all these implementations in single files (as snippets) for future reference, this is also the reason why not all the #includes are at the top: only those strictly necessary for the implementation are at the beginning.

/*
 * Dynamic stack, C implementation.
 *
 * Simple stack implementation with a dynamic array: the array doubles its
 * capacity if the stack is full, halves its capacity if the stack is full for a
 * quarter.
 */


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

#define INITIAL_CAPACITY 1

typedef struct
{
        unsigned int capacity;
        unsigned int top;
        int *items;
} dstack;

/*
 * create_stack:  creates and return a (pointer to a) new empty dynamic stack.
 *                Dies if fails.
 */
dstack *create_stack(void);

/*
 * size:  return the number of items stored in stack.
 */
unsigned int size(const dstack *stack);

/*
 * is_empty:  return true if stack does not contains items, false otherwise.
 */
bool is_empty(const dstack *stack);

/*
 * peek:  return (but does not remove) the last item added to stack.
 */
int peek(dstack *stack);

/*
 * push:  adds item to stack.
 */
void push(dstack *stack, int item);

/*
 * pop:  removes and returns the last item added to stack.
 *       Dies if stack is empty.
 */
int pop(dstack *stack);

/*
 * resize_stack:  changes stack total capacity to new_capacity.
 *                Dies if fails.
 */
static void resize_stack(dstack *stack, unsigned int new_capacity);

/*
 * free_stack:  frees the memory occupied by stack.
 */
void free_stack(dstack *stack);

/*
 * die:  prints message on stderr and calls exit(EXIT_FAILURE).
 */
static void die(const char *message);


dstack *create_stack(void)
{
        dstack *new_stack = malloc(sizeof(*new_stack));

        if (new_stack == NULL) {
                die("stack creation failed");
        }
        new_stack->capacity = 0;
        new_stack->top = 0;
        new_stack->items = NULL;
        resize_stack(new_stack, INITIAL_CAPACITY);

        return new_stack;
}

unsigned int size(const dstack *stack)
{
        return stack->top;
}

bool is_empty(const dstack *stack)
{
        return stack->top == 0;
}

int peek(dstack *stack)
{
        if (is_empty(stack)) {
                free_stack(stack);
                die("attempt to peek from an empty stack");
        }
        return stack->items[stack->top - 1];
}

void push(dstack *stack, int item)
{
        if (stack->top == stack->capacity) {
                resize_stack(stack, 2 * stack->capacity);
        }
        stack->items[stack->top++] = item;
}

int pop(dstack *stack)
{
        if (is_empty(stack)) {
                free_stack(stack);
                die("attempt to pop from an empty stack");
        }
        int item = stack->items[--stack->top];

        if (stack->top > 0 && stack->top == stack->capacity / 4) {
                resize_stack(stack, stack->capacity / 2);
        }
        return item;
}

static void resize_stack(dstack *stack, unsigned int new_capacity)
{
        void *new_pointer = realloc(stack->items,
                                    sizeof(*(stack->items)) * new_capacity);
        if (new_pointer == NULL) {
                free_stack(stack);
                die("array resize failed");
        }
        stack->items = new_pointer;
        stack->capacity = new_capacity;
}

void free_stack(dstack *stack)
{
        free(stack->items);
        free(stack);
}

static void die(const char *message)
{
        fputs("Error: stack: ", stderr);
        fputs(message, stderr);
        puts("");
        exit(EXIT_FAILURE);
}


#include <assert.h>


static void loop_test(dstack *stack, unsigned int n)
{
        assert(size(stack) == 0);
        assert(is_empty(stack));

        for (int i = 0; i < n; i++) {
                push(stack, i);
                assert(peek(stack) == i);
        }
        assert(size(stack) == n);
        if (n > 0) {
                assert( ! is_empty(stack));
        }

        for (int i = n - 1; i >= 0; i--) {
                assert(peek(stack) == i);
                assert(pop(stack) == i);
        }
        assert(size(stack) == 0);
        assert(is_empty(stack));
}

int main(void)
{
        dstack *s = create_stack();

        loop_test(s, 0);
        loop_test(s, 1);
        loop_test(s, 10);
        loop_test(s, 100);
        loop_test(s, 1000);
        loop_test(s, 10000);

        push(s, 'k');
        push(s, 'o');
        push(s, ' ');
        push(s, 't');
        push(s, 's');
        push(s, 'e');
        push(s, 't');

        while ( ! is_empty(s)) {
                printf("%c", pop(s));
        }
        puts("");

        free_stack(s);
}
\$\endgroup\$
  • 3
    \$\begingroup\$ You grow the array by the factor of 2, however, there are different opinions on the matter. Also, shrinking right away might be a bad idea. If you get hit with pop-push-pop-push.... sequence right on the boundary, alloc calls would be plenfiful, which is bad. \$\endgroup\$ – Daerdemandt Aug 22 '17 at 14:23
  • \$\begingroup\$ Minor note: if your public API functions have preconditions (peek and pop require a non-empty stack) you should at least document those in the comment. Having some way to return success/failure, as Serge says, is even better. \$\endgroup\$ – Useless Aug 22 '17 at 17:19
  • \$\begingroup\$ @Daerdemandt the growth factor of 2 was chosen for simplicity. The array is resized when is full for a quarter, shouldn't this "alleviate" the pop-push-pop-push... alloc problem you are saying? \$\endgroup\$ – MarcoLucidi Aug 22 '17 at 17:20
  • \$\begingroup\$ @Useless yeah, of course you are right! In the comment of pop I wrote "Dies if stack is empty.", in peek I forgot to do so, my bad. I definitively have to look for some proper "error reporting" method =) \$\endgroup\$ – MarcoLucidi Aug 22 '17 at 17:32
  • \$\begingroup\$ @MarcoLucidi * The array is resized when is full for a quarter* yes, that will do (I didn't notice that). \$\endgroup\$ – Daerdemandt Aug 22 '17 at 18:15
11
\$\begingroup\$

So you have build a dynamic size stack containing integers, and you guarantee that the allocated size if a power of 2 and the used size is between the allocated size and its quarter.

This automatic down-resizing of the stack is a rather uncommon requirement, so you should think twice before implementing it in real world code, but it is not really the point.

You have consistently declared and commented your functions, so it could be used as a nice .h file. Good point.

You code gave me one warning in loop test at for (int i = 0; i < n; i++) { ... because n is unsigned. While generally harmless, this kind of warning should be avoided because it can lead to undefined result. So here, you really should use for (unsigned int i = 0; i < n; i++) {.... In fact size_t should be even more appropriate, both for i and n.

In resize_stack, you use an unnecessary void * new_pointer where you could directly use stack->items. Not really expensive (only wastes a void *) but IMHO it does not really make the code more clear nor more maintainable.

But I strongly urge you not to use a die function for error processing in an utility library. I did it (I was a beginner too...) once, and the library was later used in a program that had its standard output connected to the equivalent of /dev/null and a special logging library. As you can imagine, the program sometimes was stopping with no message in the log system and this took some time to be identified because everybody had forgotten the ugly die.

So if this should be an utility library, please use an error code and let the caller do the error processing. For the same reason, I would not destroy the stack on error: let the caller decide whether the error is really a fatal one. That is just an application of the general separation of concerns rule.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you for the feedback! Yeah, my bad on the warning, I forgot to enable the compiler flag and the thing went unnoticed while debugging. When I was writing that die function, I had the feeling that it was a "wrong approach" (now I have the confirmation), along with the destruction of the stack in case of error, in fact, the void * in resize_stack was there from the beginning, to "not lose the original pointer" in case realloc returns NULL and leave the stack untouched, but then I had the "brilliant idea" to write die and call it whenever something goes wrong. \$\endgroup\$ – MarcoLucidi Aug 22 '17 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.