Subject: Re: libkern's rb tree
To: Joerg Sonnenberger <>
From: Jason Thorpe <>
List: tech-kern
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).

-- thorpej