Could anyone explain the code for me?

[C++fan]

The following code is for list operation. But I can not understand.
Could anyone explain the code for me?

/*
* List definitions.
*/

#define LIST_HEAD(name, type)
struct name {
type *lh_first; /* first element */
}
#define LIST_ENTRY(type)
struct {
type *le_next; /* next element */
type **le_prev; /* address of previous next element */
}

Questions:
Why the struct does not have a name?
Is the list a two-way list?

/*
* List functions.
*/
#define LIST_INIT(head) {
(head)->lh_first = NULL;
}

#define LIST_INSERT_AFTER(listelm, elm, field) {
if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)
(listelm)->field.le_next->field.le_prev =
&(elm)->field.le_next;
(listelm)->field.le_next = (elm);
(elm)->field.le_prev = &(listelm)->field.le_next;
}

Question:
What is listelm, elm, field?

#define LIST_INSERT_HEAD(head, elm, field) {
if (((elm)->field.le_next = (head)->lh_first) != NULL)
(head)->lh_first->field.le_prev =
&(elm)->field.le_next;
(head)->lh_first = (elm);
(elm)->field.le_prev = &(head)->lh_first;
}

Question:

If elm becomes head, what's the purpose of the last sentence:
(elm)->field.le_prev = &(head)->lh_first;


Thanks in advance.

Jack

 

[Jacques Labuschagne]

The following code is for list operation. But I can not understand.
Could anyone explain the code for me?

/*
* List definitions.
*/

#define LIST_HEAD(name, type)

This doesn't do anything useful.

struct name {
type *lh_first; /* first element */
}

Missing semi-colon after struct definition.

#define LIST_ENTRY(type)

See above.

struct {
type *le_next; /* next element */
type **le_prev; /* address of previous next element */

I suspect le_prev's comment is wrong. Surely le_prev is the previous
node in the list, not the previous le_next (which is /this/ node).

}

Questions:
Why the struct does not have a name?

Looks like an error to me.

Is the list a two-way list?

Well there are pointers to both previous and next nodes...

/*
* List functions.
*/
#define LIST_INIT(head) {
(head)->lh_first = NULL;
}

That isn't how macros work. Read a textbook.

#define LIST_INSERT_AFTER(listelm, elm, field) {
if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)
(listelm)->field.le_next->field.le_prev =
&(elm)->field.le_next;
(listelm)->field.le_next = (elm);
(elm)->field.le_prev = &(listelm)->field.le_next;
}

Question:
What is listelm, elm, field?

They're arguments to a function-style macro. Whoever wrote this doesn't
understand macros, and should be using functions instead.

#define LIST_INSERT_HEAD(head, elm, field) {
if (((elm)->field.le_next = (head)->lh_first) != NULL)
(head)->lh_first->field.le_prev =
&(elm)->field.le_next;
(head)->lh_first = (elm);
(elm)->field.le_prev = &(head)->lh_first;
}

Question:

If elm becomes head, what's the purpose of the last sentence:
(elm)->field.le_prev = &(head)->lh_first;

How about using functions so we can see what the types of the arguments
are? If possible, post a compileable example.

HTH,
Jacques.

 

[Alf P. Steinbach]

C++fan skrev i meldingen

The following code is for list operation. But I can not understand.
Could anyone explain the code for me?

It's an attempt at C++ code written by someone probably learning
basic programming. It's not even syntactically correct. Searching
for "meaning" in such code is useless; evaluate on syntax only.

 

[Cy Edmunds]

The following code is for list operation. But I can not understand.
Could anyone explain the code for me?

/*
* List definitions.
*/

#define LIST_HEAD(name, type)
struct name {
type *lh_first; /* first element */
}
#define LIST_ENTRY(type)
struct {
type *le_next; /* next element */
type **le_prev; /* address of previous next element */
}

Questions:
Why the struct does not have a name?
Is the list a two-way list?

/*
* List functions.
*/
#define LIST_INIT(head) {
(head)->lh_first = NULL;
}

