\layout Standard
+\family typewriter
+EMUFS
+\family default
\emph on
-EMUFS
+
\emph default
es la estuctura principal que encapsula todas las funciones para el manejo
de un archivo de datos.
Esta estructura consta de:
\layout Enumerate
-EMUFS_Tipo que es un tipo enumerado que indica cual es la organización.
+
+\family typewriter
+EMUFS_Tipo
+\family default
+ que es un tipo enumerado que indica cual es la organización.
+\layout Enumerate
+
+
+\family typewriter
+EMUFS_BLOCK_SIZE
+\family default
+ indica el tamaño del bloque para los tipos 1 y 3.
\layout Enumerate
-EMUFS_BLOCK_SIZE indica el tamaño del bloque para los tipos 1 y 3.
+
+\family typewriter
+EMUFS_REG_SIZE
+\family default
+ indica el tamaño del registro, para el tipo 3 que posee tamaño constante.
\layout Enumerate
-EMUFS_REG_SIZE indica el tamaño del registro, para el tipo 3 que posee tamaño
- constante.
+
+\family typewriter
+void **leer_bloque()
+\family default
+puntero a la función para leer un bloque.
\layout Enumerate
-void *leer_bloque()
-\layout Comment
-no me convence esta descripcion.
-
+\family typewriter
+void *leer_bloque_raw()
+\family default
+ puntero a la función para leer un bloque, el anterior y el siguiente.
+\layout Enumerate
+
+
+\family typewriter
+void **leer_registro()
+\family default
+ puntero a la función para leer un registro.
+\layout Enumerate
+
+
+\family typewriter
+void **leer_registro_raw()
+\family default
+ puntero a la función para leer un registro con su encabezado.
+\layout Enumerate
+
+
+\family typewriter
+EMUFS_REG_ID *grabar_registro()
+\family default
+ puntero a la función para grabar un registro.
+\layout Enumerate
+
+
+\family typewriter
+EMUFS_REG_ID *modificar_registro()
+\family default
+puntero a la función para modificar un registro.
+\layout Enumerate
+
+
+\family typewriter
+int *borrar_registro()
+\family default
+ puntero a la función para borrar un registro.
+\layout Enumerate
+
+
+\family typewriter
+EMUFS_Estadisticas *leer_estadisticas()
+\family default
+ puntero a la función para cargar una estructura con las estadísticas.
+\layout Enumerate
+
+
+\family typewriter
+void *compactar()
+\family default
+ puntero a la función para compactar un archivo.
+\layout Enumerate
+
+
+\family typewriter
+char *nombre
+\family default
+ almacena el nombre del archivo sin extensión.
+\layout Standard
+
+Esta estructura define los valores de sus punteros según el tipo de organización
+ que se desee manejar.
+\layout Standard
+
+Por ejemplo si se desea crear un archivo de nombre
+\begin_inset Quotes eld
+\end_inset
+
+facturas
+\begin_inset Quotes erd
+\end_inset
+
+ organizado de la forma 3, se invoca a la función
+\family typewriter
+EMUFS *emufs_crear(const char *filename, EMUFS_Tipo tipo,EMUFS_BLOCK_SIZE
+ tam_bloque, EMUFS_REG_SIZE tam_reg),
+\family default
+donde
+\family typewriter
+ filename
+\family default
+es el nombre que tendrán los archivos de datos e índice,
+\family typewriter
+tipo
+\family default
+ es el tipo de organización - bloques parametrizados y registros constantes
+ en este caso-,
+\family typewriter
+tam_bloque
+\family default
+ es el tamaño del bloque, y
+\family typewriter
+tam_reg
+\family default
+ es el tamaño del registro.
+\layout Standard
+
+Para las diferentes organizaciones puede ser que alguno de estos 2 últimos
+ valores no tengan sentido almacenarlas y tomaran un valor por defecto igual
+ a cero.
+\layout Standard
+
+Según el tipo de organización, se inicializan los punteros a las funciones.
+ Para el ejemplo
+\family typewriter
+leer_bloque
+\family default
+ se igualará a
+\family typewriter
+emufs_tipo3_leer_bloque()
+\family default
+, y lo mismo sucede con los demás.
\layout Subsection
EMUFS_Tipo
\layout Standard
Si un registro es borrado del archivo de datos, debe actualizarse el índice,
- esto se logra colocando un flag que indique que el id no pertenece a ningún
- bloque, hemos adoptado poner -1 en el campo location de la estructura
+ esto se logra colocando un flag que indique que el
\emph on
-EMUFS_IDX
+id
\emph default
+ no pertenece a ningún bloque, hemos adoptado poner -1 en el campo location
+ de la estructura
+\family typewriter
+EMUFS_IDX
+\family default
.
\layout Standard
Organización física
\layout Standard
-El tipo EMUFS_IDX define la estuctura de los registros de este archivo.
+El tipo
+\family typewriter
+EMUFS_IDX
+\family default
+ define la estuctura de los registros de este archivo.
\layout Standard
Esta estructura está compuesta por:
\layout Itemize
-EMUFS_REG_ID reg_id indica el
+
+\family typewriter
+EMUFS_REG_ID
+\family default
+ reg_id indica el
\emph on
id
\emph default
del registro
\layout Itemize
-EMUFS_BLOCK_ID location número de bloque donde se encuentra el registro.
+
+\family typewriter
+EMUFS_BLOCK_ID
+\family default
+ location número de bloque donde se encuentra el registro.
\layout Standard
-EMUFS_REG_ID y EMUFS_BLOCK_ID son
+
+\family typewriter
+EMUFS_REG_ID
+\family default
+ y
+\family typewriter
+EMUFS_BLOCK_ID
+\family default
+ son
\emph on
unsigned long.
\layout Comment
De esta manera al querer guardar un registro este archivo informará donde
cabe el mismo, previa invocación al la función
-\emph on
+\family typewriter
EMUFS_BLOCK_ID emufs_fsc_buscar_lugar(EMUFS *, EMUFS_FREE, EMUFS_FREE*)
-\emph default
- perteneciente a fsc.h, la cual devuelve el número de bloque donde entra
- el registro o -1 si no hay un bloque con lugar suficiente, y toma como
- parámetros una estructura
+\family default
+ perteneciente a
\emph on
-EMUFS
+fsc.h,
\emph default
+ la cual devuelve el número de bloque donde entra el registro o -1 si no
+ hay un bloque con lugar suficiente, y toma como parámetros una estructura
+
+\family typewriter
+EMUFS
+\family default
, y dos
-\emph on
+\family typewriter
EMUFS_FREE
-\emph default
+\family default
donde el segndo parámetro es el tamaño buscado, y el tercero devuelve el
tamaño disponible.
\layout Standard
La estuctura que define este archivo es la siguiente:
\layout Standard
-EMUFS_FSC que contiene:
+
+\family typewriter
+EMUFS_FSC
+\family default
+ que contiene:
\layout Itemize
-EMUFS_BLOCK_ID indica el número de bloque
+
+\family typewriter
+EMUFS_BLOCK_ID
+\family default
+ indica el número de bloque
\layout Itemize
-EMUFS_FREE freespace indica la cantidad de espacio libre que queda en el
- bloque.
+
+\family typewriter
+EMUFS_FREE
+\family default
+ freespace indica la cantidad de espacio libre que queda en el bloque.
\layout Standard
-EMUFS_FSC y EMUFS_FREE son
+
+\family typewriter
+EMUFS_FSC
+\family default
+ y
+\family typewriter
+EMUFS_FREE
+\family default
+ son
\emph on
unsiged long int
\layout Subsection
Archivo de índices recuperables
\layout Standard
-Este archivo funciona como una pila de id`s borrados, es decir, cuando se
- borra un registro el
+Este archivo funciona como una pila de i
+\emph on
+d`s
+\emph default
+ borrados, es decir, cuando se borra un registro el
\emph on
id
\emph default
Estructura Física
\layout Standard
-Este archivo tiene registros de un solo campo, EMUFS_REG_ID el cual simboliza
- al id almacenado.
+Este archivo tiene registros de un solo campo,
+\family typewriter
+EMUFS_REG_ID
+\family default
+ el cual simboliza al id almacenado.
\layout Subsection
Comportamiento
\emph default
al archivo, el cual será el primero recuperado.
-\emph on
-ver: emufs_did_agregar()
+\family typewriter
+Ver: emufs_did_agregar()
\layout Itemize
que se guardó en el archivo (o se eliminó del archivo de datos), y trunca
el archivo.
-\emph on
-ver: emufs_did_get_last()
+\family typewriter
+Ver: emufs_did_get_last()
\layout Chapter
EMUFS_Tipo
\family default
).
- Luego le sigue una cabecera propia del archivo (un EMUFS_BLOCK_SIZE, 4
- bytes) que almacena el tamaño del bloque que usa el archivo.
+ Luego le sigue una cabecera propia del archivo (un
+\family typewriter
+EMUFS_BLOCK_SIZE
+\family default
+, 4 bytes) que almacena el tamaño del bloque que usa el archivo.
De esta menera, al abrir un archivo de este tipo no se necesita tener ninguna
información sobre él.
A esta cabecera le siguen cero o más bloques del tamaño fijo especificado
\layout Caption
-NOMBRE, ARREGLAME!!!!
+Organización física de los registros en disco
\layout Standard
Luego se encuentra el espacio libre de 18 bytes dejado por el registro
de 10 bytes eliminado (10 bytes de datos + header de 8 bytes) y finalmente
el segundo registro mencionado.dsds
+\layout Subsection
+
+Comportamiento Particular de los Archivos Auxiliares
+\layout Standard
+
+Como fue explicado al inicio de la documentación, la implementación de cualquier
+a de las tres organizaciones físicas de archivos presenta la necesidad de
+ poseer tres archivos auxiliares que actuarán como índice de direcciones
+ de registro (.
+\series bold
+idx
+\series default
+), administrador de espacio libre (
+\series bold
+.fsc
+\series default
+) y administrador de Id's liberados (
+\series bold
+.did
+\series default
+) respectivamente.
+\layout Standard
+
+No obstante, cada tipo de organización presentara sus particularidades respecto
+ de estos tres archivos, las cuales describiremos a continuación en caso
+ de haberla.
+\layout Subsubsection
+
+Archivo índice o de posiciones relativas (.idx)
+\layout Standard
+
+El archivo indice (
+\series bold
+.idx
+\series default
+), permite la localizacin de los registros en el .DAT de forma directa, mediante
+ la obtención de su offset o posición relativa respecto del inicio del
+\series bold
+.dat
+\series default
+ en donde se encuentra un registro dado, indicado por su ID.
+\layout Standard
+
+Así pues, si tomamos el ejemplo descripto al inicio de este capítudlo, tendremos
+ las siguientes entradas en el archivo indice
+\series bold
+.idx
+\series default
+ :
+\newline
+
+\layout Standard
+
+
+\begin_inset Tabular
+<lyxtabular version="3" rows="3" columns="3">
+<features>
+<column alignment="center" valignment="top" leftline="true" width="0">
+<column alignment="center" valignment="top" leftline="true" width="0">
+<column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
+<row topline="true" bottomline="true">
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\emph on
+ID_REGISTRO
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\emph on
+OFFSET
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+\end_inset
+</cell>
+</row>
+<row topline="true">
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\series bold
+0
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\series bold
+4
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+El primer registro (reg0) comienza en el byte 4
+\end_inset
+</cell>
+</row>
+<row topline="true" bottomline="true">
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+1
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\series bold
+60
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+El segundo registro (reg1) comienza en el byte 60
+\end_inset
+</cell>
+</row>
+</lyxtabular>
+
+\end_inset
+
+
+\layout Standard
+
+
+\series bold
+\emph on
+\SpecialChar ~
+
+\newline
+Observación:
+\series default
+\emph default
+ LOCATION indica donde comienza el header del registro buscado, y por consiguien
+te luego del header tendremos el registro en sí (los datos).
+\layout Subsubsection
+
+Achivo de Gaps / Espacios Libres (.fsc)
+\layout Standard
+
+El archivo de espacios libres o gaps (.fsc), tiene como función la administracion
+ del espacio libre o gaps (agujeros), generados por previas eliminaciones
+ de registros en el archivo de datos.
+ El mismo, nos indicará donde hay lugar para insertar un nuevo registro
+ (se podrán insertar en algún gap acorde, o bien al final del archivo).
+ Este archivo será utilizado tambien para el proceso de compactación de
+ un archivo, explicado luego.
+\layout Standard
+
+Así pues, si tomamos el ejemplo descripto al inicio del documento, tendremos
+ las siguientes entradas en el archivo índice
+\series bold
+.fsc
+\series default
+ :
+\newline
+
+\newline
+
+\begin_inset Tabular
+<lyxtabular version="3" rows="2" columns="3">
+<features>
+<column alignment="center" valignment="top" leftline="true" width="0">
+<column alignment="center" valignment="top" leftline="true" width="0">
+<column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
+<row topline="true" bottomline="true">
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\emph on
+OFFSET
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\emph on
+FREESPACE
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+\end_inset
+</cell>
+</row>
+<row topline="true" bottomline="true">
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\series bold
+42
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+
+\series bold
+18
+\end_inset
+</cell>
+<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\layout Standard
+
+18 bytes libres a partir del byte 42 del .dat
+\end_inset
+</cell>
+</row>
+</lyxtabular>
+
+\end_inset
+
+
+\layout Standard
+
+
+\series bold
+\emph on
+\SpecialChar ~
+
+\newline
+Nota:
+\series default
+\emph default
+ Por requerimiento del algoritmo de compactación, los gaps se graban en
+ forma ordenada en el (.fsc).
+ (El orden se corresponde con lo que hay en el .dat)
+\layout Subsubsection*
+
+GAP Merging
+\layout Standard
+
+Si bien la utilización concreta de los GAPS será explicada posteriormente
+ en la ALTA y BAJA de registros, debemos remarcar la funcionalidad de MERGING
+ que posee nuestro sistema FSC.
+\layout Standard
+
+Ante la eliminación de un registro del archivo de datos, se generara por
+ consiguiente un gap o espacio libre en alguna posición del archivo.
+ Ese gap deberá ser registrado en el archivo de gaps (.fsc).
+ Ahora bien, nuestro sistema de gaps, contemplará como es debido, la posibilidad
+ de que se haya eliminado un registro que posee un GAP por delante, un GAP
+ por detrás, o bien un GAP por delante y por detrás del mismo.
+\layout Standard
+
+Nuestro sistema actuará en consecuencia, realizando un merge de los espacios
+ libres, y unificándolos en una UNICA entrada en el archivo .fsc, que contendrá
+ como dato de freespace, la suma correspondiente de los espacios libres
+ antes mencionados.
+\layout Subsubsection
+
+Archivo de ID's liberados (.did)
+\layout Standard
+
+El archivo de ID's liberados no presenta ningún aspecto particular en este
+ tipo de organización.
+ Remitirse al capítulo correspondiente a los archivos auxiliares para consultar
+ su estructura y funcionamiento.
\layout Section
Comportamiento (funciones de la interfaz)
).
Contando así con el tamaño del registro, procedemos a leer el mismo (los
datos), dando por finalizada la lectura.
+\layout Standard
+
+Ver:
+\family typewriter
+emufs_tipo2_leer_registro()
\layout Subsection
Altas de registros
.idx
\series default
), indicando su offset donde podrá ser accedido luego.
+\layout Standard
+
+Ver:
+\family typewriter
+emufs_tipo2_agregar_registro()
\layout Subsection
Bajas de registros
) la eliminación, mediante el valor ¨-1¨ en el registro correspondiente
al registro recién eliminado (se le cambia el valor al n-esimo registro,
donde N = IDReg del reg eliminado).
+\layout Standard
+
+Ver:
+\family typewriter
+emufs_tipo2_borrar_registro()
\layout Subsection
Modificación de registros
Como fue indicado, dada la naturaleza de PILA del subsistema de administración
de ID liberados, es asegurado que la nueva inserción del registro modificado
se realizará con el mismo RegID.
+\layout Standard
+
+Ver:
+\family typewriter
+emufs_tipo2_modificar_registro()
\layout Subsection
Obtención de estadísticas
+\layout Standard
+
+Se puede tener acceso a las estadísticas generales del archivo, por ejemplo,
+ cantidad de bloques, cantidad de registros, espacio libre total, espacio
+ libre promedio, espacio libre máximo y mínimo, etc.
+\layout Standard
+
+Esta información es el resultado de ciertos cálculos realizados tanto en
+ el archivo de datos como en los archivos índice.
+\layout Standard
+
+Completa una estructura del tipo EMUFS_Estadisticas con las estadísticas
+ del archivo de datos, espacio libre total, cantidad de registros, cantidad
+ de bloques, tamaño del archivo en bytes, relaciones entre tamaños y espacios
+ libres, etc.
+\layout Standard
+
+Ver:
+\family typewriter
+emufs_tipo2_leer_estadisticas()
\layout Subsection
Compactación del archivo de datos
\layout Caption
-NOMBRE, ARREGLAMEE!!!
+Archivo con gaps entre registros previo a compactación
\layout Standard
\layout Caption
-NOMBRE, ARREGLAME!!!!
+Archivo con gaps en disco luego del primer bucle de compactación
\layout Standard
Damos por terminada así, la explicación del algoritmo de compresión el cual
para el caso del tipo 2, es realmente bastante sencillo.
+\layout Standard
+
+Ver:
+\family typewriter
+void emufs_tipo2_compactar()
+\layout Section
+
+Consideraciones y Políticas de Diseño
+\layout Standard
+
+Se han tomado ciertas consideraciones para algunos casos particulares que
+ se pueden presentar durante el uso/ejecución de la aplicación, así como
+ tambien politicas respecto del diseño e implementación del sistema:
+\layout Itemize
+
+En la organización física tipo 2 para los registros que se graban en disco
+ hemos decidido utilizar como encabezado de cada uno de ellos, los datos
+ [ID_REG][REG_SIZE], los cuales fueron detallados previamente.
+ Si bien se podría haber descartado el grabado del ID del registro en el
+ archivo de datos y puede parecer redundante, dado que poseemos el archivo
+ índice con el offset directo, el mismo se lo graba por distintos motivos:
+\newline
+
+\newline
+A) En caso de la corrupción del archivo índice (.idx), podremos gracias a
+ que poseemos en el archivo de datos, el ID de cada registro, recrear dicho
+ índice, ayudándonos del archivo de espacios libres (
+\series bold
+.fsc
+\series default
+), para poder saltear los espacios libres y e ir recorriendo secuencialmente
+ los registros, reconstruyendo así el índice en cuestión.
+ (esta función de reconstrucción no pudo ser implementada para esta entrega,
+ pero es una posibilidad real).
+\newline
+
+\newline
+B) Luego de un proceso de recompactación, los espacios libres que pudieron
+ haber existido en el archivo de datos (
+\series bold
+.dat
+\series default
+), son eliminados y los registros han cambiado de posición.
+ Por ello, recorriendo secuencialmente por única vez el archivo de datos,
+ se procede a la actualización / reconstrucción del índice de direcciones
+ u offsets (.
+\series bold
+idx
+\series default
+)
+\layout Itemize
+
+Si se desea insertar un registro y no se puede hayar un gap o espacio libre
+ donde quepa, se los inserta al final del archivo.
+\layout Itemize
+
+Ante una operación de baja de un registro, el mismo no es físicamente borrado
+ del archivo de datos (
+\series bold
+.dat
+\series default
+), simplemente los bytes que ocupa son llenados con hexa (00).
+ Paralelamente, se procede a actualiza el archivo índice, insertando como
+ valor de OFFSET para el registro eliminado, el valor ¨-1¨, indicando así
+ la inexistencia del registro para el futuro, y por otro lado se genera
+ la entrada de espacio libre en el archivo de gaps (
+\series bold
+.fsc
+\series default
+).
+\layout Itemize
+
+La reutilización de ID's liberados por previas operaciones de baja de registros,
+ se ve implementada por el archivo de ID liberados (.did), y su comportamiento
+ es el de una pila por lo que el último ID liberado, sera el próximo a ser
+ reutilizado (LIFO).
+\layout Itemize
+
+Como fue explicado en la implementación del archivo índice, existe una correspon
+dencia 1 a 1 entre los registros allí presentes (en el .idx) y los ID's de
+ los registros, por lo cual el registro N-ésimo del archivo índice, será
+ el correspondiente al registro de datos cuyo ID es igual a N.
+\layout Itemize
+
+El proceso de compactación de archivos, realiza los movimientos de información
+ requeridos para dicho propósito de a chunks de 25 bytes por vez.
+ Este valor es fijo, pero se lo podría hacer parametrizable mediante la
+ GUI en próximas entregas.
\layout Chapter
por otros.
\layout Standard
+Al estar utilizando recuperación de
+\emph on
+id`s
+\emph default
+ borrados, esto me asegura que el registro borrado-guardado conservará el
+ id al grabarse.
+\layout Standard
+
Al finalizar este proceso se verifica si existen bloques vacios para truncar
el archivo.
Lo mismo se debe hacer con el archivo de espacios libres .
projects / z.facultad / 75.06 / emufs.git / blobdiff