X-Git-Url: https://git.llucax.com/z.facultad/75.06/emufs.git/blobdiff_plain/09df7c33240167f462c5cbdf3ba569b03f8f7037..151ec0aa6089804f6a7a8cdb1416ad656f4d3fa3:/doc/informe.lyx?ds=sidebyside diff --git a/doc/informe.lyx b/doc/informe.lyx index b7619bd..3645bb9 100644 --- a/doc/informe.lyx +++ b/doc/informe.lyx @@ -54,7 +54,32 @@ Tipos EMUFS \layout Standard -callbacks, etc + +\emph on +EMUFS +\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 + +EMUFS_Tipo 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. +\layout Enumerate + +EMUFS_REG_SIZE 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. + \layout Subsection EMUFS_Tipo @@ -67,46 +92,463 @@ 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 Standard +\layout Comment -Por que los 3 tipos usan los mismo. +Por que los 3 tipos usan lo mismo. Ventajas y desventajas. \layout Section -Archivo de índice (.idx) + +\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 -introduccion +El archivo de índice contiene una estructura que contiene el id de un registro + y el número de bloque al que pertenece. + Este archivo esta ordenado por +\emph on +id +\emph default +, de modo que incrementa su tamaño cada vez que se grabe en el archivo de + datos un nuevo registro, excepto que un registro haya sido borrado con + anterioridad lo cual produce que al guardar un nuevo registro se actualice + y no crezca. +\layout Standard + +Si un registro es borrado del archivo de datos, debe actualizarse el índice, + esto se logra colocando un flag que indique que el id no pertenece a ningún + bloque, hemos adoptado poner -1 en el campo location de la estructura +\emph on +EMUFS_IDX +\emph default +. +\layout Standard + +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 -Estructura física +Organización física +\layout Standard + +El tipo EMUFS_IDX define la estuctura de los registros de este archivo. +\layout Standard + +Esta estructura está compuesta por: +\layout Itemize + +EMUFS_REG_ID reg_id indica el +\emph on +id +\emph default + del registro +\layout Itemize + +EMUFS_BLOCK_ID location número de bloque donde se encuentra el registro. +\layout Standard + +EMUFS_REG_ID y EMUFS_BLOCK_ID son +\emph on +unsigned long. +\layout Comment + +ponerlo mas lindo... \layout Subsection Comportamiento (funciones generales) \layout Section -Archivo de control de espacio libre (.fsc) + +\begin_inset LatexCommand \label{sec:fsc} + +\end_inset + +Archivo de control de espacio libre \layout Standard -idem anterior +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 +\emph on +EMUFS_BLOCK_ID emufs_fsc_buscar_lugar(EMUFS *, EMUFS_FREE, EMUFS_FREE*) +\emph default + perteneciente a fsc.h, la cual devuelve el número de bloque donde entra + el registro o -1 si no hay un bloque con lugar suficiente, y toma como + parámetros una estructura +\emph on +EMUFS +\emph default +, y dos +\emph on +EMUFS_FREE +\emph default + donde el segndo parámetro es el tamaño buscado, y el tercero devuelve el + tamaño disponible. +\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 + +EMUFS_FSC que contiene: +\layout Itemize + +EMUFS_BLOCK_ID indica el número de bloque +\layout Itemize + +EMUFS_FREE freespace indica la cantidad de espacio libre que queda en el + bloque. +\layout Standard + +EMUFS_FSC y EMUFS_FREE son +\emph on +unsiged long int +\layout Subsection + +Comportamiento \layout Section -Archivo de índices recuperables (.did) + +\begin_inset LatexCommand \label{sec:did} + +\end_inset + +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 + +Estructura Física +\layout Standard + +Este archivo tiene registros de un solo campo, EMUFS_REG_ID 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. + +\emph on +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. + +\emph on +ver: emufs_did_get_last() +======= +(.did) \layout Standard idem anterior +>>>>>>> .r356 \layout Chapter + +\begin_inset LatexCommand \label{cha:tipo1} + +\end_inset + Archivo con bloques parametrizados y registros de longitud variable \layout Standard -introduccion +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 EMUFS_BLOCK_SIZE, 4 + bytes) que almacena el tamaño del bloque que usa el archivo. + De esta menera, al abrir un archivo de este tipo no se necesita tener ninguna + información sobre él. + A esta cabecera le siguen cero o más bloques del tamaño fijo especificado + en la cabecera antes mencionada. +\layout LyX-Code + +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) @@ -115,21 +557,587 @@ Comportamiento (funciones de la interf 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 -introduccion +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 Section +\layout Standard -Comportamiento (funciones de la interfáz) +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 + +NOMBRE, ARREGLAME!!!! +\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 Section -Detalles de implementación (funciones internas, ver si lo ponemos o no) +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 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 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 Subsection + +Modificación de registros +\layout Standard + +Dada la naturaleza del archivo de ID's liberados, y el manejo de espacio + libre del que consta esta organización de archivo, el proceso de modificación + de un registro se limita a los siguientes pasos: +\layout Enumerate + +Se realiza la lectura del registro, mediante el respectivo procedimiento + ya desarollado anteriormente. +\layout Enumerate + +Una vez que se cuenta con los nuevos datos modificados, se procede a dar + de baja el registro que ha sido modificado, e inmediatamente después se + realiza una inserción con los nuevos datos. +\layout Standard + + +\series bold +\emph on +NOTA: +\series default +\emph default + Como fue indicado, dada la naturaleza de PILA del subsistema de administración + de ID liberados, es asegurado que la nueva inserción del registro modificado + se realizará con el mismo RegID. +\layout Subsection + +Obtención de estadísticas +\layout Subsection + +Compactación del archivo de datos +\layout Standard + +Asi como los otros dos tipos de datos, el que nos compete también cuenta + con la posibilidad de realizar la compactación de datos cuando el usuario + lo desee, justificando todos los registros a izquierda, eliminando así + los gaps existentes y decrementando el tamaño del archivo en disco (truncandolo +). +\layout Standard + +Para poder comprender como hemos implementado el proceso de recompactación + en nuestro tipo de archivo 2, nos ayudaremos de esquemas a través de los + cuales iremos describiendo el proceso. + Notemos antes, que el proceso de compactación esta directamente ligado + con el archivo de gaps o espacios libres ( +\series bold +.fsc +\series default +). +\layout Standard + +Comenzemos con el siguiente cuadro situacional: +\begin_inset Float figure +placement H +wide false +collapsed true + +\layout Caption + +NOMBRE, ARREGLAMEE!!! +\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 + +NOMBRE, ARREGLAME!!!! +\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 Chapter + +\begin_inset LatexCommand \label{cha:tipo3} + +\end_inset + Archivo con bloques parametrizados y registros de longitud constante \layout Standard @@ -156,68 +1164,23 @@ As del archivo. \layout Subsection -Archivos Auxiliares +Comportamiento Particular de los Archivos Auxiliares \layout Subsubsection Archivo de Bloques y Registros (.idx) -\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 id, de modo que incrementa su tamaño cada - vez que se grabe en el archivo de datos un nuevo registro, excepto que - un registro haya sido borrado con anterioridad lo cual produce que al guardar - un nuevo registro se actualice y no crezca. -\layout Standard - -Si un registro es borrado del archivo de datos, debe actualizarse el índice, - esto se logra colocando un flag que indique que el id no pertenece a ningún - bloque, hemos adoptado poner -1 en el campo location de la estructura EMUFS_IDX. -\layout Standard +\layout Comment -Es necesario que este archivo esté ordenado por id de registro, ya que esto - permitirá el acceso directo para la búsqueda de un registro en el archivo - de datos. +buscar algun caso extraordinario. \layout Subsubsection Archivo de Bloques y Espacio Libre (.fsc) -\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 EMUFS_BLOCK_ID emufs_fsc_buscar_ -lugar(EMUFS *, EMUFS_FREE, EMUFS_FREE*) 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 EMUFS, y dos EMUFS_FREE - 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 Subsubsection Archivo de Id`s Borrados (.did) \layout Standard -Este archivo funciona como una pila de id`s borrados, es decir, cuando se - borra un registro el id se almacena en este archivo y será recuperado cuando - se desee grabar un registro nuevo, de esta manera se aprovechan todos los - id`s sin necesidad de crear uno nuevo cada vez que se borra y graba un - registro. +El comportamiento de este archivo, es común para todas las organizaciones + y se ha explicado en 3.3.2. \layout Section Funciones Principales @@ -238,103 +1201,90 @@ tipo3.c respectivamente, las cuales dan funcionalidad a esta organización. \layout Standard -A continuación se comentará el funcionamiento algunas de las mas importantes. +A continuación se comentará la descripción de algunas acciones importantes. \layout Subsubsection -void* emufs_tipo3_leer_registro(EMUFS *emu, EMUFS_REG_ID ID, EMUFS_REG_SIZE* - reg_size, int* err) -\layout Standard - -Devuelve un puntero con la memoria reservada que contiene al registro solicitado - por el segundo parámetro ( -\emph on -ID -\emph default - ), y almacena en -\emph on -reg_size -\emph default -el tamaño del registro leido, que en este caso no es necesario pues es constante - y es conocicdo de antemano. +Leer Registro \layout Standard -Para realizar esta acción, busca en el archivo +La lectura de un registro se realiza con la ayuda del archivo . \emph on -.idx +idx \emph default -el bloque al cual pertenece el registro. -\layout Subsubsection - -void* emufs_tipo3_leer_bloque(EMUFS *emu, EMUFS_BLOCK_ID num_bloque, int* - err) -\layout Standard - -Devuelve un puntero con la memoria reservada que contiene el bloque solicitado - por el segundo parámetro ( + 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 -num_bloque +ID \emph default -). - + especificado. \layout Standard -Como la numeración de los bloques es -\emph on -virtual, -\emph default -el acceso al archivo para levantar un bloque es directo, es decir, se posiciona - directamente en en número de bloque multiplicado por el tamaño del mismo, - salteando antes el encabezado del archivo. +Ver: +\family typewriter +emufs_tipo3_leer_registro() \layout Subsubsection -EMUFS_REG_ID emufs_tipo3_grabar_registro(EMUFS *emu, void *ptr, EMUFS_REG_SIZE - tam, int* err) +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 -El registro a grabar es apuntado por el segundo parámetro ( -\emph on -ptr -\emph default -) y el tamaño viene indicado en el tercero ( -\emph on -tam -\emph default - ). +Luego de grabar un registro, actualiza los archivos de índice .idx y .fsc + para mantener la coherencia. \layout Standard -Luego de realizar la grabación, actualiza los archivos índice con los valores - correspondientes. +Ver: +\family typewriter +emufs_tipo3_grabar_registro() \layout Subsubsection -int emufs_tipo3_borrar_registro(EMUFS *emu, EMUFS_REG_ID ID) +Borrar Registro \layout Standard -Borra el registro indicado por el segundo parámetro ( -\emph on -ID -\emph default - ) del archivo de datos, y actualiza los archivos de índice para mantener - la coherencia en las próximas modificaciones. +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 -Al borrar un registro, justifica los demás registros del bloque hacia la - izquierda. +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 -EMUFS_Estadisticas emufs_tipo3_leer_estadisticas(EMUFS *emu) +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 -void emufs_tipo3_compactar(EMUFS *emu) +Compactar el Archivo \layout Standard Esta función intenta reorganizar el archivo de manera que el espacio libre @@ -365,6 +1315,11 @@ Al finalizar este proceso se verifica si existen bloques vacios para truncar 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