6
\$\begingroup\$

Here is the stack abstraction that I've written. I've designed it to be safe and without undefined behavior.

I use ugly_cast to discourage casting and to make casts more easily visible.

stack.h:

#ifndef STACK_H
#define STACK_H 1

#include <stddef.h>

#define stack_op(var, op) stack_##op(&(var), sizeof(var), stack_global)
#define stack_op_r(var, op, stack) stack_##op(&(var), sizeof(var), (stack))

#define push(var) stack_op(var, push)
#define pop(var) stack_op(var, pop)
#define peek(var) stack_op(var, peek)
#define push_r(var, stack) stack_op_r(var, push, stack)
#define pop_r(var, stack) stack_op_r(var, pop, stack)
#define peek_r(var, stack) stack_op_r(var, peek, stack)

#define STACK_INIT(size) \
do { \
    STACK_FINI(); \
    stack_global = stack_create(size); \
} while(0)
#define STACK_INIT_R(size, name) \
do { \
    STACK_FINI_R(name); \
    name = stack_create(size); \
} while(0)
#define STACK_FINI() stack_destroy(stack_global)
#define STACK_FINI_R(name) stack_destroy(name)

extern struct stack *stack_global;

extern struct stack *stack_create(size_t);
extern int stack_resize(struct stack *, size_t);
extern void stack_destroy(struct stack *);
extern void stack_push(void *, size_t, struct stack *);
extern void stack_pop(void *, size_t, struct stack *);
extern void stack_peek(void *, size_t, struct stack *);

#endif

stack_create.c:

#include <stdio.h>
#include <stack.h>
#include <stdlib.h>
#include <stdlib.h>

#include "stack_internal.h"

struct stack *stack_create(size_t size)
{
    struct stack *ret;
    if(!size)
    {
        stack_error("creating stack with size 0");
    }
    else if(size < 16)
    {
        stack_warn("creating stack with size less than 16");
    }
    if((ret = malloc(sizeof(*ret))))
    {
        ret->beg = malloc(size);
        ret->end = ret->cur = ret->beg + size;
    }
    return ret;
}

stack_destroy.c:

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

#include "stack_internal.h"

void stack_destroy(struct stack *stack)
{
    if(stack) free(stack->beg);
    free(stack);
}

stack_diagnostics.c:

#include <stack.h>
#include <stdio.h>
#include <stdlib.h>

#include "stack_internal.h"

static void stack_diagnose(const char *type, const char *diagnostic)
{
    fprintf(stderr, "libstack %s: %s\n", type, diagnostic);
}

void stack_error(const char *str)
{
    stack_diagnose("ERROR", str);
    abort();
}

void stack_warn(const char *str)
{
    stack_diagnose("WARNING", str);
}

stack_global.c:

#include <stack.h>

#include "stack_internal.h"

struct stack *stack_global;

stack_internal.h:

#ifndef STACK_INTERNAL_H
#define STACK_INTERNAL_H 1

#if !defined(__STDC_VERSION__) || __STDC_VERSION__ < 201112L
# if defined(__cplusplus) && __cplusplus >= 201103L
#  define noreturn [[noreturn]]
# else
#  ifdef __GNUC__
#   define noreturn __attribute__((__noreturn__))
#  else
#   define noreturn
#  endif
# endif
#else
# include <stdnoreturn.h>
#endif

#define ugly_cast(x) (x)

struct stack {
    char *beg;
    char *cur;
    char *end;
};

noreturn void stack_error(const char *);
void stack_warn(const char *);

#endif

stack_peek.c:

#include <stack.h>
#include <string.h>

#include "stack_internal.h"

void stack_peek(void *val, size_t size, struct stack *stack)
{
    memcpy(val, stack->cur, size);
}

stack_pop.c:

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

#include "stack_internal.h"

void stack_pop(void *val, size_t size, struct stack *stack)
{
    if(ugly_cast(size_t)(stack->end - stack->cur) < size)
    {
        stack_error("popping past stack boundaries");
    }
    memcpy(val, stack->cur, size);
    stack->cur += size;
}

stack_push.c:

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

#include "stack_internal.h"

void stack_push(void *val, size_t size, struct stack *stack)
{
    if(ugly_cast(size_t)(stack->cur - stack->beg) < size)
    {
        stack_error("pushing past stack boundaries");
    }
    stack->cur -= size;
    memcpy(stack->cur, val, size);
}

stack_resize.c:

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

#include "stack_internal.h"

