7
\$\begingroup\$

I've been studying C for a while, as a programmer coming from a C++ background, I'm used to the standard library, STL, etc., and I quickly realized that I need some kind of a containers library/data structure implementations in C. So as an exercise decided to write one! I also intend to use it on my personal C projects, so it's got to be good!

Here is my stack implementation.

cstack.h:

/**
 * @file cstack.h
 *
 * @brief Contains the definition for `cstack` along with the `cstack_*` function signatures.
 */

#ifndef CSTACK_H
#define CSTACK_H

typedef signed long long cstack_size_t;

typedef struct
{
    cstack_size_t item_size; /**< The size of a single stack item, e.g. sizeof(int) */
    char* data;              /**< The beginning of the stack. */
    char* top;               /**< Pointer to the first empty 'slot' in the stack. */
    char* cap;               /**< Pointer to the end of the stack. */
} cstack;

/**
 * @brief Allocate a new stack.
 *
 * @param initial_items_count Specifies how many items should the function allocate space for upfront.
 * @param item_size The size (in bytes) of a single item, must be > 0. e.g. `sizeof(int)`.
 * @return The newly allocated stack. NULL on failure.
 */
cstack* cstack_alloc(cstack_size_t initial_items_count,cstack_size_t item_size);

/**
 * @brief Free the memory allocated by the stack.
 *
 * @param stack The stack whose memory to free.
 */
void cstack_free(cstack* stack);

/**
 * @brief Push a new item onto the stack.
 *
 * @param stack The stack to push the item onto.
 * @param item The item to push onto the stack.
 *
 * @note
 * - The stack is modified in place.
 * - In the case where the stack is full, i.e. `cstack_full() != 0`, the stack is expanded as necessary.
 * - In case of failure, the stack remains intact, and the contents are preserved.
 */
void cstack_push(cstack* stack, void* item);

/**
 * @brief Pop the last (top) item out of the stack.
 *
 * @param stack The stack which to pop the item from.
 *
 * @note
 * - The stack is modified in-place.
 * - In case the stack is already empty, `i.e. cstack_empty() != 0`, nothing is done.
 */
void cstack_pop(cstack* stack);

/**
 * @brief Expand `stack` by `count`.
 *
 * @param stack The stack which to expand.
 * @param count Specifies the number of _extra items_ to add to the stack, must be > 0.
 * @return The expanded stack.
 *
 * @note
 * - The stack is modified in-place.
 * - The stack is expanded by count _items_ (_NOT_ bytes).
 * - In case of failure, the function returns _NULL_, and the contents of `stack` are preserved.
 */
cstack* cstack_expand(cstack* stack, cstack_size_t count);

/**
 * @brief Truncate/Shrink the stack.
 *
 * @param stack The stack to truncate.
 * @param count Specifies the number of items to remove from the stack, must be > 0.
 *
 * The function Shrinks the stack by the amount of _items_ (_NOT_ bytes) specified
 * by count.
 *
 * The items removed are relative to the stack's capacity _Not_ size.
 * for example:
 *
 * stack is a cstack with a capacity of 10 and a size of 6, i.e. cstack_capacity() == 10
 * and cstack_size() == 6, on a successful call to cstack_truncate(stack, 4),
 * the stack has the following properties:
 * 1. A capacity of 6.
 * 2. A size of 6.
 * 3. The contents (items) of the stack remain the same, since the 4 items where still non-existent.
 *
 * if you want to truncate all the extra items you may call cstack_truncate() with the result of cstack_free_items()
 * as the items count.
 *
 * @return The truncated stack.
 *
 * @note The stack is modified in-place.
 */
cstack* cstack_truncate(cstack* stack, cstack_size_t count);

/**
 * @brief Copy the contents of src to dst.
 *
 * @param dst The stack to copy the data into.
 * @param src The stack to copy the data from.
 * @return dst is returned.
 *
 * @note
 * - dst should point to a valid (allocated using cstack_alloc()) stack.
 * - If src contains more items than dst's capacity, dst is expanded as necessary.
 * - dst's contents are _overwritten_  up-to src's size.
 */
cstack* cstack_copy(cstack* dst, const cstack* const src);

/**
 * @brief Duplicate a stack.
 *
 * @param stack The stack to duplicate.
 * @return The new stack.
 *
 * @note
 * - The new stack is allocated using cstack_alloc() and should be freed using cstack_free().
 * - In case of failure the function returns _NULL_.
 */
cstack* cstack_dupl(const cstack* const stack);

