X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/088c62b17f5b04891f9b5fd4a682670b88143b99..aa4f458f1938cfb39be5523a24a8349dcb050108:/doc/informe.lyx
diff --git a/doc/informe.lyx b/doc/informe.lyx
index 5f84015..8f32d42 100644
--- a/doc/informe.lyx
+++ b/doc/informe.lyx
@@ -40,6 +40,14 @@ Alan Kennedy
Leandro Lucarella
\newline
Ricardo Markiewicz
+\layout Standard
+
+
+\begin_inset LatexCommand \tableofcontents{}
+
+\end_inset
+
+
\layout Chapter
Introducción
@@ -51,6 +59,11 @@ Estructura com
Tipos
\layout Subsection
+
+\begin_inset LatexCommand \label{sub:EMUFS}
+
+\end_inset
+
EMUFS
\layout Standard
@@ -79,19 +92,36 @@ EMUFS_Tipo
\family typewriter
EMUFS_BLOCK_SIZE
\family default
- indica el tamaño del bloque para los tipos 1 y 3.
+ indica el tamaño del bloque para los tipos de archivo con bloques (ver
+ capítulos
+\begin_inset LatexCommand \ref{cha:tipo1}
+
+\end_inset
+
+ y
+\begin_inset LatexCommand \ref{cha:tipo3}
+
+\end_inset
+
+).
\layout Enumerate
\family typewriter
EMUFS_REG_SIZE
\family default
- indica el tamaño del registro, para el tipo 3 que posee tamaño constante.
+ indica el tamaño del registro, para el tipo de archivo con tamaño de registro
+ parametrizado (ver capítulo
+\begin_inset LatexCommand \ref{cha:tipo3}
+
+\end_inset
+
+).
\layout Enumerate
\family typewriter
-void **leer_bloque()
+void* *leer_bloque()
\family default
puntero a la función para leer un bloque.
\layout Enumerate
@@ -105,14 +135,14 @@ void *leer_bloque_raw()
\family typewriter
-void **leer_registro()
+void* *leer_registro()
\family default
puntero a la función para leer un registro.
\layout Enumerate
\family typewriter
-void **leer_registro_raw()
+void* *leer_registro_raw()
\family default
puntero a la función para leer un registro con su encabezado.
\layout Enumerate
@@ -154,7 +184,7 @@ void *compactar()
\family typewriter
-char *nombre
+char* nombre
\family default
almacena el nombre del archivo sin extensión.
\layout Standard
@@ -322,10 +352,43 @@ archivo
\layout Chapter
Archivos Auxiliares
-\layout Comment
+\layout Standard
+
+Acompañando al archivo de datos (
+\series bold
+.dat
+\series default
+) el cual es responsable de la contención de los registros, tendremos tres
+ archivos auxiliares (
+\series bold
+.idx
+\series default
+,
+\series bold
+.fsc
+\series default
+ y
+\series bold
+.did
+\series default
+) 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
+
+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
-Por que los 3 tipos usan lo mismo.
- Ventajas y desventajas.
+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
@@ -333,405 +396,1342 @@ Por que los 3 tipos usan lo mismo.
\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.
+Archivo índice
\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
+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
-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.
+id_reg.
\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
-.
+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 mísmo.
\layout Standard
Es necesario que este archivo esté ordenado por
\emph on
-id
+id_reg
\emph default
- de registro, ya que esto permitirá el acceso directo para la búsqueda de
- un registro en el archivo de datos.
+, 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
Organización física
\layout Standard
-El tipo
+Los registros de este archivo se encuentran representados a nivel codigo
+ por el siguiente tipo de dato interno (
\family typewriter
EMUFS_IDX
\family default
- define la estuctura de los registros de este archivo.
+):
+\layout LyX-Code
+
+typedef unsigned long EMUFS_REG_ID;
+\layout LyX-Code
+
+typedef unsigned long EMUFS_OFFSET;
+\layout LyX-Code
+
+typedef struct emufs_idx_t {
+\layout LyX-Code
+
+ EMUFS_REG_ID id_reg;
+\layout LyX-Code
+
+ EMUFS_OFFSET location;
+\layout LyX-Code
+
+} EMUFS_IDX;
\layout Standard
-Esta estructura está compuesta por:
-\layout Itemize
+\begin_inset Float table
+placement H
+wide false
+collapsed true
-\family typewriter
-EMUFS_REG_ID
-\family default
- reg_id indica el
-\emph on
-id
-\emph default
- del registro
-\layout Itemize
+\layout Caption
+Ejemplo de registro en archivo índice (.idx), para un archivo de organizacion
+ Tipo 1 y 3
+\layout Standard
+
+
+\begin_inset Tabular
+
+
+
+
+
+
+|
+\begin_inset Text
-\family typewriter
-EMUFS_BLOCK_ID
-\family default
- location número de bloque donde se encuentra el registro.
\layout Standard
+id_reg
+\end_inset
+ |
+
+\begin_inset Text
-\family typewriter
-EMUFS_REG_ID
-\family default
- y
-\family typewriter
-EMUFS_BLOCK_ID
-\family default
- son
-\emph on
-unsigned long.
-\layout Comment
+\layout Standard
-ponerlo mas lindo...
-\layout Subsection
+nro_bloque
+\end_inset
+ |
+
+\begin_inset Text
-Comportamiento (funciones generales)
-\layout Section
+\layout Standard
+
+\end_inset
+ |
+
+
+|
+\begin_inset Text
+\layout Standard
-\begin_inset LatexCommand \label{sec:fsc}
+5
+\end_inset
+ |
+
+\begin_inset Text
+
+\layout Standard
+54
\end_inset
+ |
+
+\begin_inset Text
-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.
+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
+
+\layout Caption
+
+Ejemplo de registro en archivo índice (.idx), para un archivo de organizacion
+ Tipo 2
\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.
+
+\begin_inset Tabular
+
+
+
+
+
+
+|
+\begin_inset Text
+
\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.
+id_reg
+\end_inset
+ |
+
+\begin_inset Text
+
\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
+nro_bloque
+\end_inset
+ |
+
+\begin_inset Text
+
+\layout Standard
+
+\end_inset
+ |
+
+
+|
+\begin_inset Text
-Organización Física
\layout Standard
-La estuctura que define este archivo es la siguiente:
+5
+\end_inset
+ |
+
+\begin_inset Text
+
\layout Standard
+54
+\end_inset
+ |
+
+\begin_inset Text
+
+\layout Standard
-\family typewriter
-EMUFS_FSC
-\family default
- que contiene:
-\layout Itemize
+Indica que el registro de id_reg = 5, se encuentra en el bloque 54
+\end_inset
+ |
+
+
+
+\end_inset
+
+
+\end_inset
+
+
+\layout Standard
+
+
+\series bold
+\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
+\emph on
+idx.h
+\series default
+\emph default
+ y
+\series bold
+\emph on
+idx.c
+\series default
+\emph default
+ respectivamente:
+\layout List
+\labelwidthstring 00.00.0000
+\series bold
+\emph on
+Búsqueda:
+\series default
+\emph default
+ Los registros del archivo indice (
+\series bold
+.idx
+\series default
+), poseen una correspondencia 1 a 1, con los Id's de los registros en el
+ archivo de datos (
+\series bold
+.dat
+\series default
+).
+ 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
-EMUFS_BLOCK_ID
+id_reg
\family default
- indica el número de bloque
-\layout Itemize
+ es N, dentro del archivo de datos (
+\series bold
+.dat
+\series default
+).
+\newline
+
+\series bold
+NOTA:
+\series default
+ Cabe aclarar que por si bien el indice 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()
+\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 cuestion,
+ 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, estableciendolo
+ en el valor -1 UL, 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 nó.
+
+\newline
+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 recompactació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 apartir 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 codigo
+ por el siguiente tipo de dato interno (
+\family typewriter
+EMUFS_FSC
+\family default
+):
+\layout LyX-Code
+
+typedef struct emufs_fsc_t {
+\layout LyX-Code
+
+ unsigned long int marker;
+\layout LyX-Code
+
+ unsigned long int freespace;
+\layout LyX-Code
+
+} EMUFS_FSC;
+\layout Standard
+
+
+\series bold
+\emph on
+
+\begin_inset Float table
+placement H
+wide false
+collapsed true
+
+\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 true
+
+\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
+\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
+\emph on
+fsc.h
+\series default
+\emph default
+ y
+\series bold
+\emph on
+fsc.c
+\series default
+\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.
+ En el caso de organizacion 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()
+\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 modificandoló.
+\newline
+
+\newline
+En el caso de organizaciónes con bloques, se actualizará el valor del espacio
+ libre
+\family typewriter
+freespace
+\family default
+ en el bloque (ya sea incrementandoló o decrementandoló) 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 fisica, 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
+: Unicamente 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
+
+Baja 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 eliminandolo.
+\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 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
+.
+ 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 mínimiza 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 menejar 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 framento 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 4 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 | tam | datos||| id | tam | datos||| id | tam |dato|..|
+\backslash
+
+\backslash
+ |
+\layout LyX-Code
+||----+-----+------+||----+-----+------+||----+-----+----+..| // |
+\layout LyX-Code
-\family typewriter
-EMUFS_FREE
-\family default
- freespace indica la cantidad de espacio libre que queda en el bloque.
-\layout Standard
+|| 0 | 10 | 1234 ||| 0 | 6 | 5678 ||| 0 | 2 | 90 |..|
+\backslash
+\backslash
+ |
+\layout LyX-Code
-\family typewriter
-EMUFS_FSC
-\family default
- y
-\family typewriter
-EMUFS_FREE
-\family default
- son
-\emph on
-unsiged long int
-\layout Subsection
+|+----+-----+------+|+----+-----+------+|+----+-----+----+..| // |
+\layout LyX-Code
-Comportamiento
++-------------------+-------------------+-------------------+-
+\backslash
+
+\backslash
+-+
\layout Section
+Funciones principales
+\layout Standard
-\begin_inset LatexCommand \label{sec:did}
+Las funciones principales son las necesarias para completar la estructura
+ EMUFS (ver página
+\begin_inset LatexCommand \pageref{sub:EMUFS}
\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
+Lectura de registros
\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
+Para leer un registro se hace uso del archivo de índice (ver página
+\begin_inset LatexCommand \pageref{sec:idx}
-Comportamiento
+\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
-Las declaraciones e implementación se pueden encontrar en
-\emph on
-did.h
-\emph default
- y
+Si se tratara de un registro
\emph on
-did.c
+multibloque
\emph default
- respectivamente
-\layout Itemize
+ (ver sección
+\begin_inset LatexCommand \ref{sub:tipo1_reg_multi}
+\end_inset
-\series bold
-Agregar:
-\series default
-agrega un
+), 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
-id
+fragmentos
\emph default
-al archivo, el cual será el primero recuperado.
-
-\family typewriter
-Ver: emufs_did_agregar()
-\layout Itemize
-
+ hasta completarlo.
+\layout Standard
-\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.
-
+Ver:
\family typewriter
-Ver: emufs_did_get_last()
-\layout Chapter
-
-
-\begin_inset LatexCommand \label{cha:tipo1}
-
-\end_inset
+emufs_tipo1_leer_registro()
+\layout Subsection
-Archivo con bloques parametrizados y registros de longitud variable
+Altas de registros
\layout Standard
-Este tipo de archivo tiene varias complicaciones, al tratarse de un punto
- intermedio entre el
-\begin_inset LatexCommand \ref{cha:tipo2}
+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 el
-\begin_inset LatexCommand \ref{cha:tipo3}
+) 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
- (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
+) 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}
-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
+\end_inset
-Organización física
+) 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
-El archivo está compuesto por la
-\emph on
-cabecera general
-\emph default
- (ver página
-\begin_inset LatexCommand \pageref{sec:cabecera_gral}
+Si el registro ocupara más de un bloque (ver sección
+\begin_inset LatexCommand \ref{sub:tipo1_reg_multi}
\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
+), se buscan N bloques consecutivos (todos los que necesite el registro)
+ absolutamente libres
+\begin_inset Foot
+collapsed true
-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}
+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
-), 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
+.
+\end_inset
+
+ y graba bloque a bloque cada
\emph on
-alinear los registros a izquierda
+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
.
-\layout LyX-Code
+ Por cada bloque utilizado se actualiza el archivo de control de espacio
+ libre.
+\layout Standard
-bloque N-1 | bloque N | bloque N+1
-\layout LyX-Code
+Ver:
+\family typewriter
+emufs_tipo1_agregar_registro()
+\layout Subsection
-/----------+------------+------------+-------------------+-----------/
-\layout LyX-Code
+Bajas de registros
+\layout Standard
+Ver:
+\family typewriter
+emufs_tipo1_borrar_registro()
+\layout Subsection
-\backslash
- | registro 1 | registro 2 | espacio libre ...
- |
-\backslash
- /----------+------------+------------+-------------------+-----------/
+Modificación de registros
\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
+Ver:
+\family typewriter
+emufs_tipo1_modificar_registro()
+\layout Subsection
-), de forma tal que no sea necesario recorrer secuencialmente en busca de
- espacio libre al hacer una inserción.
+Obtención de estadísticas
\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
+Ver:
+\family typewriter
+emufs_tipo1_leer_estadisticas()
+\layout Subsection
+
+Compactación del archivo de datos
+\layout Standard
-Comportamiento (funciones de la interfáz)
+Ver:
+\family typewriter
+ emufs_tipo1_compactar()
\layout Section
Detalles de implementación (funciones internas, ver si lo ponemos o no)
@@ -890,9 +1890,15 @@ As
\series bold
.idx
\series default
- :
-\newline
+:
+\begin_inset Float table
+placement H
+wide false
+collapsed true
+
+\layout Caption
+Organización física del archivo de índice o posiciones relativas.
\layout Standard
@@ -994,14 +2000,14 @@ El segundo registro (reg1) comienza en el byte 60
\end_inset
+\end_inset
+
+
\layout Standard
\series bold
\emph on
-\SpecialChar ~
-
-\newline
Observación:
\series default
\emph default
@@ -1026,10 +2032,21 @@ As
\series bold
.fsc
\series default
- :
-\newline
+:
+\begin_inset Float table
+placement H
+wide false
+collapsed true
+
+\layout Caption
+
+Organización física del archivo de
+\emph on
+gaps
+\emph default
+o control de espacio libre.
+\layout Standard
-\newline
\begin_inset Tabular
@@ -1101,14 +2118,14 @@ FREESPACE
\end_inset
+\end_inset
+
+
\layout Standard
\series bold
\emph on
-\SpecialChar ~
-
-\newline
Nota:
\series default
\emph default
@@ -1148,7 +2165,7 @@ El archivo de ID's liberados no presenta ning
su estructura y funcionamiento.
\layout Section
-Comportamiento (funciones de la interfaz)
+Funciones Principales
\layout Standard
Dentro de
@@ -1657,9 +2674,9 @@ Damos por terminada as
para el caso del tipo 2, es realmente bastante sencillo.
\layout Standard
-Ver:
+Ver:
\family typewriter
-void emufs_tipo2_compactar()
+ emufs_tipo2_compactar()
\layout Section
Consideraciones y Políticas de Diseño
@@ -1796,9 +2813,6 @@ El comportamiento de este archivo, es com
\layout Section
Funciones Principales
-\layout Subsection
-
-EMUFS Tipo 3
\layout Standard
Dento de
@@ -1814,7 +2828,7 @@ tipo3.c
\layout Standard
A continuación se comentará la descripción de algunas acciones importantes.
-\layout Subsubsection
+\layout Subsection
Leer Registro
\layout Standard
@@ -1836,7 +2850,7 @@ ID
Ver:
\family typewriter
emufs_tipo3_leer_registro()
-\layout Subsubsection
+\layout Subsection
Grabar Registro
\layout Standard
@@ -1852,7 +2866,7 @@ Luego de grabar un registro, actualiza los archivos de
Ver:
\family typewriter
emufs_tipo3_grabar_registro()
-\layout Subsubsection
+\layout Subsection
Borrar Registro
\layout Standard
@@ -1871,7 +2885,12 @@ Cabe destacar que para dar de baja un registro no hace falta borrarlo del
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
+\layout Standard
+
+Ver:
+\family typewriter
+emufs_tipo3_borrar_registro()
+\layout Subsection
Leer Estadísticas
\layout Standard
@@ -1894,7 +2913,7 @@ Completa una estructura del tipo EMUFS_Estadisticas con las estad
Ver:
\family typewriter
emufs_tipo3_leer_estadisticas()
-\layout Subsubsection
+\layout Subsection
Compactar el Archivo
\layout Standard