This is the mail archive of the libc-help@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: question about queue.h


Hi,

On Mon, Jul 14, 2008 at 14:44, walter harms <wharms@bfs.de> wrote:
> why should i need a 'previous next element' ? That is the current element. IMHO that is useless.
> i guess: in the beginning that was a "typo" and somebody fixed the comment.
No. Have you tried to compile a program with your proposed fix? I
suggest not, because you would get compile errors.

If you would have read the queue.h file from the beginning, you may
have stumble over this:

 * A list is headed by a single forward pointer (or an array of forward
 * pointers for a hash table header). The elements are doubly linked
 * so that an arbitrary element can be removed without a need to
 * traverse the list. New elements can be added to the list before
 * or after an existing element or at the head of the list. A list
 * may only be traversed in the forward direction.

So, the LIST is a list, which provides O(1) insertion and deletion,
but only forward traversal. To achieve this, you only need the
reference to the previously next pointer, which is exactly what is
implemented.

For example in the LIST_INSERT_AFTER macro, the last line:

   (elm)->field.le_prev = &(listelm)->field.le_next;

You see, you store the reference to the le_next field into the le_prev field.

Or in the LIST_INSERT_BEFORE macro:

  *(listelm)->field.le_prev = (elm);

you dereference the le_prev file and get store a new value for this
le_next field.

But best shown in the LIST_REMOVE macro:

  *(elm)->field.le_prev = (elm)->field.le_next;

you bend the le_next pointer behind your le_prev pointer to your
le_next pointer.

regards
Bert

> re,
>  wh


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]