Ficheros dispersos en C

Ficheros dispersos en C

En programación, un fichero disperso es un tipo de archivo que intenta utilizar de una forma más eficiente el espacio del sistema de archivos, especialmente, cuando el espacio asignado a los archivos es muy pequeño y, en su mayor parte, está vacío.

Mi objetivo, en éste artículo, es dejaros un código de ejemplo de un fichero disperso basado en una estructura de arrays dinámicos de una dimensión. Por supuesto, esta propuesta es parte de una práctica que realicé en la universidad. Como siempre, sería bueno que los lectores añadiésen en los comentarios sus observaciones y propuestas alternativas.

Comenzamos por el código .h:

#ifndef FDISP_CHAR_TYPO

#define FDISP_CHAR_TYPO

struct fd_char_typo   {
	char *cadena;
   };

typedef struct fd_char_rep *fd_char;

//  ---------------------------------------------------------------------

fd_char fd_char_nuev (char fichero [15], int num_cubetas, int tam_cubetas);
fd_char fd_char_init (char fichero [15]);
int fd_char_insert (char fichero [15], fd_char a, struct fd_char_typo *e,
		     char *(*obti_clave) (const void *));
int fd_char_find (char fichero [15], fd_char a, struct fd_char_typo *e,
		   char *(*obti_clave) (const void *),
		   int (*compar) (const void *, const void *));
int fd_char_sacar (char fichero [15], fd_char a, struct fd_char_typo *e,
		     char *(*obti_clave) (const void *),
		     int (*compar) (const void *, const void *));
void fd_char_dest (fd_char *a);

#endif

A continuación, vamos a ver el desarrollo de las funciones en el fichero .c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <mem.h>
#include <math.h>
#include "fpdisp.h"

struct fd_char_rep    {
	int num_cubetas;    // Numero de cubetas
	int tam_cubetas;    // Tama¤o de las cubetas
	int historial;      // Comportamiento de las cubetas
	struct fd_char_typo *arr;     // Puntero al array que almacena elementos
   };                                 // del tipo struct fd_char_typo

 //  La variable historial puede estar en los siguientes estados, dependiendo
 //  de las operaciones realizadas sobre la cubeta:
 //      0 ==> La cubeta nunca se ha usado.
 //      1..n  ==> Indica el numero de elementos que contiene.
 //     -1..-n  ==> Indica el numero de elementos que contiene, a la vez
 //	            que nos indica que estuvo llena en algun momento.
 //  La variable historial nos indica el tama¤o logico de la cubeta

//  ---------------------------------------------------------------------
//               	FUNCIONES PRIVADAS
//  ---------------------------------------------------------------------
	//  Coge memoria para el array con un tama¤o = tamano

struct fd_char_typo *fd_char_aloarr (int tamano)   {
	struct fd_char_typo *arr;

	if (tamano == 0) return (NULL);
	else   {
		arr = (struct fd_char_typo *) malloc (sizeof (struct fd_char_typo) * tamano);
		if (arr == NULL)   {
		     fprintf (stderr, "\n\tfd_char_aloarr: No hay memoria suficiente.\n");
		     exit (1);
		   }
		return (arr);
	  }
   }

//   -------------------------------------------------------------------
	// Primitiva para crear el array con tama¤o = tamano

fd_char fd_char_alo (int tamano)    {
	fd_char p;

	p = (fd_char) malloc (sizeof (struct fd_char_rep));
	if (p == NULL)   {
	     fprintf (stderr, "\n\tfd_char_alo: No hay memoria suficiente.\n");
	     exit (1);
	   }

	p -> arr = fd_char_aloarr (tamano);
	return (p);
   }

//   -------------------------------------------------------------------
	// Primitiva para desalojar la memoria ocupada por el array

void fd_char_daloarr (struct fd_char_typo *arr)   {

	if (arr)   free (arr);
   }

//   -------------------------------------------------------------------
	// Primitiva para eliminar el array

void fd_char_dalo (fd_char *p)    {

	if (*p != NULL)   {
	      fd_char_daloarr ((*p) -> arr);
	      free (*p);
	      *p = NULL;
	 }
   }

