Messages in this thread | | | Date | Fri, 17 Oct 2008 23:34:50 +0200 | From | Maxim Levitsky <> | Subject | [Slightly off topic] A question about R/B trees. |
| |
Hi,
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.
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.
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?
Besides a comment there states that alignment is only for CRIS
How about a check for misalignment?
Best regards, Maxim Levitsky
| |