Re: data corruption on pointer cast
gara.m...@gmail.com wrote:
I implemented a set class as follows:
Why? There's std::set in the standard, which should work
perfectly well.
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.matt@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));
Realloc doesn't work in general in C++. Don't use it. Replace
the declaration of set with:
std::vector< std::vector< Element< T > > >
set ;
Then initialize it to the length M in the constructor. To
increate the size of an individual vector (as here), just use
push_back. (And don't even worry about the original size.)
Do this, and you don't need to worry about max and size_t,
either. (And size_t is a very poor choice of name. In the C
standard, the _t suffix signals a typedef, and size_t is one of
the most commonly used typedef's, both in C and in C++.)
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:
Can't say from the posted code, but one thing that looks
suspicious to me: you're using int (rather than an unsigned
type) for your hash code. A negative value from elem->hash is
likely to cause any number of problems.
*** 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.
What is the value of h here? The C++ modulo operator (%) isn't
well defined for negative values, but typically will return a
negative value.
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.
From the name of your program, it sounds like you're trying to
solve Sudoku. If so, you don't need all this; there are at most
91 moves. A brute force search using recursion works very well,
and can be implemented in less than 10 lines of code (once
you've defined the correct data types for the grill, of course).
The problem is a lot simpler than chess (where you do need all
sorts of sets with potential moves, etc.).
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34