Agenda Hash

agenda.c

#include "agenda.h"

//=== MENU ===//
int8_t menu(void)
{
/*************************
 * Munu geral do sistema *
 *************************/
    
    clrscr();
    printf("\n"\
           " +---------------------------+\n"\
           " |            MENU           |\n"\
           " +---------------------------+\n"\
           " | 1 - Adicionar Contato     |\n"\
           " | 2 - Procurar Contato      |\n"\
           " | 3 - Deletar Contato       |\n"\
           " | 0 - Exit                  |\n"\
           " +---------------------------+\n"\
           "\n OP: ");
    return getchar()-'0';
}



//=== GERAR HASH DO CONTATO===//
int8_t gerarHashContato(pessoa_t* pContato)
{
/*****************************************************
 * Calcula a key com base no MD5 do nome e do email. *
 *****************************************************/
 
    //Soma as cadeias de caracteres
    uint32_t sum = 0;
    char* pNomeMD5 = md5Sum(pContato->nome);      //Gera o MD5 do Nome
    sum += somaASCII(pNomeMD5, 32);
    char* pEmailMD5 = md5Sum(pContato->email);   //Gera o MD5 do E-Mail
    sum += somaASCII(pEmailMD5, 32);
    
    
    //Retorna o resto da divisão da soma os valores ASCIIs pelo tabalho da tabela hash
    return sum % HASH_TABLE_SIZE;
}



//=== TEM COLISAO ===//
int8_t temColisao(int8_t key)
{
/*********************************************
 * Verficação dolisão na "lista" de contatos *
 *********************************************/
 
    if(agenda[key] != NULL)
    {
        if(agenda[key]->status == ATIVO)
        {
            return 1;
        }
    }
    return 0;
}



//=== CADASTRAR CONTATO ===//
pessoa_t* cadastrarContato(void)
{
/***************************************************************************************************
 * Realiza o "cadastro" de uma pessoa (contato), alocando em um endereço de memória.               *
 * Posteriormente esta pessoa (contato) será inserido na agenda por meio da função InserirContato. *
 ***************************************************************************************************/
 
    pessoa_t* pPessoa = (pessoa_t*) malloc(sizeof(pessoa_t));                                      
    
    printf("\n Nome: ");
    scanf("%[^\n]s", pPessoa->nome);
    getchar();

    printf("\n Data de Nascimento:\n");
    printf("  Dia: ");
    scanf("%"SCNu8, &(pPessoa->aniversario.dia));
    printf("  Mes: ");
    scanf("%"SCNu8, &(pPessoa->aniversario.mes));
    printf("  Ano: ");
    scanf("%"SCNd16, &(pPessoa->aniversario.ano));
    getchar();
    
    printf("\n Telefone: ");
    scanf("%[^\n]s", pPessoa->cel);
    getchar();
    
    printf("\n E-Mail: ");
    scanf("%[^\n]s", pPessoa->email);
    getchar();
    
    return pPessoa;
}



//=== INSERIR CONTATO ===//
void inserirContato(pessoa_t* pPessoa)
{
/******************************************************
 *  Insere o contato acastrado na "lista" de contatos *
 ******************************************************/
    
    int8_t key = gerarHashContato(pPessoa); //Gera a KEY padrão do contato
    int8_t i = 0;
    
    while(1) //Tenta fazer a insercao, dequindo o modelo da sondagem linear
    {
        
        if(i == HASH_TABLE_SIZE)
        {
            printf("\n\n === ERRO ===");
            printf("ESTOURO DE TABELA\n");
            key = -1;
            break;
        }
        
        if (temColisao(key)) // se tiver colição, incrementa 1 em "i" e segue a sondagem linear. 
        {
            key = hashSondagemLinear(key, i++, HASH_TABLE_SIZE);
        }
        else // se não tem colisão, add na tabela
        {
            contato_t* pContato = (contato_t*) malloc(sizeof(contato_t));
            
            pContato->pPessoa = pPessoa;
            pContato->status = ATIVO;
            
            agenda[key] = pContato;
            break;
        }
    }
    
    printf("\n Contato inserido na posicao %"PRId8" \n", key);
    getchar();
    return;
}