#define LIST_INSERT_AFTER(listelm, elm, field) {
if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)
(listelm)->field.le_next->field.le_prev =
&(elm)->field.le_next;
(listelm)->field.le_next = (elm);
(elm)->field.le_prev = &(listelm)->field.le_next;
}

Question:
What is listelm, elm, field?

#define LIST_INSERT_HEAD(head, elm, field) {
if (((elm)->field.le_next = (head)->lh_first) != NULL)
(head)->lh_first->field.le_prev =
&(elm)->field.le_next;
(head)->lh_first = (elm);
(elm)->field.le_prev = &(head)->lh_first;
}

Question:

If elm becomes head, what's the purpose of the last sentence:
(elm)->field.le_prev = &(head)->lh_first;


Thanks in advance.

Jack

Jack, that's quite a puzzle. As a true "C++fan" I hope you won't actually
use crap like this unless you have to! (Hint: std::list)

Anyway, I'm far from sure of this but maybe it is used as follows:

struct fred_node
{
LIST_ENTRY(struct fred_node) node;
Fred fred; // Fred is some arbitrary type -- this is a list of Freds
};

which translates to:

struct fred_node
{
struct {
struct fred_node *le_next; /* next element */
struct fred_node **le_prev; /* address of previous next element */
} node;
Fred fred; // Fred is some arbitrary type -- this is a list of Freds
};

This defines the node type. Then make the list head:

LIST_HEAD(fred_head, struct fred_node) fredlist;
LIST_INIT(fredlist);

which is equivalent to:

struct fred_head {
struct fred_node *lh_first; /* first element */
} fredlist;
fredlist->lh_first = NULL;

Now add a node:

struct fred_node *new_node = (struct fred_node *) malloc(sizeof(struct
fred_node));
new_node.fred = Fred(21); // whatever that means
LIST_INSERT_HEAD(mylist, new_node, node);

which expands to

struct fred_node *new_node = (struct fred_node *) malloc(sizeof(struct
fred_node));
new_node.fred = Fred(21); // whatever that means
if ((new_node->node.le_next = (fredlist)->lh_first) != NULL)
fredlist->lh_first->node.le_prev = &new_node->node.le_next;
fredlist->lh_first = new_node;
new_node->node.le_prev = &new_node;

Now add another node:

struct fred_node *newer_node = (struct fred_node *) malloc(sizeof(struct
fred_node));
newer_node.fred = Fred(-33); // whatever that means
LIST_INSERT_AFTER(newer_node, new_node, node);

which expands to:

struct fred_node *newer_node = (struct fred_node *) malloc(sizeof(struct
fred_node));
newer_node.fred = Fred(-33); // whatever that means
if ((new_node->node.le_next = newer_node->node.le_next) != NULL)
newer_node->node.le_next->node.le_prev = &new_node->node.le_next;
newer_node->node.le_next = new_node;
new_node->node.le_prev = &new_node;

Well, that's what I came up with. I didn't test anything. Good luck.

 

[Jeff Schwab]

The following code is for list operation. But I can not understand.
Could anyone explain the code for me?

/*
* List definitions.
*/

#define LIST_HEAD(name, type)
struct name {
type *lh_first; /* first element */
}
#define LIST_ENTRY(type)
struct {
type *le_next; /* next element */
type **le_prev; /* address of previous next element */
}

<snip> more of the same </snip>

That's the sort of code people used to write when they wanted to do
generic programming. Awful, isn't it? This is why templates were
introduced to C++.

 

[C++fan]

Hi Jacques:

Thanks a lot.
The code is modified from /sys/queue.h of FreeBSD. Below is the link:
http://fxr.watson.org/fxr/source/sys/queue.h

The original code is from line 328 to 380. But I can not completely
understand it. It is confusing.

Regards,

Jack

This doesn't do anything useful.


Missing semi-colon after struct definition.

Why use a struct?

See above.

I suspect le_prev's comment is wrong. Surely le_prev is the previous
node in the list, not the previous le_next (which is /this/ node).


