Linked list of object

**Somebody** · Jul 22 '05, 04:58 AM

Re: Linked list of object

Why not just use std::list. It gives you an already written, generic
doubly-linked list.

**Jeff Schwab** · Jul 22 '05, 04:58 AM

Re: Linked list of object

C++fan wrote:[color=blue]
> 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_elemen t = C;
> E->s1.prev_elemen t = B;
> C->s1.prev_elemen t = &(E->s1.next_elemet );
> B->s1.next_elemen t = &(E->s1.next_elemen t);
>
> Are above operation correct?[/color]

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.
[color=blue]
> For the last two sentences, I can also
> write:
> C->s1.prev_elemen t = E;
> B->s1.next_elemen t = E;[/color]

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

No, those pointers have different types.
[color=blue]
> --------------------------------------
> 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?[/color]

No, you still can't do it.
[color=blue]
> 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_elemen t = C;
> E->s1.prev_elemen t = B;
> C->s1.prev_elemen t = &(E->s1.next_elemet );
> B->s1.next_elemen t = &(E->s1.next_elemen t):
>
> Are the above operation orrect?[/color]

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

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

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?
[color=blue]
> If possible, please give your correction.
>
> Thanks a lot.
>
> Jack[/color]

**C++fan** · Jul 22 '05, 04:59 AM

Re: Linked list of object

Jeff Schwab <jeffplus@comca st.net> wrote in message news:<yOmdnTAie vz5jmaiRVn-sw@comcast.com> ...[color=blue]
> C++fan wrote:[color=green]
> > 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_elemen t = C;
> > E->s1.prev_elemen t = B;
> > C->s1.prev_elemen t = &(E->s1.next_elemet );
> > B->s1.next_elemen t = &(E->s1.next_elemen t);
> >
> > Are above operation correct?[/color]
>
> 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.
>[color=green]
> > For the last two sentences, I can also
> > write:
> > C->s1.prev_elemen t = E;
> > B->s1.next_elemen t = E;[/color]
>
> That's much better.
>[color=green]
> > I think &(E->s1.next_elemet )= E, am I right?[/color]
>
> No, those pointers have different types.[/color]

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

[color=blue]
>[color=green]
> > --------------------------------------
> > 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?[/color]
>
> No, you still can't do it.
>[color=green]
> > 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_elemen t = C;
> > E->s1.prev_elemen t = B;
> > C->s1.prev_elemen t = &(E->s1.next_elemet );
> > B->s1.next_elemen t = &(E->s1.next_elemen t):
> >
> > Are the above operation orrect?[/color]
>
> No.
>[color=green]
> > With two new variables added in front of struct st, can I still
> > say that &(E->s1.next_elemet )=E ?[/color]
>
> No.
>[color=green]
> > As long as there is variable infront of struct st, I can not
> > say &(E->s1.next_elemet )=E ?[/color]
>
> 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?
>[/color]

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_elemen t or the address of new_variable1?

The following two expression:
(example_class *)(&(E->s1.next_elemen t))== E
(example_class *)(&new_variabl e1)== E

which one is correct?

Thanks a lot.

Jack

**John Carson** · Jul 22 '05, 05:00 AM

Re: Linked list of object

"C++fan" <jw2000@excite. com> wrote in message
news:15c9b1f2.0 401061429.7d6e8 b5@posting.goog le.com[color=blue]
>
> Thanks for responding.
> What I want to know is the entry address of object E.[/color]

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.
[color=blue]
> Since E->s1.next_elemen t is the first memeber variable, is the
> address of E->s1.next_elemen t same as the address of E?
> Or is E->s1.next_elemen t located in the same memory location as E?
> Can I say that (example_class *)(&(E->s1.next_elemen t))== E ?[/color]

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)

**C++fan** · Jul 22 '05, 05:01 AM

Re: Linked list of object

"John Carson" <donaldquixote@ datafast.net.au > wrote in message news:<3ffbce76@ usenet.per.para dox.net.au>...
[color=blue][color=green]
> > Since E->s1.next_elemen t is the first memeber variable, is the
> > address of E->s1.next_elemen t same as the address of E?
> > Or is E->s1.next_elemen t located in the same memory location as E?
> > Can I say that (example_class *)(&(E->s1.next_elemen t))== E ?[/color]
>
> 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).[/color]

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_elemen t) as the address of the object that E points to,
or as E's content.
But the strange thing is that E->s1.next_elemen t 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_elemen t, 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_elemen t) as the address of the object
that E points to?
This confuses me.

Thanks a lot.

Jack

**John Carson** · Jul 22 '05, 05:02 AM

Re: Linked list of object

"C++fan" <jw2000@excite. com> wrote in message
news:15c9b1f2.0 401071126.5aa02 f09@posting.goo gle.com[color=blue]
> "John Carson" <donaldquixote@ datafast.net.au > wrote in message
> news:<3ffbce76@ usenet.per.para dox.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?[/color]

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.

