Au chapitre 71, nous avons commencé à voir les instructions
de base pour lire et écrire les données dans un tableau. Dans ce nouveau
chapitre, nous allons voir d’autres fonctions pour utiliser un tableau. Le
tableau est décrit dans une structure qui ne contient que la clé et une valeur
toutes les deux sur 4 octets. Bien sûr, on peut adapter ces 2 zones à d’autres
valeurs mais il faudra modifier les instructions ldr et str en conséquence.
Dans ce programme triTable.s, je commence à respecter les normes
préconisées pour l’utilisation des registres : x0 à x7 pour les paramètres
x8 à x18 pour les données intermédiaires et les autres pour les données à conserver.
Dans le code nous commençons par charger une table de 90
postes avec une clé aléatoire dans la plage 1,50 et une valeur contenant le N0
d’enregistrement.la routine insertionTable se contente de charger la clé et la valeur
à l’indice de la table donné par le nombre de poste déjà stockés (si 3 postes
stockés, le nouveau stockage s’effectue à l’indice 3 : les 3 premiers
étant stockés aux indices 0, 1 et 2) et retourne dans x0 le nouveau nombre de postes.
Nous gardons une marge de 10 postes pour pouvoir effectuer des insertions de
postes. Comme les zones à charger ont une longueur de 4 octets, il faut faire
attention aux instructions en mettant bien les registres de type w et pas les
registres de type x. Bien sûr pour les zones de 8 octets, il faudra utiliser
les registres en x.
Ensuite nous affichons toute la table en effectuant une
boucle puis nous effectuons une recherche sequentielle dans la table et nous
affichons le résultat.
Ensuite nous plaçons la routine de tri. C’est un tri Shell issu
d’un programme en java proposé par Robert Sedgewick dans son livre sur les
algorithmes. C’est un tri moins performant que le tri rapide mais il est plus
facile à programmer et il comporte moins de situations défavorables.
Nous affichons à nouveau la table pour vérifier le bon
fonctionnement du tri sur les clés et sur les valeurs.
Puis nous effectuons une recherche dichotomique sur la table
triée et nous terminons par une routine d’insertion qui respecte l’ordre de tri
des clés.
Dans le programme hashTable.s nous utilisons une fonction de
hachage pour calculer l’indice de poste où stocker un enregistrement. Nous
allons utiliser une chaine de caractères comme clé. Pour simplifier et examiner
les cas de collision, nous utiliserons une table avec 10 postes seulement.
L’insertion s’effectue en appelant la fonction de hachage d’une
chaine de caractère et qui va retourner un nombre compris entre 0 et 9 qui va
servir d’indice pour accèder à un poste de la table. Si une clé est déjà
stockée dans ce poste, nous cherchons le premier poste vide supérieur pour y
inserer les nouvelles valeurs. Si l’indice dépasse le nombre maxi de postes de
la table, la recherche continue au poste 0. Pour être sûr que la recherche d’un
poste vide soit toujours fructueuse, il faut que la table ne contienne qu’un %
du nombre total de poste. (voir la théorie pour avoir le % le plus correct
possible).
Vous remarquerez que c’est l’occasion d’utiliser l’instruction
particulière csinc qui suivant le résultat de la comparaison prend la valeur d’un
registre ou l’incrément d’un autre (ou du même). Ici dès que l’on atteint le maximum de poste s, on remet l’indice à zéro avec le registre spécial xzr :
astucieux non ?
La fonction de recherche consiste à calculer le N° de poste
avec la même fonction de hachage. Puis si le poste est vide on retourne non
trouvé, si le poste est rempli, on teste si les 2 chaines servant de clé sont
identiques et sinon on balaye la table jusqu à trouver la bonne clé ou un poste
vide.
Cette solution permet de trouver très rapidement des valeurs
dans une table à la condition que la fonction de hachage donne des valeurs bien
différentes et que la table ait un taux moyen de remplissage.
Exemple du résultat d’affichage de la table du programme :
Affichagetable
N° : 0 clé : 4264681
valeur : 110
N° : 1 clé : 4264675
valeur : 50
N° : 2 clé : 0 valeur
: 0
N° : 3 clé : 0 valeur
: 0
N° : 4 clé : 0 valeur
: 0
N° : 5 clé : 4264686
valeur : 60
N° : 6 clé : 4264688
valeur : 70
N° : 7 clé : 0 valeur
: 0
N° : 8 clé : 0 valeur
: 0
N° : 9 clé : 0 valeur
: 0
Dans le programme suivant hashlistTable, nous utilisons une
autre solution. En cas de collision, nous utilisons des listes chainées pour
stocker tous les enregistrements qui donnent la même valeur de poste. Ainsi même
si la table a un fort taux de remplissage, la recherche d’une clé ne s’effectue
que sur quelques nœuds de chaque liste chainée.
L’affichage suivant montre que pour le poste N°5 nous avons
un pointeur vers une autre valeur.
Affichagetable
N° : 0 clé : 4264773
valeur : 110 suivant : 0
N° : 1 clé : 4264767
valeur : 50 suivant : 0
N° : 2 clé : 0 valeur
: 0 suivant : 0
N° : 3 clé : 0 valeur
: 0 suivant : 0
N° : 4 clé : 0 valeur
: 0 suivant : 0
N° : 5 clé : 4264778
valeur : 60 suivant : 638988288
N° : 5 clé : 4264780
valeur : 70 suivant : 0
N° : 6 clé : 0 valeur
: 0 suivant : 0
N° : 7 clé : 0 valeur
: 0 suivant : 0
N° : 8 clé : 0 valeur
: 0 suivant : 0
N° : 9 clé : 0 valeur
: 0 suivant : 0
