C++fan said:
Thanks John. If possible, please look at my post at 1/4/2004, which
describes the mechanism that the code uses to implement linked list of
object. Below is the link:
I went to
http://fxr.watson.org/fxr/source/sys/queue.h
and copied lines 311-380. Drawing on Cy Edmunds heroic efforts to make sense
of this horrendous code, I produced the following program:
////////////////////////////////////////////////////////////////
#include <cstdlib>
#include <iostream>
using std::cout;
/* lines 311-380 from your link, then: */
// notice how in this struct definition, the pointers generated by
// LIST_ENTRY are NOT at the beginning of Node
struct Node
{
const char* txt;
LIST_ENTRY(Node) field;
};
int main()
{
// Define the structure for the head of the list
// and create an instance of it
LIST_HEAD(Head, Node) head;
// Define a pointer to the head of the list
// and call it phead
Head * phead = &head;
LIST_INIT(phead);
// insert a node at the start of the list
Node *p1 = new Node;
p1->txt = "Inserted at head\n";
LIST_INSERT_HEAD(phead, p1, field);
// insert a node after the first
Node *p2 = new Node;
p2->txt = "Inserted after the first\n";
LIST_INSERT_AFTER(p1, p2, field);
// insert a node before the node just inserted,
Node *p3 = new Node;
p3->txt = "Inserted inbetween\n";
LIST_INSERT_BEFORE(p2, p3, field);
/* The order should now be:
1. "Inserted at head\n"
2. "Inserted inbetween\n"
3. "Inserted after the first\n"
*/
// output the list contents
Node *p;
LIST_FOREACH(p, phead, field)
cout << p->txt;
// remove the item inserted in the middle
LIST_REMOVE(p3, field);
// output the list contents again
cout << '\n';
LIST_FOREACH(p, phead, field)
cout << p->txt;
}
////////////////////////////////////////
The above code works as expected to produce an output:
Inserted at head
Inserted inbetween
Inserted after the first
Inserted at head
Inserted after the first
One of the nice things that VC++ will do is produce the output from the
preprocessor. Using this facility on the above code, yields the following
(after removal of redundant bracketting generated by the macros).
///////////////////////////////////////////////////
#include <cstdlib>
#include <iostream>
using std::cout;
struct Node
{
const char* txt;
struct
{
struct Node *le_next;
struct Node **le_prev;
} field;
};
int main()
{
struct Head
{
struct Node *lh_first;
} head;
Head * phead = &head;
do {
phead->lh_first = 0;
} while (0);
Node *p1 = new Node;
p1->txt = "Inserted at head\n";
do {
if ((p1->field.le_next = phead->lh_first) != 0)
phead->lh_first->field.le_prev = &p1->field.le_next;
phead->lh_first = p1;
p1->field.le_prev = &phead->lh_first;
} while (0);
Node *p2 = new Node;
p2->txt = "Inserted after the first\n";
do {
if ((p2->field.le_next = p1->field.le_next) != 0)
p1->field.le_next->field.le_prev = &p2->field.le_next;
p1->field.le_next = p2;
p2->field.le_prev = &p1->field.le_next;
} while (0);
Node *p3 = new Node;
p3->txt = "Inserted inbetween\n";
do {
p3->field.le_prev = p2->field.le_prev;
p3->field.le_next = p2;
*p2->field.le_prev = p3;
p2->field.le_prev = &p3->field.le_next;
} while (0);
Node *p;
for (p = phead->lh_first; p; p = p->field.le_next)
cout << p->txt;
do {
if (p3->field.le_next != 0)
p3->field.le_next->field.le_prev = p3->field.le_prev;
*p3->field.le_prev = p3->field.le_next;
} while (0);
cout << '\n';
for (p = phead->lh_first; p; p = p->field.le_next)
cout << p->txt;
return 0;
}
/////////////////////////////////////////////////////////////
If you study this code, you will see that it nowhere makes use of the
equality of the address of a struct member and the address of the struct
object that contains it. Accordingly, the internal placement of struct
members is irrelevant.
In analysing the assignments, it is important to note that le_next is a
pointer to Node, whereas le_prev is a pointer to pointer to Node (a "double
pointer"). le_next is supposed to store the address of the next node in the
list, whereas le_prev is supposed to store the address of the le_next
pointer in the preceding node (if there is one --- otherwise le_prev stores
the address of the lh_first pointer in head).
Consider the assignments within the second do loop:
/////////////////////////////////////////////////
if ((p1->field.le_next = phead->lh_first) != 0)
phead->lh_first->field.le_prev = &p1->field.le_next;
phead->lh_first = p1;
p1->field.le_prev = &phead->lh_first;
//////////////////////////////////////////////////
Now the way this works is as follows. The list may already have one or more
nodes. If it does, denote the first node (before any insertion is made) by
"InitialFirst". Denote the node that is being inserted by "NewFirst" (it is
pointed to by p1). After the insertion, the first node in the list will be
NewFirst, with InitialFirst becoming the second node, i.e., we start with
head -> InitialFirst
and we end up with
head -> NewFirst -> InitialFirst
The way this is suppose to work is that
1. lh_first from head will point to NewFirst,
2. le_prev from NewFirst will store the address of lh_first from
head (head being the equivalent of a previous node for present purposes).
Note that le_prev is a pointer to pointer, so it is appropriate that we take
the address of the lh_first pointer.
3. le_next from NewFirst will point to InitialFirst, which is the next node
in the list,
4. le_prev from InitialFirst will store the address of le_next from
NewFirst, which is the previous node in the list.
Consider the first assignment (inside the if() test)
p1->field.le_next = phead->lh_first
phead->lh_first on the right-hand side (RHS for brevity) has not been
changed from its initial value at this stage and thus points to InitialFirst
or is zero if the list is empty. The assignment of this to p1->field.le_next
means that le_next in NewFirst will point to InitialFirst (le_next will
become zero if the list was empty), thus satisfying 3.
In the event that the list was not empty (i.e., InitalFirst actually
exists), we do the second assignment
phead->lh_first->field.le_prev = &p1->field.le_next;
We still haven't altered phead->lh_first, so it still points to
InitialFirst. Accordingly, the left-hand side (LHS for brevity) is the
le_prev pointer from InitialFirst. We assign to this le_prev pointer the
address of the le_next pointer in NewFirst, thus satisfying 4.
Now consider the third assignment:
phead->lh_first = p1;
Here we do finally change phead->lh_first by assigning to it the address of
NewFirst, thus
satisfying 1.
Finally, consider the last assignment
p1->field.le_prev = &phead->lh_first;
This makes le_prev in NewFirst store the address of the lh_first pointer
in head, thus satisfying 2.
Thus we see that 1-4 are all satisfied.
The analysis of the third do loop is just like that of the second, except
that the NewFirst node pointed to by p1 now plays the role previously played
by head, and the newly inserted node pointed to by p2 now plays the role
previously played by NewFirst.
The fourth do loop is a little different. Here we are inserting inbetween
two nodes, those pointed to by p1 and p2. Call them InitialFirst and
InitialSecond. The inserted node is pointed to by p3 and will be denoted by
NewMiddle. We start with
InitialFirst -> InitialSecond
and end up with
InitialFirst -> NewMiddle -> InitialSecond
The way this is suppose to work is that
1. le_next from InitialFirst will point to NewMiddle,
2. le_prev from NewMiddle will store the address of le_next from
InitialFirst,
3. le_next from NewMiddle will point to InitialSecond,
4. le_prev from InitialSecond will store the address of le_next from
NewMiddle.
The assignments in the do loop are:
/////////////////////////////////////////////////
p3->field.le_prev = p2->field.le_prev;
p3->field.le_next = p2;
*p2->field.le_prev = p3;
p2->field.le_prev = &p3->field.le_next;
///////////////////////////////////////////////////
Consider the assignments in order. First:
p3->field.le_prev = p2->field.le_prev;
On the RHS, we have the le_prev value from InitialSecond. This will be the
address of le_next from InitialFirst. This is being assigned to the le_prev
value of NewMiddle, thus satisfying 2.
Next, we have:
p3->field.le_next = p2;
The RHS is the address of InitialSecond. This is being stored in le_next of
NewMiddle, thus satisfying 3.
The third assignment is:
*p2->field.le_prev = p3;
p2->field.le_prev has not been altered by previous assignments. As the
le_prev field of InitialSecond, it stores the address of le_next from
InitialFirst. By dereferencing it, we are making an assignment to le_next
from InitialFirst, setting it equal to the address of NewMiddle, thus
satisfying 1.
The last assignment is:
p2->field.le_prev = &p3->field.le_next;
This makes le_prev in InitialSecond store the address of le_next in
NewMiddle, thus satisfying 4.
Thus we see that 1-4 are all satisfied.
The assignments in the remainder of the code are left as an exercise for the
reader.
