By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,110 Members | 990 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,110 IT Pros & Developers. It's quick & easy.

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

P: n/a
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 <ENTERTo 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 <ENTERTo 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 <ENTERTo Continue...\n", t);
getchar();

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

assert(! SLIST_GET_FRONT(&g_list));

return exit_prompt(
0, "\n\n\n\
_______________________\npress <ENTERto exit...\n");
}
int exit_prompt(int const status, char const* const buf) {
printf("%s", buf);
getchar();
return status;
}

____________________________

Thank you in advance.
Sep 27 '07 #1
Share this Question
Share on Google+
2 Replies


P: n/a
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:9K******************************@comcast.com. ..
>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

Sep 27 '07 #2

P: n/a
Chris Thomasson wrote On 09/27/07 05:59,:
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:9K******************************@comcast.com. ..
>>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.

--
Er*********@sun.com
Sep 27 '07 #3

This discussion thread is closed

Replies have been disabled for this discussion.