Untitled

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <signal.h>
#include <math.h>

#define MAX 200

volatile sig_atomic_t sinal = 1;

void executar_sinal () {
    sinal = 0;
}

enum Conflict_Resolutions{
    OPEN,
    LINK,
    CUCKOO,
    NOTHING
};


typedef struct lligada{
    int valor;
    struct lligada *prox;
} *Lista;



int hash_function1 (int elemento, int nr_slots){
    return (elemento % nr_slots);
}

int hash_function2 (int elemento, int nr_slots){   // NÃO ESQUECER DE COLOCAR -lm NO TERMINAL
    return ((int) floor(elemento / nr_slots) % nr_slots);
}


/* --------------------------------- LINEAR PROBING --------------------------------- */

int foi_inserido (char tabela[][MAX], int nr_slots, char elemento[], int chave, char pedido){

    int posicao_livre = -1; // armazena o índice do primeiro slot vazio encontrado
    int posicao_elemento = -1;
    int esta_inserido = 0;

    /*
    if ((tabela[chave][0] == '\0' || tabela[chave][0] == 'D') && pedido == 'I'){
        strncpy(tabela[chave], elemento, MAX);

        printf("%d -> %s\nOK\n", chave, tabela[chave]);

        return 1;
    }
    */

    for (int i = chave, n = 0; n < nr_slots && !esta_inserido; n++){

        if (((strlen(tabela[i]) == 0) || tabela[i][0] == 'D') && posicao_livre == -1 && pedido == 'I'){
            posicao_livre = i;
        }

        if (pedido == 'C' && tabela[i][0] == 'D' && posicao_livre == -1){
            posicao_livre = i;
        }

        if (strcmp(tabela[i], elemento) == 0){
            esta_inserido = 1;
            posicao_elemento = i;

            if (pedido == 'D'){
                memset(tabela[i], '\0', sizeof(tabela[i]));
                tabela[i][0] = 'D';
                return 1;
            }

            if (pedido == 'C'){
                if (posicao_livre != -1){
                    memcpy(tabela[posicao_livre], tabela[i], strlen(tabela[i]) + 1);
                    memset(tabela[i], '\0', sizeof(tabela[i]));
                    tabela[i][0] = 'D';
                    return posicao_livre;
                }

                return i;
            }

        }

        if ((i + 1) == nr_slots){
            i = 0;
        }

        else{
            i++;
        }

    }

    if (pedido == 'C' && !esta_inserido) return -1;
    
    if (pedido == 'D' && !esta_inserido) return 0;
    
    if (posicao_livre != -1 && !esta_inserido){
        memcpy(tabela[posicao_livre], elemento, strlen(elemento) + 1);
        printf("%d -> %s\nOK\n", posicao_livre, tabela[posicao_livre]);
        return 1;
    }

    if (posicao_livre != -1 && esta_inserido && posicao_elemento > -1){
        memcpy(tabela[posicao_livre], elemento, strlen(elemento) + 1);
        memset(tabela[posicao_elemento], '\0', sizeof(tabela[posicao_elemento]));
        printf("%s EXISTS\n", elemento);
        return 1;
    }

    if (posicao_livre == -1 && esta_inserido){
        printf("%s EXISTS\n", elemento);
        return 1;
    }

    return esta_inserido;
}


void inserir_elemento (char tabela[][MAX], int nr_slots, char elemento[], enum Conflict_Resolutions resolucao, int chave){

    if (resolucao == OPEN){
        if (!foi_inserido(tabela, nr_slots, elemento, chave, 'I')) printf("GIVING UP!\n");
    }

}

void mostrar_tabela (char tabela[][MAX], int nr_slots){

    for(int i = 0; i < nr_slots; i++){
        if (strlen(tabela[i]) > 0){
            printf("%d\t%s", i, tabela[i]);
            putchar('\n');
        }
    }

}

void linear_probing (char tabela[][MAX], int nr_slots){

    signal(SIGINT, executar_sinal);

    while(sinal){

        char pedido;  // pedir para inserir um elemento, remover um elemento, verificar um elemento ou imprimir a tabela (omitindo slots vazios)
        char elemento[MAX] = ""; // pode ter o caracter 'D'
        char linha[200];

        if (fgets(linha, MAX, stdin) == NULL) exit(EXIT_FAILURE);
        
        sscanf(linha, "%c", &pedido);

        if (pedido == 'P') mostrar_tabela(tabela, nr_slots);

        else{

            sscanf(linha, "%c %s", &pedido, elemento);

            int valor = atoi(elemento); // converte a string elemento num inteiro
            int chave = hash_function1(valor, nr_slots);

            if (pedido == 'I') inserir_elemento(tabela, nr_slots, elemento, OPEN, chave);
            

            else if (pedido == 'D'){
                if (foi_inserido(tabela, nr_slots, elemento, chave, 'D')) printf("OK\n");
                else printf("NO\n");
            }

            else if (pedido == 'C'){
                int sucesso = foi_inserido(tabela, nr_slots, elemento, chave, 'C');

                if (sucesso != -1) printf("%d\n", sucesso);
                else printf("NO\n");
            }

        }  

    }

}

