Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

Fonction de comparaison d'entiers avec qsort()

4 réponses
Avatar
ccandide
On 27 juil, 15:23, -ed- <emmanuel.delah...@gmail.com> wrote:
> Ce qui compte, ce n'est pas l'historique, mais l'=E9tat des lieux tel
> qu'il est affirm=E9 =E0 ce jour, c'est =E0 dire, par exemple, sur mon
> site ...

Tiens justement, j'avais =E0 coder, en r=E9ponse =E0 une question du forum =
C
du Site du Z=E9ro, une fonction callback compar() pour un qsort()
d'entiers. J'ai donc eu l'id=E9e de regarder ce que tu proposais sur ton
site. Voici ton code, cf. http://www.bien-programmer.fr/qsort.htm :


/*=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D*/
/* fonction utilisateur de comparaison fournie a qsort() */
static int compare (void const *a, void const *b)
{
/* definir des pointeurs type's et initialise's
avec les parametres */
int const *pa =3D a;
int const *pb =3D b;

/* evaluer et retourner l'etat de l'evaluation (tri croissant) */
return *pa - *pb;
}
/*=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D*/

Il me semble que ce code contient une erreur : *pa - *pb peut
engendrer un d=E9passement de capacit=E9 (integer overflow), ce qui est un
comportement ind=E9termin=E9.


Voici un exemple d'ex=E9cution :

/*=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

/* fonction utilisateur de comparaison fournie a qsort() */
static int compare (void const *a, void const *b)
{
/* definir des pointeurs type's et initialise's
avec les parametres */
int const *pa =3D a;
int const *pb =3D b;

/* evaluer et retourner l'etat de l'evaluation (tri croissant) */
return *pa - *pb;
}

void afficher(int x, int y)
{
int delta=3Dcompare(&x, &y);
printf("%d %c %d\n", x, delta > 0 ? '>' : delta =3D=3D 0 ? '=3D' : '<',
y);
}

int main (void)
{
int x=3DINT_MAX-1, y=3D-1;

afficher(x,y);
afficher(x=3DINT_MAX,y); /* <---- Overflow */

return 0;
}

/*=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D*/


et qui affiche chez moi :

2147483646 > -1
2147483647 < -1

4 réponses

Avatar
Gabriel Dos Reis
ccandide writes:

| On 27 juil, 15:23, -ed- wrote:
| > Ce qui compte, ce n'est pas l'historique, mais l'état des lieux tel
| > qu'il est affirmé à ce jour, c'est à dire, par exemple, sur mon
| > site ...
|
| Tiens justement, j'avais à coder, en réponse à une questio n du forum C
| du Site du Zéro, une fonction callback compar() pour un qsort()
| d'entiers. J'ai donc eu l'idée de regarder ce que tu proposais sur t on
| site. Voici ton code, cf. http://www.bien-programmer.fr/qsort.htm :
|
|
| /*======================= ==*/
| /* fonction utilisateur de comparaison fournie a qsort() */
| static int compare (void const *a, void const *b)
| {
| /* definir des pointeurs type's et initialise's
| avec les parametres */
| int const *pa = a;
| int const *pb = b;
|
| /* evaluer et retourner l'etat de l'evaluation (tri croissant) */
| return *pa - *pb;
| }
| /*======================= ==*/
|
| Il me semble que ce code contient une erreur : *pa - *pb peut
| engendrer un dépassement de capacité (integer overflow), ce qui est un
| comportement indéterminé.

Exact.

J'aurais écrit

static int
int_compare(const void* p, const void* q) {
const int a = *(const int*)p;
const int b = *(const int*)q;
if (a < b) return -1;
if (a > b) return 1;
return 0;
}


-- Gaby
Avatar
-ed-
On 28 juil, 19:16, Gabriel Dos Reis wrote:


J'aurais écrit

  static int
  int_compare(const void* p, const void* q) {
    const int a = *(const int*)p;
    const int b = *(const int*)q;
    if (a < b) return -1;
    if (a > b) return 1;
    return 0;
  }

-- Gaby



OK.
Avatar
Antoine Leca
Le 28/07/2009 17:16Z, Gabriel Dos Reis écrivit :
J'aurais écrit

static int
int_compare(const void* p, const void* q) {
const int a = *(const int*)p;
const int b = *(const int*)q;
if (a < b) return -1;
if (a > b) return 1;
return 0;




C'est sûr que c'est plus lisible que

return a<b ? -1 : a>b;

mais est-ce aussi efficace (avec les compilos actuels) ?


Antoine
Avatar
Gabriel Dos Reis
Antoine Leca writes:

| Le 28/07/2009 17:16Z, Gabriel Dos Reis écrivit :
| > J'aurais écrit
| >
| > static int
| > int_compare(const void* p, const void* q) {
| > const int a = *(const int*)p;
| > const int b = *(const int*)q;
| > if (a < b) return -1;
| > if (a > b) return 1;
| > return 0;
|
|
| C'est sûr que c'est plus lisible que
|
| return a<b ? -1 : a>b;
|
| mais est-ce aussi efficace (avec les compilos actuels) ?

Je comprends que la légende urbaine voudrait que l'efficacité d'u ne
fonction C soit une fonction croissante du numbre de tokens utilisés
pour l'écrire, mais je serai vraiment surpris si un compilateur moderne
tombait dans ce panneau dans ce cas précis :-)

Le compilateur C qui vient avec mon système génère (gcc-4.3. 2)

.file "gdr.c"
.text
.p2align 4,,15
.globl int_compare
.type int_compare, @function
int_compare:
.LFB2:
movl (%rsi), %eax
cmpl %eax, (%rdi)
movl $-1, %edx
jl .L3
setg %al
movzbl %al, %edx
.L3:
movl %edx, %eax
ret
.LFE2:
.size int_compare, .-int_compare

pour ma version, et

.file "al.c"
.text
.p2align 4,,15
.globl int_compare
.type int_compare, @function
int_compare:
.LFB2:
movl (%rsi), %eax
cmpl %eax, (%rdi)
movl $-1, %edx
jl .L3
setg %al
movzbl %al, %edx
.L3:
movl %edx, %eax
ret
.LFE2:
.size int_compare, .-int_compare


pour ta version. Je ne vois pas de différence (et diff non plus).
Donc, je pense que je préfère ma version :-)

-- Gaby