Gerenciamento de Área de Alocação Dinâmica (Listas Encadeadas) [C/C++]

Gerenciamento de Área de Alocação Dinâmica (Listas Encadeadas)

Publicado por Danilo Azevedo (última atualização em 23/07/2014)

[ Hits: 2.915 ]

Download gereciador_de_memoria.zip

0 0

Denuncie Favoritos Indicar

Implementação de um sistema de gerenciamento de trechos livres e ocupados de uma área de alocação dinâmica de memória.

A área de alocação será chamada de buffer. O buffer será formado por N slots. Cada slot tem um índice, que varia de 0 a N - 1. Inicialmente o buffer será considerado vazio. O programa receberá solicitações de operações sobre o buffer, como solicitações para alocar um conjunto de slots (contíguos), desalocar os slots alocados em uma solicitação o anterior ou solicitar informações sobre área de alocação. O índice do slot onde uma área alocada ou livre inicia será chamado o índice inicial daquela área.

O tamanho N do buffer (numero de slots) deverá ser uma constante no programa. Inicialmente deve-se atribuir o valor 20 a esta constante. Posteriormente, no entanto, o valor desta constante poderá ser alterado.

Para a implementação deste exercício, deve-se utilizar listas implementadas com apontadores.

Os formatos de entrada e saída do programa estão indicados nas seções a seguir. O programa deve ler da entrada padrão e escrever na saída padrão.

Segue no anexo informações de como usar o código e o programa.

Esconder código-fonte

/* UNIVERSIDADE FEDERAL DA BAHIA
CURSO: BACHARELADO EM CIENCIA DA COMPUTACAO
DISCIPLINA: ESTRUTURA DE DADOS E ALGORITMOS
ALUNO: DANILO AZEVEDO SANTOS - MATRICULA:209200256

*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
//#include <conio.h>

typedef struct blocoLista{
    int id;
    int inicio;
    int tamanho;
    //char id2;
    struct blocoLista *prox, *ant;
    }blocoLista, *Lista;


typedef struct identificador{
    int chave;
    struct identificador *prox;
    }identificador, *ListaInt;

#define MAX 20
#define vazio -1

/* DECLARACOES DE FUNCOES */

bool consultaListaId(ListaInt *i, int x);
bool criaLista(ListaInt *i, int x);
bool iniciarListas(ListaInt *i, Lista *l);
bool insere_Lista(Lista *l, int id, int tamanho);
Lista areasLivre(Lista *l);
Lista areasOcupadas(Lista *l);
Lista buscaBloco(Lista *l, int id);
Lista consultaBestFit(Lista *l, int tam);
Lista consultaFirstFit(Lista *l, int tam);
Lista consultaLista(Lista *l, int id);
Lista consultaWorstFit(Lista *l, int tam);
Lista defragmentacao(Lista *l);
Lista retirar_lista(Lista *l, int x);
bool retira_desalocacao(Lista *l, int id);
int verEspaco(Lista *l);
void corrigirPosicao(Lista *l);
void experimento(Lista *l, ListaInt *i, int num);
void inicializar(Lista *l);

Lista funcao_teste(Lista *l);

/*                      */


