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

[Chris Thomasson]

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]

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

 

[Eric Sosman]

Chris Thomasson wrote On 09/27/07 05:59,:

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.