Basic 'char' Stack implementation in C

Question

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#define STACK_SIZE 100

typedef struct _stack
{
    char *mem;
    size_t size;
    int top;
} STACK;

STACK *stack_create(char *mem, size_t size);
void stack_push(STACK *stack, char c);
char stack_pop(STACK *stack);
char stack_peek(STACK *const stack);
void stack_print(STACK *stack);
int main() {
    char stack_mem[STACK_SIZE];

    STACK *my_stack = stack_create(stack_mem, STACK_SIZE);
    stack_push(my_stack, 'a');
    stack_push(my_stack, 'b');
    stack_push(my_stack, 'c');
    stack_push(my_stack, 'd');
    stack_print(my_stack);
    printf("Top of stack contains: %c\n", stack_peek(my_stack));
    stack_pop(my_stack);
    stack_print(my_stack);
    stack_pop(my_stack);
    stack_pop(my_stack);
    stack_pop(my_stack);
    stack_push(my_stack, 'j');
    stack_push(my_stack, 'k');
    stack_print(my_stack);

    free(my_stack);
    return EXIT_SUCCESS;
}



STACK *stack_create(char *mem, size_t size) {

    assert(mem && size);

    STACK *output = malloc(sizeof(STACK));

    output->mem = mem;
    output->size = size;
    output->top = -1;
    return output;
}

void stack_push(STACK *stack, char c)
{
    assert(stack);

    if(c < 0)
    {
        fprintf(stderr, "This stack is not designed for negative char values\n");
        return;
    }
    if((stack->top + 1) < stack->size)
    {
        stack->mem[stack->top + 1] = c;
        stack->top++;
    }
    return;
}

char stack_pop(STACK *stack)
{
    assert(stack);

    if(stack-> top < 0)
    {
        fprintf(stderr, "Cannot pop from empty stack.\n");
        return -1;
    }

    char o;
    o = stack->mem[stack->top];
    stack->top--;
    return o;
}

char stack_peek(STACK * const stack)
{
    assert(stack);

    if(stack->top < 0)
    {
        fprintf(stderr, "Nothing on stack to peek at.\n");
        return -1;
    }
    return stack->mem[stack->top];
}

void stack_print(STACK *stack)
{
    assert(stack);
    if(!stack->top)
    {
        fprintf(stderr, "Nothing on stack to print.\n");
        return;
    }
    printf("Entire stack:\n");
    int i;
    for(i = stack->top; i >= 0; --i)
    {
        printf("%c\n", stack->mem[i]);
    }
}

Please provide feedback on whatever you see fit, however, error handling would be a helpful focus.

Answer 1

Datatype

The size_t size is appropriate, but int top is less. This effectively limits an entire size_t to just storing INT_MAX, and the only value that is negative is -1, the rest are wasted. gcc gave me a warning about comparing integers of different signs, but they should moreover be the same type because they are both storing indices; instead of size and top, it's more effective to store capacity and size, which is top + 1.

Code Coverage

You don't account for all return values from malloc; specifically, if null is returned, you program will write to it and crash.

Error messages are printed on stderr, which is a good habit, especially if one is doing a unix command-driven application. However, in a general library, I would not expect output from the code at all, (except when I ask.) This probably necessitates having a way to return an error condition, such as a return,

if(c < 0) return errno = EDOM, 0;

or just silently ignoring mis-formed input like the stack_push is already doing for the size,

if(stack->size >= stack->capacity || c < 0) return;

Naming

You've come up with a naming system that reduces potential namespace conflicts when defining non-static functions carefully. This is excellent for the reuseabity of your code.

_stack is a dangerous name, as explained in the C faq, "all identifiers beginning with an underscore are reserved for ordinary identifiers (functions, variables, typedefs, enumeration constants) with file scope." Also, typedef and tags have different namespace, and your names are distinct anyway, so you aren't really gaining much. You aren't self-referencing, so you might as well make it an anonymous struct. However, even if you don't agree, it's worth checking out the Linux kernel style typedef, (which says it's a mistake to typedef in this case.)

I would say that capitalized typedef names have a connotation of being constant. However, has some precedent in C, (eg, FILE.)

Design

Writing a test case is a great software engineering design practice.

Your usage of assert is effective at specifying the contract must be followed when calling a function.

In 3 places you mix declarations and code that could easily be swapped to make it C90-compatible, should you so desire.

Your design choice of specifying the stack size and STACK_SIZE is confusing. While it finds use in existing char arrays that one wants to put a stack on top of temporarily, or perhaps stacks on the stack (sic,) it's generally better to contain the implementation's external dependencies as much as possible. Instead of passing mem, consider,

struct Stack *stack_create(const size_t capacity) {
    struct Stack *output;

    assert(capacity);

    if(!(output = malloc(sizeof *output + capacity))) return 0;

    output->mem = (char *)(output + 1);
    output->capacity = capacity;
    output->size = 0;
    return output;
}

Answer 2

You could allow to initialize the stack locally. Just by separating the bigger part of stack_create to separate function.

void stack_init(STACK* stack, char* mem, size_t size)
{
    stack->mem = mem;
    stack->size = size;
    stack->top = -1;
}

char stack_mem[STACK_SIZE];
STACK stack;
stack_init(&stack, stack_mem, STACK_SIZE);

As for error handling, stack usualy does not handle it. You should instead offer the "is empty?" and "is full?" functions. Consumers of the stack are then responsible for making sure stack is not empty before they peek or pop, and that it is not full before they push. Check for emptiness is often integral part of algorithms using the stack anyway. Check for fullness not so much, it Is mostly limitation of a fixed size stack. But the consumer must check it nevertheless or they must be sure that bigger stack is never needed.

In stack_create you should check if malloc returns null then dont assign to properties and return null as well. Consumers are again responsible for checking this situation.

One last point, the stack_create could be complemented with stack_destroy.