//   -------------------------------------------------------------------
	// Funcion hash que calcula el valor de dispersion para una clave
	// alfanumerica en orden ascendente

int fd_char_hash1 (char *clave, int tamano)    {
	int i, disper = 0;

	for (i = 0; i < strlen (clave); i++)    {
		disper += (char) clave [i] * pow (32, i);
		disper = disper % tamano;
	   }

	return (disper);
    }

// ---------------------------------------------------------------------
	// Funcion hash que calcula el valor de dispersion para una clave
	// alfanumerica en orden descendente

int fd_char_hash2 (char *clave, int tamano)    {
	int i, disper = 0;

	for (i = strlen (clave) - 1; i >= 0; i--)    {
		disper += (char) clave [i] * pow (32, i);
		disper = disper % tamano;
	   }

	return (disper);
   }

// -----------------------------------------------------------------------
    // Funcion que devuelve 1 si un numero es primo y 0 en caso contrario

int fd_char_primos (int numero)    {
	int i;

	for (i = numero - 1; i > 1; i--)
		if ((numero % i) == 0)   return (0);
	return (1);
   }

// -----------------------------------------------------------------------
	// Funciones que devuelven el primo mayor y menor a un numero dado

int fd_char_pmayor (int numero)     {
	while (!(fd_char_primos (numero)))    numero++;
	return (numero);
   }

int fd_char_pmenor (int numero)     {
	while (!(fd_char_primos (numero)))    numero--;
	return (numero);
   }

// -----------------------------------------------------------------------
	// Funcion que calcula el valor de dispersion utilizando
	// dispersion doble (con dos funciones hash)

int fd_char_dispdoble (char *clave, int intentos, int numero)    {
	int disper = 0, mayor, menor;

	mayor = fd_char_pmayor (numero);
	menor = fd_char_pmenor (numero);

	disper = labs (fd_char_hash1 (clave, mayor) +
		 (intentos * fd_char_hash2 (clave, menor)));

	return (disper);
   }

// -----------------------------------------------------------------------

int fd_char_insertfp (fd_char a, FILE *fp, struct fd_char_typo *e, int pos)    {

	rewind (fp);
		     // Apunta a la cubeta que le corresponde
	fseek (fp, 2 * sizeof (int) + ((sizeof (int) + (sizeof (struct fd_char_typo)
	       * a -> tam_cubetas)) * pos), SEEK_SET);

	fread (&amp;(a -> historial), sizeof (int), 1, fp);

	if ((a -> historial < a -> tam_cubetas) &amp;&amp;
	    (a -> historial > -(a -> tam_cubetas)))    {
		  fread (a -> arr, (sizeof (struct fd_char_typo)
			 * a -> tam_cubetas), 1, fp);

		     // Inserta el elemento en una posicion libre
		  if (a -> historial >= 0)      {
			 a -> arr [a -> historial] = *e;
			 a -> historial++;
		     }
		  else     {
			 a -> arr [-(a -> historial)] = *e;
			 a -> historial--;
		    }

		     // Guardamos la cubeta con el nuevo elemento
		  rewind (fp);
		  fseek (fp, 2 * sizeof (int) + ((sizeof (int) + (sizeof (struct fd_char_typo)
			 * a -> tam_cubetas)) * pos), SEEK_SET);
		  fwrite (&amp;(a -> historial), sizeof (int), 1, fp);
		  fwrite (a -> arr, (sizeof (struct fd_char_typo)
			  * a -> tam_cubetas), 1, fp);

		  return (1);
	    }
	return (0);
   }

//  -----------------------------------------------------------------------

int fd_char_findfp (fd_char a, FILE *fp, struct fd_char_typo *e, int pos,
		int (*compar) (const void *, const void *))    {
	int i;

	rewind (fp);
		   // Apunta a la cubeta que le corresponde
	fseek (fp, 2 * sizeof (int) + ((sizeof (int) + (sizeof (struct fd_char_typo)
	       * a -> tam_cubetas)) * pos), SEEK_SET);

	fread (&amp;(a -> historial), sizeof (int), 1, fp);
	fread (a -> arr, (sizeof (struct fd_char_typo)
	       * a -> tam_cubetas), 1, fp);

	     // Buscamos el elemento *e en la cubeta
	for (i = 0; i < a -> tam_cubetas; i++)
	     if (!compar (&amp;(a -> arr [i]), e))    {
		    *e = a -> arr [i];
		    return (1);  // Encontrado
		}

	return (0);  // No encontrado
   }

