X-Git-Url: https://git.llucax.com/z.facultad/75.52/treemulator.git/blobdiff_plain/fbf727a8d5f7eb87843eb17720eb66e51ba1707a..57dbb7df8973a3e0c0c570c1eae9d84802e02bd9:/src/btree.h?ds=inline

diff --git a/src/btree.h b/src/btree.h
index 0ed4fbd..ef9f242 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.
+ *  
+ *  <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 :
+ *   <pre>
  *   +--------------+-----------------------------------+
  *   | BloqueHeader | Area de Claves                    |
  *   +--------------+-----------------------------------+
+ *   </pre>
  *
  * 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 :
+ *  <pre>
  *  +--------------+--------------+--------------+--------------+
  *  | 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 
  * quedaria algo como :
+ *  <pre>
  *  +---------+----------------------+-------+----------------------+
  *  | HijoIzq | clave1,dato1,HijoDer | ..... | claveN,datoN,HijoDer |
  *  +---------+----------------------+-------+----------------------+
+ *  </pre>
+ *
+ * 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,24 +59,35 @@
  * 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 <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 :) */
-typedef unsigned char uchar;
 
-/** Encabezado del archivo BTree */
-typedef struct _btree_file_ {
+/** 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;
-} BTreeFileHeader;
+};
 
 /** Encabezado de un bloque */
-typedef struct _btree_header_ {
+struct BTreeNodeHeader {
 	/** Indica a que nivel corresponde un bloque
 	 *
 	 *  nivel == 0 : una hoja
@@ -71,36 +103,103 @@ typedef struct _btree_header_ {
 
 	/** Cantidad de elementos en el nodo */
 	unsigned int item_count;
-} BTreeNodeHeader;
+};
+
+/** 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;
+};
 
-/** 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
  */
 class BTree {
 	public:
-		BTree (const char *filename, unsigned int block_size, bool create_new_file = false);
+		BTree (const std::string &filename, unsigned int block_size, int t_t = TYPE_UNIQUE, int k_t = KEY_FIXED, bool create_new_file = false);
 		~BTree ();
 
-		void AddKey ();
-		void DelKey ();
+		/** Tipos de clave a usar */
+		enum {
+			KEY_FIXED,    /**< Utilización de clave de longitud fija */
+			KEY_VARIABLE  /**< Utilización de clave de longitud variable */
+		};
 
-	private:
-		void write_tree_header ();
-		void write_block (uchar *block, uint num);
+		enum {
+			TYPE_UNIQUE,
+			TYPE_SELECTIVE
+		};
+	
+		/** 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 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 ();
+
+		/* 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;
+		int key_type;
+		int tree_type;
 
 		/** Apunta al archivo de datos, asi se abre solo 1 vez
 		 *
-		 *  \TODO Ver si vale la pena
+		 *  \todo Ver si vale la pena
 		 */
 		FILE *fp;
+
+
+		/* DEBUG */
+	public:
+		void PrintNode (uint num);
 };
 
 #endif // _B_TREE_H