emufs/b_plus.c

   1 /** Arbol B+ */
   2 #include "b_plus.h"
   3
   4 /* Private prototypes */
   5 /* numerando los bloques */
   6 static int nuevo_bloque = -1;
   7 int get_new_block_number();
   8 int b_plus_grabar_nodo(INDEXSPECS *idx, NODO_B_PLUS *nodo, int num_node);
   9 NODO_B_PLUS *b_plus_leer_nodo(INDEXSPECS *idx, int num_node);
  10 NODO_B_PLUS *b_plus_crearnodo(INDEXSPECS *idx);
  11
  12 /** Me devuelve un numero de bloque nuevo */
  13 int get_new_block_number()
  14 {
  15         nuevo_bloque++;
  16         return nuevo_bloque;
  17 }
  18
  19 /** Crea un nuevo nodo y lo inicializa */
  20 NODO_B_PLUS *b_plus_crearnodo(INDEXSPECS *idx) {
  21
  22         NODO_B_PLUS *nodo = (NODO_B_PLUS*)malloc(sizeof(NODO_B_PLUS));
  23         if (nodo == NULL) return NULL;
  24         nodo->nivel = 0;
  25         nodo->cant_claves = 0;
  26
  27     /* Calculamos lo que ocupan las cadenas de bytes claves + hijos */
  28         nodo->claves = (int*)malloc(idx->size_claves);
  29         nodo->hijos = (int*)malloc(idx->size_hijos);
  30         memset(nodo->claves,-1,idx->size_claves);
  31         memset(nodo->hijos,-1,idx->size_hijos);
  32
  33     return nodo;
  34 }
  35
  36 /** Crea el archivo indice B+ */
  37 int emufs_b_plus_crear(INDEXSPECS *idx) {
  38
  39         FILE *fp;
  40         NODO_B_PLUS *raiz;
  41         int error = 0;
  42
  43         /* Creamos el archivo que contendra el indice */
  44         fp = fopen(idx->filename, "w");
  45         PERR("Creando indice con nodo raiz");
  46         if (fp == NULL) {
  47                 PERR("Error al crear el archivo");
  48                 return -1;
  49         }
  50         fclose(fp);
  51
  52         /* Creamos el nodo raiz y lo guardamos el en indice */
  53         raiz = b_plus_crearnodo(idx);
  54         error = b_plus_grabar_nodo(idx,raiz,0);
  55
  56         /* Liberamos areas de memoria reservadas */
  57         free(raiz->claves);
  58         free(raiz->hijos);
  59         free(raiz);
  60
  61         return error;
  62 }
  63
  64 /* Inserta un nuevo nodo y reestructura el arbol para que quede como debe */
  65 int b_plus_actualizar(NODO_B_PLUS *padre, NODO_B_PLUS *new_nodo)
  66 {
  67         return 0;
  68 }
  69
  70 /** Busca el nro de bloque donde se debe guardar un reg con clave X */
  71 int emufs_b_plus_get_bloque(INDEXSPECS *idx, INDEX_DAT *query) {
  72
  73     NODO_B_PLUS *curnode;
  74         int i, prox_nodo;
  75         /* Comienzo leyendo la raiz, entry point de toda funcion */
  76         printf ("Buscando donde insertar clave: %i\n\n",query->clave.i_clave);
  77         curnode = b_plus_leer_nodo(idx,0);
  78         if (curnode == NULL) return -1;
  79         /* Me fijo si la raiz esta vacia */
  80         if ( curnode->cant_claves == 0 ){ /* entra la clave en la raiz */
  81                 /* ojo que este es un caso muy particular */
  82                 /* aumento la cant de claves*/
  83                 curnode->cant_claves++;
  84                 /* inserto la clave en el nodo, como es la primera no hace falta ordenar nada*/
  85                 *(curnode->claves) = query->clave.i_clave;
  86                 /* Debo obtener un numero de bloque para devolverle al query!!! */
  87                 /* por ahora el nuevo bloque se va incrementando, sin recuperacion de vacios FIX*/
  88                 query->num_bloque = get_new_block_number();
  89                 /* Le asigno al nodo del arbol el mismo numero que devolvi */
  90                 *(curnode->hijos) = query->num_bloque;
  91                 /* Cargado el query salgo de la func, luego habra que actualizar el .dat
  92                    y luego volver a grabar el nodo en el arbol*/
  93                 /*grabo el nodo en el archivo*/
  94                 b_plus_grabar_nodo(idx, curnode, 0);
  95                 /* librero el nodo */
  96                 free(curnode);
  97                 return 0;
  98         }
  99
 100         /* Mientras no encontre la hoja con la clave, busco.. */
 101         /* RECORDAR QUE LAS CLAVES DEBEN ESTAR ORDENADAS PARA QUE ESTO FUNCIONE !! */
 102         while (curnode->nivel > 0 && curnode)
 103         {       /*recorro las claves hasta encontrar la primera mayor a la que quiero insertar*/
 104                 for(i=0; i<curnode->cant_claves; i++){
 105                         /* me fijo que si es mayor */
 106                         if ( (query->clave.i_clave > curnode->claves[i])) {
 107                                 if ( curnode->cant_claves != i ) /* si no es la ultima clave del nodo */
 108                                         continue; /*paso a la siguiente*/
 109                                 else {  /* si era la ultima, la clave deberia ir ahi */
 110                                         /*cargo el proximo nodo*/
 111                                         prox_nodo = curnode->hijos[i+1];
 112                                         break; /*salgo del for*/
 113                                 }
 114                         } else {  /*si no es mayor o igual es menor*/
 115                                 prox_nodo = curnode->hijos[i];
 116                                 break;
 117                         }
 118                 }
 119                 free(curnode);
 120                 curnode = b_plus_leer_nodo(idx, prox_nodo);
 121         }
 122
 123         /*cuando salgo de aca deberia tener cargado en curnode el nodo hoja que busque*/
 124         for (i=0; i<curnode->cant_claves-1; i++){
 125                 if ( query->clave.i_clave >= curnode->claves[i] ){
 126                         if ( curnode->cant_claves != i ) /* si no es la ultima clave */
 127                                 continue;
 128                         else {   /* si era la ultima */
 129                                 /* cargo en query el numero del bloque donde deberia ir la nueva clave */
 130                                 query->num_bloque = curnode->hijos[i];
 131                                 free(curnode);
 132                                 return 0;
 133                         }
 134                 } else {  /* si no era mayor, era menor */
 135                         /* guardo el bloque anterior porque me pase.. */
 136                         if ( i == 0 ){
 137                                 /*CREAR UN NODO NUEVO PARA METER UNA CLAVE MENOR A TODAS */
 138                                 /* EL NUEVO NODO VA A SER UNA HOJA */
 139                                 NODO_B_PLUS *new_nodo = b_plus_crearnodo(idx);
 140                                 if (new_nodo == NULL){
 141                                         PERR("NO SE PUDO CREAR EL NUEVO NODO");
 142                                         return -1;
 143                                 }
 144                                 /* aumento la cantidad de claves */
 145                                 new_nodo->cant_claves++;
 146                                 /* inserto la clave en el nuevo nodo (es la primera)*/
 147                                 new_nodo->claves[0] = query->clave.i_clave;
 148                                 /* inserto la referencia al nuevo bloque, con un n */
 149                                 new_nodo->hijos[0] = query->num_nuevo_bloque;
 150                                 /* no le cambio el nivel porque es hoja ( por default == 0)*/
 151                                 /* Aca viene la papota.. hay que hacer una funcion que meta un nodo
 152                                  * en el arbol y lo reestructure correctamente.
 153                                  * Ademas hay que grabar el registro en el .dat*/
 154                                 b_plus_actualizar(curnode, new_nodo);  /* le mando el padre.. seguro que lo voy a necesitar */
 155                                 return 0;
 156                         } else {
 157                                 query->num_bloque = curnode->hijos[i-1];
 158                                 free(curnode);
 159                                 return 0;
 160                         }
 161                 }
 162         }
 163
 164         if (curnode) free(curnode);
 165         return 0;
 166 }
 167
 168 NODO_B_PLUS *b_plus_leer_nodo(INDEXSPECS *idx, int num_node) {
 169
 170         int i = 0;
 171         FILE *fp;
 172         NODO_B_PLUS *memnode = b_plus_crearnodo(idx);
 173         char *disknode = (char*)malloc(idx->tam_bloque);
 174
 175         if (disknode == NULL) return NULL;
 176         if (memnode == NULL) return NULL;
 177
 178     /* Open up file */
 179         fp = fopen(idx->filename, "r+");
 180         if (fp == NULL) {
 181                 free(disknode);
 182                 free(memnode);
 183                 return NULL;
 184         }
 185
 186         /* Intentamos leer un nodo, sino podemos error! */
 187         fseek(fp, num_node*idx->tam_bloque, SEEK_SET);
 188         if (fread(disknode, idx->tam_bloque, 1, fp) != 1) {
 189                 free(disknode);
 190                 fclose(fp);
 191                 return NULL;
 192         }
 193         fclose(fp);
 194
 195         /* Pudimos leer un nodo de disco, ahora lo transformamos a nodo mem */
 196         memcpy(memnode,disknode,SIZE_B_PLUS_HEADER);
 197         memcpy(memnode->claves,disknode+SIZE_B_PLUS_HEADER,idx->size_claves);
 198         memcpy(memnode->hijos,disknode+SIZE_B_PLUS_HEADER+idx->size_claves,idx->size_hijos);
 199         free(disknode);
 200
 201         printf("Dumping Node_%i\n",num_node);
 202         printf("Nivel: %i  Cant Claves: %i\n",memnode->nivel,memnode->cant_claves);
 203         printf("Claves:");
 204         for (i = 0; i < idx->size_claves/sizeof(int); ++i) printf(" %i",memnode->claves[i]);
 205         printf("\nHijos:");
 206         for (i = 0; i < idx->size_hijos/sizeof(int); ++i) printf(" %i",memnode->hijos[i]);
 207         printf("\nEnd Dump\n");
 208
 209         return memnode;
 210
 211 }
 212
 213 int b_plus_grabar_nodo(INDEXSPECS *idx, NODO_B_PLUS *nodo, int num_node)
 214 {
 215         FILE *fp;
 216
 217         fp = fopen(idx->filename, "r+");
 218         if (fp == NULL) return -1;
 219
 220         fseek(fp,num_node*sizeof(NODO_B_PLUS),SEEK_SET);
 221         fwrite(nodo,SIZE_B_PLUS_HEADER,1,fp);
 222         fwrite(nodo->claves,idx->size_claves,1,fp);
 223         fwrite(nodo->hijos,idx->size_hijos,1,fp);
 224         fclose(fp);
 225
 226         return 0;
 227 }
 228
 229 int emufs_b_plus_insertar_clave(INDEX_DAT *dataset)
 230 {
 231         return 0;
 232 }