Looks like an error to me.

This is the same as the original code.

Well there are pointers to both previous and next nodes...


That isn't how macros work. Read a textbook.

They're arguments to a function-style macro. Whoever wrote this doesn't
understand macros, and should be using functions instead.

I agree. I like function. But I have to use it. The three
arguements---listelm, elm and field confuse me.

It is really confusing. What is (elm)->field?

 

[Jacques Labuschagne]

Hi Jacques:

Thanks a lot.
The code is modified from /sys/queue.h of FreeBSD. Below is the link:
http://fxr.watson.org/fxr/source/sys/queue.h

The original code is from line 328 to 380. But I can not completely
understand it. It is confusing.

The slashes at the end of each line are not decoration.
They join lines, so for example
#define MY_MACRO(x) \
((x)*2)
means
#define MY_MACRO(x) ((x)*2)

That's pretty ugly code, but they probably felt they had a good reason
at the time. The struct definitions could be used like this:

typedef LIST_ENTRY(foo) foo_entry;

which the preprocessor would turn into

typedef struct{
struct foo *le_next;
struct foo **le_prev
} foo_entry;

which is perfectly valid C (and C++).

 

[Jacques Labuschagne]

By the way, is there any particular reason you're looking at the BSD
source? Or do you just like the deep end?

Jacques.

 

[Cy Edmunds]

The following code is for list operation. But I can not understand.
Could anyone explain the code for me?

/*
* List definitions.
*/

#define LIST_HEAD(name, type)
struct name {
type *lh_first; /* first element */
}
#define LIST_ENTRY(type)
struct {
type *le_next; /* next element */
type **le_prev; /* address of previous next element */
}

Questions:
Why the struct does not have a name?
Is the list a two-way list?

/*
* List functions.
*/
#define LIST_INIT(head) {
(head)->lh_first = NULL;
}

#define LIST_INSERT_AFTER(listelm, elm, field) {
if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)
(listelm)->field.le_next->field.le_prev =
&(elm)->field.le_next;
(listelm)->field.le_next = (elm);
(elm)->field.le_prev = &(listelm)->field.le_next;
}

Question:
What is listelm, elm, field?

#define LIST_INSERT_HEAD(head, elm, field) {
if (((elm)->field.le_next = (head)->lh_first) != NULL)
(head)->lh_first->field.le_prev =
&(elm)->field.le_next;
(head)->lh_first = (elm);
(elm)->field.le_prev = &(head)->lh_first;
}

Question:

If elm becomes head, what's the purpose of the last sentence:
(elm)->field.le_prev = &(head)->lh_first;


Thanks in advance.

Jack

Here is some tested code. I still hate it.

struct list_node
{
LIST_ENTRY(list_node) node;
int thing;
};

void list_test()
{
LIST_HEAD(t_head, list_node) mylist;
LIST_INIT(&mylist);
list_node *p1 = new list_node;
p1->thing = 24;
LIST_INSERT_HEAD(&mylist, p1, node);
list_node *p2 = new list_node;
p2->thing = -3;
LIST_INSERT_AFTER(p1, p2, node);

list_node *p3 = mylist.lh_first;
while (p3 != 0)
{
std::cout << p3->thing << '\n';
p3 = p3->node.le_next;
}

delete p2;
delete p1;
}

Output is:

24
-3

 

[C++fan]

Hi Cy:

Thank you very much. Your translation makes me understand more. But I
still have questions about your translation. Please look below.
By the way, I do not like the original code. But I have to use it. I
am studying NS2, which uses that code.

Regards,

Jack

Jack, that's quite a puzzle. As a true "C++fan" I hope you won't actually
use crap like this unless you have to! (Hint: std::list)

Anyway, I'm far from sure of this but maybe it is used as follows:

struct fred_node
{
LIST_ENTRY(struct fred_node) node;
Fred fred; // Fred is some arbitrary type -- this is a list of Freds
};

which translates to:

struct fred_node
{
struct {
struct fred_node *le_next; /* next element */
struct fred_node **le_prev; /* address of previous next element */
} node;
Fred fred; // Fred is some arbitrary type -- this is a list of Freds
};

This defines the node type. Then make the list head:

LIST_HEAD(fred_head, struct fred_node) fredlist;
LIST_INIT(fredlist);

which is equivalent to:

struct fred_head {
struct fred_node *lh_first; /* first element */
} fredlist;
fredlist->lh_first = NULL;

Now add a node:

struct fred_node *new_node = (struct fred_node *) malloc(sizeof(struct
fred_node));
new_node.fred = Fred(21); // whatever that means
LIST_INSERT_HEAD(mylist, new_node, node);

which expands to

struct fred_node *new_node = (struct fred_node *) malloc(sizeof(struct
fred_node));
new_node.fred = Fred(21); // whatever that means
if ((new_node->node.le_next = (fredlist)->lh_first) != NULL)
fredlist->lh_first->node.le_prev = &new_node->node.le_next;
fredlist->lh_first = new_node;
new_node->node.le_prev = &new_node;

if ((new_node->node.le_next = (fredlist)->lh_first) != NULL)
It means the head is not NULL, right? So
fredlist->lh_first->node.le_prev should be NULL.
new_node->node.le_next should be NULL, since new_node is a new node.
So what is the meaning of:
fredlist->lh_first->node.le_prev = &new_node->node.le_next;

If head is NULL, (fredlist)->lh_first is NULL. the new_node becomes
the head.
What is the meaning of new_node->node.le_prev = &new_node; ?

Now add another node:

struct fred_node *newer_node = (struct fred_node *) malloc(sizeof(struct
fred_node));
newer_node.fred = Fred(-33); // whatever that means
LIST_INSERT_AFTER(newer_node, new_node, node);

which expands to:

struct fred_node *newer_node = (struct fred_node *) malloc(sizeof(struct
fred_node));
newer_node.fred = Fred(-33); // whatever that means
if ((new_node->node.le_next = newer_node->node.le_next) != NULL)
newer_node->node.le_next->node.le_prev = &new_node->node.le_next;
newer_node->node.le_next = new_node;
new_node->node.le_prev = &new_node;

Since newer_node is a new node, newer_node->node.le_next should be
NULL, right?
newer_node->node.le_next->node.le_prev equals to newer_node itself,
right?

 

[C++fan]

Thanks Jacques. I am studying NS2, which uses that code.

Jack

 

[C++fan]

Thanks Jacques. What is the content of a node? Just two pointers,
le_next and le_prev?

Jack

 

[Jacques Labuschagne]

Thanks Jacques. What is the content of a node? Just two pointers,
le_next and le_prev?

Yes. The LIST_HEAD macro gives you a structure with a pointer to a node,
and the LIST_ENTRY macro gives a struct with those two elements.

Here's an example:

struct my_type{
int value;
};

LIST_HEAD(head, my_type);
typedef LIST_ENTRY(my_type) entry;

After preprocessing this gives us

struct my_type{
int value;
};

struct head{
struct my_type *lh_first;
}
typedef struct{
struct my_type *le_next;
struct my_type **le_prev;
} entry;

 

[Cy Edmunds]

Hi Cy:

Thank you very much. Your translation makes me understand more. But I
still have questions about your translation. Please look below.
By the way, I do not like the original code. But I have to use it. I
am studying NS2, which uses that code.

Regards,

Jack

[snip]

Jack, to tell you the truth I have invested about as much on this as I am
willing to. My suggestion is this: take the example I gave you and expand
all the macro calls manually. Then you will have a C++ program which should
not be too mysterious. Trying to look at the macro code directly would give
anybody a headache.

I figured you didn't like that code very much! As a programmer you do what
you have to do. I just didn't want to give the appearance of somehow
endorsing this monstrosity.

 

[C++fan]

Hi Cy:

I have understood the code now. Pointer is the key. I really appreciate your help.

Sincerely,

Jack