Re: data corruption on pointer cast
On Jul 15, 11:09 pm, gara.m...@gmail.com wrote:
On Jul 15, 10:56 pm, gara.m...@gmail.com wrote:
Heyllo,
Names matt,
I implemented a set class as follows:
template<class T>
class Element
{
public:
virtual int operator == (T) = 0;
virtual int hash() = 0;
};
/**
* A efficient hash implementation of a Queue-set that does not allow
addition of duplicates.
@author matt gara <gara.m...@gmail.com>
*/
template<class T, int M = p>
class QueueSet
{
public:
...
int exists(Element<T> * elem)
{
int h = elem->hash()%M;
for (int i=0; i < size_t[h]; i++)
if ( *((T*)elem) == *((T*)set[h][i]))
return 1;
return 0;
}
int add(Element<T> * elem)
{
int h = elem->hash()%M;
if (size_t[h] == max[h])
{
set[h] = (Element<T> **)realloc(set[h], sizeof(Element<T>
*)*(max[h] + P));
max[h] += P;
}
if (exists(elem))
return 0; //failed to add
set[h][size_t[h]] = elem;
size_t[h] += 1;
size++;
return 1;
}
...
Element<T> ** set[M];
int size;
private:
int size_t[M];
int max[M];
...
};
And it works up until I try adding the 52nd element and it throws an
exception:
*** glibc detected *** /home/matt/sudokusolver/debug/./src/
sudokusolver: double free or corruption (fasttop): 0x0804d170 ***
======= Backtrace: =========
/lib/tls/i686/cmov/libc.so.6[0xb7dba7cd]
/lib/tls/i686/cmov/libc.so.6(cfree+0x90)[0xb7dbde30]
/home/matt/sudokusolver/debug/./src/sudokusolver[0x8048d7c]
/home/matt/sudokusolver/debug/./src/sudokusolver[0x804ada1]
/home/matt/sudokusolver/debug/./src/sudokusolver[0x804aeb6]
/home/matt/sudokusolver/debug/./src/sudokusolver[0x804a6f5]
/home/matt/sudokusolver/debug/./src/sudokusolver[0x804a795]
/home/matt/sudokusolver/debug/./src/sudokusolver[0x804962d]
/lib/tls/i686/cmov/libc.so.6(__libc_start_main+0xdc)[0xb7d68ebc]
/home/matt/sudokusolver/debug/./src/
sudokusolver(__gxx_personality_v0+0x49)[0x8048911]
I've done some debugging and it looks like the exception happens in
the exists member. I'm pretty certain the exception is caused by the
following line:
if ( *((T*)elem) == *((T*)set[h][i]))
which is weird because it works for the first 51st elements and then
throws this nutty error.
If the code doesn't speak for itself, T is a class that implements
Element to get the hash and ==. The hash is used in creating the table
and the == is supposed to be used to make sure duplicated do not
exist, but clearly its not working properly. Thanks.
Note that the following code works:
template<class T>
class Element
{
public:
virtual bool equals(T * elem ) = 0;
// virtual int operator == (T) = 0;
virtual int hash() = 0;
};
class QueueSet
{
...
int exists(Element<T> * elem)
{
int h = elem->hash()%M;
for (int i=0; i < size_t[h]; i++)
if (elem->equals((T*)set[h][i]))
return 1;
return 0;
}
...
};
It works all the time. Its really weird, any ideas why the previous
didn't work?
Also, this code also works:
template<class T>
class Element
{
public:
// virtual bool equals(T * elem ) = 0;
virtual int operator == (T*) = 0;
virtual int hash() = 0;
};
class QueueSet
{
....
int exists(Element<T> * elem)
{
int h = elem->hash()%M;
for (int i=0; i < size_t[h]; i++)
if (*elem == (T*)set[h][i])
return 1;
return 0;
}
....
};
It works all the time. Its really weird, any ideas why the previous
didn't work?