question about queue.h

walter harms
Wed Jul 16 17:05:00 GMT 2008

Bert Wesarg wrote:
> Hi,
> On Mon, Jul 14, 2008 at 14:44, walter harms <> 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.

of cause i read the statement but obviously i did not understand it.
I have a double linked list what is supposed to be used in one
direction. Who needs that ?

later versions of queue.h (e.g.
have a single linked list and more. there is also remque() and insque().

i am not sure what should i make from this situation. perhaps i will continue
rewriting the macros and later merge them with insque().

if someone is interessted in lists he/she may like to take a look at this thread.
linked lists that can run in shared mem.

ntl i would like to thank all people trying to explain this unusual configuration.


> 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

More information about the Libc-help mailing list