Chapter 5, Tipo2 uploaded y terminado al menos por ahora

[z.facultad/75.06/emufs.git] / doc / informe.lyx

#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 Title

E
\begin_inset Formula $\mu$
\end_inset 

FS
\layout Author

Nicolás Dimov
\newline 
Alan Kennedy
\newline 
Leandro Lucarella
\newline 
Ricardo Markiewicz
\layout Chapter

Introducción
\layout Chapter

Estructura común
\layout Section

Tipos
\layout Subsection

EMUFS
\layout Standard


\family typewriter 
EMUFS
\family default 
\emph on 
 
\emph default 
es la estuctura principal que encapsula todas las funciones para el manejo
 de un archivo de datos.
\layout Standard

Esta estructura consta de:
\layout Enumerate


\family typewriter 
EMUFS_Tipo
\family default 
 que es un tipo enumerado que indica cual es la organización.
\layout Enumerate


\family typewriter 
EMUFS_BLOCK_SIZE
\family default 
 indica el tamaño del bloque para los tipos 1 y 3.
\layout Enumerate


\family typewriter 
EMUFS_REG_SIZE
\family default 
 indica el tamaño del registro, para el tipo 3 que posee tamaño constante.
\layout Enumerate


\family typewriter 
void **leer_bloque() 
\family default 
puntero a la función para leer un bloque.
\layout Enumerate


\family typewriter 
void *leer_bloque_raw()
\family default 
 puntero a la función para leer un bloque, el anterior y el siguiente.
\layout Enumerate


\family typewriter 
void **leer_registro()
\family default 
 puntero a la función para leer un registro.
\layout Enumerate


\family typewriter 
void **leer_registro_raw()
\family default 
 puntero a la función para leer un registro con su encabezado.
\layout Enumerate


\family typewriter 
EMUFS_REG_ID *grabar_registro()
\family default 
 puntero a la función para grabar un registro.
\layout Enumerate


\family typewriter 
EMUFS_REG_ID *modificar_registro() 
\family default 
puntero a la función para modificar un registro.
\layout Enumerate


\family typewriter 
int *borrar_registro()
\family default 
 puntero a la función para borrar un registro.
\layout Enumerate


\family typewriter 
EMUFS_Estadisticas *leer_estadisticas()
\family default 
 puntero a la función para cargar una estructura con las estadísticas.
\layout Enumerate


\family typewriter 
void *compactar()
\family default 
 puntero a la función para compactar un archivo.
\layout Enumerate


\family typewriter 
char *nombre
\family default 
 almacena el nombre del archivo sin extensión.
\layout Standard

Esta estructura define los valores de sus punteros según el tipo de organización
 que se desee manejar.
\layout Standard

Por ejemplo si se desea crear un archivo de nombre 
\begin_inset Quotes eld
\end_inset 

facturas
\begin_inset Quotes erd
\end_inset 

 organizado de la forma 3, se invoca a la función 
\family typewriter 
EMUFS *emufs_crear(const char *filename, EMUFS_Tipo tipo,EMUFS_BLOCK_SIZE
 tam_bloque, EMUFS_REG_SIZE tam_reg), 
\family default 
donde
\family typewriter 
 filename 
\family default 
es el nombre que tendrán los archivos de datos e índice, 
\family typewriter 
tipo
\family default 
 es el tipo de organización - bloques parametrizados y registros constantes
 en este caso-, 
\family typewriter 
tam_bloque
\family default 
 es el tamaño del bloque, y 
\family typewriter 
tam_reg
\family default 
 es el tamaño del registro.
\layout Standard

Para las diferentes organizaciones puede ser que alguno de estos 2 últimos
 valores no tengan sentido almacenarlas y tomaran un valor por defecto igual
 a cero.
\layout Standard

Según el tipo de organización, se inicializan los punteros a las funciones.
 Para el ejemplo 
\family typewriter 
leer_bloque
\family default 
 se igualará a 
\family typewriter 
emufs_tipo3_leer_bloque()
\family default 
, y lo mismo sucede con los demás.
\layout Subsection

EMUFS_Tipo
\layout Subsection

EMUFS_Estadisticas
\layout Subsection

EMUFS_BLOCK_ID
\layout Standard

etc
\layout Section


\begin_inset LatexCommand \label{sec:cabecera_gral}

\end_inset 

Organización física general de un archivo E
\begin_inset Formula $\mu$
\end_inset 

FS
\layout Standard

Todo archivo E
\begin_inset Formula $\mu$
\end_inset 

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}

\end_inset 

, 
\begin_inset LatexCommand \pageref{cha:tipo2}

\end_inset 

 y 
\begin_inset LatexCommand \pageref{cha:tipo3}

