A C style question and a review request (newbie alert)

[Barry Schwarz]

Original code as requested - this has been changed quite a bit since.
I'll post an updated one soon.

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

/* stack element */
typedef struct stack_element_t {
void* payload;
struct stack_element_t * next;
} stack_element_t;

/* stack */
typedef struct stack_t {
stack_element_t * tos;
size_t size;
} stack_t;

/* initialise stack object */
stack_t *
stack_init()
{
stack_t* stack;
stack = malloc(sizeof(stack_t));
stack->tos = NULL;
stack->size = 0;
return stack;
}


/* pop value from stack */
void*
stack_pop(stack_t* stack)
{
stack_element_t* element;

if (stack->size == 0)
return NULL;

element = stack->tos;
stack->tos = element->next;
void* result = element->payload;

Unless you have a C99 compiler and don't need help from anyone who
doesn't, your object definitions need to appear before any statements.

free(element);
stack->size--;
return result;
}


/* destroy stack */
void
stack_destroy(stack_t* stack)
{
while((void*)stack_pop(stack) != NULL);

The cast serves no purpose. Any type of object pointer can be
compared against NULL.

free(stack);
}


/* push element onto stack */
void
stack_push(stack_t* stack, void* value)
{
stack_element_t* entry;
entry = malloc(sizeof(stack_element_t));
entry->next = stack->tos;
entry->payload = value;
stack->tos = entry;
stack->size++;
}

/* entry point */
int
main()
{
stack_t* stack;
stack = stack_init();
printf("size pre-push: %d\n", stack->size);

stack->size is a size_t. That is unsigned and need not be the same
size as an int. If size_t is actually unsigned long and if a long is
larger than an int, this would invoke undefined behavior. If you
don't have C99 (which has %zu for size_t) then you should cast the
value to match the format. The usual recommendation is to use %lu and
cast to unsigned long.

stack_push(stack, "entry 1");
stack_push(stack, "entry 2");
stack_push(stack, "entry 3");
printf("size post-push: %d\n", stack->size);
printf("%s\n", (char*)stack_pop(stack));

This cast is appropriate.

 

[Barry Schwarz]

Some of my points below apply to multiple parts of the program. I'm
only going to mention them once each.

"(e-mail address removed)" <[email protected]>
writes:

snip

snip


snip


Some may criticize you for exposing the stack length as a structure
member rather than through a function; I don't see the problem myself.


This cast isn't actually necessary (6.2.5p25). It's probably a good
habit anyway: if it had been a pointer to anything other than character
type, the cast would most definitely be necessary in this context.

6.2.5p25 has nothing to do with pointers to char or arguments to
printf. I can't see how it applies here at all. 6.2.5p27 requires
char* and void* to have the same representation and alignment which
may be what you meant. Even then, there is no requirement that void*
and char* be passed to printf the same way. Since stack_pop returns a
void* and printf requires a char*, the cast is appropriate.

 

[Mark Wooding]

6.2.5p25 has nothing to do with pointers to char or arguments to
printf. I can't see how it applies here at all.

You're right. I typoed; sorry. I meant to 6.2.5p26. (I'm using
ISO/IEC 9899:1999(E).)

6.2.5p27 requires char* and void* to have the same representation and
alignment which may be what you meant. Even then, there is no
requirement that void* and char* be passed to printf the same way.

: [26] A pointer to void shall have the same representation and
: alignment requirements as a pointer to a character type.39)

and the footnote says

: 39) The same representation and alignment requirements are meant to
: imply interchangeability as arguments to functions, return values
: from functions, and members of unions.

