data corruption on pointer cast

[gara.matt]

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 <[email protected]>
*/
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]))
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]))

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.

 

[gara.matt]

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 <[email protected]>
*/
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]))
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]))

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]))
return 1;
return 0;
}
....
};


It works all the time. Its really weird, any ideas why the previous
didn't work?

 

[gara.matt]

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 <[email protected]>
*/
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]))
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]))

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]))
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])
return 1;
return 0;
}
....

};

It works all the time. Its really weird, any ideas why the previous
didn't work?

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

Heyllo,

Names matt,

I implemented a set class as follows:

template<class T>
class Element
{
public:
virtual int operator == (T) = 0;

virtual bool operator==(const T&) = 0;

virtual int hash() = 0;
};

/**
* A efficient hash implementation of a Queue-set that does not allow
addition of duplicates.
@author matt gara <[email protected]>
*/
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]))
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));

Unfortunately I don't think that there's any guarantee that realloc will
work on anything except POD types, which makes it very dangerous to use
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];

size_t is the name of a type used extensively throughout the standard
library, using it as an identifier might not be a good idea.

int max[M];
...
};

Sorry, can't help you with your problem, I can only point out some other
things in your code. One thing I noticed was that you use an awful lot
of pointers, try using references instead. Also you might want to make
Element a private class to QueueSet and make it's use transparent to the
user, require instead that the elements are comparable and let the user
supply the hash-function as a template parameter:

template<class T, class H, int M = p>
class QueueSet { ... };

where H is the hash-function.

 

[James Kanze]

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 <[email protected]>
*/
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]))
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]))

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.).

 

[Old Wolf]

Heyllo,

template<class T>
class Element
{
public:
virtual int operator == (T) = 0;
virtual int hash() = 0;
};