\end_inset 

), archivo de índice (ver página 
\begin_inset LatexCommand \pageref{sec:idx}

\end_inset 

), 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 

).
\layout Standard

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

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 Chapter

Archivos Auxiliares
\layout Comment

Por que los 3 tipos usan lo mismo.
 Ventajas y desventajas.
\layout Section


\begin_inset LatexCommand \label{sec:idx}

\end_inset 

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

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 
\emph on 
id
\emph default 
 no pertenece a ningún bloque, hemos adoptado poner -1 en el campo location
 de la estructura 
\family typewriter 
EMUFS_IDX
\family default 
.
\layout Standard

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

El tipo 
\family typewriter 
EMUFS_IDX
\family default 
 define la estuctura de los registros de este archivo.
\layout Standard

Esta estructura está compuesta por:
\layout Itemize


\family typewriter 
EMUFS_REG_ID
\family default 
 reg_id indica el 
\emph on 
id
\emph default 
 del registro
\layout Itemize


\family typewriter 
EMUFS_BLOCK_ID
\family default 
 location número de bloque donde se encuentra el registro.
\layout Standard


\family typewriter 
EMUFS_REG_ID
\family default 
 y 
\family typewriter 
EMUFS_BLOCK_ID
\family default 
 son 
\emph on 
unsigned long.
\layout Comment

ponerlo mas lindo...
\layout Subsection

Comportamiento (funciones generales)
\layout Section


\begin_inset LatexCommand \label{sec:fsc}

\end_inset 

Archivo de control de espacio libre
\layout Standard

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.
\layout Standard

De esta manera al querer guardar un registro este archivo informará donde
 cabe el mismo, previa invocación al la función 
\family typewriter 
EMUFS_BLOCK_ID emufs_fsc_buscar_lugar(EMUFS *, EMUFS_FREE, EMUFS_FREE*)
\family default 
 perteneciente a 
\emph on 
fsc.h,
\emph default 
 la cual devuelve el número de bloque donde entra el registro o -1 si no
 hay un bloque con lugar suficiente, y toma como parámetros una estructura
 
\family typewriter 
EMUFS
\family default 
, y dos 
\family typewriter 
EMUFS_FREE
\family default 
 donde el segndo parámetro es el tamaño buscado, y el tercero devuelve el
 tamaño disponible.
\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

Organización Física
\layout Standard

La estuctura que define este archivo es la siguiente:
\layout Standard


\family typewriter 
EMUFS_FSC
\family default 
 que contiene:
\layout Itemize


\family typewriter 
EMUFS_BLOCK_ID
\family default 
 indica el número de bloque
\layout Itemize


\family typewriter 
EMUFS_FREE
\family default 
 freespace indica la cantidad de espacio libre que queda en el bloque.
\layout Standard


\family typewriter 
EMUFS_FSC
\family default 
 y 
\family typewriter 
EMUFS_FREE
\family default 
 son 
\emph on 
unsiged long int
\layout Subsection

Comportamiento
\layout Section


\begin_inset LatexCommand \label{sec:did}

\end_inset 

Archivo de índices recuperables
\layout Standard