/**
 * @brief Clear the stack.
 *
 * @param stack The stack to be cleared.
 * @return The cleared stack.
 *
 * This function resets the _top_ pointer,
 * and subsequent calls to cstack_push() will overwrite the existing data.
 *
 * @note After calling cstack_clear(), there is no guarantee that the data in the stack is still valid!
 */
cstack* cstack_clear(cstack* stack);

/**
 * @brief Get the top-most item in the stack. i.e. the last cstack_push()ed item.
 *
 * @param stack The stack to get the item from.
 * @return The item at the top of the stack.
 *
 * @note
 * - If the stack is empty, the function returns _NULL_.
 * - The returned item is a `void*` which should be cast to the proper type if desired/needed.
 */
void* cstack_top(const cstack* const stack);

/**
 * @brief Retrieve the size of a single stack item.
 *
 * @param stack The stack of which to get the item size of.
 * @return The item size in bytes.
 */
cstack_size_t cstack_item_size(const cstack* const stack);

/**
 * @brief Retrieves the count of the items in the stack.
 *
 * @param stack The stack of which to get the items count of.
 * @return The items count.
 */
cstack_size_t cstack_items_count(const cstack* const stack);

/**
 * @brief Retrieves the available (free) items in the stack.
 *
 * @param stack The stack to get the free items of.
 * @return The number of free items.
 */
cstack_size_t cstack_free_items(const cstack* const stack);
/**
 * @brief Retrieves the size of the items in the stack.
 *
 * @param stack The stack of which to get the size of.
 * @return The size of the items in the stack, in _bytes_.
 */
cstack_size_t cstack_size(const cstack* const stack);

/**
 * @brief Retrieves the total capacity of the stack.
 *
 * @param stack The stack of which to get the capacity of.
 * @return The capacity of the stack, in _bytes_.
 */
cstack_size_t cstack_capacity(const cstack* const stack);

/**
 * @brief Retrieve the available (free) space in the stack.
 *
 * @param stack The stack to get the free space of.
 * @return The free space (in bytes) in the stack.
 */
cstack_size_t cstack_free_space(const cstack* const stack);
/**
 * @brief Checks if the stack is empty, i.e. cstack_size() == 0.
 *
 * @param stack The stack to check.
 * @return Returns a non-zero value if empty, 0 otherwise.
 */
int cstack_empty(const cstack* const stack);

/**
 * @brief Checks if the stack is full, i.e. cstack_size() == cstack_capacity().
 *
 * @param stack The stack to check if full.
 * @return Returns a non-zero value if full, 0 otherwise.
 */
int cstack_full(const cstack* const stack);

#endif // CSTACK_H

cstack.c

#include "cstack.h"

#include <string.h>
#include <stdlib.h>