Built-in / intrinsic / primitive data types, C++ FAQ

http://www.parashift.com/c++-faq-lite/intrinsic-types.html#faq-26.7

[color=blue]
> 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_elemen t) as the address of the object that E points to,
> or as E's content.[/color]

Are you sure that you have interpreted the code correctly? Why would the
code do this rather than just use E?
[color=blue]
> But the strange thing is that E->s1.next_elemen t 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_elemen t, 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_elemen t) as the address of the object
> that E points to?
> This confuses me.[/color]

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)

**C++fan** · Jul 22 '05, 05:04 AM

Re: Linked list of object

"John Carson" <donaldquixote@ datafast.net.au > wrote in message news:<3ffcc02a@ usenet.per.para dox.net.au>...[color=blue]
> "C++fan" <jw2000@excite. com> wrote in message
> news:15c9b1f2.0 401071126.5aa02 f09@posting.goo gle.com[color=green]
> > "John Carson" <donaldquixote@ datafast.net.au > wrote in message
> > news:<3ffbce76@ usenet.per.para dox.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?[/color]
>
> 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
>[color=green]
> > 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_elemen t) as the address of the object that E points to,
> > or as E's content.[/color]
>
> Are you sure that you have interpreted the code correctly? Why would the
> code do this rather than just use E?
>[/color]

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:

Error 500 (Server Error)!!1

http://groups.google.com/groups?dq=&hl=en&lr=&ie=UTF-8&threadm=15c9b1f2.0401042016.4bf1c116%40posting.google.com&prev=/groups%3Fdq%3D%26num%3D25%26hl%3Den%26lr%3D%26ie%3DUTF-8%26group%3Dcomp.lang.c%252B%252B%26start%3D100

[color=blue][color=green]
> > But the strange thing is that E->s1.next_elemen t 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_elemen t, 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_elemen t) as the address of the object
> > that E points to?
> > This confuses me.[/color]
>
>
> 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.[/color]

**John Carson** · Jul 22 '05, 05:05 AM

Re: Linked list of object

"C++fan" <jw2000@excite. com> wrote in message
news:15c9b1f2.0 401081025.2baff 5db@posting.goo gle.com[color=blue]
>
> 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:[/color]

I went to

fxr.watson.org: sys/sys/queue.h

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_HEA D(phead, p1, field);

// insert a node after the first
Node *p2 = new Node;
p2->txt = "Inserted after the first\n";
LIST_INSERT_AFT ER(p1, p2, field);

// insert a node before the node just inserted,
Node *p3 = new Node;
p3->txt = "Inserted inbetween\n";
LIST_INSERT_BEF ORE(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_nex t = phead->lh_first) != 0)
phead->lh_first->field.le_pre v = &p1->field.le_nex t;

phead->lh_first = p1;
p1->field.le_pre v = &phead->lh_first;
} while (0);

Node *p2 = new Node;
p2->txt = "Inserted after the first\n";
do {
if ((p2->field.le_nex t = p1->field.le_nex t) != 0)
p1->field.le_nex t->field.le_pre v = &p2->field.le_nex t;

p1->field.le_nex t = p2;
p2->field.le_pre v = &p1->field.le_nex t;
} while (0);

Node *p3 = new Node;
p3->txt = "Inserted inbetween\n";
do {
p3->field.le_pre v = p2->field.le_pre v;
p3->field.le_nex t = p2;
*p2->field.le_pre v = p3;
p2->field.le_pre v = &p3->field.le_nex t;
} while (0);

Node *p;
for (p = phead->lh_first; p; p = p->field.le_nex t)
cout << p->txt;
do {
if (p3->field.le_nex t != 0)
p3->field.le_nex t->field.le_pre v = p3->field.le_pre v;

*p3->field.le_pre v = p3->field.le_nex t;
} while (0);

cout << '\n';
for (p = phead->lh_first; p; p = p->field.le_nex t)
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_nex t = phead->lh_first) != 0)
phead->lh_first->field.le_pre v = &p1->field.le_nex t;

phead->lh_first = p1;
p1->field.le_pre v = &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
"InitialFir st". 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_nex t = 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_nex t
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_pre v = &p1->field.le_nex t;

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_pre v = &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_pre v = p2->field.le_pre v;
p3->field.le_nex t = p2;
*p2->field.le_pre v = p3;
p2->field.le_pre v = &p3->field.le_nex t;
///////////////////////////////////////////////////

Consider the assignments in order. First:

p3->field.le_pre v = p2->field.le_pre v;

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_nex t = 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_pre v = p3;

p2->field.le_pre v 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_pre v = &p3->field.le_nex t;

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)

**C++fan** · Jul 22 '05, 05:06 AM