int exists(Element<T> * elem)
{
int h = elem->hash()%M;
for (int i=0; i < size_t[h]; i++)

This is a syntax error -- size_t is a keyword,
you can't apply array indexing to it

if ( *((T*)elem) == *((T*)set[h]))

This line is wrong. 'elem' does not point to
a T, it points to a class with virtual functions.

The only way this could work is if 'elem' defined
an "operator T *" conversion operator, but it doesn't.

You should never use a C-style cast in C++, because
it will usually make the compiler suppress all the
warnings that you're doing something wrong.

I'm not sure what the code is meant to do, so I can't
suggest a replacement. Element<> contains no T and
no functions to access a T, so I don't see how you
are expecting to get a T out of it.

If Element<T>:perator== took another Element<T> as
the argument, then you could write:
if ( *elem == set[h] )

As James Kanze pointed out, you're using far
too many pointers. You should be able to
rewrite this program to not use any pointers.

 

[Robert Bauck Hamar]

Heyllo,

template<class T>
class Element
{
public:
virtual int operator == (T) = 0;
virtual int hash() = 0;
};

int exists(Element<T> * elem)
{
int h = elem->hash()%M;
for (int i=0; i < size_t[h]; i++)

This is a syntax error -- size_t is a keyword,

No, it's not. From the standard's point of view, it's a defined type from
the standard library. <cstddef>, <cstdio>, <cstring> and <ctime> should all
define std::size_t, and thus, their .h version puts size_t in the global
namespace. As std::size_t is a typedef from the C libraries, ::size_t is
also a reserved name. But it's not a keyword; maybe you're thinking of
wchar_t?

you can't apply array indexing to it

Though a poorly chosen name, it is legal. Size_t is a data member of the
class.

 

[gara.matt]

Heyllo,
template<class T>
class Element
{
public:
virtual int operator == (T) = 0;
virtual int hash() = 0;
};
int exists(Element<T> * elem)
{
int h = elem->hash()%M;
for (int i=0; i < size_t[h]; i++)

This is a syntax error -- size_t is a keyword,

No, it's not. From the standard's point of view, it's a defined type from
the standard library. <cstddef>, <cstdio>, <cstring> and <ctime> should all
define std::size_t, and thus, their .h version puts size_t in the global
namespace. As std::size_t is a typedef from the C libraries, ::size_t is
also a reserved name. But it's not a keyword; maybe you're thinking of
wchar_t?

you can't apply array indexing to it

Though a poorly chosen name, it is legal. Size_t is a data member of the
class.

Hey guys, thanks for all the replies. I'll try to address each issue
brought up. First I've received almost universal criticism on using
size_t, which I agree in whole, what can I say? It seemed like a good
idea at the time

I've heard some discontent in some poster with my use of realloc, but
coming from a C background I tend to like to manually allocate memory.
I am fairly certain allocating space for an array of pointers works
just the same in C++ as in C, since are they not at the very core just
integers (in particular data types with no constructors?)

Next, some people disapprove of me using "so many" pointers in my
code, and I would love to take your advice on this topic because I'm
used to C. Can you be more specific, for example, do you mean I should
not pass pointers to classes as parameters but rather pass the classes
by reference? What other advantages other than a cosmetic change to
code readability does this have over the other way? I do, however,
oppose the idea of storing a set of elements in the class rather than
a set of pointers to the elements since I may want to keep the
"actual" objects elsewhere.

Next, I'd like to thank james for pointing out the std::set class, I
was totally oblivious to it, although I knew about vector and list, go
figure. Reinventing the wheel is painful, but it is instructive,
although I make no claims that my code is half as efficient as the std
code.

Also Erik in your suggestion of the implementation, how would you pass
in the hash function as a parameter? Just a regular function pointer?
And how can you guarantee that the == operator would be implemented,
other than the obvious default operator?

Last but not least, old wolf, I think you may have pointed out what
I've been doing wrong, I'll try it out.

 

[gara.matt]

Heyllo,
template<class T>
class Element
{
public:
virtual int operator == (T) = 0;
virtual int hash() = 0;
};
int exists(Element<T> * elem)
{
int h = elem->hash()%M;
for (int i=0; i < size_t[h]; i++)

This is a syntax error -- size_t is a keyword,

No, it's not. From the standard's point of view, it's a defined type from
the standard library. <cstddef>, <cstdio>, <cstring> and <ctime> should all
define std::size_t, and thus, their .h version puts size_t in the global
namespace. As std::size_t is a typedef from the C libraries, ::size_t is
also a reserved name. But it's not a keyword; maybe you're thinking of
wchar_t?

you can't apply array indexing to it

Though a poorly chosen name, it is legal. Size_t is a data member of the
class.

Well it seems my previous message was not posted or deleted somehow...
annoying. I'll retype it again later

 

[gara.matt]

Heyllo,
template<class T>
class Element
{
public:
virtual int operator == (T) = 0;
virtual int hash() = 0;
};
int exists(Element<T> * elem)
{
int h = elem->hash()%M;
for (int i=0; i < size_t[h]; i++)

This is a syntax error -- size_t is a keyword,

No, it's not. From the standard's point of view, it's a defined type from
the standard library. <cstddef>, <cstdio>, <cstring> and <ctime> should all
define std::size_t, and thus, their .h version puts size_t in the global
namespace. As std::size_t is a typedef from the C libraries, ::size_t is
also a reserved name. But it's not a keyword; maybe you're thinking of
wchar_t?

you can't apply array indexing to it

Though a poorly chosen name, it is legal. Size_t is a data member of the
class.

I can't seem to reply... every post I make never posts.

 

[BobR]

I can't seem to reply... every post I make never posts.

Are you waiting the required 24-48 hours before makeing that claim?
<G>

Did you killfile yourself?

 

[Default User]

Did you killfile yourself?

He uses Google Groups, so unlikely. Posting problems from GG, on the
other hand, all too common.




Brian

 

[gara.matt]

He uses Google Groups, so unlikely. Posting problems from GG, on the
other hand, all too common.

Brian

Yes you guessed correctly I am using Google Groups and it seems GG has
problems with usenet posting at times (I searched this after realizing
none of my posts were being posted, and I'd gladly remove the two
useless posts but unfortunately I don't know how or it is impossible.)
Sorry, I don't know anything about the 24-48hr required wait before
making claims, I'm new to newsgroups.