`void **' revisited: void *pop(void **root)

S

Stig Brautaset

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=en&lr=&ie=UTF-8&[email protected]


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;
}
 
R

Richard Heathfield

[My track record on void ** is not good. I believe this reply to be correct,
but it might just make rich pickings for the Dan Pops of this world, so you
might want to wait until Monday (Dan doesn't seem to post at the weekends
IIRC) before you make your mind up.]

Stig Brautaset wrote:

/* 1: not 100% certain if this is allowed in ANSI C */
void *pop(void **root)
{
struct node2 *p = *root;

This is fine, syntactically speaking. As long as *root was originally a
struct node2 *, it's fine semantically, too.
if (!p)
return NULL;
*root = p->next;

This is okay too - you're assigning a struct2 * to a void *, which is legal.
p->next = NULL;
return p;
}

int main(void)
{

/* 2: GCC gives a warning unless I put that cast in. */
while ((p = pop((void **)&root))) {

Whether this is correct is less clear. I think it would be better to break
it up, which will mean restructuring your loop a little. By "break it up",
I mean:

void *tmp = root;
p = pop(&tmp);

I don't see any reason for gcc to complain about that.
 
S

Sheldon Simms

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.

The FAQ is correct.
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]

What Ben Pfaff suggests in that post and what you are doing are quite
different. His void ** is a pointer to a dynamically allocated array
of pointers to void. Each of the pointers to void in that array will
be used as a generic pointer. His void ** is not being used as a
generic pointer, rather it is being used to access the array.
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.

I don't think so. I'll try to explain. For the following, assume
we are compiling on a weird machine where the representation of
void * is incompatibly different than the representation of
struct node1 * (or struct node2 *) and that the compiler must
generate code to convert from void * to struct node1 * or vice-
versa. Here's your call to pop():
p = pop((void **)&root))

First you take a pointer to pointer to struct node1 and force
the compiler to consider it a pointer to pointer to void.
This case converts its struct node1 ** argument to a void **,
as necessary. However, it does not convert the representation
of root. It remains a struct node1 *, and not a void *
/* 1: not 100% certain if this is allowed in ANSI C */
void *pop(void **root)
{
struct node2 *p = *root;

Here your intent is to assign *root, which you know is a
struct node1 *, to p. The problem described in the C FAQ is this:
The compiler does not know that *root is actually a struct node1 *
at this point. It thinks *root is a void *.

The compiler, when assigning a void * to p must do a conversion
in order to change the representation of a void * to that of a
struct node2 *. It will generate the code to do the conversion.
But since *root is not actually a void *, the conversion code will
not work properly and the value stored in p will not be what you
want.
if (!p)
return NULL;
*root = p->next;
p->next = NULL;
return p;
}

Richard's solution:

void *tmp = root;
p = pop(&tmp);

resolves this problem by getting the compiler to do this conversion
correctly before the call to pop(). However I suspect you don't
want to require your users to do this (or to have to do the void **
cast for that matter).

One solution is to declare a list type, and have your push() and pop()
functions take a parameter of that type:

(warning: untested code)

struct list
{
struct node2 * root;
/* you can also include other useful members like: */
unsigned int size;
};

void init (struct list * plist)
{
plist->root = NULL;
plist->size = 0;
}

void push(struct list * plist, void * p)
{
struct node2 *q = p;
if (!q) return;

q->next = plist->root;
plist->root = p;
plist->size += 1;
}

void * pop(struct list * plist)
{
struct node2 * p;
if (plist->size == 0) return NULL;

p = plist->root;
plist->root = plist->root->next;
p->next = NULL;
return p;
}

-Sheldon
 
C

Chris Torek

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

It does.
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?

There are indeed uses for "void **", but this is not one of them.
What "void **" can do is point to actual objects of type "void *".

There is a way to think about this that should generally get you
the right answer; I will get to that in a moment.
The argument is that I wouldn't be using it as a pointer to pointer to
any type but for structures only.

In at least one actual implementation, "void *" (and "char *") are
"byte pointers", while all other pointers -- short *, int *, float *,
double *, and importantly, struct S * for any "S" -- are "word
pointers".
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?

Yes. But you must have an actual instance of such an object.

The way to think about this is:

- A cast always produces a conversion, as if by assignment to
a temporary. The only real differences between casting and
ordinary assignment (to just such a temporary) are that
(a) if you had an actual temporary, you could take its
address, and (b) casts involving pointers can remove the
requirement for, and usually the actual issuing of, diagnostic
messages in "dodgy cases".

- Ordinary assignment to or from "void *" variables also
produces a conversion.

The conversions you get when mixing "void *" and other pointer
types are, at least in principle, just like those you get when
converting between integral and floating-point types. On today's
typical 32-bit-integer 32-bit-IEEE-float machine, if you have:

int i;
float f;

then sizeof i == sizeof f, yet in operations like:

i = f; /* or */
f = i; /* after assigning values to them, of course */

nobody expects these to be simple "copy the bits" operations, at
least not after examining how floating-point works or looking at
the actual machine code produced by the compiler. (The machine
code involved may be a single "convert FP to int" or "convert int
to FP" instruction, or even a whole series of instructions, depending
on the CPU.) In any case, the change from something like 3.14159
(a float) to 3 (an int) actually changes the bit pattern in memory,
so that a memory-dump of the bits stored in "i" and those stored
in "f" look nothing alike. Moreover, doing:

i = f, f = i;

or even:

f = (int)f;

drops any digits past the decimal point, changing f from 3.14159
to 3.0. Clearly ordinary assignment is not a bitwise copy!

The key here is that, in the "C virtual machine" defined by the
standard, THE SAME THING HAPPENS WITH POINTERS. Changing "pointer
to T", for some type T, to "pointer to unspecified byte(s)" -- the
special "void *" thing in C -- is allowed to change the bits, even
when sizeof(T *) == sizeof(void *). On a few rare systems, it
really does change the bits. (On a few even-rarer systems, the
sizeof()s may even differ.)

Thus, if a routine takes a pointer to a "void *" object, you must
pass it the address of an actual "void *" object -- just as a
routine that takes a "float *" needs the address of an actual
float, not the address of an int cast to "float *". That is,
just as you would do:

result = set_a_float(&f);
i = f; /* we only want the integer part -- do a conversion
to discard the fractional part of f. */

you can do the equivalent with "void *" and other pointers:

struct S *x;
void *tmp;

result = set_a_voidstar(&tmp);
x = tmp; /* we know that the value in tmp is valid after conversion
(back) to "struct S *", so do the conversion. */
The alternative is to declare all functions to take/return a `struct
mynode *' instead (and `struct mynode **' for the problematic pop()
function).