It seems to me that being passed to printf in different ways would
contradict `interchangeability as arguments to functions'. Therefore
the cast in question is redundant but nonetheless probably good
practice.

-- [mdw]

 

[Barry Schwarz]

The cast is appropriate, but and because,
"same representation and alignment"
almost but not quite, guarantees
that they can be interchanged as arguments.

Paragraph 6 of the Forward says footnotes are for information only.
Therefore, the same representation and alignment are guaranteed but
interchangeability is a statement of future intent/nice to
have/quality of implementation issue.

One has to wonder why they wrote "meant to imply". It sounds like
they wanted it to be normative but somebody on the committee had (or
knew of) a product that didn't quite meet the requirement so it got
diluted.

 

[Richard Bos]

Of course in terms of the syntax there's no best way to do it.
But there are style that are better readable than others. And
the best test is, how well people new to the subject can read
it.

That argument would mean that the best style of literature in English is

"See Spot. See Spot run. Run, Spot, run!"

I submit that it is, therefore, a bogus argument.

Richard

 

[Tim Rentsch]

about whether to use a (char*) cast on a (void*) argument to printf...]

6.2.5p25 has nothing to do with pointers to char or arguments to
printf. I can't see how it applies here at all. 6.2.5p27 requires
char* and void* to have the same representation and alignment which
may be what you meant. Even then, there is no requirement that void*
and char* be passed to printf the same way. [snip]

Not everyone agrees that there is no such requirement. In
particular, (void*) and (char*) are guaranteed to be
interchangeable when passed as variadic arguments for
functions that use <stdarg.h>. The question is whether
arguments given to printf() are provided the same guarantees
as those accessed through <stdarg.h>, and there are opinions
on both sides of that question.

I do agree that casting a (void*) argument to (char*) is
good style for arguments that go with %s format specifiers.
That notwithstanding, it seems a misrepresentation to give a
statement about (void*)/(char*) as though it were a fact,
given the noticeably differing views on the subject.

Also, even if in theory it might be allowed to pass
(void*) and (char*) differently as arguments to
printf(), it's never going to happen in practice
because printf() is going to use the same mechanisms
as those in <stdarg.h>, which guarantee identical
treatment.

 

[CBFalconer]

.... snip ...

I do agree that casting a (void*) argument to (char*) is
good style for arguments that go with %s format specifiers.
That notwithstanding, it seems a misrepresentation to give a
statement about (void*)/(char*) as though it were a fact,
given the noticeably differing views on the subject.

It's essential, not style. You can't dereference a void*.

 

[Keith Thompson]

It's essential, not style. You can't dereference a void*.

That's not always relevant. The discussion is about whether void* and
char* are interchangeable when passed as arguments. Here's a program
(admittedly a contrived one) for which the question is relevant:

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

#define target "world"

int main(void)
{
void *buf = malloc(50);
if (buf == NULL) {
exit(EXIT_FAILURE);
}
memcpy(buf, target, sizeof target);
printf("Hello, %s\n", target);
return 0;
}

 

[CBFalconer]

CBFalconer said:

You think casting a void * is essential? I use them all the time,
but I can't remember casting any so far. Perhaps you'd explain to
me why a cast is required? Thanks.

You have to convert it before you can dereference it. One of those
ways is a cast. There are usually better means available.

 

[Tim Rentsch]

That's not always relevant. The discussion is about whether void* and
char* are interchangeable when passed as arguments. Here's a program
(admittedly a contrived one) for which the question is relevant:

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

#define target "world"

int main(void)
{
void *buf = malloc(50);
if (buf == NULL) {
exit(EXIT_FAILURE);
}
memcpy(buf, target, sizeof target);
printf("Hello, %s\n", target);
return 0;
}

I presume you meant to write

printf("Hello, %s\n", buf);

I know you do this just to see if anyone's paying attention.

 

[Keith Thompson]

I presume you meant to write

printf("Hello, %s\n", buf);
Yeah.

I know you do this just to see if anyone's paying attention.

No, just so everyone can see if I'm paying attention (I wasn't). }

 

[CBFalconer]

.... snip ...


I presume you meant to write

printf("Hello, %s\n", buf);

I know you do this just to see if anyone's paying attention.

Why? Both codes will give the same result. But his code can
eliminate all lines referring to buf, and thus the faulty 'failute'
exit.

 

[Chris M. Thomasson]

Original code as requested - this has been changed quite a bit since.
I'll post an updated one soon.

[...]

Won't you get a memory leak if I push a NULL pointer onto your stack? Say
something like:


/* entry point */
int
main()
{
stack_t* stack;
stack = stack_init();
printf("size pre-push: %d\n", stack->size);
stack_push(stack, "entry 1");
stack_push(stack, "entry 2");
stack_push(stack, "entry 3");
stack_push(stack, NULL);
printf("size post-push: %d\n", stack->size);
printf("%s\n", (char*)stack_pop(stack));
printf("%s\n", (char*)stack_pop(stack));
printf("%s\n", (char*)stack_pop(stack));
printf("size post-pop: %d\n", stack->size);
stack_destroy(stack);
return 0;
}


There may be a legitimate reason a program needs to push a NULL pointer onto
a stack. Your implementation should be robust enough to handle such a
situation.




Also, the following code does not work on pre-C99 compilers:

/* pop value from stack */
void*
stack_pop(stack_t* stack)
{
stack_element_t* element;

if (stack->size == 0)
return NULL;

element = stack->tos;
stack->tos = element->next;
void* result = element->payload; ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

free(element);
stack->size--;
return result;
}

You simply NEED to check the return value of `malloc()'. Report some sort of
error condition and allow the caller of the function to attempt any
recovery. There are many ways to "attempt" to recover from failed
`malloc()'. One very simple method is to empty, or reduce, your programs
cached data, and retry the allocation. A failed `malloc()' does not always
have to result in calling `exit()/abort()' ect... I have programmed robust
server applications that have the ability to correct conditions in which
`malloc()' fails...

 

