On 07/19/2010 01:50 PM, Steven Schveighoffer wrote:
On Mon, 19 Jul 2010 13:47:38 -0400, Andrei Alexandrescu
<[email protected]> wrote:
On 07/19/2010 12:23 PM, Steven Schveighoffer wrote:
On Mon, 19 Jul 2010 12:21:36 -0400, Andrei Alexandrescu
<[email protected]> wrote:
By the way, I'm still eagerly waiting for your red-black tree
implementation.
Sorry for the delay, I've been very busy at work, and I wanted to slip
in a couple druntime fixes for array appending.
All that is left really is the unit testing, and making the docs more
phobos-ish.
I think it would be pure awesomeness if you massaged the red/black bit
inside one of the pointers. I figured out a way of doing that without
throwing off the garbage collector:
Yes, that works (BTW, you don't need the union, I hate unions :), just
substitute _bits for _left everywhere, I think it would even work with a
moving GC).
Walter told me that union is instrumental to keeping the compiler in
the know about such shenanigans. What does your idea look like? You
mean keeping a possibly misaligned RBTreeNode pointer and manipulating
that? I think that's a bit worse than unions because it transforms a
sure thing into a maybe works thing.
I don't pretend to know what ominous problems Walter knows about
regarding the compiler's view, but here is what I'm thinking:
If a pointer points to the beginning of a node, and a node has at least
one pointer in it (which it must, since it's a tree), then pointing one
byte into the node means you're still pointing at the same block, making
sure the GC doesn't collect.
Really, the generated code will be exactly the same as your solution,
but it's less of a misuse of the type system IMO (believe it or not).
I'd rather use casts when you are trying to use something that's typed
as one thing as something else. When using unions, I usually expect only
one member of the union to be valid at any one time.
And wouldn't a union be more egregious with the upcoming mostly-precise
scanner?
I don't think so (applied to all of the above) for reasons of various
degree of obviousness, but perhaps it's not worth expanding on such a
minor issue.
Andrei
