Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Hartmut Kaiser (hartmut.kaiser)
Date: 2010-09-10 09:11:43

> Since all these examples uses EMPTY classes, codes as following will
> complaint nothing and event run as people expects -- the tree::foo() will
> be invoked:
> 
> 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();
> 
> As a member function needs a object pointer to be invoked, in facts, it's
> not matter what's the pointer really pointed to, if your  class hierarchy
> is empty classes, no CRASH will complaint. But if you try to insert some
> member fields in 'tree', and intend to access any fields, the whole world
> will CRASH -- the 'this' pointer is in fact pointed to something totally
> different.

Even with empty classes it's still undefined behavior, so all bets are off.

Regards Hartmut
---------------
http://boost-spirit.com

> 
> 
> --
> Duzy Chan
> http://duzy.info
> 
> On Fri, Sep 10, 2010 at 5:39 PM, Adam Wulkiewicz
> <adam.wulkiewicz_at_[hidden]> wrote:
> 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
> 
> _______________________________________________
> ggl mailing list
> ggl_at_[hidden]
> http://lists.osgeo.org/mailman/listinfo/ggl