From d916a88e11de815e4793e54c61476376135aa94d Mon Sep 17 00:00:00 2001 From: Alan Kennedy Date: Mon, 19 Apr 2004 04:23:15 +0000 Subject: [PATCH] Archivos Auxiliares Done, la tengo que revisar porque debe haber alguna burrada.. --- doc/informe.lyx | 913 +++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 757 insertions(+), 156 deletions(-) diff --git a/doc/informe.lyx b/doc/informe.lyx index 5f84015..8e5ee5b 100644 --- a/doc/informe.lyx +++ b/doc/informe.lyx @@ -322,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 + +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,181 +366,700 @@ Por que los 3 tipos usan lo mismo. \end_inset -Archivo de índice +Archivo índice +\layout Standard + +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_reg. +\layout Standard + +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_reg +\emph default +, 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 + +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 + + +\series bold +\emph on +Ejemplo de registro en archivo índice (.idx), para un archivo de organizacion + Tipo 1 y 3: +\newline + +\series default +\emph default + +\newline + +\begin_inset Tabular + + + + + + + +\begin_inset Text + +\layout Standard + +id_reg +\end_inset + + +\begin_inset Text + +\layout Standard + +nro_bloque +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + + + +\begin_inset Text + +\layout Standard + +5 +\end_inset + + +\begin_inset Text + +\layout Standard + +54 +\end_inset + + +\begin_inset Text + +\layout Standard + +Indica que el registro de id_reg = 5, se encuentra en el bloque 54 +\end_inset + + + + +\end_inset + + +\layout Standard + +\SpecialChar ~ + +\newline + +\series bold +\emph on +Ejemplo de registro en archivo índice (.idx), para un archivo de organizacion + Tipo 2: +\series default +\emph default + +\newline + +\newline + +\begin_inset Tabular + + + + + + + +\begin_inset Text + +\layout Standard + +id_reg +\end_inset + + +\begin_inset Text + +\layout Standard + +nro_bloque +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + + + +\begin_inset Text + +\layout Standard + +5 +\end_inset + + +\begin_inset Text + +\layout Standard + +54 +\end_inset + + +\begin_inset Text + +\layout Standard + +Indica que el registro de id_reg = 5, se encuentra en el bloque 54 +\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 +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 +id_reg +\family default + es N, dentro del archivo de datos ( +\series bold +.dat +\series default +). + +\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 +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). +\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 -Con la ayuda de un archivo de bloques y registros (de extensión .idx), podremos - ubicar cualquier registro existente dentro del archivo. -\layout Standard +12 +\end_inset + + +\begin_inset Text -El archivo de índice contiene una estructura que contiene el id de un registro - y el número de bloque al que pertenece. - Este archivo esta ordenado por -\emph on -id -\emph default -, de modo que incrementa su tamaño cada vez que se grabe en el archivo de - datos un nuevo registro, excepto que un registro haya sido borrado con - anterioridad lo cual produce que al guardar un nuevo registro se actualice - y no crezca. \layout Standard -Si un registro es borrado del archivo de datos, debe actualizarse el índice, - esto se logra colocando un flag que indique que el -\emph on -id -\emph default - no pertenece a ningún bloque, hemos adoptado poner -1 en el campo location - de la estructura -\family typewriter -EMUFS_IDX -\family default -. +120 +\end_inset + + +\begin_inset Text + \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 +Indica que en el bloque 12, hay 120 bytes libres al final del mismo. +\end_inset + + + + +\end_inset -Organización física -\layout Standard -El tipo -\family typewriter -EMUFS_IDX -\family default - define la estuctura de los registros de este archivo. \layout Standard -Esta estructura está compuesta por: -\layout Itemize +\SpecialChar ~ +\newline -\family typewriter -EMUFS_REG_ID -\family default - reg_id indica el +\series bold \emph on -id +Ejemplo de registro en archivo de gaps o espacios libres en archivo (.fsc), + para un archivo de organizacion Tipo 2: +\series default \emph default - del registro -\layout Itemize + +\newline + +\newline +\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 +offset +\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 +freespace +\end_inset + + +\begin_inset Text -Comportamiento (funciones generales) -\layout Section +\layout Standard +\end_inset + + + + +\begin_inset Text -\begin_inset LatexCommand \label{sec:fsc} +\layout Standard +12 \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. - +120 +\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 a partir del byte 12 del archivo de datos, hay 120 bytes libres. +\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 -\family typewriter -EMUFS_BLOCK_ID emufs_fsc_buscar_lugar(EMUFS *, EMUFS_FREE, EMUFS_FREE*) -\family default - perteneciente a + +\series bold \emph on -fsc.h, -\emph default - la cual devuelve el número de bloque donde entra el registro o -1 si no - hay un bloque con lugar suficiente, y toma como parámetros una estructura - -\family typewriter -EMUFS -\family default -, y dos -\family typewriter -EMUFS_FREE -\family default - donde el segndo parámetro es el tamaño buscado, y el tercero devuelve el - tamaño disponible. -\layout Standard +\SpecialChar ~ -De la misma manera, al borrar un registro este archivo debe ser actualizado - colocando el nuevo espacio libre en el bloque. +\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 -Organización Física +Comportamiento \layout Standard -La estuctura que define este archivo es la siguiente: -\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 -EMUFS_FSC +nro_bloque \family default - que contiene: -\layout Itemize - - + 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 -EMUFS_BLOCK_ID +offset \family default - indica el número de bloque -\layout Itemize - - + hasta el mismo. +\newline +Ver: \family typewriter -EMUFS_FREE -\family default - freespace indica la cantidad de espacio libre que queda en el bloque. -\layout Standard +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 -EMUFS_FSC +freespace \family default - y + 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_FREE -\family default - son -\emph on -unsiged long int -\layout Subsection +emufs_fsc_agregar(), emufs_fsc_agregar_gap(), emufs_fsc_actualizar(), emufs_fsc_ +actualizar_gap(). +\layout List +\labelwidthstring 00.00.0000 -Comportamiento + +\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 @@ -518,73 +1070,122 @@ Comportamiento 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 +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 +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 + que fue liberado mas recientemente), y truncará el archivo eliminando el + \emph on -id`s +Id \emph default - sin necesidad de crear uno nuevo cada vez que se borra y graba un registro. + recuperado de la tabla. + (LIFO, Last in First Out). \layout Subsection -Estructura Física +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 almacenado. + 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 Itemize +\layout List +\labelwidthstring 00.00.0000 \series bold -Agregar: +Alta: \series default -agrega un -\emph on -id -\emph default -al archivo, el cual será el primero recuperado. - +Ante la eliminación de un registro del archivo de datos ( +\series bold +.dat +\series default +) se procederá al agregado del correspondiente \family typewriter -Ver: emufs_did_agregar() -\layout Itemize - - +id_reg +\family default + que fue liberado por dicha operación, al archivo \series bold -Obtener el último: +.did \series default - Obtiene el último +. +\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 trunca - el archivo. - + 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 -Ver: emufs_did_get_last() +emufs_did_get_last() \layout Chapter -- 2.43.0