Second instance of KDTree::insert fails when destructor is called

[Ingo Jenni]

Hi Paul

Thanks a lot for your great answer and suggested solutions!

cheers
Ingo

Quoting "Paul Harris" <paulharris at computer.org>:

> Sorry, one minor extension to answer:  You might think that your original
> constructor makes it safe because you make a deep copy of the pointer's
> contents... but that is the explicit manual constructor.  You have not
> declared the copy-constructor or assignment-constructor, which means C++
> will declare them for you and simply make a copy of the pointer addresses...
>
>
>
> 2009/7/28 Paul Harris <paulharris at computer.org>
>
>> Looks like Keypoint is being copied.  The short, easiest answer is, do
>> option B (see below).  Read in detail for more options.
>>
>>
>> Your constructor is taking ownership of descriptor, and then deleting it on
>> destruction.  But what if you do this:
>>
>> {
>> unsigned int * d = new unsigned int[10];
>>
>> Keypoint a(d,10);
>> Keypoint b(a); // copy of a
>>
>> }  // end of scope, both a and b delete 'd'.
>>
>> to resolve this, you either:
>> a) ensure the caller (in this case, main) has ownership, and therefore is
>> in charge of deleting the pointers ONCE.
>> or
>> b) use a shared_ptr that can handle being copied around
>> or
>> c) avoid all Keypoint copies.  either inherit boost::noncopyable or declare
>> the copy-constructor and assignment operator like so...
>>
>> struct Keypoint
>> {
>> blah
>> private:
>>   Keypoint operator=(Keypoint const&); // not implemented
>>   Keypoint(Keypoint const &); // not implemented
>> };
>>
>> that won't compile if there are any copies happening.
>>
>>
>> depending on the application, I would use either A or B.
>>
>> A is more manual but if you have a lot of memory to handle then you may
>> want manual control of memory allocs and deallocs.  can be the fastest
>> solution.
>>
>>
>> B is very simple to implement...
>> #include <boost/shared_ptr.hpp>   // or use the TR1 implementation from
>> your shiny new compiler
>>
>> struct Keypoint
>> {
>>   shared_ptr<unsigned int> descriptor;
>>   Keypoint(etc etc can either pass in the pointer or shared_ptr, depending
>> on whether you will construct any other Keypoint with the same pointer);
>> NOTE NO destructor required.
>> };
>>
>> simple to implement, pretty darn quick, you won't notice the difference and
>> it'll work as expected.
>>
>>
>> option C is the most difficult as MOST STL containers (and KDTree) assume
>> that you can freely copy the items around.   so you would have to alter the
>> containers.
>>
>>
>> I've done a hybrid of A and C before.  I alloc the data beforehand (in the
>> stack or vector), pass POINTERS to kdtree to store, and write the kdtree
>> wrappers so that it can handle pointers. (the accessors etc).
>>
>>
>> see ya
>> Paul
>>
>>
>>
>> 2009/7/27 Ingo Jenni <ijenni at ee.ethz.ch>
>>
>>  Hi everybody!
>>>
>>> I want to insert structures containing a dynamically allocated element
>>> into the tree:
>>>
>>> struct Keypoint
>>> {
>>>        unsigned int* descriptor;
>>>        size_t descLen;
>>>
>>>        Keypoint(unsigned int* desc_pt, size_t _descLen)
>>>        {
>>>                descLen = _descLen;
>>>                descriptor = new unsigned int[descLen];
>>>
>>>                for(int i = 0; i != descLen; i++)
>>>                {
>>>                        descriptor[i] = desc_pt[i];
>>>                }
>>>        }
>>>
>>>        ~Keypoint()
>>>        {
>>>                delete descriptor;
>>>        }
>>>
>>>        unsigned int operator[](size_t const N) const {return
>>> descriptor[N];}
>>> };
>>>
>>> // Vector access function
>>> unsigned int descAcc(Keypoint k, size_t n)
>>> {
>>>        return k[n];
>>> }
>>>
>>> unsigned int* desc1 = new unsigned int[descLen];
>>> unsigned int* desc2 = new unsigned int[descLen];
>>>
>>> Keypoint k1(desc1, descLen);
>>> Keypoint k2(desc2, descLen);
>>>
>>> typedef KDTree::KDTree<descLen, Keypoint,
>>> std::pointer_to_binary_function<Keypoint, size_t, unsigned int> > Tree;
>>>
>>>
>>> Tree tree(std::ptr_fun(descAcc));
>>>
>>> tree.insert(k1);
>>> tree.insert(k2);
>>>
>>> Now the first insert works fine, but the second one fails with a crash:
>>>
>>> *** glibc detected *** ./a.out: double free or corruption (fasttop):
>>> 0x08ff6038 **
>>>
>>> This error does not happen when I comment out the destructor of Keypoint,
>>> but that would be the dirty solution by my count :-)
>>>
>>> Does anyone have an idea what's going on here?
>>>
>>> Best regards
>>> Ingo
>>>
>>>
>>>
>>> _______________________________________________
>>> libkdtree-devel mailing list
>>> libkdtree-devel at lists.alioth.debian.org
>>> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>>>
>>
>>
>