void pointers

Discussion in 'C Programming' started by John Hanley, Aug 1, 2004.

  1. John Hanley

    John Hanley Guest

    I working in C. I haven't paid much attention to void pointers in the past,
    but I am wondering if I can use them for my various linked lists to save
    work.

    I have two different linked lists that each use nodes of different structs.
    However the principle of my adding to the linked lists and removing them is
    the same. So will it work to have these functions accept a void pointer as
    an argument for the list and a void pointer as an argument to a node like
    this:

    void add_to_tail(void * list, voic * new_node)
    {
    (list->tail)->next = new_node;

    etc...
    }

    I have two different kinds of "nodes" (structs). Will assigning the void *
    new_node to either kind of node automatically cast it to that kind of node
    (struct)?

    I am just thinking of ways to have one function that serves a generic
    purpose to be used by different kinds of structs. If this was C++ or Java,
    it wouldn't be much of a problem.

    Ideas?

    Thanks again!

    John
     
    John Hanley, Aug 1, 2004
    #1
    1. Advertising

  2. On Sat, 31 Jul 2004 21:52:31 -0600, "John Hanley"
    <> wrote:

    >I working in C. I haven't paid much attention to void pointers in the past,
    >but I am wondering if I can use them for my various linked lists to save
    >work.
    >
    >I have two different linked lists that each use nodes of different structs.
    >However the principle of my adding to the linked lists and removing them is
    >the same. So will it work to have these functions accept a void pointer as
    >an argument for the list and a void pointer as an argument to a node like
    >this:
    >
    >void add_to_tail(void * list, voic * new_node)
    >{
    > (list->tail)->next = new_node;


    Unless you cast it, list does not point to a struct. Therefore, you
    cannot use it on the left of the -> operator.
    >
    > etc...
    >}
    >
    >I have two different kinds of "nodes" (structs). Will assigning the void *
    >new_node to either kind of node automatically cast it to that kind of node
    >(struct)?


    A void* is compatible with any type of object pointer for purposes of
    assignment, in either direction. Both
    void_ptr = obj_ptr;
    and
    obj_ptr = void_ptr;
    are syntactically correct. The only restriction is that the value of
    void_ptr in the second must be valid for the type of obj_ptr. (This
    is obviously not a problem in the first statement.)

    >
    >I am just thinking of ways to have one function that serves a generic
    >purpose to be used by different kinds of structs. If this was C++ or Java,
    >it wouldn't be much of a problem.




    <<Remove the del for email>>
     
    Barry Schwarz, Aug 1, 2004
    #2
    1. Advertising

  3. John Hanley wrote on 01/08/04 :
    > I working in C. I haven't paid much attention to void pointers in the past,
    > but I am wondering if I can use them for my various linked lists to save
    > work.


    Yes, void pointers are useful for generic programming. OTOH, the
    programmer must exactly know what is he doing, because the compiler
    doesn't check the types anymore.

    It is highly recommended that the user is kept away from such gory
    details. Abstraction is not a option.

    --
    Emmanuel
    The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html

    "C is a sharp tool"
     
    Emmanuel Delahaye, Aug 1, 2004
    #3
  4. John Hanley

    Chris Torek Guest

    In article <>
    John Hanley <> writes:
    >I have two different linked lists that each use nodes of different structs.
    >However the principle of my adding to the linked lists and removing them is
    >the same. So will it work to have these functions accept a void pointer as
    >an argument for the list and a void pointer as an argument to a node like
    >this:
    >
    >void add_to_tail(void * list, voic * new_node)
    >{
    > (list->tail)->next = new_node;
    >
    > etc...
    >}
    >
    >I have two different kinds of "nodes" (structs). Will assigning the void *
    >new_node to either kind of node automatically cast it to that kind of node
    >(struct)?


    No, but you are in luck, at least with C99: C99 says that all
    "struct S *" pointers (regardless of S) use the same representation.
    (C89 does *not* say this but in practice it is true anyway.)

    >I am just thinking of ways to have one function that serves a generic
    >purpose to be used by different kinds of structs.


    You *can* do this, but it requires a bit more work. For instance,
    suppose "add_to_tail" works with a structure with two "struct S *"
    objects (for some arbitrary structure type S) whose names might as
    well be "head" and "tail":

    struct S_Header {
    struct S *head;
    struct S *tail;
    };

    /* add the given new "struct S *" to the tail of the given list,
    using the given S_Header. */
    void add_to_tail_using_S_Header(struct S_Header *sh, struct S *new) {
    if (sh->head == NULL)
    sh->head = sh->tail = new;
    else {
    sh->tail->next = new;
    sh->tail = new;
    }
    }

    Of course, add_to_tail_using_S_Header() works only with an S_Header
    and S, and you would like a variant that works regardless of what
    the *name* of the two structures is -- and meanwhile we will hope
    and pray that nobody calls the "genericized" add_to_tail() incorrectly:

    /* "generic" version of add_to_tail_using_S_Header. */
    void add_to_tail(void *sh0, void *new0) {
    struct S_Header *sh;
    struct S *new;

    /* these two steps *are* required for portability */
    sh = sh0;
    new = new0;

    /* the rest is as before */
    if (sh->head == NULL)
    sh->head = sh->tail = new;
    else {
    sh->tail->next = new;
    sh->tail = new;
    }
    }

    Note that the types "struct S_Header" and "struct S" are assumed
    to exist here; if they do not already exist you can simply define
    them within add_to_tail(). The "sh = sh0" and "new = new0"
    assignments above are crucial on word-oriented machines (such as
    the Data General Eclipse); these assignments may actually convert
    from "byte pointers" (in "void *") to "word pointers".

    You can then later have:

    struct T_Header { struct T *head, *tail; };
    struct T { struct T *next; ... };

    struct T_header th;
    ...
    struct T *new = new_t(...);
    add_to_tail(&th, new_t);

    and the C99 Standard's guarantee that "all struct pointers smell
    the same" (as the saying goes) will -- presumably -- mean that the
    only difference between a T_Header and T, and an S_Header and S,
    is the type name, not any underlying representation in storage.
    Thus, even if the call (inefficiently) converts the two word pointers
    &th and new_t to byte pointers, just so that add_to_tail() can
    convert them back from byte pointers to word pointers, it will
    all work.

    Unfortunately, an incorrect call like:

    struct T *a, *b;
    ...
    add_to_tail(a, b);

    will *not* get a diagnostic (unless your compiler goes way beyond
    the requirements of the standard, deep into the "telepathic" range
    of "I sense what you really meant instead of what you wrote" :) ),
    because "void *" is TOO compatible here. Ideally, what you would
    really want is a way to say "the first parameter must be a pointer
    to an object comprising two consecutive pointer objects of the same
    type, both being `pointer to struct X' for some X, and the second
    parameter must then be a `pointer to struct X' for the same X" --
    but there is no way to do this in C.

    If you have access to a BSD machine (or current BSD sources) you
    might look at the BSD <sys/queue.h> macros. These achieve the
    desired effect using compile-time macros that are fully type-checked
    by any conforming C compiler.
    --
    In-Real-Life: Chris Torek, Wind River Systems
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: forget about it http://web.torek.net/torek/index.html
    Reading email is like searching for food in the garbage, thanks to spammers.
     
    Chris Torek, Aug 1, 2004
    #4
  5. John Hanley

    Malcolm Guest

    "John Hanley" <> wrote
    >
    > I working in C. I haven't paid much attention to void pointers in the

    past,
    > but I am wondering if I can use them for my various linked lists to save
    > work.
    >
    > I have two different linked lists that each use nodes of different

    structs.
    > However the principle of my adding to the linked lists and removing them

    is
    > the same. So will it work to have these functions accept a void pointer

    as
    > an argument for the list and a void pointer as an argument to a node like
    > this:
    >
    > void add_to_tail(void * list, voic * new_node)
    > {
    > (list->tail)->next = new_node;
    >
    > etc...
    > }
    >
    > I have two different kinds of "nodes" (structs). Will assigning the void

    *
    > new_node to either kind of node automatically cast it to that kind of node
    > (struct)?
    >
    > I am just thinking of ways to have one function that serves a generic
    > purpose to be used by different kinds of structs. If this was C++ or

    Java,
    > it wouldn't be much of a problem.
    >

    As you say, C++ has a template mechanism that offers compile-time binding by
    name. Thus the same code can operate on two unrelated structs that happen to
    have a member called "next".

    void * is useful for creating generic functions, but it is not as powerful
    as C++ templates. Generally you use void * for passing data of an unknown
    type

    eg struct linkedlistnode
    {
    struct linkedlistnode *prev;
    struct linkedlistnode *next;
    void *data;
    };

    would be a generic node, but you would have to know the size and layout of
    the data pointed to by the last member in other areas of the program.
     
    Malcolm, Aug 1, 2004
    #5
  6. John Hanley <> wrote:
    > I have two different linked lists that each use nodes of different
    > structs. However the principle of my adding to the linked lists and
    > removing them is the same.


    Have a look at http://brautaset.org/projects/sl/ for an example
    implementation of generic linked lists using void pointers. It exploits
    the notion that one struct pointer smells like another, even though the
    structs might be different.

    Additionally, instead of using container nodes with pointers to your
    data it uses a pointer to the next item directly in the datastructure
    you want to create lists (or stacks) of. In addition to significant
    memory savings, this allows for very fast push and pop operations since
    there is no need to allocate/free memory for the container nodes. It
    also means that a push can't fail because memory couldn't be allocated
    for the container node.

    PS: thanks to all the people here on comp.lang.c that helped me get the
    understanding that enabled me to write the above mentioned library.

    Stig
     
    Stig Brautaset, Aug 1, 2004
    #6
  7. John Hanley

    pete Guest

    John Hanley wrote:
    >
    > I working in C. I haven't paid much attention to
    > void pointers in the past,
    > but I am wondering if I can use them for my
    > various linked lists to save work.
    >
    > I have two different linked lists that each
    > use nodes of different structs.
    > However the principle of my adding to the linked
    > lists and removing them is the same.


    I wind up writing nearly identical functions when working
    with list of different type nodes.
    Sometimes, things, like concatenation of lists, are exactly the same.

    void cl_cat(cn_type *head, cn_type *tail)
    {
    cn_type *old;

    if (head != NULL) {
    do {
    old = head;
    head = head -> c_NEXT;
    } while (head != NULL);
    old -> c_NEXT = tail;
    }
    }

    void pl_cat(pn_type *head, pn_type *tail)
    {
    pn_type *old;

    if (head != NULL) {
    do {
    old = head;
    head = head -> p_NEXT;
    } while (head != NULL);
    old -> p_NEXT = tail;
    }
    }

    Sometimes, things, like freeing the lists, aren't exactly the same.

    void pl_free(pn_type *node)
    {
    pn_type *next;

    while (node != NULL) {
    next = node -> p_NEXT;
    free(node);
    node = next;
    }
    }

    void cl_free(cn_type *node)
    {
    cn_type *next;

    while (node != NULL) {
    pl_free(node -> car.part_list);
    next = node -> c_NEXT;
    free(node);
    node = next;
    }
    }

    --
    pete
     
    pete, Aug 2, 2004
    #7
  8. John Hanley

    CBFalconer Guest

    pete wrote:
    > John Hanley wrote:
    >>
    >> I working in C. I haven't paid much attention to void pointers
    >> in the past, but I am wondering if I can use them for my
    >> various linked lists to save work.
    >>
    >> I have two different linked lists that each use nodes of
    >> different structs. However the principle of my adding to the
    >> linked lists and removing them is the same.

    >
    > I wind up writing nearly identical functions when working
    > with list of different type nodes. Sometimes, things, like
    > concatenation of lists, are exactly the same.


    Define the essence of a singly linked list with:

    typedef struct slinklist {
    struct slinklist *next;
    void *data;
    } slinklist;

    and similarly for a doubly linked list:

    typedef struct dlinklist {
    struct dlinklist *next, *prev;
    void *data;
    } dlinklist;

    Now you can write universal functions to do the list
    manipulations, and functions to handle the list data that are
    customized to that data.

    whatever dataop(void *data, otherparams)
    {
    datatype datap = data;

    /* code as needed, using the well typed datap */
    }

    and call it with:

    dataop(mylistitem->data, otherparams);

    --
    "I'm a war president. I make decisions here in the Oval Office
    in foreign policy matters with war on my mind." - Bush.
    "Churchill and Bush can both be considered wartime leaders, just
    as Secretariat and Mr Ed were both horses." - James Rhodes.
     
    CBFalconer, Aug 2, 2004
    #8
  9. John Hanley

    pete Guest

    CBFalconer wrote:
    >
    > pete wrote:
    > > John Hanley wrote:
    > >>
    > >> I working in C. I haven't paid much attention to void pointers
    > >> in the past, but I am wondering if I can use them for my
    > >> various linked lists to save work.
    > >>
    > >> I have two different linked lists that each use nodes of
    > >> different structs. However the principle of my adding to the
    > >> linked lists and removing them is the same.

    > >
    > > I wind up writing nearly identical functions when working
    > > with list of different type nodes. Sometimes, things, like
    > > concatenation of lists, are exactly the same.

    >
    > Define the essence of a singly linked list with:
    >
    > typedef struct slinklist {
    > struct slinklist *next;
    > void *data;
    > } slinklist;
    >
    > and similarly for a doubly linked list:
    >
    > typedef struct dlinklist {
    > struct dlinklist *next, *prev;
    > void *data;
    > } dlinklist;
    >
    > Now you can write universal functions to do the list
    > manipulations, and functions to handle the list data that are
    > customized to that data.
    >
    > whatever dataop(void *data, otherparams)
    > {
    > datatype datap = data;
    >
    > /* code as needed, using the well typed datap */
    > }
    >
    > and call it with:
    >
    > dataop(mylistitem->data, otherparams);


    That's interesting. I'll look into it.

    --
    pete
     
    pete, Aug 3, 2004
    #9
  10. Chris Torek wrote:
    <snip>
    >
    > No, but you are in luck, at least with C99: C99 says that all
    > "struct S *" pointers (regardless of S) use the same representation.
    > (C89 does *not* say this but in practice it is true anyway.)
    >


    In C99, they have the same representation. In C89, they may not, but
    they sure do smell alike!

    :)


    Mark F. Haigh
     
    Mark F. Haigh, Aug 4, 2004
    #10
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ollej Reemt
    Replies:
    7
    Views:
    543
    Jack Klein
    Apr 22, 2005
  2. Stig Brautaset

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

    Stig Brautaset, Oct 25, 2003, in forum: C Programming
    Replies:
    15
    Views:
    791
    The Real OS/2 Guy
    Oct 28, 2003
  3. Peter Goddard

    void pointers & void function pointers

    Peter Goddard, May 16, 2005, in forum: C Programming
    Replies:
    3
    Views:
    519
    Peter Goddard
    May 16, 2005
  4. Replies:
    5
    Views:
    842
    S.Tobias
    Jul 22, 2005
  5. Replies:
    1
    Views:
    412
    Victor Bazarov
    May 23, 2007
Loading...

Share This Page