Este archivo funciona como una pila de i
\emph on 
d`s
\emph default 
 borrados, es decir, cuando se borra un registro el 
\emph on 
id
\emph default 
 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.
\layout Subsection

Estructura Física
\layout Standard

Este archivo tiene registros de un solo campo, 
\family typewriter 
EMUFS_REG_ID
\family default 
 el cual simboliza al id almacenado.
\layout Subsection

Comportamiento
\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
\layout Itemize


\series bold 
Agregar: 
\series default 
agrega un 
\emph on 
id 
\emph default 
al archivo, el cual será el primero recuperado.
 
\family typewriter 
Ver: emufs_did_agregar()
\layout Itemize


\series bold 
Obtener el último:
\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.
 
\family typewriter 
Ver: 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 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

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 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

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 
.
\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 Standard

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 

), 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 Section

Comportamiento (funciones de la interfáz)
\layout Section

Detalles de implementación (funciones internas, ver si lo ponemos o no)
\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, 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 
).
\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 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: 
\begin_inset Float figure
placement H
wide false
collapsed true

\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.dsds
\layout Subsection

Comportamiento Particular de los Archivos Auxiliares
\layout Standard

Como fue explicado al inicio de la documentación, la implementación de cualquier
a de las tres organizaciones físicas de archivos presenta la necesidad de
 poseer tres archivos auxiliares que actuarán como índice de direcciones
 de registro (.
\series bold 
idx
\series default 
), administrador de espacio libre (
\series bold 
.fsc
\series default 
) y administrador de Id's liberados (
\series bold 
.did
\series default 
) respectivamente.
\layout Standard

No obstante, cada tipo de organización presentara sus particularidades respecto
 de estos tres archivos, las cuales describiremos a continuación en caso
 de haberla.
\layout Subsubsection

Archivo índice o de posiciones relativas (.idx)
\layout Standard

El archivo indice (
\series bold 
.idx
\series default 
), permite la localizacin de los registros en el .DAT de forma directa, mediante
 la obtención de su offset o posición relativa respecto del inicio del 
\series bold 
.dat
\series default 
 en donde se encuentra un registro dado, indicado por su ID.
\layout Standard

Así pues, si tomamos el ejemplo descripto al inicio de este capítudlo, tendremos
 las siguientes entradas en el archivo indice 
\series bold 
.idx
\series default 
 :
\newline 

\layout Standard


\begin_inset  Tabular
<lyxtabular version="3" rows="3" columns="3">
<features>
<column alignment="center" valignment="top" leftline="true" width="0">
<column alignment="center" valignment="top" leftline="true" width="0">
<column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
<row topline="true" bottomline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\emph on 
ID_REGISTRO
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\emph on 
OFFSET
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

\end_inset 
</cell>
</row>
<row topline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\series bold 
0
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\series bold 
4
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

El primer registro (reg0) comienza en el byte 4
\end_inset 
</cell>
</row>
<row topline="true" bottomline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard

1
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\series bold 
60
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

El segundo registro (reg1) comienza en el byte 60
\end_inset 
</cell>
</row>
</lyxtabular>

\end_inset 


\layout Standard


\series bold 
\emph on 
\SpecialChar ~

\newline 
Observación:
\series default 
\emph default 
 LOCATION indica donde comienza el header del registro buscado, y por consiguien
te luego del header tendremos el registro en sí (los datos).
\layout Subsubsection

Achivo de Gaps / Espacios Libres (.fsc)
\layout Standard

El archivo de espacios libres o gaps (.fsc), tiene como función la administracion
 del espacio libre o gaps (agujeros), generados por previas eliminaciones
 de registros en el archivo de datos.
 El mismo, nos indicará donde hay lugar para insertar un nuevo registro
 (se podrán insertar en algún gap acorde, o bien al final del archivo).
 Este archivo será utilizado tambien para el proceso de compactación de
 un archivo, explicado luego.
\layout Standard

Así pues, si tomamos el ejemplo descripto al inicio del documento, tendremos
 las siguientes entradas en el archivo índice 
\series bold 
.fsc
\series default 
 : 
\newline 

\newline 

\begin_inset  Tabular
<lyxtabular version="3" rows="2" columns="3">
<features>
<column alignment="center" valignment="top" leftline="true" width="0">
<column alignment="center" valignment="top" leftline="true" width="0">
<column alignment="center" valignment="top" leftline="true" rightline="true" width="0">
<row topline="true" bottomline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\emph on 
OFFSET
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\emph on 
FREESPACE
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

\end_inset 
</cell>
</row>
<row topline="true" bottomline="true">
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\series bold 
42
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none">
\begin_inset Text

\layout Standard


\series bold 
18
\end_inset 
</cell>
<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
\begin_inset Text

\layout Standard

18 bytes libres a partir del byte 42 del .dat
\end_inset 
</cell>
</row>
</lyxtabular>

\end_inset 


\layout Standard


\series bold 
\emph on 
\SpecialChar ~

\newline 
Nota:
\series default 
\emph default 
 Por requerimiento del algoritmo de compactación, los gaps se graban en
 forma ordenada en el (.fsc).
 (El orden se corresponde con lo que hay en el .dat)
\layout Subsubsection*

GAP Merging
\layout Standard

Si bien la utilización concreta de los GAPS será explicada posteriormente
 en la ALTA y BAJA de registros, debemos remarcar la funcionalidad de MERGING
 que posee nuestro sistema FSC.
\layout Standard

Ante la eliminación de un registro del archivo de datos, se generara por
 consiguiente un gap o espacio libre en alguna posición del archivo.
 Ese gap deberá ser registrado en el archivo de gaps (.fsc).
 Ahora bien, nuestro sistema de gaps, contemplará como es debido, la posibilidad
 de que se haya eliminado un registro que posee un GAP por delante, un GAP
 por detrás, o bien un GAP por delante y por detrás del mismo.
\layout Standard

Nuestro sistema actuará en consecuencia, realizando un merge de los espacios
 libres, y unificándolos en una UNICA entrada en el archivo .fsc, que contendrá
 como dato de freespace, la suma correspondiente de los espacios libres
 antes mencionados.
\layout Subsubsection

Archivo de ID's liberados (.did)
\layout Standard

El archivo de ID's liberados no presenta ningún aspecto particular en este
 tipo de organización.
 Remitirse al capítulo correspondiente a los archivos auxiliares para consultar
 su estructura y funcionamiento.
\layout Section

Comportamiento (funciones de la interfaz)
\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.
\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á 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).
\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 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 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

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 
).
\layout Standard

Comenzemos con el siguiente cuadro situacional: 
\begin_inset Float figure
placement H
wide false
collapsed true

\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 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 
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 
}
\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

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 
void emufs_tipo2_compactar()
\layout Section

Consideraciones y Políticas de Diseño
\layout Standard

Se han tomado ciertas consideraciones para algunos casos particulares que
 se pueden presentar durante el uso/ejecución de la aplicación, así como
 tambien politicas respecto del diseño e implementación del sistema:
\layout Itemize

En la organización física tipo 2 para los registros que se graban en disco
 hemos decidido utilizar como encabezado de cada uno de ellos, los datos
 [ID_REG][REG_SIZE], los cuales fueron detallados previamente.
 Si bien se podría haber descartado el grabado del ID del registro en el
 archivo de datos y puede parecer redundante, dado que poseemos el archivo
 índice con el offset directo, el mismo se lo graba por distintos motivos:
\newline 

\newline 
A) En caso de la corrupción del archivo índice (.idx), podremos gracias a
 que poseemos en el archivo de datos, el ID de cada registro, recrear dicho
 índice, ayudándonos del archivo de espacios libres (
\series bold 
.fsc
\series default 
), para poder saltear los espacios libres y e ir recorriendo secuencialmente
 los registros, reconstruyendo así el índice en cuestión.
 (esta función de reconstrucción no pudo ser implementada para esta entrega,
 pero es una posibilidad real).
\newline 

\newline 
B) Luego de un proceso de recompactación, los espacios libres que pudieron
 haber existido en el archivo de datos (
\series bold 
.dat
\series default 
), son eliminados y los registros han cambiado de posición.
 Por ello, recorriendo secuencialmente por única vez el archivo de datos,
 se procede a la actualización / reconstrucción del índice de direcciones
 u offsets (.
\series bold 
idx
\series default 
)
\layout Itemize

Si se desea insertar un registro y no se puede hayar un gap o espacio libre
 donde quepa, se los inserta al final del archivo.
\layout Itemize

Ante una operación de baja de un registro, el mismo no es físicamente borrado
 del archivo de datos (
\series bold 
.dat
\series default 
), simplemente los bytes que ocupa son llenados con hexa (00).
 Paralelamente, se procede a actualiza el archivo índice, insertando como
 valor de OFFSET para el registro eliminado, el valor ¨-1¨, indicando así
 la inexistencia del registro para el futuro, y por otro lado se genera
 la entrada de espacio libre en el archivo de gaps (
\series bold 
.fsc
\series default 
).
\layout Itemize

La reutilización de ID's liberados por previas operaciones de baja de registros,
 se ve implementada por el archivo de ID liberados (.did), y su comportamiento
 es el de una pila por lo que el último ID liberado, sera el próximo a ser
 reutilizado (LIFO).
\layout Itemize

Como fue explicado en la implementación del archivo índice, existe una correspon
dencia 1 a 1 entre los registros allí presentes (en el .idx) y los ID's de
 los registros, por lo cual el registro N-ésimo del archivo índice, será
 el correspondiente al registro de datos cuyo ID es igual a N.
\layout Itemize

El proceso de compactación de archivos, realiza los movimientos de información
 requeridos para dicho propósito de a chunks de 25 bytes por vez.
 Este valor es fijo, pero se lo podría hacer parametrizable mediante la
 GUI en próximas entregas.
\layout Chapter


\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 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 Subsection

Comportamiento Particular de los Archivos Auxiliares
\layout Subsubsection

Archivo de Bloques y Registros (.idx)
\layout Comment

buscar algun caso extraordinario.
\layout Subsubsection

Archivo de Bloques y Espacio Libre (.fsc)
\layout Subsubsection

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

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.
\layout Standard

A continuación se comentará la descripción de algunas acciones importantes.
\layout Subsubsection

Leer Registro
\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.
\layout Standard

Ver: 
\family typewriter 
emufs_tipo3_leer_registro()
\layout Subsubsection

Grabar Registro
\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

Ver: 
\family typewriter 
emufs_tipo3_grabar_registro()
\layout Subsubsection

Borrar Registro
\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.
\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
\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 Subsubsection

Compactar el Archivo
\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 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.
\layout Standard

Ver: 
\family typewriter 
void emufs_tipo3_compactar()
\layout Section

Consideraciones y Políticas de Diseño
\layout Comment

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

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

Conclusiones
\layout Standard

Las comparaciones, pruebas, etc...
\the_end