LIFO in C

[arnuld]

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)

 

[Ike Naar]

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?

 

[arnuld]

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.

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().

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.

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.

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 ?

 

[Ike Naar]

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*);

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?

 

[Default User]

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

 

[Malcolm McLean]

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.

 

[Keith Thompson]

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

Why not?

[...]

 

[Malcolm McLean]

Why not?

Namespace pollution.

Bool breaks libraries.

 

[Keith Thompson]

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?

 

[Malcolm McLean]

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.

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.

 

[Keith Thompson]

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.

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.

 

[Malcolm McLean]

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.