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

Linked list of object

P: n/a
Suppose that I define the following class:

class example_class{

public:
example_class();
void funtion_1();
void function_2();

protected:
struct st {
example_class *next_element;
example_class *prev_element;
} s1;

int variable_1;
double variable_2;

private:
int *variable_3;
}

Then I create four objects:
example_class *A;
example_class *B;
example_class *C;
example_class *D;

And link them togother as a linked list: A-B-C-D.
Then I create a new object E and want to insert E before C.
Below is what I do:

example_class *E;

E->s1.next_element = C;
E->s1.prev_element = B;
C->s1.prev_element = &(E->s1.next_elemet);
B->s1.next_element = &(E->s1.next_element);

Are above operation correct? For the last two sentences, I can also
write:
C->s1.prev_element = E;
B->s1.next_element = E;
I think &(E->s1.next_elemet)= E, am I right?

--------------------------------------
Below is another situation:
I modify the defination of example_class to be:

class example_class{

public:
example_class();
void funtion_1();
void function_2();

double new_variable1; //I add two variables
int new_variable2; // in front of the strust st.
protected:
struct st {
example_class *next_element;
example_class *prev_element;
} s1;

int variable_1;
double variable_2;

private:
int *variable_3;
}

After I add two new variables in front of struct st, can I still do
the same operation as above example? That is:

With a linked list: A-B-C-D same as above.
Then I create a new object E and want to insert E before C.
Below is what I do:

example_class *E;

E->s1.next_element = C;
E->s1.prev_element = B;
C->s1.prev_element = &(E->s1.next_elemet);
B->s1.next_element = &(E->s1.next_element):

Are the above operation correct?
With two new variables added in front of struct st, can I still
say that &(E->s1.next_elemet)=E ?
As long as there is variable infront of struct st, I can not
say &(E->s1.next_elemet)=E ?
If possible, please give your correction.

Thanks a lot.

Jack
Jul 22 '05 #1
Share this Question
Share on Google+
11 Replies


P: n/a
Why not just use std::list. It gives you an already written, generic
doubly-linked list.
Jul 22 '05 #2

P: n/a
C++fan wrote:
Suppose that I define the following class:

class example_class{

public:
example_class();
void funtion_1();
void function_2();

protected:
struct st {
example_class *next_element;
example_class *prev_element;
} s1;

int variable_1;
double variable_2;

private:
int *variable_3;
}

Then I create four objects:
example_class *A;
example_class *B;
example_class *C;
example_class *D;

And link them togother as a linked list: A-B-C-D.
Then I create a new object E and want to insert E before C.
Below is what I do:

example_class *E;

E->s1.next_element = C;
E->s1.prev_element = B;
C->s1.prev_element = &(E->s1.next_elemet);
B->s1.next_element = &(E->s1.next_element);

Are above operation correct?
No. Aside from the typo, you're assigning a "pointer to pointer to
example_class" to a "pointer to example_class." Your compiler should be
telling you about this.
For the last two sentences, I can also
write:
C->s1.prev_element = E;
B->s1.next_element = E;
That's much better.
I think &(E->s1.next_elemet)= E, am I right?
No, those pointers have different types.
--------------------------------------
Below is another situation:
I modify the defination of example_class to be:

class example_class{

public:
example_class();
void funtion_1();
void function_2();

double new_variable1; //I add two variables
int new_variable2; // in front of the strust st.
protected:
struct st {
example_class *next_element;
example_class *prev_element;
} s1;

int variable_1;
double variable_2;

private:
int *variable_3;
}

After I add two new variables in front of struct st, can I still do
the same operation as above example?
No, you still can't do it.
That is:

With a linked list: A-B-C-D same as above.
Then I create a new object E and want to insert E before C.
Below is what I do:

example_class *E;

E->s1.next_element = C;
E->s1.prev_element = B;
C->s1.prev_element = &(E->s1.next_elemet);
B->s1.next_element = &(E->s1.next_element):