There are other alternatives (although for my part, I think of
linked lists -- whether used as stacks or not -- as so simple that
you might as well just do them in line in many cases). One is the
one outlined above: have an actual temporary variable of type
"void *", pass its address, and convert the result stored in it.
Another is to return a structure containing two "void *"s:

struct list {
struct list *next;
};
struct uglyval {
void *head;
void *rest;
};

struct uglyval ugly(void *head) {
struct popval ret;
struct list *tmp;

tmp = head;
ret.head = tmp; /* or ret.head = head */
ret.rest = tmp->next;
return ret;
}

This second version illustrates the real problem with both
approaches, because now the stack-pop sequence goes from:
while ((p = pop((void **)&root))) {
printf("p->val: %d\n", p->val);
free(p);
}

(where "p" and "root" are both "struct node1 *") to:

struct node1 *p, *root;
struct uglyval tmp;
...
for (;;) {
tmp = ugly(root);
if ((p = tmp.head) == NULL)
break;
root = tmp.rest;
printf("p->val: %d\n", p->val);
free(p);
}

and you might as well just inline the whole thing, giving:

while (root != NULL) {
p = root;
root = p->next;
...
}

getting rid of both the temporary and function ugly(). The
version with a single "void *" temporary is not QUITE as bad:

struct node1 *p, *root;
void *tmp;
...
while (tmp = root, p = pop(&tmp), root = tmp, p != NULL) {
...
}

which is just a comma-operator-ized variant of the ugly() loop.
We can do the same with ugly():

while (tmp = ugly(root), p = tmp.head, root = tmp.rest, p != NULL)

but the result remains, well, ugly. :)

There is one last technique that uses the "all structure pointers
smell the same" idea that, comp.std.c folks assure us, is true even
though it is not literally spelled out in the C standard. This
method is horrible enough that I decided not to illustrate it after
all.
 
J

Jeremy Yallop

Chris said:
There is one last technique that uses the "all structure pointers
smell the same" idea that, comp.std.c folks assure us, is true even
though it is not literally spelled out in the C standard.

FWIW, this has been made explicit in C99:

"All pointers to structure types shall have the same representation
and alignment requirements as each other." (6.2.5[26])

Jeremy.
 
T

Thomas Stegen

Stig Brautaset wrote:

