X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/151ec0aa6089804f6a7a8cdb1416ad656f4d3fa3..088c62b17f5b04891f9b5fd4a682670b88143b99:/doc/informe.lyx?ds=sidebyside diff --git a/doc/informe.lyx b/doc/informe.lyx index 3645bb9..5f84015 100644 --- a/doc/informe.lyx +++ b/doc/informe.lyx @@ -55,8 +55,11 @@ EMUFS \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. @@ -65,21 +68,149 @@ es la estuctura principal que encapsula todas las funciones para el manejo 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 @@ -222,11 +353,15 @@ id \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 @@ -241,23 +376,43 @@ id 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 @@ -287,19 +442,23 @@ La estructura de este archivo est 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 @@ -314,17 +473,36 @@ Organizaci 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 @@ -340,9 +518,11 @@ Comportamiento Archivo de índices recuperables \layout Standard -<<<<<<< .mine -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 @@ -357,8 +537,11 @@ id`s 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 @@ -385,8 +568,8 @@ id \emph default al archivo, el cual será el primero recuperado. -\emph on -ver: emufs_did_agregar() +\family typewriter +Ver: emufs_did_agregar() \layout Itemize @@ -400,14 +583,8 @@ id que se guardó en el archivo (o se eliminó del archivo de datos), y trunca el archivo. -\emph on -ver: emufs_did_get_last() -======= -(.did) -\layout Standard - -idem anterior ->>>>>>> .r356 +\family typewriter +Ver: emufs_did_get_last() \layout Chapter @@ -469,8 +646,11 @@ T1 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 @@ -633,7 +813,7 @@ collapsed true \layout Caption -NOMBRE, ARREGLAME!!!! +Organización física de los registros en disco \layout Standard @@ -662,6 +842,310 @@ EMUFS_REG_SIZE 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 + + + + + + + +\begin_inset Text + +\layout Standard + + +\emph on +ID_REGISTRO +\end_inset + + +\begin_inset Text + +\layout Standard + + +\emph on +OFFSET +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\series bold +0 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +4 +\end_inset + + +\begin_inset Text + +\layout Standard + +El primer registro (reg0) comienza en el byte 4 +\end_inset + + + + +\begin_inset Text + +\layout Standard + +1 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +60 +\end_inset + + +\begin_inset Text + +\layout Standard + +El segundo registro (reg1) comienza en el byte 60 +\end_inset + + + + +\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 + + + + + + + +\begin_inset Text + +\layout Standard + + +\emph on +OFFSET +\end_inset + + +\begin_inset Text + +\layout Standard + + +\emph on +FREESPACE +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\series bold +42 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +18 +\end_inset + + +\begin_inset Text + +\layout Standard + +18 bytes libres a partir del byte 42 del .dat +\end_inset + + + + +\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) @@ -724,6 +1208,11 @@ RegSize ). 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 @@ -790,6 +1279,11 @@ Actualizamos la entrada correspondiente al registro ingresado (determinada .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 @@ -870,6 +1364,11 @@ Se marca en el archivo ) 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 @@ -898,9 +1397,34 @@ NOTA: 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 @@ -932,7 +1456,7 @@ collapsed true \layout Caption -NOMBRE, ARREGLAMEE!!! +Archivo con gaps entre registros previo a compactación \layout Standard @@ -1078,7 +1602,7 @@ collapsed true \layout Caption -NOMBRE, ARREGLAME!!!! +Archivo con gaps en disco luego del primer bucle de compactación \layout Standard @@ -1131,6 +1655,94 @@ Mustmove_bytes = Datsize - Source 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 @@ -1308,6 +1920,14 @@ que pudieron haberse formado por la eliminaci 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 .