lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
Date: Fri, 17 Oct 2008 23:34:50 +0200 From: Maxim Levitsky <maximlevitsky@...il.com> To: linux-kernel@...r.kernel.org 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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@...r.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists