Bonjour

Je viens à vous pour la première fois sur ce forum avec un problème que j'arrive pas à résoudre.

Je suis débutant en C et j'ai un projet étudiant à réaliser qui porte sur les enveloppes convexes (projet plutôt intéressant), mon problème est que je dois trié des points avec un tri rapide et je n'arrive pas à trouver l'erreur provoquant l'overflow. Je précise que le programme présenté ci-dessous marche partiellement, il arrive que le programme s’exécute jusqu'au bout. Les points à trier sont envoyés sur l'entrée standard et un autre programme crée des points aléatoirement, j’exécute mon programme de cette manière : ./hull-generator 10 | ./pilote où 10 est le nombre points créés .

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>

struct vec {
    double x;
    double y;
};


struct vecset {
struct vec *data;
size_t size;
size_t capacity;
};

typedef int (*comp_func_t)(const struct vec *p1, const struct vec *p2, const void *ctx);

void vecset_create(struct vecset *self)
{
    self->size=0;
    self->capacity=10;
    self->data = calloc(self->capacity, sizeof(struct vec));
}

void vecset_destroy(struct vecset *self)
{
    self->size = 0;
	self->capacity = 0;
    free(self->data);
}

int comp_ord(const struct vec *p1, const struct vec *p2, const void *ctx)
{
    if(p1->y<p2->y){
        return -1;
    }
    else if(p1->y==p2->y) {
        if(p1->x==p2->x){
            return 0;
        }
        if(p1->x<p2->x){
            return -1;
        }
    }
        return 1;
}

void swap(struct vecset *self, int i, int j)
{
    struct vec tmp = self->data[i];
    self->data[i] = self->data[j];
    self->data[j] = tmp;
}
ssize_t partitionner(struct vecset *self, comp_func_t func, const void *ctx, int i, int j) {
    ssize_t pivot_index = i;
    const struct vec pivot = self->data[i];
    swap(self, pivot_index, j);
    ssize_t l = i;
    ssize_t k;
    for (k = i; k < j; ++k) {
        if(func(&pivot,self->data+k,ctx) > 0){
            swap(self, k, l);
            l++;
        }
    }
    swap(self, l, j);
    return l;
}

void quickSort(struct vecset *self, comp_func_t func, const void *ctx, size_t i, size_t j)
{
    if (i < j) {
        ssize_t pivot = partitionner(self, func, ctx, i, j);
        quickSort(self, func, ctx, i, pivot-1);
        quickSort(self, func, ctx, pivot+1, j);
    }

}
void vecsetsort(struct vecset *self, comp_func_t func, const void *ctx)
{
    quickSort(self, func, ctx, 0, self->size-1);
}


void vecset_Alloc(struct vecset *self)
{
	self->capacity *= 2;
	struct vec *data = calloc(self->capacity, sizeof(struct vec));
	memcpy(data, self->data, self->size * sizeof(struct vec));
	free(self->data);
	self->data = data;
}

void vecset_add(struct vecset *self, struct vec p)
{
    if (self->capacity == self->size) {
        vecset_Alloc(self);
    }
    self->data[self->size]=p;
    self->size++;
}

#define BUFSIZE 25

int main() {

    struct vecset *in = malloc(sizeof(struct vecset));

    vecset_create(in);

    setbuf(stdout, NULL);
    char buffer[BUFSIZE];
    fgets(buffer, BUFSIZE, stdin);
    size_t count = strtol(buffer, NULL, 10);
    size_t i;
    for (i = 0; i < count; ++i) {
        struct vec p;
        fgets(buffer, BUFSIZE, stdin);
        char *endptr = buffer;
        p.x = strtod(endptr, &endptr);
        p.y = strtod(endptr, &endptr);
        vecset_add(in, p);
    }
    for (i=0; i < in->size; i++){
        printf("%zu %f %f\n", i, in->data[i].x, in->data[i].y);
    }
    vecsetsort(in, comp_ord, NULL);
    for (i=0; i < in->size; i++){
        printf("%f %f\n", in->data[i].x, in->data[i].y);
    }
    vecset_destroy(in);
    free(in);
    return 0;
}

J'ai également testé avec Valgrind les possibles erreurs de fuite mémoire : RAS

Il m'affiche par contre cette erreur à répétition :