[CBFalconer]

.... snip ...

Also pointers to things. What's the best notation:

stack_t * stack;
or
stack_t* stack;

stack_t *stack;

The reason: Consider what happens when you have multiple things
defined, such as:

stack_t *stack, bar, *foo;

now bar is of type stack_t, as is *foo. Note that bar is NOT of
type stack_t*, and foo is NOT of type stack_t, but of type
stack_t*.

If you don't like this, you can use a typedef. Others just insist
that only one type is defined by a line.

 

[Tim Rentsch]

Why? Both codes will give the same result. But his code can
eliminate all lines referring to buf, and thus the faulty 'failute'
exit.

If you go back and re-read the portion that you snipped, you'll
see that Keith was trying to make a point, and this point was
illustrated only if 'buf' rather than 'target' were used in the
printf() statement. Furthermore, Keith already acknowledged the
appropriateness of the correction.

Is it too much to ask that people read the posting they are about
to respond to, or at least enough of it so that they understand
the context of what's being said?

 

[Ben Bacarisse]

Original code as requested - this has been changed quite a bit since.
I'll post an updated one soon.

[...]

Won't you get a memory leak if I push a NULL pointer onto your
stack?

I can't see it. Can you say why you think it would be a problem?

 

[Chris M. Thomasson]

Zach said:
In the future please paste your code on a site like
http://pastebin.comrather that your personal webserver attached
to a dynamic IP on a residential connection.

Better still, post it in your article, so that anyone reading the
article can also read the code.

Original code as requested - this has been changed quite a bit since.
I'll post an updated one soon.

[...]

Won't you get a memory leak if I push a NULL pointer onto your
stack?

I can't see it. Can you say why you think it would be a problem?

Okay. Here is the problem:
_______________________________________________________
/* pop value from stack */
void*
stack_pop(stack_t* stack)
{
stack_element_t* element;

if (stack->size == 0)
return NULL;

element = stack->tos;
stack->tos = element->next;
void* result = element->payload;
free(element);
stack->size--;
return result;
}


/* destroy stack */
void
stack_destroy(stack_t* stack)
{
while((void*)stack_pop(stack) != NULL);
free(stack);
}
_______________________________________________________




As you can clearly see, `stack_pop()' returns the `stack_element_t:ayload'
portion of a dynamically allocated stack element. Now, `stack_destroy()' has
a while loop in there which calls `stack_pop()' until it gets a NULL return
value. Therefore, if I push 1,000 nodes with NULL values for payloads, the
`stack_destroy()' function will only eliminate a single node, and then free
the `stack' which means 999 nodes are leaked.

