Agrego Magic.

[z.facultad/75.52/treemulator.git] / src / btree.h

diff --git a/src/btree.h b/src/btree.h
index 6764a63d5f0ef8bc559df9e650691cff6781c0ad..9e492139317a15351162c43f5c3637fc42a767cf 100644 (file)
--- a/src/btree.h
+++ b/src/btree.h
@@ -2,62 +2,220 @@
 #ifndef _B_TREE_H
 #define _B_TREE_H
 
 #ifndef _B_TREE_H
 #define _B_TREE_H
 

-/**
- *  La estructura general del archivo seria :
+/** \page page_btree Árbol B
+ * 
+ * \section page_model_class Estructura del árbol en memoria.
+ *
+ * La organización de las clases utilizadas es la siguiente :
+ * 
+ * \image html clases.png
+ * \image latex clases.eps "Diagrama de Clases" width=10cm
+ * 
+ * Para operar con un determinado nodo en memoria, lo que se hace es lo siguiente.
+ * Como primer paso se carga el bloque en memoria llamando a ReadBlock y se lee de él 
+ * su encabezado utilizando una llamada a BTree::ReadNodeHeader, que almacena los datos
+ * en una clase BTreeNodeHeader. A continuación se leen las claves, todavía en formato
+ * RAW, y se genera una lista con instancias de BTreeData. Esta lista es generada
+ * con la llamada a BTree::ReadKeys.
+ *
+ * La operación de búsqueda o inserción se realiza en memoria sobre la lista cargada
+ * anteriormente. Cuando se está listo para guardar todo de nuevo en disco se opera
+ * como se explica a continuación.
+ *
+ * Como primer paso se escriben las claves de la lista nuevamente en el bloque en
+ * memoria en formato RAW, para ello se utilizar WriteKeys, que además de pasar
+ * las claves a formato RAW, también actualiza los datos del header (espacio libre
+ * y cantidad de ítems). Luego se escribe el header en formato RAW con BTree::WriteNodeHeader
+ * y por último se baja a disco el bloque con WriteBlock.
+ *
+ * Para liberar la memoria utilizada solo basta llamar a BTree::DeleteKeys y liberar
+ * el bloque RAW utilizado para el nodo.
+ *
+ * \section page_model_estructura Estructura del árbol en disco.
+ *
+ *  La estructura del archivo donde se almacena el árbol es una secuencia
+ *  de bloques de tamaño fijo parametrizable. Cada bloque representa un nodo
+ *  del árbol, exceptuando el bloque 0 que corresponde al encabezado donde se
+ *  guardan los parámetros del árbol.
+ *  
+ *  <pre>
+ *     Bloque 0   Bloque 1   Bloque 2         Bloque N

  *   +----------+----------+----------+-----+----------+
  *   +----------+----------+----------+-----+----------+

- *   |FileHeader| Bloque 0 | Bloque 1 | ... | Bloque N |
+ *   |FileHeader|  Nodo  0 |  Nodo  1 | ... | Nodo N-1 |

  *   +----------+----------+----------+-----+----------+
  *   +----------+----------+----------+-----+----------+

- *
+ *  </pre>
+ *  

  * Cada bloque tiene su propio encabezado siguiendo la siguiente
  * estructura :
  * Cada bloque tiene su propio encabezado siguiendo la siguiente
  * estructura :

+ *   <pre>

  *   +--------------+-----------------------------------+
  *   +--------------+-----------------------------------+

- *   | BloqueHeader | Area de Claves                    |
+ *   | BloqueHeader | Área de Claves                    |

  *   +--------------+-----------------------------------+
  *   +--------------+-----------------------------------+

+ *   </pre>

  *
  *

- * El area de claves depende del tipo de arbol (INDICE o EXAHUSTIVO)
- * y del tipo de clave (Longitud fija o variable).
+ * El área de claves depende del tipo de árbol (IDENTIFICACION o CLASIFICACION)
+ * y del tipo de Clave (ClaveFija o ClaveVariable).

  *
  *

- * Los nodos que "hojas" (es decir, aquellos que no tienen hijos) no
- * tienen "punteros", por lo que el area de datos seria algo como :
+ * Los nodos que son "hojas" (es decir, aquellos que no tienen hijos) no
+ * tienen "punteros", por lo que el área de datos seria algo como :
+ *  <pre>

  *  +--------------+--------------+--------------+--------------+
  *  | clave1,dato1 | clave2,dato2 | ............ | claveN,datoN |
  *  +--------------+--------------+--------------+--------------+
  *  +--------------+--------------+--------------+--------------+
  *  | clave1,dato1 | clave2,dato2 | ............ | claveN,datoN |
  *  +--------------+--------------+--------------+--------------+

+ *  </pre>
+ *
+ * El par (claveN,datoN) es representado por la clase BTreeLeafData.

  *
  * Ahora, los bloques intermedios tienen punteros a los hijos, y 
  *
  * Ahora, los bloques intermedios tienen punteros a los hijos, y 

- * quedaria algo como :
+ * quedaría algo como :
+ *  <pre>

  *  +---------+----------------------+-------+----------------------+
  *  | HijoIzq | clave1,dato1,HijoDer | ..... | claveN,datoN,HijoDer |
  *  +---------+----------------------+-------+----------------------+
  *  +---------+----------------------+-------+----------------------+
  *  | HijoIzq | clave1,dato1,HijoDer | ..... | claveN,datoN,HijoDer |
  *  +---------+----------------------+-------+----------------------+

+ *  </pre>
+ *
+ * El puntero HijoIzq es representado en memoria por la clase BTreeChildData, y
+ * el resto por BTreeData.

  *
  * El tamaño de la clave es variable, por lo que la cantidad de claves
  * que puede almacenar se basa en la cantidad de espacio libre.
  *
  * Para saber si hay que romper en dos un nodo, se debe ver si la clave
  * a agregar entra en el espacio libre del nodo encontrado como "lugar
  *
  * El tamaño de la clave es variable, por lo que la cantidad de claves
  * que puede almacenar se basa en la cantidad de espacio libre.
  *
  * Para saber si hay que romper en dos un nodo, se debe ver si la clave
  * a agregar entra en el espacio libre del nodo encontrado como "lugar

- * de insercion". Ahora, un problema a resolver es cuando se debe
- * juntar nodos, ya que el arbol B este es particular (Preguntar a Cerveto?).
+ * de inserción".
+ *
+ * \section page_model_op Operaciones Básicas
+ *
+ * En esta sección explicaremos como se realizan las diferentes operaciones
+ * sobre el árbol.
+ *
+ * \subsection page_model_add Agregar una Clave.
+ *
+ * Agregar una clave al árbol es relativamente fácil ya que siempre se agregan
+ * en las hojas.
+ *
+ * El algoritmo comienza a recorrer la raíz buscando la clave inmediatamente
+ * superior (llamada clave de corte) a la que deseamos agregar. Si la raíz es una hoja, la clave es
+ * agregada antes de la clave que corta el algoritmo.
+ *
+ * Si la raíz no es una hoja, se llama recursivamente yendo al nodo hijo de
+ * la clave anterior a la clave de corte, hasta llegar a una hoja y finalmente
+ * agregar la clave.
+ *
+ * En este punto pueden pasar dos cosas. La primera es que la clave entre en el 
+ * lugar libre que le queda al nodo, entonces es agregada y retorna liberando
+ * todo lo que quedó pendiente.
+ *
+ * La segunda situación es que la clave no entre y el nodo deba ser separado
+ * en dos. Cuando esto sucede se crea una lista temporal ordenada con las
+ * claves del nodo a partir y la nueva clave a agregar.
+ * 
+ * La primer mitad se guarda en un nodo, la clave del medio se deja para retornar
+ * al padre y la segunda mitad se pone en un nuevo nodo. Luego de guardar todo
+ * se le retorna al padre una clave. Éste al detectar que un hijo manda una clave
+ * tratará de agregarla siguiendo el mismo procedimiento que el hijo (si no entra
+ * debe realizar un split), hasta llegar a la raíz.
+ *
+ * La única diferencia entre el split en una hoja y el resto de los nodos, es que 
+ * estos últimos hace uso de los datos "hijo izquierdo" e "hijo derecho" también
+ * pasados como parámetros luego del split, a fin de ajustar los punteros necesarios.
+ *
+ * \subsection page_model_del Eliminar una Clave.
+ *
+ * El proceso de eliminar una clave es un poco más complejo y cubre más situaciones
+ * particulares.
+ *
+ * El algoritmo se divide básicamente en 2 casos : eliminar de una hoja y eliminar
+ * de un nodo interno.
+ *
+ * Ambos algoritmos comienzan con una búsqueda en profundidad de la clave a borrar.
+ * en el momento de encontrarla se llama a BTree::DelKeyFromLeaf o BTree::DelKeyFromNode
+ * dependiendo del caso.
+ * 
+ * \subsubsection page_model_del_hoja Eliminar de una Hoja.
+ *
+ * Cuando la clave es encontrada en una hoja simplemente se elimina de la hoja.
+ *
+ * Luego debemos verificar que se cumpla la condición de que el nodo tenga al menos
+ * el 50% del espacio ocupado. Si esto no ocurre debemos actuar como se explica a
+ * continuación.
+ *
+ * Como primer intento pedimos prestada una clave a alguno nuestros hermanos. Si 
+ * alguno es capaz de pasar una clave, ésta última se reemplaza en el padre y la
+ * clave del padre para al nodo en cuestión. Esto se hace para mantener el ordenamiento
+ * del árbol intacto.
+ *
+ * Si ningún hermano me puede prestar, lo único que nos queda es unir dos nodos.
+ * La unión se realiza con cualquier nodo disponible, siempre preguntando primero
+ * por el derecho y si este no existe, se une con el izquierdo. Luego de unir se
+ * le notifica al padre y se ajustan los punteros correspondientes.
+ *
+ * \subsubsection page_model_del_nodo Eliminar de un Nodo.
+ *
+ * Cuando la clave a eliminar se encuentra en una hoja se debe tratar de forma
+ * especial. Lo primero que se hace es buscar en todo el árbol la clave
+ * inmediatamente superior. Esto se logra yendo al hijo derecho de la clave a borrar
+ * y luego siempre hacia el hijo izquierdo hasta llegar a una hoja.
+ *
+ * La primer clave de la hoja encontrada es reemplazada por la clave del padre y 
+ * se llama al borrar de una hoja. Como siempre la clave reemplazada en la hoja queda
+ * en primer lugar, no hay problemas que no esté ordenada al momento de llamar
+ * al algoritmo de borrado en una hoja. De acá en más todo sigue como fue descripto
+ * en el borrado en una hoja.

  *
  *

+ * \subsubsection page_model_problema El problema de la Clave Mayor.

  *
  *

- * TODO :
- *  * Ver como manejar las claves de manera transparente a las APIs de
- *    agregar y de borrar (EMUFS lo solucionaba bastante bien, se puede
- *    tomar una idea simimar)
+ * Este es un problema que hemos encontrado en la actual implementación de árbol
+ * B con claves variables.
+ *
+ * Este puede ocurrir únicamente cuando sucede una junta de nodos. Lo que ocurre
+ * se ejemplifica a continuación. Supongamos por un momento que tenemos dos
+ * nodos a unir cuya suma de tamaños ocupados es N. Ahora supongamos que la clave
+ * del padre, que debe ser unida con los nodos es de tamaño M.
+ *
+ * Si por algun caso particular de las claves N+M es mayor al tamaño del bloque,
+ * la junta no podrá ser realizada.
+ *
+ * Hemos detectado este problema seguido en árboles con bloques de 128 o 256, y muy
+ * rara vez en nodos de 512 o superiores, por lo que no hemos tomado medida alguna
+ * más que documentar su existencia.
+ * 
+ * \subsection page_model_find Búsqueda de una Clave.
+ *
+ * Esta operación se realiza haciendo una búsqueda en profundidad en el árbol.
+ * Si la clave es encontrada se retorna una estructura del tipo BTreeFindResult
+ * con toda la información útil.
+ *
+ * Si no se encuentra retorna NULL.

  */
 
  */
 

