Crazy macro-based doubly-linked list...

Discussion in 'C Programming' started by Chris Thomasson, Feb 27, 2008.

  1. Here is the code:

    ** WARNING ** - Reading this might make your eyes squirt blood all over the
    room!

    http://appcore.home.comcast.net/misc/dlist_macro_h.html


    You use it like a intrusive C++ template-based collection. The default setup
    relies on the node data-structures to have members named 'llprev' and
    'llnext', and the anchor data-structure uses 'llhead' and 'lltail' as member
    named. These can be changed by defining 'DLIST_DEFAULT_XXX' macros before
    you include the file. Here is a little program which shows how to use some
    of the macro functions:
    _________________________________________________________________
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include "dlist_macro.h"


    #define LIST_DEPTH() 10


    typedef struct foo_node_s foo_node;
    typedef struct foo_list_s foo_list;

    struct foo_node_s {
    foo_node* llprev;
    foo_node* llnext;
    int id;
    };

    struct foo_list_s {
    foo_node* llhead;
    foo_node* lltail;
    };


    static foo_list g_list1 = { 0 }, g_list2 = { 0 };


    int main(void) {
    int i;
    foo_list list_tmp = { 0 };
    foo_node* node;

    for (i = 0; i < LIST_DEPTH(); ++i) {
    if (! (i % 2)) {
    node = DLIST_PUSHHEAD(&g_list1, malloc(sizeof(*node)));
    } else {
    node = DLIST_PUSHTAIL(&g_list1, malloc(sizeof(*node)));
    }
    if (node) {
    node->id = i;
    printf("created %p(%d)\n", (void*)node, node->id);
    }
    }

    node = DLIST_GETHEAD(&g_list1);
    while (node) {
    foo_node* const next = DLINK_GETNEXT(node);
    if (! (node->id % 2)) {
    DLIST_POP(&g_list1, node);
    DLIST_PUSHHEAD(&g_list2, node);
    }
    node = next;
    }

    while (DLIST_POPTAIL(&g_list1, &node)) {
    DLIST_PUSHHEAD(&list_tmp, node);
    if (DLIST_POPHEAD(&g_list1, &node)) {
    DLIST_PUSHTAIL(&list_tmp, node);
    }
    }

    DLIST_MERGETAIL(&g_list2, &list_tmp);
    DLIST_MERGEHEAD(&g_list1, &g_list2);

    DLIST_FLUSH(&g_list1, &node);
    while (node) {
    foo_node* const next = DLINK_GETNEXT(node);
    if (! (node->id % 2)) {
    DLIST_PUSHTAIL(&list_tmp, node);
    } else {
    DLIST_PUSHHEAD(&list_tmp, node);
    }
    node = next;
    }

    while (DLIST_POPHEAD(&list_tmp, &node)) {
    printf("destroyed %p(%d)\n", (void*)node, node->id);
    free(node);
    if (DLIST_POPTAIL(&g_list1, &node)) {
    printf("destroyed %p(%d)\n", (void*)node, node->id);
    free(node);
    }
    }

    assert(! DLIST_FLUSH(&g_list1, &node) &&
    ! DLIST_FLUSH(&g_list2, &node) &&
    ! DLIST_FLUSH(&list_tmp, &node));

    /*-----------------------------------------------------------*/
    puts("\n\n\n______________________________________________\n\
    press <ENTER> to exit...");
    getchar();
    return 0;
    }

    _________________________________________________________________



    Do the macro functions look okay to you?


    --
    Chris M. Thomasson
    http://appcore.home.comcast.net
     
    Chris Thomasson, Feb 27, 2008
    #1
    1. Advertising

  2. Chris Thomasson

    Ben Pfaff Guest

    "Chris Thomasson" <> writes:

    > ** WARNING ** - Reading this might make your eyes squirt blood all
    > over the room!
    >
    > http://appcore.home.comcast.net/misc/dlist_macro_h.html
    >
    >
    > You use it like a intrusive C++ template-based collection. The default
    > setup relies on the node data-structures to have members named
    > llprev' and 'llnext', and the anchor data-structure uses 'llhead' and
    > lltail' as member named. These can be changed by defining
    > DLIST_DEFAULT_XXX' macros before you include the file. Here is a
    > little program which shows how to use some of the macro functions:


    This approach is a pretty common way to do linked lists in C,
    except that most implementations do not hard-code the names of
    the members. See, for example, include/linux/list.h in any Linux
    kernel source distribution, or sys/queue.h in any of the BSDs.
    --
    char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
    ={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa67f6aaa,0xaa9aa9f6,0x11f6},*p
    =b,i=24;for(;p+=!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
    2:{i++;if(i)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}
     
    Ben Pfaff, Feb 27, 2008
    #2
    1. Advertising

  3. "Chris Thomasson" <> wrote in message
    news:...
    > Here is the code:
    >
    > ** WARNING ** - Reading this might make your eyes squirt blood all over
    > the room!
    >
    > http://appcore.home.comcast.net/misc/dlist_macro_h.html
    >
    >

    [...]
    > _________________________________________________________________

    [...]

    > while (DLIST_POPHEAD(&list_tmp, &node)) {
    > printf("destroyed %p(%d)\n", (void*)node, node->id);
    > free(node);
    > if (DLIST_POPTAIL(&g_list1, &node)) {
    > printf("destroyed %p(%d)\n", (void*)node, node->id);
    > free(node);
    > }
    > }

    [...]

    One little typo. The test code runs fine, for me at least, as-is. However,
    wrt the code above I wanted to pop the head off 'list_tmp', and then pop the
    tail off 'list_tmp'. Therefore, I need to change the above to:


    while (DLIST_POPHEAD(&list_tmp, &node)) {
    printf("destroyed %p(%d)\n", (void*)node, node->id);
    free(node);
    if (DLIST_POPTAIL(&list_tmp, &node)) {
    printf("destroyed %p(%d)\n", (void*)node, node->id);
    free(node);
    }
    }



    > _________________________________________________________________

    [...]


    Does the test run on your systems? Or does it seg-fault right off the bat?
     
    Chris Thomasson, Feb 27, 2008
    #3
  4. "Ben Pfaff" <> wrote in message
    news:...
    > "Chris Thomasson" <> writes:
    >
    >> ** WARNING ** - Reading this might make your eyes squirt blood all
    >> over the room!
    >>
    >> http://appcore.home.comcast.net/misc/dlist_macro_h.html
    >>
    >>
    >> You use it like a intrusive C++ template-based collection. The default
    >> setup relies on the node data-structures to have members named
    >> llprev' and 'llnext', and the anchor data-structure uses 'llhead' and
    >> lltail' as member named. These can be changed by defining
    >> DLIST_DEFAULT_XXX' macros before you include the file. Here is a
    >> little program which shows how to use some of the macro functions:

    >
    > This approach is a pretty common way to do linked lists in C,
    > except that most implementations do not hard-code the names of
    > the members. See, for example, include/linux/list.h in any Linux
    > kernel source distribution, or sys/queue.h in any of the BSDs.


    [...]

    IIRC, you use the 'list_entry' macro function and pass it a pointer to a
    'list_head' data-structure, name of the user data-structure and a member
    name. I believe that it uses the offsetof macro to do this.
     
    Chris Thomasson, Feb 27, 2008
    #4
  5. Chris Thomasson

    Ben Pfaff Guest

    "Chris Thomasson" <> writes:

    > "Ben Pfaff" <> wrote in message
    > news:...
    >> "Chris Thomasson" <> writes:
    >>
    >>> ** WARNING ** - Reading this might make your eyes squirt blood all
    >>> over the room!
    >>>
    >>> http://appcore.home.comcast.net/misc/dlist_macro_h.html
    >>>
    >>>
    >>> You use it like a intrusive C++ template-based collection. The default
    >>> setup relies on the node data-structures to have members named
    >>> llprev' and 'llnext', and the anchor data-structure uses 'llhead' and
    >>> lltail' as member named. These can be changed by defining
    >>> DLIST_DEFAULT_XXX' macros before you include the file. Here is a
    >>> little program which shows how to use some of the macro functions:

    >>
    >> This approach is a pretty common way to do linked lists in C,
    >> except that most implementations do not hard-code the names of
    >> the members. See, for example, include/linux/list.h in any Linux
    >> kernel source distribution, or sys/queue.h in any of the BSDs.

    >
    > IIRC, you use the 'list_entry' macro function and pass it a pointer to
    > a 'list_head' data-structure, name of the user data-structure and a
    > member name. I believe that it uses the offsetof macro to do this.


    Something like that, yes. It's more flexible to do it than way
    than to use hard-coded member names, because it allows a single
    structure to be in more than one linked list.
    --
    char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
    ={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa67f6aaa,0xaa9aa9f6,0x11f6},*p
    =b,i=24;for(;p+=!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
    2:{i++;if(i)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}
     
    Ben Pfaff, Feb 27, 2008
    #5
  6. Chris Thomasson

    Randy Howard Guest

    On Wed, 27 Feb 2008 16:35:57 -0600, Chris Thomasson wrote
    (in article <>):

    > "Chris Thomasson" <> wrote in message
    > news:...
    >> Here is the code:
    >>
    >> ** WARNING ** - Reading this might make your eyes squirt blood all over
    >> the room!
    >>
    >> http://appcore.home.comcast.net/misc/dlist_macro_h.html
    >>
    >>

    > [...]
    >> _________________________________________________________________

    > [...]
    >
    >> while (DLIST_POPHEAD(&list_tmp, &node)) {
    >> printf("destroyed %p(%d)\n", (void*)node, node->id);
    >> free(node);
    >> if (DLIST_POPTAIL(&g_list1, &node)) {
    >> printf("destroyed %p(%d)\n", (void*)node, node->id);
    >> free(node);
    >> }
    >> }

    > [...]
    >
    > One little typo. The test code runs fine, for me at least, as-is. However,
    > wrt the code above I wanted to pop the head off 'list_tmp', and then pop the
    > tail off 'list_tmp'. Therefore, I need to change the above to:
    >
    >
    > while (DLIST_POPHEAD(&list_tmp, &node)) {
    > printf("destroyed %p(%d)\n", (void*)node, node->id);
    > free(node);
    > if (DLIST_POPTAIL(&list_tmp, &node)) {
    > printf("destroyed %p(%d)\n", (void*)node, node->id);
    > free(node);
    > }
    > }
    >
    >
    >
    >> _________________________________________________________________

    > [...]
    >
    >
    > Does the test run on your systems? Or does it seg-fault right off the bat?
    >


    You didn't post the header that goes along with it, so that's going to
    be difficult to test.



    --
    Randy Howard (2reply remove FOOBAR)
    "The power of accurate observation is called cynicism by those
    who have not got it." - George Bernard Shaw
     
    Randy Howard, Feb 28, 2008
    #6
  7. Chris Thomasson

    Randy Howard Guest

    On Wed, 27 Feb 2008 16:35:57 -0600, Chris Thomasson wrote
    (in article <>):

    > "Chris Thomasson" <> wrote in message
    > news:...
    >> Here is the code:
    >>
    >> ** WARNING ** - Reading this might make your eyes squirt blood all over
    >> the room!
    >>
    >> http://appcore.home.comcast.net/misc/dlist_macro_h.html
    >>
    >>

    > [...]
    >> _________________________________________________________________

    > [...]
    >
    >> while (DLIST_POPHEAD(&list_tmp, &node)) {
    >> printf("destroyed %p(%d)\n", (void*)node, node->id);
    >> free(node);
    >> if (DLIST_POPTAIL(&g_list1, &node)) {
    >> printf("destroyed %p(%d)\n", (void*)node, node->id);
    >> free(node);
    >> }
    >> }

    > [...]
    >
    > One little typo. The test code runs fine, for me at least, as-is. However,
    > wrt the code above I wanted to pop the head off 'list_tmp', and then pop the
    > tail off 'list_tmp'. Therefore, I need to change the above to:
    >
    >
    > while (DLIST_POPHEAD(&list_tmp, &node)) {
    > printf("destroyed %p(%d)\n", (void*)node, node->id);
    > free(node);
    > if (DLIST_POPTAIL(&list_tmp, &node)) {
    > printf("destroyed %p(%d)\n", (void*)node, node->id);
    > free(node);
    > }
    > }
    >
    >
    >
    >> _________________________________________________________________

    > [...]
    >
    >
    > Does the test run on your systems? Or does it seg-fault right off the bat?
    >


    Disregard the last, I missed the URL.



    --
    Randy Howard (2reply remove FOOBAR)
    "The power of accurate observation is called cynicism by those
    who have not got it." - George Bernard Shaw
     
    Randy Howard, Feb 28, 2008
    #7
  8. Chris Thomasson

    WANG Cong Guest

    On Wed, 27 Feb 2008 15:49:40 -0800,Chris Thomasson wrote:

    > "Ben Pfaff" <> wrote in message
    > news:...
    >> "Chris Thomasson" <> writes:
    >>
    >>> ** WARNING ** - Reading this might make your eyes squirt blood all
    >>> over the room!
    >>>
    >>> http://appcore.home.comcast.net/misc/dlist_macro_h.html
    >>>
    >>>
    >>> You use it like a intrusive C++ template-based collection. The default
    >>> setup relies on the node data-structures to have members named llprev'
    >>> and 'llnext', and the anchor data-structure uses 'llhead' and lltail'
    >>> as member named. These can be changed by defining DLIST_DEFAULT_XXX'
    >>> macros before you include the file. Here is a little program which
    >>> shows how to use some of the macro functions:

    >>
    >> This approach is a pretty common way to do linked lists in C, except
    >> that most implementations do not hard-code the names of the members.
    >> See, for example, include/linux/list.h in any Linux kernel source
    >> distribution, or sys/queue.h in any of the BSDs.

    >
    > [...]
    >
    > IIRC, you use the 'list_entry' macro function and pass it a pointer to a
    > 'list_head' data-structure, name of the user data-structure and a member
    > name. I believe that it uses the offsetof macro to do this.


    Yes, Linux really does so. IIRC, 'list_entry' is a wrapper of
    'container_of' which in turn uses 'offsetof'.
     
    WANG Cong, Feb 28, 2008
    #8
    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. murali@pune

    doubly linked list

    murali@pune, Mar 23, 2006, in forum: Java
    Replies:
    3
    Views:
    933
    bugbear
    Mar 24, 2006
  2. darth
    Replies:
    0
    Views:
    458
    darth
    Apr 30, 2004
  3. chand
    Replies:
    7
    Views:
    324
    Terry Reedy
    Sep 5, 2005
  4. Daniel
    Replies:
    5
    Views:
    388
  5. dssuresh6

    need for doubly linked list

    dssuresh6, Nov 18, 2004, in forum: C Programming
    Replies:
    4
    Views:
    632
    J. J. Farrell
    Nov 19, 2004
Loading...

Share This Page