Thread: Finished Stack

  1. #1
    Registered User
    Join Date
    Jan 2005
    Posts
    42

    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
    Last edited by the pooper; 01-31-2005 at 10:38 AM.

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    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.
    If you understand what you're doing, you're not learning anything.

  3. #3
    Registered User Sake's Avatar
    Join Date
    Jan 2005
    Posts
    89
    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.
    Kampai!

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    42
    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.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  7. #7
    Registered User Sake's Avatar
    Join Date
    Jan 2005
    Posts
    89
    >>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.
    Kampai!

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  9. #9
    Registered User Sake's Avatar
    Join Date
    Jan 2005
    Posts
    89
    >>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.
    Kampai!

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Well I don't know why the hell it's not in the index. :P

    Quzah.
    Hope is the first step on the road to disappointment.

  11. #11
    Registered User
    Join Date
    Jan 2005
    Posts
    42
    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.

  12. #12
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. stack and pointer problem
    By ramaadhitia in forum C Programming
    Replies: 2
    Last Post: 09-11-2006, 11:41 PM
  2. Question about a stack using array of pointers
    By Ricochet in forum C++ Programming
    Replies: 6
    Last Post: 11-17-2003, 10:12 PM
  3. error trying to compile stack program
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-03-2003, 06:27 PM
  4. What am I doing wrong, stack?
    By TeenyTig in forum C Programming
    Replies: 2
    Last Post: 05-27-2002, 02:12 PM
  5. Stack Program Here
    By Troll_King in forum C Programming
    Replies: 7
    Last Post: 10-15-2001, 05:36 PM