X-Git-Url: https://git.llucax.com/z.facultad/75.52/treemulator.git/blobdiff_plain/8f65edaf64b0014de583abe4f6b29d75be1d77ce..b08d09c0c5ba065ea663371f3ad577a81948860d:/src/btree.h
diff --git a/src/btree.h b/src/btree.h
index 6764a63..861b535 100644
--- a/src/btree.h
+++ b/src/btree.h
@@ -2,32 +2,53 @@
#ifndef _B_TREE_H
#define _B_TREE_H
-/**
- * La estructura general del archivo seria :
+/** \page page_btree Árbol B
+ *
+ * \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.
+ *
+ *
+ * Bloque 0 Bloque 1 Bloque 2 Bloque N
* +----------+----------+----------+-----+----------+
- * |FileHeader| Bloque 0 | Bloque 1 | ... | Bloque N |
+ * |FileHeader| Nodo 0 | Nodo 1 | ... | Nodo N-1 |
* +----------+----------+----------+-----+----------+
- *
+ *
+ *
* Cada bloque tiene su propio encabezado siguiendo la siguiente
* estructura :
+ *
* +--------------+-----------------------------------+
* | BloqueHeader | Area de Claves |
* +--------------+-----------------------------------+
+ *
*
* El area de claves depende del tipo de arbol (INDICE o EXAHUSTIVO)
- * y del tipo de clave (Longitud fija o variable).
+ * y del tipo de Clave (ClaveFija o ClaveVariable).
*
- * Los nodos que "hojas" (es decir, aquellos que no tienen hijos) no
+ * Los nodos que son "hojas" (es decir, aquellos que no tienen hijos) no
* tienen "punteros", por lo que el area de datos seria algo como :
+ *
* +--------------+--------------+--------------+--------------+
* | clave1,dato1 | clave2,dato2 | ............ | claveN,datoN |
* +--------------+--------------+--------------+--------------+
+ *
+ *
+ * El par (claveN,datoN) es representado por la clase BTreeLeafData.
*
* Ahora, los bloques intermedios tienen punteros a los hijos, y
* quedaria algo como :
+ *
* +---------+----------------------+-------+----------------------+
* | HijoIzq | clave1,dato1,HijoDer | ..... | claveN,datoN,HijoDer |
* +---------+----------------------+-------+----------------------+
+ *
+ *
+ * El puntore 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.
@@ -38,26 +59,34 @@
* juntar nodos, ya que el arbol B este es particular (Preguntar a Cerveto?).
*
*
- * TODO :
+ * \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)
*/
-#include
-#include
-#include
+#include
+#include
+#include
+#include "common.h"
+#include "clave.h"
+#include "clave_fija.h"
+#include "clave_variable.h"
+#include "btree_data.h"
/* 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 {
+ uint block_size;
+};
/** Encabezado de un bloque */
-typedef struct _btree_header_ {
+struct BTreeNodeHeader {
/** Indica a que nivel corresponde un bloque
*
* nivel == 0 : una hoja
@@ -73,48 +102,93 @@ typedef struct _btree_header_ {
/** 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 k_t Tipo de clave a utilizar
* \return Un nuevo arbol B creado o NULL en caso de error
*/
-BTree *btree_create (const char *filename, unsigned int block_size);
-
-/** 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);
-
-/** Agrega una clave en el arbol
- *
- * \TODO Definir parametros
- */
-int btree_add (BTree *);
-
-/** Borra una clave del arbol
- *
- * \TODO Definir parametros
- */
-int btree_del (BTree *);
-
-/** Cierra el arbol y libera los recursos */
-int btree_close (BTree *);
+class BTree {
+ public:
+ BTree (const std::string &filename, unsigned int block_size, int k_t = KEY_FIXED, bool create_new_file = false);
+ ~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 */
+ };
+
+ /** 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);
+
+ //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 DelKeyFromOther (const Clave &k, BTreeFindResult *r);
+ 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);
+
+ /* Funciones de Búsqueda */
+ BTreeFindResult *FindKeyR (const Clave *k, uint node);
+
+ /* Funciones de manejo de archivo */
+ void WriteFileHeader ();
+
+ /* 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 ReadKeys (uchar *node, BTreeNodeHeader &node_header);
+ void WriteKeys (uchar *node, BTreeNodeHeader &node_header, std::list &keys);
+ void DeleteKeys (std::list &keys);
+
+ std::string filename;
+ BTreeFileHeader header;
+ int key_type;
+
+ /** Apunta al archivo de datos, asi se abre solo 1 vez
+ *
+ * \todo Ver si vale la pena
+ */
+ FILE *fp;
+
+
+ /* DEBUG */
+ public:
+ void PrintNode (uint num);
+};
#endif // _B_TREE_H