X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/151ec0aa6089804f6a7a8cdb1416ad656f4d3fa3..d916a88e11de815e4793e54c61476376135aa94d:/doc/informe.lyx?ds=inline diff --git a/doc/informe.lyx b/doc/informe.lyx index 3645bb9..8e5ee5b 100644 --- a/doc/informe.lyx +++ b/doc/informe.lyx @@ -55,8 +55,11 @@ EMUFS \layout Standard +\family typewriter +EMUFS +\family default \emph on -EMUFS + \emph default es la estuctura principal que encapsula todas las funciones para el manejo de un archivo de datos. @@ -65,21 +68,149 @@ es la estuctura principal que encapsula todas las funciones para el manejo Esta estructura consta de: \layout Enumerate -EMUFS_Tipo que es un tipo enumerado que indica cual es la organización. + +\family typewriter +EMUFS_Tipo +\family default + que es un tipo enumerado que indica cual es la organización. \layout Enumerate -EMUFS_BLOCK_SIZE indica el tamaño del bloque para los tipos 1 y 3. + +\family typewriter +EMUFS_BLOCK_SIZE +\family default + indica el tamaño del bloque para los tipos 1 y 3. \layout Enumerate -EMUFS_REG_SIZE indica el tamaño del registro, para el tipo 3 que posee tamaño - constante. + +\family typewriter +EMUFS_REG_SIZE +\family default + indica el tamaño del registro, para el tipo 3 que posee tamaño constante. \layout Enumerate -void *leer_bloque() -\layout Comment -no me convence esta descripcion. - +\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 @@ -191,10 +322,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 -Por que los 3 tipos usan lo mismo. - Ventajas y desventajas. +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 + +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 @@ -202,212 +366,826 @@ 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 id no pertenece a ningún - bloque, hemos adoptado poner -1 en el campo location de la estructura -\emph on -EMUFS_IDX -\emph 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 EMUFS_IDX define la estuctura de los registros de este archivo. +Los registros de este archivo se encuentran representados a nivel codigo + por el siguiente tipo de dato interno ( +\family typewriter +EMUFS_IDX +\family default +): +\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 -EMUFS_REG_ID reg_id indica el +\series bold \emph on -id +Ejemplo de registro en archivo índice (.idx), para un archivo de organizacion + Tipo 1 y 3: +\newline + +\series default \emph default - del registro -\layout Itemize -EMUFS_BLOCK_ID location número de bloque donde se encuentra el registro. +\newline + +\begin_inset Tabular + + + + + + + +\begin_inset Text + \layout Standard -EMUFS_REG_ID y EMUFS_BLOCK_ID son -\emph on -unsigned long. -\layout Comment +id_reg +\end_inset + + +\begin_inset Text -ponerlo mas lindo... -\layout Subsection +\layout Standard -Comportamiento (funciones generales) -\layout Section +nro_bloque +\end_inset + + +\begin_inset Text + +\layout Standard +\end_inset + + + + +\begin_inset Text -\begin_inset LatexCommand \label{sec:fsc} +\layout Standard +5 \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. - +54 +\end_inset + + +\begin_inset Text + \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. +Indica que el registro de id_reg = 5, se encuentra en el bloque 54 +\end_inset + + + + +\end_inset + + \layout Standard -De esta manera al querer guardar un registro este archivo informará donde - cabe el mismo, previa invocación al la función -\emph on -EMUFS_BLOCK_ID emufs_fsc_buscar_lugar(EMUFS *, EMUFS_FREE, EMUFS_FREE*) -\emph default - perteneciente a fsc.h, la cual devuelve el número de bloque donde entra - el registro o -1 si no hay un bloque con lugar suficiente, y toma como - parámetros una estructura -\emph on -EMUFS -\emph default -, y dos +\SpecialChar ~ + +\newline + +\series bold \emph on -EMUFS_FREE +Ejemplo de registro en archivo índice (.idx), para un archivo de organizacion + Tipo 2: +\series default \emph default - donde el segndo parámetro es el tamaño buscado, y el tercero devuelve el - tamaño disponible. -\layout Standard + +\newline + +\newline -De la misma manera, al borrar un registro este archivo debe ser actualizado - colocando el nuevo espacio libre en el bloque. -\layout Subsection +\begin_inset Tabular + + + + + + + +\begin_inset Text -Organización Física \layout Standard -La estuctura que define este archivo es la siguiente: -\layout Standard +id_reg +\end_inset + + +\begin_inset Text -EMUFS_FSC que contiene: -\layout Itemize +\layout Standard -EMUFS_BLOCK_ID indica el número de bloque -\layout Itemize +nro_bloque +\end_inset + + +\begin_inset Text -EMUFS_FREE freespace indica la cantidad de espacio libre que queda en el - bloque. \layout Standard -EMUFS_FSC y EMUFS_FREE son -\emph on -unsiged long int -\layout Subsection +\end_inset + + + + +\begin_inset Text -Comportamiento -\layout Section +\layout Standard +5 +\end_inset + + +\begin_inset Text -\begin_inset LatexCommand \label{sec:did} +\layout Standard +54 \end_inset + + +\begin_inset Text -Archivo de índices recuperables \layout Standard -<<<<<<< .mine -Este archivo funciona como una pila de id`s borrados, es decir, cuando se - borra un registro el -\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 +Indica que el registro de id_reg = 5, se encuentra en el bloque 54 +\end_inset + + + + +\end_inset + -Estructura Física \layout Standard -Este archivo tiene registros de un solo campo, EMUFS_REG_ID el cual simboliza - al id almacenado. + +\series bold +\emph on +\SpecialChar ~ + +\newline +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 -did.h +idx.h +\series default \emph default y +\series bold \emph on -did.c +idx.c +\series default \emph default - respectivamente -\layout Itemize + respectivamente: +\layout List +\labelwidthstring 00.00.0000 \series bold -Agregar: -\series default -agrega un \emph on -id +Búsqueda: +\series default \emph default -al archivo, el cual será el primero recuperado. + 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 +id_reg +\family default + es N, dentro del archivo de datos ( +\series bold +.dat +\series default +). -\emph on -ver: emufs_did_agregar() -\layout Itemize +\newline + +\newline +NOTA: 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 -Obtener el último: +Alta: \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. - + 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). +\newline + +\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 +Ejemplo de registro en archivo de espacio libre en bloque (.fsc), para un + archivo de organizacion Tipo 1 y 3: +\newline + +\series default +\emph default + +\newline + +\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 + + +\layout Standard + +\SpecialChar ~ + +\newline + +\series bold +\emph on +Ejemplo de registro en archivo de gaps o espacios libres en archivo (.fsc), + para un archivo de organizacion Tipo 2: +\series default +\emph default + +\newline + +\newline + +\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 + + +\layout Standard + + +\series bold +\emph on +\SpecialChar ~ + +\newline +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 -ver: emufs_did_get_last() -======= -(.did) +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 índices 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 -idem anterior ->>>>>>> .r356 +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 + +Comportamiento +\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 @@ -469,8 +1247,11 @@ T1 EMUFS_Tipo \family default ). - Luego le sigue una cabecera propia del archivo (un EMUFS_BLOCK_SIZE, 4 - bytes) que almacena el tamaño del bloque que usa el archivo. + Luego le sigue una cabecera propia del archivo (un +\family typewriter +EMUFS_BLOCK_SIZE +\family default +, 4 bytes) que almacena el tamaño del bloque que usa el archivo. De esta menera, al abrir un archivo de este tipo no se necesita tener ninguna información sobre él. A esta cabecera le siguen cero o más bloques del tamaño fijo especificado @@ -633,7 +1414,7 @@ collapsed true \layout Caption -NOMBRE, ARREGLAME!!!! +Organización física de los registros en disco \layout Standard @@ -662,6 +1443,310 @@ EMUFS_REG_SIZE Luego se encuentra el espacio libre de 18 bytes dejado por el registro de 10 bytes eliminado (10 bytes de datos + header de 8 bytes) y finalmente el segundo registro mencionado.dsds +\layout Subsection + +Comportamiento Particular de los Archivos Auxiliares +\layout Standard + +Como fue explicado al inicio de la documentación, la implementación de cualquier +a de las tres organizaciones físicas de archivos presenta la necesidad de + poseer tres archivos auxiliares que actuarán como índice de direcciones + de registro (. +\series bold +idx +\series default +), administrador de espacio libre ( +\series bold +.fsc +\series default +) y administrador de Id's liberados ( +\series bold +.did +\series default +) respectivamente. +\layout Standard + +No obstante, cada tipo de organización presentara sus particularidades respecto + de estos tres archivos, las cuales describiremos a continuación en caso + de haberla. +\layout Subsubsection + +Archivo índice o de posiciones relativas (.idx) +\layout Standard + +El archivo indice ( +\series bold +.idx +\series default +), permite la localizacin de los registros en el .DAT de forma directa, mediante + la obtención de su offset o posición relativa respecto del inicio del +\series bold +.dat +\series default + en donde se encuentra un registro dado, indicado por su ID. +\layout Standard + +Así pues, si tomamos el ejemplo descripto al inicio de este capítudlo, tendremos + las siguientes entradas en el archivo indice +\series bold +.idx +\series default + : +\newline + +\layout Standard + + +\begin_inset Tabular + + + + + + + +\begin_inset Text + +\layout Standard + + +\emph on +ID_REGISTRO +\end_inset + + +\begin_inset Text + +\layout Standard + + +\emph on +OFFSET +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\series bold +0 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +4 +\end_inset + + +\begin_inset Text + +\layout Standard + +El primer registro (reg0) comienza en el byte 4 +\end_inset + + + + +\begin_inset Text + +\layout Standard + +1 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +60 +\end_inset + + +\begin_inset Text + +\layout Standard + +El segundo registro (reg1) comienza en el byte 60 +\end_inset + + + + +\end_inset + + +\layout Standard + + +\series bold +\emph on +\SpecialChar ~ + +\newline +Observación: +\series default +\emph default + LOCATION indica donde comienza el header del registro buscado, y por consiguien +te luego del header tendremos el registro en sí (los datos). +\layout Subsubsection + +Achivo de Gaps / Espacios Libres (.fsc) +\layout Standard + +El archivo de espacios libres o gaps (.fsc), tiene como función la administracion + del espacio libre o gaps (agujeros), generados por previas eliminaciones + de registros en el archivo de datos. + El mismo, nos indicará donde hay lugar para insertar un nuevo registro + (se podrán insertar en algún gap acorde, o bien al final del archivo). + Este archivo será utilizado tambien para el proceso de compactación de + un archivo, explicado luego. +\layout Standard + +Así pues, si tomamos el ejemplo descripto al inicio del documento, tendremos + las siguientes entradas en el archivo índice +\series bold +.fsc +\series default + : +\newline + +\newline + +\begin_inset Tabular + + + + + + + +\begin_inset Text + +\layout Standard + + +\emph on +OFFSET +\end_inset + + +\begin_inset Text + +\layout Standard + + +\emph on +FREESPACE +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + + + +\begin_inset Text + +\layout Standard + + +\series bold +42 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +18 +\end_inset + + +\begin_inset Text + +\layout Standard + +18 bytes libres a partir del byte 42 del .dat +\end_inset + + + + +\end_inset + + +\layout Standard + + +\series bold +\emph on +\SpecialChar ~ + +\newline +Nota: +\series default +\emph default + Por requerimiento del algoritmo de compactación, los gaps se graban en + forma ordenada en el (.fsc). + (El orden se corresponde con lo que hay en el .dat) +\layout Subsubsection* + +GAP Merging +\layout Standard + +Si bien la utilización concreta de los GAPS será explicada posteriormente + en la ALTA y BAJA de registros, debemos remarcar la funcionalidad de MERGING + que posee nuestro sistema FSC. +\layout Standard + +Ante la eliminación de un registro del archivo de datos, se generara por + consiguiente un gap o espacio libre en alguna posición del archivo. + Ese gap deberá ser registrado en el archivo de gaps (.fsc). + Ahora bien, nuestro sistema de gaps, contemplará como es debido, la posibilidad + de que se haya eliminado un registro que posee un GAP por delante, un GAP + por detrás, o bien un GAP por delante y por detrás del mismo. +\layout Standard + +Nuestro sistema actuará en consecuencia, realizando un merge de los espacios + libres, y unificándolos en una UNICA entrada en el archivo .fsc, que contendrá + como dato de freespace, la suma correspondiente de los espacios libres + antes mencionados. +\layout Subsubsection + +Archivo de ID's liberados (.did) +\layout Standard + +El archivo de ID's liberados no presenta ningún aspecto particular en este + tipo de organización. + Remitirse al capítulo correspondiente a los archivos auxiliares para consultar + su estructura y funcionamiento. \layout Section Comportamiento (funciones de la interfaz) @@ -724,6 +1809,11 @@ RegSize ). Contando así con el tamaño del registro, procedemos a leer el mismo (los datos), dando por finalizada la lectura. +\layout Standard + +Ver: +\family typewriter +emufs_tipo2_leer_registro() \layout Subsection Altas de registros @@ -790,6 +1880,11 @@ Actualizamos la entrada correspondiente al registro ingresado (determinada .idx \series default ), indicando su offset donde podrá ser accedido luego. +\layout Standard + +Ver: +\family typewriter +emufs_tipo2_agregar_registro() \layout Subsection Bajas de registros @@ -870,6 +1965,11 @@ Se marca en el archivo ) la eliminación, mediante el valor ¨-1¨ en el registro correspondiente al registro recién eliminado (se le cambia el valor al n-esimo registro, donde N = IDReg del reg eliminado). +\layout Standard + +Ver: +\family typewriter +emufs_tipo2_borrar_registro() \layout Subsection Modificación de registros @@ -898,9 +1998,34 @@ NOTA: Como fue indicado, dada la naturaleza de PILA del subsistema de administración de ID liberados, es asegurado que la nueva inserción del registro modificado se realizará con el mismo RegID. +\layout Standard + +Ver: +\family typewriter +emufs_tipo2_modificar_registro() \layout Subsection Obtención de estadísticas +\layout Standard + +Se puede tener acceso a las estadísticas generales del archivo, por ejemplo, + cantidad de bloques, cantidad de registros, espacio libre total, espacio + libre promedio, espacio libre máximo y mínimo, etc. +\layout Standard + +Esta información es el resultado de ciertos cálculos realizados tanto en + el archivo de datos como en los archivos índice. +\layout Standard + +Completa una estructura del tipo EMUFS_Estadisticas con las estadísticas + del archivo de datos, espacio libre total, cantidad de registros, cantidad + de bloques, tamaño del archivo en bytes, relaciones entre tamaños y espacios + libres, etc. +\layout Standard + +Ver: +\family typewriter +emufs_tipo2_leer_estadisticas() \layout Subsection Compactación del archivo de datos @@ -932,7 +2057,7 @@ collapsed true \layout Caption -NOMBRE, ARREGLAMEE!!! +Archivo con gaps entre registros previo a compactación \layout Standard @@ -1078,7 +2203,7 @@ collapsed true \layout Caption -NOMBRE, ARREGLAME!!!! +Archivo con gaps en disco luego del primer bucle de compactación \layout Standard @@ -1131,6 +2256,94 @@ Mustmove_bytes = Datsize - Source Damos por terminada así, la explicación del algoritmo de compresión el cual para el caso del tipo 2, es realmente bastante sencillo. +\layout Standard + +Ver: +\family typewriter +void emufs_tipo2_compactar() +\layout Section + +Consideraciones y Políticas de Diseño +\layout Standard + +Se han tomado ciertas consideraciones para algunos casos particulares que + se pueden presentar durante el uso/ejecución de la aplicación, así como + tambien politicas respecto del diseño e implementación del sistema: +\layout Itemize + +En la organización física tipo 2 para los registros que se graban en disco + hemos decidido utilizar como encabezado de cada uno de ellos, los datos + [ID_REG][REG_SIZE], los cuales fueron detallados previamente. + Si bien se podría haber descartado el grabado del ID del registro en el + archivo de datos y puede parecer redundante, dado que poseemos el archivo + índice con el offset directo, el mismo se lo graba por distintos motivos: +\newline + +\newline +A) En caso de la corrupción del archivo índice (.idx), podremos gracias a + que poseemos en el archivo de datos, el ID de cada registro, recrear dicho + índice, ayudándonos del archivo de espacios libres ( +\series bold +.fsc +\series default +), para poder saltear los espacios libres y e ir recorriendo secuencialmente + los registros, reconstruyendo así el índice en cuestión. + (esta función de reconstrucción no pudo ser implementada para esta entrega, + pero es una posibilidad real). +\newline + +\newline +B) Luego de un proceso de recompactación, los espacios libres que pudieron + haber existido en el archivo de datos ( +\series bold +.dat +\series default +), son eliminados y los registros han cambiado de posición. + Por ello, recorriendo secuencialmente por única vez el archivo de datos, + se procede a la actualización / reconstrucción del índice de direcciones + u offsets (. +\series bold +idx +\series default +) +\layout Itemize + +Si se desea insertar un registro y no se puede hayar un gap o espacio libre + donde quepa, se los inserta al final del archivo. +\layout Itemize + +Ante una operación de baja de un registro, el mismo no es físicamente borrado + del archivo de datos ( +\series bold +.dat +\series default +), simplemente los bytes que ocupa son llenados con hexa (00). + Paralelamente, se procede a actualiza el archivo índice, insertando como + valor de OFFSET para el registro eliminado, el valor ¨-1¨, indicando así + la inexistencia del registro para el futuro, y por otro lado se genera + la entrada de espacio libre en el archivo de gaps ( +\series bold +.fsc +\series default +). +\layout Itemize + +La reutilización de ID's liberados por previas operaciones de baja de registros, + se ve implementada por el archivo de ID liberados (.did), y su comportamiento + es el de una pila por lo que el último ID liberado, sera el próximo a ser + reutilizado (LIFO). +\layout Itemize + +Como fue explicado en la implementación del archivo índice, existe una correspon +dencia 1 a 1 entre los registros allí presentes (en el .idx) y los ID's de + los registros, por lo cual el registro N-ésimo del archivo índice, será + el correspondiente al registro de datos cuyo ID es igual a N. +\layout Itemize + +El proceso de compactación de archivos, realiza los movimientos de información + requeridos para dicho propósito de a chunks de 25 bytes por vez. + Este valor es fijo, pero se lo podría hacer parametrizable mediante la + GUI en próximas entregas. \layout Chapter @@ -1308,6 +2521,14 @@ que pudieron haberse formado por la eliminaci por otros. \layout Standard +Al estar utilizando recuperación de +\emph on +id`s +\emph default + borrados, esto me asegura que el registro borrado-guardado conservará el + id al grabarse. +\layout Standard + Al finalizar este proceso se verifica si existen bloques vacios para truncar el archivo. Lo mismo se debe hacer con el archivo de espacios libres .