Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > LIFO in C

Reply
Thread Tools

LIFO in C

 
 
arnuld
Guest
Posts: n/a
 
      12-10-2010
Have written some LIFO in C. Have already discussed it here but some
improvements were left:


http://groups.google.com/group/comp....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
 
Reply With Quote
 
 
 
 
Ike Naar
Guest
Posts: n/a
 
      12-10-2010
On 2010-12-10, arnuld <(E-Mail Removed)> 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?
 
Reply With Quote
 
 
 
 
arnuld
Guest
Posts: n/a
 
      12-10-2010
> On Fri, 10 Dec 2010 09:24:49 +0000, Ike Naar wrote:

>> On 2010-12-10, arnuld <(E-Mail Removed)> 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.



, 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
 
Reply With Quote
 
Ike Naar
Guest
Posts: n/a
 
      12-10-2010
On 2010-12-10, arnuld <(E-Mail Removed)> wrote:
>> On Fri, 10 Dec 2010 09:24:49 +0000, Ike Naar wrote:
>>> On 2010-12-10, arnuld <(E-Mail Removed)> 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?
 
Reply With Quote
 
Default User
Guest
Posts: n/a
 
      12-10-2010
"Ike Naar" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> On 2010-12-10, arnuld <(E-Mail Removed)> wrote:
>>> On Fri, 10 Dec 2010 09:24:49 +0000, Ike Naar wrote:
>>>> On 2010-12-10, arnuld <(E-Mail Removed)> 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.


 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      12-12-2010
On Dec 10, 9:06*am, arnuld <(E-Mail Removed)> 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.

 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      12-12-2010
Malcolm McLean <(E-Mail Removed)> writes:
> On Dec 10, 9:06*am, arnuld <(E-Mail Removed)> 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.velocityreviews.com/forums/(E-Mail Removed) <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"
 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      12-13-2010
On Dec 12, 9:29*pm, Keith Thompson <(E-Mail Removed)> wrote:
> Malcolm McLean <(E-Mail Removed)> writes:
> > On Dec 10, 9:06*am, arnuld <(E-Mail Removed)> 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.


 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      12-13-2010
Malcolm McLean <(E-Mail Removed)> writes:
> On Dec 12, 9:29*pm, Keith Thompson <(E-Mail Removed)> wrote:
>> Malcolm McLean <(E-Mail Removed)> writes:
>> > On Dec 10, 9:06*am, arnuld <(E-Mail Removed)> 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) (E-Mail Removed) <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"
 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      12-14-2010
On Dec 13, 6:22*pm, Keith Thompson <(E-Mail Removed)> wrote:
> Malcolm McLean <(E-Mail Removed)> writes:
> > On Dec 12, 9:29*pm, Keith Thompson <(E-Mail Removed)> wrote:
> >> Malcolm McLean <(E-Mail Removed)> writes:
> >> > On Dec 10, 9:06*am, arnuld <(E-Mail Removed)> 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.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[Q] How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ? Standish P Python 91 08-26-2010 08:48 PM
[Q] How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ? Standish P C++ 87 08-26-2010 08:44 PM
[Q] How far can stack [LIFO] solve do automatic garbage collectionand prevent memory leak ? Standish P C Programming 52 08-25-2010 02:43 PM
LIFO in C, need your suggestions Sumit C Programming 20 08-11-2009 02:51 AM
can we implement LIFO using SRL16 ??? Oleg VHDL 5 02-18-2004 10:29 PM



Advertisments