Finished Stack

I've learned a lot thanks to people on this board. Below is an implementation of an array stack that I wrote and rewrote as I learned new or better concepts. I hope people will take a moment to review it and give me any and all criticisms. I'm doing this to try to learn so the more criticism the better.

stack.h

Code:

#ifndef _STACK_H_
#define _STACK_H_

#include <stddef.h>  /* size_t */

typedef
    struct stack
    stack_t;

struct stack {
    void **stack;
    size_t top;
    size_t capacity;
    unsigned int err;
};

enum {
    STACK_ERR_OK,
    STACK_ERR_MEMORY
};

stack_t *  stack_create(void);
void       stack_destroy(stack_t *stack);
void       stack_push(stack_t *stack, void *item);
void *     stack_pop(stack_t *stack);
void *     stack_peek(stack_t *stack);
int        stack_isempty(stack_t *stack);

/*******************************************************************************
 *
 * stack_create
 *   Dynamically allocates and initializes a new stack. Returns a valid pointer
 *   if successful, NULL otherwise.
 *
 * stack_destroy
 *   Frees all memory dynamically allocated by the associated stack functions.
 *   It will *not* free items that have been pushed on the stack. If you
 *   dynamically allocated these items yourself then you must free them
 *   yourself.
 *
 * stack_push
 *   Pushes the given item onto the stack. The stack will increase in size if
 *   necessary. If memory could not be allocated to accomodate the stack's new
 *   size, the stack will retain its state prior to the function call and the
 *   member 'err' is set to STACK_ERR_MEMORY. The member 'err' is otherwise
 *   guarenteed to hold the value STACK_ERR_OK.
 *
 * stack_pop
 *   Removes and returns the last item pushed onto the stack. If the stack is
 *   empty the behavior is undefined.
 *
 * stack_peek
 *   Returns the last item pushed onto the stack. If the stack is empty the
 *   behavior is undefined.
 *
 * stack_isempty
 *   Returns a value that evaluates to true if the stack is empty, false
 *   otherwise.
 *
 ******************************************************************************/

#endif

stack.c

Code:

#ifndef _STACK_C_
#define _STACK_C_

#include <stddef.h>  /* NULL size_t */
#include <stdlib.h>  /* malloc realloc free */
#include "stack.h"

#define  STACK_INITIAL_CAPACITY    (8 * sizeof(int))
#define  STACK_CAPACITY_INCREMENT  (8 * sizeof(int))

stack_t *
stack_create(void)
{
    stack_t *stack;

    stack = malloc(sizeof(stack_t));
    if (stack == NULL)
        return NULL;

    stack->stack = malloc(STACK_INITIAL_CAPACITY * sizeof(void *));
    if (stack->stack == NULL) {
        free(stack);
        return NULL;
    }

    stack->top = (size_t)-1;
    stack->capacity = STACK_INITIAL_CAPACITY;
    stack->err = STACK_ERR_OK;

    return stack;
}

void
stack_destroy(stack_t *stack)
{
    free(stack->stack);
    free(stack);
}

void
stack_push(stack_t *stack, void *item)
{
    stack->err = STACK_ERR_OK;

    stack->top++;
    if (stack->top == stack->capacity)
    {
        void *bigger_stack;

        stack->capacity += STACK_CAPACITY_INCREMENT;
        bigger_stack = realloc(stack->stack, stack->capacity * sizeof(void *));
        if (bigger_stack == NULL) {
            stack->err = STACK_ERR_MEMORY;
            stack->top--;
            stack->capacity -= STACK_CAPACITY_INCREMENT;
            return;
        }
        stack->stack = bigger_stack;
    }

    stack->stack[stack->top] = item;
}

void *
stack_pop(stack_t *stack)
{
    stack->top--;
    if (stack->capacity - stack->top - 1 >= 1.5 * STACK_CAPACITY_INCREMENT)
    {
        void *smaller_stack;

        stack->capacity -= STACK_CAPACITY_INCREMENT;
        smaller_stack = realloc(stack->stack, stack->capacity * sizeof(void *));
        if (smaller_stack == NULL)
            stack->capacity += STACK_CAPACITY_INCREMENT;
        else
            stack->stack = smaller_stack;
    }

    return stack->stack[1 + stack->top];
}

void *
stack_peek(stack_t *stack)
{
    return stack->stack[stack->top];
}

int
stack_isempty(stack_t *stack)
{
    return stack->top == (size_t)-1;
}

#endif

It looks pretty good to me. I would add some error checking to stack_pop(). If stack_top == (size_t)-1 then you're going to run into problems. You might want to add a STACK_ERR_EMPTY or some such error if someone pops from an empty stack. You could make stack_peek() use the same error.

Also, I don't think you need the _STACK_C_ wrapper ifdef unless you plan on #include'ing the .c file for some strange reason.

Code:

#ifndef _STACK_H_
#define _STACK_H_

This invades the implementation's namespace. You should avoid leading underscores unless you're familiar with the tricky rules.

No, I don't believe it actually does. It's a #define, not a variable. These are preprocessor directives. I don't believe they're considered in the same catergory as standard naming conventions, simply because the preprocessor handles the macro in its entirety first. For example, you can make macros which have the name of reserved keywords, and the compiler won't complain, because the preprocessor takes care of them all before the compiler ever sees them.

Quzah.

You should avoid leading underscores unless you're familiar with the tricky rules.

Is there a general style then for pre-processed constants in library code?

I would add some error checking to stack_pop(). If stack_top == (size_t)-1 then you're going to run into problems.

The responsibility for this I decided to leave to the user. If they push some fixed number of items then they should know exactly how many need to be popped off. If they push items iteratively then they can safely pop items off iteratively using stack_isempty in the loop condition.

So while I did choose to check for and report errors that the user would have no control over (e.g., memory allocation), I chose not to bloat the code for detecting mistakes that are the fault of the user.

Also, I don't think you need the _STACK_C_ wrapper ifdef unless you plan on #include'ing the .c file for some strange reason.

That reason could be better optimized code. I've found that with optimizations, some functions may be inlined. But this does not appear to happen across separate translation units. It is setup such that the user has the choice of including the .h file and compiling the .c file separately, or to simply include the .c file.

It's usually never a good idea to leave error checking up to the user. The reason being, most users are idiots.

My includes usually take on something like this:

Code:

#ifndef FOO_H_
#define FOO_H_

#endif

Also, you usually never include ".c" files. It's just bad form. You don't include C files, you compile them. You include headers. Oh sure, technically you can include them, but it makes for ugly code.


Quzah.

>>No, I don't believe it actually does. It's a #define, not a variable.
It doesn't have to be a variable, just an identifier. The standard describes an identifier to be "a sequence of nondigit characters (including the underscore _, the lowercase and uppercase Latin letters, and other characters) and digits, which designates one or more entities as described in 6.2.1."

The referenced section says that an identifier can denote "an object; a function; a tag or a member of a structure, union, or enumeration; a typedef name; a label name; a macro name; or a macro parameter."

The section that gives the rule that's broken says "All identifiers that begin with an underscore and either an uppercase letter or another underscore are always reserved for any use."

I could be wrong, but if you flip around to the right places, it's pretty clear that the inclusion guards posted are using reserved identifiers.

Thanks. I couldn't locate it. I was trying to find it in "C: A Reference Manual, 5th Edition", but the only thing with namespaces refers to C++, and the only thing with the _ covered is just that you can include it in names.

Quzah.

>>I was trying to find it in "C: A Reference Manual, 5th Edition"
Try page 313, secton 10.1.1. It covers what you want in the third paragraph saying "for macros, keywords, or global variables, identifiers beginning with _ and either a second _ or an uppercase letter".

But from what I can tell, that book is short on a good description of exactly what constitutes an identifier. That's why I've learned to back up my claims with the standard itself. The people I work with are hardcore when it comes to this stuff.

Well I don't know why the hell it's not in the index. :P

Quzah.

It's usually never a good idea to leave error checking up to the user. The reason being, most users are idiots.

I think I will provide these additional checks through assertions. That way they can still be disabled in the final program.

My includes usually take on something like this:

#ifndef FOO_H_
#define FOO_H_

I remember now where I got the style of _FOO_H_. I was looking at the sources for the XviD MPEG-4 codec (http://cvs.xvid.org) for some guidelines in C programming style.

So I just want to confirm now that everyone agrees that defines with a leading underscore is bad practice? And that's because this naming convention is reserved for the standard library, correct?

Also, you usually never include ".c" files. It's just bad form. You don't include C files, you compile them. You include headers.

I understand that. I simply decided to allow it to work either way just in case there is someone who is obsessed with speed and wants those additional optimizations.

>So I just want to confirm now that everyone agrees that defines with a leading underscore is bad practice?
I don't know about everyone, but most of the people you want to listen to agree.

>And that's because this naming convention is reserved for the standard library, correct?
Correct.