int stack_resize(struct stack *stack, size_t newsize)
{
    char *newptr;
    size_t oldsize, off;

    oldsize = ugly_cast(size_t)(stack->end - stack->beg);
    off = ugly_cast(size_t)(stack->cur - stack->beg);

    if(!newsize)
        stack_error("resizing stack to size 0");
    else if(newsize < 16)
        stack_warn("resizing stack to size less than 16");

    if(newsize < oldsize)
    {
        stack_warn("truncating stack");
    }
    if(off > newsize)
    {
        stack_warn("truncating offset into stack to new size");
        off = newsize;
    }

    newptr = realloc(stack->beg, newsize);

    if(!newptr)
    {
        free(stack->beg);
        return -1;
    }

    if(newsize > oldsize)
        memset(newptr + oldsize, 0, oldsize - newsize);

    stack->beg = newptr;
    stack->end = stack->beg + newsize;
    stack->cur = stack->beg + off;
    return 0;
}

Here's an example program that uses the library:

#include <stack.h>
#include <stdlib.h>

int main(void)
{
    int err = 0;
    STACK_INIT(8);
    STACK_FINI();
    STACK_INIT(16);
    push(err);
    push(err);
    err = stack_resize(stack_global, 8);
    STACK_FINI();
    return err != 0;
}

Here's another example program that uses it:

#include <stdio.h>
#include <stack.h>

int main(void)
{
    int a = 16, b = 32;
    struct stack *stack = 0;
    STACK_INIT_R(32, stack);
    push_r(a, stack);
    push_r(b, stack);
    pop_r(a, stack);
    pop_r(b, stack);
    printf("a=%d, b=%d\n", a, b);
    STACK_FINI_R(stack);
    return a != 32 || b != 16;
}

Is there anything I can improve?

This project is available under the LGPLv2.1+ on my GitHub site.

\$\endgroup\$
5
\$\begingroup\$

Overall the code is well-written, consistent and easy to follow.

Program design / big picture

  • Having one .c file per function is quite extreme - this just creates a lot of fuss when linking and maintaining the code. This isn't a whole lot of code, so it is hard to justify splitting it in so many different .c files when it could have been placed in a single file. The opaque struct definition could then also be placed in this single .c file, making stack_interal.h mostly superfluous.

  • One exception to the above is error handling/diagnostics, which should be put in a file of its own. You definitely should not mix your ADT with console output etc. Either leave error diagnostic printing to the caller, or put it in a separate (public) file. Libs shouldn't call functions like abort() or exit() internally, leave such things to the caller or it will make debugging a pain for them. (Also, not all systems support stdio.h)

    Also, you aren't consistent here, since your program does not deal with malloc errors internally, but passes on NULL to the caller.

  • Inventing your own "macro language" is always a bad idea. The caller should simply call stack_push instead of push. The stack_ prefix having the huge advantage of self-documenting which source file the function belongs to. push and pop etc are also common names (even assembler mnemonics in some cases), so the potential for namespace collisions is pretty big.

    I would strongly recommend to get rid of all of these function-like macros, they just add a type safety hazard while at the same time making the source harder to read and maintain.

  • Instead of passing around the ugly (and thread unsafe) stack_global, let the user of your lib be the one to worry about keeping tabs of the pointers to your ADT.

  • Always name the parameters in the public header and document their use, in source code comments.

  • Allowing your code to be compiled from C++ (as indicated by your noreturn handling macros) will require a lot of stricter typing, most notably when dealing with void pointers. Currently, this code won't compile at all in C++, unless you add various extern "C" tricks.

Coding style

  • #include <stack.h> Don't use < > for your own headers, only for standard lib headers. Unlike when you use " ", the compiler isn't required to check the local path for the location of the header, so it might just check its own library path.

  • Avoid assignment inside conditions. It is dangerous, error-prone and makes the code harder to read. There are a few cases when you can justify it but they are very rare.

    Instead of if((ret = malloc(sizeof(*ret)))), you should do

    ret = malloc(sizeof *ret);
    if(ret != NULL)
    
  • I often advise against the do {...} while(0) trick, because its only purpose is to allow code such as if(x) y(); else. It is best practice to always use compound statements after control or loop statements, that is { }. Getting a compiler error for forgetting to add { } is not necessarily a bad thing.

  • Unless you only intend the stack to work with strings, using char as a generic byte type isn't a good idea. The main problem being that it has implementation-defined signedness and therefore can cause all manner of subtle, severe bugs related to implicit type promotion, integer overflows or bitwise operations. Instead, use uint8_t.

  • It's not really necessary to explicitly add extern linkage to function declarations, as that's the default linkage anyway. It tends to confuse less experienced programmers and that's about all it does. (I used that style myself for a long while until I got fed up with explaining it.)

  • I recommend to put all library includes inside the public header instead of in the .c files. That way you document all library dependencies to the caller.

  • I disagree that an explicit cast from ptrdiff_t to size_t is an ugly cast. However, for various "language lawyer" reasons, ptrdiff_t should always end up larger than size_t, so strictly speaking the cast shouldn't be needed at all.