//=== BUSCAR CONTATO ===//
int8_t buscarContato(void)
{
    clrscr();
    int8_t result;
    pessoa_t pessoa;
    
    printf("===== Buscar Contatos =====\n"\
           "\n Nome do contato: ");
    scanf("%[^\n]s", pessoa.nome);
    getchar();
    
    printf(" E-Mail: ");
    scanf("%[^\n]s", pessoa.email);
    
    int8_t key = gerarHashContato(&pessoa);
    int8_t i = 0;
    while(1)
    {
        //Estouro de tabela
        if(i == HASH_TABLE_SIZE)
        {
            result = NAO_CADASTRADO;
            break;
        }
        
        //Contato não cadastrado
        if(agenda[key] == NULL)
        {
            result = NAO_CADASTRADO;
            break;
        }
        
        //Contato desativado
        if(agenda[key]->status == INATIVO && 
           (!strcmp(pessoa.nome, agenda[key]->pPessoa->nome) && !strcmp(pessoa.email, agenda[key]->pPessoa->email)))
        {
            result = INATIVO;
            break;
        }
        
        //Ainda não é o contrato buscado, pois as informações (uma ou ambas) não batem
        if(strcmp(pessoa.nome, agenda[key]->pPessoa->nome) || strcmp(pessoa.email, agenda[key]->pPessoa->email))
        {
            key = hashSondagemLinear(key, i, HASH_TABLE_SIZE);
        }
        else //se ambas as informações baterem, então é o mesmo contato buscado
        {
            result = key;
            break;
        }
    }
    
    return result;
}



//=== EXIBIR CONTATO ===//
void exibirContato(int8_t key)
{
    if(key == INATIVO)
    {
        printf("\n Contato desativado!\n");
    }
    else if(key == NAO_CADASTRADO)
    {
        printf("\n Contato nao cadastrado!\n");
    }
    else
    {
        printf("\n Nome: %s", agenda[key]->pPessoa->nome);
        printf("\n E-Mail: %s", agenda[key]->pPessoa->email);
        printf("\n Tel: %s", agenda[key]->pPessoa->cel);
        printf("\n Data de Nacimento: %d/%d/%d", agenda[key]->pPessoa->aniversario.dia,
                                                 agenda[key]->pPessoa->aniversario.mes,
                                                 agenda[key]->pPessoa->aniversario.ano);
        printf("\n Key: %i", key);
    }
        
    return;
}



//=== DELETAR CONTATO ===//
void deletarContato(int8_t key)
{
    int8_t resposta;
    
    if(key>=0)
        {
        printf("\n\n Deseja realmente deletar esse contato? S-SIM, N-NAO");
        printf("\n > ");
        resposta = getchar();
        
        if((resposta>'Z') ? resposta-32 == 'S' : resposta == 'S')  
        {
            agenda[key]->status = INATIVO;
            
            printf("\n === Contato removido! ===\n");
        }
    }
    return;
}

agenda.h

#ifndef _AGENDA_H
#define _AGENDA_H

//=== Includes ===//
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include "hash.h"
#include "md5.h"


//=== Defines ===//
#define HASH_TABLE_SIZE     97
#define ATIVO               1
#define INATIVO             -2
#define NAO_CADASTRADO      -1
#define clrscr()            system("@cls||clear")   // Função para limpar a tela que garante a compatibilidade com Windows(CMD), Linux(Bash e ZSH) e OS X(ZSH).


//=== Structs ===//
typedef struct data_   //Cria o tipo data
{
    uint8_t     dia;
    uint8_t     mes;
    uint16_t    ano;
} data_t;

typedef struct pessoa_ //Cria o tipo pessoa
{
    char        nome[80];
    data_t      aniversario;
    char        cel[17];
    char        email[100];
} pessoa_t;

typedef struct contato_  //Cria o tipo memória
{ 
    pessoa_t*   pPessoa;
    int8_t     status; // 1- ATIVO  2- INATIVO (AKA Deletado)
} contato_t;



//=== Global Variables ===//
static contato_t* agenda[HASH_TABLE_SIZE];  //Tabela Hash



//=== Prototypes ===//
int8_t temColisao(int8_t key);              // Função p/ verificar se ha ou não colisão.
                                            /// Caso mude o tamanho da tabela hash (AKA agenda), pode-se fazer necessário alterar o tipo do parãmetro desta função.

int8_t gerarHashContato(pessoa_t* pContato);// Função p/ calcular o Hash do contato.
                                            /// Caso mude o tamanho da tabela hash (AKA agenda), pode-se fazer necessário alterar o tipo do retorno desta função.

pessoa_t* cadastrarContato(void);           // Ao chamar esta função (sem parametros) é solicitado ao usuário que digite as informações do contato,
                                            //o contato é criado (MALOC) e a funçaõ retorna um ponteiro de PESSOA. (para ser passado p/ a MEMORIA).

