Problème avec bsearch()

Le
JKB
Bonjour à tous,

J'ai un petit problème avec bsearch(), la fonction de comparaison
me renvoyant un segfault. Avant de poster ici, j'ai naturellement
vérifié avec valgrind qu'il n'y avait pas de corruption mémoire,
je n'ai rien trouvé. La même fonction de comparaison fonctionne
parfaitement (sur le même tableau) avec qsort().

J'ai écrit ceci :

static int
fonction_comparaison(const void *argument_1, const void *argument_2)
{
return(strcmp((unsigned char *) (**((struct_objet **) argument_1)).objet,
(unsigned char *) (**((struct_objet **) argument_2)).objet));
}

Le prototype de struct_objet est le suivant :
typedef struct objet
{
enum t_type type;
integer8 extension_type;
void *descripteur_bibliotheque;
volatile long nombre_occurrences;
pthread_mutex_t mutex;
void *objet;
} struct_objet;

Seul nous intéresse ici le pointeur sur le void. En l'occurence,
lorsque l'objet contient une chaîne de caractère, ce pointeur est un
pointeur sur un unsigned char *.

Lorsque cet objet est un tableau, le pointeur tape sur une structure
struct_tableau définie comme :

typedef struct tableau
{
integer8 nombre_elements;
struct_objet **elements;
} struct_tableau;

Le type integer8 est un entier 64 bits.

Le bout de code en question crée un objet tableau contenant
quatre chaînes de caractères.

On a donc une structure S :

struct_objet -> struct_tableau -> elements(4)

Je réécris les fonctions qui posent problème. Il peut s'être
glissées des coquilles car j'ai simplifié les expressions (les
structures en mémoire sont beaucoup plus complexes que cela).

qsort(((struct_tableau *) S->objet)->elements,
(size_t) ((struct_tableau *) S->objet)->nombre_elements,
sizeof(struct_objet *),
fonction_comparaison);

Ce tri fonctionne parfaitement et mon tableau est trié. Je
l'initialise pour mon test avec "key" "value" "i" "j", qsort()
retourne "i" "j" "key" "value".

J'essaie d'accéder à un élément particulier en utilisant bsearch() à
partir d'une autre fonction. J'utilise donc la même fonction
de comparaison. Avant d'appeler bsearch(), je vérifie que le contenu
de mon tableau est bon :

(indice->adresse (chaîne))

0->0x559c5070b3c8 (i)
1->0x559c50712958 (j)
2->0x559c506f0a38 (key)
3->0x559c506f09f8 (value)
0x559c506f0a38->key

Cette sortie est faite par :

for(i = 0; i < ((struct_tableau *) S->objet).nombre_elements;
printf("%d->%p (%s)", i,
(unsigned char *) ((struct_tableau*) S->objet)->elements[i])->objet,
(unsigned char *) ((struct_tableau*) S->objet)->elements[i])->objet,
i++);

Le nombre d'éléments est correct, le contenu des chaînes est bon.
Valgrind ne rale pas.

J'appelle donc bsearch() de la manière suivante (clef est
initialisée un peu plus haut) :

s_objet_element = bsearch((unsigned char *) clef,
((struct_tableau *) S->objet)->elements,
(size_t) ((struct_tableau *) S->objet)->nombre_elements,
sizeof(struct_objet *), fonction_comparaison);

Et je me tape un segfault dans la fonction de comparaison. J'ai donc
investigué un peu plus loin en regardant les adresses passées à
cette fonction.

