3
\$\begingroup\$

The provided code (a header-only library inspired by stb libraries] defines functions for creating a stack, pushing elements onto the stack, popping elements from the stack, peeking at the top element without removing it, checking if the stack is full or empty, getting the size of the stack, and destroying the stack.

Note: The implementation does not support heterogeneous types.

#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__)
#define ATTRIBUTE_NONNULL(...)              __attribute__ ((nonnull (__VA_ARGS__)))
#define ATTRIBUTE_WARN_UNUSED_RESULT        __attribute__ ((warn_unused_result))
#else
#define ATTRIBUTE_NONNULL(...)          /* If only. */
#define ATTRIBUTE_WARN_UNUSED_RESULT    /* If only. */
#endif                          /* defined(__GNUC__) || defined(__clang__) */

#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, unsigned int memb_size)
    ATTRIBUTE_WARN_UNUSED_RESULT;

/* 
 * 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)
    ATTRIBUTE_NONNULL(1, 2) ATTRIBUTE_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) ATTRIBUTE_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) ATTRIBUTE_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) ATTRIBUTE_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) ATTRIBUTE_NONNULL(1);

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

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

#endif                          /* STACK_H */

#ifdef STACK_IMPLEMENTATION

#if defined(STACK_MALLOC) && defined(STACK_REALLOC) && defined(STACK_FREE)
// Ok.
#elif !defined(STACK_MALLOC) && !defined(STACK_REALLOC) && !defined(STACK_FREE)
// Ok.
#else
#error  "Must define all or none of STACK_MALLOC, STACK_REALLOC, and STACK_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;
    unsigned int 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;
}

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, unsigned int memb_size)
{
    if (!cap || !memb_size) {
        return NULL;
    }

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

    if (s) {
        s->data = STACK_MALLOC(memb_size * cap);

        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) {
        s->cap *= 2;
        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);

    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(100, 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);
    assert(*(int *) stack_peek(stack) == 149);
    assert(*(int *) stack_peek(stack) == 149);

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

#endif                          /* TEST_MAIN */

Are there any bugs or undefined/implementation-defined behavior in the code?

How can it be modified to support heterogeneous types?

General coding comments, style, et cetera.

\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

Advice I - unsigned int memb_size

This is a counter. Therefore, I suggest using a data type that is tailored for counting: size_t memb_size;.

Advice II - More verbose zero comparisons

In stack_is_empty, you write: !s->size;. I suggest you write instead s->size == 0;.

Advice III - stack_create

In stack_create, you write:

if (!cap || !memb_size) {
    return NULL;
}

Why not:

if (cap == 0 || memb_size == 0) {
    return NULL;
}

Advice IV - Contract the stack when too small

I suggest this: when the load factor of your stack drops below 25%, halve its capacity. This will optimize the memory usage of your stack while keeping the running time complexity of stack_pop as amortized \$\Theta(1)\$. This is a basic stuff from CLRS.

\$\endgroup\$
5
  • \$\begingroup\$ Should stack_pop() fail and return NULL if resizing was unsuccessful? Would it also be an improvement to raise memb_size up to the nearest power of 2? \$\endgroup\$
    – Harith
    Mar 2 at 14:20
  • \$\begingroup\$ @Harith If you allow NULLs as a datum, you have no much choice than abort():ing. \$\endgroup\$
    – coderodde
    Mar 2 at 14:55
  • \$\begingroup\$ @Harith I don’t see your logic of increasing member size field to the nearest power of two. After all, shouldn’t it be a constant throughout the stack? \$\endgroup\$
    – coderodde
    Mar 2 at 14:58
  • \$\begingroup\$ Excuse the unclear comment. I was speaking of the case where an odd capacity is passed to stack_create(). Would it be an improvement to round it up to the nearest power of 2? (That reminds me, I didn't check for integer overflow before the call to malloc(). cap * memb_size can overflow.) \$\endgroup\$
    – Harith
    Mar 2 at 15:00
  • \$\begingroup\$ @Harith You are free to give any initial capacity you want. When pushing to a full stack, double its capacity. When load factor drops below 25%, do halve the capacity of the stack. Under this arrangement, both push and pop will run in amortized constant time. \$\endgroup\$
    – coderodde
    Mar 4 at 16:42

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.