tech-kern archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: in which we present an ugly hack to make sys/queue.h CIRCLEQ work

On Fri 22 Nov 2013 at 11:56:05 +0100, Martin Husemann wrote:
> On Thu, Nov 21, 2013 at 11:02:24PM -0500, Ken Hornstein wrote:
> > So ... looking at this code ... it seems like the core problem is that
> > TAILQ_HEAD and TAILQ_ENTRY are two different types (even though they
> > literally the same structure layout).  So if TAILQ_HEAD and TAILQ_ENTRY
> > were the same structure, it wouldn't be an issue.  It doesn't quite leap
> > out to me how that would be possible without changing the API a bit.
> Right. Let's break the API and fix it for real (which also should cover
> making it usable for a C++ compiler).

Since the "tqe_prev" field doesn't actually points to the previous
object in the list, but to the pointer that points to this object, it is
useful for insertion and deletion, but less so for actually finding the
previous object.

The current TAILQ_PREV essentially goes back 2 steps and then 1 forward
(since the forward pointers do point to the objects in the list).

I was thinking of something like this, which breaks the API because the
current TAILQ_PREV takes 'headname' and not 'type' as a parameter:

#defined TAILQ_PREV(elm, type, field) \
    (char *)(elm->field.tqe_prev) - offsetof(struct type, field)

(omitting outer parentheses and cast to (struct type *) for readability).

Similarly for TAILQ_LAST:

#defined TAILQ_LAST(elm, type, field) \
    (char *)(elm->field.tqe_last) - offsetof(struct type, field)

This saves on memory accesses too, compared with the current version.

I hope my diagram of how the pointers point was correct :-)

> Martin
___ Olaf 'Rhialto' Seibert  -- The Doctor: No, 'eureka' is Greek for
\X/ rhialto/at/    -- 'this bath is too hot.'

Attachment: pgp_V3ZLq6nhU.pgp
Description: PGP signature

Home | Main Index | Thread Index | Old Index