Fonction de comparaison d'entiers avec qsort()

Le
ccandide
On 27 juil, 15:23, -ed- <emmanuel.delah@gmail.com> 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 question 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 ton
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é.


Voici un exemple d'exécution :

/*=
=*/
#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 = a;
int const *pb = b;

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

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

int main (void)
{
int x=INT_MAX-1, y=-1;

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

return 0;
}

/*=
=*/


et qui affiche chez moi :

2147483646 > -1
2147483647 < -1
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Gabriel Dos Reis
Le #19844131
ccandide
| On 27 juil, 15:23, -ed- | > 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
-ed-
Le #19844721
On 28 juil, 19:16, Gabriel Dos Reis

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.
Antoine Leca
Le #19850091
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
Gabriel Dos Reis
Le #19850451
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) ?

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
Publicité
Poster une réponse
Anonyme