Optimizations

  • Storing the size of the stack explicitly will save you from a lot of extra run-time arithmetic. Faster execution at the expense of a little extra memory consumption for the ADT.

  • In order to reduce the amount of needed realloc calls you could alloc some even multiple of the CPU alignment and keep track of the allocated size. When running out of allocated memory, you'd allocate n new segments and not just the necessary size. Again, this is an execution speed optimization, at the cost of memory use.

    (It's possible that keeping the same chunk of memory for longer before calling realloc will also lead to slightly better data cache performance on some systems, but that's speculation.)

Bugs

  • Upon free() you don't set the freed memory to NULL (and your interal API does not allow this). Therefore STACK_INIT -> STACK_FINI -> stack_destroy -> if(stack) free(stack->beg); is always a bug, because stack is either not initialized or it can be non-null, but pointing at garbage. free() can however not set the pointer to NULL afterwards.

  • Typo, you include #include <stdlib.h> twice in stack_create.c

\$\endgroup\$
  • \$\begingroup\$ The issue with converting between ptrdiff_t and size_t is signedness. The compiler emits a warning with -Wextra. \$\endgroup\$ – JL2210 Sep 17 at 15:47
  • \$\begingroup\$ What does ADT mean? \$\endgroup\$ – JL2210 Sep 17 at 16:45
  • 1
    \$\begingroup\$ @JL2210 Abstract Data Type, basically the predecessor of classes. But if you say class instead of ADT, some C programmers start to freak out and think you are talking about C++. In practice, it means the same thing. \$\endgroup\$ – Lundin Sep 18 at 6:21
5
\$\begingroup\$

Modularization
Generally I like well modularized C programs and libraries, however, in this case the library would benefit from having all the functions in one file. This would allow all the function access to certain functions that the user should not see.

The functions that the user should not see are:

  • stack_resize(struct stack *, size_t)
  • stack_diagnose(const char *type, const char *diagnostic)
  • stack_error(const char *str)
  • stack_warn(const char *str)

The above functions should be defined as static functions within the module so that they do not impact the global name space.

It might be better if the function void stack_push(void *val, size_t size, struct stack *stack) called stack_resize(struct stack *, size_t) rather than forcing the user to resize the stack.

Note: none of the functions in stack_diagnostics.c are declared as externs where they are used or in a header file so that they are declared at run time; this could possibly cause some compilers to complain.

Possible Problems in the Code
I see two possible problems in the following code:

    if(!newsize)
        stack_error("resizing stack to size 0");
    else if(newsize < 16)
        stack_warn("resizing stack to size less than 16");

The first is that while the allocation error is reported, it is not handled. If stack_resize is called internally then there really should be error handling. If stack_resize is called explicitly by the user then the function should return at this point so that the user can handle the allocation error.

The second problem I see is that while in the rest of the function the if and else clauses are wrapped in braces this code is not wrapped in braces. First this is inconsistent and second for maintenance reasons it would be better if all if and else clauses were compound statements to allow for expansion of the code.

Include Files
Some compilers can't find the include file stack.h which is local to the code when it is used as

#include <stack.h>

While that usage would be correct if the file was in a library folder somewhere, it is not correct within the source code for the library itself unless a -I flag is set during the build.

It's not really clear what stack_internal.h is for.

\$\endgroup\$
  • \$\begingroup\$ Isn't extern the default linkage for functions? I don't see the relevance of your note. \$\endgroup\$ – Toby Speight Sep 18 at 8:48
3
\$\begingroup\$

The usage example is unrealistic, as it fails to show the error handling that's necessary when initialising the stack. Wrapping the initialisation in command-like macros makes it harder to write the correct checks (as we can't just use a return value, we have to inspect the macro to see where the result went):

STACK_INIT(8);
if (!stack_global) { /* not obviously connected to above */
    fprintf("Stack allocation failure\n");
    return EXIT_FAILURE;
}
STACK_FINI();

I'm not a big fan of expanding STACK_FINI() here:

#define STACK_INIT(size) \
do { \
    STACK_FINI(); \
    stack_global = stack_create(size); \
} while(0)

Firstly, I'd prefer the stack_global definition to explicitly initialize with a null pointer, rather than relying on the implicit initialization; secondly, I consider an init of an already inited stack to be a programming error - and we're already willing to abort() on underflow.

I'm concerned about these allocations in stack_create():

    if((ret = malloc(sizeof(*ret))))
    {
        ret->beg = malloc(size);
        ret->end = ret->cur = ret->beg + size;
    }
    return ret;

