src/btree.h

   1
   2 #ifndef _B_TREE_H
   3 #define _B_TREE_H
   4
   5 /**
   6  *  La estructura general del archivo seria :
   7  *   +----------+----------+----------+-----+----------+
   8  *   |FileHeader| Bloque 0 | Bloque 1 | ... | Bloque N |
   9  *   +----------+----------+----------+-----+----------+
  10  *
  11  * Cada bloque tiene su propio encabezado siguiendo la siguiente
  12  * estructura :
  13  *   +--------------+-----------------------------------+
  14  *   | BloqueHeader | Area de Claves                    |
  15  *   +--------------+-----------------------------------+
  16  *
  17  * El area de claves depende del tipo de arbol (INDICE o EXAHUSTIVO)
  18  * y del tipo de clave (Longitud fija o variable).
  19  *
  20  * Los nodos que "hojas" (es decir, aquellos que no tienen hijos) no
  21  * tienen "punteros", por lo que el area de datos seria algo como :
  22  *  +--------------+--------------+--------------+--------------+
  23  *  | clave1,dato1 | clave2,dato2 | ............ | claveN,datoN |
  24  *  +--------------+--------------+--------------+--------------+
  25  *
  26  * Ahora, los bloques intermedios tienen punteros a los hijos, y
  27  * quedaria algo como :
  28  *  +---------+----------------------+-------+----------------------+
  29  *  | HijoIzq | clave1,dato1,HijoDer | ..... | claveN,datoN,HijoDer |
  30  *  +---------+----------------------+-------+----------------------+
  31  *
  32  * El tamaño de la clave es variable, por lo que la cantidad de claves
  33  * que puede almacenar se basa en la cantidad de espacio libre.
  34  *
  35  * Para saber si hay que romper en dos un nodo, se debe ver si la clave
  36  * a agregar entra en el espacio libre del nodo encontrado como "lugar
  37  * de insercion". Ahora, un problema a resolver es cuando se debe
  38  * juntar nodos, ya que el arbol B este es particular (Preguntar a Cerveto?).
  39  *
  40  *
  41  * TODO :
  42  *  * Ver como manejar las claves de manera transparente a las APIs de
  43  *    agregar y de borrar (EMUFS lo solucionaba bastante bien, se puede
  44  *    tomar una idea simimar)
  45  */
  46
  47 #include <stdio.h>
  48 #include <stdlib.h>
  49 #include <string.h>
  50
  51 /* alias para codear menos :) */
  52 typedef unsigned char uchar;
  53
  54 /** Encabezado del archivo BTree */
  55 typedef struct _btree_file_ {
  56         unsigned int block_size;
  57 } BTreeFileHeader;
  58
  59 /** Encabezado de un bloque */
  60 typedef struct _btree_header_ {
  61         /** Indica a que nivel corresponde un bloque
  62          *
  63          *  nivel == 0 : una hoja
  64          *  nivel != 0 : nodo intermedio
  65          */
  66         unsigned short level;
  67
  68         /** Espacio libre en el bloque
  69          *
  70          *  El nodo empieza con free_space = block_size - sizeof (BTreeHeader)
  71          */
  72         unsigned int free_space;
  73
  74         /** Cantidad de elementos en el nodo */
  75         unsigned int item_count;
  76 } BTreeHeader;
  77
  78 typedef struct _btree_ {
  79         char *filename;
  80         BTreeFileHeader header;
  81
  82         /** Apunta al archivo de datos, asi se abre solo 1 vez
  83          *
  84          *  \TODO Ver si vale la pena
  85          */
  86         FILE *fp;
  87 } BTree;
  88
  89 /** Crea un nuevo arbol B
  90  *
  91  *  \param filename Nombre del archivo a crear
  92  *  \param block_size Tamaño de bloque a utilizar
  93  *  \return Un nuevo arbol B creado o NULL en caso de error
  94  */
  95 BTree *btree_create (const char *filename, unsigned int block_size);
  96
  97 /** Abre un arbol B existente
  98  *
  99  *  \param filename Nombre del archivo a abrir
 100  *  \return El arbol abierto o NULL en caso de error
 101  */
 102 BTree *btree_open (const char *filename);
 103
 104 /** Agrega una clave en el arbol
 105  *
 106  *  \TODO Definir parametros
 107  */
 108 int btree_add (BTree *);
 109
 110 /** Borra una clave del arbol
 111  *
 112  *  \TODO Definir parametros
 113  */
 114 int btree_del (BTree *);
 115
 116 /** Cierra el arbol y libera los recursos */
 117 int btree_close (BTree *);
 118
 119 #endif // _B_TREE_H
 120