#if defined(ENABLE_ASSERTS)
    #if defined(_WIN32)
        #define DEBUG_BREAK __debugbreak();
    #elif defined(__linux__) || (!defined(_WIN32) && (defined(__unix__) || defined(__unix)))
        #include <signal.h>
        #define DEBUG_BREAK raise(SIGTRAP)
    #else
        #define DEBUG_BREAK;
    #endif // WIN32
    #include <stdio.h>
    #define ASSERT(x) \
        if (x) { } \
        else \
        { \
            fprintf(stderr, "%s (%d): Assertion failed: %s\n", __FILE__, __LINE__, #x); DEBUG_BREAK; \
        }
#else
    #define ASSERT(x)
#endif

#ifndef min
    #define min(x, y) (((x) < (y)) ? (x) : (y))
#endif
#ifndef max
    #define max(x, y) (((x) > (y)) ? (x) : (y))
#endif

cstack* cstack_alloc(cstack_size_t initial_items_count, cstack_size_t item_size)
{
    ASSERT(initial_items_count > 0);
    ASSERT(item_size > 0);

    cstack* new_stack = malloc(sizeof(cstack));

    if (!new_stack)
    {
        return NULL;
    }

    cstack_size_t size = initial_items_count * item_size;
    new_stack->data = malloc(size);

    if (!new_stack->data)
    {
        free(new_stack);
        return NULL;
    }

    new_stack->item_size = item_size;
    new_stack->top = new_stack->data;
    new_stack->cap = new_stack->data + (size);

    return new_stack;
}

void cstack_free(cstack* stack)
{
    if (stack)
    {
        if (stack->data)
        {
            free(stack->data);
            stack->data = NULL;
        }

        stack->item_size = 0;
        stack->top = NULL;
        stack->cap = NULL;

        free(stack);
    }
}

void cstack_push(cstack* stack, void* item)
{
    ASSERT(stack);
    ASSERT(item);

    if (cstack_full(stack))
    {
        if (!cstack_expand(stack, 1))
        {
            return;
        }
    }

    memcpy(stack->top, item, cstack_item_size(stack));
    stack->top += cstack_item_size(stack);
}

void cstack_pop(cstack* stack)
{
    ASSERT(stack);

    if (!cstack_empty(stack))
    {
        stack->top -= cstack_item_size(stack);
    }
}

cstack* cstack_expand(cstack* stack, cstack_size_t count)
{
    ASSERT(stack);
    ASSERT(count > 0);

    cstack_size_t new_size = cstack_capacity(stack) + (count * cstack_item_size(stack));

    cstack_size_t top_offset = stack->top - stack->data;
    char* data_backup = stack->data;

    stack->data = realloc(stack->data, new_size);

    if (!stack->data)
    {
        stack->data = data_backup;
        return NULL;
    }

    stack->top = stack->data + top_offset;
    stack->cap = stack->data + new_size;

    return stack;
}

cstack* cstack_truncate(cstack* stack, cstack_size_t count)
{
    ASSERT(stack);
    ASSERT(count > 0);
    ASSERT(count <= cstack_items_count(stack));

    cstack_size_t new_size = cstack_capacity(stack) - (count * cstack_item_size(stack));
    cstack_size_t top_offset = min(new_size, cstack_size(stack));

    char* data_backup = stack->data;
    stack->data = realloc(stack->data, new_size);

    if (!stack->data)
    {
        stack->data = data_backup;
        return NULL;
    }

    stack->top = stack->data + top_offset;
    stack->cap = stack->data + new_size;

    return stack;
}

cstack* cstack_copy(cstack* dst, const cstack* const src)
{
    ASSERT(dst);
    ASSERT(src);
    ASSERT(cstack_item_size(dst) == cstack_item_size(src));

    cstack_size_t extra_items = (cstack_size(src) - cstack_capacity(dst)) / cstack_item_size(dst);

    if (extra_items > 0)
    {
        cstack_expand(dst, extra_items);
    }

    memcpy(dst->data, src->data, cstack_size(src));

    cstack_size_t src_top_offset = src->top - src->data;
    cstack_size_t dst_top_offset = dst->top - dst->data;
    cstack_size_t offset = max(src_top_offset, dst_top_offset);

    dst->top = dst->data + offset;

    return dst;
}

cstack* cstack_dupl(const cstack* const stack)
{
    ASSERT(stack);

    cstack* new_stack = cstack_alloc(cstack_items_count(stack), cstack_item_size(stack));

    if (!new_stack)
    {
        return NULL;
    }

    cstack_copy(new_stack, stack);

    return new_stack;
}

cstack* cstack_clear(cstack* stack)
{
    ASSERT(stack);

    stack->top = stack->data;

    return stack;
}

void* cstack_top(const cstack* const stack)
{
    ASSERT(stack);

    if (cstack_empty(stack))
    {
        return NULL;
    }
    // top points to the item after the last one. i.e. to the next empty 'slot'
    return (void*)(stack->top - cstack_item_size(stack));
}

cstack_size_t cstack_item_size(const cstack* const stack)
{
    ASSERT(stack);

    return stack->item_size;
}

cstack_size_t cstack_items_count(const cstack* const stack)
{
    ASSERT(stack);

    return cstack_size(stack) / cstack_item_size(stack);
}

cstack_size_t cstack_free_items(const cstack* const stack)
{
    ASSERT(stack);

    return cstack_free_space(stack) / cstack_item_size(stack);
}

cstack_size_t cstack_size(const cstack* const stack)
{
    ASSERT(stack);

    return stack->top - stack->data;
}

cstack_size_t cstack_capacity(const cstack* const stack)
{
    ASSERT(stack);

    return stack->cap - stack->data;
}

cstack_size_t cstack_free_space(const cstack* const stack)
{
    ASSERT(stack);

    return cstack_capacity(stack) - cstack_size(stack);
}

int cstack_empty(const cstack* const stack)
{
    ASSERT(stack);

    return cstack_size(stack) == 0;
}

int cstack_full(const cstack* const stack)
{
    ASSERT(stack);

    return cstack_size(stack) == cstack_capacity(stack);
}

main.c

#include <stdio.h>

#include "cstack.h"

void print_stack(const cstack* const stack);

int main()
{
    cstack* stack = cstack_alloc(4, sizeof(int));

    while (1)
    {
        int choice = 0;
        fprintf(stdout, "1. push\n");
        fprintf(stdout, "2. pop\n");
        fprintf(stdout, "3. print\n");
        fprintf(stdout, ">>> ");
        fscanf(stdin, "%d", &choice);

        switch (choice)
        {
        case 1:
            fprintf(stdout, "Number to push: ");
            int num = 0;
            fscanf(stdin, "%d", &num);
            cstack_push(stack, &num);
            break;
        case 2:
            if (cstack_empty(stack))
            {
                fprintf(stdout, "Stack is empty!\n");
                continue;
            }
            fprintf(stdout, "Poping %d (at %p)\n", *(int*)cstack_top(stack), cstack_top(stack));
            cstack_pop(stack);
            break;
        case 3:
            print_stack(stack);
            break;
        default:
            fprintf(stdout, "Invalid option!");
            continue;
        }
    }

    cstack_free(stack);

    return 0;
}

void print_stack(const cstack* const stack)
{
    fprintf(stdout, "Item size:        %lld\n", cstack_item_size(stack));
    fprintf(stdout, "Items count:      %lld\n", cstack_items_count(stack));
    fprintf(stdout, "Free items:       %lld\n", cstack_free_items(stack));
    fprintf(stdout, "Stack size:       %lld\n", cstack_size(stack));
    fprintf(stdout, "Stack cap:        %lld\n", cstack_capacity(stack));
    fprintf(stdout, "Stack free space: %lld\n", cstack_free_space(stack));

    if (!cstack_empty(stack))
    {
        fprintf(stdout, "Stack top: %d (at %p)\n", *(int*)cstack_top(stack), cstack_top(stack));
    }
}

As a beginner, I'm open to any suggestions, best practices, coding conventions, bugs (obviously), performance improvements, improvements to the interface/docs, etc.

Any suggestions are very welcome.

\$\endgroup\$
  • \$\begingroup\$ A common convention is that no line should be more than 80 character long, which you might want to consider. \$\endgroup\$ – Eraklon Apr 13 at 17:36
  • \$\begingroup\$ I thought that convention was long gone! after taking a quick look around i guess there are still some valid reasons to stick to it! Noted. \$\endgroup\$ – Isho Antar Apr 13 at 17:41
  • 2
    \$\begingroup\$ It would be nice if there was a file with a main() function for testing purposes. \$\endgroup\$ – pacmaninbw Apr 13 at 19:12
4
\$\begingroup\$

The code is nicely documented, so keep that up! I see some things that may help you improve your code.

Use int main(void) in C

You mentioned that you were coming from C++, so although it's not a problem in this code, it's important to realize that C and C++ are different when it comes to the formal argument list of a function. In C, use int main(void) instead of int main(). See this question for details.

Think of the user

The existing program has no graceful way for the user to end which also means that the cstack_free() function is never called. I'd suggest that instead of while (1), you could do this:

bool running = true;
while (running)

and then provide a menu choice for the user to quit.

Check return values for errors

The calls malloc are all properly checked, but fscanf can also fail. You must check the return values to make sure they haven't or your program may crash (or worse) when given malformed input. Rigorous error handling is the difference between mostly working versus bug-free software. You should, of course, strive for the latter.

Avoid function-like macros

Function-like macros are a common source of errors and the min and max macros are paricularly dangerous. The reason is that any invocation of that macro with a side effect will be executed multiple times. Here's an example:

int a = 7, b = 9;
printf("a = %d, b = %d\n", a, b);
int c = max(++a, b++);
printf("a = %d, b = %d\n", a, b);
printf("c = %d\n", c);

The first printf, predictably, prints

 a = 7, b = 9

However, the second two printf statements result in this:

 a = 8, b = 11
 c = 10

What a mess! The solution is simple: write a function instead. That's particularly simple in this case because each macro is used only once anyway.

Use string concatenation

The menu includes these lines:

fprintf(stdout, "1. push\n");
fprintf(stdout, "2. pop\n");
fprintf(stdout, "3. print\n");
fprintf(stdout, ">>> ");

There are a couple ways in which this could be improved. First, since you're printing to stdout, you could simply use printf. Second, the strings can be concatenated and use a single invocation of printf:

printf("1. push\n"
       "2. pop\n"
       "3. print\n"
       ">>> ");

Reconsider the interface

If a cstack_push fails because realloc fails, the user has no way to detect this condition because cstack_push does not return anything. It would be nice to provide a bool return instead.

Exercise all functions

It's understood that the sample program is just an illustration and not a comprehensive test, but it would be good to write test code that exercises all functions.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

cstack_alloc failure

This:

cstack* stack = cstack_alloc(4, sizeof(int));

does not check for a null, which you return from here:

if (!new_stack)
{
    return NULL;
}

There are two problems with this. First, if it fails, it will not be graceful; it will likely segfault. Second, you are discarding errno information, and would be well-served to call perror.

Logic inversion

This is a matter of style, but I usually like to convert this kind of logic:

if (stack)
{
    if (stack->data)
    {
        free(stack->data);
        stack->data = NULL;
    }

    stack->item_size = 0;
    stack->top = NULL;
    stack->cap = NULL;

    free(stack);
}

into

if (!stack)
    return;
// ...

It will probably not affect the output of the compiler, and is easier on the eyes and brain.

printf

Why fprintf(stdout, "1. push\n"); when you can simply printf? Better yet, puts, which does not need to process a format string.

The same goes for fscanf(stdin, "%d", &choice);, which can just use scanf.

Input validation

fscanf(stdin, "%d", &choice);

should return 1 on success. It's important that you validate this, in case someone entered text that is non-numeric.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I wrote this main function as a basic demo, and it's by no means "production-ready", i do agree on the first point though, i did rush a bit there and forgot to check the return value. Logic inversion, i didn't think of it that way! but i agree that it is more readable, I'll do that right away. Printf, i guess i just like fprintfing everywhere :), no seriously though, fprintf is needed to print to stderr so i use it for stdout as well, for consistency. Input validation, i would definitely validate any input in an actual program but since this was just a demo i didn't see a need for it \$\endgroup\$ – Isho Antar Apr 14 at 15:27
2
\$\begingroup\$