// -----------------------------------------------------------------------

int fd_char_sacarfp (fd_char a, FILE *fp, struct fd_char_typo *e, int pos,
		int (*compar) (const void *, const void *))    {
	int i = 0;

	rewind (fp);
		   // Apunta a la cubeta que le corresponde
	fseek (fp, 2 * sizeof (int) + ((sizeof (int) + (sizeof (struct fd_char_typo)
	       * a -> tam_cubetas)) * pos), SEEK_SET);

	fread (&amp;(a -> historial), sizeof (int), 1, fp);

	if (a -> historial)    { // La cubeta tiene elementos
		fread (a -> arr, (sizeof (struct fd_char_typo)
		       * a -> tam_cubetas), 1, fp);

		 // Buscamos el elemento *e en la cubeta
		while (i < a -> tam_cubetas)    {
		    if (!compar ((a -> arr + i), e))   {
			  *e = a -> arr [i]; // Lo actualizamos
			  i = a -> tam_cubetas;
			     // Sacamos el elemento *e
			  if (a -> historial >= 0)       {
				   // Intercambiamos el ultimo elemento en la
				   // posicion del elemento sacado
				if (a -> historial == a -> tam_cubetas)
				      a -> historial = -(a -> tam_cubetas - 1);
				else  a -> historial--;
				a -> arr [i] = a -> arr [a -> tam_cubetas - 1];
			    }
			  else      {
				a -> arr [i] = a -> arr [a -> tam_cubetas - 1];
				a -> historial++;
			    }

			  rewind (fp);
			  fseek (fp, 2 * sizeof (int) + ((sizeof (int) + (sizeof (struct fd_char_typo)
				 * a -> tam_cubetas)) * pos), SEEK_SET);

			  fwrite (&amp;(a -> historial), sizeof (int), 1, fp);
			  fwrite (a -> arr, (sizeof (struct fd_char_typo)
				  * a -> tam_cubetas), 1, fp);

			  return (1);
		      }
		    i++;
		 }
	   }
	return (0);
   }

//  ---------------------------------------------------------------------
//  	                   FUNCIONES PUBLICAS
//  ---------------------------------------------------------------------

fd_char fd_char_nuev (char fichero [15], int num_cubetas, int tam_cubetas)    {
	fd_char a;
	int i;
	FILE *fp;

	num_cubetas = fd_char_pmayor (num_cubetas);
	tam_cubetas = fd_char_pmayor (tam_cubetas);

	a = fd_char_alo (tam_cubetas);
	a -> num_cubetas = num_cubetas;
	a -> tam_cubetas = tam_cubetas;
	a -> historial = 0;

	if (!(fp = fopen (fichero, "wb")))     {
		fprintf (stderr, "\n\tfd_char_nuev: No se puede abrir el fichero.\n");
		exit (1);
	   }

	fwrite (&amp;(a -> num_cubetas), sizeof (int), 1, fp);
	fwrite (&amp;(a -> tam_cubetas), sizeof (int), 1, fp);

	for (i = 1; i <= num_cubetas; i++)    {
		fwrite (&amp;(a -> historial), sizeof (int), 1, fp);
		fwrite (a -> arr, sizeof (struct fd_char_typo) * tam_cubetas, 1, fp);
	  }

	fclose (fp);
	return (a);
   }

// -----------------------------------------------------------------------