int main (){

    int i, j, tam_entrada, id, tam; char operacao, id_aloc[30], tam_aloc[5], id_area, entrada[30];
    Lista lista, aux; ListaInt listaint;

    iniciarListas(&listaint,&lista);
    inicializar(&lista);

    while(1){ //LOOP DO ESCOPO DE REPETICAO P/ SAIR ENTRE 'e'

    aux=NULL;
    fflush(stdin);
    gets(entrada);
    operacao = entrada[0];//IDENTIFICADOR DE OPERACAO

{//if's
if(operacao == 'a'){ // VERIFICANDO O TIPO DE ENTRADA
        id = 0; tam = 0;
    i = 2; j = 0;
    while(entrada[i] != ' '){// EXTRAINDO O IDENTIFICADOR DE ALOCACAO
    id_aloc[j] = entrada[i];
    i++;
    j++;
    }
    id_aloc[j]='{FONTE}';
    id = atoi(id_aloc); //CONVERTE ID_ALOC DE CHAR PARA INTEIRO
    i = strlen(id_aloc) + 3; // TAMANHO DO IDENTIFICADOR DE ALOCACAO + 2 + 1 - PELO ESPACO
    j = 0;

    while(entrada[i] != ' '){//EXTRAINDO O TAMANHO DA ALOCACAO
    tam_aloc[j] = entrada[i];
    i++;
    j++;
    }
    tam_aloc[j] ='{FONTE}';
    tam = atoi(tam_aloc);
    tam_entrada = strlen(entrada);
    id_area = entrada[tam_entrada+vazio];

    }//FIM 'a'

if(operacao == 'c'){
    i = 2;  j = 0;
    while(entrada[i]!= '{FONTE}'){
    id_aloc[j] =entrada[i];
    j++; i++;
    }
    id_aloc[j] = '{FONTE}';
    id=atoi(id_aloc);
    }//FIM 'c'

if(operacao == 'f'){
    i = 2;  j = 0;
    while(entrada[i]!= '{FONTE}'){
    id_aloc[j] = entrada[i];
    j++; i++;
    }
    id = atoi(id_aloc);
    }//FIM 'f'

if(operacao == 'x'){
    i = 2;  j = 0;
    while(entrada[i]!= '{FONTE}'){
    id_aloc[j] =entrada[i];
    j++; i++;
    }
    id = atoi(id_aloc);
    }//FIM 'x'
}

    switch (operacao){

    case 'a':{

    if((consultaListaId(&listaint,id))||((verEspaco(&lista)) == MAX)||(tam > (MAX -(verEspaco(&lista)))) || (id < 0 || tam < 0))
    printf("nao foi possivel alocar %d\n",id);
    else{
    switch (id_area){
            case 'b':
            aux = consultaBestFit(&lista,tam);
            insere_Lista(&aux,id,tam);
            criaLista(&listaint,id);
            break;

            case 'f':
            aux = consultaFirstFit(&lista,tam);
            insere_Lista(&aux,id,tam);
            criaLista(&listaint,id);
            break;

            case 'w':
            aux = consultaWorstFit(&lista,tam);
            insere_Lista(&aux,id,tam);
            criaLista(&listaint,id);
            break;

            default:
            printf("nao foi possivel alocar %d\n",id);
            break;
            }
                }
                    }

    break;

    case 'c': buscaBloco(&lista,id);

    break;

    case 'd': defragmentacao(&lista);
              corrigirPosicao(&lista);

    break;

    case 'e':exit(0);


    case 'f':
    if(!consultaListaId(&listaint,id))
    printf("\n");
    else
    retira_desalocacao(&lista,id);

    break;

    case 'l':areasLivre(&lista);


    break;

    case 'o':areasOcupadas(&lista);

    break;


    case 'x': experimento(&lista,&listaint,id);
    break;
//
    case 'q':funcao_teste(&lista);// USADO SOMENTE PARA TESTE DE CONSTRUCAO DO PROGRAMA
    break;

    default:

    break;
    }
            }
                return 0;
                        }



bool iniciarListas(ListaInt *i, Lista *l){ // INICIALIZAR LISTAS PARA FUNCAO "MAIN"
     (*l) = NULL;
     (*i) = NULL;
    return true;
    }


bool insere_Lista(Lista *l, int id, int tamanho){ //INSERE SOLICITACAO DE ALOCACAO

    blocoLista *p;
    Lista aux=NULL;

    if((*l)->tamanho >= tamanho){
        if(tamanho == (*l)->tamanho){
            (*l)->id = id;

            return true;
            }
        else{

        p = (blocoLista*)malloc(sizeof(blocoLista));

        if (!p){
        printf("nao foi possivel alocar %d",id);
        return false;
    }
        aux = (*l);
        aux -> inicio = aux->inicio;
        aux->id = id;
        p->tamanho = aux->tamanho - tamanho;
        aux->tamanho = tamanho;
        p->prox = aux->prox;
        aux->prox = p;  p->ant = aux;
        p->id = vazio;  p->inicio = p->ant->tamanho + p->ant->inicio;

        return true;
            }
        }
    return true;
    }


Lista areasLivre(Lista *l){
    Lista p;
for(p=(*l); p!=NULL; p=p->prox){
    if(p->id == vazio ){
    printf("%d %d",p->inicio,p->tamanho);
        printf("\n");
    }
    }
    return NULL;
    }


Lista areasOcupadas(Lista *l){
    Lista p;
for(p=(*l); p!=NULL; p=p->prox){
    if(p->id != vazio ){
    printf("%d %d",p->inicio,p->tamanho);
        printf("\n");
    }
    }
    return NULL;
    }


Lista buscaBloco(Lista *l, int id){//CONSULTA PARA IDENTIFICACAO DO BLOCO
    Lista p=NULL;

    for(p=(*l);p->prox!=NULL; p=p->prox){
        if(id == p->id){
            printf("%d\n",p->inicio);
            return p;
            }
        }
    if((p->prox == NULL)&&(id != p->id))
    printf("requisicao nao atendida");
    return p;
    }


Lista consultaLista(Lista *l, int id){
    Lista p;

    for(p=(*l);(p)&&(p->id != id); p=p->prox);
    return p;
    }


