mysh/subdiv.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "subdiv.h" 

/* --- Fonctions privées traitement valeurs --- */
/**
 * Indique si une chaine est la clef d'un noeud
 * @param node* Le noeud
 * @param char* La mémoire
 * @param char* La clef
 * @return true - Oui/false - Non
 */
boolean is_key(node* n, char* mem, char* key) {
    int i, length = strlen(key);
    //Verif que la clef correspond à celle en param
    for (i = 0; i < length; i++) {
        if (mem[i + n->start] != key[i]) {
            return false;
        }
    }
    //Verif que le caractere suivant est bien un =
    if (mem[i + n->start] != '=') {
        return false;
    }
    return true;
}

/**
 * Cherche une clef
 * @param subdiv* Le gestionnaire de mémoire par subdivision
 * @param char* La mémoire
 * @param char* La clef
 * @return La node correspondante ou NULL si introuvable
 */
node* find_key(subdiv* sd, char* mem, char* key) {
    int length = strlen(key) + 2; //Clef + = + taille min mot
    node* n = NULL;
    //Cherche la clef
    for (int i = 0; i < MEM_SIZE / 2; i++) {
        if (sd->use[i] && sd->mem[i].type == MEMSET && sd->mem[i].length >= length) {
            //Regarde si la clef correspond
            if (is_key(&sd->mem[i], mem, key)) {
                n = &sd->mem[i];
                break;
            }
        }
    }
    return n;
}

/**
 * Récupère la valeur d'un noeid
 * @param node* La noeud
 * @param char* La mémoire
 */
char* parse_val(node* n, char* mem) {
    int pos = 0;
    //Cherche la postion du =
    while (mem[pos + n->start] != '=') {
        pos++;
    }
    pos++;
    //Creation chaine
    char* str = mem + n->start + pos;
    char* val = malloc(sizeof (char) * (n->length - pos + 1));
    memset(val, 0, n->length - pos + 1);
    strncpy(val, str, n->length - pos);
    //Retour
    return val;
}

/* --- Fonctions privées nodes --- */

boolean div_node(subdiv* sd, node* n) {
    node* newn = NULL;
    int i;
    //Verif que la node à diviser est bien libre
    if (n->type != MEMEMPTY) {
        return false;
    }
    //Cherche une node libre
    for (i = 0; i < MEM_SIZE; i++) {
        if (sd->use[i] == 0) {
            newn = &sd->mem[i];
            break;
        }
    }
    //Plus de place
    if (newn == NULL) {
        return false;
    }
    //Setup node
    newn->index = i;
    newn->start = n->start + (n->length / 2);
    newn->end = n->end;
    newn->length = n->length / 2;
    newn->type = MEMEMPTY;
    newn->prev = n->index;
    newn->next = n->next;
    //Modifie node suivant la nouvelle
    if (n->next != -1 || n->next == n->index) {
        sd->mem[n->next].prev = newn->index;
    }
    //Modifie node origine
    n->end = n->start + (n->length / 2);
    n->length /= 2;
    n->next = newn->index;
    //Indique que la node est utilisé
    sd->use[i] = true;
    return true;
}

boolean fusion_node(subdiv* sd, node* n) {
    //Verif que la node et la node suivante sont vide
    if (!(n->type == MEMEMPTY && n->next != -1 && sd->mem[n->next].type == MEMEMPTY)) {
        return false;
    }
    node* n2 = &sd->mem[n->next];
    //Verif qu'elles ont la meme taille
    if (n->length != n2->length) {
        return false;
    }
    //Met à jour la node
    n->end = n2->end;
    n->length *= 2;
    n->next = n2->next;
    if (n2->next != -1 || n2->next == n2->index) {
        sd->mem[n2->next].prev = n->index;
    }
    //Indique que l'autre node n'est plus utilisée
    sd->use[n2->index] = false;
    return true;
}

/* --- Fonctions publiques --- */

void ini_subdiv(subdiv* sd) {
    sd->mem[0] = (node){0, 0, MEM_SIZE, MEM_SIZE, MEMEMPTY, -1, -1};
    sd->use[0] = true;
    for (int i = 1; i < MEM_SIZE / 2; i++) {
        sd->use[i] = false;
    }
}