/* 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;
}

Try this maybe.

void *pop(void *root)
{
struct node2 *p = *(struct node2 **)root;
if (!p)
return NULL;
*root = p->next;
p->next = NULL;
return p;
}

Since void is a generic pointer it is also a generic pointer
to pointer.
 
J

James Hu

Stig Brautaset wrote:



Try this maybe.

void *pop(void *root)
{
struct node2 *p = *(struct node2 **)root;
if (!p)
return NULL;
*root = p->next;
p->next = NULL;
return p;
}

Since void is a generic pointer it is also a generic pointer
to pointer.


Good idea, just needs a minor correction:

void *pop(void *root)
{
struct node2 **pp = root;
struct node2 *p = *pp;
if (!p)
return NULL;
*pp = p->next;
p->next = NULL;
return p;
}

-- James
 
J

James Antill

Good idea, just needs a minor correction:

struct node2 **pp = root;
struct node2 *p = *pp;

Why does it "need" this? Do you have chapter and verse for why the first
form is undefined?
 
T

Thomas Stegen

James said:
Why does it "need" this? Do you have chapter and verse for why the first
form is undefined?

That is not where the problem is. The problem is the dereferencing of
root a bit further down without an explicit conversion from void*.
This is not the problem, but it solves the problem :)
 
S

Stig Brautaset

James Hu said:
Good idea, just needs a minor correction:

void *pop(void *root)
{
struct node2 **pp = root;
struct node2 *p = *pp;
if (!p)
return NULL;
*pp = p->next;
p->next = NULL;
return p;
}

Ah, this would do me nicely as long as it is conforming C. Using a `void
*' as argument did cross my mind at one point, but I discarded it
because I didn't think it would work since I wanted to pass data _back_
through it too.

It is weird-looking, but with proper documentation... :)

Thanks guys :)
 
G

goose

Stig Brautaset said:
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.

<rest of post snipped>

I've also played around with a generic list library, haven't
as yet /used/ it anywhere, but feel free to use and distribute.
this was done purely in response to an earlier thread on clc
(search google groups (clc) for goose ll_new to find the thread).

<beware>
there may be bugs, not fully tested as this is
just a toy for playing, not production.
</beware>


/*
credit all the macro-safety fixes to Bernd Jendrissek
(berndj at prism.co.za) and the initial rather dodgy
code to l. k. manickum (leem at acs.altech.co.za).

consider this code to be in the public domain, with
no warranties, etc ad nauseum ...

-lee
*/

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


/* TODO: some sort of iterator */

/***************************/
/* some misc. declarations */
/***************************/
typedef int (*f_compare_ptr) (void *, void *);


/******************************/
/* all the node related stuff */
/******************************/
struct node_t {
void *data;
struct node_t *next;
struct node_t *prev;
};

struct node_t *fll_new (size_t size) {
struct node_t *node = malloc (sizeof *node);
if (!node) {
return NULL;
}
node->data = malloc (size);
if (!node->data) {
free (node);
return NULL;
} else {
node->next = NULL;
node->prev = NULL;
return node;
}
}


#define ll_node_new(the_type) fll_new (sizeof (the_type))
#define ll_node_del(node) \
do { free(node->data); free (node); } while (0)
#define ll_node_set(node,type,val) *(type *)node->data = val
#define ll_node_get(node,type) *(type *)node->data

#define ll_node_insert(list,node) do {\
struct node_t *t = list->next;\
list->next = node;\
node->prev = list;\
node->next = t;\
} while (0)

#define ll_node_remove(node) do {\
node->prev->next = node->next;\
node->next->prev = node->prev;\
ll_node_del (node);\
} while (0)


/******************************/
/* all the list related stuff */
/******************************/
struct list_t {
struct node_t *head;
struct node_t *tail;
};

struct list_t *fll_list_new (void) {
struct list_t *retvalue = malloc (sizeof *retvalue);
if (!retvalue) {
return NULL;
}
retvalue->head = fll_new (0);
if (!retvalue->head) {
free (retvalue);
return NULL;
}
retvalue->tail = fll_new (0);
if (!retvalue->tail) {
free (retvalue->head);
free (retvalue);
return NULL;
}
ll_node_insert (retvalue->head, retvalue->tail);
return retvalue;
}

void *fll_list_find (struct list_t *list, void *value, f_compare_ptr compare) {
struct node_t *t = list->head;
while (t!=list->tail) {
if ((*compare)(t->data, value)==0) {
return t;
}
t = t->next;
}
return NULL;
}

#define ll_list_insert(list,node) ll_node_insert (list->head, node)
#define ll_list_remove(list,node) ll_node_remove (node) /* for later */

#define ll_list_new fll_list_new /* also for future use*/

#define ll_list_del(list) do {\
while (list->head->next!=list->tail) {\
struct node_t *t = list->head->next;\
ll_node_remove (t);\
}\
ll_node_del (list->head);\
ll_node_del (list->tail);\
} while (0)

#define ll_list_find(list,value,functino) \
fll_list_find (list, value, functino)


/* the comparison function for ints */
int compare_ints (void *int1, void *int2) {
if (*(int *)int1 < *(int *)int2) {
return -1;
}
if (*(int *)int1 > *(int *)int2) {
return 1;
}
return 0;
}

