From: Alan Kennedy <kennedya@3dgames.com.ar>
Date: Mon, 19 Apr 2004 00:26:47 +0000 (+0000)
Subject: Chapter 5 al 80%, revisen sino no explique demasiado profundo las funciones o mejor... 
X-Git-Tag: svn_import_r684~333
X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/commitdiff_plain/13ca793fc609013394a7adb645350f68a09fb5ca?ds=sidebyside

Chapter 5 al 80%, revisen sino no explique demasiado profundo las funciones o mejor dicho el API
---

diff --git a/doc/informeChapter5.lyx b/doc/informeChapter5.lyx
new file mode 100644
index 0000000..06e07c4
--- /dev/null
+++ b/doc/informeChapter5.lyx
@@ -0,0 +1,628 @@
+#LyX 1.3 created this file. For more info see http://www.lyx.org/
+\lyxformat 221
+\textclass book
+\language spanish
+\inputencoding auto
+\fontscheme palatino
+\graphics default
+\paperfontsize default
+\spacing single 
+\papersize a4paper
+\paperpackage widemarginsa4
+\use_geometry 0
+\use_amsmath 0
+\use_natbib 0
+\use_numerical_citations 0
+\paperorientation portrait
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\defskip medskip
+\quotes_language english
+\quotes_times 2
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+
+\layout Chapter
+
+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 variablesin 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
+
+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 
+).
+\newline 
+
+\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.
+\newline 
+
+\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 
+\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:
+\newline 
+
+\newline 
+
+\begin_inset Graphics
+	filename graphics/Example1.png
+	width 100text%
+
+\end_inset 
+
+
+\newline 
+
+\newline 
+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.dsds
+\layout Section
+
+Comportamiento (funciones de la interfáz)
+\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 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.
+\newline 
+
+\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 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 
+).
+ 
+\newline 
+
+\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 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 
+).
+\newline 
+
+\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á 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).
+\newline 
+
+\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 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 desarollado 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 Subsection
+
+Obtención de estadísticas
+\layout Subsection
+
+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
+).
+\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 
+)
+\newline 
+
+\layout Standard
+
+Comenzemos con el siguiente cuadro situacional:
+\newline 
+
+\newline 
+
+\begin_inset Graphics
+	filename graphics/Compact1.png
+	width 100text%
+	keepAspectRatio
+
+\end_inset 
+
+
+\newline 
+
+\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:
+\newline 
+
+\layout Standard
+
+
+\series bold 
+StartGap0
+\series default 
+ + 
+\series bold 
+SizeGap0
+\series default 
+ = 
+\series bold 
+EndGap0
+\series default 
+ = 
+\series bold 
+Source
+\newline 
+
+\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:
+\newline 
+
+\layout Standard
+
+
+\series bold 
+Mientras haya Gaps
+\series default 
+ {
+\layout Enumerate
+
+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
+
+
+\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 
+ 
+\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 leido (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 
+}
+\newline 
+
+\layout Standard
+
+Luego del primer bucle, el archivo se vera de la siguiente forma:
+\newline 
+
+\newline 
+
+\begin_inset Graphics
+	filename graphics/Compact2.png
+	width 100text%
+
+\end_inset 
+
+
+\newline 
+
+\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.
+\newline 
+
+\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.
+\newline 
+
+\layout Standard
+
+
+\series bold 
+Source = StartLastGap + SizeLastGap = EndLastGap
+\layout Standard
+
+
+\series bold 
+Mustmove_bytes = Datsize - Source
+\series default 
+
+\newline 
+
+\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 Section
+
+Detalles de implementación (funciones internas, ver si lo ponemos o no)
+\the_end