Are the above operation orrect?
No.
With two new variables added in front of struct st, can I still
say that &(E->s1.next_elemet)=E ?
No.
As long as there is variable infront of struct st, I can not
say &(E->s1.next_elemet)=E ?
No, even if those pointers contain the same address (I'm not sure
whether that's required), you've got a type mismatch. By the way,
that's the fifth time you've made the same typo... Am I missing something?
If possible, please give your correction.

Thanks a lot.

Jack


Jul 22 '05 #3

P: n/a
Jeff Schwab <je******@comcast.net> wrote in message news:<yO********************@comcast.com>...
C++fan wrote:
Suppose that I define the following class:

class example_class{

public:
example_class();
void funtion_1();
void function_2();

protected:
struct st {
example_class *next_element;
example_class *prev_element;
} s1;

int variable_1;
double variable_2;

private:
int *variable_3;
}

Then I create four objects:
example_class *A;
example_class *B;
example_class *C;
example_class *D;

And link them togother as a linked list: A-B-C-D.
Then I create a new object E and want to insert E before C.
Below is what I do:

example_class *E;

E->s1.next_element = C;
E->s1.prev_element = B;
C->s1.prev_element = &(E->s1.next_elemet);
B->s1.next_element = &(E->s1.next_element);

Are above operation correct?
No. Aside from the typo, you're assigning a "pointer to pointer to
example_class" to a "pointer to example_class." Your compiler should be
telling you about this.
For the last two sentences, I can also
write:
C->s1.prev_element = E;
B->s1.next_element = E;


That's much better.
I think &(E->s1.next_elemet)= E, am I right?


No, those pointers have different types.


Thanks for responding.
What I want to know is the entry address of object E.
Since E->s1.next_element is the first memeber variable, is the
address of E->s1.next_element same as the address of E?
Or is E->s1.next_element located in the same memory location as E?
Can I say that (example_class *)(&(E->s1.next_element))== E ?
--------------------------------------
Below is another situation:
I modify the defination of example_class to be:

class example_class{

public:
example_class();
void funtion_1();
void function_2();

double new_variable1; //I add two variables
int new_variable2; // in front of the strust st.
protected:
struct st {
example_class *next_element;
example_class *prev_element;
} s1;

int variable_1;
double variable_2;

private:
int *variable_3;
}

After I add two new variables in front of struct st, can I still do
the same operation as above example?


No, you still can't do it.
That is:

With a linked list: A-B-C-D same as above.
Then I create a new object E and want to insert E before C.
Below is what I do:

example_class *E;

E->s1.next_element = C;
E->s1.prev_element = B;
C->s1.prev_element = &(E->s1.next_elemet);
B->s1.next_element = &(E->s1.next_element):

Are the above operation orrect?


No.
With two new variables added in front of struct st, can I still
say that &(E->s1.next_elemet)=E ?


No.
As long as there is variable infront of struct st, I can not
say &(E->s1.next_elemet)=E ?


No, even if those pointers contain the same address (I'm not sure
whether that's required), you've got a type mismatch. By the way,
that's the fifth time you've made the same typo... Am I missing something?


After adding two variable in front of struct st, has the entry address
of object E been changed? The entry address of object E is the
address of E->s1.next_element or the address of new_variable1?

The following two expression:
(example_class *)(&(E->s1.next_element))== E
(example_class *)(&new_variable1)== E

which one is correct?

Thanks a lot.

Jack
Jul 22 '05 #4

P: n/a
"C++fan" <jw****@excite.com> wrote in message
news:15*************************@posting.google.co m

Thanks for responding.
What I want to know is the entry address of object E.
E is not an object, it is a pointer to an object. I suggest that you change
the way you name variables so as to make this distinction clear, e.g., E for
the object and pE for the pointer to the object.

Sticking with your unfortunate notation for the moment, the address of the
object pointed to by E is E itself. A pointer is simply a variable that
stores an address. So E will have some value (e.g., 0x0012fabc) and this
value will be the address of the object to which E points.

The address (or location) of E is something quite different. The pointer E
will occupy (usually) 4 bytes of memory and these 4 bytes could be
anywhere --- they don't need to be anywhere near the object that E points
to. Written in those 4 bytes will be the location (address) of the object
pointed to. That is the only connection between the pointer and the object
pointed to.
Since E->s1.next_element is the first memeber variable, is the
address of E->s1.next_element same as the address of E?
Or is E->s1.next_element located in the same memory location as E?
Can I say that (example_class *)(&(E->s1.next_element))== E ?


Again, you seem to be fundamentally confused between a pointer and the
object it points to. You have a pointer on the right-hand side, but an
object on the left-hand side. E could be at, say, address 58790 and the
object pointed to could be at, say, address 7987987.

If your question is: is the address of the first data member of a class
object necessarily the same as the address of the class object itself, then
the answer is no. The answer is yes for POD structs (basically C style
structs).

You should not normally need to bother with the address of data members.
Given an object, X, its address is &X. Given a pointer to X, pX, the address
of X is pX.
--
John Carson
1. To reply to email address, remove donald
2. Don't reply to email address (post here instead)

Jul 22 '05 #5

P: n/a
"John Carson" <do***********@datafast.net.au> wrote in message news:<3f******@usenet.per.paradox.net.au>...
Since E->s1.next_element is the first memeber variable, is the
address of E->s1.next_element same as the address of E?
Or is E->s1.next_element located in the same memory location as E?
Can I say that (example_class *)(&(E->s1.next_element))== E ?


Again, you seem to be fundamentally confused between a pointer and the
object it points to. You have a pointer on the right-hand side, but an
object on the left-hand side. E could be at, say, address 58790 and the
object pointed to could be at, say, address 7987987.

If your question is: is the address of the first data member of a class
object necessarily the same as the address of the class object itself, then
the answer is no. The answer is yes for POD structs (basically C style
structs).


Thanks John. That is exactly what I want to know. A class object can
also be a POD, right? If it is, is the answer yes?
I am studying a code (NS2), which use the mechanism that I described
here to operate a linked list of object. That is, using
&(E->s1.next_element) as the address of the object that E points to,
or as E's content.
But the strange thing is that E->s1.next_element is not the first data
memeber of the class object. In the defination of the class, there are
two data memebers defined infront of E->s1.next_element, just as the
example that I give
here. Below is the defination, which has similiar structure as the
class defined in the code (NS2):

class example_class{

public:
example_class();
void funtion_1();
void function_2();

double new_variable1; //Two variables are defined
int new_variable2; // in front of the strust st.
protected:
struct st {
example_class *next_element;
example_class *prev_element;
} s1;

int variable_1;
double variable_2;

private:
int *variable_3;
}

With two public data members defined in front of struct st, is it
possible to use &(E->s1.next_element) as the address of the object
that E points to?
This confuses me.

Thanks a lot.

Jack
Jul 22 '05 #6

P: n/a
"C++fan" <jw****@excite.com> wrote in message
news:15**************************@posting.google.c om
"John Carson" <do***********@datafast.net.au> wrote in message
news:<3f******@usenet.per.paradox.net.au>...
Thanks John. That is exactly what I want to know. A class object can
also be a POD, right? If it is, is the answer yes?
My answer would be yes to both questions.

The definition of a POD in the standard is complicated. The following from
the C++ FAQ is simpler.

http://www.parashift.com/c++-faq-lit....html#faq-26.7
I am studying a code (NS2), which use the mechanism that I described
here to operate a linked list of object. That is, using
&(E->s1.next_element) as the address of the object that E points to,
or as E's content.
Are you sure that you have interpreted the code correctly? Why would the
code do this rather than just use E?
But the strange thing is that E->s1.next_element is not the first data
memeber of the class object. In the defination of the class, there are
two data memebers defined infront of E->s1.next_element, just as the
example that I give
here. Below is the defination, which has similiar structure as the
class defined in the code (NS2):

class example_class{

public:
example_class();
void funtion_1();
void function_2();

double new_variable1; //Two variables are defined
int new_variable2; // in front of the strust st.
protected:
struct st {
example_class *next_element;
example_class *prev_element;
} s1;

int variable_1;
double variable_2;

private:
int *variable_3;
}

With two public data members defined in front of struct st, is it
possible to use &(E->s1.next_element) as the address of the object
that E points to?
This confuses me.

Assuming that you have correctly interpreted the code (about which I am
sceptical), this strikes me as very poor coding. Basically, you have a
non-POD class (not all members are public) so anything goes.

Section 9.2, p12 of the standard says:

"Nonstatic data members of a (non-union) class declared without an
intervening access-specifier are allocated so that later members have higher
addresses within a class object. The order of allocation of nonstatic data
members separated by an access-specifier is unspecified (11.1)."

Since the first two variables and the struct are separated by an access
specifier (i.e., "protected"), the order in which the two variables and the
struct appear is unspecified. It would thus appear that the code is
exploiting an implementation-specific feature that makes the protected
variables come first.

--
John Carson
1. To reply to email address, remove donald
2. Don't reply to email address (post here instead)

Jul 22 '05 #7

P: n/a
"John Carson" <do***********@datafast.net.au> wrote in message news:<3f******@usenet.per.paradox.net.au>...
"C++fan" <jw****@excite.com> wrote in message
news:15**************************@posting.google.c om
"John Carson" <do***********@datafast.net.au> wrote in message
news:<3f******@usenet.per.paradox.net.au>...
Thanks John. That is exactly what I want to know. A class object can
also be a POD, right? If it is, is the answer yes?


My answer would be yes to both questions.

The definition of a POD in the standard is complicated. The following from
the C++ FAQ is simpler.

http://www.parashift.com/c++-faq-lit....html#faq-26.7
I am studying a code (NS2), which use the mechanism that I described
here to operate a linked list of object. That is, using
&(E->s1.next_element) as the address of the object that E points to,
or as E's content.


Are you sure that you have interpreted the code correctly? Why would the
code do this rather than just use E?


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:
http://groups.google.com/groups?dq=&...%26start%3D100

But the strange thing is that E->s1.next_element is not the first data
memeber of the class object. In the defination of the class, there are
two data memebers defined infront of E->s1.next_element, just as the
example that I give
here. Below is the defination, which has similiar structure as the
class defined in the code (NS2):

class example_class{

public:
example_class();
void funtion_1();
void function_2();

double new_variable1; //Two variables are defined
int new_variable2; // in front of the strust st.
protected:
struct st {
example_class *next_element;
example_class *prev_element;
} s1;

int variable_1;
double variable_2;

private:
int *variable_3;
}

With two public data members defined in front of struct st, is it
possible to use &(E->s1.next_element) as the address of the object
that E points to?
This confuses me.

Assuming that you have correctly interpreted the code (about which I am
sceptical), this strikes me as very poor coding. Basically, you have a
non-POD class (not all members are public) so anything goes.

Section 9.2, p12 of the standard says:

"Nonstatic data members of a (non-union) class declared without an
intervening access-specifier are allocated so that later members have higher
addresses within a class object. The order of allocation of nonstatic data
members separated by an access-specifier is unspecified (11.1)."

Since the first two variables and the struct are separated by an access
specifier (i.e., "protected"), the order in which the two variables and the
struct appear is unspecified. It would thus appear that the code is
exploiting an implementation-specific feature that makes the protected
variables come first.

Jul 22 '05 #8

P: n/a
"C++fan" <jw****@excite.com> wrote in message
news:15**************************@posting.google.c om

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.
--
John Carson
1. To reply to email address, remove donald
2. Don't reply to email address (post here instead)

Jul 22 '05 #9

P: n/a
Hi John:

Thank you very much! I really understand now. I have saved your post
for future reference.
When I studied that code, the struct that I used is:
struct Node
{
LIST_ENTRY(Node) field;
const char* txt;
} node1;

So, &(node1) == &(node1.field.le_next).
So it confused me for the situation of linked list of class object.

The drawback of that code is that the linked list created is not
two-way linked list, right? For instance, if the list is p1-p3-p2,
which is the same as your example, then p3.field->le_prev =
&(p1.field->next). So p3 can not access p1's data member. Am I right?

By the way, according to your expertise, what's the advantage of
implement a linked list as that code does?

Regards,

Jack
"John Carson" <do***********@datafast.net.au> wrote in message news:<3f******@usenet.per.paradox.net.au>...
"C++fan" <jw****@excite.com> wrote in message
news:15**************************@posting.google.c om

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.

Jul 22 '05 #10

P: n/a
"C++fan" <jw****@excite.com> wrote in message
news:15**************************@posting.google.c om
Hi John:

Thank you very much! I really understand now. I have saved your post
for future reference.
When I studied that code, the struct that I used is:
struct Node
{
LIST_ENTRY(Node) field;
const char* txt;
} node1;

So, &(node1) == &(node1.field.le_next).
So it confused me for the situation of linked list of class object.

The drawback of that code is that the linked list created is not
two-way linked list, right? For instance, if the list is p1-p3-p2,
which is the same as your example, then p3.field->le_prev =
&(p1.field->next). So p3 can not access p1's data member. Am I right?
You have the -> and . in the wrong places. p3 and p1 are pointers, and field
is an object, so it is

p3->field.le_prev = &(p1->field.le_next)

As for p3 accessing p1's data member, it is possible to do it indirectly.
Suppose we have

p0-p1-p3-p2

In p3->field.le_prev, we have the address of p1->field.le_next. Now, because
field is a POD (even if it is embedded in a structure that is not) and
le_next is its first member, the address of p1->field.le_next is the same as
the address of p1->field. Thus we can use this address to get
p1->field.le_prev. Now, p1->field.le_prev will store the address of
p0->field.le_next. By dereferencing this address, we can get the address of
p1 and from that we can get p1's data member. The argument is similar if p1
is preceded by phead rather than p0 .
By the way, according to your expertise, what's the advantage of
implement a linked list as that code does?


It is a peculiar type of linked list. Normally when you have a linked list
with two pointers, one points to the next node and one points to the
previous node. Just why this form would be chosen over the more normal form
is a mystery to me.

The advantage of this form of linked list over a linked list with only a
single pointer per node (pointing to the next node) is, however, clear.
With this form, if you have the address of a single node, then you can
delete the node or add another node either before it or after it. This is
because storing the address of the le_next pointer from the preceding node
means that the value of the le_next pointer in that preceding node can be
changed to point to a new node.

If, by contrast, you had a linked list in which each node had only a single
pointer, then there is no way, starting from a given node, that you could
affect the pointer value in the preceding node. This means that if you want
to either insert or remove a pointer in the middle of the list, you have to
traverse the list from the start and, at each step, store the address of the
preceding node in a scratch variable so that the pointer from that node can
be changed when the traversal reaches the target node.
--
John Carson
1. To reply to email address, remove donald
2. Don't reply to email address (post here instead)

Jul 22 '05 #11

P: n/a
Thanks.

Jack

"John Carson" <do***********@datafast.net.au> wrote in message news:<3f******@usenet.per.paradox.net.au>...
"C++fan" <jw****@excite.com> wrote in message
news:15**************************@posting.google.c om
Hi John:

Thank you very much! I really understand now. I have saved your post
for future reference.
When I studied that code, the struct that I used is:
struct Node
{
LIST_ENTRY(Node) field;
const char* txt;
} node1;

So, &(node1) == &(node1.field.le_next).
So it confused me for the situation of linked list of class object.

The drawback of that code is that the linked list created is not
two-way linked list, right? For instance, if the list is p1-p3-p2,
which is the same as your example, then p3.field->le_prev =
&(p1.field->next). So p3 can not access p1's data member. Am I right?


You have the -> and . in the wrong places. p3 and p1 are pointers, and field
is an object, so it is

p3->field.le_prev = &(p1->field.le_next)

As for p3 accessing p1's data member, it is possible to do it indirectly.
Suppose we have

p0-p1-p3-p2

In p3->field.le_prev, we have the address of p1->field.le_next. Now, because
field is a POD (even if it is embedded in a structure that is not) and
le_next is its first member, the address of p1->field.le_next is the same as
the address of p1->field. Thus we can use this address to get
p1->field.le_prev. Now, p1->field.le_prev will store the address of
p0->field.le_next. By dereferencing this address, we can get the address of
p1 and from that we can get p1's data member. The argument is similar if p1
is preceded by phead rather than p0 .
By the way, according to your expertise, what's the advantage of
implement a linked list as that code does?


It is a peculiar type of linked list. Normally when you have a linked list
with two pointers, one points to the next node and one points to the
previous node. Just why this form would be chosen over the more normal form
is a mystery to me.

The advantage of this form of linked list over a linked list with only a
single pointer per node (pointing to the next node) is, however, clear.
With this form, if you have the address of a single node, then you can
delete the node or add another node either before it or after it. This is
because storing the address of the le_next pointer from the preceding node
means that the value of the le_next pointer in that preceding node can be
changed to point to a new node.

If, by contrast, you had a linked list in which each node had only a single
pointer, then there is no way, starting from a given node, that you could
affect the pointer value in the preceding node. This means that if you want
to either insert or remove a pointer in the middle of the list, you have to
traverse the list from the start and, at each step, store the address of the
preceding node in a scratch variable so that the pointer from that node can
be changed when the traversal reaches the target node.

Jul 22 '05 #12

This discussion thread is closed

Replies have been disabled for this discussion.