int main (void) {
int i;
struct list_t *list;
struct node_t *t;

/* create a linked list */
list = ll_list_new ();
if (!list) {
printf ("no mem ?\n");
return EXIT_FAILURE;
}

/* add stuff into the list */
for (i = 0; i<10; i++) {
struct node_t *node = ll_node_new (int);
ll_node_set (node, int, i+42);
ll_list_insert (list, node);
printf ("set %i\n", i+42);
}

/* find an item in the list */
i = 45;
t = ll_list_find (list, &i, compare_ints);
printf ("item is %p\n value is %i\n", (void *)t, ll_node_get (t, int));

/* print the list out */
t = list->head->next;
while (t!=list->tail) {
int value = ll_node_get (t, int);
printf ("%i\n", value);
t = t->next;
}

/* delete the list */
ll_list_del (list);

return EXIT_SUCCESS;
}
 
S

Stig Brautaset

goose said:
<rest of post snipped>

I've also played around with a generic list library, haven't
as yet /used/ it anywhere, but feel free to use and distribute.
this was done purely in response to an earlier thread on clc
(search google groups (clc) for goose ll_new to find the thread).

I have written such a small library already (which I've used in a few
programs), but it (as yours) uses two allocations per node. I wanted to
get that down to one. Mostly out of curiosity, to be honest.

http://www.brautaset.org/projects/#yalla
<beware>
there may be bugs, not fully tested as this is
just a toy for playing, not production.
</beware>

Likewise :)

Stig
 
J

James Hu

I have written such a small library already (which I've used in a few
programs), but it (as yours) uses two allocations per node. I wanted to
get that down to one. Mostly out of curiosity, to be honest.

http://www.brautaset.org/projects/#yalla


Likewise :)

One way to reduce the number of allocations is to provide an inheritance
interface to your list. This way is closest in spirit to the interface
you posted recently.

---
#define IS_A(type) type is_a

struct listnode {
struct listnode *next;
};

struct list {
struct listnode *top;
}

extern int push(struct list *l, struct listnode *n);
extern struct listnode * pop(struct list *l);

#define PUSH(root,node) push(&root->is_a, &node->is_a)
#define POP(root) pop(&root->is_a)
---
struct my_listnode1 {
IS_A(struct listnode);
int data;
};

struct my_list1 {
IS_A(struct list);
};

struct my_listnode2 {
IS_A(struct listnode);
double data;
};

struct my_list2 {
IS_A(struct list);
};
---

Another way to reduce the number of allocations is to provide a factory
mechanism for creating nodes.

---
struct listnode; /* opaque */

/* allocates a listnode */
extern struct listnode * make_listnode(size_t data_size);

/* returns pointer to data portion of listnode */
extern void * listnode_data(struct listnode *node);

... rest of listnode interface ...
---

-- James
 
T

The Real OS/2 Guy

I have written such a small library already (which I've used in a few
programs), but it (as yours) uses two allocations per node. I wanted to
get that down to one. Mostly out of curiosity, to be honest.

Legitime because avoiding pointers is avoiding memory overload.


------------list.h-------------

typedef void *(*pfnlist)(void *elem);

void *new_list(void *root, size_t size);
void *insert_list(void *root, void *elem);
void *remove_list(void *elem, pfnlist);
.......

typedef struct list *PLIST; /* incomplete type - but enough to use */
/* it as self document placeholder */
/* instead of plain void* in the caller*/
--------------------------------

------------list.c--------------
struct list {
struct list *pNext;
} list;

/* create new node, insert at end of list */
void* new_list(void *root, size_t size) {
struct list *pel = malloc(sizeof(*p) + size);
struct list *pprev = root;
struct list *pcur;
if (p) {
/* insert at end of list */
for (pcur = root; pprev->pNext; pprev = pcur, pcur = pcur->
pNext)
;

pcur->pNext = pel; /* same as *pcur = pel; */
pel->pNext = NULL;
}
return pel;
}

...........

-------------data.c---------

#include "list.h" /* anything we need to know about a list */

struct data {
PLIST pNEXT; /* must be 1. member of struct! */
/* data definitions */
} data;

struct data *root = NULL;


struct data *p = new_list(&root, sizeof(*p);
.......

-----------------------------


The same is for tree:

struct tree {
struct tree *pNelt;
struct tree *pPre;
} tree;

We use the warranty the standard gives about the member alignment of
the first element of a struct. So even if we address

struct data data;
struct data p = NULL;

struct list *pl = &p;
struct list *pn = pl->pNext;
struct list *pn2 = *p1;

pl->pNext = ....;

the target is always the same pointer.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Void problem 1
void* and void** compatibility 20
void * 10
Changing styles inside shadow-root 2
void * 36
Infinite loop problem 1
void * 22
void pointers 36

Members online

Forum statistics

Threads
473,733
Messages
2,569,439
Members
44,829
Latest member
PIXThurman

Latest Threads

Top