cerhu > comp.lang.* > comp.lang.c

JKB (22/12/2018, 11h22)
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.

Bien cordialement,

JKB
Pascal J. Bourguignon (22/12/2018, 11h41)
JKB <jkb> writes:

[..]
> 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 (22/12/2018, 11h42)
JKB <jkb> writes:

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 (22/12/2018, 11h47)
JKB <jkb> writes:

> 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?
JKB (22/12/2018, 11h58)
Le Sat, 22 Dec 2018 10:47:46 +0100,
Pascal J. Bourguignon <pjb> écrivait :
> JKB <jkb> writes:
>> 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
JKB (22/12/2018, 12h09)
Le Sat, 22 Dec 2018 10:42:42 +0100,
Pascal J. Bourguignon <pjb> écrivait :
> JKB <jkb> writes:
> 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
JKB (22/12/2018, 12h30)
Le Sat, 22 Dec 2018 10:41:10 +0100,
Pascal J. Bourguignon <pjb> écrivait :
> Ç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 :
[..]
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
Samuel DEVULDER (22/12/2018, 13h14)
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 (22/12/2018, 13h48)
Le Sat, 22 Dec 2018 12:14:25 +0100,
Samuel DEVULDER <samuel.devulder> écrivait :
> Le 22/12/2018 à 10:22, JKB a écrit :
> 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.

> 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
Pascal J. Bourguignon (22/12/2018, 16h22)
JKB <jkb> writes:
> 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).

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.

------------------------------------------------------------------------
# J'ai gcc-8 dans /usr/local/gcc
# Adapter ou enleve ces variables en fonction de votre environmenet.

LIBS=-lgc
PATH = /usr/local/gcc/bin:/usr/local/bin:/usr/bin:/bin
CFLAGS = -I/usr/local/gcc/include -I/usr/local/include $(sanitize) -g -g3 -ggdb -O0 -std=c11
CXXFLAGS = -I/usr/local/gcc/include -I/usr/local/include $(sanitize) -g -g3 -ggdb -O0
LDFLAGS = -L/usr/local/gcc/lib64 -L/usr/local/gcc/lib -L/usr/local/lib -L/usr/lib -L/lib -rdynamic $(LIBS)
LD_LIBRARY_PATH = /usr/local/gcc/lib64:/usr/local/gcc/lib:/usr/local/lib:/usr/lib:/lib
DYLD_LIBRARY_PATH = $(LD_LIBRARY_PATH)

sanitize = -fsanitize=address \
-fsanitize=null \
-fsanitize=bounds \
-fsanitize=vla-bound \
-fsanitize=object-size \
-fsanitize=unreachable \
-fsanitize=return \
-fsanitize=float-divide-by-zero \
-fsanitize=float-cast-overflow \
-fsanitize=nonnull-attribute \
-fsanitize=returns-nonnull-attribute \
-fsanitize=bool \
-fsanitize=enum \
-fsanitize-address-use-after-scope \
-fsanitize-undefined-trap-on-error \
-fstack-protector-all \
-fstack-check
CC = gcc

all:bsearch
run:bsearch
./bsearch
clean:
-@rm -rf bsearch bsearch.o bsearch.a bsearch.dSYM
bsearch:bsearch.c
$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $<

------------------------------------------------------------------------

#include <stdarg.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <pthread.h>
#include <gc.h>

#ifdef __GNUC__
#include <execinfo.h>
#define MAX_FRAMES 128
void print_backtrace(){
void* buffer[MAX_FRAMES];
int size=backtrace(buffer,MAX_FRAMES);
backtrace_symbols_fd(buffer,size,2);}
#else
void print_backtrace(){}
#endif

int verbose=1;
typedef int64_t integer8;
typedef enum t_type{type_string=574129,type_vector=23707} type_t;

typedef struct object
{
enum t_type type;
integer8 extension_type;
void *descripteur_bibliotheque;
volatile long nombre_occurrences;
pthread_mutex_t mutex;
void *object;
} object_t;

typedef struct vector
{
integer8 capacity;
integer8 nombre_elements;
object_t **elements;
} vector_t;

void error(const char* function,int line,char* message,...){
va_list args;
va_start(args,message);
int size=vsnprintf(NULL,0,message,args);
va_end(args);
char* buffer=GC_MALLOC(size+1);
if(buffer==0){
buffer=message;}
else{
va_start(args,message);
vsnprintf(buffer,size+1,message,args);
va_end(args);
}
fprintf(stderr,"%s:%d: %s\n",function,line,buffer);
print_backtrace();
exit(1);}

#define ERROR(message,...) error(__FILE__,__LINE__,message,##__VA_ARGS__)

void*check_memory(void* mem){
if(mem){return mem;}
ERROR("Out of memory");
return NULL;}

vector_t* vector_new(integer8 capacity){
vector_t* that=check_memory(GC_MALLOC(sizeof(*that)));
that->capacity=capacity;
that->nombre_elements=0;
that->elements=check_memory(GC_MALLOC(sizeof(that->elements[0])*capacity));
return that;}

void vector_add_element(vector_t* that,object_t* element){
if(that->nombre_elements>=that->capacity){
ERROR("out of capacity");}
that->elements[that->nombre_elements++]=element;}

integer8 vector_length(vector_t* that){
return that->nombre_elements;}

object_t* vector_ref(vector_t* that,integer8 index){
if((index<0)||(that->nombre_elements<=index)){
ERROR("out of bound");}
return that->elements[index];}

type_t object_type(object_t* that){
return that->type;}

object_t* object_allocate(type_t type){
object_t* that=check_memory(GC_MALLOC(sizeof(*that)));
that->type=type;
that->extension_type=0;
that->descripteur_bibliotheque=NULL;
that->nombre_occurrences=0;
pthread_mutex_init(&that->mutex,NULL);
that->object=NULL;
return that;}

object_t* object_new_string(char* string){
object_t* that=object_allocate(type_string);
that->object=string;
return that;}

object_t* object_new_vector(vector_t* vector){
object_t* that=object_allocate(type_vector);
that->object=vector;
return that;}

char* object_string(object_t* that){
if(that->type!=type_string){
ERROR("type error, string expected instead of type %d",that->type);}
return that->object;}

vector_t* object_vector(object_t* that){
if(that->type!=type_vector){
ERROR("type error, vector expected instead of type %d",that->type);}
return that->object;}

void vector_free(vector_t* that);
void object_free(object_t* that){
switch(that->type){
case type_string:free(object_string(that)); break;
case type_vector:vector_free(object_vector(that)); break;}
pthread_mutex_destroy(&that->mutex);}

void vector_free(vector_t* that){
while(that->nombre_elements>0){
object_free(vector_ref(that,that->nombre_elements-1));
that->nombre_elements--;}
free(that->elements);
free(that);}

void string_print(char* string){
// TODO: escape \ and " in string:
printf("\"%s\"",string);}

void vector_print(vector_t* that);

void object_print(object_t* that){
switch(object_type(that)){
case type_string:string_print(object_string(that));brea k;
case type_vector:vector_print(object_vector(that));brea k;}}

void vector_print(vector_t* that){
printf("(");
char* sep="";
for(int i=0;i<that->nombre_elements;i++){
printf("%s",sep);
object_print(vector_ref(that,i));
sep=" ";}
printf(")");}

void test(){
object_t* string=object_new_string("Hello");
printf("A string: ");object_print(string);printf("\n");
vector_t* vector=vector_new(8);
vector_add_element(vector,object_new_string("foo") );
vector_add_element(vector,object_new_string("bar") );
vector_add_element(vector,object_new_string("baz") );
printf("A vector: ");vector_print(vector); printf("\n");
object_t* object=object_new_vector(vector);
printf("A vector in an object: ");object_print(object);printf("\n");}

object_t* make_data(){
/* ("foo" ("foo" "bar") "bar" ("bar" "foo" "baz") "baz") */
vector_t* sub;
vector_t* vector=vector_new(8);
vector_add_element(vector,object_new_string("foo") );
sub=vector_new(8);
vector_add_element(sub,object_new_string("foo"));
vector_add_element(sub,object_new_string("bar"));
vector_add_element(vector,object_new_vector(sub));
vector_add_element(vector,object_new_string("bar") );
sub=vector_new(8);
vector_add_element(sub,object_new_string("bar"));
vector_add_element(sub,object_new_string("foo"));
vector_add_element(sub,object_new_string("baz"));
vector_add_element(vector,object_new_vector(sub));
vector_add_element(vector,object_new_string("baz") );
return object_new_vector(vector);}

int vector_compare(vector_t* va,vector_t* vb);

int object_compare_for_sort(object_t** pa,object_t** pb){
object_t* a=*pa;
object_t* b=*pb;
int result=0;
/* strings are smaller than vectors */
switch(object_type(a)){
case type_string:
switch(object_type(b)){
case type_string:
result=strcmp(object_string(a),object_string(b));
break;
case type_vector:
result=-1;
break;}
break;
case type_vector:
switch(object_type(b)){
case type_string:
result=+1;
break;
case type_vector:
result=vector_compare(object_vector(a),object_vect or(b));
break;}
break;}
if(verbose){
printf("compare "); object_print(a); printf(" vs. "); object_print(b); printf(" -> %d\n",result);}
return result;}

int object_compare_for_bsearch(object_t* a,object_t** pb){
return object_compare_for_sort(&a,pb);}

int vector_compare(vector_t* va,vector_t* vb){
integer8 la=vector_length(va);
integer8 lb=vector_length(vb);
integer8 i=0;
object_t* a=vector_ref(va,i);
object_t* b=vector_ref(vb,i);
while((i<la)&&(i<lb)&&(0==object_compare_for_sort( &a,&b))){
i++;}
if(i==la){
if(i==lb){
return 0;}
else{
return -1;}}
else{
return +1;}}

typedef int (*compar) (const void *, const void *);
void vector_sort(vector_t* that){
qsort(that->elements,
(size_t)that->nombre_elements,
sizeof(object_t*),
(compar)object_compare_for_sort);}

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);}

int main(){
if(verbose){
test();}
object_t* object=make_data();
if(verbose){
printf("Before sort: "); object_print(object); printf("\n");}
vector_sort(object_vector(object));
if(verbose){
printf("After sort: "); object_print(object); printf("\n");}
object_t** found=vector_search(object_vector(object),object_n ew_string("bar"));
if(found==NULL){
printf("object bar not found\n");}
else{
printf("object bar found: "); object_print(*found); printf("\n");}
return 0;}

------------------------------------------------------------------------
Pascal J. Bourguignon (22/12/2018, 16h34)
"Pascal J. Bourguignon" <pjb> writes:

> JKB <jkb> writes:
>> 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.


Voici les résultats obtenus:
$ gcc -I/usr/local/gcc/include -I/usr/local/include -fsanitize=address -fsanitize=null -fsanitize=bounds -fsanitize=vla-bound -fsanitize=object-size -fsanitize=unreachable -fsanitize=return -fsanitize=float-divide-by-zero -fsanitize=float-cast-overflow -fsanitize=nonnull-attribute -fsanitize=returns-nonnull-attribute -fsanitize=bool -fsanitize=enum -fsanitize-address-use-after-scope -fsanitize-undefined-trap-on-error -fstack-protector-all -fstack-check -g -g3 -ggdb -O0 -std=c11 -L/usr/local/gcc/lib64 -L/usr/local/gcc/lib -L/usr/local/lib -L/usr/lib -L/lib -rdynamic -lgc -o bsearch bsearch.c
$ ./bsearch
A string: "Hello"
A vector: ("foo" "bar" "baz")
A vector in an object: ("foo" "bar" "baz")
Before sort: ("foo" ("foo" "bar") "bar" ("bar" "foo" "baz") "baz")
compare "foo" vs. ("foo" "bar") -> -1
compare ("bar" "foo" "baz") vs. "baz" -> 1
compare "bar" vs. "baz" -> -1
compare "foo" vs. "bar" -> 1
compare "foo" vs. "baz" -> 1
compare "foo" vs. ("bar" "foo" "baz") -> -1
compare "foo" vs. "bar" -> 1
compare ("foo" "bar") vs. ("bar" "foo" "baz") -> 1
After sort: ("bar" "baz" "foo" ("bar" "foo" "baz") ("foo" "bar"))
compare "bar" vs. "foo" -> -1
compare "bar" vs. "baz" -> -1
compare "bar" vs. "bar" -> 0
object bar found: "bar"
$
JKB (23/12/2018, 00h24)
Le Sat, 22 Dec 2018 15:22:44 +0100,
Pascal J. Bourguignon <pjb> écrivait :
> JKB <jkb> writes:
> 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
Pascal J. Bourguignon (23/12/2018, 10h17)
JKB <jkb> writes:

> Le Sat, 22 Dec 2018 15:22:44 +0100,
> Pascal J. Bourguignon <pjb> écrivait :
> 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);}
Samuel DEVULDER (24/12/2018, 00h04)
Le 22/12/2018 à 15:22, Pascal J. Bourguignon a écrit :
> 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!


Méfiance!! Comme je le dis concernant du code légacy: on ne répare pas
un code qui marche. Le mieux est l'ennemi du bien!

Souvent en faisant mieux, on obtient bien pire parce qu'on considère
comme mieux actuellement n'est pas forcément adapté au codes et aux
machines de l'époque. Exemple: un GC c'est bien de nos jours, mais sur
un ordi monocoeur il bloquera l?exécution de façon imprédictible ce qui
posera des soucis avec un traitement "temps réel".

a+

sam.
Pascal J. Bourguignon (24/12/2018, 03h30)
Samuel DEVULDER <samuel-dot-devulder> writes:

> Le 22/12/2018 à 15:22, Pascal J. Bourguignon a écrit :
> Méfiance!! Comme je le dis concernant du code légacy: on ne répare pas
> un code qui marche. Le mieux est l'ennemi du bien!
> Souvent en faisant mieux, on obtient bien pire parce qu'on considère
> comme mieux actuellement n'est pas forcément adapté au codes etaux
> machines de l'époque. Exemple: un GC c'est bien de nos jours, mais sur
> un ordi monocoeur il bloquera l?exécution de façon imprédictible ce
> qui posera des soucis avec un traitement "temps réel".


On parle de code legacy, pas d'ordinateur legacy.

S'il s'agit de faire tourner de vielles machines, c'est sur, on ne va
pas pouvoir moderniser beaucoup le logiciel. Déjà, il n'y aura pas les
outils, ou ça va être une galère pour compiler les outils récents sur
les vieux systèmes, avec toutes les dépendences, etc.

Mais reprendre du vieux code sur un système moderne, dans la mesure des
besoins, on peu le faire évoluer drastiquement.

Le seul cas où c'est difficile, c'est quand on veut du bogue-pour-bogue,
car il est en effet facile d'éliminer beaucoup de bogues en le faisant
évoluer proprement?

Discussions similaires
Retour de la fonction bsearch

bsearch

Exception avec bsearch

Personne ne sait pour l'exception de bsearch ?


Fuseau horaire GMT +2. Il est actuellement 14h11. | Privacy Policy