4
\$\begingroup\$

Following on from my previous question: C pointer based growable stack

I have made some improvements (hopefully!) based on the very helpful comments and suggestions. I have checked that the stack can push and pop doubles now, so hopefully it will also be OK with structs.

I have a could of questions regarding the changes I have made:

  1. I noticed memcpy() didn't work with void * so I switched to using uin8_t; is that recommended/necessary or could I have cast to uint8_t for memcpy()? Not sure which approach is the best...
  2. How should a failed malloc()/realloc() be handled? Return an error code? Exit? Return NULL?

Again, I would greatly appreciate any suggestions/criticism:

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

#define MAX_ITEMS 16

typedef struct {
    uint8_t *data;
    size_t itemSize;
    unsigned count;
    unsigned capacity;
} Stack;

void stack_init(Stack *stack, size_t itemSize, unsigned capacity);
bool stack_is_empty(const Stack *stack);
void stack_push(Stack *stack, void *item);
void* stack_pop(Stack *stack);
void stack_destroy(Stack *stack);

void stack_init(Stack *stack, size_t itemSize, unsigned capacity)
{
    unsigned initialCapacity = capacity == 0 ? 1 : capacity;
    size_t size = initialCapacity * itemSize;

    stack->count = 0;
    stack->capacity = initialCapacity;
    stack->itemSize = itemSize;
    stack->data = (uint8_t *)malloc(size);

    if (stack->data == NULL)
    {
        // TODO
    }

    memset(stack->data, 0, size);
}

bool stack_is_empty(const Stack *stack)
{
    return stack->count == 0;
}

void stack_push(Stack *stack, void *item)
{
    if (stack->count >= stack->capacity)
    {
        stack->capacity *= 2;
        stack->data = (uint8_t *)realloc(stack->data, stack->capacity * stack->itemSize);

        if (stack->data == NULL)
        {
            // TODO
        }
    }

    unsigned offset = stack->count * stack->itemSize;
    memcpy(stack->data + offset, item, stack->itemSize);
    stack->count++;
}

void* stack_pop(Stack *stack)
{
    if (stack_is_empty(stack) == true)
    {
        // TODO
    }

    uint8_t *item = (uint8_t *)malloc(stack->itemSize);

    if (item == NULL)
    {
        // TODO
    }

    stack->count--;
    unsigned offset = stack->count * stack->itemSize;
    memcpy(item, stack->data + offset, stack->itemSize);

    return (void *)item;
}

void stack_destroy(Stack *stack)
{
    free(stack->data);
    stack->count = 0;
}

int main(void)
{
    Stack stack;
    stack_init(&stack, sizeof(int), 0);

    for (int i = 0; i < MAX_ITEMS; i++)
    {
        stack_push(&stack, (void *)&i);
    }

    while (!stack_is_empty(&stack))
    {
        int value;
        value = *((int *)stack_pop(&stack));
        printf("%d\n", value);
    }

    stack_destroy(&stack);
}

\$\endgroup\$
5
\$\begingroup\$
    stack->data = (uint8_t *)realloc(stack->data, stack->capacity * stack->itemSize);

This is wrong, because if realloc() failed, then there's now no way to access the memory previously pointed to by stack->data. The correct pattern for realloc() is:

void *newData = realloc(stack->data, stack->capacity * stack->itemSize);
if (!newData) {
    // Insert error handling - you'll want to restore the old stack->capacity here
    // or (better) wait until we're okay before updating.
    return FAILURE:
}
stack->data = newData;

I recommend against casting the result of malloc() family when assigning - these functions return void*, which is assignable to any pointer type without a cast. The unnecessary cast just distracts the reader (because casts generally indicate danger areas in code). The same is true for conversions from pointer types to void*, such as this one:

return (void *)item;

That can simply be

return item;

The stack_pop interface is difficult to use - callers have to deal with possible null pointer return, and must remember to free() the result. Instead, consider having the caller provide memory to write into:

void stack_pop(Stack *stack, void *target);

The caller should already know the size required for target, and can now get results in local (auto) storage:

int foo;
stack_pop(&stack, &foo);
// no need to check for null, or to call free()
\$\endgroup\$

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.