LIFO in C

Discussion in 'C Programming' started by arnuld, Dec 10, 2010.

  1. arnuld

    arnuld Guest

    Have written some LIFO in C. Have already discussed it here but some
    improvements were left:


    http://groups.google.com/group/comp.lang.c/browse_thread/thread/
    f0ea73e0d528ae25/f309938a64506e42?q=stack+arnuld&lnk=ol&

    any advice on new code will be appreciated. Please ignore push()
    returning int while other functions returning pointer. Just tried to make
    it more useful with returning int, will make change to others soon.
    Implementation of LIFO conforms to definition presented in section 2.3 of
    "Data Structures and Algorithms" by Aho, Hopcraft and Ullman.



    /* A LIFO written using a singly linked list with 4 operations: Pop,
    Push, Top and Print elements in the list.
    *
    * VERISON 0.5
    *
    */

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

    enum { VAL_ERR = -1, VAL_SUCC = 0, LIFO_ARR_SIZE = 10 };

    struct my_LIFO
    {
    char arrc[LIFO_ARR_SIZE+1];
    struct my_LIFO* next;
    };

    struct LIFO_list
    {
    struct my_LIFO* head;
    };

    int push( struct LIFO_list*, const char* );
    struct LIFO_list* pop( struct LIFO_list* );
    struct my_LIFO* top( struct LIFO_list* );
    struct my_LIFO* make_null( struct LIFO_list* );
    struct my_LIFO* is_empty( struct LIFO_list* );

    struct LIFO_list* LIFO_new( void );
    void LIFO_print( const struct LIFO_list* );
    void LIFO_print_element( const struct my_LIFO* );
    struct LIFO_list* LIFO_free( struct LIFO_list* );

    int main( void )
    {
    struct my_LIFO* p = NULL;
    struct LIFO_list* ms = NULL;
    ms = LIFO_new();

    LIFO_print(ms);

    push(ms, "compppppppppppppp");
    push(ms, "(dot)");
    push(ms, "lang");
    push(ms, "(dot)");
    push(ms, "c");

    LIFO_print(ms);

    pop(ms);
    p = top(ms);

    LIFO_print(ms);
    LIFO_free(ms);
    free(ms);
    ms = NULL;

    return 0;
    }

    int push(struct LIFO_list* s, const char* c )
    {
    struct my_LIFO* p = malloc( 1 * sizeof *p );

    if( NULL == p )
    {
    fprintf(stderr, "malloc() failed\n");
    return VAL_ERR;
    }

    p->next = NULL;
    /* If use gave us more characters than what we want, then its his
    problem */
    if( strlen(c) < LIFO_ARR_SIZE )
    {
    strcpy(p->arrc, c);
    }
    else
    {
    printf("Input is more than what is recommended. Adding '%s' failed
    \n", c);
    free(p);
    return VAL_ERR;
    }

    if( NULL == s )
    {
    fprintf(stderr, "LIFO not initialized ?\n");
    free(p);
    }
    else if( NULL == s->head )
    {
    /* printf("LIFO is Empty, adding first element\n"); */
    s->head = p;
    }
    else
    {
    /* printf("LIFO not Empty, adding in front of first element
    \n"); */
    p->next = s->head;
    s->head = p; /* push new element onto the head */
    }

    return VAL_SUCC;
    }


    struct LIFO_list* pop( struct LIFO_list* s )
    {
    struct my_LIFO* p = NULL;

    if( NULL == s )
    {
    printf("There is no LIFO list ?\n");
    }
    else if( NULL == s->head )
    {
    printf("There is no element on the LIFO\n");
    }
    else
    {
    p = s->head;
    s->head = s->head->next;
    free(p);
    }

    return s;
    }

    struct my_LIFO* top( struct LIFO_list* s)
    {
    if( NULL == s )
    {
    printf("There is no LIFO list ?\n");
    return NULL;
    }
    else if( NULL == s->head )
    {
    printf("There is no element on the LIFO\n");
    }

    return s->head;
    }

    /* Make a LIFO empty */
    struct my_LIFO* make_null( struct LIFO_list* s )
    {
    if( NULL == s )
    {
    printf("Can not make NULL when there is no LIFO List\n");
    return NULL;
    }
    else if( NULL == s->head )
    {
    printf("LIFO is already Empty\n");
    }
    else
    {
    LIFO_free(s);
    }

    return s->head;
    }

    struct my_LIFO* is_empty( struct LIFO_list* s )
    {
    if( NULL == s )
    {
    printf("There is no LIFO\n");
    return NULL;
    }
    else if( NULL == s->head )
    {
    printf("LIFO is Empty\n");
    }
    else
    {
    printf("LIFO is not Empty\n");
    }

    return s->head;
    }

    /* ---------- small helper functions -------------------- */
    struct LIFO_list* LIFO_free( struct LIFO_list* s )
    {
    if( NULL == s )
    {
    printf("Can't free a NULL LIFO list\n");
    }

    while( s->head ) pop(s);

    return s;
    }

    struct LIFO_list* LIFO_new( void )
    {
    struct LIFO_list* p = malloc( 1 * sizeof *p );

    if( NULL == p )
    {
    fprintf(stderr, "malloc() in LIFO Initialization failed\n");
    exit( EXIT_FAILURE ); /* There is no point in going beyond this
    point */
    }

    p->head = NULL;

    return p;
    }

    void LIFO_print( const struct LIFO_list* s )
    {
    struct my_LIFO* p = NULL;

    if( NULL == s )
    {
    printf("Can not print an Empty LIFO\n");
    }
    else
    {
    for( p = s->head; p; p = p->next ) LIFO_print_element(p);
    }

    printf("-------------------------- \n");
    }

    void LIFO_print_element(const struct my_LIFO* s)
    {
    if( s ) printf("arrc = %s\n", s->arrc);
    }

    ========================= OUTPUT ==========================
    [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra LIFO.c
    [arnuld@dune programs]$ ./a.out
    --------------------------
    Input is more than what is recommended. Adding 'compppppppppppppp' failed
    arrc = c
    arrc = (dot)
    arrc = lang
    arrc = (dot)
    --------------------------
    arrc = (dot)
    arrc = lang
    arrc = (dot)
    --------------------------
    [arnuld@dune programs]$




    --
    www.lispmachine.wordpress.com
    arnuld, Dec 10, 2010
    #1
    1. Advertising

  2. arnuld

    Ike Naar Guest

    On 2010-12-10, arnuld <> wrote:

    > int push( struct LIFO_list*, const char* );


    It seems to be an error to call push() with NULL for the first argument.
    Then why push() returns VAL_SUCC in this situation?

    > struct LIFO_list* pop( struct LIFO_list* );


    What's the rationale for pop() having a return value?
    (it always returns its argument).

    > struct my_LIFO* top( struct LIFO_list* );
    > struct my_LIFO* make_null( struct LIFO_list* );


    Why do you treat it as an exception when make_null() is called
    with an empty LIFO_list? Seems like a harmless no-op.

    > struct my_LIFO* is_empty( struct LIFO_list* );


    1) is_empty() behaves the same as top(), so it seems redundant.
    2) wouldn't it have been more natural for is_empty() to return a Boolean value?

    > struct LIFO_list* LIFO_new( void );
    > void LIFO_print( const struct LIFO_list* );
    > void LIFO_print_element( const struct my_LIFO* );
    > struct LIFO_list* LIFO_free( struct LIFO_list* );


    Same question as for pop(): what's the rationale for LIFO_free() having
    a return value?
    Ike Naar, Dec 10, 2010
    #2
    1. Advertising

  3. arnuld

    arnuld Guest

    > On Fri, 10 Dec 2010 09:24:49 +0000, Ike Naar wrote:

    >> On 2010-12-10, arnuld <> wrote:


    >> int push( struct LIFO_list*, const char* );


    > It seems to be an error to call push() with NULL for the first argument.
    > Then why push() returns VAL_SUCC in this situation?


    ouch! .. corrected.



    >> struct LIFO_list* pop( struct LIFO_list* );

    >
    > What's the rationale for pop() having a return value? (it always returns
    > its argument).


    If you read that archive where I discussed version 0.0, you will see
    there are 2 schools of pop(), one where they say pop() should return its
    argument and the calling function should call free() for that pop()ed
    element. 2nd school says that piece of program can be (and will be ?)
    used as independent module most of the time, so it must free() its malloc
    ()ed memory. I found 2nd school to be more compatible with my thinking.
    What I do is I just take some extra pointer argument and copy all those
    values where pointer is pointing to and free() my malloc().




    >> struct my_LIFO* top( struct LIFO_list* ); struct my_LIFO* make_null(
    >> struct LIFO_list* );


    > Why do you treat it as an exception when make_null() is called with an
    > empty LIFO_list? Seems like a harmless no-op.


    corrected.



    >> struct my_LIFO* is_empty( struct LIFO_list* );

    >
    > 1) is_empty() behaves the same as top(), so it seems redundant.



    :-o , did not notice that


    > 2) wouldn't it have been more natural for is_empty() to return a Boolean
    > value?


    I thought NULL and any pointer value can be used as same as 1 and 0
    (zero) for conditional expressions.



    >> struct LIFO_list* LIFO_new( void );
    >> void LIFO_print( const struct LIFO_list* ); void LIFO_print_element(
    >> const struct my_LIFO* ); struct LIFO_list* LIFO_free( struct LIFO_list*
    >> );


    > Same question as for pop(): what's the rationale for LIFO_free() having
    > a return value?


    Does the program not need to know whether the list was successfully free()
    ed or not ?





    --
    www.lispmachine.wordpress.com
    arnuld, Dec 10, 2010
    #3
  4. arnuld

    Ike Naar Guest

    On 2010-12-10, arnuld <> wrote:
    >> On Fri, 10 Dec 2010 09:24:49 +0000, Ike Naar wrote:
    >>> On 2010-12-10, arnuld <> wrote:
    >>> struct LIFO_list* pop( struct LIFO_list* );

    >>
    >> What's the rationale for pop() having a return value? (it always returns
    >> its argument).

    >
    > If you read that archive where I discussed version 0.0, you will see
    > there are 2 schools of pop(), one where they say pop() should return its
    > argument and the calling function should call free() for that pop()ed
    > element. 2nd school says that piece of program can be (and will be ?)
    > used as independent module most of the time, so it must free() its malloc
    > ()ed memory. I found 2nd school to be more compatible with my thinking.
    > What I do is I just take some extra pointer argument and copy all those
    > values where pointer is pointing to and free() my malloc().


    Note that in your own code you never use the return value of pop(),
    which also indicates that the returned value isn't very useful.
    The prototype might as well have been the simpler:

    void pop(struct LIFO_list*);

    >>> struct LIFO_list* LIFO_new( void );
    >>> void LIFO_print( const struct LIFO_list* ); void LIFO_print_element(
    >>> const struct my_LIFO* ); struct LIFO_list* LIFO_free( struct LIFO_list*
    >>> );

    >
    >> Same question as for pop(): what's the rationale for LIFO_free() having
    >> a return value?

    >
    > Does the program not need to know whether the list was successfully free()
    > ed or not ?


    How can the program get that information from LIFO_free()'s return
    value, if LIFO_free(x) always returns x, whether succesful or not?
    Ike Naar, Dec 10, 2010
    #4
  5. arnuld

    Default User Guest

    "Ike Naar" <> wrote in message
    news:...
    > On 2010-12-10, arnuld <> wrote:
    >>> On Fri, 10 Dec 2010 09:24:49 +0000, Ike Naar wrote:
    >>>> On 2010-12-10, arnuld <> wrote:
    >>>> struct LIFO_list* pop( struct LIFO_list* );
    >>>
    >>> What's the rationale for pop() having a return value? (it always returns
    >>> its argument).

    >>
    >> If you read that archive where I discussed version 0.0, you will see
    >> there are 2 schools of pop(), one where they say pop() should return its
    >> argument and the calling function should call free() for that pop()ed
    >> element. 2nd school says that piece of program can be (and will be ?)
    >> used as independent module most of the time, so it must free() its malloc
    >> ()ed memory. I found 2nd school to be more compatible with my thinking.
    >> What I do is I just take some extra pointer argument and copy all those
    >> values where pointer is pointing to and free() my malloc().

    >
    > Note that in your own code you never use the return value of pop(),
    > which also indicates that the returned value isn't very useful.


    strcpy() returns destination, but I never use it. I imagine the rationale
    above is similar, it allow call chaining if you desire. The fact that it
    isn't used in Arnuld's baby example doesn't mean that it's not useful.
    Simplicity doesn't buy one a whole lot in the above example.



    Brian
    --
    Day 674 of the "no grouchy usenet posts" project.
    Current music playing: None.
    Default User, Dec 10, 2010
    #5
  6. On Dec 10, 9:06 am, arnuld <> wrote:
    >
    > enum { VAL_ERR = -1, VAL_SUCC = 0, LIFO_ARR_SIZE = 10 };  
    >

    You may not define VAL_ERR in a LIFO stack module, if you want the
    code to be reusable.

    The general problem with LIFO stacks, as with other simple structures
    like linked lists, is that in C it is generally easier to implement
    them from scratch rather than to use a general-purpose 3rd party
    library. Whether this says something positive or something negative
    about C is maybe a subject for discussion.
    Malcolm McLean, Dec 12, 2010
    #6
  7. Malcolm McLean <> writes:
    > On Dec 10, 9:06 am, arnuld <> wrote:
    >>
    >> enum { VAL_ERR = -1, VAL_SUCC = 0, LIFO_ARR_SIZE = 10 };  
    >>

    > You may not define VAL_ERR in a LIFO stack module, if you want the
    > code to be reusable.


    Why not?

    [...]

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Dec 12, 2010
    #7
  8. On Dec 12, 9:29 pm, Keith Thompson <> wrote:
    > Malcolm McLean <> writes:
    > > On Dec 10, 9:06 am, arnuld <> wrote:

    >
    > >> enum { VAL_ERR = -1, VAL_SUCC = 0, LIFO_ARR_SIZE = 10 };  

    >
    > > You may not define VAL_ERR in a LIFO stack module, if you want the
    > > code to be reusable.

    >
    > Why not?
    >

    Namespace pollution.

    Bool breaks libraries.
    Malcolm McLean, Dec 13, 2010
    #8
  9. Malcolm McLean <> writes:
    > On Dec 12, 9:29 pm, Keith Thompson <> wrote:
    >> Malcolm McLean <> writes:
    >> > On Dec 10, 9:06 am, arnuld <> wrote:

    >>
    >> >> enum { VAL_ERR = -1, VAL_SUCC = 0, LIFO_ARR_SIZE = 10 };  

    >>
    >> > You may not define VAL_ERR in a LIFO stack module, if you want the
    >> > code to be reusable.

    >>
    >> Why not?
    >>

    > Namespace pollution.


    So your concern is that it could conflict with a definition of the
    identifier VAL_ERR in another library? The same applies to VAL_SUCC
    (and to LIFO_ARR_SIZE, for that matter). I assumed your remark
    applied specifically to VAL_ERR.

    > Bool breaks libraries.


    What does Bool have to do with this? If you're referring to C99's
    "bool", that's not visible without a #include <stdbool.h>. If you're
    referring to something else, what?

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Dec 13, 2010
    #9
  10. On Dec 13, 6:22 pm, Keith Thompson <> wrote:
    > Malcolm McLean <> writes:
    > > On Dec 12, 9:29 pm, Keith Thompson <> wrote:
    > >> Malcolm McLean <> writes:
    > >> > On Dec 10, 9:06 am, arnuld <> wrote:

    >
    > >> >> enum { VAL_ERR = -1, VAL_SUCC = 0, LIFO_ARR_SIZE = 10 };  

    >
    > >> > You may not define VAL_ERR in a LIFO stack module, if you want the
    > >> > code to be reusable.

    >
    > >> Why not?

    >
    > > Namespace pollution.

    >
    > So your concern is that it could conflict with a definition of the
    > identifier VAL_ERR in another library?  The same applies to VAL_SUCC
    > (and to LIFO_ARR_SIZE, for that matter).  I assumed your remark
    > applied specifically to VAL_ERR.
    >

    No, not LIFO_ARR_SIZE. Once identifiers get beyond a certain length
    and degree of generality, the chance of a collision becomes very low.

    Almost every module needs VAL_ERR or VAL_SUCC, because the number of
    functions that return error or success conditions is very high.
    However only a last=in first out module is likely to need
    LIFO_ARR_SIZE.

    > > Bool breaks libraries.

    >
    > What does Bool have to do with this?  If you're referring to C99's
    > "bool", that's not visible without a #include <stdbool.h>.  If you're
    > referring to something else, what?
    >


    The bool problem was a huge one, and the same issue.
    Malcolm McLean, Dec 14, 2010
    #10
  11. Malcolm McLean <> writes:
    > On Dec 13, 6:22 pm, Keith Thompson <> wrote:
    >> Malcolm McLean <> writes:
    >> > On Dec 12, 9:29 pm, Keith Thompson <> wrote:
    >> >> Malcolm McLean <> writes:
    >> >> > On Dec 10, 9:06 am, arnuld <> wrote:

    >>
    >> >> >> enum { VAL_ERR = -1, VAL_SUCC = 0, LIFO_ARR_SIZE = 10 };  

    >>
    >> >> > You may not define VAL_ERR in a LIFO stack module, if you want the
    >> >> > code to be reusable.

    >>
    >> >> Why not?

    >>
    >> > Namespace pollution.

    >>
    >> So your concern is that it could conflict with a definition of the
    >> identifier VAL_ERR in another library?  The same applies to VAL_SUCC
    >> (and to LIFO_ARR_SIZE, for that matter).  I assumed your remark
    >> applied specifically to VAL_ERR.
    >>

    > No, not LIFO_ARR_SIZE. Once identifiers get beyond a certain length
    > and degree of generality, the chance of a collision becomes very low.


    Ok, so you're saying VAL_ERR and VAL_SUCC are poor choices of names.

    I'm just pointing out that that was *very* unclear in your previous
    article. I assumed there was some significance to the fact that you
    specifically mentioned VAL_ERR but not VAL_SUCC (I thought you might be
    confused about the restriction on identifiers starting with E).

    If your intent was to help arnuld, you needed to explain *why* the names
    VAL_ERR and VAL_SUCC were poor choices.

    > Almost every module needs VAL_ERR or VAL_SUCC, because the number of
    > functions that return error or success conditions is very high.
    > However only a last=in first out module is likely to need
    > LIFO_ARR_SIZE.


    Few modules would use those particular names, but you do have a point.

    >> > Bool breaks libraries.

    >>
    >> What does Bool have to do with this?  If you're referring to C99's
    >> "bool", that's not visible without a #include <stdbool.h>.  If you're
    >> referring to something else, what?

    >
    > The bool problem was a huge one, and the same issue.


    Can you expand on that? Personally, I think bool was a problem
    prior to C99 (though there were workarounds), and that C99's _Bool
    and <stdbool.h> were a reasonably good solution, perhaps the best
    possible given the constraints of backward compatibility. I have
    no idea from what you've written so fare whether you agree. We
    can't read your mind.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Dec 14, 2010
    #11
  12. On Dec 14, 6:00 pm, Keith Thompson <> wrote:
    > Malcolm McLean <> writes:
    >
    > > The bool problem was a huge one, and the same issue.

    >
    > Can you expand on that?
    >

    Muggins wants a routine to invert a matrix (let's say). It something
    he could write himeslef, but it's non-trivial.

    Dopey is a library writer. His routine goes

    typedef in bool

    /*
    Invert a matrix, in place
    Returns - true if successful, false if matrix is singular (can't be
    inverted)
    */
    bool invertmatrix(double *mtx, int N)

    The return is inherently true/false, so in a sense Dopey is doing the
    wrong thing.

    The problem is that now Muggins does

    #include "invertmatrix.h"

    /* now I have bool defined */

    So he's either go to go through the entire source, #including Dopey's
    header anywhere he needs a bool, or he's got to juggle bool, Bool,
    boolean, bool_t. If someone else defines bool then you have to do a
    bit of hackery with #ifdefs and #undefs.
    Often it's a lot easier for Muggins simply to throw up his hands and
    write the silly matrix invert routine from scratch.

    That's how bool break libraries.
     
    Malcolm McLean, Dec 15, 2010
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Oleg
    Replies:
    5
    Views:
    2,458
    Ray Andraka
    Feb 18, 2004
  2. Sumit

    LIFO in C, need your suggestions

    Sumit, Aug 5, 2009, in forum: C Programming
    Replies:
    20
    Views:
    820
    Giorgos Keramidas
    Aug 11, 2009
  3. Standish P
    Replies:
    52
    Views:
    1,228
    Nick Keighley
    Aug 25, 2010
  4. Standish P
    Replies:
    87
    Views:
    1,644
  5. Standish P
    Replies:
    91
    Views:
    1,863
    Navkirat Singh
    Aug 26, 2010
Loading...

Share This Page