boolean add_data_subdiv(subdiv* sd, char* mem, char* key, char* data) {
    //Recup taille data
    int length = strlen(data) + strlen(key) + 1;
    //Cherche un espace ou mettre la données
    node* n = &sd->mem[0];
    while (n != NULL) {
        if (n->type == MEMEMPTY && n->length >= length) {
            break;
        }
        //Charge le prochain noeud
        if(n->next == -1 || n->next == n->index){
            n = NULL;
        } else {
            n = &sd->mem[n->next];
        }
    }
    //Si plus de place
    if (n == NULL) {
        return false;
    }
    //Si on peut diviser par deux la place libre et stocker dedans
    if ((n->length / 2) >= length) {
        //On divise la zone en 2
        if (!div_node(sd, n)) {
            return false;
        }
        return add_data_subdiv(sd, mem, key, data);
    }
    //Genere chaine à mettre en mémoire
    char* str = malloc(sizeof (char) * (length + 1));
    memset(str, 0, length + 1);
    snprintf(str, length + 1, "%s=%s", key, data);
    //On maj la node
    n->type = MEMSET;
    n->length = length;
    //On met dans la mémoire
    for (int i = 0; i < length; i++) {
        mem[i + n->start] = str[i];
    }
    //Nettoyage
    free(str);
    return true;
}

boolean add_fdata_subdiv(subdiv* sd, char* mem, char* data) {
    //Recup taille data
    int length = strlen(data);
    //Cherche un espace ou mettre la données
    node* n = &sd->mem[0];
    while (n != NULL) {
        if (n->type == MEMEMPTY && n->length >= length) {
            break;
        }
        //Charge le prochain noeud
        if(n->next == -1 || n->next == n->index){
            n = NULL;
        } else {
            n = &sd->mem[n->next];
        }
    }
    //Si plus de place
    if (n == NULL) {
        return false;
    }
    //Si on peut diviser par deux la place libre et stocker dedans
    if ((n->length / 2) >= length) {
        //On divise la zone en 2
        if (!div_node(sd, n)) {
            return false;
        }
        return add_fdata_subdiv(sd, mem, data);
    }
    //On maj la node
    n->type = MEMSET;
    n->length = length;
    //On met dans la mémoire
    for (int i = 0; i < length; i++) {
        mem[i + n->start] = data[i];
    }
    return true;
}

char* get_data_subdiv(subdiv* sd, char* mem, char* key) {
    node* n = find_key(sd, mem, key);
    //Si pas trouvé la clef
    if (n == NULL) {
        return NULL;
    }
    //Recup valeur
    return parse_val(n, mem);
}

boolean remove_data_subdiv(subdiv* sd, char* mem, char* key) {
    node* n = find_key(sd, mem, key);
    //Si pas trouvé la clef
    if (n == NULL) {
        return false;
    }
    //Marque la node comme vide
    n->length = n->end - n->start;
    n->type = MEMEMPTY;
    //Tente la fusion des noeuds (Algo imparfait)
    n = &sd->mem[0];
    while (n != NULL) {
        //On fusionne avec celui d'après si celui d'avant à une taille différente
        if (n == &sd->mem[0]) {
            if (fusion_node(sd, n)) {
                n = &sd->mem[0];
            } else {
                //Charge le prochain noeud
                if(n->next == -1 || n->next == n->index){
                    n = NULL;
                } else {
                    n = &sd->mem[n->next];
                }
            }
        } else if (sd->mem[n->prev].length != n->length) {
            if (fusion_node(sd, n)) {
                n = &sd->mem[0];
            } else {
                //Charge le prochain noeud
                if(n->next == -1 || n->next == n->index){
                    n = NULL;
                } else {
                    n = &sd->mem[n->next];
                }
            }
        } else {
            //Charge le prochain noeud
            if(n->next == -1 || n->next == n->index){
                n = NULL;
            } else {
                n = &sd->mem[n->next];
            }
        }
    }
    return true;
}

void show_subdiv(subdiv* sd) {
    node* n = &sd->mem[0];
    while (n != NULL) {
        printf("Deb : %d, Fin : %d, Length : %d, Real length : %d, Use : %d\n", n->start, n->end, n->length, n->end - n->start, (int) n->type);
        //Charge le prochain noeud
        if(n->next == -1){
            n = NULL;
        } else {
            n = &sd->mem[n->next];
        }
    }
}

void show_data_subdiv(subdiv* sd, char* mem){
    boolean vide = true;
    node* n = &sd->mem[0];
    while (n != NULL) {
        if(n->type == MEMSET){
            vide = false;
            char* str = malloc(sizeof(char) * (n->length + 1));
            char* deb = mem + n->start;
            memset(str, 0, n->length + 1);
            strncpy(str, deb, n->length);
            printf("%s\n", str);
            free(str);
        }
        //Charge le prochain noeud
        if(n->next == -1 || n->next == n->index){
            n = NULL;
        } else {
            n = &sd->mem[n->next];
        }
    }
    //Si vide
    if(vide){
        printf("Aucune variable en mémoire\n");
    }
}