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

Discussion in 'C Programming' started by Stig Brautaset, Oct 25, 2003.

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

    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:


    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);
    return 0;
    Stig Brautaset, Oct 25, 2003
    1. Advertisements

  2. [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:

    This is fine, syntactically speaking. As long as *root was originally a
    struct node2 *, it's fine semantically, too.
    This is okay too - you're assigning a struct2 * to a void *, which is legal.
    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.
    Richard Heathfield, Oct 25, 2003
    1. Advertisements

  3. The FAQ is correct.
    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.
    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():
    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 *
    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
    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 Simms, Oct 25, 2003
  4. Stig Brautaset

    Chris Torek Guest

    It does.
    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.
    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
    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. */
    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:
    (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)
    root = tmp.rest;
    printf("p->val: %d\n", p->val);

    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
    Chris Torek, Oct 25, 2003
  5. 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 Yallop, Oct 26, 2003
  6. 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.
    Thomas Stegen, Oct 26, 2003
  7. Stig Brautaset

    James Hu Guest

    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
    James Hu, Oct 26, 2003
  8. Stig Brautaset

    James Antill Guest

    Why does it "need" this? Do you have chapter and verse for why the first
    form is undefined?
    James Antill, Oct 27, 2003
  9. Stig Brautaset

    James Hu Guest

    Please review Thomas' code again.

    -- James
    James Hu, Oct 27, 2003
  10. ^^^^
    Oops, yep. I was a bit quick there. Thanks.
    Thomas Stegen, Oct 27, 2003
  11. 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 :)
    Thomas Stegen, Oct 27, 2003
  12. 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 :)
    Stig Brautaset, Oct 27, 2003
  13. Stig Brautaset

    goose Guest

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

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

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


    #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;
    goose, Oct 27, 2003
  14. 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.

    Likewise :)

    Stig Brautaset, Oct 27, 2003
  15. Stig Brautaset

    James Hu Guest

    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
    James Hu, Oct 27, 2003
  16. Legitime because avoiding pointers is avoiding memory overload.


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

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

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



    #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.
    The Real OS/2 Guy, Oct 28, 2003
    1. Advertisements

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 (here). After that, you can post your question and our members will help you out.