Lors du premier appel de la fonction de comparaison, le second
argument semble bon (il pointe sur l'une de mes chaînes) :

0x559c506f0a38->key

En revanche, le premier argument pointe sur n'importe quoi :

0x41048c200e47038d->Trying to catch access violation

Le message "Trying to catch access violation" provient du
gestionnaire de signaux.

Là, je ne comprends pas. J'ai beau reprendre les arguments de
bsearch(), je passe bien dans l'ordre la clef, le pointeur sur la
base du tableau, le nombre d'éléments du tableau, la taille de
chaque élément et un pointeur sur la fonction de comparaison. Et les
types sont les bons.

Je sèche. Toute idée sera la bienvenue.

Bien cordialement,

JKB

--
Si votre demande me parvient sur carte perforée, je titiouaillerai très
volontiers une réponse
=> http://grincheux.de-charybde-en-scylla.fr
=> http://loubardes.de-charybde-en-scylla.fr
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Pascal J. Bourguignon
Le #26502603
JKB
Bonjour à tous,
J'ai un petit problème avec bsearch(), la fonction de comparaison
me renvoyant un segfault. Avant de poster ici, j'ai naturellement
vérifié avec valgrind qu'il n'y avait pas de corruption mémoire,
je n'ai rien trouvé. La même fonction de comparaison fonctionne
parfaitement (sur le même tableau) avec qsort().
J'ai écrit ceci :
static int
fonction_comparaison(const void *argument_1, const void *argument_2)
{
return(strcmp((unsigned char *) (**((struct_objet **) argument_1)).objet,
(unsigned char *) (**((struct_objet **) argument_2)).objet));
}
Le prototype de struct_objet est le suivant :
typedef struct objet
{
enum t_type type;
integer8 extension_type;
void *descripteur_bibliotheque;
volatile long nombre_occurrences;
pthread_mutex_t mutex;
void *objet;
} struct_objet;
Seul nous intéresse ici le pointeur sur le void. En l'occurence,
lorsque l'objet contient une chaîne de caractère, ce pointeur est un
pointeur sur un unsigned char *.
Lorsque cet objet est un tableau, le pointeur tape sur une structure
struct_tableau définie comme :
typedef struct tableau
{
integer8 nombre_elements;
struct_objet **elements;
} struct_tableau;
Le type integer8 est un entier 64 bits.
Le bout de code en question crée un objet tableau contenant
quatre chaînes de caractères.
On a donc une structure S :
struct_objet -> struct_tableau -> elements(4)
Je réécris les fonctions qui posent problème. Il peut s'être
glissées des coquilles car j'ai simplifié les expressions (les
structures en mémoire sont beaucoup plus complexes que cela).
qsort(((struct_tableau *) S->objet)->elements,
(size_t) ((struct_tableau *) S->objet)->nombre_elements,
sizeof(struct_objet *),
fonction_comparaison);
Ce tri fonctionne parfaitement et mon tableau est trié. Je
l'initialise pour mon test avec "key" "value" "i" "j", qsort()
retourne "i" "j" "key" "value".
J'essaie d'accéder à un élément particulier en utilisant bsearch() à
partir d'une autre fonction. J'utilise donc la même fonction
de comparaison. Avant d'appeler bsearch(), je vérifie que le contenu
de mon tableau est bon :
(indice->adresse (chaîne))
0->0x559c5070b3c8 (i)
1->0x559c50712958 (j)
2->0x559c506f0a38 (key)
3->0x559c506f09f8 (value)
0x559c506f0a38->key
Cette sortie est faite par :
for(i = 0; i < ((struct_tableau *) S->objet).nombre_elements;
printf("%d->%p (%s)n", i,
(unsigned char *) ((struct_tableau*) S->objet)->elements[i])->objet,
(unsigned char *) ((struct_tableau*) S->objet)->elements[i])->objet,
i++);
Le nombre d'éléments est correct, le contenu des chaînes est bon.
Valgrind ne rale pas.
J'appelle donc bsearch() de la manière suivante (clef est
initialisée un peu plus haut) :
s_objet_element = bsearch((unsigned char *) clef,
((struct_tableau *) S->objet)->elements,
(size_t) ((struct_tableau *) S->objet)->nombre_elements,
sizeof(struct_objet *), fonction_comparaison);
Et je me tape un segfault dans la fonction de comparaison. J'ai donc
investigué un peu plus loin en regardant les adresses passées à
cette fonction.
Lors du premier appel de la fonction de comparaison, le second
argument semble bon (il pointe sur l'une de mes chaînes) :
0x559c506f0a38->key
En revanche, le premier argument pointe sur n'importe quoi :
0x41048c200e47038d->Trying to catch access violation
Le message "Trying to catch access violation" provient du
gestionnaire de signaux.
Là, je ne comprends pas. J'ai beau reprendre les arguments de
bsearch(), je passe bien dans l'ordre la clef, le pointeur sur la
base du tableau, le nombre d'éléments du tableau, la taille de
chaque élément et un pointeur sur la fonction de comparaison. Et les
types sont les bons.
Je sèche. Toute idée sera la bienvenue.

Ça serait plus facile d'aider si tu fournissais un source complet et un
makefile.
--
__Pascal J. Bourguignon__
http://www.informatimago.com
Pascal J. Bourguignon
Le #26502602
JKB Par exemple, c'est complètement idiot d'écrire:
Le type integer8 est un entier 64 bits.

quand le source contiendrait déjà:
typdef int64_t integer8;
--
__Pascal J. Bourguignon__
http://www.informatimago.com
Pascal J. Bourguignon
Le #26502601
JKB
static int
fonction_comparaison(const void *argument_1, const void *argument_2)
{
return(strcmp((unsigned char *) (**((struct_objet **) argument_1)).objet,
(unsigned char *) (**((struct_objet **) argument_2)).objet));
}
Seul nous intéresse ici le pointeur sur le void. En l'occurence,
lorsque l'objet contient une chaîne de caractère, ce pointeur est un
pointeur sur un unsigned char *.
Lorsque cet objet est un tableau, le pointeur tape sur une structure
struct_tableau définie comme :

Alors, trois questions:
1- comment tu compare un tableau avec une chaine?
2- comment tu compare un tableau avec un tableau?
3- où les code implémentant ces comparaisons?
--
__Pascal J. Bourguignon__
http://www.informatimago.com
JKB
Le #26502608
Le Sat, 22 Dec 2018 10:47:46 +0100,
Pascal J. Bourguignon
JKB
static int
fonction_comparaison(const void *argument_1, const void *argument_2)
{
return(strcmp((unsigned char *) (**((struct_objet **) argument_1)).objet,
(unsigned char *) (**((struct_objet **) argument_2)).objet));
}
Seul nous intéresse ici le pointeur sur le void. En l'occurence,
lorsque l'objet contient une chaîne de caractère, ce pointeur est un
pointeur sur un unsigned char *.
Lorsque cet objet est un tableau, le pointeur tape sur une structure
struct_tableau définie comme :

Alors, trois questions:
1- comment tu compare un tableau avec une chaine?
2- comment tu compare un tableau avec un tableau?
3- où les code implémentant ces comparaisons?

Je ne compare que des chaînes entre elles. Je trie les éléments du
tableau en fonction de leur contenu. La fonction est
static int
fonction_comparaison(const void *argument_1, const void *argument_2)
{
return(strcmp((unsigned char *) (**((struct_objet **) argument_1)).objet,
(unsigned char *) (**((struct_objet **) argument_2)).objet));
}
qsort() se démerde parfaitement avec cette fonction. bsearch() est
censé utiliser la même fonction.
Ce qui me chagrine, c'est que les pointeurs passés à la fonction de
comparaison de bsearch() sont mauvais (au moins l'un d'entre eux).
Donc soit je n'ai pas compris comment fonctionne bsearch(), soit il
y a un truc plus tordu mais qui ne fait pas raler valgrind.
JKB
--
Si votre demande me parvient sur carte perforée, je titiouaillerai très
volontiers une réponse...
=> http://grincheux.de-charybde-en-scylla.fr
=> http://loubardes.de-charybde-en-scylla.fr
JKB
Le #26502612
Le Sat, 22 Dec 2018 10:42:42 +0100,
Pascal J. Bourguignon
JKB Par exemple, c'est complètement idiot d'écrire:
Le type integer8 est un entier 64 bits.

quand le source contiendrait déjà:
typdef int64_t integer8;

Celle-là, je l'attendais. Des pans de ce code datent du début des
années 1990 avec des compilos qui ne connaissaient pas int64_t et
interprétaient bizarrement la notation ->. De mémoire, la notation
(*x).y permettait plus d'indirection que x->y parce que les
indirections n'étaient pas faites de la même manière. J'avais
regardé à l'époque l'assembleur VAX généré et les deux indirections
n'étaient pas traitées de la même manière, ce que j'avais trouvé
étrange.
Il y a 250 000 lignes de code et je n'ai pas le temps de remplacer
tous les integer? et real? utilisés pour interfacer des routines
FORTRAN par les types intxx_t. Même remarque pour le remplacement
des (*x).y par des x->y.
Il n'y a aucune ligne de C K&R, mais historiquement, certaines
notations sont restées celles du C ANSI disponible sur un VAX.
Bref, pour un code écrit aujourd'hui, ce serait totalement idiot et
je souscris à ton avis. Mais on n'est pas dans un code écrit
aujourd'hui. Je rajoute une fonction dans un bout de code qui a
presque trente ans.
JKB
--
Si votre demande me parvient sur carte perforée, je titiouaillerai très
volontiers une réponse...
=> http://grincheux.de-charybde-en-scylla.fr
=> http://loubardes.de-charybde-en-scylla.fr
JKB
Le #26502615
Le Sat, 22 Dec 2018 10:41:10 +0100,
Pascal J. Bourguignon
Ça serait plus facile d'aider si tu fournissais un source complet et un
makefile.

Là encore, je ne puis que souscrire, mais ça risque d'être
particulièrement difficile et pas simple à lire, ne serait-ce que
parce qu'il faut allouer toutes les structures en mémoire. Ce que
j'ai indiqué dans mon pseudo-code, c'est la partie émergée de
l'iceberg.
Le code fautif est ici :
http://www.rpl2.fr/cgi-bin/cvsweb/rpl/src/instructions_g2.c?rev=1.65;content-type=text%2Fplain
ligne 568
Merci de ne pas faire de remarque sur l'utilisation des (*x).y qui
ne sont là que pour des raisons historiques, le compilo utilisé au
début du projet ayant du mal avec les -> imbriqués, je pourrai
développer. Je continue avec cette notation sur les anciennes
fonctions du coeur du programme.
JKB
--
Si votre demande me parvient sur carte perforée, je titiouaillerai très
volontiers une réponse...
=> http://grincheux.de-charybde-en-scylla.fr
=> http://loubardes.de-charybde-en-scylla.fr
Samuel DEVULDER
Le #26502623
Le 22/12/2018 à 10:22, JKB a écrit :
typedef struct tableau
{
integer8 nombre_elements;
struct_objet **elements;
} struct_tableau;

1ère remarque: C'est étrange d'avoir struct_object **. Pourquoi une
double indirection? Les objets manipulés sont des structures ou des
pointeurs sur des structures allouées dans le tas ?
On a donc une structure S :
struct_objet -> struct_tableau -> elements(4)

2e remarque: je pige pas. Un struct_objet n'a pas de pointeur sur un
struct_tableau. La 1ère flèche n'a pas de sens pour moi. Je pense sur le
"struct_object" du début est une typo: tu voulais écrire autre chose à
cet endroit.
s_objet_element = bsearch((unsigned char *) clef,
((struct_tableau *) S->objet)->elements,
(size_t) ((struct_tableau *) S->objet)->nombre_elements,
sizeof(struct_objet *), fonction_comparaison);


Hmm, la fonction de comparaison compare deux "struct_object*" (ou **, cf
remarque 1), ca marche très bien pour qsort parce que le tri compare
toujours deux struct_object** entre eux.
Cependant la fonction de comparaison dans bsearch n'est pas du tout la
même! Son 1er argument est la clef (unsigned char*) alors que ton code
attends un (struct_object**). Pas étonannt que ca marche pas!
Les deux fonctions de comparaisons ne peuvent pas être les mêmes.
1) pour qsort il faut comparer deux (struct_object**). Ok c'est ce que
tu as.
2) pour bsearch il faut comparer un (char*) avec un (struct_object**).
C'est là que la bât blesse.
C'est très clair.
a+
sam.
JKB
Le #26502631
Le Sat, 22 Dec 2018 12:14:25 +0100,
Samuel DEVULDER
Le 22/12/2018 à 10:22, JKB a écrit :
typedef struct tableau
{
integer8 nombre_elements;
struct_objet **elements;
} struct_tableau;

1ère remarque: C'est étrange d'avoir struct_object **. Pourquoi une
double indirection? Les objets manipulés sont des structures ou des
pointeurs sur des structures allouées dans le tas ?

C'est un tableau de struct_objet * alloué dynamiquement sur le tas.
...elements[i] contient un pointeur sur un struct_objet *.
On a donc une structure S :
struct_objet -> struct_tableau -> elements(4)

2e remarque: je pige pas. Un struct_objet n'a pas de pointeur sur un
struct_tableau. La 1ère flèche n'a pas de sens pour moi. Je pense sur le
"struct_object" du début est une typo: tu voulais écrire autre chose à
cet endroit.

J'ai été un peu rapide. En fait, struct_objet est une structure
générique qui pointe sur tout un tas d'objets différents au travers
du champ objet qui est un void *. Le champ type de la structure
permet de savoir sur quoi cela pointe. Là encore, si je devais
réécrire ce code aujourd'hui, j'utiliserais à la place du void * une
union, mais je n'ai pas le temps de tout réécrire.
s_objet_element = bsearch((unsigned char *) clef,
((struct_tableau *) S->objet)->elements,
(size_t) ((struct_tableau *) S->objet)->nombre_elements,
sizeof(struct_objet *), fonction_comparaison);

Hmm, la fonction de comparaison compare deux "struct_object*" (ou **, cf
remarque 1), ca marche très bien pour qsort parce que le tri compare
toujours deux struct_object** entre eux.
Cependant la fonction de comparaison dans bsearch n'est pas du tout la
même! Son 1er argument est la clef (unsigned char*) alors que ton code
attends un (struct_object**). Pas étonannt que ca marche pas!
Les deux fonctions de comparaisons ne peuvent pas être les mêmes.
1) pour qsort il faut comparer deux (struct_object**). Ok c'est ce que
tu as.
2) pour bsearch il faut comparer un (char*) avec un (struct_object**).
C'est là que la bât blesse.
C'est très clair.

Rhoh pétard... Oui, maintenant que tu le dis, c'est très clair.
Je vais modifier le truc, ça devrait fonctionner bien mieux.
J'ai pourtant lu et relu cette fichue page de manuel un sacré nombre
de fois sans tilter !
Merci,
JKB
--
Si votre demande me parvient sur carte perforée, je titiouaillerai très
volontiers une réponse...
=> http://grincheux.de-charybde-en-scylla.fr
=> http://loubardes.de-charybde-en-scylla.fr
JKB
Le #26502721
Le Sat, 22 Dec 2018 15:22:44 +0100,
Pascal J. Bourguignon
JKB
J'ai un petit problème avec bsearch(), la fonction de comparaison

En effet, le point précis c'est que la fonction de comparaison de
bsearch n'est pas la même que celle de qsort.
Voir le programme suivant, ce n'est pas difficile d'écrire un code
"minimal" qui démontre le problème et que l'on peut dégoguer de façon
modulaire.
Ensuite, c'est trés facile de faire évoluer le code avec des
rechercher-replacer globaux! (Note par exemple, comment j'ai substitué
les noms idiots comme struct_object et struct_tableau par object_t et
vector_t).

Avec 250000 lignes, ce n'est pas aussi simple. Mais si tu veux le
faire, tu es le bienvenu. Personnellement, je ne touche pas un code
qui fonctionne parfaitement. Juste pour ta gouverne, ces types font
partie du cahier des charges initial et du style d'écriture imposé
lors de la dernière grosse modification de l'outil en 1996.
Enfin, pour s'en sortir, surtout avec du code legacy, il faut absolument
introduire des abstraction fonctionnelles, et ne surtout pas utiliser
partout des accès aux structures et des casts!
Et profiter du C11 et des options sanitize depuis gcc-7, qui abortent au
lieu de continuer l'exécution avec des résultats débiles.
Et utiliser un garbage collector au lieu de se faire chier avec la
gestion de mémoire.

Parfait. On est très loin de la question initiale. Mais puisque tu
m'y invites, je vais juste te répondre.
Mon boulot n'est ni de maintenir ni de pisser du code. Mon boulot,
c'est le traitement du signal et l'électronique analogique. Je veux bien
rajouter une fonction dans un code complexe, parce qu'un thésard
me le demande gentiment, mais je ne suis pas payé pour le faire.
Ce code est entièrement documenté, mais ce que je peux faire en deux
heures parce que je connais l'application, quelqu'un qui est contraint de
se taper d'abord toute la documentation va y mettre plusieurs jours.
Je ne vais donc pas passer du temps que je n'ai pas à changer des noms
de type utilisés il y a trente ans parce que ça te défrise ou que tu
les trouves idiots. De la même manière, je ne vais pas virer les void *
et les casts en pagaille parce qu'on peut faire mieux aujourd'hui
ni les (*x).y utilisés parce que le compilo initialement utilisé
n'arrivait pas à enquiller plus de quatre indirections x->y sans se tirer
une balle dans le pied, enfin dans le pointeur de frame. Tout ces trucs,
je les connais parfaitement, sauf que j'ai d'autres choses à faire que
de modifier ce code. Parce que, figure-toi, si j'avais le temps, je
réécrirais cette application dans un langage plus approprié que le C. Au
hasard, le C++, ce qui éviterait bien des problèmes pour gérer
efficacement les objets et les opérations associées.
Il n'y a pas de garbage collector parce que je me suis fait chier
comme tu dis avec la gestion de la mémoire et qu'il y a un allocateur
à cache particulièrement efficace et thread safe. Je ne vois pas pourquoi
je devrais le virer pour te faire plaisir parce que c'est à la mode.
Donc oui, c'est un vieux code. Oui, les noms de types et de variables
peuvent être étranges. Oui, il y a des bizarreries dans l'écriture.
Oui, je me suis gaufré en lisant la page man de bsearch() alors que
je l'ai relu à plusieurs reprises. Oui, j'ai naturellement fait un
test plus simple avec les mêmes structures provoquant les mêmes
erreurs (et pour cause). Mais oui, ce code donne satisfaction depuis
de longues années, alors il restera ce qu'il est sauf si quelqu'un
décide de le moderniser.
JKB
--
Si votre demande me parvient sur carte perforée, je titiouaillerai très
volontiers une réponse...
=> http://grincheux.de-charybde-en-scylla.fr
=> http://loubardes.de-charybde-en-scylla.fr
Pascal J. Bourguignon
Le #26502744
JKB
Le Sat, 22 Dec 2018 15:22:44 +0100,
Pascal J. Bourguignon
JKB
J'ai un petit problème avec bsearch(), la fonction de comparaison


Oui, je me suis gaufré en lisant la page man de bsearch() alors que
je l'ai relu à plusieurs reprises. Oui, j'ai naturellement fait un
test plus simple avec les mêmes structures provoquant les mêmes
erreurs (et pour cause).

La page man de bsearch n'est pas claire sur cette question.
En particulier, elle utilise la même forme pour compar:
int (*compar) (const void *, const void *)
que celle sur qsort.
Donc je crois que l'erreur que nous avons fait, c'est de passer un
vector_t* comme key, au lieu de passer vector_t**.
au lieu de:
object_t** vector_search(vector_t* that,object_t* key){
return bsearch(key,
that->elements,
(size_t)that->nombre_elements,
sizeof(object_t*),
(compar)object_compare_for_bsearch);}
on devrait écrire:
object_t** vector_search(vector_t* that,object_t* key){
return bsearch(&key,
that->elements,
(size_t)that->nombre_elements,
sizeof(object_t*),
(compar)object_compare_for_qsort);}
--
__Pascal J. Bourguignon__
http://www.informatimago.com
Publicité
Poster une réponse
Anonyme