Re: Linked list of object

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.l e_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" <donaldquixote@ datafast.net.au > wrote in message news:<3ffe5e0f@ usenet.per.para dox.net.au>...[color=blue]
> "C++fan" <jw2000@excite. com> wrote in message
> news:15c9b1f2.0 401081025.2baff 5db@posting.goo gle.com[color=green]
> >
> > 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:[/color]
>
> 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_HEA D(phead, p1, field);
>
> // insert a node after the first
> Node *p2 = new Node;
> p2->txt = "Inserted after the first\n";
> LIST_INSERT_AFT ER(p1, p2, field);
>
> // insert a node before the node just inserted,
> Node *p3 = new Node;
> p3->txt = "Inserted inbetween\n";
> LIST_INSERT_BEF ORE(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_nex t = phead->lh_first) != 0)
> phead->lh_first->field.le_pre v = &p1->field.le_nex t;
>
> phead->lh_first = p1;
> p1->field.le_pre v = &phead->lh_first;
> } while (0);
>
> Node *p2 = new Node;
> p2->txt = "Inserted after the first\n";
> do {
> if ((p2->field.le_nex t = p1->field.le_nex t) != 0)
> p1->field.le_nex t->field.le_pre v = &p2->field.le_nex t;
>
> p1->field.le_nex t = p2;
> p2->field.le_pre v = &p1->field.le_nex t;
> } while (0);
>
> Node *p3 = new Node;
> p3->txt = "Inserted inbetween\n";
> do {
> p3->field.le_pre v = p2->field.le_pre v;
> p3->field.le_nex t = p2;
> *p2->field.le_pre v = p3;
> p2->field.le_pre v = &p3->field.le_nex t;
> } while (0);
>
> Node *p;
> for (p = phead->lh_first; p; p = p->field.le_nex t)
> cout << p->txt;
> do {
> if (p3->field.le_nex t != 0)
> p3->field.le_nex t->field.le_pre v = p3->field.le_pre v;
>
> *p3->field.le_pre v = p3->field.le_nex t;
> } while (0);
>
> cout << '\n';
> for (p = phead->lh_first; p; p = p->field.le_nex t)
> 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_nex t = phead->lh_first) != 0)
> phead->lh_first->field.le_pre v = &p1->field.le_nex t;
>
> phead->lh_first = p1;
> p1->field.le_pre v = &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
> "InitialFir st". 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_nex t = 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_nex t
> 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_pre v = &p1->field.le_nex t;
>
> 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_pre v = &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_pre v = p2->field.le_pre v;
> p3->field.le_nex t = p2;
> *p2->field.le_pre v = p3;
> p2->field.le_pre v = &p3->field.le_nex t;
> ///////////////////////////////////////////////////
>
> Consider the assignments in order. First:
>
> p3->field.le_pre v = p2->field.le_pre v;
>
> 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_nex t = 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_pre v = p3;
>
> p2->field.le_pre v 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_pre v = &p3->field.le_nex t;
>
> 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.[/color]

**John Carson** · Jul 22 '05, 05:06 AM

Re: Linked list of object

"C++fan" <jw2000@excite. com> wrote in message
news:15c9b1f2.0 401091153.1ceee fda@posting.goo gle.com[color=blue]
> 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.l e_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?[/color]

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

p3->field.le_pre v = &(p1->field.le_nex t)

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_pre v, we have the address of p1->field.le_nex t. 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_nex t is the same as
the address of p1->field. Thus we can use this address to get
p1->field.le_pre v. Now, p1->field.le_pre v will store the address of
p0->field.le_nex t. 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 .
[color=blue]
> By the way, according to your expertise, what's the advantage of
> implement a linked list as that code does?[/color]

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)

**C++fan** · Jul 22 '05, 05:07 AM

Re: Linked list of object

Thanks.

Jack

"John Carson" <donaldquixote@ datafast.net.au > wrote in message news:<3fff4be5@ usenet.per.para dox.net.au>...[color=blue]
> "C++fan" <jw2000@excite. com> wrote in message
> news:15c9b1f2.0 401091153.1ceee fda@posting.goo gle.com[color=green]
> > 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.l e_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?[/color]
>
> You have the -> and . in the wrong places. p3 and p1 are pointers, and field
> is an object, so it is
>
> p3->field.le_pre v = &(p1->field.le_nex t)
>
> 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_pre v, we have the address of p1->field.le_nex t. 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_nex t is the same as
> the address of p1->field. Thus we can use this address to get
> p1->field.le_pre v. Now, p1->field.le_pre v will store the address of
> p0->field.le_nex t. 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 .
>[color=green]
> > By the way, according to your expertise, what's the advantage of
> > implement a linked list as that code does?[/color]
>
> 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.[/color]

Linked list of object

Linked list of object

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment