2009/CaoCourseTme2: dico.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "dico.h"
#include "hash.h"

/**************************************************************
 Creation d'un dictionnaire possédant 'size' cases
*************************************************************/
dico_root_t *dico_create(unsigned int size)
{
dico_root_t *root = malloc(sizeof(dico_root_t));
if(root == NULL) {
    perror("dico_create");
    exit(1);
}
root->SIZE = size;
root->HTAB = calloc(size, sizeof(dico_item_t *));
if(root->HTAB == NULL) {
    perror("dico_create");
    exit(1);
}
return root;
}

/**************************************************************
 Recherche d'un item de cle 'key' dans le dictionaire 'root'
 - Si l'item existe déjà, on renvoie un pointeur sur cet item.
 - S'il n'existe pas, on le crée, en initialisant le champs
   COUNT à la valeur 0. 
**************************************************************/
dico_item_t *dico_get (dico_root_t *root, char *key)
{
unsigned int index;
dico_item_t *curr;
dico_item_t *item;
unsigned int trouve = 0;

if (key)
    {
        /* calcul de l'index dans le tableau */
        index = hashindex(key) % root->SIZE;

        /* recherche de l'item dans sa liste */
        for (curr = root->HTAB[index] ; curr ; curr = curr->NEXT) {
                if (strcmp (key, curr->KEY) == 0) { 
            trouve = 1;
            item = curr;
        } 
    }
    /* creation d'un item si necessaire */
    if(trouve == 0) {
            item = malloc(  sizeof(struct dico_item_t *) + 
                sizeof(unsigned int) + 
                strlen (key) + 1);
        if(item == NULL) perror("dico_get");
        item->NEXT = root->HTAB[index];
        item->COUNT = 0;
        strcpy(item->KEY, key);
        root->HTAB[index] = item;
    }
    return item;
}
perror ("dico_get");
exit (1);
} 


/***********************************************************
  Création d'un iterateur sur la table de hachage root
************************************************************/
dico_iterator_t *dico_iterator(dico_root_t *root)
{
dico_iterator_t *iter;
if ((iter = malloc (sizeof (dico_iterator_t)))) {
    iter->ROOT = root;
    return iter;
}
perror ("dico_iterator");        /* si malloc rend NULL */
exit (1);
}

/*******************************************************
  Recherche du premier item de la table de hachage 
*******************************************************/
dico_item_t *dico_first (dico_iterator_t *iter)
{
if (iter) {
        /* recherche de la première liste non nulle */
        dico_root_t * root = iter->ROOT;
        for (iter->INDEX = 0;
             (iter->INDEX < root->SIZE) && (root->HTAB[iter->INDEX] == NULL);
             iter->INDEX++);

        /* retour de la fonction, attention le dictionnaire peut être vide */
        if (iter->INDEX >= root->SIZE) return NULL;    
        else return iter->ITEM = root->HTAB[iter->INDEX];
}
return NULL;
} 

/************************************************
 * Recherche de l'item suivant dans iterator  
*************************************************/
dico_item_t *dico_next (dico_iterator_t *iter)
{
if (iter)
    {
        /* pointe sur l'item suivant dans la liste et retour si non nul */
        iter->ITEM = iter->ITEM->NEXT;
        if (iter->ITEM) return iter->ITEM;

        /* recherche de la prochaine liste non nulle */
        dico_root_t * root = iter->ROOT;
        for (iter->INDEX++;
             (iter->INDEX < root->SIZE) && (root->HTAB[iter->INDEX] == NULL);
             iter->INDEX++);

        /* retour de la fonction, attention le dictionnaire peut être vide */
        if (iter->INDEX >= root->SIZE) return NULL;     
        else return iter->ITEM = root->HTAB[iter->INDEX];
    }
    return NULL;
}