Stack API for generic values

Question

I'm trying to create a stack library from scratch. It stores generic elements which are passed in void* pointers.

This is the defined structure:

typedef struct stackObject
{
    void* obj;
    struct stackObject *next;
} StackObject_t;

typedef struct stackMeta
{
    StackObject_t *stack;
    size_t objsize;
    int numelem;
} StackMeta_t;

So far I have implemented the following:

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

/* Creates a stack of c objects of size objsize and returns
 * a handle (pointer) to the just created stack. On error, 
 * NULL is returned.*/
StackMeta_t *mystack_create(size_t objsize)
{
    StackMeta_t *newstack = malloc(sizeof(StackMeta_t));
    if(newstack != NULL && objsize > 0){
        newstack->stack = NULL;
        newstack->objsize = objsize;
        newstack->numelem = 0;
        return newstack;
    }
    else{
        return NULL;
    }
}

/* Pushes an object to the stack identified by its handle
 * returns 0 on success and -1 on an error*/
int mystack_push(StackMeta_t *stack, void* obj)
{
    /* pointer to new object */
    StackObject_t *newObj = malloc(sizeof(StackObject_t));
    newObj->obj = malloc(stack->objsize);
    
    if(newObj != NULL){
        newObj->obj = memcpy(newObj->obj, obj, stack->objsize);
        newObj->next = stack->stack; 
        stack->stack = newObj;
        stack->numelem++;
        return 0;
    }
    else{ /* no space available */
        return-1;
    }
}

/* Pops an object from the stack identified by its handle
 * returns 0 on success and -1 on an error*/
int mystack_pop(StackMeta_t *stack, void* obj)
{
    StackObject_t *tempObj = stack->stack;
    if(tempObj != NULL){
        obj = memcpy(obj, tempObj->obj, stack->objsize);
        stack->stack = tempObj->next;
        stack->numelem--;
        free(tempObj->obj);
        free(tempObj);
        return 0;
    }
    else{
        return -1;
    }
}

/* Destroys and cleans the stack handle */
void mystack_destroy(StackMeta_t *stack)
{
    StackObject_t *tempObj = stack->stack;
    StackObject_t *nextObj = NULL; 
    while(tempObj != NULL){
        nextObj = tempObj->next;
        free(tempObj->obj);
        free(tempObj);
        tempObj = nextObj;
    }
    stack = NULL;
}

/* Returns number of elements of the stack or -1 if invalid handle*/
int mystack_nofelem(StackMeta_t *stack)
{
    if(stack != NULL){
        return stack->numelem;
    }
    return -1;
}

What is the purpose of the objsize parameter? It seems to be unused, as you only store pointers to the objects. — Martin R
– Martin R, Commented Nov 3, 2021 at 8:45
I can't help but point out that C++ has container types as part of its standard library, and language support for generic code. — JDługosz
– JDługosz, Commented Nov 3, 2021 at 16:19

Toby Speight · Accepted Answer · 2021-11-03 09:23:34Z

Data structure

We've implemented a stack using a linked list. That will work, but is likely less efficient than using a growable array.

We only store pointers to the objects in the stack, meaning that we are dependent on the owners of those objects for lifecycle. If any of the objects is freed while we hold a pointer, we don't know that the pointer is no longer valid.

It might make sense to copy the passed objects to our stack instead (and if we did that, we would actually need the objsize member, to allocate sufficient storage).

Why is numelem a (signed) int? I think size_t is more appropriate for a count of objects.

Code

The following headers are included but not needed:

#include <stddef.h>
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

malloc() and related functions work with void*, so there's no need to cast when assigning to other pointer types. It's also good practice to use an expression rather than a type as argument to sizeof operator:

    StackMeta_t *newstack = malloc(sizeof *newstack);

If we pass a zero size, we allocate newstack but then leak it. I would test for that before the allocation:

StackMeta_t *mystack_create(size_t objsize)
{
    if (objsize == 0) {
        return NULL;
    }

    StackMeta_t *newstack = malloc(sizeof *newstack);
    if (newstack) {
        newstack->objsize = objsize;
        newstack->numelem = 0;
        newstack->stack->next = NULL;
    }
    return newstack;
}

However, think about whether we really need the stack structure to be in allocated memory. Is there really a good reason we shouldn't be able to use automatic storage? It might be better to provide

bool mystack_init(StackMeta_t&, size_t)

We can still provide mystack_create(), but now implemented by using the init function on our allocated object.

Why does mystack_push() return int? We had an include of <stdbool.h> that we didn't use, and that would be a good choice of return type to indicate success or failure.

mystack_pop() looks like it might be better to return a pointer, with NULL indicating failure.

mystack_nofelem() can take its argument as pointer-to-const.

I have to emphasize the remark that linked lists are slow on modern architectures. Memory access time dominates, and jumping around gives you a cold cache. Allocating and freeing when pushing and popping will be slow. There are hour-long talks given at conferences and papers published showing that memory locality is king, and a std::vector beats a linked list even at things they teach you that linked lists are good for, for a surprisingly large list size. — JDługosz
– JDługosz, Commented Nov 3, 2021 at 16:22
For very large stacks, a hybrid solution works well - a linked list of contiguous blocks of items, so we don't get problems when we realloc(). But don't do that until it's necessary, as it adds a lot of bookkeeping complexity (and if/when you do, then unit-test it half to death!). — Toby Speight
– Toby Speight, Commented Nov 3, 2021 at 16:46

chux · Accepted Answer · 2021-11-03 22:13:53Z

objsize == 0

Why error? Code is (should be) certainly capable of handling objsize == 0.

As is, code leaks memory when objsize == 0 as mystack_create() allocation is lost.

Allocate to the size of the referenced type

Its easier to code right, review and maintain.

// newstack = malloc(sizeof(StackMeta_t));
newstack = malloc(sizeof *newstack);

Missing StackMeta.h

I'd expect a companion StackMeta.h with the public functions. Put the documentation there. Users do not need to see the implementation nor the details of StackMeta_t.

Info hiding

Consider adding access functions instead of exposing struct members to the public.

Use const as able

This allows greater application as const data may pushed.

// int mystack_push(StackMeta_t *stack, void* obj)
int mystack_push(StackMeta_t *stack, const void* obj)

Tolerate mystack_destroy(NULL)

Like free(NULL) is OK, test the pointer. This simplifies calling code usage, especially in error handling.

void mystack_destroy(StackMeta_t *stack) {
  if (stack) {
    StackObject_t *tempObj = stack->stack;
    ...

Pedantic: Pushing too much is OK?

No detection of impending stack->numelem++ overflow.

Why clear sometimes

stack = NULL; at the end of mystack_destroy() has merit, so does clearing data before free'ing it - which is not done.

Consider a peek()

Code some way to get the top without popping.

int mystack_peek(const StackMeta_t *stack, void* obj);

Consider an apply()

Code some way to apply a function to each member of the stack. Very useful.

int mystack_apply(const StackMeta_t *stack, int foo(void *state, void *obj), void *state) {
  // For each member of the stack, call foo(state, obj)
  // If return value is non-zero, quit loop early with that value.

Reduce error

Now, mystack_nofelem(NULL) returns -1 (an error). I'd consider such benign function calls on NULL as OK and just return 0 here.

I doubt calling code is going to check for -1.

Advanced: Research restrict

Selectively use restrict on pointers for greater optimization potential.

Example: The compiler can assume stack and obj do not point to overlapping data. (And you are letting the caller know not to attempt such pathological code.)

// int mystack_pop(StackMeta_t *stack, void* obj)
int mystack_pop(StackMeta_t * restrict stack, void* restrict obj)

Stack Exchange Network

Stack API for generic values

2 Answers 2

Data structure

Code

You must log in to answer this question.

Hot Network Questions

Stack API for generic values

2 Answers 2

Data structure

Code

You must log in to answer this question.

Related

Hot Network Questions