Lista consultaBestFit(Lista *l, int tam){ //BUSCA BLOCO COM MENOR TAMANHO
    Lista p, aux=NULL;
    int soma = 0, menor = (MAX+1);

    //se for vazio
 for(p=(*l); p!=NULL; p = p->prox){
     soma = soma + p->tamanho;
     if(p->id == vazio){
        if((p->tamanho < menor)&&(p->tamanho >= tam)){

            menor = p->tamanho;
            aux = p;

            }
                }
                    }
 if(soma == MAX)
    return aux;

    return NULL;

    }


Lista consultaFirstFit(Lista *l, int tam){//BUSCA BLOCO COM MENOR INDICE
    Lista p = NULL, aux;
    int soma = 0, menor = MAX+1;
    // vazio

for(p=(*l); p!=NULL; p = p->prox){
    soma = soma + p->tamanho;
    if(p->id == vazio){
        if(p->tamanho >= tam){
            if(p->inicio < menor){
            menor = p->inicio;
            aux = p;
            }
                }
                    }
                        }
        if(soma == MAX)
        return aux;

    return NULL;
    }


Lista consultaWorstFit(Lista *l, int tam){ // BUSCA BLOCO COM MAIOR TAMANHO
    Lista p, aux;
    int soma = 0, maior = 0;

    //se for vazio
 for(p=(*l); p!=NULL; p = p->prox){
     soma = soma + p->tamanho;
     if(p->id == vazio){
        if(p->tamanho > maior){
            if(p->tamanho >= tam){
            maior = p->tamanho;
            aux = p;
        }
            }
                }
                    }
 if(soma == MAX)
    return aux;

    return NULL;

    }


int verEspaco(Lista *l){//VERIFICA TAMANHO DE ESPACOS OCUPADOS/LIVRES
    Lista p; int soma = 0;

    for(p=(*l);p!=NULL; p=p->prox){
    if(p->id !=vazio)
    soma += p->tamanho;
    }
    return soma;
    }


void inicializar(Lista *l){  //INICIALIZAR BLOCO DE ALOCACAO JÁ PREENCHIDO
         blocoLista *p;
    p = (blocoLista*)malloc(sizeof(blocoLista));

    p->prox = *l;   p->ant = NULL;
    p->id = vazio;  p->inicio = 0; p->tamanho = MAX;
    (*l) = p;
    }


bool retira_desalocacao(Lista *l, int id){ // FUNCAO PARA DESALOCACAO
        Lista p, aux;
    p = consultaLista(&(*l),id);
    p->id = vazio;

    if(p->prox->id == vazio){// verificação de blocos adjacentes depois do **prox
    p->tamanho = p->prox->tamanho + p->tamanho;
    aux = p->prox;
    p->prox = aux->prox;

    if(aux->prox != NULL)
    aux->prox->ant = p;


    free(aux);
    return (*l);
    }

    if(p->ant){
    if(p->ant->id == vazio){ // verificação de blocos adjacentes antes do **ant
    p->tamanho = p->ant->tamanho + p->tamanho;

    if(p->inicio > p->ant->inicio)
    p-> inicio = p->ant->inicio;

    aux = p->ant;
    p->ant = aux->ant;
    aux->ant->prox = p;
    free(aux);
    return (*l);
        }
    }
    return (*l);
        }


// FUNCOES PARA DEFRAGMENTACAO

Lista retirar_lista(Lista *l, int x){

    Lista p, aux;
    p = consultaLista(&(*l),x);

    if(p->prox == NULL){
        if(p->ant == NULL){
            (*l) = p->prox;
            free(p);
            return (*l);
            }

    aux = p->ant;
    aux->prox = p->prox;
    free(p);
    return (*l);
    }

    if(p->ant == NULL){
    (*l) = p->prox;
    p->prox->ant = NULL;
    free(p);
    return (*l);
    }
    else{
    aux = p->ant;
    aux->prox = p->prox;
    p->prox->ant = aux;
    free(p);
    return (*l);

        }

        return (*l);
    }


Lista defragmentacao(Lista *l){
    blocoLista *p;
    Lista aux, aux2 = *l;
    int soma = 0;

    p = (blocoLista*)malloc(sizeof(blocoLista));

    for(aux=(*l);(aux); aux = aux->prox){//REALIZANDO A SOMA DO TAMANHO DE ESPACOS VAZIOS
        if(aux->id == vazio){
            soma += aux->tamanho;


            }
        }
    for(aux=(*l);(aux); aux = aux->prox){// DELETANDO ESPAÇOS VAZIOS
        if(aux->id == vazio){
            retirar_lista(&(*l),aux->id);

            }
    }

    while(aux2->prox!=NULL){
        aux2=aux2->prox;
        }
                        // CONSTRUINDO UM NOVO ESPACO VAZIO
    p->tamanho = soma;
    p->inicio = 0; // INDICE TEMPORARIO
    p->prox = aux2->prox;
    p->ant = aux2;
    p->id = vazio;
    aux2->prox = p;

    return p;
}