==11639== Invalid write of size 8
==11639==    at 0x400A13: swap (in /home/user/Dropbox/Cours/Partage/test)
==11639==    by 0x400AF8: partitionner (in /home/user/Dropbox/Cours/Partage/test)
==11639==    by 0x400B47: quickSort (in /home/user/Dropbox/Cours/Partage/test)
==11639==    by 0x400B71: quickSort (in /home/user/Dropbox/Cours/Partage/test)
==11639==    by 0x400BD5: vecsetsort (in /home/user/Dropbox/Cours/Partage/test)
==11639==    by 0x400E88: main (in /home/user/Dropbox/Cours/Partage/test)
==11639==  Address 0x51fc098 is 8 bytes before a block of size 160 alloc'd
==11639==    at 0x4C2CC70: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==11639==    by 0x4008B5: vecset_create (in /home/user/Dropbox/Cours/Partage/test)
==11639==    by 0x400D16: main (in /home/user/Dropbox/Cours/Partage/test)
==11639== 
==11639== Stack overflow in thread 1: can't grow stack to 0xffe801ff8

Merci d'avance pour le temps que vous me consacrerez

Salut,

Combien as tu d'éléments dans ton tableau ?

Il peut arriver que le quicksort brut fasse un stack overflow dans le cas ou le pivot est trop près d'un bord, et ce récursivement. Mais c'est quand il y a des centaines de milliers d'éléments ça.

Sinon, pourquoi n'utilises tu pas la fonction qsort de stdlib ? C'est un quicksort amélioré qui justement ne partira pas en overflow

Dans le cadre de mes études notre professeur nous encourage à bosser les algos en tout genre dont l'algo de tri rapide.

Au niveaux des points je test actuellement le programme sur une série de 10 points.

Je comprends qu'on refasse des algos de tri pour s'entrainer, mais après, il est dommage de ne pas utiliser le standard, mais bon, soit.

Avec 10 éléments, on n'est pas dans le cas que je citais.

Passe au debuggueur, et regarde au moment du crash les valeurs des variables. Tu crash dans ta fonction swap, regarde i,j, regarde si tu n'as pas piné un pointeur en amont.

Bonjour,

valgrind c'est bien, mais si en plus tu compiles en mode debug (option -g avec gcc/clang) alors tu auras une information plus claire, à savoir où exactement tu écrit trop loin.

J'ai compris d'où venait le problème, ligne 76, "pivot-1" fais que lors de l'utilisation de swap je vais échanger la case -1 et 0, d'où l'overflow, l'ai donc enlevé ce -1 et ça marche mais cela ne me parait pas normal que ce cas puisse ce produire.

D'ou l'avantage du debuggueur !

Il te montre quand ça plante (ou quand tu veux) quelle est la pile d'appel, et tu peux consulter la valeur de chaque variable. Ainsi, tu vois pourquoi tu en es arrivé à ce cas la ! 

duckzed a écrit:

J'ai compris d'où venait le problème, ligne 76, "pivot-1" fais que lors de l'utilisation de swap je vais échanger la case -1 et 0, d'où l'overflow, l'ai donc enlevé ce -1 et ça marche mais cela ne me parait pas normal que ce cas puisse ce produire.

Pourquoi, en regardant ta méthode de partition, le pivot ne pourrait pas être à l'index 0 ? Autrement dit, dans quel cas l n'est-il jamais incrémenté dans la fonction partitionner ?

PicoDev a écrit:

duckzed a écrit:

J'ai compris d'où venait le problème, ligne 76, "pivot-1" fais que lors de l'utilisation de swap je vais échanger la case -1 et 0, d'où l'overflow, l'ai donc enlevé ce -1 et ça marche mais cela ne me parait pas normal que ce cas puisse ce produire.

Pourquoi, en regardant ta méthode de partition, le pivot ne pourrait pas être à l'index 0 ? Autrement dit, dans quel cas l n'est-il jamais incrémenté dans la fonction partitionner ?

 l ne s’incrémente pas si il est le plus petit élément de la partition 

-
Edité par duckzed 25 mars 2017 à 22:52:48

Et ça peut arriver ? Si oui, quand ? Et dans ce cas que faut-il faire ou ne pas faire ?

En fait quand le pivot est le plus petit élément de la liste, on aura une partition à gauche avec le pivot uniquement, et une partition à droite qui appartient à l'ensemble [1,n], ça peut arriver à chaque récursion, et dans ce cas, on va traiter la partie de droite, et vu que i et j sont égaux dans la partie de gauche, on n'a plus besoin d'effectuer de récursion, on sort donc du quicksort (ligne 74), c'est donc tout à fait normal en fait !

Et en mode pas à pas avec le debuger tu vois que ...

En pas à pas ? Avec quel debuger ? Sinon mon programme marche parfaitement du coup je ne vois donc pas ce que je pourrais voir avec un debuger ?

