STL sort problem

[Nomak]

Hello,

i have a bug i can't find. I hope somebody will have some ideas...

Here is the bad peace of code:


int compare_sentence(sentence * s1, sentence * s2)
{
assert(s1);
assert(s2);

return s1->similarity_ >= s2->similarity_;
}

....
// check
{
sentences_list_type::iterator it, end = ds->doc.sentences_.end();
for (it = ds->doc.sentences_.begin(); it != end; it++)
{
sentence * s = *it;

assert(s);
assert(s->similarity_ < INT_MAX);
assert(s->sentence_.size() > 0);
}
}

// sort
if (ds->doc.sentences_.size() >= 2)
{
cerr << "&ds.doc.sentences_ = " << &ds->doc.sentences_ << endl;
cerr << "ds.doc.sentences_.size() = " << ds->doc.sentences_.size() <<
endl;

std::sort(ds->doc.sentences_.begin(),
ds->doc.sentences_.end(),
compare_sentence);

sentence * s1 = *ds->doc.sentences_.begin(),
* s2 = *(++(ds->doc.sentences_.begin()));

assert(s1->similarity_ >= s2->similarity_);
}
....


The types:
typedef vector< sentence * > sentences_list_type;
sentences_list_type sentences_;


The output:
&ds.doc.sentences_ = 0x80550a0
ds.doc.sentences_.size() = 852
sim: sim.cc:125: int compare_sentence(sentence*, sentence*): Assertion
`s1' failed.
make: *** [check] Aborted


Valgrind 2.1.1 memcheck:
&ds.doc.sentences_ = 0x3c3690b8
ds.doc.sentences_.size() = 852
==32628==
==32628== Conditional jump or move depends on uninitialised value(s)
==32628== at 0x8049356: compare_sentence(sentence*, sentence*)
(sim.cc:125)
==32628== by 0x804CBB4:
_ZSt21__unguarded_partitionIN9__gnu_cxx17__normal_iteratorIPP8sentenceSt6vectorIS3_SaIS3_EEEES3_PFiS3_S3_EET_SB_SB_T0_T1_
(stl_algo.h:1912)
==32628== by 0x804C46B:
_ZSt16__introsort_loopIN9__gnu_cxx17__normal_iteratorIPP8sentenceSt6vectorIS3_SaIS3_EEEEiPFiS3_S3_EEvT_SB_T0_T1_
(stl_algo.h:2149)
==32628== by 0x804C481:
_ZSt16__introsort_loopIN9__gnu_cxx17__normal_iteratorIPP8sentenceSt6vectorIS3_SaIS3_EEEEiPFiS3_S3_EEvT_SB_T0_T1_
(stl_algo.h:2150)
sim: sim.cc:125: int compare_sentence(sentence*, sentence*): Assertion
`s1' failed.


Valgrind doesn't show any error before the sort call.

I must be doing something bad but i'm lost now...

