Hi group,
I'm playing with a little generic linked list/stack library, and have a
little problem with the interface of the pop() function. If I used a
struct like this it would be simple:
struct node {
struct node *next;
void *data;
};
Doing this requires at least two allocations per node. I want to get
that down to 1. The program at the bottom of this post illustrates what
I want to do: the declaration of `struct node2' would exist only in the
library source file. When using the library I would be able to define
multiple lists of different types of elements. The only requirement
would be that the ->next member would be the first member in the
structure.
I'm not 100% certain that it doesn't rely on undefined behaviour though.
The weak spot is the pop() function, that needs to take a pointer to a
pointer to the root node. The c-faq states (q: 4.9) that you can _not_
rely on void ** as a generic pointer to pointer. However, this post (by
Ben Pfaff in this group) seem to indicate that there _are_ uses of `void
**' that are acceptable:
http://tinyurl.com/sbem [0]
Therefore, I ask: is it okay to use `void **' for my use in this case?
The argument is that I wouldn't be using it as a pointer to pointer to
any type but for structures only.
The standard (C89, A6.8) states that any pointer to an object can be
converted to a pointer to void * and back. But can `void *' be thought
of as an object on its own which can be pointer to?
The alternative is to declare all functions to take/return a `struct
mynode *' instead (and `struct mynode **' for the problematic pop()
function). Then, I define `struct mynode' similarly to `struct node'
above internally and let users define `struct mynode' as they want. This
would provide more type safety and was indeed my initial approach, but I
ran into a problem when I wanted lists of two different types of nodes
in the same program. I would then have to use a different name for at
least one of the structures and cast them for every call to my library
functions. I didn't like that approach.
[0] here is that url in full; after some time in the archive, the
tinyurl entry will probably expire:
http://groups.google.com/groups?hl=e...n.user.msu.edu
Stig
Here is that program. The `irky' points are numbered 1 and 2 in
comments. With the cast to void ** in place GCC compiles it cleanly and
without complaints with -W -Wall -ansi -pedantic. The program also seem
to run correctly and produces the output I would expect. However, I have
heard often that void ** is not portable[1], so I am not entirely sure
if it is a conforming standard C program.
[1] and gcc requiring a cast to shut up about wrong types is a hint in
that direction...
#include <stdio.h>
#include <stdlib.h>
struct node1 {
struct node1 *next;
int val;
};
struct node2 {
struct node2 *next;
};
void *push(void *root, void *p)
{
struct node2 *q = p;
if (!q)
return root;
q->next = root;
return q;
}
/* 1: not 100% certain if this is allowed in ANSI C */
void *pop(void **root)
{
struct node2 *p = *root;
if (!p)
return NULL;
*root = p->next;
p->next = NULL;
return p;
}
int main(void)
{
struct node1 *root, *p;
int i;
root = NULL;
for (i = 0; i < 10; i++) {
p = malloc(sizeof *p);
if (!p) {
puts("can't get new node");
return EXIT_FAILURE;
}
p->next = NULL;
p->val = i;
root = push(root, p);
}
/* 2: GCC gives a warning unless I put that cast in. */
while ((p = pop((void **)&root))) {
printf("p->val: %d\n", p->val);
free(p);
}
return 0;
}
--
brautaset.org
