Crazy macro-based doubly-linked list...

[Chris Thomasson]

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?

 

[Ben Pfaff]

** 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.

 

[Chris Thomasson]

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]

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.

 

[Ben Pfaff]

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.

 

[Randy Howard]

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]

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.

 

[WANG Cong]

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

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'.