From: Ricardo Markiewicz <rmarkie@fi.uba.ar>
Date: Wed, 7 Sep 2005 00:54:38 +0000 (+0000)
Subject: Agrego header inicial
X-Git-Tag: 1_0-pre1~167
X-Git-Url: https://git.llucax.com/z.facultad/75.52/treemulator.git/commitdiff_plain/5595409c0aaab1075c083f91c335acb368be51d5

Agrego header inicial
Agrego un header inicial para empezar a mover el proyecto. Defini algunas
funciones tentativas que se necesitan como API publica, estructuras de datos
tentativas y un gran comentario con documentacion de como se podria organizar
en base a lo hablado hoy.
---

diff --git a/src/btree.h b/src/btree.h
new file mode 100644
index 0000000..40261fb
--- /dev/null
+++ b/src/btree.h
@@ -0,0 +1,113 @@
+
+#ifdef _B_TREE_H
+#define _B_TREE_H
+
+/**
+ *  La estructura general del archivo seria :
+ *   +----------+----------+----------+-----+----------+
+ *   |FileHeader| Bloque 0 | Bloque 1 | ... | Bloque N |
+ *   +----------+----------+----------+-----+----------+
+ *
+ * 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).
+ *
+ * Los nodos que "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 |
+ *  +--------------+--------------+--------------+--------------+
+ *
+ * Ahora, los bloques intermedios tienen punteros a los hijos, y 
+ * quedaria algo como :
+ *  +---------+----------------------+-------+----------------------+
+ *  | HijoIzq | clave1,dato1,HijoDer | ..... | claveN,datoN,HijoDer |
+ *  +---------+----------------------+-------+----------------------+
+ *
+ * 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?).
+ *
+ *
+ * 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)
+ */
+
+/** Encabezado del archivo BTree */
+typedef struct _btree_file_ {
+	unsigned int block_sise;
+} BTreeFileHeader;
+
+/** Encabezado de un bloque */
+typedef struct _btree_header_ {
+	/** Indica a que nivel corresponde un bloque
+	 *
+	 *  nivel == 0 : una hoja
+	 *  nivel != 0 : nodo intermedio
+	 */
+	unsigned short level;
+
+	/** Espacio libre en el bloque 
+	 *
+	 *  El nodo empieza con free_space = block_size - sizeof (BTreeHeader)
+	 */
+	unsigned int free_space;
+
+	/** Cantidad de elementos en el nodo */
+	unsigned int item_count;
+} BTreeHeader;
+
+typedef struct _btree_ {
+	char *filename;
+	BTreeFileHeader 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
+ *
+ *  \param filename Nombre del archivo a crear
+ *  \param block_size Tamaño de bloque 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 *breee_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 *);
+
+#endif // _B_TREE_H
+