On the style side, I'd separate the assignment from the test, and give the variable a more meaningful name:

    stack = malloc(sizeof *stack);
    if (!stack) {
        return stack;
    }

More worryingly, what happens when this first allocation succeeds, but the allocation of size chars (for stack->beg) fails? We return a stack that's unusable, and callers need to test beg as well:

STACK_INIT(8);
if (!stack_global || !stack_global->beg) { /* even less obvious */
    fprintf("Stack allocation failure\n");
    return EXIT_FAILURE;
}
STACK_FINI();

A better approach, if beg can't be allocated, is to release the stack and return null:

    stack = malloc(sizeof *stack);
    if (!stack) {
        return stack;
    }
    stack->beg = malloc(size);
    if (!stack->beg) {
        free(stack);
        return NULL;
    }
    ret->end = ret->cur = ret->beg + size;

Other error handling is also suspect. For example, if the realloc() fails in stack_resize(), most programmers would expect the stack to be unchanged. But we have this code instead:

    newptr = realloc(stack->beg, newsize);

    if(!newptr)
    {
        free(stack->beg);
        return -1;
    }

So if we couldn't realloc, we now have a broken, unusable stack; any attempt to use it will dereference the dangling pointer, which is Undefined Behaviour. And in the success case, we fail to free the memory which is about to become inaccessible (a leak). I think what's intended is:

    newptr = realloc(stack->beg, newsize);
    if (!newptr) {
        return -1;
    }
    free(stack->beg);
    stack->beg = newptr;

Problems with the interface:

  • There's no size() function to determine whether pop() and peek() can be called - the programmer needs to maintain their own count of elements.
  • pop() aborts on underflow, but peek() does no checking, which is inconsistent.
  • peek() requires a pointer to mutable stack, but would be expected to work with a const one.
  • The term "safe" is highly misleading. If objects of differing sizes are pushed, the pop() calls must exactly match, as there's no checking built into the stack to record object sizes.
\$\endgroup\$
  • \$\begingroup\$ if(!stack) return stack; is actually is(!stack) return NULL; :) \$\endgroup\$ – bipll Sep 18 at 9:34
  • \$\begingroup\$ @bipll They're equivalent. \$\endgroup\$ – JL2210 Sep 18 at 11:43
  • \$\begingroup\$ Thanks. I'll work on this. \$\endgroup\$ – JL2210 Sep 18 at 11:43
  • \$\begingroup\$ @bipll Yes, absolutely - I don't have a strong argument for or against either form. There's perhaps an argument here for return NULL, giving consistency with the return following if (!stack->beg). \$\endgroup\$ – Toby Speight Sep 18 at 12:03
1
\$\begingroup\$

One issue that I see is that you will not be able to call functions in this library from C++.

To be able to do so, you need to wrap stack.h in an extern "C" block:

#ifdef __cplusplus
extern "C" {
#endif
/* functions */
#ifdef __cplusplus
}
#endif
\$\endgroup\$
  • 5
    \$\begingroup\$ I disagree that this is an improvement, considering that the question does not suggest that it is a requirement to make the header files compilable in a C++ compiler. I would not advocate it as general good practice to wrap all C headers with extern "C". If you were targeting C++, you wouldn't write your own stack implementation anyway; you would just use std::stack. \$\endgroup\$ – Cody Gray Sep 14 at 1:27
  • \$\begingroup\$ @CodyGray You're right, but I generally try to make all my projects work seamlessly in C++ and C anyway. \$\endgroup\$ – JL2210 Sep 14 at 1:51
  • 1
    \$\begingroup\$ Seems like a lot of extra work for a dubious advantage. If you cannot use namespaces (which you can't if you want C compatibility), then you have to worry about a whole lot of name clashes introduced by the massive C++ standard library. Not to mention all of the seemingly minor, but potentially serious, differences between the two languages' semantics (e.g., sizeof(bool)...that is, if you can even use bool without an #ifdef'd typedef...). C and C++ are vastly different languages and should be treated as such. They just have similar syntax. Don't let that fool you. \$\endgroup\$ – Cody Gray Oct 13 at 6:45
1
\$\begingroup\$
    if((ret = malloc(sizeof(*ret))))
    {
        ret->beg = malloc(size);
        ret->end = ret->cur = ret->beg + size;
    }

You don't check the second malloc's returned value. When out of memory, you're likely to return an object in invalid state (or maybe not, since ret->end and ret->cur initialization is an UB anyway).

\$\endgroup\$
  • 1
    \$\begingroup\$ Looks like we saw the same thing at around the same time! \$\endgroup\$ – Toby Speight Sep 18 at 9:30
  • \$\begingroup\$ Thanks. I'll work on this. \$\endgroup\$ – JL2210 Sep 18 at 11:44

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.