The while loop will call `stack_pop()', which will pop a single node and
return NULL because I pushed a NULL values onto the stack. This will in turn
terminate the while loop even though there are other nodes still in the
stack.


Does that make sense?





Here is a test program to prove my point:
_______________________________________________________
#include <stdio.h>
#include <stdlib.h>

/* stack element */
typedef struct stack_element_t {
void* payload;
struct stack_element_t * next;
} stack_element_t;

/* stack */
typedef struct stack_t {
stack_element_t * tos;
size_t size;
} stack_t;

/* initialise stack object */
stack_t *
stack_init()
{
stack_t* stack;
stack = malloc(sizeof(stack_t));
stack->tos = NULL;
stack->size = 0;
return stack;
}


/* pop value from stack */
void*
stack_pop(stack_t* stack)
{
void* result;
stack_element_t* element;

if (stack->size == 0)
return NULL;

element = stack->tos;
stack->tos = element->next;
result = element->payload;
free(element);
stack->size--;
printf("popped element %p with a payload of %p\n",
(void*)element, result);
return result;
}


/* destroy stack */
void
stack_destroy(stack_t* stack)
{
puts("destroying all nodes");
while((void*)stack_pop(stack) != NULL);
free(stack);
puts("destroyed the stack!");
}


/* push element onto stack */
void
stack_push(stack_t* stack, void* value)
{
stack_element_t* entry;
entry = malloc(sizeof(stack_element_t));
entry->next = stack->tos;
entry->payload = value;
stack->tos = entry;
stack->size++;
printf("pushed element %p with a payload of %p\n",
(void*)entry, value);
}

/* entry point */
int
main()
{
unsigned i;
stack_t* stack;
stack = stack_init();
for (i = 0; i < 10; ++i) {
stack_push(stack, NULL);
}
stack_destroy(stack);
return 0;
}
_______________________________________________________






See how it leaks 9 nodes?

 

[Chris M. Thomasson]

Zach said:
In the future please paste your code on a site like
http://pastebin.comrather that your personal webserver attached
to a dynamic IP on a residential connection.

Better still, post it in your article, so that anyone reading the
article can also read the code.

Original code as requested - this has been changed quite a bit since.
I'll post an updated one soon.

[...]

Won't you get a memory leak if I push a NULL pointer onto your
stack?

I can't see it. Can you say why you think it would be a problem?

Okay. Here is the problem:
[...]

Here is a simple way to fix it:


/* destroy stack */
void
stack_destroy(stack_t* stack)
{
puts("destroying all nodes");

while (stack->size) {
stack_pop(stack);
}


free(stack);
puts("destroyed the stack!");
}

 

[Ben Bacarisse]

Zach said:
In the future please paste your code on a site like
http://pastebin.comrather that your personal webserver attached
to a dynamic IP on a residential connection.

Better still, post it in your article, so that anyone reading the
article can also read the code.

Original code as requested - this has been changed quite a bit since.
I'll post an updated one soon.

[...]

Won't you get a memory leak if I push a NULL pointer onto your
stack?

I can't see it. Can you say why you think it would be a problem?

Okay. Here is the problem:
_______________________________________________________
/* pop value from stack */
void*
stack_pop(stack_t* stack)
{
stack_element_t* element;

if (stack->size == 0)
return NULL;

element = stack->tos;
stack->tos = element->next;
void* result = element->payload;
free(element);
stack->size--;
return result;
}


/* destroy stack */
void
stack_destroy(stack_t* stack)
{
while((void*)stack_pop(stack) != NULL);
free(stack);
}
_______________________________________________________




As you can clearly see, `stack_pop()' returns the
stack_element_t:ayload' portion of a dynamically allocated stack
element. Now, `stack_destroy()' has a while loop in there which calls
stack_pop()' until it gets a NULL return value. Therefore, if I push
1,000 nodes with NULL values for payloads, the `stack_destroy()'
function will only eliminate a single node, and then free the `stack'
which means 999 nodes are leaked.

The while loop will call `stack_pop()', which will pop a single node
and return NULL because I pushed a NULL values onto the stack. This
will in turn terminate the while loop even though there are other
nodes still in the stack.


Does that make sense?

Yes. I think I would have been more explicit (had I been reporting
the error) in that the problem is not pushing NULL, but the wrong test
for empty. I see it now.

 

[Chris M. Thomasson]

Zach said:
In the future please paste your code on a site like
http://pastebin.comrather that your personal webserver attached
to a dynamic IP on a residential connection.

Better still, post it in your article, so that anyone reading the
article can also read the code.

Original code as requested - this has been changed quite a bit since.
I'll post an updated one soon.

[...]

Won't you get a memory leak if I push a NULL pointer onto your
stack?

I can't see it. Can you say why you think it would be a problem?

[...]
Does that make sense?

Yes. I think I would have been more explicit (had I been reporting
the error) in that the problem is not pushing NULL, but the wrong test
for empty.
Agreed.



I see it now.