Aquí teneis el enunciado,el header, la plantilla, el test y el resultado (puff, parece que va a ser una entrada algo larga xD).
Bueno, el enunciado dice tal que asi:
Se desea gestionar dinámicamente cierta cantidad de memoria comprendida entre las direcciones (números naturales) 0 y MAX=99 (constante). Para ello se ha pensado en utilizar una estructura como la siguiente:Aquí teneis el header:
typedef struct T_Nodo* T_Manejador; struct T_Nodo { unsigned inicio; unsigned fin; T_Manejador sig; }en la que cada nodo nos indica una zona de memoria continua (desde la dirección inicio hasta la dirección fin, ambas incluidas) disponible en la memoria total (ver figura ejemplo). Inicialmente existirá un único nodo con inicio = 0 y fin = MAX. Esta lista estará ordenada por el valor inicio.
Cuando se necesite obtener cierta cantidad de memoria continua (operación Obtener), se buscará un nodo con tamaño suficiente para conseguir el tamaño solicitado y la información de dicho nodo se verá modificada para reflejar que ahora hay menos memoria disponible. Si se requiere toda la memoria indicada por dicho nodo, éste desaparecerá de la lista.
Cuando se desee devolver un trozo de memoria continua (operación Devolver), se añadirá un nuevo nodo a la lista con la información de la cantidad de memoria continua devuelta. Esta operación puede ocasionar que el trozo de memoria devuelto quede junto a uno o dos disponibles. Esto hay que tenerlo en cuenta en la lista de gestión, de forma que nunca existirán dos nodos seguidos en los que el valor del campo fin del primero sea uno menos que el campo inicio del segundo. Con esto se gestiona lo que se denomina compactación de memoria (dos o tres nodos se transforman en uno).
#ifndef GESTIONMEMORIA_H_
#define GESTIONMEMORIA_H_
typedef struct T_Nodo* T_manejador;
struct T_Nodo {
unsigned inicio;
unsigned fin;
T_manejador sig;
};
// Crea la estructura utilizada para gestionar la memoria disponible.
void Crear(T_manejador* Manejador);
// Destruye la estructura utilizada.
void Destruir(T_manejador* manejador);
/* Devuelve en “dir” la dirección de memoria donde comienza el
* trozo de memoria continua de tamaño “tam” solicitada.
* Si la operación se pudo llevar a cabo, es decir, existe dicho
* trozo, devolvera TRUE en “ok”; FALSE en otro caso.
*/
void Obtener(T_manejador* manejador,unsigned tam, unsigned* dir, unsigned* ok);
/* Devuelve el trozo de memoria continua de tamaño “tam” y que
* comienza en “dir”.
* Se puede suponer que se trata de un trozo obtenido previamente.
*/
void Devolver(T_manejador* manejador,unsigned tam,unsigned dir);
/* Muestra el estado actual de la memoria */
void Mostrar (T_manejador manejador);
#endif /* GESTIONMEMORIA_H_ */
Aquí la plantilla:
#include <stdio.h>
#include <stdlib.h>
#include <GestionMemoria.h>
/* Crea la estructura utilizada para gestionar la memoria disponible. */
void Crear(T_manejador *Manejador) {
}
/* Destruye la estructura utilizada. */
void Destruir(T_manejador* manejador) {
}
/* Devuelve en �dir� la direcci�n de memoria donde comienza el
* trozo de memoria continua de tama�o �tam� solicitada.
* Si la operaci�n se pudo llevar a cabo, es decir, existe dicho
* trozo, devolvera TRUE en �ok�; FALSE en otro caso.
*/
void Obtener(T_manejador* manejador,unsigned tam, unsigned* dir, unsigned* ok) {
}
/* Compacta la memoria juntando bloques contiguos */
void Compactar(T_manejador *manejador) {
}
/* Devuelve el trozo de memoria continua de tama�o �tam� y que
* comienza en �dir�.
* Se puede suponer que se trata de un trozo obtenido previamente.
*/
void Devolver(T_manejador* manejador,unsigned tam,unsigned dir) {
}
/* Muestra el estado actual de la memoria */
void Mostrar (T_manejador manejador) {
}
Aquí el test:
#include <stdio.h>
#include <stdlib.h>
#include <GestionMemoria.h>
int main (int argc, char **argv) {
T_manejador manej;
unsigned ok;
unsigned dir; Crear(&manej);
Mostrar(manej);
Obtener(&manej,50,&dir,&ok);
if (ok) {
Mostrar(manej);
printf("la direccion de comienzo es: %d\n", dir);
} else {
printf("No es posible obtener esa memoria\n");
}
Devolver(&manej, 20,0);
Mostrar (manej);
Obtener(&manej,25,&dir,&ok);
if (ok) {
Mostrar(manej);
printf("la direccion de comienzo es: %d\n", dir);
} else {
printf("No es posible obtener esa memoria\n");
}
Devolver(&manej,10,50);
Mostrar(manej);
Obtener(&manej,25,&dir,&ok);
if (ok) {
Mostrar(manej);
printf("la direccion de comienzo es: %d\n", dir);
} else {
printf("No es posible obtener esa memoria\n"); } Devolver(&manej, 20,75); Mostrar(manej); Destruir(&manej); Mostrar (manej); printf("Fin Programa\n"); //system("PAUSE"); return 0; }
Y por último aquí está la solución.
#include <stdio.h>
#include <stdlib.h>
#include "GestionMemoria.h"
#define MAX 100
/* Crea la estructura utilizada para gestionar la memoria disponible. */
void Crear(T_manejador *Manejador) {
*Manejador=(T_manejador)malloc(sizeof(struct T_Nodo));
(*Manejador)->inicio=0;
(*Manejador)->fin=MAX-1;
(*Manejador)->sig=NULL;
}
/* Destruye la estructura utilizada. */
void Destruir(T_manejador* manejador) {
T_manejador ptr;
while (*manejador != NULL) {
ptr=(*manejador)->sig;
free((void *)*manejador);
*manejador=ptr;
}
}
/* Devuelve en “dir” la dirección de memoria donde comienza el
* trozo de memoria continua de tamaño “tam” solicitada.
* Si la operación se pudo llevar a cabo, es decir, existe dicho
* trozo, devolvera TRUE en “ok”; FALSE en otro caso.
*/
void Obtener(T_manejador* manejador,unsigned tam, unsigned* dir, unsigned* ok) {
int tam_actual,restante;
T_manejador ptr,ant,aux;
*ok=0;
ant=NULL;
ptr=*manejador;
while ((!(*ok)) && (ptr != NULL)) {
tam_actual=ptr->fin-ptr->inicio+1;
if (tam_actual>=tam) {
*dir=ptr->inicio;
*ok=1;
/* Dividir el bloque */
restante=tam_actual-tam;
if (restante) { /* Queda algo de memoria libre, simplemente modificar el contenido */
ptr->inicio=ptr->inicio+tam; /* Nueva direccion de inicio */
}
else {
/* Hay que eliminar el nodo de la lista */
if (ant==NULL) {
aux=ptr->sig;
free((void *)*manejador);
*manejador=aux;
}
else {
/* El bloque esta en medio de la lista */
ant->sig=ptr->sig;
free((void *)ptr);
}
} /* end-else dividir bloque */
} /* end-if bloque encontrado */
else {
ant=ptr;
ptr=ptr->sig;
}
} /* end-while */
}
/* Compacta la memoria juntando bloques contiguos */
void Compactar(T_manejador *manejador) {
T_manejador ptr,aux;
if (*manejador != NULL) { /* Lista no vacia */
ptr=*manejador;
while (ptr->sig != NULL) {
if (ptr->fin+1==ptr->sig->inicio) { /* Hay que compactar */
ptr->fin=ptr->sig->fin;
aux=ptr->sig->sig;
free((void *)ptr->sig);
ptr->sig=aux;
}
else {
ptr=ptr->sig; /* No hay que compactar, avanzar */
}
}
}
}
/* Devuelve el trozo de memoria continua de tamaño “tam” y que
* comienza en “dir”.
* Se puede suponer que se trata de un trozo obtenido previamente.
*/
void Devolver(T_manejador* manejador,unsigned tam,unsigned dir) {
T_manejador ptr,ant,aux;
/* Buscar posicion a insertar */
ptr=*manejador;
ant=NULL;
while ((ptr != NULL) && (dir>ptr->inicio)) {
ant=ptr;
ptr=ptr->sig;
}
if (ant==NULL) {
/* Insertar al comienzo de la lista */
aux=(T_manejador)malloc(sizeof(struct T_Nodo));
aux->inicio=dir;
aux->fin=dir+tam-1;
aux->sig=*manejador;
*manejador=aux;
} else {
/* Insertar en medio o al final de la lista */
aux=(T_manejador)malloc(sizeof(struct T_Nodo));
aux->inicio=dir;
aux->fin=dir+tam-1;
aux->sig=ptr;
ant->sig=aux;
}
/* Hacer compactacion */
Compactar(manejador);
}
/* Muestra el estado actual de la memoria */
void Mostrar (T_manejador manejador) {
printf("------\n");
while (manejador != NULL){
printf("Desde %d a %d: Libre\n", manejador->inicio, manejador->fin);
manejador = manejador->sig;
}
fflush(stdout);
}
Esto ya se empieza a poner algo complicadete, pero espero que le vayais pillando el hilo.
Saludos y hasta otra ;)
No hay comentarios:
Publicar un comentario