void corrigirPosicao(Lista *l){
    Lista aux;

    for(aux=(*l); aux!=NULL; aux = aux->prox){// CORRIGINDO POSICOES
    if(aux->ant == NULL){
        aux->inicio = 0;
                }
        else{
        aux->inicio = (aux->ant->inicio + aux->ant->tamanho);
            }
                }
                    }


void experimento(Lista *l, ListaInt *k, int num){
    int i, j, tam_entrada, id, tam, cont = 0;
    char operacao, id_aloc[30], tam_aloc[5], id_area, entrada[30];
    Lista lista=(*l), aux, p; ListaInt listaint = (*k);
    int a=0, b=0, c=0, d=0, soma=0;
    float media = 0;

    while( cont < num){

    fflush(stdin);gets(entrada);
    operacao = entrada[0];
if(operacao == 'a'){
    id = 0; tam = 0;
    i = 2; j = 0;
    while(entrada[i] != ' '){
    id_aloc[j] = entrada[i];
    i++;
    j++;
    }
    id_aloc[j]='{FONTE}';
    id = atoi(id_aloc);
    i = strlen(id_aloc) + 3;
    j = 0;

    while(entrada[i] != ' '){
    tam_aloc[j] = entrada[i];
    i++;
    j++;
    }
    tam_aloc[j] ='{FONTE}';
    tam = atoi(tam_aloc);
    tam_entrada = strlen(entrada);
    id_area = entrada[tam_entrada+vazio];

}

if(operacao == 'f'){
    i = 2;  j = 0;
    while(entrada[i]!= '{FONTE}'){
    id_aloc[j] = entrada[i];
    j++; i++;
    }
    id = atoi(id_aloc);
    }//FIM 'f'

switch (operacao){

    case 'a':{

    if((consultaListaId(&listaint,id))||((verEspaco(&lista)) == MAX)||(tam > (MAX -(verEspaco(&lista)))) || (id < 0 || tam < 0)){

    b++;
    }
    else{
    switch (id_area){
            case 'b':
            aux = consultaBestFit(&lista,tam);
            insere_Lista(&aux,id,tam);
            criaLista(&listaint,id);
            a++;
            break;

            case 'f':
            aux = consultaFirstFit(&lista,tam);
            insere_Lista(&aux,id,tam);
            criaLista(&listaint,id);
            a++;
            break;

            case 'w':
            aux = consultaWorstFit(&lista,tam);
            insere_Lista(&aux,id,tam);
            criaLista(&listaint,id);
            a++;
            break;

            default:

            b++;
            break;
            }
                }
                    }

    break;

    case 'f':if(!consultaLista(&lista,id))
                b++;
            else
            retira_desalocacao(&lista,id);
            a++;
    break;

    default:
    b++;
    break;

        } cont++;
            }

for(p=(*l); p!=NULL; p=p->prox){// areas livres
    if(p->id == vazio ){
        soma = soma + p->tamanho;
        c++;
        }
    if(p->id != vazio ){

        d++;
        }
        }

    media = soma/c;

printf("numero total de solicitacoes: %d\n",num);
printf("numero de solicitacoes atendidas: %d\n",a);
printf("numero de slots ocupados: %d\n",d);
printf("numero total de slots livres: %d\n",c);
printf("media do numero de slots nas areas livres: %.1f\n",media);

                    }



//



// LISTA AUXILIAR PARA GUARDAR OS IDENTIFICADORES


bool criaLista(ListaInt *i, int x){
    identificador *p;
    p = (identificador*)malloc(sizeof(identificador));
    if(!p){
    //printf("nao foi possivel alocar %d",x);
    return false;
    }
    p->prox = *i;
    *i = p;
    p->chave = x;
    return true;
    }


bool consultaListaId(ListaInt *i, int x){
    ListaInt p;

    for(p=(*i); p!=NULL; p = p->prox){
    if(p->chave == x){
    return true;
    }
    }
    return false;
    }


//

Lista funcao_teste(Lista *l){//CONSULTA PARA IDENTIFICACAO DO BLOCO
    Lista p;

    for(p=(*l); p!=NULL; p = p->prox){
        printf("%d\n",p->inicio);

            }
            return p;
        }

Scripts recomendados

Google Code Jam 2010 - Africa Classification Round

[C] Listas Duplamente Encadeadas

Biblioteca ctype.h

Jogo defutebol simples (com gráficos)

Aplicção em C++

Comentários

Nenhum comentário foi encontrado.