-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
+#include <iostream>
+#include <string>
+#include <list>
+#include "common.h"
+#include "clave.h"
+#include "clave_fija.h"
+#include "clave_variable.h"
+#include "btree_data.h"
+#include "exception.h"

 
 /* alias para codear menos :) */
 
 /* alias para codear menos :) */

-typedef unsigned char uchar;

 
 

-/** Encabezado del archivo BTree */
-typedef struct _btree_file_ {
-       unsigned int block_size;
-} BTreeFileHeader;
+/** Encabezado del archivo BTree 
+ *
+ *  Esta estructura es para comodidad de manejo, aunque en disco
+ *  ocupe block_size de tamaño.
+ */
+struct BTreeFileHeader {
+       char magic[7];
+       uint block_size;
+       int tree_type;
+       int key_type;
+       uint block_data_counter;
+};

 
 /** Encabezado de un bloque */
 
 /** Encabezado de un bloque */

-typedef struct _btree_header_ {
+struct BTreeNodeHeader {

        /** Indica a que nivel corresponde un bloque
         *
         *  nivel == 0 : una hoja
        /** Indica a que nivel corresponde un bloque
         *
         *  nivel == 0 : una hoja


@@ -73,48 +231,111 @@ typedef struct _btree_header_ {
 
        /** Cantidad de elementos en el nodo */
        unsigned int item_count;
 
        /** Cantidad de elementos en el nodo */
        unsigned int item_count;

-} BTreeHeader;
+};

 
 