void inserirContato(pessoa_t* contato);     // Função p/ inserir o contato recem cadastrado na memória da agenda.


int8_t buscarContato(void);                 // Busca, com base no nome, o contato solicitado e retorna a posição dele na agenda.
                                            /// Caso mude o tamanho da tabela hash (AKA agenda), pode-se fazer necessário alterar o tipo do retorno desta função.
                                            
void deletarContato(int8_t key);            // Deleta (inativa) o contato solicitado.
                                            /// Caso mude o tamanho da tabela hash (AKA agenda), pode-se fazer necessário alterar o tipo do parãmetro desta função.

void exibirContato(int8_t key);             // Função que exibe as infomações do contato solicitado no terminal.
                                            /// Caso mude o tamanho da tabela hash (AKA agenda), pode-se fazer necessário alterar o tipo do parãmetro desta função.

int8_t menu(void);                          // Menu de opções.

#endif

hash.c

#include "hash.h"

//=== SOMA ASCII ===//
uint32_t somaASCII(char* pPalavra, uint8_t len)
{
/******************************************************************
 * Retorna soma de todos os caracteres de uma array de caracteres *
 ******************************************************************/
 
    int8_t i;
    uint32_t sum = 0;
    
    for(i=0; i<len; i++)
    {
        sum += pPalavra[i];
    }
    
    return sum;
}

//=== HASH - SONDAGEM LINEAR ===//
int8_t hashSondagemLinear(int8_t key, int8_t i, int8_t hashTableSize)
{
    return (key + i) % hashTableSize;
}

hash.h

#ifndef _HASH_H
#define _HASH_H

//=== Includes ===//
#include <stdint.h>

//=== PROTOTYPES ===//
uint32_t somaASCII(char* pPalavra, uint8_t len);
int8_t hashSondagemLinear(int8_t key, int8_t i, int8_t hashTableSize);
#endif

main.c

//======================================================================================//
//  Desenvolvido por: Vitor Rodrigues Di Toro"                                          //
//  Graduando em Engenharia de Computação - INATEL                                      //
//                                                                                      //
//  Finalidade: Estudo de Hash na disciplina de Algoritmos III                          //
//======================================================================================//

//=================================== OBSERVAÇÕES ======================================//
//  1 - Todas as estruturas criadas criadas tem "_t" no final do nome devido ao POSIX.  // 
//  2 - Toda a codificação segue o padrão ANSI C.                                       //
//======================================================================================//

#include "agenda.h"


//=== MAIN ===//
int main(void)
{
    int8_t opcao = -1;
    int8_t keyAux;
    
    while(opcao!=0)
    {
        clrscr();
        
        opcao = menu();
        getchar();
        
        clrscr();
        
        switch(opcao)
        {
            case 1: // Adicionar Contato
                printf("\n === Adicionar Contato ===\n");
                inserirContato(cadastrarContato());
                break;
            
            case 2: //Procurar Contato
                printf("\n === Procurar Contato ===\n");
                keyAux = buscarContato();
                printf((keyAux>=0)?"\n === Contato Encontrado ===":"");
                exibirContato(keyAux);
                getchar(); //Captura o "ENTER"
                getchar(); //Espero o usuário apertar qualquer tecla p/ continuar
                break;
            
            case 3: //Deletar Contato
                printf("\n === Buscar Contato ===\n");
                keyAux = buscarContato();
                printf((keyAux>=0)?"\n === Contato Encontrado ===":"");
                exibirContato(keyAux);
                getchar(); //Captura o "ENTER"
                deletarContato(keyAux);
                getchar(); //Captura o "ENTER"
                getchar(); //Espero o usuário apertar qualquer tecla p/ continuar
                break;
            
            case 0: //Sair
                for(keyAux=0; keyAux<97; keyAux++)
                {
                    free(agenda[keyAux]);
                }
                break;
                
            default: //Opção inválida
                printf("\n Opcao invalida!\n"\
                       " << Precione qualquer tecla para continuar! >>\n");
                getchar();
                break;
        }
    }
    return 0;
}

md5.c

#include "md5.h"

