La fonction de bibliothèque C bsearch

bsearch, ce doit être en ordre croissant.
Pour comprendre le mécanisme d’une recherche binaire, imaginons que l’on recherche
un mot dans un dictionnaire. Doit-on effectuer une recherche sérielle en commençant
par le premier mot du dictionnaire et en lisant jusqu’à  ce qu’on trouve le mot
recherché ? Bien sûr que non ! La commande LookUp RPG effectue toujours une
recherche sérielle, même si le tableau est ordonné.



Quand on recherche un mot, on va directement à  la page jugée la plus proche
du mot. A l’examen de cette page, trois possibilités se présentent :

1. On a visé juste.

2. Le mot se trouve avant cette page.

3. Le mot se trouve après cette page.



Même si le mot que l’on recherche se trouve avant ou après la page courante,
on a quand même éliminé la recherche dans quelques centaines de pages du dictionnaire.
On peut itérer cette méthode pour trouver rapidement la page recherchée. Comme
chaque étape de ce processus peut éliminer des centaines de pages, elle est
bien plus efficace qu’une recherche purement sérielle, qui n’éliminerait qu’un
mot à  la fois.



Une recherche binaire fonctionne de la même manière que l’exemple précédent.
Elle examine un élément de tableau qui se trouve à  peu près au milieu de l’ensemble
des éléments. Elle détermine ensuite si l’élément de tableau est celui qu’elle
recherche ou s’il se trouve avant ou après celui-ci. Si l’élément de tableau
recherché se trouve avant l’élément courant, la recherche binaire examine l’élément
qui se trouve à  peu près au milieu, entre le début du tableau et l’élément courant.
Si l’élément recherché se trouve après l’élément courant, la recherche binaire
examine un élément de tableau situé à  peu près au milieu, entre l’élément courant
et la fin du tableau. La recherche se poursuit en réduisant le nombre d’éléments
de tableau examinés jusqu’à  ce qu’elle trouve ce qu’elle recherche ou constate
son absence dans le tableau.



Bien entendu, une recherche sérielle sera plus rapide si, par chance, l’élément
recherché est proche du début du tableau. Mais, si les arguments de recherche
sont des valeurs aléatoires, il est évident qu’une recherche sérielle trouvera
en moyenne l’élément correct après avoir recherché la moitié des éléments du
tableau. Une recherche binaire dans un grand tableau sera bien plus rapide que
cela. Supposons, par exemple, un tableau contenant 2.000 éléments triés par
ordre croissant. En moyenne, une recherche sérielle aboutira après avoir examiné
environ 1.000 éléments. Une recherche binaire trouvera l’élément après avoir
examiné 10 éléments de tableau au maximum.



Naturellement, l’amélioration est moins spectaculaire si le nombre d’éléments
de tableau se réduit. Si le tableau n’a que 10 éléments, la méthode de recherche
importe peu. De plus, une recherche binaire doit effectuer plus de travail qu’une
recherche sérielle pour déterminer l’élément suivant à  examiner. Une recherche
sérielle ajoute simplement 1 à  l’index de l’élément précédent examiné. Mais
une recherche binaire détermine le numéro du prochain élément à  examiner en
divisant le nombre des éléments candidats par 2 et en ajoutant le résultat à 
l’index de l’élément candidat de départ. La recherche sérielle ne doit suivre
que l’élément de tableau en cours d’examen. En revanche, la recherche binaire
doit suivre l’élément courant examiné mais aussi les index inférieur et supérieur
de la gamme courante des éléments de tableau candidats. Il en résulte qu’une
recherche binaire n’est pas très avantageuse pour moins de 50 éléments de tableau.





Bien que l’on puisse coder sa propre recherche binaire en RPG ILE, il
est plus facile (et plus sûr !) d’utiliser la fonction de bibliothèque C bsearch



Malheureusement, le RPG ILE n’a pas d’instruction de recherche binaire. Bien
que l’on puisse coder sa propre recherche binaire en RPG ILE, il est plus facile
(et plus sûr !) d’utiliser la fonction de bibliothèque C bsearch. La figure
8 présente la documentation IBM pour cette fonction.



On voit tout de suite que la fonction bsearch est bien plus complexe que la
fonction Log. Mais si l’on comprend cette explication et l’exemple suivant utilisant
la fonction bsearch, on sera près de savoir utiliser les fonctions de bibliothèque
C dans un programme RPG ILE. Prêt ? Partez !



Le #include et le prototype C pour la fonction bsearch apparaissent en A, figure
8. Bien qu’un programme RPG ILE ne puisse pas faire /Copy (l’équivalent RPG
ILE du #include C) des membres qui incluent l’équivalent RPG ILE du membre source,
il est néanmoins utile de savoir que le membre STDLIB dans le fichier physique
source QCLE/H contient quelques informations critiques utiles aux programmes
C. Nous verrons dans un moment pourquoi il en est ainsi.



Le prototype démarre avec void *bsearch. Rappelons qu’une fonction qui renvoie
void ne renvoie pas une valeur. Bien qu’elle inclue void, cette fonction renvoie
quand même un pointeur. Le caractère * qui précède le nom de la fonction (bsearch)
fait partie de ce qui est renvoyé par la fonction. Autrement dit, la fonction
bsearch renvoie void *, qui est un pointeur vers un type quelconque d’objet
C. En E, figure 8, on peut voir une description de cette valeur de renvoi. Cette
documentation indique que la valeur de renvoi est un pointeur vers l’élément
de tableau que l’on recherchait. Elle indique en outre que si l’élément de tableau
recherché n’est pas trouvé, le pointeur renvoyé sera NULL.



Le prototype en A définit cinq paramètres qui doivent être transmis vers la
fonction bsearch. Le premier paramètre est défini comme const void *key. La
description du paramètre commence par le mot-clé const. Je décrirai très bientôt
ce que signifie const. Le type réel de ce paramètre est void *. Cela signifie
que c’est un pointeur vers un objet C de n’importe quel type.



Le mot-clé const qui précède la spécification void * est utile pour des paramètres
qui sont des pointeurs. Rappelons que les paramètres C sont toujours transmis
par valeur. Il s’en suit que la fonction peut modifier en toute sécurité le
paramètre, sans modifier l’objet original. Cependant, chaque fois qu’un pointeur
est transmis, la fonction invoquée peut être capable d’utiliser le pointeur
pour accéder à  l’objet C sur lequel il pointe. La fonction pourrait alors modifier
cet objet. Le mot-clé constest une assurance (qui n’est pas donnée à  100 % par
logiciel) que la fonction ne modifiera pas l’objet sur lequel le paramètre pointe.
En C, nous voyons que ce paramètre (dont le nom officiel est key) est la valeur
que l’on recherche dans le tableau.



Le second paramètre (base) est également un pointeur. A nouveau, le mot-clé
const nous assure que la fonction bsearch ne modifiera pas l’objet sur lequel
on pointe. La description en C nous dit que c’est un pointeur vers le début
du tableau.



Le troisième paramètre (num) a un type de size_t. Un coup d’oeil rapide aux types
de base de la figure 2 indique que size_t n’est pas l’un d’eux. Mais alors qu’est
size_t ? Nous nous souvenons qu’en A, figure 8, un programmeur C doit coder
#include
[STDLIB.H] pour utiliser cette fonction bsearch. Cela correspond au membre STDLIB
dans un fichier physique source QCLE/H. Ce membre contient (en partie) les lignes
de code suivantes :



#ifndef __size_t

#define __size_t

typedef unsigned int size_t

#endif



La directive typdef définit size_t comme un unsigned int (entier non signé). Cela
signifie que chaque fois qu’on code size_t dans un programme C qui a spécifié
#include [STDLIB.H], on spécifie en réalité unsigned int. La figure 2 montre que
ce type correspond à  un type ILE de U avec 10 chiffres et 0 positions décimales.
Donc, bien qu’un programmeur RPG ne puisse pas utiliser directement les membres
#include qu’un programmeur C doit utiliser, il est parfois utile d’examiner ces
membres pour obtenir les informations nécessaires. La description en B, figure
8, indique clairement que ce paramètre (dont le nom officiel est num) est le nombre
d’éléments du tableau. Toujours en B, on voit que le tableau doit être disposé
en ordre croissant.



Le quatrième paramètre (size) est également défini pour avoir le type size_t (et,
par conséquent, unsigned int). La description en B, figure 8, nous indique que
ce paramètre est la taille en octets de chaque élément de tableau.



Le cinquième élément défini dans le prototype en A est un peu compliqué. D’abord,
son type est int. La figure 2 nous indique qu’il s’agit d’un type RPG ILE I avec
10 chiffres et 0 positions décimales. Le nom officiel de ce paramètre est (*compare).
Chaque fois qu’un nom est spécifié comme (*quelque_chose), c’est en fait un pointeur
vers une fonction. Dans notre cas, le nom officiel (pas le nom réel) de la fonction
est compare. Ce paramètre est en réalité un pointeur vers une fonction qui renvoie
un type int (ou ILE RPG 10I 0). Cette fonction doit en principe être fournie (c’est-à -dire
écrite) par l’utilisateur de la fonction bsearch, et donc le paramètre est en
réalité un pointeur vers une procédure écrite par l’utilisateur. En RPG ILE, un
pointeur de procédure doit être identifié avec le mot-clé ProcPtr (procédure pointer).
Nous verrons comment cela fonctionne dans l’exemple suivant.



Comme ce paramètre pointe vers une fonction (ou procédure ILE), le prototype doit
dire quelle valeur est renvoyée par la fonction et quels paramètres celle-ci requiert.
Le type int précédant le nom de fonction officiel indique que cette fonction renvoie
une valeur int. Revenons une fois encore à  la figure 2 : elle indique que c’est
un type RPG I avec 10 chiffres et 0 positions décimales. Les paramètres qui sont
transmis à  cette procédure écrite par l’utilisateur sont définis en suivant le
nom officiel de (*compare). Ils sont définis de la manière suivante :



(const void *key, const void *element)



La fonction compare nécessite deux paramètres. Le premier paramètre (key) est
un type C de void * et c’est par conséquent un pointeur vers un objet d’un type
quelconque. Sa description, en D figure 8, indique que ce paramètre est un pointeur
vers la valeur clé (c’est-à -dire la valeur recherchée).



Le second paramètre (element) requis par la fonction compare est également un
pointeur vers un objet de type quelconque. La description en D dit que c’est un
pointeur vers un élément de tableau.



Les quelques dernières phrases, en D, expliquent l’action que cette fonction doit
effectuer et la valeur qui doit être renvoyée. On peut alors voir que la fonction
doit comparer la valeur clé à  l’élément de tableau et définir la valeur de renvoi
selon le résultat de cette comparaison. Elle doit mettre la valeur de renvoi à 
0 si la valeur clé est égale à  l’élément de tableau. Elle doit donner un nombre
négatif à  cette valeur si la valeur clé est inférieure à  l’élément de tableau.
Enfin, elle doit donner un nombre positif à  cette valeur si la valeur clé est
supérieure à  l’élément de tableau.



On notera au passage la polyvalence de cette fonction bsearch. Comme la fonction
compare est écrite par l’utilisateur, la fonction bsearch elle-même n’exige pas
de connaissance du format des éléments de tableau. Le seul logiciel qui a besoin
de cette connaissance à  l’exécution de la fonction bsearch est la fonction compare,
écrite par l’utilisateur. Cela permet à  bsearch d’effectuer une recherche binaire
sur des tableaux où les éléments sont d’un type quelconque. La fonction compare
peut même réaliser son propre ordre de collationnement. Elle pourrait, par exemple,
faire des opérations de comparaison ne distinguant pas les majuscules des minuscules,
et la fonction bsearch fonctionnerait bien tant que le tableau serait disposé
en ordre croissant, sans distinguer les majuscules des minuscules.

Voyons à  présent un exemple utilisant réellement la fonction bsearch.