-typedef struct _btree_ {
-       char *filename;
-       BTreeFileHeader header;
+/** Resultado de la búsqueda de una clave */
+struct BTreeFindResult {
+       /** Número de nodo que contiene la clave buscada. */
+       uint node;
+       /** Encabezado del nodo que contiene la clave. */
+       BTreeNodeHeader header;
+};

 
 

-       /** Apunta al archivo de datos, asi se abre solo 1 vez
-        *
-        *  \TODO Ver si vale la pena
-        */
-       FILE *fp;
-} BTree;
-
-/** Crea un nuevo arbol B
+/** Modelo del árbol B

  *
  *  \param filename Nombre del archivo a crear
  *  \param block_size Tamaño de bloque a utilizar
  *
  *  \param filename Nombre del archivo a crear
  *  \param block_size Tamaño de bloque a utilizar

+ *  \param k_t Tipo de clave a utilizar

  *  \return Un nuevo arbol B creado o NULL en caso de error
  */
  *  \return Un nuevo arbol B creado o NULL en caso de error
  */

-BTree *btree_create (const char *filename, unsigned int block_size);
+class BTree {
+       public:
+               BTree (const std::string &filename, unsigned int block_size, int t_t = TYPE_IDENTIFICACION, int k_t = KEY_FIXED, bool create_new_file = false);
+               BTree (const std::string &filename);

 
 

-/** Abre un arbol B existente
- *
- *  \param filename Nombre del archivo a abrir
- *  \return El arbol abierto o NULL en caso de error
- */
-BTree *btree_open (const char *filename);
+               ~BTree ();

 
 

-/** Agrega una clave en el arbol
- *
- *  \TODO Definir parametros
- */
-int btree_add (BTree *);
+               /** Tipos de clave a usar */
+               enum {
+                       KEY_FIXED,    /**< Utilización de clave de longitud fija */
+                       KEY_VARIABLE  /**< Utilización de clave de longitud variable */
+               };
+
+               enum {
+                       TYPE_IDENTIFICACION,
+                       TYPE_CLASIFICACION
+               };
+       
+               /** Agrega una nueva clave al árbol. */
+               void AddKey (const Clave &k);
+               /** Elimina una clave del árbol. */
+               void DelKey (const Clave &k);
+               /** Busca si existe una clave en el árbol
+                *
+                * \return Un BTreeFindResult que el usuario debe liberar.
+                */
+               BTreeFindResult *FindKey (const Clave &k);
+
+               int type() const;
+
+       //protected:
+               /* Funciones de Alta */
+               Clave* AddKeyR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
+               Clave* AddKeyOtherR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
+               Clave* AddKeyLeafR (const Clave *k, uint node_num, uint &left_child, uint &right_child);
+
+               /* Funciones de Baja */
+               void DelKeyR (BTreeData *k, uint node, uint padre);
+               void DelKeyFromLeaf (Clave *k, uint node_num, uint padre);
+               void DelKeyFromNode (Clave *k, uint node_num, uint padre, uint left, uint right);
+               void FindBrothers (uint node_num, uint padre, uint &left, uint &right);
+               Clave *ReplaceKeyInFather (uint node_num, uint padre, Clave *k);
+               Clave *GetKey (uint node_num, char maxmin);
+               void JoinNodes (uint node1, uint node2, uint padre, int);
+
+               /* Funciones de Búsqueda */
+               BTreeFindResult *FindKeyR (const Clave *k, uint node);
+
+               /* Funciones de manejo de archivo */
+               void WriteFileHeader ();
+               void ReadFileHeader ();
+
+               /* Manejo de Bloques */
+               void WriteBlock (uchar *block, uint num);
+               uchar *ReadBlock (uint num);
+               uchar *NewBlock (uint &num);
+
+               /* Manejo de headers */
+               void ReadNodoHeader (uchar *node, BTreeNodeHeader *header);
+               void WriteNodoHeader (uchar *node, BTreeNodeHeader *header);
+
+               /* Manejo de claves en memoria */
+               std::list<BTreeData *> ReadKeys (uchar *node, BTreeNodeHeader &node_header);
+               void WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list<BTreeData *> &keys);
+               void DeleteKeys (std::list<BTreeData *> &keys);
+
+               /* Abreviacion de Claves */
+               void AbrevKey (std::list<BTreeData *> &lst);
+               void DeAbrevKey (std::list<BTreeData *> &lst);
+
+               std::string filename;
+               BTreeFileHeader header;
+
+               uint GetNextBlockData ();
+
+               /** Apunta al archivo de datos, asi se abre solo 1 vez
+                *
+                *  \todo Ver si vale la pena
+                */
+               FILE *fp;
+               std::list<uint> deleted_nodes;
+               std::list<uint> deleted_block_data;

 
 

-/** Borra una clave del arbol
- *
- *  \TODO Definir parametros
- */
-int btree_del (BTree *);

 
 

-/** Cierra el arbol y libera los recursos */
-int btree_close (BTree *);
+               /* DEBUG */
+       public:
+               void PrintNode (uint num);
+};

 
 #endif // _B_TREE_H
 
 
 #endif // _B_TREE_H