undefined behavior in "macro-based" single-linked list impl...

Discussion in 'C Programming' started by Chris Thomasson, Sep 27, 2007.

  1. I was wondering if the 'SLINK_*' and 'SLIST_*' macros, which
    implement a simple singly-linked list, will produce _any_ possible
    undefined behavior:


    ____________________________

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



    /* Single-Link API
    ____________________________________*/
    typedef struct slink_s slink;

    struct slink_s {
    slink* next;
    };

    #define SLINK_STATICINIT() {0}

    #define SLINK_GET_NEXT(mp_this) ( \
    (mp_this)->next \
    )

    #define SLINK_SET_NEXT(mp_this, mp_link) ( \
    (mp_this)->next = (mp_link) \
    )



    /* Single-List API
    ____________________________________*/
    typedef struct slist_s slist;

    struct slist_s {
    slink front;
    };

    /* static init */
    #define SLIST_STATICINIT() { \
    SLINK_STATICINIT() \
    }

    /* returns the front of the list */
    #define SLIST_GET_FRONT(mp_this) ( \
    SLINK_GET_NEXT(&(mp_this)->front) \
    )

    /* returns the mp_link parameter */
    #define SLIST_PUSH_FRONT(mp_this, mp_link) ( \
    SLINK_SET_NEXT(mp_link, SLIST_GET_FRONT(mp_this)), \
    SLINK_SET_NEXT(&(mp_this)->front, mp_link) \
    )

    /* returns 0 on failure */
    #define SLIST_POP_FRONT(mp_this, mp_plink) ( \
    *(mp_plink) = SLIST_GET_FRONT(mp_this), \
    *(mp_plink) \
    ? SLINK_SET_NEXT(&(mp_this)->front, \
    SLINK_GET_NEXT(*(mp_plink))), 1 \
    : 0 \
    )



    /* Test Application
    ____________________________________*/
    #define TEST_DEPTH() 5

    static int exit_prompt(int const, char const* const);


    static slist g_list = SLIST_STATICINIT();


    int main(void) {
    int t;
    for(t = 0; t < TEST_DEPTH(); ++t) {
    int i;
    slink* _this;
    #define LIST_DEPTH() (t + 5)

    for(i = 0; i < LIST_DEPTH(); ++i) {
    slink* cmp = 0;
    _this = malloc(sizeof(*_this));
    cmp = SLIST_PUSH_FRONT(&g_list, _this);
    printf("(%p/%p/%p)-SLIST_PUSH_FRONT(...)\n",
    (void*)_this,
    (void*)SLIST_GET_FRONT(&g_list),
    (void*)SLINK_GET_NEXT(_this));
    assert(_this == cmp);
    }
    printf("(%i)-FILLED! Press <ENTER> To Continue...\n", t);
    getchar();


    _this = SLIST_GET_FRONT(&g_list);
    while(_this) {
    printf("(%p)-SLIST_GET_FRONT(...)\n", (void*)_this);
    _this = SLINK_GET_NEXT(_this);
    }
    printf("(%i)-ITERATED! Press <ENTER> To Continue...\n", t);
    getchar();


    while(SLIST_POP_FRONT(&g_list, &_this)) {
    printf("(%p)-SLIST_POP_FRONT(...)\n", (void*)_this);
    free(_this);
    }
    printf("(%i)-FLUSHED! Press <ENTER> To Continue...\n", t);
    getchar();

    puts("\n----------------------------------");
    }

    assert(! SLIST_GET_FRONT(&g_list));

    return exit_prompt(
    0, "\n\n\n\
    _______________________\npress <ENTER> to exit...\n");
    }


    int exit_prompt(int const status, char const* const buf) {
    printf("%s", buf);
    getchar();
    return status;
    }

    ____________________________



    Thank you in advance.
     
    Chris Thomasson, Sep 27, 2007
    #1
    1. Advertising

  2. "Chris Thomasson" <> wrote in message
    news:...
    >I was wondering if the 'SLINK_*' and 'SLIST_*' macros, which implement a
    >simple singly-linked list, will produce _any_ possible undefined behavior:


    Sorry for any copy-and-paste errors; here is a link to the code in question:

    > ____________________________


    http://appcore.home.comcast.net/misc/macro-slist-c.html

    > ____________________________



    :^0
     
    Chris Thomasson, Sep 27, 2007
    #2
    1. Advertising

  3. Chris Thomasson

    Eric Sosman Guest

    Chris Thomasson wrote On 09/27/07 05:59,:
    > "Chris Thomasson" <> wrote in message
    > news:...
    >
    >>I was wondering if the 'SLINK_*' and 'SLIST_*' macros, which implement a
    >>simple singly-linked list, will produce _any_ possible undefined behavior:

    >
    >
    > Sorry for any copy-and-paste errors; here is a link to the code in question:
    >
    >
    >>____________________________

    >
    >
    > http://appcore.home.comcast.net/misc/macro-slist-c.html


    The macros look all right to me. SLIST_POP_FRONT
    could be streamlined a bit, but I think it's correct.
    They're not safe if the arguments have side-effects:

    SLIST_PUSH_FRONT(list, getAnotherNode());
    or
    slist half[2] = { SLIST_STATICINIT(), SLIST_STATICINIT() };
    int which = 1;
    /* Divide the input nodes among the two lists: */
    while ((node = getAnotherNode()) != NULL)
    SLIST_PUSH_FRONT(half[ which ^= 1 ], node);

    It's a shame that SLIST_POP_FRONT needs an auxiliary
    output variable. I can sympathize with the desire to move
    the success/failure indication "out of band," but in this
    case it seems clumsy. NULL is a widely-understood "failure"
    value for many pointer-related things, and would not be a
    stylistic shock to anyone. SLIST_POP_FRONT already uses
    the nullness of the link to detect end-of-list; why not
    let the user do the same?

    It's too bad that SLINK_SET_NEXT and SLINK_GET_NEXT
    differ by only one letter, buried in the middle of the
    names. Fortunately, their argument counts are different,
    so the compiler will holler if/when somebody mixes them up.

    It'd be Really Ugly to use these macros with nodes
    that can inhabit multiple lists simultaneously. Sparse
    matrices, for example, where each node might be linked
    in both a row list and a column list:

    struct cell {
    int row, col;
    double value;
    slink nextinrow;
    slink nextincol;
    };

    Navigating such a setup will find you using offsetof()
    and casts more heavily than is healthy. (True, the matrix
    as a whole is not a "simple singly-linked list." But its
    rows and columns are when viewed separately, and it's a
    shame that the macros make them hard to manipulate.)

    If I were going to do something like this, I think
    I'd use functions instead of macros: all the side-effect
    safety issues disappear, it's easy to add sanity-checking
    in debug builds, and so on. Also, you gain some type
    safety: SLINK_GET_NEXT will work quite happily with any
    pointer to a struct or union with a `next' member, even
    if that pointer is not an `slink*'. Compilers are pretty
    good at expanding simple functions in-line, especially if
    given C99's `inline' hint.

    --
     
    Eric Sosman, Sep 27, 2007
    #3
    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. Mantorok Redgormor
    Replies:
    70
    Views:
    1,854
    Dan Pop
    Feb 17, 2004
  2. fool
    Replies:
    14
    Views:
    549
    Barry Schwarz
    Jul 3, 2006
  3. joshd
    Replies:
    12
    Views:
    705
    John Carson
    Oct 2, 2006
  4. Chris Thomasson

    Crazy macro-based doubly-linked list...

    Chris Thomasson, Feb 27, 2008, in forum: C Programming
    Replies:
    7
    Views:
    621
    WANG Cong
    Feb 28, 2008
  5. Sébastien de Mapias

    Impl of a list of key/value pairs (and more ?)

    Sébastien de Mapias, Jul 15, 2008, in forum: Java
    Replies:
    31
    Views:
    1,201
    Roger Lindsjö
    Jul 23, 2008
Loading...

Share This Page