parfaitement c'est un grand mot si tu accèdes hors zone qui t'appartient … il y a un bug, ton programme plante d'ailleur.
Pour trouver un bug, tu peux utiliser un debuger (car c'est prévu pour). Il y a les debuger en mode REPL comme gdb ou lldb, en mode GUI comme DDD ou nemiver (qui ne sont que des front end).

Tu sais qu'à un moment donné un paramètre prend une valeur interdite, pose un point d'arrêt conditionnelle  pour savoir ou quand comment …

$ gdb ./sort 
GNU gdb (Ubuntu 7.11.90.20161005-0ubuntu2)
...
Reading symbols from ./sort...done.
(gdb) break 57 if j<0 || j>10
Breakpoint 1 at 0x555555554b69: file sort.c, line 57.
(gdb) run
Starting program: /home/fred/Projects/tests/sort 
10
9
8
7
6
5
4
3
2
1
0
0 9.000000 0.000000
1 8.000000 0.000000
2 7.000000 0.000000
3 6.000000 0.000000
4 5.000000 0.000000
5 4.000000 0.000000
6 3.000000 0.000000
7 2.000000 0.000000
8 1.000000 0.000000
9 0.000000 0.000000

Breakpoint 2, partitionner (self=0x555555757010, func=0x555555554a1c <comp_ord>, ctx=0x0, i=0, j=-1) at sort.c:57
57	    ssize_t pivot_index = i;
(gdb) n
58	    const struct vec pivot = self->data[i];
(gdb) n
59	    swap(self, pivot_index, j);
(gdb) n
60	    ssize_t l = i;
(gdb) n
62	    for (k = i; k < j; ++k) {
(gdb) n
68	    swap(self, l, j);
(gdb) n
69	    return l;
(gdb) p l
$1 = 0
(gdb) backtrace 
#0  partitionner (self=0x555555757010, func=0x555555554a1c <comp_ord>, ctx=0x0, i=0, j=-1) at sort.c:69
#1  0x0000555555554c91 in quickSort (self=0x555555757010, func=0x555555554a1c <comp_ord>, ctx=0x0, i=0, 
    j=18446744073709551615) at sort.c:75
#2  0x0000555555554cbb in quickSort (self=0x555555757010, func=0x555555554a1c <comp_ord>, ctx=0x0, i=0, j=8) at sort.c:76
#3  0x0000555555554cbb in quickSort (self=0x555555757010, func=0x555555554a1c <comp_ord>, ctx=0x0, i=0, j=9) at sort.c:76
#4  0x0000555555554d23 in vecsetsort (self=0x555555757010, func=0x555555554a1c <comp_ord>, ctx=0x0) at sort.c:83
#5  0x0000555555554fbe in main () at sort.c:129
(gdb) 

....

Donc ici il y a un chemin qui amène à un retour de partitionner valant 0, donc pivot-1 vaut ... non ça ne vaut pas -1 ... c'est quoi comme type size_t ????

Je n'utilise pas de size_t mais des ssize_t. Là j'avoue être complètement perdu... Je ne comprends également pas pourquoi il y aurait un bug, j'ai testé mon projet en réimplantant le quicksort dedans, aucune erreur malgré les nombreux tests que j'ai pu effectuer, modifiant le nombre de points et leurs valeurs.

Bon, le code que tu as posté une fois compilé donne par exemple :

$ ./qsort 
10
9
8
7
6
5
4
3
2
1
0
0 9.000000 0.000000
1 8.000000 0.000000
2 7.000000 0.000000
3 6.000000 0.000000
4 5.000000 0.000000
5 4.000000 0.000000
6 3.000000 0.000000
7 2.000000 0.000000
8 1.000000 0.000000
9 0.000000 0.000000
Segmentation fault

Je viens de le reprendre, de le recompiler et de le retester.

Le prototype de ton quicksort est :

void quickSort(struct vecset *self, comp_func_t func, const void *ctx, size_t i, size_t j);

Si tu donne pivot-1 comme valeur au paramètre j, que pivot vaut 0 alors tu auras -1 casté en size_t … ce qui ne doit pas du tout être ce que tu veux.

Oui c'est ce que j'ai modifier, à la place d'envoyer pivot-1 ligne 76 j'envoie pivot, et je n'ai pas de soucis de seg fault. Suis-je à coté de la plaque ?

Disons simplement que pivot est à la bonne place, il n'a plus besoin de passer par une phase de tri. Si tu l'inclues c'est pas un problème, en se faisant trier il reviendra à la même place (enfin plus ou moins car quicksort n'est pas un tri stable).

Maintenant si pivot vaut 0, cela signifie qu'il 'y a rien à trier du côté gauche, donc que l'appel récursif à quicksort est inutile ; symétriquement si pivot est le dernier élément alors pas la peine de lancer un quicksort à droite. Si tu avais eu un type entier signé alors tu n'aurais pas eu ce problème.