2
\$\begingroup\$

The below post is a follow-up of Generic stack implementation.

Below follows a header-only implementation of a generic stack (inspired by stb-libraries, following these guidelines: stb-howto.txt). After incorporating @Coderodde's advice into the code, I am left with:

#ifndef STACK_H
#define STACK_H

/* To use, do this:
 *  #define STACK_IMPLEMENTATION
 * before you include this file in *one* C file to create the implementation.
 *
 * i.e. it should look like:
 * #include ...
 * #include ...
 *
 * #define STACK_IMPLEMENTATION
 * #include "stack.h"
 * ...
 *
 * To make all the functions have internal linkage, i.e. be private to the
 * source file, do this:
 * #define IO_STATIC
 * before including "stack.h"
 *
 * i.e. it should look like:
 * #define STACK_IMPLEMENTATION
 * #define STACK_STATIC
 * #include "stack.h"
 * ...
 *
 * You can define STACK_MALLOC, STACK_REALLOC, and STACK_FREE to avoid using 
 * malloc(), realloc(), and free().
 */

#ifndef STACK_DEF
    #ifdef STACK_STATIC
        #define STACK_DEF   static
    #else
        #define STACK_DEF   extern
    #endif                          /* STACK_STATIC */
#endif                              /* STACK_DEF */

#if defined(__GNUC__) || defined(__clang__) || defined(__INTEL_LLVM_COMPILER) 
    #define ATTRIB_NONNULL(...)             __attribute__((nonnull(__VA_ARGS__)))
    #define ATTRIB_WARN_UNUSED_RESULT       __attribute__((warn_unused_result))
    #define ATTRIB_MALLOC                   __attribute__((malloc))
#else
    #define ATTRIB_NONNULL(...)             /**/
    #define ATTRIB_WARN_UNUSED_RESULT       /**/
    #define ATTRIB_MALLOC                   /**/
#endif                          /* defined(__GNUC__) || defined(__clang__) || defined(__INTEL_LLVM_COMPILER) */

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

typedef struct stack Stack;

/*
 * Creates a stack with `cap` elements of size `memb_size`. 
 *
 * The stack can only store one type of elements. It does not support
 * heterogeneuous types. 
 *
 * Returns a pointer to the stack on success, or NULL on failure to allocate 
 * memory.
 */
STACK_DEF Stack *stack_create(size_t cap, size_t memb_size) 
    ATTRIB_WARN_UNUSED_RESULT ATTRIB_MALLOC;

/* 
 * Pushes an element to the top of the stack referenced by `s`. It automatically
 * resizes the stack if it is full.
 *
 * Whilst pushing an element, there's no need of a cast, as there is an implicit
 * conversion to and from a void *.
 *
 * On a memory allocation failure, it returns false. Else it returns true.
 */
STACK_DEF bool stack_push(Stack *s, const void *data)
    ATTRIB_NONNULL(1, 2) ATTRIB_WARN_UNUSED_RESULT;

/*
 * Removes the topmost element of the stack referenced by `s` and returns it. 
 * If the stack is empty, it returns NULL.
 *
 * The returned element should be casted to a pointer of the type that was 
 * pushed on the stack, and then dereferenced.
 * 
 * Note that casting to a pointer of the wrong type is Undefined Behavior, and
 * so is dereferencing to performing arithmetic on a void *.
 */
STACK_DEF void *stack_pop(Stack *s) ATTRIB_NONNULL(1);

/* 
 * Returns a pointer to the topmost element of the stack referenced by `s`
 * without removing it.  If the stack is empty, it returns NULL.
 */
STACK_DEF const void *stack_peek(const Stack *s) ATTRIB_NONNULL(1);

/*
 * Returns true if the capacity of the stack referenced by `s` is full, or false
 * elsewise.
 */
STACK_DEF bool stack_is_full(const Stack *s) ATTRIB_NONNULL(1);

/*
 * Returns true if the count of elements in the stack referenced by `s` is zero,
 * or false elsewise.
 */
STACK_DEF bool stack_is_empty(const Stack *s) ATTRIB_NONNULL(1);

/* 
 * Returns the count of elements in the stack referenced by `s`.
 */
STACK_DEF size_t stack_size(const Stack *s) ATTRIB_NONNULL(1);

/*
 * Destroys and frees all memory associated with the stack referenced by `s`.
 */
STACK_DEF void stack_destroy(Stack *s) ATTRIB_NONNULL(1);

#endif                          /* STACK_H */

#ifdef STACK_IMPLEMENTATION

#if defined(IO_MALLOC) != defined(IO_REALLOC) || defined(IO_REALLOC) != defined(IO_FREE)
    #error  "Must define all or none of IO_MALLOC, IO_REALLOC, and IO_FREE."
#endif

#ifndef STACK_MALLOC
    #define STACK_MALLOC(sz)       malloc(sz)
    #define STACK_REALLOC(p, sz)   realloc(p, sz)
    #define STACK_FREE(p)          free(p)
#endif

struct stack {
    void *data;
    size_t size;
    size_t cap;
    size_t memb_size;
};

STACK_DEF bool stack_is_full(const Stack *s)
{
    return s->size == s->cap;
}

STACK_DEF bool stack_is_empty(const Stack *s)
{
    return s->size == 0;
}

STACK_DEF const void *stack_peek(const Stack *s)
{
    if (stack_is_empty(s)) {
        return NULL;
    }

    return (char *) s->data + (s->size - 1) * s->memb_size;
}

STACK_DEF Stack *stack_create(size_t cap, size_t memb_size)
{
    if (cap == 0 || memb_size == 0 || cap > SIZE_MAX / memb_size) {
        return NULL;
    }

    Stack *const s = STACK_MALLOC(sizeof *s);

    if (s) {
        /* Would it be an improvement to round this up to the nearest
         * multiple/power of 2.
         */
        size_t total_size = memb_size * cap;
        s->data = STACK_MALLOC(total_size);

        if (s->data) {
            s->cap = cap;
            s->size = 0;
            s->memb_size = memb_size;
        } else {
            free(s);
            return NULL;
        }
    }

    return s;
}

STACK_DEF bool stack_push(Stack *s, const void *data)
{
    if (s->size >= s->cap) {
        /* If we cannot allocate geometrically, we shall allocate linearly. */ 
        if (s->cap > SIZE_MAX / 2) {
            if (s->cap + BUFSIZ < s->cap) {
                return false;
            }
            s->cap += BUFSIZ;
        } else {
            s->cap *= 2;
        }

        if (s->cap > SIZE_MAX / s->memb_size) {
            return false;
        }

        void *const tmp = STACK_REALLOC(s->data, s->cap * s->memb_size);

        if (!tmp) {
            return false;
        }

        s->data = tmp;
    } 

    char *const target = (char *) s->data + (s->size * s->memb_size);

    memcpy(target, data, s->memb_size);
    return !!++s->size;
}

STACK_DEF void *stack_pop(Stack *s)
{
    if (stack_is_empty(s)) {
        return NULL;
    }

    --s->size;
    void *const top = (char *) s->data + (s->size * s->memb_size);
        
    if (s->size && (s->size <= s->cap / 4)) {
        void *const tmp = realloc(s->data, s->cap / 2 * s->memb_size);
        
        if (tmp) {
            s->data = tmp;
            s->cap /= 2;
        } 
        /* Else do nothing. The original memory is left intact. */
    }
    
    return top;
}

STACK_DEF void stack_destroy(Stack *s)
{
    STACK_FREE(s->data);
    STACK_FREE(s);
}

STACK_DEF size_t stack_size(const Stack *s)
{
    return s->size;
}

#endif                          /* STACK_IMPLEMENTATION */

#ifdef TEST_MAIN

#include <assert.h>

int main(void)
{
    /* We could support heterogenuous objects by using void pointers. */
    Stack *stack = stack_create(SIZE_MAX - 1000, sizeof (size_t));
    assert(!stack);

    stack = stack_create(1000, sizeof (int));
    assert(stack);

    for (int i = 0; i < 150; ++i) {
        assert(stack_push(stack, &i));
    }
    
    assert(!stack_is_empty(stack));
    assert(stack_size(stack) == 150);
    assert(*(int *) stack_peek(stack) == 149);

    for (int i = 149; i >= 0; i--) {
        assert(*(int *) stack_peek(stack) == i);
        assert(*(int *) stack_pop(stack) == i);
    }
    stack_destroy(stack);
    return EXIT_SUCCESS;
}

#endif                          /* TEST_MAIN */

Review Request:

What I am mainly interested in are my new overflow checks and reallocation strategy, namely in stack_create(), stack_push(), and stack_pop().

Other comments are also welcome.

Edit:

This is how it can be used:

#define GSTACK_IMPLEMENTATION     // Include the implementation as well
#define GSTACK_STATIC             // Make all functions static
#define TEST_MAIN                 // Include a sample main() function
\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

Name space

Code is taking up stack, stack_..., Stack, STACK_....

I can foresee user code collisions as "stack" is very common.

Consider something like gstack, gstack_..., GSTACK_... and not gStack.

... an improvement to round this up ...

        /* Would it be an improvement to round this up to the nearest
         * multiple/power of 2. */

No. Rounding up makes sense only if you understand STACK_MALLOC() better than the implementer of STACK_MALLOC().

Really going to test this well?

Do you really want linear growth of say a BUFSIZ of 4k when SIZE_MAX is 264 - 1?

Instead when geometric growth not possible either:

  • Fail.

  • Use SIZE_MAX/memb_size to simplify testing. Fail if above that.

I'd go for the first.

Why 4?

Magic numbers vs named constants.

if (s->size && (s->size <= s->cap / 4)) { deserves explanation.

Unclear why !!

As the return type is bool, why !!? What benefit do you see?

// return !!++s->size;
return ++s->size;

Why define IO_STATIC?

 * To make all the functions have internal linkage, i.e. be private to the
 * source file, do this:
 * #define IO_STATIC
 * before including "stack.h"

Where are IO_... defined?

Code is for a generic stack type. Does it compile with a generic C compiler?

#if defined(IO_MALLOC) != defined(IO_REALLOC) || defined(IO_REALLOC) != defined(IO_FREE)
    #error  "Must define all or none of IO_MALLOC, IO_REALLOC, and IO_FREE."

1 .h file vs. a .c and .h file

This .h file brings in various #include <....h> files that would not be needed with classic .c, .h file approach.

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

Unclear why code always includes <stdio.h>, <stdint.h>.

[Edit]
Tolerate stack_destroy(NULL)

As free(NULL) is OK, allow stack_destroy(). This simplifies caller's clean-up code.

STACK_DEF void stack_destroy(Stack *s) {
  if (s) {  // Add condition
    STACK_FREE(s->data);
    STACK_FREE(s);
  }
}
\$\endgroup\$
5
  • \$\begingroup\$ "Where are IO_... defined?" ==> Like the opening comment states, one can define these to replace the standard malloc(), realloc(), and free(). That's the approach stb-libraries take, and IO_STATIC is an idiom I took from them too. \$\endgroup\$
    – Harith
    Mar 5 at 19:27
  • \$\begingroup\$ " That's the approach stb-libraries take," --> stb-libraries and IO_STATIC are not in the standard C spec. Are you coding to the C spec? Please post link to approach stb-libraries take. \$\endgroup\$ Mar 5 at 19:34
  • \$\begingroup\$ Oops, I thought I had added a link in the follow-up too. I have edited the question now. \$\endgroup\$
    – Harith
    Mar 5 at 19:42
  • \$\begingroup\$ @Harith How is IO_STATIC used here? Comments suggest to define it, (without explanation) and then code does not use it. \$\endgroup\$ Mar 5 at 22:01
  • \$\begingroup\$ It wasn't used in the sample main program, because it was in the same file. I have added an example now. It is only now that I realize that IO_STATIC has been a typo for GSTACK_STATIC all along. \$\endgroup\$
    – Harith
    Mar 7 at 12:32
1
\$\begingroup\$

Use-after-free bug:

In stack_pop():

    --s->size;
    void *const top = (char *) s->data + (s->size * s->memb_size);
        
    if (s->size && (s->size <= s->cap / 4)) {
        void *const tmp = realloc(s->data, s->cap / 2 * s->memb_size);
        
        if (tmp) {
            s->data = tmp;
            s->cap /= 2;
        } 
        /* Else do nothing. The original memory is left intact. */
    }

The lifetime of s->data ends with the call to realloc(), assuming it succeeded, so top is pointing to a block of memory that might have already been freed whilst shrinking.

GCC 12.3 caught the bug with -O1 -Wall -Werror -Wpedantic.

In file included from <source>:269:
<source>: In function 'main':
<source>:291:16: error: pointer used after 'realloc' [-Werror=use-after-free]
  291 |         assert(*(size_t *) gstack_pop(stack) == i);
      |                ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In function 'stack_pop',
    inlined from 'main' at <source>:291:9:
<source>:238:27: note: call to 'realloc' here
  238 |         void *const tmp = realloc(s->data, s->memb_size * new_cap);
      |                           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cc1: all warnings being treated as errors

If you remove -O1 it doesn't detect anything. GCC 13.1 and 13.2 did not detect the bug, or if they did, they did not output anything.

Valgrind also reports a read error for this in stack_pop().

The solution is to move the statement to the end of the function:

return (char *) s->data + (s->size * s->memb_size);

This also eliminated the variable top.

Incomplete documentation:

The documentation should include a warning about pushing function pointers onto the stack, as function pointers may not be compatible with a void *.

Aside:

stack_is_empty(), stack_is_full(), stack_size(), and stack_peek() are pure functions and may benefit from __attribute__((pure)). They are not constant functions because they're accessing global memory.

\$\endgroup\$
5
  • \$\begingroup\$ " pushing function pointers onto the stack, as that would invoke undefined behavior." --> How would pushing invoke UB? Perhaps popping and using the pointer when its original size > void *. \$\endgroup\$ Mar 7 at 15:46
  • \$\begingroup\$ @chux-ReinstateMonica Because a void * and a function pointer are not compatible according to (6.3.2.3 Pointers) "8 A pointer to a function of one type may be converted to a pointer to a function of another type and back again; the result shall compare equal to the original pointer. If a converted pointer is used to call a function whose type is not compatible with the referenced type, the behavior is undefined." Or is my understanding of it awry? \$\endgroup\$
    – Harith
    Mar 7 at 16:06
  • \$\begingroup\$ Your quote 1) does not certainly imply incompatibility - only potential incompatibility. 2) The push does not invoke UB - hence the problem with " pushing function pointers onto the stack, as that would invoke undefined behavior." . The pop does not invoke UB. The potential UB is a function call with the pointer after the push, pop. " If a converted pointer is used to call " --- IOWs, the concern is good, but the place where UB occurs is mis-placed. \$\endgroup\$ Mar 7 at 16:13
  • \$\begingroup\$ @chux-ReinstateMonica That makes sense. What would you suggest I change the documentation to? \$\endgroup\$
    – Harith
    Mar 7 at 16:28
  • \$\begingroup\$ Perhaps "The documentation should include a warning about pushing function pointers onto the stack, as function pointers may not be compatible with a void ." \$\endgroup\$ Mar 7 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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