This is the mail archive of the
libc-help@sourceware.org
mailing list for the glibc project.
Re: question about queue.h
- From: "Bert Wesarg" <bert dot wesarg at googlemail dot com>
- To: wharms at bfs dot de
- Cc: "Sadashiiv, Halesh" <halesh dot sadashiv at ap dot sony dot com>, libc-help at sourceware dot org
- Date: Mon, 14 Jul 2008 19:12:37 +0200
- Subject: Re: question about queue.h
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:to :subject:cc:in-reply-to:mime-version:content-type :content-transfer-encoding:content-disposition:references; bh=nYcOllUFnjNeRi9FAGRRdgEzb/+GLnZtPOu/mtp4fX8=; b=YTnpchD0hrUjOiNgMyokRFIsUowkm8B8mqurIGN3gL0f+teaV858kDcHYhX2cru1bL 8Mz00/9JZVfGHWJUKPlNWdDw9Fgms+wSSA1yRfd18kk1lNeyUjH0N3m0estLqRd5+ozO 5dcoPxXHznugdlKgjSx1ROwLnaeyA/NJvsBt8=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=googlemail.com; s=gamma; h=message-id:date:from:to:subject:cc:in-reply-to:mime-version :content-type:content-transfer-encoding:content-disposition :references; b=ji79fhi/QHFTQYPn/It8U7Kcfa1y2TuNf5jHRBs4NfivxRyddkhdZRVqEHEtR9tMWy p5s7G6T5+aKJINXQyLjNzoyPEMfvb0b9PArZfUE9MapMGWIXkPDIntIwmcS3s3fwOmld LmA5whA1Wf4jn2lQSKKIy+0d2lqeTBwN2bF5Q=
- References: <7B7EF7F090B9804A830ACC82F2CDE95D3783E6@insardxms01.ap.sony.com> <487B4A12.4030709@bfs.de>
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