Reinventing the Wheel

The code contains it's own version of the ASSERT() macro. It might be better to use the ASSERT() macro provided by `#include so that anyone that has to maintain the code is familiar with the macro and it's usage. This will default to the macro being enabled when the code is being debugged.

The original version of the code had included local versions of assert.h and math.h, it would have been better to just use the standard versions of those file.

Private Data

Not all of the functions listed in cstack.h need to be listed in cstack.h. Some examples are cstack_size(const cstack* const stack), cstack_size_t cstack_capacity(const cstack* const stack) and cstack_size_t cstack_free_space(const cstack* const stack).

These functions are primarily for internal use of the library. They can be declared static functions which makes them private to cstack.h. To be able to print the values returned from those functions the function print_stack() should be added to cstack.h and the entire function should be moved to the bottom of cstack.c.

static cstack_size_t cstack_size(const cstack* const stack)
{
    ASSERT(stack);

    return stack->top - stack->data;
}

static cstack_size_t cstack_capacity(const cstack* const stack)
{
    ASSERT(stack);

    return stack->cap - stack->data;
}

static cstack_size_t cstack_free_space(const cstack* const stack)
{
    ASSERT(stack);

    return cstack_capacity(stack) - cstack_size(stack);
}

Function Order

There really isn't any reason to have a function prototype for print_stack(). The order of main() and print_stack() can be swapped. This is also true of the 3 functions listed in the Private Data section. The beginning of a C source file should be the building blocks used by the rest of the functions, this is counter intuitive to those coming to C from C++ where it is better to list the public functions first.

