Re: [Slightly off topic] A question about R/B trees.

[Chris Snook <csnook@redhat.com>]

Maxim Levitsky wrote:
> I am working on my small project, and I need a fast container to hold a 
> large sparse array.
> Balanced trees seem to fit perfectly.

Balanced trees take O(log n) to perform a great many operations, and traversing 
a binary tree is a particularly bad case for branch prediction.  Hash tables 
will perform much better, unless you get them horribly wrong.

> I decided to implement a red/black tree, and took a look at kernel rb 
> tree for reference,
> and I noticed that tree item has no parent pointer, while it seems that 
> it should have it.
> 
> I know now that it has parent pointer, but it is mixed with current and 
> parent node colour.
> Thus it is assumed that last two bits of this pointer are zero.

Not quite.  Read this:

http://lwn.net/Articles/184495/

> I can see anywhere that this restriction is applied.
> I see that structure is "aligned" but that I think only ensures that 
> compiler places it
> aligned in static data, does the alignment ensures that it will always 
> place it on aligned address in a structure?
> But then, the whole container structure can be misaligned, can't it?

GCC will only misalign the contents of a struct if you explicitly tell it to 
pack the struct.  That's one of those things you only do if you're 100% certain 
it's the right thing, and you're prepared to accept the consequences if you 
screw it up.

> Besides a comment there states that alignment is only for CRIS

I'm not sure this check is still necessary, but CRIS is a rather niche 
architecture.  On most architectures, word-aligning structures boosts 
performance at negligible memory cost, so compilers do it automatically.

> How about a check for misalignment?

The kernel is written in a dialect of C that makes several assumptions about the 
compiler, among them that the compiler won't screw this up unless you tell it 
to.  Any compiler that has alignment problems with the rbtree code is going to 
have similar problems in lots of other places too.  We don't support those 
compilers.

-- Chris