New submission from Zbigniew Halas:
Comparison function slotdef_cmp in Objects/typeobject.c is based on the
assumption that qsort may be stabilised by taking memory addresses of compared
objects into consideration. This assumption is not guaranteed by the C standard
and may not always be true, like for example in the case of qsort implemented
as a typical quicksort.
Sometimes it may be even more harmful, as some implementations may be unhappy
about comparison function changing its value just because an element was moved
to another memory location (I discovered this problem while porting Python to
HelenOS, where this comparison function caused qsort to enter infinite
recursion).
The actual function:
/* Comparison function for qsort() to compare slotdefs by their offset, and
for equal offset by their address (to force a stable sort). */
static int
slotdef_cmp(const void *aa, const void *bb)
{
const slotdef *a = (const slotdef *)aa, *b = (const slotdef *)bb;
int c = a->offset - b->offset;
if (c != 0)
return c;
else
/* Cannot use a-b, as this gives off_t,
which may lose precision when converted to int. */
return (a > b) ? 1 : (a < b) ? -1 : 0;
}
--
components: Interpreter Core
messages: 185738
nosy: zhalas
priority: normal
severity: normal
status: open
title: Qsort function misuse in typeobject.c
type: behavior
versions: Python 2.6, Python 2.7, Python 3.1, Python 3.2, Python 3.3
___
Python tracker
<http://bugs.python.org/issue17610>
___
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