fd_char fd_char_init (char fichero [15])    {
	fd_char a;
	int num_cubetas, tam_cubetas;
	FILE *fp;

	if (!(fp = fopen (fichero, "r+b")))    {
		fprintf (stderr, "\n\tfd_char_init: No se puede abrir el fichero.\n");
		exit (1);
	    }

	fread (&amp;num_cubetas, sizeof (int), 1, fp);
	fread (&amp;tam_cubetas, sizeof (int), 1, fp);

	a = fd_char_alo (tam_cubetas);
	a -> num_cubetas = num_cubetas;
	a -> tam_cubetas = tam_cubetas;
	a -> historial = 0;

	fclose (fp);
	return (a);
   }

// ----------------------------------------------------------------------

int fd_char_insert (char fichero [15], fd_char a, struct fd_char_typo *e,
			   char *(*obti_clave) (const void *))      {
	int pos = 0, intentos = 0, insertado = 0;
	char *clave = NULL;
	FILE *fp;

	if (!a)   {
		fprintf (stderr, "\n\tfd_char_insert: El fichero disperso no existe.\n");
		exit (1);
	   }

	if (!(fp = fopen (fichero, "r+b")))    {
		fprintf (stderr, "fd_char_insert: No se puede abrir el fichero.\n");
		exit (1);
	   }

	while ((intentos <= 100) &amp;&amp; (!insertado))    {
		clave = obti_clave (e);
		pos = fd_char_dispdoble (clave, intentos, a -> num_cubetas);
		if (pos >= a -> num_cubetas)
			pos = pos % a -> num_cubetas;
		    // Insertamos el elemento en el fichero
		insertado = fd_char_insertfp (a, fp, e, pos);
		intentos++;
	  }

	fclose (fp);
	return (intentos);
   }

// -----------------------------------------------------------------------

int fd_char_find (char fichero [15], fd_char a, struct fd_char_typo *e,
		   char *(*obti_clave) (const void *),
		   int (*compar) (const void *, const void *))     {
	int pos = 0, intentos = 0, encontrado = 0;
	char *clave = NULL;
	FILE *fp;

	if (!a)   {
		fprintf (stderr, "\n\tfd_char_find: El fichero disperso no existe.\n");
		exit (1);
	   }

	if (!(fp = fopen (fichero, "r+b")))    {
		fprintf (stderr, "\n\tfd_char_find: No se puede abrir el fichero.\n");
		exit (1);
	   }

	while ((intentos <= 100) &amp;&amp; (!encontrado))    {
		clave = obti_clave (e);
		pos = fd_char_dispdoble (clave, intentos, a -> num_cubetas);
		if (pos >= a -> num_cubetas)
			pos = pos % a -> num_cubetas;
		  // Buscamos el elemento en el fichero
		encontrado = fd_char_findfp (a, fp, e, pos, compar);
		intentos++;
	   }

	fclose (fp);
	return (intentos);
   }

// ----------------------------------------------------------------------

int fd_char_sacar (char fichero [15], fd_char a, struct fd_char_typo *e,
		     char *(*obti_clave) (const void *),
		     int (*compar) (const void *, const void *))     {
	int pos = 0, intentos = 0, sacado = 0;
	char *clave = NULL;
	FILE *fp;

	if (!a)   {
		fprintf (stderr, "\n\tfd_char_sacar: El fichero disperso no existe.\n");
		exit (1);
	   }

	if (!(fp = fopen (fichero, "r+b")))   {
		fprintf (stderr, "\n\tfd_char_sacar: No se puede abrir el fichero.\n");
		exit (1);
	   }

	while ((intentos <= 100) &amp;&amp; (!sacado))    {
		clave = obti_clave (e);
		pos = fd_char_dispdoble (clave, intentos, a -> num_cubetas);
		if (pos >= a -> num_cubetas)
			pos = pos % a -> num_cubetas;
		   // Sacamos el elemento del fichero
		sacado = fd_char_sacarfp (a, fp, e, pos, compar);
		intentos++;
	   }

	fclose (fp);
	return (intentos);
   }

// ------------------------------------------------------------------------

void fd_char_dest (fd_char *a)     {

	if (!*a)   {
		fprintf (stderr, "\n\tfd_char_dest: El fichero disperso no existe.\n");
		exit (1);
	   }

	fd_char_dalo (a);
    }


Confio en que mi experiencia en programación en la universidad os haya sido útil.

No Comments

Deja un comentario

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.