queue.h - LIST - le_prev

[samuncle09]

#define LIST_ENTRY(type) \
struct { \
struct type *le_next; /* next element */ \
struct type **le_prev; /* address of previous next element */ \
}

Could someone please tell me why the "le_prev" points to "address of previous next element" instead of the previous element?

Thank you very much!

[wje_lf]

It depends on what you mean by "because".

struct type xxx is the struct itself, with all its parts.

struct type *xxx is a pointer to the struct.

struct type **xxx is a pointer to a pointer to the struct; that is, it's the address of the pointer to the struct.

Now, you might be saying, "Yeah, yeah, yeah, I know all that. But why do they do it that way?"

The reason they would do it that way is to make it fairly easy to remove an item from the list.

[samuncle09]

Thanks for your response!

but I still don't understand why not make "le_prev" directly point to the previous element. It wouldn't cause much trouble for removing an element, plus, it enables traversing in backward direction.

Am I right?

It depends on what you mean by "because".

struct type xxx is the struct itself, with all its parts.

struct type *xxx is a pointer to the struct.

struct type **xxx is a pointer to a pointer to the struct; that is, it's the address of the pointer to the struct.

Now, you might be saying, "Yeah, yeah, yeah, I know all that. But why do they do it that way?"

The reason they would do it that way is to make it fairly easy to remove an item from the list.

[wje_lf]

Both ways enable traversing in both directions.

And you'd think that only one level of indirection would work. I don't know why this added complexity is necessary.

One question to investigate is: just where do they keep this extra pointer to the previous element in the list? Maybe you'll never get the answer to your original question without looking through all the source code. And that will probably give you more of an education than you really want. :)

[samuncle09]

I read the LIST operation macros, and is a bit confusing about the meaning of "address of previous next element".
It seems that "le_prev" points to the "le_next" of the previous element. So how to obtain the previous element from the "le_prev" (without this, backward traversing is not possible)?

BTW. from the LIST_INSERT_BEFORE macro:
#define LIST_INSERT_BEFORE(listelm, elm, field) do {
(elm)->field.le_prev = (listelm)->field.le_prev;
LIST_NEXT((elm), field) = (listelm);
*(listelm)->field.le_prev = (elm);
(listelm)->field.le_prev = &LIST_NEXT((elm), field);
} while (0)

why (listelm)->field.le_prev are defined twice here, and seems to be given different values?

Both ways enable traversing in both directions.

And you'd think that only one level of indirection would work. I don't know why this added complexity is necessary.

One question to investigate is: just where do they keep this extra pointer to the previous element in the list? Maybe you'll never get the answer to your original question without looking through all the source code. And that will probably give you more of an education than you really want.

[Cabhan]

This is a very strange design. le_prev is very interesting here. Note that after this code runs, elm's le_prev will point to whatever listelm's used to point to, and then it is changed to point to elm. So it would appear that le_prev always points to the current element (at least in a sane program. The LIST_NEXT() in the last line might ruin an improper implementation). I don't know what to tell you. This is not how I would ever consider programming a linked list...

As for the two definitions, the two are actually different. Note that the first assigns to what the pointer is pointing to, while the second assigns to the pointer itself. There seems no reason to use a double-pointer here, but as said, this is a strange design.

Also note that a linked list does not have to traverse backwards (one that does is called a doubly-linked list). So even though this may not do backwards-traversals does not mean it's not a linked list.

[samuncle09]

One claim of this usage is that the "le_prev" can point to an object with different type than the "le_prev" owner. For example, the "le_prev" of the first element can point to the head of the LIST, which is a simple pointer, instead of a completed struct. Not sure whether this is the only intention to use "le_prev" in this strange way.

BTW. Can we conclude that this LIST cannot do backward traversing?

[Cabhan]

Since they're specifying the type of the pointer, you should be able to do that even without this craziness.

And based on LIST_INSERT_BEFORE(), I would say that it doesn't point to the previous element, but you claim that the first element does point to "something" before it. I am assuming a special case here, in which case it wouldn't point to the previous element, but for all I know, there's some crazy pointer arithmetic somewhere.

Is there a LIST_PREV() macro?

[samuncle09]

LIST-PREV() is not defined in queue.h