Sous-sections
Dans chaque programme qui gère une grande liste d'utilisateurs, la
base de données joue un rôle primordial. C'est pourquoi nous avons
longtemps réfléchi sur la méthode à employer pour gérer cette
base. Notre but est d'en avoir une rapide et occupant peu de place
en mémoire principale (moins de 2 Mo). Nous avions le choix entre
les arbres, les tableaux statiques, les méthodes de hachages. Nous
avons finalement opté pour les arbres. Les tableaux statiques sont
incompatibles avec nos besoins. Il nous est impossible de savoir
le nombre de personnes qui feront partie de notre base de données.
Les méthodes de hachage auraient pu nous convenir : elles sont
très rapides pour la recherche, mais elles ne sont pas compatibles
avec des recherches par tranches car les données ne sont pas
ordonnées selon leur valeur mais selon la valeur de la fonction de
hachage. Par ailleurs, le calcul de la fonction de hachage n'est
pas simple dans notre cas (pour les mêmes raisons que pour les
tableaux statiques la gestion des collisions n'est pas évidente).
Les arbres binaires constituent donc une bonne alternative entre
simplicité et rapidité. Le principal défaut des arbres binaires
est le déséquilibre qui peut engendrer un arbre dégénéré.
L'avantage de la représentation en AVL est que la durée de n'
importe quelle opération, que ce soit ajout, insertion,
suppression ou recherche, et au plus 
où n est le nombre
d'informations stockées. En effet, cela est dû à la présence de
fonctions de rééquilibrage qui opèrent lors d'une insertion ou
d'une suppression et maintiennent ainsi un déséquilibre au maximum
de 1 en valeur absolue (le déséquilibre d'un arbre est calculé en
faisant la différence entre la hauteur du fils droit de la racine
et la hauteur de son fils gauche ; la hauteur étant le nombre de
noeud que l'on rencontre en parcours descendant jusqu' à atteindre
une feuille). Nous utilisons donc l'AVL et toutes les fonctions
qui l'accompagnent (calcul du déséquilibre, rotations ...) pour
contrer ce problème.
Pour " simplifier les choses ", nous avons choisi de représenter
l'objet [base de donnée] (tout du moins, celui représenté en
mémoire) directement par sa propre classe d'objet et ses propres
méthodes qui lui seront appliquées.
La classe Base De Donnée (DB) comprend essentiellement une liste
chaînée et un AVL pour chaque critère selon lesquels on peut
rechercher un utilisateur.
Nous avons 4 critères principaux (Nickname, genre, date
de naissance et ville). Ceci signifie que les opérations
d'insertion et de suppression seront de l'ordre de
.
L'objet DB comporte deux opérations classiques : le constructeur
qui initialise la liste et les arbres à NULL et le destructeur qui
se charge de libérer la mémoire proprement.
Il comporte également une fonction d'insertion (celle
qui stock et insert dans les AVL) et une fonction de recherche qui
retourne une liste chaînée d'objets utilisateurs en fonction d'un
objet utilisateur passé en paramètre (critères plus ou moins vides
selon ce que l'on recherche : c'est la fonction qui gère).
Bien entendu, dans le but d'être propre, les utilisateurs ne sont
représentés qu'une seule fois en mémoire et les arbres
s'entrecroisent sur les pointeurs "data" stockés dans la liste
chaînée.
L'insertion d'un élément dans un AVL classique fonctionne
principalement en insertion en feuille (noeud terminaison d'un
arbre). Dans nos AVL, il est possible d'insérer un élément dans un
noeud interne.
Principe :
Soit " A " l'arbre où l'on désire insérer l'élément " X " de type
pointeur non typé. Précisons que l'algorithme est récursif est que
lorsque l'on parle d'insertion, on relance l'algorithme sur les
paramètres indiqués.
Si A est non NUL Alors :
Si l'élément X est strictement inférieur à l'élément de A,
alors on insère X dans le sous fils gauche de A.
Sinon
Si l'élément X est strictement supérieur à l'élément de A alors :
On insère X dans le sous fils droit de A.
Sinon
On est dans le cas où l'élément de A a la même valeur que X.
On insère X dans la liste chaînée du fils courant.
La modification n'aboutit pas à un déséquilibre de l'arbre.
Sinon
On crée un noeud et on insère X dans sa liste chaînée.
Le nouvel élément se trouve donc en feuille.
La modification aboutit à une modification de l'équilibre dans l'arbre.
On fait ce qu'il faut pour rééquilibrer.
C'est certainement la partie qui a demandé le plus de réflexion
dans la base de données. En définitive, la suppression marche par
adresse. Il faut tout d'abord récupérer l'adresse de l'élément à
supprimer pour pouvoir ensuite lancer la suppression sur tous les
AVL de la base de données.
Principe :
L'algorithme se divise en fait en deux parties :
- La suppression de l'élément en lui-même.
- La suppression des noeuds qui font références à des listes
chaînées référencées plus haut dans l'arborescence.
Rappelons que lors de la suppression dans un AVL classique, elle
peut avoir lieu en feuille mais également plus haut dans
l'arborescence ; et dans ce cas-là, selon le déséquilibre du
noeud, on fait pointer son élément sur le minimum du sous fils
droit ou le maximum du sous fils gauche ; puis ensuite on relance
la suppression sur ce sous-fils pour supprimer le noeud d'où l'on
a remonté l'élément. Dans notre cas, cela a lieu lorsque la liste
chaînée du noeud où a eu lieu la suppression est vide.
Soit A l'arbre dans lequel on lance la recherche et X soit le
pointeur sur élément que l'on veut supprimer soit l'adresse de la
liste chaînée du noeud que l'on veut supprimer. (Les deux
algorithmes se différencient uniquement par la comparaison : " X "
ou " ième(X, 0) ").
Si A est non-nul Alors
Si le premier élément de la liste de A est strictement supérieur à X
(ou supérieur au premier élément de la liste X)
Alors
Lancer la suppression sur le sous fils gauche de A.
Sinon
Si le premier élément de la liste de A est strictement inférieur à X
(ou inférieur au premier élément de la liste X)
Alors
Lancer la suppression sur le sous fils droit de A.
Sinon
Si le premier élément de la liste de A est égal à X
(ou égal au premier élément de la liste X)
Alors
Si A est une feuille Alors
Supprimer X dans la liste de A.
(Supprimer A et rééquilibrer l'arbre.)
Si la liste chaînée de A est vide supprimer A
et rééquilibrer l'arbre.
Sinon
Supprimer X dans la liste de A.
Si la liste de A est vide Alors
Si le déséquilibre de A est -1 Alors
La liste chaînée de A devient le min du
Sous fils droit de A.
On lance la suppression de la liste
Chaînée de A dans son sous-fils droit.
Sinon
La liste chaînée de A devient le Max du
Sous fils gauche de A.
On lance la suppression de la liste
Chaînée de A dans son sous-fils gauche.
Le plutôt simple et répétitif. Cela correspond à une recherche
classique dans un arbre binaire de recherche.
Principe :
En général :
Si le premier élément de la liste de A est supérieur à l'élément X
alors
On relance la recherche sur le sous fils gauche de A.
Sinon
Si le premier élément de la liste de A est inférieur à X alors
On relance la recherche sur le sous fils droit de A.
Sinon
On ajoute à la liste chaînée des résultats, les éléments de la liste
chaînée de A.
Si on recherche un Utilisateur ou un Canal bien précis, par
exemple, on retourne directement le pointeur sur le premier
élément de la liste chaînée de A (vu que chaque Canal et
Utilisateur ont chacun un nom unique, A ne peut qu'avoir un
élément par liste chaînée) : ce principe sera utilisé lorsque l'on
recherchera à supprimer un élément ; On récupère le pointeur que
l'on met en paramètre de la fonction que l'on a rencontrée
précédemment.
Par contre, ci on recherche l'ensemble des Utilisateurs ou Canaux
qui ont leurs noms qui commencent comme l'élément X, on utilisera
plutôt ce principe d'algorithme ci-dessous : (on utilisera une
fonction de comparaison et d'inclusion de liste chaînée)
Si le premier élément de la liste de A est supérieur à l'élément X
alors
On relance la recherche sur le sous fils gauche de A
Sinon
Si le premier élément de la liste de A est supérieur
à l'élément X alors
On relance la recherche sur le sous fils droit de A
Sinon
Si le premier élément de la liste de A commence par X
(X inclus dans A) alors
Ajouter les éléments de la liste chaînée de A dans la
liste chaînée des résultats.
Si le sous fils gauche de A est non nul et si le premier
élément de sa liste commence par X alors
Poursuivre la recherche sur le sous fils gauche de A.
Si le sous fils droit de A est non nul et si le premier
élément de sa liste commence par X alors
Poursuivre la recherche sur le sous fils droit de A.
Dans cette partie, nous allons décrire les différentes fonctions
élaborées selon les besoins du server de YooGoo.
- int add_canal(canal *new_canal)
- :
Cette fonction sert à ajouter un objet " canal "à la base de
donnée.
Elle retourne 0 si l'opération s'est correctement effectuée,
sinon elle retourne 1 s'il existe déjà, elle retourne 2 si le
pointeur sur objet " canal " est à NUL et elle retourne 3 si
la base de données est déjà en activité critique (Ajout ou Suppression).
Dans les cas où elle retourne une autre valeur que 0, elle se charge
d'appeler le destructeur de l'objet.
- int del_canal(canal *canal)
- :
Cette fonction sert à détruire un objet " canal " dans la
base de données. Elle retourne 0 en cas de succès, 2 si le
pointeur sur objet " canal " est à NUL et 3 si la base de
donnée est en activité critique.
- int canal_exists(char *canal_name)
- :
Cette fonction sert à tester si un canal du nom désigné
existe déjà (en C, l' équivalent du vrai booléen est un
entier non nul et nul pour l'équivalent de faut).
- t_elt *search_canal(canal mycanal)
- :
Cette fonction retourne une liste chaînée dont les éléments
sont des objets canaux dont les noms commencent par le nom
de celui mis en paramètres.
- canal *search_canal_by_name(char *canal_name)
- :
Cette fonction retourne un pointeur sur l'objet canal s'il
est trouvé dans la base de données, sinon elle retourne NUL
(sert principalement à trouver un pointeur pour ensuite relancer
la suppression ou bien encore tester si l'objet de ce nom existe
déjà).
- t_elt *search_canal_by_profil(char *canal_name)
- :
Cette fonction retourne une liste chaînée des objets " canal "
dont les noms commencent comme le nom mis en paramètres (Cf
principe d'algo n°2 de recherche). Elle fait appel à la fonction
t_elt *search_canal(canal mycanal).
- int add_user(user *new_user)
- :
Cette fonction retourne 0 si l' insertion dans la base de données
s' est bien passée. Elle retourne 1 si l' objet existe déjà, 2
si le pointeur sur objet " user " mis en paramètre est NUL et elle
retourne 3 si la base de données est en activité
critique.
- int del_user(user *user_todel)
- :
Cette fonction supprime l'objet mis en paramètre dans la base de
donnée.
- int user_exists(char *user_name)
- :
Cette fonction retourne 1 si un objet " user " a une propriété
Nick égale à la chaîne de caractères mise en paramètres.
- t_elt *search_user(user myuser)
- :
Cette fonction recherche un utilisateur selon le remplissage
des critères de celui mis en paramètre. Si la propriété " Nick "
est remplie, alors le moteur de recherche effectue sa tâche sur
l'arbre de classement " sort_by_nick ", sinon si la propriété
" City " est remplie alors il effectue sa recherche dans
" sort_by_city ", sinon si la propriété " Birth " est remplie
alors il effectue sa recherche dans " sort_by_birth " et dans l'
arbre " sort_by_gender " en dernier ressort (il n'y a que 3 genres
définis (0 : homme, 1 : femme, 2 : non défini) donc nous avons affaire
à un arbre de 3 noeuds à grandes listes chaînées et la recherche se ferait
en partie linéairement et donc plus longuement qu' avec un arbre
binaire de recherche). Pour la recherche par " Nick " ou encore par
" city ", la comparaison des noms se fait selon si les chaînes de
caractères commencent de la même manière. Pour les critères nous
utilisons des macros :
- DB_USER_NICK_EMPTY pour une propriété " Nick " vide.
- DB_USER_GENDER_EMPTY pour une propriété " Gender " vide.
- DB_USER_BIRTH_EMPTY pour une propriété " Birth " vide.
- DB_USER_CITY_EMPTY pour une propriété " City " vide.
- int add_user_online(user *new_user)
- :
Cette fonction retourne 0 si l' insertion de l'objet " user " mis
en paramètre a été correctement effectuée dans l' arbre " sort_by_status "
sinon elle retourne 1 si un objet avec la même propriété " Name " existe
déjà, retourne 2 si le pointeur de l'objet " user " mis en paramètre est
NUL et retourne 3 si la base de donné est en activité critique. Dans le
case de retour de valeurs autres que 0, elle se charge d' appeler le
destructeur de l'objet mis en paramètre.
- int del_user_online(user *user_todel)
- :
Cette fonction permet de supprimer un objet " user " de l'arbre " sort_by_status
".
Elle retourne 0 en cas de réussite, 2 si le pointeur mis en paramètre
est NUL et 3 si la base de données est en activité
critique.
- int user_online_exists(char *user_name)
- :
Cette fonction test si un objet " user " dont la propriété " name " est
celle mise en paramètre existe déjà dans l'arbre " sort_by_status".
- t_elt *users_connected_list()
- :
Cette fonction retourne une liste chaînée des objets " user " recherchés
dans l' arbre " sort_by_nick " et qui ont leur propriétés " Status"
différentes de " Offline ".
- t_elt *users_list()
- :
Cette fonction retourne une liste chaînée de l' ensemble des utilisateurs
de la base de données. Elle sert surtout à la sauvegarde de la base de
donnée en mémoire morte.
- int initialize()
- :
Cette fonction fait appel à une fonction de chargement de fichier qui
permet de récupérer les différents profils d' utilisateurs sauvegardés en
mémoire morte.
- i_node *get_node(int i)
- :
Cette fonction permet de récupérer les AVL selon un index mis en paramètre.
Pour ce dernier, nous utilisons les macros ainsi définies :
- DB_NAVL_SORT_USER_BY_NICK : permet de récupérer "sort_by_nick"
- DB_NAVL_SORT_USER_BY_GENDER : permet de récupérer "sort_by_gender"
- DB_NAVL_SORT_USER_BY_BIRTH : permet de récupérer "sort_by_birth"
- DB_NAVL_SORT_USER_BY_CITY : permet de récupérer "sort_by_city"
- DB_NAVL_SORT_USER_CONNECTED : permet de récupérer "sort_by_status"
- DB_NAVL_SORT_CANAL_BY_NAME : permet de récupérer "channels"
comparaisons. Cependant
une adjonction ou une suppression dans un AVL peuvent déséquilibrer
l'arbre. Ainsi, après avoir ajouté (aux feuilles) ou supprimé un
élément dans un AVL, il faut éventuellement le rééquilibrer, tout
en conservant la structure d'arbre binaire de
recherche.
un AVL; supposons que l'adjonction de
l'élément x a lieu sur une feuille de G et qu'elle fait
augmenter de 1 la hauteur de G, et que G reste un AVL (donc
avant l'adjonction, le déséquilibre de G vaut 0).
