Subject: [ggl] space partitioning
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2010-09-10 05:39:16
Duzy Chan wrote:
> It's undefined:
>
> struct base
> {
> };
>
> struct derived : base
> {
> void blah() { /* ... */ }
> };
>
> base obj;
>
> void foo()
> {
> base * o = &obj;
>
> derived * p = (derived*) o;
> p->blah(); //<--------------------------- undefined behavior
> }
>
> --
> Duzy Chan
> http://duzy.info
>
>
> On Fri, Sep 10, 2010 at 8:06 AM, Simonson, Lucanus J
> <lucanus.j.simonson_at_[hidden] <mailto:lucanus.j.simonson_at_[hidden]>> wrote:
>
> Adam Wulkiewicz wrote:
> > Barend Gehrels wrote:
> >> hi Adam,
> >>
> >>>
> >>>
> >>> Yes, I'm using the old version, thanks. But I don't know if I'll
> >>> make corrections now. It seems that dynamic self balancing spacial
> >>> index is desirable. What do you think about it?
> >>>
> >>
> >> I don't know, it (whether or not self balancing) is probably
> >> dependent on the situation and should ideally be configurable.
> >>
> >> It is of course no problem not making the corrections instantly, I
> >> however cannot have a thorough look then (this is usually how I do
> >> it, walking through). At least the main program should compile, and
> >> I can use the old version, the last time it was sent in two mails,
> >> can you send one consistent (compiling) set again?
> >
> > Hi,
> >
> > Sorry that I haven't written to you sooner. I'd like to show you
> > something else instead of kd-tree.
> > The community said that spacial index should work like std::set and
> > even
> > if I feel different the first data structure should be implemented
> > this way. The spacial index may be e.g. a dynamic AABBTree. Leaf and
> > internal
> > nodes should be different classes derived from one Node class and
> > created by allocator or possibly two different allocators defined by
> > the user.
> >
> > I've implemented a generic tree which I'd like to use as a base of
> > this container. I've taken the idea from "Game programming gems 4"
> > but my version is an intrusive container without memory allocation.
> > It's not
> > the 'final' container it's just an implementation of some needed
> > algorithms and iterators. Users could use this generic tree class to
> > build their own trees.
> >
> > I had two designs in mind. First one was the tree which contains
> > pointer
> > to root. The tree structure would be defined only by nodes. Nodes
> > could
> > be manipulated only by use of the tree class and an iterator to node:
> >
> > child_iterator begin_child(Iter nodeit)
> > void push_back_child(node *n, Iter nodeit)
> >
> > tree t;
> > node *n = (node*)create_internal_node();
> > t.push_back(n);
> > n = (node*)create_leaf_node();
> > t.push_back_child(n, t.root());
> >
> > The second one is a tree derived from node, which I've chosen. The
> > main drawbacks are that the tree creation isn't intuitive, there is
> > more pointers casting and in this case the tree isn't a container
> > actually:
> >
> > node *n = (node*)create_internal_node();
> > tree *t = (tree*)n;
> > n = create_leaf_node();
> > t.push_back_child((tree*)n);
>
> This syntax isn't technially "legal" because the C++ standard says
> that the results of casting a pointer of base type to a pointer of
> derived type if the object pointed to is of base type is undefined.
> That means there is no guarentee that the code will do what you
> expect even if it compiles. In reality it does compile and usually
> does what you expect, but it is against boost coding standards to do
> with sort of thing. I'm not sure what type your
> create_internal_node() returns, but I assume it is not tree*. I
> also don't think the public interface should provide access to
> internal nodes, but regardless, the design of the internals cannot
> rely on undefined behavior.
>
> Regards,
> Luke_______________________________________________
> ggl mailing list
> ggl_at_[hidden] <mailto:ggl_at_[hidden]>
> http://lists.osgeo.org/mailman/listinfo/ggl
>
Is it undefined even if the object of derived class was created in the
first place and the pointer casted to the base type? Isn't it used in
Boost.Intrusive?
struct node {}
struct internal_node : public node {}
struct leaf_node : public node {}
internal_node *in = new internal_node();
node *n = static_cast<node*>(in);
/* do something with node n */
internal_node *in2 = static_cast<internal_node*>(n);
/* do something with internal node n2 */
leaf_node *ln = new leaf_node();
node *n2 = static_cast<node*>(ln);
/* do something with node n2 */
leaf_node *ln2 = static_cast<leaf_node*>(n2);
/* do something with leaf node ln2 */
I have objections about following code where object of derived type 1 is
created, and the pointer is casted to the base class and then to the
derived type 2 extending the interface of the base class.
struct tree : public node
{
void foo()
{
do_something_with_node(static_cast<node*>(this));
}
/* no atributes */
}
internal_node *in = new internal_node();
tree *t = static_cast<tree*>(static_cast<node*>(in));
t->foo();
Regards,
Adam