Boolean Values

If the file stdbool.h is included, you can use variables of type bool and values of true and false. Then the function cstack_empty() can return a bool rather than an int.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ They can be declared static functions which makes them private to cstack.h - not quite, unfortunately. If they're declared in cstack.h, they are not "private" at all; a compile-time call to that function from another module would succeed and then linking would fail. Suggesting static is correct but insufficient - those functions should be pulled out of the header file entirely. \$\endgroup\$ – Reinderien Apr 14 at 17:03
  • \$\begingroup\$ I don't think my version of ASSERT differs that much from the standard assert (except for the fact that you don't have to put a semi-colon at the end!), and about math.h my research shows that min and max aren't defined, so i do have to write those, i guess?. Regarding the private data, i exposed them on purpose. for example, the stack allocates memory (expands) on demand, but never actually automatically release it, so you can utilize those functions to do that... \$\endgroup\$ – Isho Antar Apr 14 at 17:05
  • \$\begingroup\$ I thought I suggested that they be removed from cstack.h. \$\endgroup\$ – pacmaninbw Apr 14 at 17:05
  • 1
    \$\begingroup\$ ...e.g. cstack_truncate(stack, cstack_free_items(stack)) simulates shrink_to_fit in C++. i can of course provide that function. i will also consider using stdbool.h since true and false makes more sense than 0 and 1! \$\endgroup\$ – Isho Antar Apr 14 at 17:06

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.