X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/03af81695f99bbce5810f0d9bf5bb986e7f80f2b..c247394a18d8d486fcf05d3492eb53a72230e0ab:/doc/informe.lyx?ds=inline diff --git a/doc/informe.lyx b/doc/informe.lyx index a545920..dc71eb8 100644 --- a/doc/informe.lyx +++ b/doc/informe.lyx @@ -26,6 +26,10 @@ \layout Title +Organización de Datos (75.06) +\newline +Trabajo Práctico +\newline E \begin_inset Formula $\mu$ \end_inset @@ -33,606 +37,760 @@ E FS \layout Author -Nicolás Dimov + +\series bold +Grupo 11 +\series default + \newline -Alan Kennedy +Nicolás Dimov (77624) \newline -Leandro Lucarella +Alan Kennedy (78907) \newline -Ricardo Markiewicz -\layout Chapter +Leandro Lucarella (77891) +\newline +Ricardo Markiewicz (78226) +\layout Date -Introducción -\layout Chapter +Primera Entrega, 19 de Abril de 2004 +\layout Standard -Estructura común -\layout Section -Tipos -\layout Subsection +\begin_inset LatexCommand \tableofcontents{} -EMUFS -\layout Standard +\end_inset -\emph on -EMUFS -\emph default -es la estuctura principal que encapsula todas las funciones para el manejo - de un archivo de datos. +\layout Chapter + +Introducción \layout Standard -Esta estructura consta de: -\layout Enumerate +Esta es la documentación correspondiente a las API`s para el manejo de tres + organizaciones de archivo diferentes. + A continuación se describe cada una de ellas y su modo de funcionamiento + y sus características principales. + De la correcta elección de la organización, dependerá la eficiencia de + la aplicación que la utilice. + +\layout Standard -EMUFS_Tipo que es un tipo enumerado que indica cual es la organización. +EMUFS se presenta como un +\emph on +emulador +\emph default + de un +\emph on +filesystem +\emph default +, capaz de administrar datos almacenados en cualquiera de las tres organizacione +s de archivo previamente mencionadas, las cuales a saberse son: \layout Enumerate -EMUFS_BLOCK_SIZE indica el tamaño del bloque para los tipos 1 y 3. +Registros de Longitud Variable, Bloques de tamaño parametrizable \layout Enumerate -EMUFS_REG_SIZE indica el tamaño del registro, para el tipo 3 que posee tamaño - constante. +Registros de Longitud Variable, Sin Bloques \layout Enumerate -void *leer_bloque() -\layout Comment - -no me convence esta descripcion. - -\layout Subsection - -EMUFS_Tipo -\layout Subsection +Registros de Longitud Fija, Bloques de tamaño parametrizables +\layout Standard -EMUFS_Estadisticas -\layout Subsection +A través de este trabajo, se podrán observar las diferencias entre distintos + tipos de organización de archivos, ventajas y desventajas de cada una de + ellas, y las situaciones particulares que deberá sortear un filesystem, + como la partición de registros en distintos bloques, manejo de espacio + libre, compactación de un archivo, etc. +\layout Standard -EMUFS_BLOCK_ID +A continuación, veremos que el manejo de los archivos en EMUFS se realiza + a través de una estructura de control común para cualquier tipo de archivo, + dándole flexibilidad y escalabilidad a nuestro sistema. \layout Standard -etc +Hacia el final de esta presentación, se observaran las pruebas realizadas + con las distintas organizaciones de archivos, y las conclusiones obtenidos + al respecto. \layout Section +Documentación de la API +\layout Standard -\begin_inset LatexCommand \label{sec:cabecera_gral} - -\end_inset +Para obtener una documentación de la API más completa, se incluye en formato + HTML en el CD-ROM la documentación generado con Doxygen. + Esta documentación se encuentra en el directorio +\family typewriter +doc/api/html +\family default +. +\layout Chapter -Organización física general de un archivo E -\begin_inset Formula $\mu$ -\end_inset +Estructura común +\layout Section -FS +Tipos \layout Standard -Todo archivo E -\begin_inset Formula $\mu$ -\end_inset +Se detallan a continuación los tipos de datos definidos y utilizados en + las distintas implementaciones que conforman nuestro sistema, siendo el + más importante de ellos, la estructura +\family typewriter +EMUFS +\family default + que actúa como interfaz común para el manejo de cualquier tipo de archivo + (no importa que tipo de organización física posea un archivo, esta estructura + proveerá una interfaz (funciones) para su manejo). +\layout Subsection -FS está compuesto por 4 archivos a nivel de sistema operativo: archivo de - datos (con 3 formatos posibles, ver páginas -\begin_inset LatexCommand \pageref{cha:tipo1} +Tipos Comunes +\layout Standard -\end_inset +En la implementación de cada tipo de organización física, así como también + en las API de los archivos auxiliares comunes a ellas, se da la utilización + de tipo definidos para una clara interfaz entre las mismas, los cuales + son brevemente descriptos a continuación y pueden ser hallados en el archivo + +\series bold +emufs.h +\series default +: +\layout Itemize -, -\begin_inset LatexCommand \pageref{cha:tipo2} -\end_inset +\family typewriter +EMUFS_REG_ID +\family default +: usado para representar un +\emph on +Id +\emph default + de un registro. +\layout Itemize - y -\begin_inset LatexCommand \pageref{cha:tipo3} -\end_inset +\family typewriter +EMUFS_REG_SIZE +\family default +: usado para representar el tamaño en bytes de un registro. +\layout Itemize -), archivo de índice (ver página -\begin_inset LatexCommand \pageref{sec:idx} -\end_inset +\family typewriter +EMUFS_BLOCK_ID +\family default +: usado para representar un número de bloque. +\layout Itemize -), archivo de control de espacio libre (ver página -\begin_inset LatexCommand \pageref{sec:fsc} -\end_inset +\family typewriter +EMUFS_BLOCK_SIZE +\family default +: usado para representar el tamaño en bytes de un bloque. +\layout Itemize -) y archivo de índices recuperables (ver página -\begin_inset LatexCommand \pageref{sec:did} -\end_inset +\family typewriter +EMUFS_FREE +\family default +: usado para representar espacio libre en bytes. +\layout Itemize -). -\layout Standard -El archivo de datos está compuesto por: -\layout Itemize +\family typewriter +EMUFS_OFFSET +\family default +: usado para representar un offset. +\layout Standard -Una -\emph on -cabecera general -\emph default - compuesta por un +Todos son del tipo \family typewriter -int +unsigned long \family default - (4 bytes en plataformas Linux de 32 bits) que representa el tipo de archivo. -\layout Itemize +. +\layout Subsection -Datos dependientes del tipo de archivo. +EMUFS \layout Standard -La + +\family typewriter +EMUFS +\family default \emph on -cabecera general + \emph default - es utilizada para poder detectar el formato de un archivo al abrirlo. - Los datos dependientes del tipo de archivo serán explicados en sus secciones - correspondientes. -\layout LyX-Code - -archivo -\layout LyX-Code - -+-----------+--------------------------------------------//-+ -\layout LyX-Code - -| tipo | Datos dependientes del tipo de archivo ... +es la estructura principal que encapsula todas las funciones para el manejo + de un archivo de datos. + Posee punteros a funciones que dependiendo de la organización física por + la cual se opte dentro del sistema, serán asignados de acorde. -\backslash - -\backslash - | -\layout LyX-Code +\layout Standard -+-----------+--------------------------------------------//-+ -\layout LyX-Code +Su declaración puede ser observada en el archivo +\series bold +emufs.h +\series default +y la misma cuenta con los siguiente campos: +\layout Itemize -/- 4 bytes -/ -\layout Chapter -Archivos Auxiliares -\layout Comment +\family typewriter +EMUFS_Tipo +\family default + que es un tipo enumerado que indica cual es la organización. +\layout Itemize -Por que los 3 tipos usan lo mismo. - Ventajas y desventajas. -\layout Section +\family typewriter +EMUFS_BLOCK_SIZE +\family default + indica el tamaño del bloque para los tipos 1 y 3. +\layout Itemize -\begin_inset LatexCommand \label{sec:idx} -\end_inset +\family typewriter +EMUFS_REG_SIZE +\family default + indica el tamaño del registro, para el tipo 3 que posee tamaño constante. +\layout Itemize -Archivo de índice -\layout Standard -Con la ayuda de un archivo de bloques y registros (de extensión .idx), podremos - ubicar cualquier registro existente dentro del archivo. -\layout Standard +\family typewriter +void **leer_bloque() +\family default +puntero a la función para leer un bloque. +\layout Itemize -El archivo de índice contiene una estructura que contiene el id de un registro - y el número de bloque al que pertenece. - Este archivo esta ordenado por -\emph on -id -\emph default -, de modo que incrementa su tamaño cada vez que se grabe en el archivo de - datos un nuevo registro, excepto que un registro haya sido borrado con - anterioridad lo cual produce que al guardar un nuevo registro se actualice - y no crezca. -\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 -\emph on -EMUFS_IDX -\emph default -. -\layout Standard +\family typewriter +void *leer_bloque_raw() +\family default + puntero a la función para leer un bloque, el anterior y el siguiente. +\layout Itemize -Es necesario que este archivo esté ordenado por -\emph on -id -\emph default - de registro, ya que esto permitirá el acceso directo para la búsqueda de - un registro en el archivo de datos. -\layout Subsection -Organización física -\layout Standard +\family typewriter +void **leer_registro() +\family default + puntero a la función para leer un registro. +\layout Itemize -El tipo EMUFS_IDX define la estuctura de los registros de este archivo. -\layout Standard -Esta estructura está compuesta por: +\family typewriter +void **leer_registro_raw() +\family default + puntero a la función para leer un registro con su encabezado. \layout Itemize -EMUFS_REG_ID reg_id indica el -\emph on -id -\emph default - del registro + +\family typewriter +EMUFS_REG_ID *grabar_registro() +\family default + puntero a la función para grabar un registro. \layout Itemize -EMUFS_BLOCK_ID location número de bloque donde se encuentra el registro. -\layout Standard -EMUFS_REG_ID y EMUFS_BLOCK_ID son -\emph on -unsigned long. -\layout Comment +\family typewriter +EMUFS_REG_ID *modificar_registro() +\family default +puntero a la función para modificar un registro. +\layout Itemize -ponerlo mas lindo... -\layout Subsection -Comportamiento (funciones generales) -\layout Section +\family typewriter +int *borrar_registro() +\family default + puntero a la función para borrar un registro. +\layout Itemize -\begin_inset LatexCommand \label{sec:fsc} +\family typewriter +EMUFS_Estadisticas *leer_estadisticas() +\family default + puntero a la función para cargar una estructura con las estadísticas. +\layout Itemize -\end_inset -Archivo de control de espacio libre -\layout Standard +\family typewriter +void *compactar() +\family default + puntero a la función para compactar un archivo. +\layout Itemize -El archivo de de espacios libres permite decidir a la hora de guardar un - registro, donde será guardado. - -\layout Standard -La estructura de este archivo está formada por un número que indica el bloque - y otro que indica el espacio libre en él. +\family typewriter +char *nombre +\family default + almacena el nombre del archivo sin extensión. \layout Standard -De esta manera al querer guardar un registro este archivo informará donde - cabe el mismo, previa invocación al la función -\emph on -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 -\emph on -EMUFS -\emph default -, y dos -\emph on -EMUFS_FREE -\emph default - donde el segndo parámetro es el tamaño buscado, y el tercero devuelve el - tamaño disponible. +Esta estructura define los valores de sus punteros según el tipo de organización + que se desee manejar y esto se realiza a través del API emufs, implementado + en +\series bold +emufs.c +\series default +, que se describirá posteriormente. \layout Standard -De la misma manera, al borrar un registro este archivo debe ser actualizado - colocando el nuevo espacio libre en el bloque. -\layout Subsection +Por ejemplo si se desea crear un archivo de nombre +\begin_inset Quotes eld +\end_inset -Organización Física -\layout Standard +facturas +\begin_inset Quotes erd +\end_inset -La estuctura que define este archivo es la siguiente: + organizado de la forma 3, se invoca a la función: \layout Standard -EMUFS_FSC que contiene: -\layout Itemize - -EMUFS_BLOCK_ID 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_crear(filename,tipo,tam_bloque,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 -EMUFS_FSC y EMUFS_FREE son -\emph on -unsiged long int -\layout Subsection - -Comportamiento -\layout Section - - -\begin_inset LatexCommand \label{sec:did} - -\end_inset - -Archivo de índices recuperables +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 -Este archivo funciona como una pila de id`s borrados, es decir, cuando se - borra un registro el -\emph on -id -\emph default - se almacena en este archivo y será recuperado cuando se desee grabar un - registro nuevo, de esta manera se aprovechan todos los -\emph on -id`s -\emph default - sin necesidad de crear uno nuevo cada vez que se borra y graba un registro. +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 -Estructura Física +EMUFS_Tipo \layout Standard -Este archivo tiene registros de un solo campo, EMUFS_REG_ID el cual simboliza - al id almacenado. -\layout Subsection -Comportamiento +\family typewriter +EMUFS_Tipo +\family default + es un tipo de dato enum, el cual será utilizado en la cabecera de todo + archivo de datos ( +\series bold +.dat +\series default +), para indicar los distintos tipos de organización física. + Su declaración puede verse en el archivo +\series bold +emufs.h. \layout Standard -Las declaraciones e implementación se pueden encontrar en -\emph on -did.h -\emph default - y -\emph on -did.c -\emph default - respectivamente +A saberse los valores y significado correspondiente que puede tomar este + tipo de dato son: \layout Itemize \series bold -Agregar: +T1 \series default -agrega un -\emph on -id -\emph default -al archivo, el cual será el primero recuperado. - -\emph on -ver: emufs_did_agregar() + : Archivos con registros de longitud variable y bloques parametrizables. \layout Itemize \series bold -Obtener el último: +T2 \series default - Obtiene el último -\emph on -id -\emph default - que se guardó en el archivo (o se eliminó del archivo de datos), y trunca - el archivo. - -\emph on -ver: emufs_did_get_last() -\layout Chapter + : Archivos con registros de longitud variable sin bloques. +\layout Itemize -\begin_inset LatexCommand \label{cha:tipo1} +\series bold +T3 +\series default + : Archivos con registros de longitud fija y bloques parametrizables. +\layout Subsection -\end_inset +EMUFS_Estadisticas +\layout Standard -Archivo con bloques parametrizados y registros de longitud variable + +\family typewriter +EMUFS_Estadisticas +\family default + es una estructura que almacenará los datos pertinentes a las estadísticas + de un archivo dado, y será utilizada para visualizar dichas observaciones + a través de la GUI. \layout Standard -Este tipo de archivo tiene varias complicaciones, al tratarse de un punto - intermedio entre el -\begin_inset LatexCommand \ref{cha:tipo2} +Su declaración puede ser observada en el archivo +\series bold +emufs.h +\series default +y la misma cuenta con los siguiente campos: +\layout Itemize -\end_inset - y el -\begin_inset LatexCommand \ref{cha:tipo3} +\family typewriter +unsigned long +\family default + +\family typewriter +tam_archivo +\family default +: indica el tamaño del archivo de datos (.dat) en bytes. +\layout Itemize -\end_inset - (cuenta tanto con bloques como con registros variables), hereda los inconvenien -tes (y ventajas) de ambos, más los propios. - Al implementar este tipo de archivo se puso enfásis en la eficiencia mientras - esta no comprometa la mantenibilidad del código, es por esto que en algunas - circunstancias no se hace un uso óptimo del espacio. -\layout Standard +\family typewriter +unsigned long +\family default + +\family typewriter +tam_archivos_aux +\family default +: indica el tamaño de los archivos auxiliares sumados en bytes. +\layout Itemize + -La implementación de este tipo de archivo puede ser encontrada en \family typewriter -emufs/tipo1.c +unsigned long \family default - mientras que su interfaz pública está disponible en + \family typewriter -emufs/tipo1.h +tam_info_control_dat \family default -. -\layout Section +: indica la cantidad de bytes en información de control utilizados para + el archivo. +\layout Itemize -Organización física -\layout Standard -El archivo está compuesto por la -\emph on -cabecera general -\emph default - (ver página -\begin_inset LatexCommand \pageref{sec:cabecera_gral} +\family typewriter +unsigned long +\family default + +\family typewriter +media_fs +\family default +: promedio de espacio libre en el archivo de datos (por bloque o gap promedio + según la org) +\layout Itemize -\end_inset -). - El valor que toma en este tipo de archivo es 0 (o el valor simbólico \family typewriter -T1 +unsigned long \family default - del tipo + \family typewriter -EMUFS_Tipo +total_fs \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. - 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 - en la cabecera antes mencionada. -\layout LyX-Code +: total de espacio libre en el archivo de datos. +\layout Itemize -archivo -\layout LyX-Code -+-----------+-----------+------------------------//-+ -\layout LyX-Code +\family typewriter +unsigned long +\family default + +\family typewriter +max_fs +\family default +: máximo espacio libre en el archivo de datos (en un bloque o máximo gap + segun la org). +\layout Itemize -| tipo | tam bloque| Cero o más bloques ... + +\family typewriter +unsigned long +\family default -\backslash +\family typewriter +min_fs +\family default +: ídem pero mínimo. +\layout Itemize -\backslash - | -\layout LyX-Code -+-----------+-----------+------------------------//-+ -\layout LyX-Code +\family typewriter +unsigned long +\family default + +\family typewriter +cant_bloques +\family default +: cantidad de bloques en el archivo de datos (. +\series bold +dat +\series default +) +\layout Itemize -/- 4 bytes -/- 4 bytes -/ -\layout Subsection -Organización física de un bloque +\family typewriter +unsigned long +\family default + +\family typewriter +cant_registros +\family default +: cantidad de registros en el archivo de datos ( +\series bold +.dat +\series default +) \layout Standard -Cada bloque no guarda información en sí, sólo se comporta como un contenedor - de registros. - Esto no significa que un bloque no tenga utilidad, el bloque es utilizado - para proveer un acceso semi-aleatorio a los registros. - Para esto se utiliza el archivo de índice (ver página -\begin_inset LatexCommand \ref{sec:idx} +En base a la estructura descripta anteriormente y mediante la utilización + de la función de lectura de estadísticas +\family typewriter +emufs_leer_estadisticas() +\family default + disponible en la estructura común +\family typewriter +EMUFS +\family default + handler de cualquier tipo de archivo, podremos obtener una serie de estadística +s que pasamos a detallar (más allá de los datos básicos como cant registros, + cant bloques, tam archivo, etc): +\layout Itemize -\end_inset +Relación entre espacio libre y el tamaño del archivo de datos ( +\series bold +.dat +\series default +) +\layout Itemize -), que almacena pares (identificador de registro, número de bloque). - Para que sea suficiente este único índice para hallar un registro (siendo - que puede haber más de un registro por bloque), es necesario -\emph on -alinear los registros a izquierda -\emph default -. -\layout LyX-Code +Relación entre el espacio ocupado por información de control y el tamaño + del archivo de datos ( +\series bold +.dat +\series default +) +\layout Itemize -bloque N-1 | bloque N | bloque N+1 -\layout LyX-Code +Cantidad promedio de espacio libre (en bloque o gap promedio) +\layout Itemize -/----------+------------+------------+-------------------+-----------/ -\layout LyX-Code +Desviaciones extremas de espacio libre (máximo/mínimo espacio libre en bloque + o mayor/menor gap) +\layout Section -\backslash - | registro 1 | registro 2 | espacio libre ... - | -\backslash - /----------+------------+------------+-------------------+-----------/ -\layout Standard +\begin_inset LatexCommand \label{sec:cabecera_gral} -De forma tal que una vez obtenido el número de bloque se pueda recorrer - secuencialmente hasta encontrar el registro deseado. - A fin de llevar el conteo de espacio libre se utiliza el archivo de control - de espacio libre (ver página -\begin_inset LatexCommand \ref{sec:fsc} +\end_inset +Organización física general de un archivo E +\begin_inset Formula $\mu$ \end_inset -), de forma tal que no sea necesario recorrer secuencialmente en busca de - espacio libre al hacer una inserción. +FS \layout Standard -Puede darse un caso excepcional en el que un registro sea más grande que - un bloque, en este caso el registro se almacenará en N bloques consecutivos - (siendo N la cantidad de bloques que necesita el registro), ocupando completos - los todos los bloques a excepción del último, en el que posteriormente - se pueden agregar más registros. -\layout Section +Todo archivo E +\begin_inset Formula $\mu$ +\end_inset -Comportamiento (funciones de la interfáz) -\layout Section +FS está compuesto por 4 archivos a nivel de sistema operativo: archivo de + datos (con 3 formatos posibles, ver páginas +\begin_inset LatexCommand \pageref{cha:tipo1} -Detalles de implementación (funciones internas, ver si lo ponemos o no) -\layout Chapter +\end_inset +, +\begin_inset LatexCommand \pageref{cha:tipo2} -\begin_inset LatexCommand \label{cha:tipo2} +\end_inset + + y +\begin_inset LatexCommand \pageref{cha:tipo3} \end_inset -Archivo sin bloques y registros de longitud variable -\layout Standard +), archivo de índice (ver página +\begin_inset LatexCommand \pageref{sec:idx} -Este tipo de archivo nos traerá a la mesa la particularidad de grabar registros - de longitud variable sin realizar su agrupación en bloques, y como veremos - en la siguiente sección, tambien permitirá la administración de gaps que - queden en el archivo luego de operaciones de baja de registros. -\layout Section +\end_inset -Organización física -\layout Standard +), archivo de control de espacio libre (ver página +\begin_inset LatexCommand \pageref{sec:fsc} + +\end_inset + +) y archivo de índices recuperables (ver página +\begin_inset LatexCommand \pageref{sec:did} + +\end_inset -Este tipo de archivo realizará el almacenamiento de registros de longitud - variable en disco, su borrado y modificación sin la utilización de bloques - de ningún tipo. - Su implementación se encuentra en los archivos fuente ( -\series bold -tipo2.c -\series default - y -\series bold -tipo2.h -\series default ). \layout Standard -Los archivos del tipo 2, presentarán al comienzo del mismo un header compuesto - simplemente por un dato del tipo EMUFS_Tipo (int) el cual indicará el tipo - de archivo en cuestión. +El archivo de datos está compuesto por: +\layout Itemize + +Una +\emph on +cabecera general +\emph default + compuesta por un +\family typewriter +int +\family default + (4 bytes en plataformas Linux de 32 bits) que representa el tipo de archivo. +\layout Itemize + +Datos dependientes del tipo de archivo. \layout Standard -Para poder entender mejor la organización fisica de este tipo de archivo, - tomemos el caso hipotético en el que se encuentran grabados -\series bold -dos registros -\series default - (comenzando desde registro 0) de +La +\emph on +cabecera general +\emph default + es utilizada para poder detectar el formato de un archivo al abrirlo. + Los datos dependientes del tipo de archivo serán explicados en sus secciones + correspondientes. +\layout LyX-Code + +archivo +\layout LyX-Code + ++-----------+--------------------------------------------//-+ +\layout LyX-Code + +| tipo | Datos dependientes del tipo de archivo ... + +\backslash + +\backslash + | +\layout LyX-Code + ++-----------+--------------------------------------------//-+ +\layout LyX-Code + +/- 4 bytes -/ +\layout Section + +Uso de la estructura EMUFS +\layout Standard + +Como fue mencionado anteriormente en la descripción de la estructura EMUFS, + la misma proporciona al usuario una interfaz a través de la cual puede + realizar el manejo de archivos en forma genérica, abstrayéndose del tipo + de organización física en particular que dicho archivo posea. + Se la declara en \series bold -30 bytes +emufs.h \series default -, y + y las funciones que inicializan la estructura se encuentran en \series bold -25 bytes -\series default -, respectivamente. - Supongamos también que entre el registro 0 y 1 se encontraba un +emufs.c +\layout Standard + +Es decir que a través de esta estructura, podemos manejar cualquier tipo + de archivo, mediante una misma interfaz en común. + La estructura +\family typewriter +EMUFS +\family default +posee además de ciertos datos que describen la organización física de un + archivo dado como por ejemplo \series bold -registro de 10 bytes +\emph on +tamaño de registro \series default - que fue +\emph default +, \series bold -borrado +\emph on +tamaño de bloque \series default -, generando un +\emph default + y \series bold -gap +\emph on +nombre del archivo \series default - +\emph default +, una serie de punteros a funciones para el manejo del archivo del cual + es handler: +\layout Standard + +Entre dichos funciones se encuentran: +\family typewriter +leer_registro() +\family default +, +\family typewriter +leer_bloque(), borrar_registro() +\family default +, +\family typewriter +agregar_registro() +\family default +, +\family typewriter +modificar_registro, leer_estadisticas() +\family default +, +\family typewriter +compactar(). +\layout Standard + +Para entender mejor el uso de esta estructura para el manejo de los archivos, + mostraremos un ejemplo concreto. + Supongamos que tenemos el siguiente código: +\layout LyX-Code + +EMUFS *efs = emufs_crear(¨articulos.dat¨,T3,200,50); +\layout Standard + +Esto hará que se cree el archivo de datos \series bold -o freespace +articulos.dat \series default -. - Si miramos al archivo de datos (.dat) en el disco nos encontraremos con - lo siguiente: +, con la organización física tipo 3 con registros de longitud fija de 50 + bytes y bloques de 200 bytes. + Al mismo tiempo, los se asignaran valores a los punteros a funciones que + posee dicha estructura, la cual de ahora en más estará en condiciones de + manejar un archivo del tipo 3. + Gráficamente lo que sucede es: +\layout Standard + + \begin_inset Float figure placement H wide false -collapsed true +collapsed false \layout Caption -NOMBRE, ARREGLAME!!!! +Inicialización de estructura EMUFS para un caso Archivo Tipo 3 \layout Standard - +\align center \begin_inset Graphics - filename graphics/Example1.png - width 100text% + filename graphics/Emufsinit.png + scale 75 + keepAspectRatio \end_inset @@ -642,718 +800,5853 @@ NOMBRE, ARREGLAME!!!! \layout Standard -Como se puede observar, a nivel físico cada registro grabado esta compuesto - por un Header cuyo tamaño total es de 8 bytes ( +Así pues, cuando se utilice la estructura para por ejemplo leer un registro, + sucederá lo siguiente: +\layout LyX-Code + +efs->leer_registro(params) -- calls --> emufs_tipo3_leer_registro(params) +\layout Standard + +Como se puede observar, la estructura +\family typewriter +EMUFS +\family default + permitirá el manejo de cualquier tipo de archivo, a través del mismo código, + dándole gran flexibilidad a nuestro sistema, que podrá expandirse a más + tipos de archivos de ser necesario. +\layout Chapter + +Archivos Auxiliares +\layout Standard + +Acompañando al archivo de datos ( \series bold -EMUFS_REG_ID +.dat \series default - + +) el cual es responsable de la contención de los registros, tendremos tres + archivos auxiliares ( \series bold -EMUFS_REG_SIZE +.idx \series default -), y posteriormente el registro (bloque de datos) en sí. - 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 Section - -Comportamiento (funciones de la interfaz) -\layout Standard - -Dentro de +, \series bold -\emph on -tipo2.h +.fsc \series default -\emph default y \series bold -\emph on -tipo2.c +.did \series default -\emph default - se encuentran las cabeceras y la implementación de las funciones principales - respectivamente, las cuales dan funcionalidad a esta organización. - +) cuya funcionalidad y propósito pasamos a describir a continuación, sin + antes remarcar que los tres archivos poseen una sola implementación para + las distintas formas de organización física que hemos implementado (tres + para ser mas exactos). \layout Standard -A continuación se comentará el funcionamiento algunas de las mas importantes. -\layout Subsection - -Lectura de registros +Entre las ventajas de poseer la misma implementación se encuentra el tener + un API común entre los tres tipos para el manejo de la localización de + sus registros, administración de espacio libre e Id's liberados, sin necesidad + de realizar n-implementaciones para un mismo objetivo final. \layout Standard -Como se vió al comienzo, los registros en este tipo de archivo no se encuentran - agrupados en bloques de ninguna índole y estan dispersos a lo largo del - archivo, con la particularidad de que pueden existir gaps o espacio libre, - entre dos registros dados. -\layout Standard +Además, la obtención de ciertos datos estadísticos como espacio libre, o + cantidad de registros, se realiza a través de la misma interfaz, y también + se ha facilitado en cierto grado la re-organización física de un archivo + (pasar de un tipo a otro), dado el uso de estos tres archivos auxiliares + en común para funciones tan predominantes como índexación, administración + de espacio libre y recuperación de Id's. +\layout Section -Por ende la lectura de registros en este tipo de organización es muy simple - y dada la inexistencia de bloques, el procedimiento será el siguiente: -\layout Enumerate -Se determina el offset en bytes, donde comienza el registro deseado, a través - de su ID, buscando la misma en el archivo índice ( -\series bold -.idx -\series default -) -\layout Enumerate +\begin_inset LatexCommand \label{sec:idx} -Ya determinada la posición física del registro dentro del archivo de datos - ( -\series bold -.dat -\series default -), nos posicionamos en la misma, y leemos el header del registro ( -\series bold -IDReg -\series default - + -\series bold -RegSize -\series default -). - Contando así con el tamaño del registro, procedemos a leer el mismo (los - datos), dando por finalizada la lectura. -\layout Subsection +\end_inset -Altas de registros +Archivo índice \layout Standard -En el proceso de alta de registros entrarán en juego dos archivos descriptos - en la +El archivo índice (.idx), permite la localización de los registros en el + .DAT de forma directa, mediante la obtención de su offset respecto del inicio + del .dat, o nro bloque (segun el tipo de organización física) en donde se + encuentra un registro dado, indicado por su \emph on -sección de archivos auxiliares -\emph default -, siendo estos el archivo índice ( -\series bold -.idx -\series default -), y el archivo de gaps / espacios libres ( -\series bold -.fsc -\series default -). +id_reg. \layout Standard -Así pues, a la hora de realizar una inserción de un registro en el archivo - de datos, el procedimiento será el siguiente: -\layout Enumerate +Los registros de este archivo se encuentran representados una estructura + que indica un número de registro y el bloque u offset en donde se encuentra + el mismo. +\layout Standard -Calculamos el espacio que necesitaremos para el registro: sizeof( -\series bold -EMUFS_REG_ID -\series default -) + sizeof( -\series bold -EMUFS_REG_SIZE -\series default -) + sizeof(registro). -\layout Enumerate +Es necesario que este archivo esté ordenado por +\emph on +id_reg +\emph default +, ya que esto permitirá el acceso directo al mismo, para la rápida obtención + del nro de bloque u offset y posterior búsqueda de un registro en el archivo + de datos. +\layout Subsection -Determinamos donde debemos insertar el registro, ya sea un gap donde entre, - o bien al final del archivo. -\layout Enumerate +Organización física +\layout Standard -Insertamos el registro e información de control ( -\series bold -header -\series default -+ -\series bold -data -\series default -), en la posición indicada en el paso 2. -\layout Enumerate - -En caso de haber utilizado un GAP, actualizamos el espacio libre restante - en el mismo y en caso de que se haya utilizado al totalidad del GAP, se - lo elimina del archivo ( -\series bold -.fsc -\series default -). -\layout Enumerate +Los registros de este archivo se encuentran representados a nivel código + por el siguiente tipo de dato interno ( +\family typewriter +EMUFS_IDX +\family default +): +\layout LyX-Code -Actualizamos la entrada correspondiente al registro ingresado (determinada - por su RegID), en el archivo índice ( -\series bold -.idx -\series default -), indicando su offset donde podrá ser accedido luego. -\layout Subsection +typedef struct emufs_idx_t { +\layout LyX-Code -Bajas de registros -\layout Standard + EMUFS_REG_ID id_reg; +\layout LyX-Code -En el proceso de baja de registros entrarán en juego los tres archivos descripto -s en la -\emph on -sección de archivos auxiliares -\emph default -, siendo estos el archivo índice ( -\series bold -.idx -\series default -), el archivo de gaps / espacios libres ( -\series bold -.fsc -\series default -) y el archivo de ID's liberados ( -\series bold -.did -\series default -). -\layout Standard + EMUFS_OFFSET location; +\layout LyX-Code -Dado que en la implementación de este tipo de organización física contamos - con los gaps o espacios libres entre registros, no se eliminará fisicamente - el registro del archivo de datos ( -\series bold -.dat -\series default -), pues entonces carecería de sentido el archivo anteriormente mencionado - ( -\series bold -.fsc -\series default -). - En cambio, se agrega el gap dejado por la eliminación a dicho archivo, - y se marca fisicamente en el archivo de datos la eliminación mediante un - fill de los bytes correspondientes con un caracter nulo. - (hexa 00 y con el propósito de probar fehacientemente que el sistema funciona). +} EMUFS_IDX; \layout Standard -El proceso de baja o eliminación de un registro constará luego de los siguientes - pasos: -\layout Enumerate -Se obtiene el offset o posición relativa en donde se encuentra grabado el - registro dentro del archivo de datos. -\layout Enumerate +\begin_inset Float table +placement H +wide false +collapsed false -Se obtiene el tamaño del registro y se realiza un dummyfill del sector del - archivo correspondiente al registro que se está dando de baja. - (Se rellena la zona correspondiente a su header+data). -\layout Enumerate +\layout Caption -Se agrega el GAP generado al archivo de gaps o espacios libres, y en caso - de haberse generado un GAP lindante con otro GAP, se realizará un merge - de los mismos y se los registrará bajo una única entrada en el archivo - de espacios libres (.fsc). -\layout Enumerate +Ejemplo de registro en archivo índice (.idx), para un archivo de organización + Tipo 1 y 3 +\layout Standard -Se agrega el ID que fue liberado, al archivo de ID's liberados ( -\series bold -.did -\series default -), al final del mismo ( -\emph on -pila -\emph default -). -\layout Enumerate -Se marca en el archivo índice ( -\series bold -.idx -\series default -) 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 Subsection +\begin_inset Tabular + + + + + + + +\begin_inset Text -Modificación de registros \layout Standard -Dada la naturaleza del archivo de ID's liberados, y el manejo de espacio - libre del que consta esta organización de archivo, el proceso de modificación - de un registro se limita a los siguientes pasos: -\layout Enumerate - -Se realiza la lectura del registro, mediante el respectivo procedimiento - ya desarollado anteriormente. -\layout Enumerate +id_reg +\end_inset + + +\begin_inset Text -Una vez que se cuenta con los nuevos datos modificados, se procede a dar - de baja el registro que ha sido modificado, e inmediatamente después se - realiza una inserción con los nuevos datos. \layout Standard +nro_bloque +\end_inset + + +\begin_inset Text -\series bold -\emph on -NOTA: -\series default -\emph default - 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 Subsection +\layout Standard -Obtención de estadísticas -\layout Subsection +\end_inset + + + + +\begin_inset Text -Compactación del archivo de datos \layout Standard -Asi como los otros dos tipos de datos, el que nos compete también cuenta - con la posibilidad de realizar la compactación de datos cuando el usuario - lo desee, justificando todos los registros a izquierda, eliminando así - los gaps existentes y decrementando el tamaño del archivo en disco (truncandolo -). +5 +\end_inset + + +\begin_inset Text + \layout Standard -Para poder comprender como hemos implementado el proceso de recompactación - en nuestro tipo de archivo 2, nos ayudaremos de esquemas a través de los - cuales iremos describiendo el proceso. - Notemos antes, que el proceso de compactación esta directamente ligado - con el archivo de gaps o espacios libres ( -\series bold -.fsc -\series default -). +54 +\end_inset + + +\begin_inset Text + \layout Standard -Comenzemos con el siguiente cuadro situacional: -\begin_inset Float figure +Indica que el registro de id_reg = 5, se encuentra en el bloque 54 +\end_inset + + + + +\end_inset + + +\end_inset + + +\begin_inset Float table placement H wide false -collapsed true +collapsed false \layout Caption -NOMBRE, ARREGLAMEE!!! +Ejemplo de registro en archivo índice (.idx), para un archivo de organización + Tipo 2 \layout Standard -\begin_inset Graphics - filename graphics/Compact1.png - width 100text% - keepAspectRatio +\begin_inset Tabular + + + + + + + +\begin_inset Text + +\layout Standard +id_reg \end_inset + + +\begin_inset Text +\layout Standard +nro_bloque \end_inset - + + +\begin_inset Text \layout Standard -Partiendo de esta base, el algoritmo de compactación tomará en su inicio - al primer gap existente dentro del archivo de datos, en este caso llamado - -\series bold -Gap0 -\series default -. - Luego, establecerá que el -\series bold -Source -\series default - a partir de donde se quieren mover datos, sera: -\layout LyX-Code +\end_inset + + + + +\begin_inset Text -StartGap0 + SizeGap0 = EndGap0 = Source \layout Standard -Lo cual no es nada más y nada menos que lo obvio, la fuente a partir de - donde se mueven los datos, sera el fin del primer gap, donde comienzan - datos. - Como destino ( -\series bold -Destination -\series default -) del movimiento, se establece inicialmente, el inicio del gap, o sea -\series bold -StartGap0 = Destination -\series default -. +5 +\end_inset + + +\begin_inset Text + \layout Standard -Luego, el algoritmo entrara en un bucle while (mientras haya bucles por - levantar), el cual trabajara hasta el final de la compactación de la siguiente - manera: +54 +\end_inset + + +\begin_inset Text + \layout Standard +Indica que el registro de id_reg = 5, se encuentra en el bloque 54 +\end_inset + + + -\series bold -Mientras haya Gaps -\series default - { -\layout Enumerate +\end_inset -Se levanta el proximo gap al levantado en una instancia previa. - En este ejemplo, durante el primer loop del while, se levantará -\series bold -Gap1 -\layout Enumerate -Luego, se calcula cuantos bytes hay que mover hacia el Destination de la - siguiente manera: -\layout Enumerate +\end_inset + + +\layout Standard \series bold -Mustmove_bytes +\emph on +Nota: \series default - = +\emph default +Como se puede observar, para distintas organizaciones el significado de + los registros en este archivo es diferente y se utilizará de distinta manera + en consecuencia. +\layout Subsection + +Comportamiento +\layout Standard + +Las declaraciones e implementación se pueden encontrar en \series bold -StartGap1 +\emph on +idx.h \series default - - +\emph default + y \series bold -Source +\emph on +idx.c \series default - = +\emph default + respectivamente: +\layout List +\labelwidthstring 00.00.0000 + + \series bold -StartGap1 +\emph on +Búsqueda: \series default - - +\emph default + Los registros del archivo índice ( \series bold -EndGap0 ( +.idx \series default -Lo cual nuevamente es lógico pues querremos mover lo que se encuentra entre - el final del primer gap levantado y el inicio del siguiente). -\layout Enumerate - -Se realiza el movimiento de los datos, utilizando las direcciones +), poseen una correspondencia 1 a 1, con los Id's de los registros en el + archivo de datos ( \series bold -Source +.dat \series default - y +). + Con esto, queremos decir que el N-ésimo registro del archivo índice, será + aquél que posea la información para localizar al registro cuyo +\family typewriter +id_reg +\family default + es N, dentro del archivo de datos ( \series bold -Destination +.dat \series default -, así como la variable +). \series bold -Mustmove_bytes + +\newline +NOTA: \series default - que nos indica cuantos bytes transferir. + Cabe aclarar que por si bien el índice se encuentra ordenado por +\family typewriter +id_reg +\family default +, los registros en el archivo de datos, por lo general no lo estarán (ordenados + por id). + +\newline +Ver: +\family typewriter +emufs_idx_buscar_registro(), emufs_idx_get() +\layout List +\labelwidthstring 00.00.0000 + + \series bold +Alta: +\series default + Ante la alta de un registro en el archivo de datos, se insetará un nuevo + registro en el archivo índice, con el id_reg del registro en cuestión, + y el offset u bloque donde se lo haya grabado en disco. +\newline +Ver: +\family typewriter +emufs_idx_agregar() +\layout List +\labelwidthstring 00.00.0000 + +\series bold +Baja: +\series default + Ante el borrado de un registro del archivo de datos, se accederá el registro + correspondiente en el índice, y se actualizara su LOCATION, estableciéndolo + en el valor especial +\family typewriter +EMUFS_NOT_FOUND +\family default +, el cual indica que ese registro ha sido eliminado y por ende no se lo + podrá localizar en el futuro. + Como se verá mas adelante, según el tipo de organización física, el registro + puede ser borrado concretamente del . +\series bold +dat +\series default + o no. + \newline -IMPORTANTE: +Ver: +\family typewriter +emufs_idx_borrar() +\layout List +\labelwidthstring 00.00.0000 + + +\series bold +Modificación: +\series default + Ante la modificación en la posición física de un registro dentro del archivo + de datos (por ejemplo luego del proceso de re-compactación, se realizará + la modificación respectiva del campo +\family typewriter +location +\family default +. +\newline +Ver: +\family typewriter +emufs_idx_actualizar() +\layout Section + + +\begin_inset LatexCommand \label{sec:fsc} + +\end_inset + +Archivo de control de espacio libre +\layout Standard + +El archivo de espacio libre ( +\series bold +.fsc +\series default +) (espacio por bloque o gaps en archivo, según el tipo de organización física), + tiene como función la administración del espacio libre, generado por previas + eliminaciones de registros en el archivo de datos. + El mismo, nos indicará donde hay lugar para insertar un nuevo registro. +\layout Standard + +Para el caso de una organización por bloque, nos dirá en que bloque o si + se debe generar un nuevo bloque. + En el caso de la organización sin bloques, nos indicará en que gap o si + al final del archivo. +\layout Standard + +Los registros de este archivo se encuentran representados una estructura + que indica un número de bloque u offset y el espacio libre disponible en + el mismo (o a partir del mismo en el caso del offset). +\layout Standard + + +\series bold +Nota +\series default +: Por requerimiento del algoritmo de compactación el tipo de organización + física con reg long var, sin bloques, los gaps se graban en forma ordenada + en el (.fsc). + (El orden se corresponde con lo que hay en el .dat). +\layout Subsection + +Organización Física +\layout Standard + +Los registros de este archivo se encuentran representados a nivel código + por el siguiente tipo de dato interno ( +\family typewriter +EMUFS_FSC +\family default +): +\layout LyX-Code + +typedef struct emufs_fsc_t { +\layout LyX-Code + + EMUFS_BLOCK_ID marker; +\layout LyX-Code + + EMUFS_FREE freespace; +\layout LyX-Code + +} EMUFS_FSC; +\layout Standard + + +\series bold \emph on -La transferencia se hace de a chunks de 25 bytes + un resto segun el valor - de Mustmove_bytes. -\layout Enumerate -Se establece como gap de referencia, al ultimo gap leido (En este caso se - realiza: +\begin_inset Float table +placement H +wide false +collapsed false + +\layout Caption + +Ejemplo de registro en archivo de control de espacio libre para un archivo + con bloques +\layout Standard + + +\begin_inset Tabular + + + + + + + +\begin_inset Text + +\layout Standard + +nro_bloque +\end_inset + + +\begin_inset Text + +\layout Standard + +freespace +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + + + +\begin_inset Text + +\layout Standard + +12 +\end_inset + + +\begin_inset Text + +\layout Standard + +120 +\end_inset + + +\begin_inset Text + +\layout Standard + +Indica que en el bloque 12, hay 120 bytes libres al final del mismo. +\end_inset + + + + +\end_inset + + +\end_inset + + +\begin_inset Float table +placement H +wide false +collapsed false + +\layout Caption + +Ejemplo de registro en archivo de +\emph on +gaps +\emph default + para un archivo sin bloques +\layout Standard + + +\begin_inset Tabular + + + + + + + +\begin_inset Text + +\layout Standard + +offset +\end_inset + + +\begin_inset Text + +\layout Standard + +freespace +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + + + +\begin_inset Text + +\layout Standard + +12 +\end_inset + + +\begin_inset Text + +\layout Standard + +120 +\end_inset + + +\begin_inset Text + +\layout Standard + +Indica que a partir del byte 12 del archivo de datos, hay 120 bytes libres. +\end_inset + + + + +\end_inset + + +\end_inset + + +\layout Standard + + \series bold -StartGap0 +\emph on +Nota: \series default - = +\emph default +Como se puede observar, para distintas organizaciones el significado de + los registros en este archivo es diferente y se utilizará de distinta manera + en consecuencia. +\layout Subsection + +Funciones principales +\layout Standard + +Las declaraciones e implementación se pueden encontrar en \series bold -StartGap1 +\emph on +fsc.h \series default -, +\emph default + y \series bold -Gap0Size = Gap1Size +\emph on +fsc.c \series default -) y termina el código de repetición del bucle, dando lugar a la carga del - siguiente gap en el inicio del mismo. +\emph default + respectivamente: +\layout List +\labelwidthstring 00.00.0000 + + +\series bold +Búsqueda: +\series default + Ante la operación de alta de un registro en el archivo de datos, se realizará + la búsqueda de espacio libre donde este podrá ser insertado. + En el caso de organizaciones con bloques, se buscará en que +\family typewriter +nro_bloque +\family default + se posee espacio suficiente para albergar el nuevo registro (o a partir + de qué +\family typewriter +nro_bloque +\family default + se encuentran +\family typewriter +N +\family default + bloques consecutivos libres). + En el caso de organización sin bloque, se buscará un gap o espacio libre + en el archivo, obteniéndose en consecuencia, el +\family typewriter +offset +\family default + hasta el mismo. + +\newline +Ver: +\family typewriter +emufs_fsc_buscar_lugar(), emufs_fsc_buscar_n_lugares() +\layout List +\labelwidthstring 00.00.0000 + + +\series bold +Alta/Mod: +\series default + Luego de una operación de baja o alta de un registro en el archivo de datos + ( +\series bold +.dat +\series default +), incrementará o decrementará respectivamente el espacio libre en el archivo + de datos, y esto deberá ser registrado, agregando un nuevo registro en + el archivo de espacios libres ( +\series bold +.fsc +\series default +) o bien modificándolo. +\newline + +\newline +En el caso de organizaciones con bloques, se actualizará el valor del espacio + libre +\family typewriter +freespace +\family default + en el bloque (ya sea incrementándolo o decrementándolo) o bien se insertará + un nuevo registro en caso de que se esté creando un nuevo bloque en el + archivo de datos (en este caso no será debido a un alta o baja de registro + como se mencionó al principio). +\newline + +\newline +Para el caso de organización sin bloques, en el caso de baja de un registro + de datos ( +\series bold +.dat +\series default +) se insertará un nuevo registro en el +\series bold +.fsc +\series default + dando cuenta de la aparición de un nuevo gap en el archivo de datos ( +\series bold +.dat +\series default +), y en caso de estar este lindante con otro gap, se realizará el merge + pertinente. + (esto esta explicado más en profundidad en los casos particulares de organizaci +ón física, registros variables sin bloques). + Para el caso de una alta en el archivo de datos ( +\series bold +.dat +\series default +), el valor del gap donde se haya insertado se actualizará. + +\newline +Ver: +\family typewriter +emufs_fsc_agregar(), emufs_fsc_agregar_gap(), emufs_fsc_actualizar(), emufs_fsc_ +actualizar_gap(). +\layout List +\labelwidthstring 00.00.0000 + + +\series bold +Baja +\series default +: Únicamente para el caso de una organización que presente gaps en el archivo, + se podrá dar a lugar la eliminación de un registro del archivo de espacios + libres ( +\series bold +.fsc) +\series default +. + Esta situación tendrá efecto cuando se inserte un registro que entre perfecto + en un gap disponible, y por ende el gap desaparecerá. +\newline +Ver: +\family typewriter +emufs_fsc_borrar_gap() +\layout Section + + +\begin_inset LatexCommand \label{sec:did} + +\end_inset + +Archivo de id's recuperables \layout Standard +El archivo de Id's liberado ( +\series bold +.did +\series default +) llevará cuenta de aquellos Id's de registros ( +\family typewriter +id_reg +\family default +) que ya no se encuentran siendo utilizados y fueron liberados por registros + eliminados previamente. + A través del mismo, se podrá realizar la reutilización de Id's ante la + alta de nuevos registros. +\layout Standard + +A nivel físico, este archivo poseerá una secuencia de datos del tipo EMUFS_REG_I +D, y el comportamiento del sistema de recuperación de Id's será el de una + pila. + Es decir, ante el requerimiento de un +\family typewriter +reg_id +\family default + libre por una función del sistema como por ejemplo la alta de un nuevo + registro, el API del archivo ( +\series bold +.did +\series default +), obtendrá el último dato del mismo (el +\emph on +Id +\emph default + que fue liberado mas recientemente), y truncará el archivo eliminando el + +\emph on +Id +\emph default + recuperado de la tabla. + (LIFO, Last in First Out). +\layout Subsection + +Organización Física +\layout Standard + +Este archivo tiene registros de un solo campo, +\family typewriter +EMUFS_REG_ID +\family default + el cual simboliza al id que fue liberado en un proceso de baja de registros. +\layout Subsection + +Funciones principales +\layout Standard + +Las declaraciones e implementación se pueden encontrar en +\series bold +\emph on +did.h +\series default +\emph default + y +\series bold +\emph on +did.c +\series default +\emph default + respectivamente +\layout List +\labelwidthstring 00.00.0000 + + +\series bold +Alta: +\series default +Ante la eliminación de un registro del archivo de datos ( +\series bold +.dat +\series default +) se procederá al agregado del correspondiente +\family typewriter +id_reg +\family default + que fue liberado por dicha operación, al archivo +\series bold +.did +\series default +. +\family typewriter + +\newline + +\family default +Ver: +\family typewriter +emufs_did_agregar() +\layout List +\labelwidthstring 00.00.0000 + + +\series bold +Baja +\series default + Cuando el sistema desee grabar un nuevo registro en el archivo de datos, + este pedirá un +\family typewriter +id_reg +\family default + disponible para el mismo. + El sistema de administración de Id's libres, obtendrá el último +\emph on +id +\emph default + que se guardó en el archivo (o se eliminó del archivo de datos), y truncará + el archivo eliminándolo. +\family typewriter + +\newline + +\family default +Ver: +\family typewriter +emufs_did_get_last() +\layout Chapter + + +\begin_inset LatexCommand \label{cha:tipo1} + +\end_inset + +Archivo con bloques parametrizados y registros de longitud variable +\layout Standard + +Este tipo de archivo tiene varias complicaciones, al tratarse de un punto + intermedio entre el +\begin_inset LatexCommand \ref{cha:tipo2} + +\end_inset + + y el +\begin_inset LatexCommand \ref{cha:tipo3} + +\end_inset + + (cuenta tanto con bloques como con registros variables), hereda los inconvenien +tes (y ventajas) de ambos, más los propios. + Al implementar este tipo de archivo se puso énfasis en la eficiencia mientras + esta no comprometa la mantenibilidad del código, es por esto que en algunas + circunstancias no se hace un uso óptimo del espacio. +\layout Standard + +La implementación de este tipo de archivo puede ser encontrada en +\family typewriter +emufs/tipo1.c +\family default + mientras que su interfaz pública está disponible en +\family typewriter +emufs/tipo1.h +\family default +. +\layout Section + +Organización física +\layout Standard + +El archivo está compuesto por la +\emph on +cabecera general +\emph default + (ver página +\begin_inset LatexCommand \pageref{sec:cabecera_gral} + +\end_inset + +). + El valor que toma en este tipo de archivo es 0 (o el valor simbólico +\family typewriter +T1 +\family default + del tipo +\family typewriter +EMUFS_Tipo +\family default +). + 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 manera, 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 + en la cabecera antes mencionada. +\layout LyX-Code + +archivo +\layout LyX-Code + ++-----------+-----------+------------------------//-+ +\layout LyX-Code + +| tipo | tam_bloque| Cero o más bloques ... + +\backslash + +\backslash + | +\layout LyX-Code + ++-----------+-----------+------------------------//-+ +\layout LyX-Code + +/- 4 bytes -/- 4 bytes -/ +\layout Subsection + +Organización física de un bloque +\layout Standard + +Cada bloque no guarda información en sí, sólo se comporta como un contenedor + de registros. + Esto no significa que un bloque no tenga utilidad, el bloque es utilizado + para proveer un acceso semi-aleatorio a los registros. + Para esto se utiliza el archivo de índice (ver página +\begin_inset LatexCommand \ref{sec:idx} + +\end_inset + +), que almacena pares [identificador de registro, número de bloque]. + Para que sea suficiente este único índice para hallar un registro (siendo + que puede haber más de un registro por bloque), es necesario +\emph on +alinear los registros a izquierda +\emph default +. + Esto significa que hay que asegurar que siempre los registros en un bloque + se presenten de forma consecutiva, jamás permitiendo que haya un espacio + libre entre registros (en un mismo bloque). +\layout Standard + +Podemos ver un ejemplo de esto en forma gráfica: +\layout LyX-Code + +bloque N-1 | bloque N | bloque N+1 +\layout LyX-Code + +/----------+------------+------------+---------------+-----------/ +\layout LyX-Code + + +\backslash + | registro 1 | registro 2 | espacio libre | +\backslash + +\layout LyX-Code + +/----------+------------+------------+---------------+-----------/ +\layout LyX-Code + + /------------- tamaño del bloque ---------/ +\layout Standard + +De esta forma, una vez obtenido el número de bloque, se pueda recorrer secuencia +lmente hasta encontrar el registro deseado. + A fin de llevar el conteo de espacio libre se utiliza el archivo de control + de espacio libre (ver página +\begin_inset LatexCommand \ref{sec:fsc} + +\end_inset + +), de forma tal que no sea necesario recorrer secuencialmente en busca de + espacio libre al hacer una inserción. +\layout Standard + +Puede darse un caso excepcional en el que un registro sea más grande que + un bloque, en este caso el registro se almacenará en N bloques consecutivos + (siendo N la cantidad de bloques que necesita el registro), ocupando completos + los todos los bloques a excepción del último, en el que posteriormente + se pueden agregar más registros. +\layout Subsubsection + + +\begin_inset LatexCommand \label{sub:tipo1_reg} + +\end_inset + +Organización física de un registro. +\layout Standard + +El registro es el que representa al dato realmente que se quiere almacenar. + Para representar ese dato se necesita una determinada información de control, + tanto para poder identificar el registro en un bloque (en búsquedas secuenciale +s dentro del bloque) como para saber su longitud (dado que este tipo de + archivo utiliza registros de tamaño variable). +\layout Standard + +Siguiendo la metodología general de E +\begin_inset Formula $\mu$ +\end_inset + +FS, se optó por incluir esta información de control como una cabecera al + comienzo del registro, siguiendo a esta los datos en sí. + La cabecera está compuesta por un identificador ( +\family typewriter +id +\family default +) de registro (EMUFS_REG_ID, 4 bytes) seguido por el tamaño ( +\family typewriter +tamaño +\family default +) del registros (EMUFS_REG_SIZE, 4 bytes). + Podemos ver gráficamente como se se compone un registro: +\layout LyX-Code + +registro [id] +\layout LyX-Code + ++-----------+-----------+------------------+ +\layout LyX-Code + +| id | tamaño | datos ... + | +\layout LyX-Code + ++-----------+-----------+------------------+ +\layout LyX-Code + +/- 4 bytes -/- 4 bytes -/- [tamaño] bytes -/ +\layout Subsubsection + + +\begin_inset LatexCommand \label{sub:tipo1_reg_multi} + +\end_inset + +Organización física de un registro más grande que un bloque (registro +\emph on +multibloque +\emph default +). +\layout Standard + +Puede darse el caso excepcional en que un registro sea de mayor longitud + que un bloque. + Al ser una situación excepcional, no siempre se resuelve de la forma más + eficiente ni se minimiza el espacio ocupado por datos de control (como + se dijo anteriormente, se prefirió conservar la simpleza del código, adoptando + algoritmos generales aunque no sea de la forma más eficiente o maximizando + el uso del espacio para no perjudicar la mantenibilidad). +\layout Standard + +Para manejar un registro +\emph on +multibloque +\emph default +se optó por limitarlo a la siguiente estructura (suponiendo que el registro + ocupa N bloques, con N > 1 y que un +\emph on +fragmento +\emph default + es una porción del registro que entra en un bloque): +\layout Itemize + +Los primeros N-1 +\emph on +fragmentos +\emph default + se almacenan en bloques completos consecutivos. +\layout Itemize + +El último fragmento se almacena al comienzo del bloque inmediatamente posterior + al penúltimo. +\layout Itemize + +Cada fragmento posee las cabeceras mencionadas en la sección +\begin_inset LatexCommand \ref{sub:tipo1_reg} + +\end_inset + +, cuyo contenido es el siguiente: +\begin_deeper +\layout Itemize + +En +\family typewriter +id +\family default + se almacena el identificador único obtenido al hacer el alta. +\layout Itemize + +En +\family typewriter +tamaño +\family default + se almacena el tamaño del +\emph on +fragmento +\emph default + actual más los tamaños de los +\emph on +fragmentos +\emph default + posteriores, quedando en el primer +\emph on +fragmento +\emph default + el tamaño completo del registro y en el último sólo el tamaño del +\emph on +fragmento +\emph default + final. +\end_deeper +\layout Standard + +Como puede observarse, la información de control en los +\emph on +fragmentos +\emph default + intermedios puede ser redundante, pero se conserva para poder realizar + algoritmos genéricos (que se basan en que al principio de un bloque, si + no está vacío, hay una cabecera de un registro) y para facilitar chequeos + de integridad del archivo. +\layout Standard + +A continuación se presenta un ejemplo gráfico de un registro multibloque + de 10 bytes (de contenido +\begin_inset Quotes eld +\end_inset + +1234567890 +\begin_inset Quotes erd +\end_inset + +) almacenado en un archivo con bloques de 12 bytes (4 para datos): +\layout LyX-Code + +| bloque 0 | bloque 1 | bloque 2 +\layout LyX-Code + ++-------------------+-------------------+-------------------+-//-+ +\layout LyX-Code + +| registro 0 - 1/3 | registro 0 - 2/3 | registro 0 - 3/3..| +\backslash + +\backslash + | +\layout LyX-Code + +|+----+-----+------+|+----+-----+------+|+----+-----+----+..| // | +\layout LyX-Code + +|| id | tam | datos||| id | tam | datos||| id | tam |dato|..| +\backslash + +\backslash + | +\layout LyX-Code + +||----+-----+------+||----+-----+------+||----+-----+----+..| // | +\layout LyX-Code + +|| 0 | 10 | 1234 ||| 0 | 6 | 5678 ||| 0 | 2 | 90 |..| +\backslash + +\backslash + | +\layout LyX-Code + +|+----+-----+------+|+----+-----+------+|+----+-----+----+..| // | +\layout LyX-Code + ++-------------------+-------------------+-------------------+- +\backslash + +\backslash +-+ +\layout LyX-Code + + ^^ +\layout LyX-Code + + 2 bytes libres al final del bloque 2 +\layout Standard + +Este es un ejemplo figurativo, ya que se puso como límite mínimo de tamaño + de bloque 16 bytes (para que haya al menos la misma cantidad de espacio + para datos que para información de control). + Este límite mínimo ya roza lo absurdo (es muy ineficiente por la gran cantidad + de accesos a disco que necesita). + El límite físico es de 9 bytes (8 para información de control, 1 para datos). +\layout Section + +Funciones principales +\layout Standard + +Las funciones principales son las necesarias para completar la estructura + EMUFS (ver página +\begin_inset LatexCommand \pageref{sub:EMUFS} + +\end_inset + +). +\layout Subsection + +Lectura de registros +\layout Standard + +Para leer un registro se hace uso del archivo de índice (ver página +\begin_inset LatexCommand \pageref{sec:idx} + +\end_inset + +), obteniéndose el número de bloque en donde está almacenado el registro + a buscar. + Una vez obtenido, se carga en memoria el bloque entero y se busca secuencialmen +te en él (leyendo la cabecera de cada registro y salteando los datos) hasta + encontrar el registro pedido. + Una vez encontrado se lo copia y devuelve. +\layout Standard + +Si se tratara de un registro +\emph on +multibloque +\emph default + (ver sección +\begin_inset LatexCommand \ref{sub:tipo1_reg_multi} + +\end_inset + +), se procede forma similar, sólo que se cargan en memoria uno a uno los + bloques que componen el registro y se van copiando (y uniendo) los +\emph on +fragmentos +\emph default + hasta completarlo. +\layout Standard + +Ver: +\family typewriter +emufs_tipo1_leer_registro() +\layout Subsection + +Altas de registros +\layout Standard + +Para realizar el alta de un registro, lo primero que se obtiene es un identifica +dor, buscando primero en el archivo de identificadores recuperables (pág. + +\begin_inset LatexCommand \ref{sec:did} + +\end_inset + +) y de no haber ninguno, buscando el mayor identificador presente en el + archivo de índice (pág. + +\begin_inset LatexCommand \ref{sec:idx} + +\end_inset + +) y sumándole uno. + El paso siguiente es buscar un bloque con espacio libre suficiente como + para almacenar el registro (y su cabecera) en el archivo de control de + espacio libre (pág. + +\begin_inset LatexCommand \ref{sec:fsc} + +\end_inset + +) y cargarlo completo en memoria. + De no encontrarse, se crea un bloque nuevo al final de archivo. + En el bloque cargado en memoria, se agrega el registro nuevo (con su cabecera) + al comienzo del espacio libre (calculado a partir del tamaño del bloque + y el espacio libre en bloque) y se lo graba en disco. + Finalmente se agrega (o actualiza) el identificador al archivo índice y + el espacio libre en el bloque. +\layout Standard + +Si el registro ocupara más de un bloque (ver sección +\begin_inset LatexCommand \ref{sub:tipo1_reg_multi} + +\end_inset + +), se buscan N bloques consecutivos (todos los que necesite el registro) + absolutamente libres +\begin_inset Foot +collapsed false + +\layout Standard + +Incluso el último bloque debe estar absolutamente libre para cumplir con + las condiciones presentadas en la sección +\begin_inset LatexCommand \ref{sub:tipo1_reg_multi} + +\end_inset + +. +\end_inset + + y graba bloque a bloque cada +\emph on +fragmento +\emph default + del registro (con sus cabeceras intermedias), al último +\emph on +fragmento +\emph default + se lo trata de forma análoga a un registro +\emph on +simple +\emph default +. + Por cada bloque utilizado se actualiza el archivo de control de espacio + libre. +\layout Standard + +Ver: +\family typewriter +emufs_tipo1_agregar_registro() +\layout Subsection + +Bajas de registros +\layout Standard + +Al eliminar un registro lo primero que se hace es actualizar los archivos + de índice y de identificadores recuperables, poniendo como número de bloque + el valor especial +\family typewriter +EMUFS_NOT_FOUND +\family default + y agregando el identificador del registro a borrar respectivamente. + También se actualiza el archivo de control de espacio libre por cada bloque + (en caso de ser más de uno, en registros +\emph on +multibloque +\emph default +, se actualizan todos los bloques) y se carga el bloque en memoria para + +\emph on +alinear los datos a izquierda +\emph default + (en caso de ser un registro +\emph on +multibloque +\emph default +, esto se realiza sólo para el último bloque). + Para alinear los datos, se recorre secuencialmente en bloque (leyendo la + cabecera de cada registro y salteando los datos) hasta encontrar el registro + a borrar. + Encontrado el registro, se copian todos los bytes que se encuentran entre + el fin del registro a borrar y el fin del bloque, en el comienzo del bloque + borrado. +\layout Standard + +Ver: +\family typewriter +emufs_tipo1_borrar_registro() +\layout Subsection + +Modificación de registros +\layout Standard + +Se optó por un algoritmo simple y general, que usa las funciones de alto + nivel mencionadas hasta ahora. + Simplemente borra el registro y vuelve a crearlo. + Al recuperar el último identificador de registro borrado, nos aseguramos + de que se mantenga el identificador del registro. +\layout Standard + +Ver: +\family typewriter +emufs_tipo1_modificar_registro() +\layout Subsection + +Obtención de estadísticas +\layout Standard + +Es una función bastante simple, con una única complicación que mencionaremos + más adelante. +\layout Standard + +Para obtener las máximas desviaciones, cantidad total de espacio libre, + cantidad de registros y tamaño de los archivos auxiliares se utilizan las + funciones apropiadas de los archivos auxiliares (ver secciones +\begin_inset LatexCommand \ref{sec:idx} + +\end_inset + +, +\begin_inset LatexCommand \ref{sec:fsc} + +\end_inset + + y +\begin_inset LatexCommand \ref{sec:did} + +\end_inset + +). +\layout Standard + +Para obtener la cantidad de bloques se hace el siguiente calculo: +\layout LyX-Code + +cant_bloques = (tamaño_archivo_datos - tamaño_cabecera_archivo_datos) +\layout LyX-Code + + / tamaño_bloque; +\layout Standard + +Hasta aquí no hay mayores inconvenientes. + El problema se presenta para calcular el tamaño de la información de control + utilizada por el archivo de datos; se utiliza el siguiente cálculo: +\layout LyX-Code + +tam_info_control_datos = tamaño_cabecera_archivo_datos +\layout LyX-Code + + + cant_registros * tamaño_cabecera_registro; +\layout Standard + +Aunque a simple vista esto parece acertado, no contempla el caso de los + registros +\emph on +multibloque +\emph default + (pág +\begin_inset LatexCommand \pageref{sub:tipo1_reg_multi} + +\end_inset + +), estos registros almacenan +\family typewriter +tamaño_cabecera_registro * N +\family default +, donde +\family typewriter +N +\family default + es la cantidad de bloques que ocupan. + Salvar este caso sería muy costoso, porque habría que recorrer el archivo + registro a registro, +\emph on +fragmento +\emph default + a +\emph on +fragmento +\emph default + e ir contando todas las cabeceras de registro que aparecen (similar a lo + que se hace en la compactación, ver sección +\begin_inset LatexCommand \ref{sub:tipo1_compact} + +\end_inset + +). + Al tratarse este de un caso excepcional, se optó por mantener la función + simple ya que funciona bien en la mayoría de los casos. +\layout Standard + +Ver: +\family typewriter +emufs_tipo1_leer_estadisticas() +\layout Subsection + + +\begin_inset LatexCommand \label{sub:tipo1_compact} + +\end_inset + +Compactación del archivo de datos +\layout Standard + +Esta función es una de las más simples, porque se limita a un algoritmo + muy simple que utiliza las funciones de +\emph on +alto nivel +\emph default + antes nombradas para realizar su tarea. + Básicamente recorre el archivo de índices de registros, de comienzo a fin, + leyendo el registro, borrándolo y volviéndolo a insertar. + Si había espacio libre en un bloque anterior al que estaba, será insertado + en él, si no volverá a grabarse en el lugar en que estaba. + De esta forma se aprovechan todos los espacios libres intermedios, concluyendo + con un archivo igual o más pequeño que el original. +\layout Standard + +Esta implementación no es la más eficiente, pero siendo que esta es una + operación costosa y excepcional por naturaleza, se optó por mantener el + algoritmo simple a costo de un poco de eficiencia. +\layout Standard + +Ver: +\family typewriter + emufs_tipo1_compactar() +\layout Chapter + + +\begin_inset LatexCommand \label{cha:tipo2} + +\end_inset + +Archivo sin bloques y registros de longitud variable +\layout Standard + +Este tipo de archivo nos traerá a la mesa la particularidad de grabar registros + de longitud variable sin realizar su agrupación en bloques, y como veremos + en la siguiente sección, también permitirá la administración de gaps que + queden en el archivo luego de operaciones de baja de registros. +\layout Section + +Organización física +\layout Standard + +Este tipo de archivo realizará el almacenamiento de registros de longitud + variable en disco, su borrado y modificación sin la utilización de bloques + de ningún tipo. + Su implementación se encuentra en los archivos fuente ( +\series bold +tipo2.c +\series default + y +\series bold +tipo2.h +\series default +). +\layout Standard + +Los archivos del tipo 2, presentarán al comienzo del mismo un header compuesto + simplemente por un dato del tipo EMUFS_Tipo (int) el cual indicará el tipo + de archivo en cuestión. +\layout Standard + +Para poder entender mejor la organización física de este tipo de archivo, + tomemos el caso hipotético en el que se encuentran grabados +\series bold +dos registros +\series default + (comenzando desde registro 0) de +\series bold +30 bytes +\series default +, y +\series bold +25 bytes +\series default +, respectivamente. + Supongamos también que entre el registro 0 y 1 se encontraba un +\series bold +registro de 10 bytes +\series default + que fue +\series bold +borrado +\series default +, generando un +\series bold +gap +\series default + +\series bold +o freespace +\series default +. + Si miramos al archivo de datos (.dat) en el disco nos encontraremos con + lo siguiente: +\begin_inset Float figure +placement H +wide false +collapsed false + +\layout Caption + +Organización física de los registros en disco +\layout Standard + + +\begin_inset Graphics + filename graphics/Example1.png + width 100text% + +\end_inset + + +\end_inset + + +\layout Standard + +Como se puede observar, a nivel físico cada registro grabado esta compuesto + por un Header cuyo tamaño total es de 8 bytes ( +\series bold +EMUFS_REG_ID +\series default + + +\series bold +EMUFS_REG_SIZE +\series default +), y posteriormente el registro (bloque de datos) en sí. + 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. +\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 índice ( +\series bold +.idx +\series default +), permite la localización 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ítulo, tendremos + las siguientes entradas en el archivo índice +\series bold +.idx +\series default +: +\begin_inset Float table +placement H +wide false +collapsed false + +\layout Caption + +Organización física del archivo de índice o posiciones relativas. +\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 + + +\end_inset + + +\layout Standard + + +\series bold +\emph on +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 + +Archivo de Gaps / Espacios Libres (.fsc) +\layout Standard + +El archivo de espacios libres o gaps (.fsc), tiene como función la administración + 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 también 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 +: +\begin_inset Float table +placement H +wide false +collapsed false + +\layout Caption + +Organización física del archivo de +\emph on +gaps +\emph default +o control de espacio libre. +\layout Standard + + +\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 + + +\end_inset + + +\layout Standard + + +\series bold +\emph on +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 +\series bold +.dat +\series default +. +\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 ÚNICA 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 + +Funciones Principales +\layout Standard + +Dentro de +\series bold +\emph on +tipo2.h +\series default +\emph default + y +\series bold +\emph on +tipo2.c +\series default +\emph default + se encuentran las cabeceras y la implementación de las funciones principales + respectivamente, las cuales dan funcionalidad a esta organización. + +\layout Standard + +A continuación se comentará el funcionamiento algunas de las mas importantes. +\layout Subsection + +Lectura de registros +\layout Standard + +Como se vio al comienzo, los registros en este tipo de archivo no se encuentran + agrupados en bloques de ninguna índole y están dispersos a lo largo del + archivo, con la particularidad de que pueden existir gaps o espacio libre, + entre dos registros dados. +\layout Standard + +Por ende la lectura de registros en este tipo de organización es muy simple + y dada la inexistencia de bloques, el procedimiento será el siguiente: +\layout Enumerate + +Se determina el offset en bytes, donde comienza el registro deseado, a través + de su ID, buscando la misma en el archivo índice ( +\series bold +.idx +\series default +) +\layout Enumerate + +Ya determinada la posición física del registro dentro del archivo de datos + ( +\series bold +.dat +\series default +), nos posicionamos en la misma, y leemos el header del registro ( +\series bold +IDReg +\series default + + +\series bold +RegSize +\series default +). + 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 +\layout Standard + +En el proceso de alta de registros entrarán en juego dos archivos descriptos + en la +\emph on +sección de archivos auxiliares +\emph default +, siendo estos el archivo índice ( +\series bold +.idx +\series default +), y el archivo de gaps / espacios libres ( +\series bold +.fsc +\series default +). +\layout Standard + +Así pues, a la hora de realizar una inserción de un registro en el archivo + de datos, el procedimiento será el siguiente: +\layout Enumerate + +Calculamos el espacio que necesitaremos para el registro: sizeof( +\series bold +EMUFS_REG_ID +\series default +) + sizeof( +\series bold +EMUFS_REG_SIZE +\series default +) + sizeof(registro). +\layout Enumerate + +Determinamos donde debemos insertar el registro, ya sea un gap donde entre, + o bien al final del archivo. +\layout Enumerate + +Insertamos el registro e información de control ( +\series bold +header +\series default ++ +\series bold +data +\series default +), en la posición indicada en el paso 2. +\layout Enumerate + +En caso de haber utilizado un GAP, actualizamos el espacio libre restante + en el mismo y en caso de que se haya utilizado al totalidad del GAP, se + lo elimina del archivo ( +\series bold +.fsc +\series default +). +\layout Enumerate + +Actualizamos la entrada correspondiente al registro ingresado (determinada + por su RegID), en el archivo índice ( +\series bold +.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 +\layout Standard + +En el proceso de baja de registros entrarán en juego los tres archivos descripto +s en la +\emph on +sección de archivos auxiliares +\emph default +, siendo estos el archivo índice ( +\series bold +.idx +\series default +), el archivo de gaps / espacios libres ( +\series bold +.fsc +\series default +) y el archivo de ID's liberados ( +\series bold +.did +\series default +). +\layout Standard + +Dado que en la implementación de este tipo de organización física contamos + con los gaps o espacios libres entre registros, no se eliminará físicamente + el registro del archivo de datos ( +\series bold +.dat +\series default +), pues entonces carecería de sentido el archivo anteriormente mencionado + ( +\series bold +.fsc +\series default +). + En cambio, se agrega el gap dejado por la eliminación a dicho archivo, + y se marca físicamente en el archivo de datos la eliminación mediante un + fill de los bytes correspondientes con un caracter nulo. + (hexa 00 y con el propósito de probar fehacientemente que el sistema funciona). +\layout Standard + +El proceso de baja o eliminación de un registro constará luego de los siguientes + pasos: +\layout Enumerate + +Se obtiene el offset o posición relativa en donde se encuentra grabado el + registro dentro del archivo de datos. +\layout Enumerate + +Se obtiene el tamaño del registro y se realiza un dummyfill del sector del + archivo correspondiente al registro que se está dando de baja. + (Se rellena la zona correspondiente a su header+data). +\layout Enumerate + +Se agrega el GAP generado al archivo de gaps o espacios libres, y en caso + de haberse generado un GAP lindante con otro GAP, se realizará un merge + de los mismos y se los registrará bajo una única entrada en el archivo + de espacios libres (.fsc). +\layout Enumerate + +Se agrega el ID que fue liberado, al archivo de ID's liberados ( +\series bold +.did +\series default +), al final del mismo ( +\emph on +pila +\emph default +). +\layout Enumerate + +Se marca en el archivo índice ( +\series bold +.idx +\series default +) 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 +\layout Standard + +Dada la naturaleza del archivo de ID's liberados, y el manejo de espacio + libre del que consta esta organización de archivo, el proceso de modificación + de un registro se limita a los siguientes pasos: +\layout Enumerate + +Se realiza la lectura del registro, mediante el respectivo procedimiento + ya desarrollado anteriormente. +\layout Enumerate + +Una vez que se cuenta con los nuevos datos modificados, se procede a dar + de baja el registro que ha sido modificado, e inmediatamente después se + realiza una inserción con los nuevos datos. +\layout Standard + + +\series bold +\emph on +NOTA: +\series default +\emph default + 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 Standard + +Así como los otros dos tipos de datos, el que nos compete también cuenta + con la posibilidad de realizar la compactación de datos cuando el usuario + lo desee, justificando todos los registros a izquierda, eliminando así + los gaps existentes y decrementando el tamaño del archivo en disco (truncándolo +). +\layout Standard + +Para poder comprender como hemos implementado el proceso de re-compactación + en nuestro tipo de archivo 2, nos ayudaremos de esquemas a través de los + cuales iremos describiendo el proceso. + Notemos antes, que el proceso de compactación esta directamente ligado + con el archivo de gaps o espacios libres ( +\series bold +.fsc +\series default +). +\layout Standard + +Comencemos con el siguiente cuadro situacional: +\begin_inset Float figure +placement H +wide false +collapsed false + +\layout Caption + +Archivo con gaps entre registros previo a compactación +\layout Standard + + +\begin_inset Graphics + filename graphics/Compact1.png + width 100text% + keepAspectRatio + +\end_inset + + +\end_inset + + +\layout Standard + +Partiendo de esta base, el algoritmo de compactación tomará en su inicio + al primer gap existente dentro del archivo de datos, en este caso llamado + +\series bold +Gap0 +\series default +. + Luego, establecerá que el +\series bold +Source +\series default + a partir de donde se quieren mover datos, sera: +\layout LyX-Code + +StartGap0 + SizeGap0 = EndGap0 = Source +\layout Standard + +Lo cual no es nada más y nada menos que lo obvio, la fuente a partir de + donde se mueven los datos, sera el fin del primer gap, donde comienzan + datos. + Como destino ( +\series bold +Destination +\series default +) del movimiento, se establece inicialmente, el inicio del gap, o sea +\series bold +StartGap0 = Destination +\series default +. +\layout Standard + +Luego, el algoritmo entrara en un bucle while (mientras haya bucles por + levantar), el cual trabajara hasta el final de la compactación de la siguiente + manera: +\layout Standard + + +\series bold +Mientras haya Gaps +\series default + { +\layout Enumerate + +Se levanta el próximo gap al levantado en una instancia previa. + En este ejemplo, durante el primer loop del while, se levantará +\series bold +Gap1 +\layout Enumerate + +Luego, se calcula cuantos bytes hay que mover hacia el Destination de la + siguiente manera: +\layout Enumerate + + +\series bold +Mustmove_bytes +\series default + = +\series bold +StartGap1 +\series default + - +\series bold +Source +\series default + = +\series bold +StartGap1 +\series default + - +\series bold +EndGap0 ( +\series default +Lo cual nuevamente es lógico pues querremos mover lo que se encuentra entre + el final del primer gap levantado y el inicio del siguiente). +\layout Enumerate + +Se realiza el movimiento de los datos, utilizando las direcciones +\series bold +Source +\series default + y +\series bold +Destination +\series default +, así como la variable +\series bold +Mustmove_bytes +\series default + que nos indica cuantos bytes transferir. +\series bold + +\newline +IMPORTANTE: +\emph on +La transferencia se hace de a chunks de 25 bytes + un resto segun el valor + de Mustmove_bytes. +\layout Enumerate + +Se establece como gap de referencia, al ultimo gap leído (En este caso se + realiza: +\series bold +StartGap0 +\series default + = +\series bold +StartGap1 +\series default +, +\series bold +Gap0Size = Gap1Size +\series default +) y termina el código de repetición del bucle, dando lugar a la carga del + siguiente gap en el inicio del mismo. +\layout Standard + + +\series bold +} +\layout Standard + +Luego del primer bucle, el archivo se vera de la siguiente forma: +\begin_inset Float figure +placement H +wide false +collapsed false + +\layout Caption + +Archivo con gaps en disco luego del primer bucle de compactación +\layout Standard + + +\begin_inset Graphics + filename graphics/Compact2.png + width 100text% + +\end_inset + + +\end_inset + + +\layout Standard + +Notemos que al final de la porción de datos de los bytes movidos (donde + quedo apuntando +\series bold +Destination +\series default +), hay basura que será pisada por el próximo movimiento. +\layout Standard + +En el próximo loop, el bucle levantará un nuevo gap, y utilizando el gap + anterior (En esta caso el Gap anterior será +\series bold +Gap1 +\series default +) como referencia, realizará los mismos cálculos, desde donde transferir + y cuantos bytes mover. + (El destino es solo establecido inicialmente por código, y para el resto + del algoritmo es el lugar donde quedo el puntero destination luego de la + última escritura). +\layout Standard + +Una vez que se salga del bucle while, se realizará un último movimiento + preprogramado, donde la fuente ( +\series bold +Source +\series default +) será el final del ultimo gap, y la cantidad de bytes a mover será lo que + se encuentre luego del mismo hasta el fin de archivo. +\layout LyX-Code + +Source = StartLastGap + SizeLastGap = EndLastGap +\layout LyX-Code + +Mustmove_bytes = Datsize - Source +\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 + 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 + también políticas 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 re-compactació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 hallar 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 + + +\begin_inset LatexCommand \label{cha:tipo3} + +\end_inset + +Archivo con bloques parametrizados y registros de longitud constante +\layout Standard + +Las distintas organizaciones de archivos buscan aprovechar al máximo el + espacio del archivo. +\layout Standard + +En este caso veremos que sucede luego de agregar y borrar una gran cantidad + de registros del archivo, lo que provoca como consecuencia directa la fragmenta +ción del archivo, es decir, quedan huecos entre un registro y otro, lo que + produce un desperdicio de espacio. +\layout Standard + +La implementación de este tipo de archivo puede ser encontrada en +\family typewriter +emufs/tipo3.c +\family default + mientras que su interfaz pública está disponible en +\family typewriter +emufs/tipo3.h +\family default +. +\layout Section + +Organización Física +\layout Standard + +Esta organización guarda los registros pertenecientes al archivo en bloques + de tamaño parametrizado, de modo que intentará guardar la mayor cantidad + de registros que quepan en un bloque. + +\layout Standard + +Así como los graba, también tendrá la posibilidad de leer registros y borrarlos + del archivo. +\layout Standard + +El archivo estará compuesto por una cabecera que da información sobre el + tipo (2, o el valor T3 del tipo +\family typewriter +EMUFS_Tipo +\family default + en este caso) de organización, el tamaño de los bloques y el tamaño de + los registros. +\layout LyX-Code + +archivo +\layout LyX-Code + ++-----------+-----------+-----------+------------------------//-+ +\layout LyX-Code + +| tipo | tam_bloque| tam_reg | Cero o más bloques ... + +\backslash + +\backslash + | +\layout LyX-Code + ++-----------+-----------+-----------+------------------------//-+ +\layout LyX-Code + +/- 4 bytes -/- 4 bytes -/- 4 bytes -/ +\layout Subsection + +Organización Física de un Bloque +\layout Standard + +Cada bloque será capaz de contener la cantidad de registros enteros que + quepan en él. + De esta manera un registro que no entre completamente en el bloque deberá + almacenarse en un bloque diferente. +\layout Standard + +Los bloques no contienen ninguna información adicional, solo se conoce su + tamaño y se usa para delimitar +\begin_inset Quotes eld +\end_inset + +virtualmente +\begin_inset Quotes erd +\end_inset + + zonas en el archivo y obtener de esta manera acceso semi-aleatorio a los + registros. +\layout LyX-Code + +bloque N-1 | bloque N | bloque N+1 +\layout LyX-Code + +/----------+------------+------------+---------------+-----------/ +\layout LyX-Code + + +\backslash + | registro 1 | registro 2 | espacio libre | +\backslash + +\layout LyX-Code + +/----------+------------+------------+---------------+-----------/ +\layout LyX-Code + + /------------- tamaño del bloque ---------/ +\layout Subsection + +Organización Física de Registros +\layout Standard + +Cada registro se almacena en un bloque, y contiene una cabecera que indica + su +\emph on +ID, +\emph default +por este motivo al realizar la búsqueda de espacio en un bloque se lo hará + preguntando por el tamaño del registro más +\family typewriter +sizeof(EMUFS_REG_ID). +\layout LyX-Code + +registro [id] +\layout LyX-Code + ++-----------+-------------------+ +\layout LyX-Code + +| id | datos ... + | +\layout LyX-Code + ++-----------+-------------------+ +\layout LyX-Code + +/- 4 bytes -/- [tam_reg] bytes -/ +\layout Subsection + +Organización Física de Registros +\emph on +Multibloque +\layout Standard + +Al ser los registros de longitud constante, se ha adoptado que un registro + +\emph on +multibloque +\emph default + nunca podrá estar almacenado en algún lugar que no sea el comienzo de un + bloque. + De esta manera se puede calcular cuantos bloques ocupará un registro y + se podrá solicitar lugar para almacenarlo con la ayuda de la función +\family typewriter +emufs_fsc_buscar_n_lugares(), +\family default +que es muy importante para evitar el solapamiento de registros. + Esta consideración acarrea como consecuencia directa un alto costo en términos + del espacio desperdiciado. +\layout Standard + +A continuación se presenta un ejemplo gráfico de un registro multibloque + de 26 bytes (de contenido +\begin_inset Quotes eld +\end_inset + +12345678901234567890123456 +\begin_inset Quotes erd +\end_inset + +) almacenado en un archivo con bloques de bytes 14 bytes (10 para datos) + y registros de 38 bytes: +\layout LyX-Code + +| bloque 0 | bloque 1 | bloque 2 +\layout LyX-Code + ++-------------------+-------------------+-------------------+-//-+ +\layout LyX-Code + +| registro 0 - 1/3 | registro 0 - 2/3 | registro 0 - 3/3..| +\backslash + +\backslash + | +\layout LyX-Code + +|+----+------------+|+----+------------+|+----+--------+....| // | +\layout LyX-Code + +|| id | datos ||| id | datos ||| id | datos |....| +\backslash + +\backslash + | +\layout LyX-Code + +||----+------------+||----+------------+||----+--------+....| // | +\layout LyX-Code + +|| 0 | 1234567890 ||| 0 | 1234567890 ||| 0 | 123456 |....| +\backslash + +\backslash + | +\layout LyX-Code + +|+----+------------+|+----+------------+|+----+--------+....| // | +\layout LyX-Code + ++-------------------+-------------------+-------------------+- +\backslash + +\backslash +-+ +\layout LyX-Code + + ^^^^ +\layout LyX-Code + + 4 bytes libres (e inutilizables) al final del bloque 2 +\layout Section + +Funciones Principales +\layout Standard + +Dento de +\family typewriter +tipo3.h +\family default + y +\family typewriter +tipo3.c +\family default + se encuentran las cabeceras y la implementación de las funciones principales + respectivamente, las cuales dan funcionalidad a esta organización. +\layout Standard + +A continuación se comentará la descripción de algunas acciones importantes. +\layout Subsection + +Lectura de registros +\layout Standard + +La lectura de un registro se realiza con la ayuda del archivo . +\emph on +idx +\emph default + el cual contiene la información de la posición del registro dentro del + archivo de datos. + Una vez leída esta información, se recupera el bloque (en su totalidad) + del archivo y se busca secuencialmente el registro con el +\emph on +ID +\emph default + especificado. +\layout Standard + +Ver: +\family typewriter +emufs_tipo3_leer_registro() +\layout Subsection + +Alta de registros +\layout Standard + +Graba un registro en un bloque donde haya espacio suficiente, y si no crea + un nuevo bloque y lo agrega al final del archivo. +\layout Standard + +Luego de grabar un registro, actualiza los archivos de índice .idx y .fsc + para mantener la coherencia. +\layout Standard + +Cuando nos encontramos con registros multibloque, se calcula cuantos bloques + ocupará el registro de la siguiente manera: +\family typewriter +Cantidad de Bloques = 1 + Tamaño del Registro/(Tamaño del Bloque-Sizeof(EMUFS_RE +G_ID) +\layout Standard + +Esta ecuación solo falla en el caso que el tamaño del registro y el tamaño + del bloque sean iguales, en tal caso, se coloca el valor 1 en +\family typewriter +Cantidad de Bloques +\family default + post verificación. +\layout Standard + +Y con esta información se realiza un ciclo +\family typewriter +for +\family default + que grabará tantas veces como sea necesario levantando y grabando los bloques + que correspondan. +\layout Standard + +Ver: +\family typewriter +emufs_tipo3_grabar_registro() +\layout Subsection + +Baja de registros +\layout Standard + +Borra un registro del archivo de datos, para esto levanta el bloque al que + pertenece el archivo y ajusta los demás registros justificándolos hacia + la izquierda. +\layout Standard + +Cabe destacar que para dar de baja un registro no hace falta borrarlo del + archivo de datos, solo es necesario borrar las entradas en los archivos + de índice, pero cuando se realiza el ajuste el algoritmo toma porciones + del bloque del tamaño de un registro mas su encabezado - comenzando desde + el siguiente al que fue borrado - y copia (sobreescribe) sobre el anterior. + De esta manera, la información correspondiente al registro borrado no estará + presente en el archivo de datos. + Esto es una consecuencia del ajuste al borrar un registro, pudiendo no + ser así, si no se realizara el mismo. +\layout Standard + +En el caso de los registros multibloque, se eliminará la porción del registro + contenida en el primer bloque y se actualizarán de manera conveniente los + archivos índice, para restaurarlos a un valor verdadero. +\layout Standard + +Ver: +\family typewriter +emufs_tipo3_borrar_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_tipo3_leer_estadisticas() +\layout Subsection + +Compactación del archivo de datos +\layout Standard + +Esta función intenta reorganizar el archivo de manera que el espacio libre + sea lo menor posible, recordando siempre que un registro no puede ser almacenad +o en mas de un bloque excepto que el tamaño del registro sea mayor que el + del bloque. +\layout Standard + +Para realizar esto, se aprovecha la funcionalidad de +\emph on +emufs_tipo3_grabar_registro() +\emph default +ya que esta tiene la capacidad de determinar una posición mas eficiente + en el archivo para un registro. + Por esto lo que se hace es levantar uno por uno los registros y volverlos + a grabar, de ese modo todos los +\emph on +gaps +\emph default +que pudieron haberse formado por la eliminación de registros serán cubiertos + 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 vacíos para truncar + el archivo. + Lo mismo se debe hacer con el archivo de espacios libres . +\emph on +fsc +\emph default +el cual disminuye su tamaño también. +\layout Standard + +Ver: +\family typewriter +void emufs_tipo3_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. +\layout Enumerate + +Cada registro tiene un encabezado que indica el +\emph on +id +\emph default +del mismo. +\layout Enumerate + +Si el tamaño del registro es mayor que el tamaño del bloque el registro + se particionará en la cantidad de bloques que sea necesario, pero siempre + se guardará desde el comienzo de un bloque, esto quiere decir que nunca + se podrá encontrar un comienzo de registro en algún lugar de un bloque + que no sea el comienzo del mismo. +\layout Enumerate + +Si el registro se divide en mas de un bloque, se le coloca el id como encabezado + igualmente, pero en el archivo . +\emph on +idx +\emph default + solo se guarda el primer bloque. + En el +\emph on +.fsc +\emph default + se actualizan todos los bloques con el espacio libre que realmente tienen. +\layout Chapter + +EMUFS View (interfaz gráfica) +\layout Section + +Introducción +\layout Standard + +La interfaz de visualización de EMUFS permite interactuar con los distintos + tipos de archivos para cada conjunto de datos almacenado (ya sean facturas, + articulos, o notas de facturas). +\layout Section + +Instalación +\layout Standard + +Para poder correr la interfaz gráfica necesitará previamente compilarla + (así como compilar los programas auxiliares), para ello necesitará cumplir + con los siguiente requisitos: +\layout Enumerate + +Compilador gcc versión 3.3.x preferentemente. + No podemos garantizar la compatibilidad con otras versiones debido a cambios + drásticos que sufrieron las versiones anteriores. +\layout Enumerate + +Parser XML libxml2 versión 2.6.x . + Versiones 2.5 y anteriores son incompatibles en la API y no funcionarán. +\layout Enumerate + +libncurses version 5 o superior (probado con 5.4). +\layout Enumerate + +GNU Make. +\layout Subsection + +Compilar GUI +\layout Standard + +Para compilar la GUI solo debe ejecutar el comando make dentro del directorio + raíz del proyecto. + Esto compilará primero una biblioteca estática con los manejadores de los + 3 tipos de archivo y luego compilará la GUI. +\layout LyX-Code + +#~/emufs/> make +\layout Subsection + +Preparar el banco de pruebas +\layout Standard + +Antes de comenzar a utilizar la GUI deberá generar los archivo XML desde + donde serán leídos los datos para generar los archivos que luego se utilizará. + Para ello el proceso de compilación creará 2 ejecutable : generar_fact + y generar_art, que se ubicarán en la carpeta generar dentro de emufs_gui. +\layout Standard + +Estos programas generan facturas y artículos respectivamente en forma aleatorio, + utilizando diccionarios de datos para llenar los campos. + Primero deberá ejecutar generar_art, ya que éste último crea un diccionario + de artículos que luego utilizará generar_fact para los items de las facturas. +\layout Standard + +Ambos programas reciben 2 parámetros : el nombre de archivo de salida y + la cantidad de entradas a generar. +\layout Standard + +El generador de facturas fue diseñado para cumplir con los porcentajes pedidos + por el enunciado en algunos aspectos. + La cantidad de facturas por dia del mes es aleatoria. +\layout Section + +Línea de comandos +\layout Standard + +El programa acepta varios parámetros, algunos de ellos opcionales, otros + obligatorios dependiendo de las elecciones realizadas. +\layout Standard + +Para obtener una completa descripción de los parámetros el programa acepta + +\begin_inset Quotes eld +\end_inset + +-h +\begin_inset Quotes erd +\end_inset + + o +\begin_inset Quotes eld +\end_inset + +--help +\begin_inset Quotes erd +\end_inset + + para mostrar una ayuda en línea. +\layout Standard + +Si el programa es ejecutado sin parámetros tratará de recuperar los artículos + y las facturas desde archivo previamente creados. +\layout Standard + +Para crear un archivo de artículos a partir de un archivo XML bien formado, + se debe ejecutar el programa con la opción +\begin_inset Quotes eld +\end_inset + +-a +\begin_inset Quotes erd +\end_inset + +. + Dicha opción espera que el siguiente parámetro sea el nombre del archivo + a leer, y que éste útimo tenga extensión xml (notar que es solo minúsculas). + A continuación espera encontrar el tipo de archivo que se quiere crear, + pudiendo ser éste último 1, 2 ó 3. + De ser el tipo de archivo con bloques, se le exigirá que ingrese como último + parámetro el tamaño del mismo. +\layout Standard + +Para crear el archivo de facturas es el mismo procedimiento, solo que utilizando + el parámetro +\begin_inset Quotes eld +\end_inset + +-f +\begin_inset Quotes erd +\end_inset + +. + Luego de los parámetros de tipo y tamaño de bloque debe especificarse el + tipo y tamaño de bloque para el archivo de notas. + +\layout Standard + +Debe saber que estos parámetros no son mutuamente excluyentes, por lo que + podrá utilizarlos al mismo tiempo. +\layout Section + +Características +\layout Standard + +A continuación se da una lista detallada de las operaciones que son posibles + hacerse desde esta interfaz : +\layout Itemize + +Alta, baja y modificación de Artículos. + Para ello se abrirá una ventana donde se podrá editar comodamente los datos. +\layout Itemize + +Alta, baja y modificación +\begin_inset Foot +collapsed true + +\layout Standard + +En la modificación de una factura no se podrán cambiar ni la cantidad de + items y los datos de los mismo!. + La nota si podrá ser modificada. +\end_inset + + de Facturas. +\layout Itemize + +Ver registros. + Ver fisicamente los registros de cualquiera de los archivos sin importar + el tipo al que pertenezcan. + Desde aquí podrá tambien eliminar, agregar o modificar el registro actual. +\layout Itemize + +Ver Bloques. + Para aquellos archivos que hallan sido creados con un tipo con bloques, + podrá verlos fisicamente, viendo el bloque actual y los anteriores/posteriores. +\layout Itemize + +Ver las estadísticas de cada archivo según su tipo, para realizar comparativas +\layout Itemize + +Cambiar el formato de cualquier tipo o parametros de archivo. +\layout Itemize + +Compactar los archivos. +\layout Section + +Decisiones de Diseño +\layout Standard + +Durante el desarrollo se han tomado ciertas decisiones en el diseño o restriccio +nes. + En este punto nos centraremos en las especificas tomadas por la interfaz + de visualización, y no tomaremos en cuenta las que ponen los tipos de archivo + por si solos. +\layout Enumerate + +La cantidad de items por factura es igual a 10 para archivos de registro + de longitud fija y bloque parametrizado (TIPO 3). + Esta decición fue tomada por poner un valor típico de items que puede haber + en una factura, evaluando un caso de un comercio chico. + Como el tipo de archivo permite cortar un registro y guardarlo en varios + bloques consecutivos, la restricción de cantidad solo es un hecho de elección, + y así pusieramos 100, 1000, 10000 no habría diferencia, ya que el tipo + de archivo lo guardaría sin problemas. +\layout Enumerate + +Si el archivo es de TIPO 3 y se agregan más de 10 items estos son truncados + y descartados sin aviso al usuario. + Esta fue una desición basada en el tiempo del proyecto. + De tener que validar y consultar al usuario se hubiera perdido tiempo de + mucho valor para completar objetivos más importantes del TP. +\layout Enumerate + +Los campos son delimitados por el caracter nulo (en caso de los strings) + y por la longitud del tipo de dato en caso de los campos numéricos. + De esta forma se aprovechan las características de manejo de string en + C. +\layout Section + +Vista de Registros +\layout Standard + +Un ejemplo de vista de registros es la que se observa a continuación : +\layout Standard + + +\begin_inset Graphics + filename gui_ver_registros.eps + width 14cm + keepAspectRatio + +\end_inset + + +\layout Standard + +Como puede verse el registro actual se ve resaltado respecto de los demás. + También se puede observar que en este caso (el bloque es de 2000 bytes) + no entra toda la información en pantalla, pero es posible desplazar utilizando + las teclas A y Z. +\layout Standard + +Los datos binarios son convertidos a texto para ser mostrados, siendo la + representación elegida : +\layout Itemize + +(XXX) : Representa un ID. + En el caso de las facturas también aparece en los datos el número de índice + de la nota asociada con esta representación. +\layout Itemize + +{XXX} : Representa el tamaño de los datos. + Esto siempre y cuando el registro sea de longitud variable (TIPO1 y TIPO2). +\layout Standard + +También es posible ejecutar acciones de edición sobre el registro seleccioado, + así como buscar por ID de registro. +\layout Standard + +Cuando se procesa la información en crudo (es decir, el area de datos) algunos + bytes son modificados para evitar errores visuales. + Un caso es cuando el bytes es compuesto por 8 bits de valor 0 (caracter + +\backslash +0). + Lo que se hace es cambiarlo por un caracter que tenga representacion visual + (en este caso un *). + Lo mismo suscede para los caracteres de control ( +\backslash +b +\backslash +n +\backslash +r por ejemplo) y los espacion. + Esta política fue tomada ya que estos caracteres modifican la salida en + pantalla, y de no evitar su envío a la pantalla, producirían resultados + inesperados en la visualización. +\layout Section + +Bugs conocidos +\layout Standard + +A continuación se enumera los errores que sabemos que existen, que no hemos + tenido tiempo de corregir, pero que no hacen al TP en sí : +\layout Enumerate + +Si la consola o terminal cambia de tamaño la GUI no sigue el nuevo tamaño, + pudiendose producir defectos visuales. + Esto es debido a que se debe capturar una señal que envia el SO, pero no + pudimos hacer que funciones con todas las terminales bajo X, por lo que + se decidio dejarlo para cuando tengamos tiempo. +\layout Enumerate + +Si la GUI fue compilada con -DDEBUG y no se utiliza un PIPE para redirigir + la salida de error estandar, es posible que algun componente del programa + emita un mensaje de debug o warning y esta cause defectos de visualización + o el programa deje directamente de funcionar. + Esto es un defecto de la biblioteca NCurses. +\layout Enumerate + +Cuando se cargan datos desde el XML y este contiene caracteres extendidos, + estos son mostrados en UTF8 en la pantalla. + Si no posee una consola configurada en UTF8 verá los caracteres extendidos + en su representación ASCII (2 caracteres por cada caracter extendido). + Esto se da a causa de que la LibXml maneja de forma interna todo en UTF8 + sin importar el encoding declarado en el XML. + El encoding solo lo tienen en cuenta para guado se guarde. + No nos hemos tomado el trabajo de hacer la conversión solo por cuestiones + de tiempo. +\layout Chapter + +Comparación de tipos de archivo (conclusiones) +\layout Section + +Método utilizado para la comparación +\layout Standard + +Para realizar la comparación entre los distintos tipos de archivo, se generaron + un XML de artículos con 200 entradas y uno de facturas de 1750 entradas. + Los valores fueron arbitrarios y un poco más elevados que los requeridos + en el enunciado para poner a prueba el sistema. +\layout Standard + +En la tabla que se dará más adelante, se pueden apreciar los datos característic +os de cada tipo de archivo. + El método de prueba fue el siguiente : +\layout Enumerate + +Para cada tipo de archivo se cargaron los archivos XML de prueba. +\layout Enumerate + +Se anotaron las estadísticas que entrega la GUI. +\layout Enumerate + +Se eliminaron alrededor de 50 artículos y 200 facturas. + El valor no es exacto, puesto que al ser pseudo-aleatoria la cantidad borrada + puede no ser 50 o 200. +\layout Enumerate + +Se anotaron las estadísticas nuevamente. +\layout Standard + +Ahora, los tamaños de bloque para los archivos con bloques fueron tomados + de 512 bytes, por ser una unidad típica de dispositivos de almacenamiento, + y nos pareció lógico dada la similitud utilizar esta unidad. +\layout Section + +Artículos +\layout Standard + + +\begin_inset Float table +placement H +wide false +collapsed true + +\layout Caption + +Artículos con archivos con tamaño de bloque 512 (cuando aplica) +\layout Standard + + +\size small + +\begin_inset Tabular + + + + + + + + + + + +\begin_inset Text + +\layout Standard + + +\size small +Artículos +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +T1 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +T2 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +T3 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +T1 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +T2 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +T3 +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Tamaño de bloque: 512 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +Inicial +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +Luego de borrar +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Tamaño Datos +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +10528 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +10528 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +28800 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +7874 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +7278 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +17856 bytes +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Tamaño Datos de Control +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +1608 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +1604 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +812 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +1208 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +1108 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +508 bytes +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Espacio Libre +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +672 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +0 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +4704 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +3726 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +3746 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +15952 bytes +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Media de Espacio Libre +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +26 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +0 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +70 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +149 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +73 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +238 bytes +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Máximo de Espacio Libre +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +83 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +0 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +216 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +279 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +480 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +512 bytes +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Mínimo de Espacio Libre +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +2 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +0 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +68 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +36 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small + 41 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small + 68 bytes +\end_inset + + + + +\end_inset + + +\end_inset + + +\begin_inset Float table +placement H +wide false +collapsed true + +\layout Caption + +Artículos con archivos con tamaño de bloque 1024 (cuando aplica) +\layout Standard + + +\size small + +\begin_inset Tabular + + + + + + + + + + + +\begin_inset Text + +\layout Standard + + +\size small +Luego de borrar +\end_inset + + +\begin_inset Text + +\layout Standard + +T1 +\end_inset + + +\begin_inset Text + +\layout Standard + +T2 +\end_inset + + +\begin_inset Text + +\layout Standard + +T3 +\end_inset + + +\begin_inset Text + +\layout Standard + +T1 +\end_inset + + +\begin_inset Text + +\layout Standard + +T2 +\end_inset + + +\begin_inset Text + +\layout Standard + +T3 +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Tamaño de bloque: 1024 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +Inicial +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +Luego de borrar +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Tamaño Datos +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +10528 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +................ +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +28800 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +7902 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +................ +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +20448 bytes +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Tamaño Datos de Control +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +1608 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +................ +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +812 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +1208 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +................ +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +580 bytes +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Espacio Libre +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +1184 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +................ +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +5216 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +4210 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +................ +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +13800 bytes +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Media de Espacio Libre +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +91 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +................ +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +153 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +323 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +................ +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +405 bytes +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Máximo de Espacio Libre +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +938 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +................ +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +728 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +938 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +................ +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +1024 bytes +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Mínimo de Espacio Libre +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +0 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +................ +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +136 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +7 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +................ +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +136 bytes +\end_inset + + + + +\end_inset + + +\end_inset + + +\layout Standard + +Evidentemente para el caso de artículos, una muy mala elección sería utilizar + el archivo de tipo3, puesto que al usar registros constantes es posible + que se desperdicie mucho espacio si ocurren muchas eliminaciones (como + se observa en la tabla). + Entre los tipos 1 y 2 no existe mucha diferencia en los números, por lo + que la decisión podría ser tomada en base a los tiempos de acceso. + Tomando este criterio el T2 sería la mejor forma de almacenar los datos + si lo más frecuente son lecturas, ya que al leer se puede obtener el offset + desde el principio del registro, mientras que en el tipo1 se debe hacer + una búsqueda secuencial sobre el bloque, y de ser éste último muy grande + el tiempo de acceso puede ser elevado. +\layout Standard + +Para operaciones que requiera muchas bajas de elementos el tipo 2 no sería + la mejor opción, puesto que la liberación es compleja, ya que cuando se + da de baja un registro se debe verificar si dicho espacio se solapa con + algún espacio libre actual, de manera de mantener espacios libres como + lo hacen los sistemas de archivo ext2, manteniendo la lista de los offsets + y tamaño de espacios libres, a fin de buscar el que mejor ajuste en caso + de una alta. +\layout Standard + +Para el caso de artículos, donde puede haber un continuo cambio en la oferta + de nuestro negocio, nos inclinaremos por el tipo de archivo 1, con un tamaño + de bloque reducido. + Solo recordaremos compactar el archivo periódicamente a fin de minimizar + el espacio desperdiciado. +\layout Section + +Facturas +\layout Standard + + +\begin_inset Float table +placement H +wide false +collapsed true + +\layout Caption + +Facturas con archivos con tamaño de bloque 512 (cuando aplica) +\layout Standard + + +\size small + +\begin_inset Tabular + + + + + + + + + + + +\begin_inset Text + +\layout Standard + + +\size small +Facturas +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +T1 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +T2 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +T3 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +T1 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +T2 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +T3 +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Tamaño de bloque = 512 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +Inicial +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +Luego de borrar +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Tamaño Datos +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +268707 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +268707 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +546000 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +207295 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +212465 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +482664 bytes +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Tamaño Datos de Control +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +14008 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +14004 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +7012 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +12288 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +12324 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +6200 bytes +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Espacio Libre +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +17325 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +0 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +343000 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +80457 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +57922 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +407148 bytes +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Media de Espacio Libre +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +29 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +0 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +196 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +137 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +981 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +232 bytes +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Máximo de Espacio Libre +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +386 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +0 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +196 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +512 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +10656 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +512 bytes +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Mínimo de Espacio Libre +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +1 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +0 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +196 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +1 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +216 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +196 bytes +\end_inset + + + + +\end_inset + + +\end_inset + + +\begin_inset Float table +placement H +wide false +collapsed true + +\layout Caption + +Artículos con archivos con tamaño de bloque 1024 (cuando aplica) +\layout Standard + + +\size small + +\begin_inset Tabular + + + + + + + + + + + +\begin_inset Text + +\layout Standard + +Facturas +\end_inset + + +\begin_inset Text + +\layout Standard + +T1 +\end_inset + + +\begin_inset Text + +\layout Standard + +T2 +\end_inset + + +\begin_inset Text + +\layout Standard + +T3 +\end_inset + + +\begin_inset Text + +\layout Standard + +T1 +\end_inset + + +\begin_inset Text + +\layout Standard + +T2 +\end_inset + + +\begin_inset Text + +\layout Standard + +T3 +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none +Tamaño de bloque: 1024 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none +Inicial +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + +\begin_inset Text + +\layout Standard + + +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none +Luego de borrar +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Tamaño Datos +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +268707 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +................ +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +546000 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +219731 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +................ +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +482976 bytes +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\size small +Tamaño Datos de Control +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +14008 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +................ +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +7012 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +12440 bytes +\end_inset + + +\begin_inset Text + +\layout Standard + + +\size small +................ +\end_inset + + +\begin_inset Text -\series bold -} \layout Standard -Luego del primer bucle, el archivo se vera de la siguiente forma: -\begin_inset Float figure -placement H -wide false -collapsed true -\layout Caption +\size small +6204 bytes +\end_inset + + + + +\begin_inset Text -NOMBRE, ARREGLAME!!!! \layout Standard -\begin_inset Graphics - filename graphics/Compact2.png - width 100text% - +\size small +Espacio Libre \end_inset + + +\begin_inset Text +\layout Standard -\end_inset +\size small +10157 bytes +\end_inset + + +\begin_inset Text \layout Standard -Notemos que al final de la porción de datos de los bytes movidos (donde - quedo apuntando -\series bold -Destination -\series default -), hay basura que será pisada por el próximo movimiento. -\layout Standard -En el próximo loop, el bucle levantará un nuevo gap, y utilizando el gap - anterior (En esta caso el Gap anterior será -\series bold -Gap1 -\series default -) como referencia, realizará los mismos cálculos, desde donde transferir - y cuantos bytes mover. - (El destino es solo establecido inicialmente por código, y para el resto - del algoritmo es el lugar donde quedo el puntero destination luego de la - última escritura). +\size small +................ +\end_inset + + +\begin_inset Text + \layout Standard -Una vez que se salga del bucle while, se realizará un último movimiento - preprogramado, donde la fuente ( -\series bold -Source -\series default -) será el final del ultimo gap, y la cantidad de bytes a mover será lo que - se encuentre luego del mismo hasta el fin de archivo. -\layout LyX-Code -Source = StartLastGap + SizeLastGap = EndLastGap -\layout LyX-Code +\size small +45016 bytes +\end_inset + + +\begin_inset Text -Mustmove_bytes = Datsize - Source \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 Chapter +\size small +60701 bytes +\end_inset + + +\begin_inset Text + +\layout Standard -\begin_inset LatexCommand \label{cha:tipo3} +\size small +................ \end_inset + + +\begin_inset Text -Archivo con bloques parametrizados y registros de longitud constante \layout Standard -Las distintas organizaciones de archivos buscan aprovechar al máximo el - espacio del archivo. -\layout Standard -En este caso veremos que sucede luego de agregar y borrar una gran cantidad - de registros del archivo, lo que provoca como consecuencia directa la fragmenta -ción del archivo, es decir, quedan huecos entre un registro y otro, lo que - produce un desperdicio de espacio. -\layout Section +\size small +108848 bytes +\end_inset + + + + +\begin_inset Text -Organización Física \layout Standard -Esta organización guarda los registros pertenecientes al archivo en bloques - de tamaño parametrizado, de modo que intentará guardar la mayor cantidad - de registros que quepan en un bloque. - + +\size small +Media de Espacio Libre +\end_inset + + +\begin_inset Text + \layout Standard -Así como los graba, también tendrá la posibilidad de leer registros y borrarlos - del archivo. -\layout Subsection -Comportamiento Particular de los Archivos Auxiliares -\layout Subsubsection +\size small +35 bytes +\end_inset + + +\begin_inset Text -Archivo de Bloques y Registros (.idx) -\layout Comment +\layout Standard -buscar algun caso extraordinario. -\layout Subsubsection -Archivo de Bloques y Espacio Libre (.fsc) -\layout Subsubsection +\size small +................ +\end_inset + + +\begin_inset Text -Archivo de Id`s Borrados (.did) \layout Standard -El comportamiento de este archivo, es común para todas las organizaciones - y se ha explicado en 3.3.2. -\layout Section -Funciones Principales -\layout Subsection +\size small +77 bytes +\end_inset + + +\begin_inset Text -EMUFS Tipo 3 \layout Standard -Dento de -\emph on -tipo3.h -\emph default - y -\emph on -tipo3.c -\emph default - se encuentran las cabeceras y la implementación de las funciones principales - respectivamente, las cuales dan funcionalidad a esta organización. + +\size small +212 bytes +\end_inset + + +\begin_inset Text + \layout Standard -A continuación se comentará la descripción de algunas acciones importantes. -\layout Subsubsection -Leer Registro +\size small +................ +\end_inset + + +\begin_inset Text + \layout Standard -La lectura de un registro se realiza con la ayuda del archivo . -\emph on -idx -\emph default - el cual contiene la información de la posición del registro dentro del - archivo de datos. - Una vez leida esta información, se recupera el bloque (en su totalidad) - del archivo y se busca secuencialmente el registro con el -\emph on -ID -\emph default - especificado. + +\size small +186 bytes +\end_inset + + + + +\begin_inset Text + \layout Standard -Ver: -\family typewriter -emufs_tipo3_leer_registro() -\layout Subsubsection -Grabar Registro +\size small +Máximo de Espacio Libre +\end_inset + + +\begin_inset Text + \layout Standard -Graba un registro en un bloque donde haya espacio suficiente, y si no crea - un nuevo bloque y lo agrega al final del archivo. + +\size small +922 bytes +\end_inset + + +\begin_inset Text + \layout Standard -Luego de grabar un registro, actualiza los archivos de índice .idx y .fsc - para mantener la coherencia. + +\size small +................ +\end_inset + + +\begin_inset Text + \layout Standard -Ver: -\family typewriter -emufs_tipo3_grabar_registro() -\layout Subsubsection -Borrar Registro +\size small +708 bytes +\end_inset + + +\begin_inset Text + \layout Standard -Borra un registro del archivo de datos, para esto levanta el bloque al que - pertenece el archivo y ajusta los demás registros justificandolos hacia - la izquierda. + +\size small +1024 bytes +\end_inset + + +\begin_inset Text + \layout Standard -Cabe destacar que para dar de baja un registro no hace falta borrarlo del - archivo de datos, solo es necesario borrar las entradas en los archivos - de índice, pero cuando se realiza el ajuste el algoritmo toma porciones - del bloque del tamaño de un registro mas su encabezado - comenzando desde - el siguiente al que fue borrado - y copia (sobreescribe) sobre el anterior. - De esta manera, la información correspondiente al registro borrado no estará - presente en el archivo de datos. - Esto es una consecuencia del ajuste al borrar un registro, pudiendo no - ser así, si no se realizara el mismo. -\layout Subsubsection -Leer Estadísticas +\size small +................ +\end_inset + + +\begin_inset Text + \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. + +\size small +1024 bytes +\end_inset + + + + +\begin_inset Text + \layout Standard -Esta información es el resultado de ciertos cálculos realizados tanto en - el archivo de datos como en los archivos índice. + +\size small +Mínimo de Espacio Libre +\end_inset + + +\begin_inset Text + \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. + +\size small +5 bytes +\end_inset + + +\begin_inset Text + \layout Standard -Ver: -\family typewriter -emufs_tipo3_leer_estadisticas() -\layout Subsubsection -Compactar el Archivo +\size small +................ +\end_inset + + +\begin_inset Text + \layout Standard -Esta función intenta reorganizar el archivo de manera que el espacio libre - sea lo menor posible, recordando siempre que un registro no puede ser almacenad -o en mas de un bloque excepto que el tamaño del registro sea mayor que el - del bloque. + +\size small +76 bytes +\end_inset + + +\begin_inset Text + \layout Standard -Para realizar esto, se aprovecha la funcionalidad de -\emph on -emufs_tipo3_grabar_registro() -\emph default -ya que esta tiene la capacidad de determinar una posición mas eficiente - en el archivo para un registro. - Por esto lo que se hace es levantar uno por uno los registros y volverlos - a grabar, de ese modo todos los -\emph on -gaps -\emph default -que pudieron haberse formado por la eliminación de registros serán cubiertos - por otros. + +\size small +5 bytes +\end_inset + + +\begin_inset Text + \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 . -\emph on -fsc -\emph default -el cual disminuye su tamaño también. + +\size small +................ +\end_inset + + +\begin_inset Text + \layout Standard -Ver: -\family typewriter -void emufs_tipo3_compactar() -\layout Section -Consideraciones y Políticas de Diseño -\layout Comment +\size small +76 bytes +\end_inset + + + + +\end_inset + + +\end_inset + -Esto para mi va en organización física. \layout Standard -Se han tomado ciertas consideraciones para algunos casos particulares que - se pueden presentar durante el uso/ejecución de la aplicación. -\layout Enumerate +Primero descartaremos al tipo 3 como un buen modo de almacenar las facturas, + por el sólo hecho de que la cantidad de ítems que puede tener una factura + está limitada al tamaño de registro utilizado. + Esto sólo sería razonable en un contexto en donde la variabilidad del registro + no sea drástica como es el caso de las facturas. + De tomar valores grande de registros, se corre el riesgo de tener mucho + espacio desperdiciado en los datos, y tomando valores pequeños de registro + se limita el sistema en cuanto a cantidad de ítems a colocar en una factura + se refiere. + Se puede notar una leve baja en el espacio libre, y aumentar el tamaño + del bloque quizás más haga que este valor baje, pero se aumentaría el tiempo + de acceso a los registros. +\layout Standard -Cada registro tiene un encabezado que indica el -\emph on -id -\emph default -del mismo. -\layout Enumerate +Nuevamente tenemos una disputa entre el los tipo 1 y 2. +\layout Standard -Si el tamaño del registro es mayor que el tamaño del bloque el registro - se particionará en la cantidad de bloques que sea necesario, pero siempre - se guardará desde el comienzo de un bloque, esto quiere decir que nunca - se podrá encontrar un comienzo de registro en algún lugar de un bloque - que no sea el comienzo del mismo. -\layout Enumerate +Idealmente, si sólo tuviéramos altas el mejor tipo sería el 2 sin dudarlo, + ya que aprovecha el máximo espacio al no tener pérdidas, debido a que los + registros van uno a continuación del otro. + También tenemos la ventaja de que el acceso es directo. + Para un caso teórico donde las facturas no se dan de baja, esto sería ideal. + Hasta aquí solo hemos visto comparaciones con la carga inicial. +\layout Standard -Si el registro se divide en mas de un bloque, se le coloca el id como encabezado - igualmente, pero en el archivo . -\emph on -idx -\emph default - solo se guarda el primer bloque. - En el -\emph on -.fsc -\emph default - se actualizan todos los bloques con el espacio libre que realmente tienen. -\layout Chapter +Analizaremos ahora que pasa luego de borrar varios registros en posiciones + pseudo-aleatorias. + Primeramente se puede observar que el tamaño de datos de control es similar + (recordar que se guarda el id del registro para poder realizar tareas de + recuperación de datos en caso de que el índice se dañe). + El máximo espacio libre no nos da mucha información, ya que en el caso + del tipo 1 podríamos tener n bloques consecutivos libres y tener posiciones + para almacenar registros grandes en ambos casos (recordar que tipo1 tiene + recuperación de espacio libre para n bloques consecutivos, no siempre se + agrega al final). + De todos determinar un espacio libre para un archivo de tipo 2 es mucho + más rápido que para tipo1 si el tamaño del registro es grande, ya que el + archivo de tipo1 debe hacer una búsqueda sobre n bloques, mientras que + el tipo 2 encuentra un gap de tamaño suficiente más rápido. +\layout Standard -Conclusiones +Pero no todo es color de rosa en el mundo de archivos de tipo2. + Como se dijo anteriormente las bajas de registros requieren de un proceso + grande al actualizar el índice de espacio libre, para asegurarse de tomar + espacios libres consecutivos como un solo espacio libre, y en el caso de + que las bajas y las altas comunes, esto es una pérdida de performance del + sistema. \layout Standard -Las comparaciones, pruebas, etc... +En este caso como se trata de facturas, y suponemos que como usuarios de + sistema queremos cancelar pocas facturas (ya que cancelar una factura significa + que se cayó una venta) optamos por que el mejor tipo de archivo para almacenar + las facturas sera el tipo2. \the_end