Re: question about queue.h

[walter harms <wharms at bfs dot de>]

Bert Wesarg wrote:
> 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.


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. http://freebsd.active-venture.com/FreeBSD-srctree/newsrc/sys/queue.h.html)
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.
http://ml.osdir.com/os.freebsd.architechture/2002-11/msg00054.html


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

re,
  wh

> 
> 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
> 
>