Generic stack implementation (revision)

Question

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

Answer 1

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 2⁶⁴ - 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);
 }
}

• Madagascar: "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.
• chux: " 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.
• Madagascar: Oops, I thought I had added a link in the follow-up too. I have edited the question now.
• chux: @Harith How is IO_STATIC used here? Comments suggest to define it, (without explanation) and then code does not use it.
• Madagascar: 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.

Answer 2

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.

• chux: " 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 *.
• Madagascar: @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?
• chux: 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.
• Madagascar: @chux-ReinstateMonica That makes sense. What would you suggest I change the documentation to?
• chux: Perhaps "The documentation should include a warning about pushing function pointers onto the stack, as function pointers may not be compatible with a void ."