Subject: Re: libkern's rb tree
To: Joerg Sonnenberger <email@example.com>
From: Jason Thorpe <firstname.lastname@example.org>
Date: 10/24/2007 12:04:18
On Oct 24, 2007, at 1:37 AM, Joerg Sonnenberger wrote:
> As soon as the rb tree entry is not the first field in a structure,
> it is a bother.
Been there in proplib -- wasn't that big of a deal.
> Is MIPS a platform where NULL pointer comparisions are more
> expensive then
> testing a bit field in a pointer? Otherwise I am quite sure that
> this is an
> argument that doesn't hold.
You're completely missing the point and/or haven't read the comments
in the code. The sentinel node saves having to even test for NULL in
a few places (since every linkage pointer will point to valid memory
-- either a real node or the sentinel) .. this saves cycles during
insertion and removal.
It's the position of rb_sentinel that really benefits MIPS (when your
lookup is written in asm).