//=== MD5 ===//
char* md5Sum(char* initial_msg)
{
/*********************************************************************************************************
 * A função calcula o MD5 da string passado como parâmetro e retorna uma "STRING" com código convertido. *
 *********************************************************************************************************/
    uint32_t h0, h1, h2, h3;
    
    size_t initial_len = strlen(initial_msg);
    
    // Message (to prepare)
    uint8_t *msg = NULL;

    // Note: All variables are unsigned 32 bit and wrap modulo 2^32 when calculating

    // r specifies the per-round shift amounts
    uint32_t r[] = {7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
                    5,  9, 14, 20, 5,  9, 14, 20, 5,  9, 14, 20, 5,  9, 14, 20,
                    4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
                    6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21};

    // Use binary integer part of the sines of integers (in radians) as constants// Initialize variables:
    uint32_t k[] = 
    {
        0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
        0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
        0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
        0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
        0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
        0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
        0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
        0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
        0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
        0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
        0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
        0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
        0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
        0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
        0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
        0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
    };

    h0 = 0x67452301;
    h1 = 0xefcdab89;
    h2 = 0x98badcfe;
    h3 = 0x10325476;

    // Pre-processing: adding a single 1 bit
    //append "1" bit to message    
    /* Notice: the input bytes are considered as bits strings,
       where the first bit is the most significant bit of the byte.[37] */

    // Pre-processing: padding with zeros
    //append "0" bit until message length in bit ≡ 448 (mod 512)
    //append length mod (2 pow 64) to message

    int new_len;
    for(new_len = initial_len*8 + 1; new_len%512!=448; new_len++);
    new_len /= 8;

    msg = calloc(new_len + 64, 1); // also appends "0" bits 
                                   // (we alloc also 64 extra bytes...)
    memcpy(msg, initial_msg, initial_len);
    msg[initial_len] = 128; // write the "1" bit

    uint32_t bits_len = 8*initial_len; // note, we append the len
    memcpy(msg + new_len, &bits_len, 4);           // in bits at the end of the buffer

    // Process the message in successive 512-bit chunks:
    //for each 512-bit chunk of message:
    int offset;
    for(offset=0; offset<new_len; offset += (512/8))
    {
        // break chunk into sixteen 32-bit words w[j], 0 ≤ j ≤ 15
        uint32_t *w = (uint32_t *) (msg + offset);
        
        // Initialize hash value for this chunk:
        uint32_t a = h0;
        uint32_t b = h1;
        uint32_t c = h2;
        uint32_t d = h3;
        
        // Main loop:
        uint32_t i;
        for(i = 0; i<64; i++) 
        {
            
            uint32_t f, g;
            
            if (i < 16) 
            {
                f = (b & c) | ((~b) & d);
                g = i;
            }
            else if (i < 32)
            {
                f = (d & b) | ((~d) & c);
                g = (5*i + 1) % 16;
            }
            else if (i < 48)
            {
                f = b ^ c ^ d;
                g = (3*i + 5) % 16;          
            } else
            {
                f = c ^ (b | (~d));
                g = (7*i) % 16;
            }
            
            uint32_t temp = d;
            d = c;
            c = b;
            b = b + LEFTROTATE((a + f + k[i] + w[g]), r[i]);
            a = temp;
            
        }
        
        // Add this chunk's hash to result so far:
        h0 += a;
        h1 += b;
        h2 += c;
        h3 += d;
        
    }
    
    // cleanup
    free(msg);
    
    //var char digest[16] := h0 append h1 append h2 append h3 //(Output is in little-endian)
    uint8_t *p;
    static char str[33];
    char buffer[8];
    
    strcpy(str,"");
    
    p=(uint8_t *)&h0;
    sprintf(buffer,"%2.2x%2.2x%2.2x%2.2x", p[0], p[1], p[2], p[3], h0);
    strcat(str,buffer);
    
    p=(uint8_t *)&h1;
    sprintf(buffer,"%2.2x%2.2x%2.2x%2.2x", p[0], p[1], p[2], p[3], h1);
    strcat(str,buffer);
    
    p=(uint8_t *)&h2;
    sprintf(buffer,"%2.2x%2.2x%2.2x%2.2x", p[0], p[1], p[2], p[3], h2);
    strcat(str,buffer);
    
    p=(uint8_t *)&h3;
    sprintf(buffer,"%2.2x%2.2x%2.2x%2.2x", p[0], p[1], p[2], p[3], h3);
    strcat(str,buffer);
     
    return str;
}

md5.h

#ifndef _MD5_H
#define _MD5_H

//=== INCLUDES ===//
#include <string.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

//=== DEFINES ===//
#define LEFTROTATE(x, c)    (((x) << (c)) | ((x) >> (32 - (c))))

//=== PROTOTYPES ===//
char* md5Sum(char *initial_msg);

#endif