/* --------------------------------- LINKED LISTS --------------------------------- */

int percorre_lista (Lista lista_ligada, int elemento){

    int esta_na_lista = 0;

    if (lista_ligada == NULL) return 0;
    
    while (lista_ligada != NULL){
        if (lista_ligada->valor == elemento){
            esta_na_lista = 1;
            break;
        }

        lista_ligada = lista_ligada->prox;
    }

    return esta_na_lista;
}

int remove_lista (Lista *array_listas, Lista cabeca, int elemento){

    if (*array_listas == NULL) return 0;
    
    if ((*array_listas)->valor == elemento){
        Lista cabeca_atual = *array_listas;
        *array_listas = (*array_listas)->prox;
        free(cabeca_atual);
        return 1;
    }

    while (cabeca->prox != NULL){
        if ((cabeca->prox)->valor == elemento){
            Lista a_remover = cabeca->prox;
            cabeca->prox = (cabeca->prox)->prox;
            free(a_remover);
            return 1;
        }

        cabeca = cabeca->prox;
    }

    return 0;
}

int inserir_lista (Lista *array_listas, Lista cabeca, int elemento){

    int esta_inserido = 0;

    if (cabeca == NULL){
        Lista novo_elemento = malloc(sizeof(struct lligada));
        novo_elemento->valor = elemento;
        novo_elemento->prox = NULL;
        *array_listas = novo_elemento;
        return 1;
    }

    esta_inserido = percorre_lista(cabeca, elemento);

    if (!esta_inserido){
        Lista novo_elemento = malloc(sizeof(struct lligada));
        novo_elemento->valor = elemento;
        novo_elemento->prox = cabeca;
        *array_listas = novo_elemento;
        return 1;
    }

    else return 0;
    
}

void mostra_listas (Lista array_listas, int indice){

    if (array_listas != NULL) printf("%d ", indice);
    else return;
    
    while (array_listas != NULL){
        printf("%d", array_listas->valor);
        if (array_listas->prox == NULL) putchar('\n');
        else putchar(' ');
        array_listas = array_listas->prox;
    }

}


void linked_lists (Lista *array_listas[], int nr_slots){

    signal(SIGINT, executar_sinal);

    while (sinal){

        char pedido;
        int valor;
        char linha[MAX];

        if (fgets(linha, MAX, stdin) == NULL) exit(EXIT_FAILURE);
        
        sscanf(linha, "%c", &pedido);

        if(pedido == 'P'){
            for (int i = 0; i < nr_slots; i++){
                mostra_listas(*array_listas[i], i);
            }
        }

        else{

            sscanf(linha, "%c %d", &pedido, &valor);

            int chave = hash_function1(valor, nr_slots);

            if (pedido == 'I'){
                int foi_inserido = 0;
                foi_inserido = inserir_lista(array_listas[chave], *array_listas[chave], valor);

                if (foi_inserido) printf("%d -> %d\nOK\n", chave, valor);
                else printf("%d EXISTS\n", valor);
                
            }

            else if (pedido == 'C'){
                if (percorre_lista(*array_listas[chave], valor)) printf("%d\n", chave);
                else printf("NO\n");     
            }

            else if (pedido == 'D'){
                if (remove_lista(array_listas[chave], *array_listas[chave], valor)) printf("OK\n");
                else printf("NO\n");
            }

        }

    }


    for (int i = 0; i < nr_slots; i++){
        for (; *array_listas[i] != NULL;){
            Lista proxima = (*array_listas[i])->prox;
            free(*array_listas[i]); // 'free' à cabeça da lista
            *array_listas[i] = proxima;
        }
    }

}


/* -------------------------------------- MAIN -------------------------------------- */

int main(){

    int nr_slots;

    char *opcao = malloc(10 * sizeof(char));

    enum Conflict_Resolutions resolucao;

    if (scanf("%d", &nr_slots) != 1){
        exit(EXIT_FAILURE);
    }

    if (scanf("%s", opcao) != 1){
        exit(EXIT_FAILURE);
    }

    char tabela_open[nr_slots][MAX];

    Lista *array_listas[nr_slots];
    Lista listas_cabecas[nr_slots];

    if (strcmp(opcao, "OPEN") == 0){
        resolucao = OPEN;
    }

    else if (strcmp(opcao, "LINK") == 0){
        resolucao = LINK;
    }

    else if (strcmp(opcao, "CUCKOO") == 0){
        resolucao = CUCKOO;
    }

    else{
        resolucao = NOTHING;
    }

    free(opcao);

    switch(resolucao){
        case OPEN:
            for (int i = 0; i < nr_slots; i++){
                tabela_open[i][0] = '\0';
            }
            linear_probing(tabela_open, nr_slots);
            break;
        case LINK:
            for (int i = 0; i < nr_slots; i++){
                listas_cabecas[i] = NULL;
                array_listas[i] = &listas_cabecas[i];
            }
            linked_lists(array_listas, nr_slots);
            break;
        case CUCKOO:
            printf("\nCUCKOO\n");
            break;
        default:
            break;
    }

    return 0;
}