The check block checks for null pointer and also use a pointer to
access data (since linux doesn't have a IsBadPointer).

So i'm lost. How can i find the bug?

NB: sorry for the > 80 columns

 

[Gernot Frisch]

sentence * s1 = *ds->doc.sentences_.begin(),

* s2 = *(++(ds->doc.sentences_.begin()));

I'm not sure if you can do that.
Try:
sentence *s1 = &*ds->doc.sentences_.begin();
sentence *s2=s1;
std::advance(s2, 1);

HTH,

--
-Gernot
int main(int argc, char** argv) {printf
("%silto%c%cf%cgl%ssic%ccom%c", "ma", 58, 'g', 64, "ba", 46, 10);}

________________________________________
Looking for a good game? Do it yourself!
GLBasic - you can do
www.GLBasic.com

 

[Victor Bazarov]

i have a bug i can't find. I hope somebody will have some ideas...

Here is the bad peace of code:


int compare_sentence(sentence * s1, sentence * s2)
{
assert(s1);
assert(s2);

return s1->similarity_ >= s2->similarity_;
}

No bug here. If it compiles, it should be fine.

As you indicate below, the assert(s1) is failing. That means 's1'
is NULL when it's passed here. The only valid possibility of that
is that your vector contains NULL pointers. Can it? Sure it can.
Unless you disallow that yourself, that is. Do you? No way to tell
from the code you posted.

...
// check
{
sentences_list_type::iterator it, end = ds->doc.sentences_.end();
for (it = ds->doc.sentences_.begin(); it != end; it++)

The potential problem here is that 'end' may become invalid during
the loop execution. That's why it's often better to always check
against a value returned from the function .end() _every_ time,
instead of remembering the 'end' and checking against it.

I know, I know, in this particular case the loop does not cause any
mutation of the sequence. So, it's not critical.

{
sentence * s = *it;

assert(s);
assert(s->similarity_ < INT_MAX);
assert(s->sentence_.size() > 0);
}
}

// sort
if (ds->doc.sentences_.size() >= 2)
{
cerr << "&ds.doc.sentences_ = " << &ds->doc.sentences_ << endl;
cerr << "ds.doc.sentences_.size() = " << ds->doc.sentences_.size() <<
endl;

std::sort(ds->doc.sentences_.begin(),
ds->doc.sentences_.end(),
compare_sentence);

Somewhere during this call the assertion "assert(s1)" fails inside the
'compare_sentence' function. Is it possible that the check is OK but
the 'compare_sentence' somehow gets called with a NULL? Doesn't sound
like it, but I'd put a breakpoint into 'compare_sentence' to see who
is calling it with NULL.

sentence * s1 = *ds->doc.sentences_.begin(),
* s2 = *(++(ds->doc.sentences_.begin()));

assert(s1->similarity_ >= s2->similarity_);
}
...


The types:
typedef vector< sentence * > sentences_list_type;
sentences_list_type sentences_;


The output:
&ds.doc.sentences_ = 0x80550a0
ds.doc.sentences_.size() = 852
sim: sim.cc:125: int compare_sentence(sentence*, sentence*): Assertion
`s1' failed.
make: *** [check] Aborted

That's the most important information. The first argument is NULL. How
can that happen?

Since you don't provide the full source or input data, we can't tell. It
is up to you to find the cause.

[...]
I must be doing something bad but i'm lost now...

The check block checks for null pointer and also use a pointer to
access data (since linux doesn't have a IsBadPointer).

So i'm lost. How can i find the bug?

Try a debugger.

Victor

 

[John Harrison]

Hello,

i have a bug i can't find. I hope somebody will have some ideas...

Here is the bad peace of code:


int compare_sentence(sentence * s1, sentence * s2)
{
assert(s1);
assert(s2);

return s1->similarity_ >= s2->similarity_;
}
[snip]

Valgrind doesn't show any error before the sort call.

I must be doing something bad but i'm lost now...

The check block checks for null pointer and also use a pointer to
access data (since linux doesn't have a IsBadPointer).

So i'm lost. How can i find the bug?

Your comparison function returns true for equal sentences. That is not
allowed. Try this

int compare_sentence(sentence * s1, sentence * s2)
{
assert(s1);
assert(s2);

return s1->similarity_ > s2->similarity_;
}

john

 

[Victor Bazarov]

Hello,

i have a bug i can't find. I hope somebody will have some ideas...

Here is the bad peace of code:


int compare_sentence(sentence * s1, sentence * s2)
{
assert(s1);
assert(s2);

return s1->similarity_ >= s2->similarity_;
}

[snip]

Valgrind doesn't show any error before the sort call.

I must be doing something bad but i'm lost now...

The check block checks for null pointer and also use a pointer to
access data (since linux doesn't have a IsBadPointer).

So i'm lost. How can i find the bug?

Your comparison function returns true for equal sentences. That is not
allowed.

Why should that be a problem? Apparently, the 'compare_sentence' gets
called with s1 == 0. How would what 'compare_sentence' returns cause
that?

I am not contending the validity of your suggestion. I am simply trying
to understand how changing the >= to > would fix the OP's problem.

 

[Nomak]

Your comparison function returns true for equal sentences. That is
not allowed. Try this

int compare_sentence(sentence * s1, sentence * s2)
{
assert(s1);
assert(s2);

return s1->similarity_ > s2->similarity_;
}

Thank you SOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
much, you even can't imagine how much )))

No segfault any more

 

[John Harrison]

Hello,

i have a bug i can't find. I hope somebody will have some ideas...

Here is the bad peace of code:


int compare_sentence(sentence * s1, sentence * s2)
{
assert(s1);
assert(s2);

return s1->similarity_ >= s2->similarity_;
}

[snip]

Valgrind doesn't show any error before the sort call.

I must be doing something bad but i'm lost now...

The check block checks for null pointer and also use a pointer to
access data (since linux doesn't have a IsBadPointer).

So i'm lost. How can i find the bug?

Your comparison function returns true for equal sentences. That is not
allowed.

Why should that be a problem?

Because it breaks the strict weak ordering requirement that std::sort
imposes.

Apparently, the 'compare_sentence' gets
called with s1 == 0. How would what 'compare_sentence' returns cause
that?

The OP's compare function was undefined behaviour. compare_sentence being
called with NULL is one possible symptom.

I saw one error and I pointed it out, I didn't claim it was the only problem
with the OP's code (though apparently it was).

john

 

[Pete Becker]

Why should that be a problem? Apparently, the 'compare_sentence' gets
called with s1 == 0. How would what 'compare_sentence' returns cause
that?

When the predicate doesn't define a strict weak ordering sort typically
walks off the end of the data structure, so it passes garbage to the
predicate. Sometimes that garbage is a null pointer.