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         nodo->nivel = 0;
  24         nodo->cant_claves = 0;
  25
  26     /* Calculamos lo que ocupan las cadenas de bytes claves + hijos */
  27         nodo->claves = (int*)malloc(idx->size_claves);
  28         nodo->hijos = (int*)malloc(idx->size_hijos);
  29         memset(nodo->claves,-1,idx->size_claves);
  30         memset(nodo->hijos,-1,idx->size_hijos);
  31
  32     return nodo;
  33 }
  34
  35 /** Crea el archivo indice B+ */
  36 int emufs_b_plus_crear(INDEXSPECS *idx) {
  37
  38         FILE *fp;
  39         NODO_B_PLUS *raiz;
  40         int error = 0;
  41
  42         /* Creamos el archivo que contendra el indice */
  43         fp = fopen(idx->filename, "w");
  44         PERR("Creando indice con nodo raiz");
  45         if (fp == NULL) {
  46                 PERR("Error al crear el archivo");
  47                 return -1;
  48         }
  49         fclose(fp);
  50
  51         /* Creamos el nodo raiz y lo guardamos el en indice */
  52         raiz = b_plus_crearnodo(idx);
  53         error = b_plus_grabar_nodo(idx,raiz,0);
  54
  55         /* Liberamos areas de memoria reservadas */
  56         free(raiz->claves);
  57         free(raiz->hijos);
  58         free(raiz);
  59
  60         return error;
  61 }
  62
  63 /** Busca el nro de bloque donde se debe guardar un reg con clave X */
  64 int emufs_b_plus_get_bloque(INDEXSPECS *idx, INDEX_DAT *query) {
  65
  66     NODO_B_PLUS *curnode;
  67         int i, prox_nodo;
  68         /* Comienzo leyendo la raiz, entry point de toda funcion */
  69         printf ("Buscando donde insertar clave: %i\n\n",query->clave.i_clave);
  70         curnode = b_plus_leer_nodo(idx,0);
  71         if (curnode == NULL) return -1;
  72         /* Me fijo si es el primero que se inserta */
  73         if ( curnode->cant_claves == 0 ){ /* entra la clave en la raiz */
  74                 /* ojo que este es un caso muy particular */
  75                 /* aumento la cant de claves*/
  76                 curnode->cant_claves++;
  77                 /* inserto la clave en el nodo, como es la primera no hace falta ordenar nada*/
  78                 *(curnode->claves) = query->clave.i_clave;
  79                 /* Debo obtener un numero de bloque para devolverle al query!!! */
  80                 /* por ahora el nuevo bloque se va incrementando, sin recuperacion de vacios FIX*/
  81                 query->num_bloque = get_new_block_number();
  82                 /* Le asigno al nodo del arbol el mismo numero que devolvi */
  83                 *(curnode->hijos) = query->num_bloque;
  84                 /* Cargado el query salgo de la func, luego habra que actualizar el .dat
  85                    y luego volver a grabar el nodo en el arbol*/
  86                 /* librero el nodo */
  87                 free(curnode);
  88                 return 0;
  89         }
  90
  91         /* Mientras no encontre la hoja con la clave, busco.. */
  92         /* RECORDAR QUE LAS CLAVES DEBEN ESTAR ORDENADAS PARA QUE ESTO FUNCIONE !! */
  93         while (curnode->nivel > 0)
  94         {       /*recorro las claves hasta encontrar la primera mayor a la que quiero insertar*/
  95                 for(i=0; i<=curnode->cant_claves; i++){ /* ojo si la cant_claves es cero!!!!*/
  96                         /* me fijo que si es mayor */
  97                         if ( (query->clave.i_clave >= curnode->claves[i])) {
  98                                 if ( curnode->cant_claves != i ) /* si no es la ultima clave del nodo */
  99                                         continue; /*paso a la siguiente*/
 100                                 else {  /* si era la ultima, la clave deberia ir ahi */
 101                                         /*cargo el proximo nodo*/
 102                                         prox_nodo = curnode->hijos[i+1];
 103                                         break; /*salgo del for*/
 104                                 }
 105                         } else {  /*si no es mayor o igual es menor*/
 106                                 prox_nodo = curnode->hijos[i];
 107                                 break;
 108                         }
 109                 }
 110                 free(curnode);
 111                 curnode = b_plus_leer_nodo(idx, prox_nodo);
 112         }
 113         /*cuando salgo de aca deberia tener cargado en curnode el nodo hoja que busque*/
 114         for (i=0; i<=curnode->cant_claves-1; i++){
 115                 if ( query->clave.i_clave > curnode->claves[i] ){
 116                         if ( curnode->cant_claves != i ) /* si no es la ultima clave */
 117                                 continue;
 118                         else {   /* si era la ultima */
 119                                 /* cargo en query el numero del bloque donde deberia ir la nueva clave */
 120                                 query->num_bloque = curnode->hijos[i];
 121                                 free(curnode);
 122                                 return 0;
 123                         }
 124                 } else {  /* si no era mayor, era menor */
 125                         /* guardo el bloque anterior porque me pase.. */
 126                         query->num_bloque = curnode->hijos[i-1];
 127                         free(curnode);
 128                         return 0;
 129                 }
 130         }
 131
 132         free(curnode);
 133         return 0;
 134 }
 135
 136 NODO_B_PLUS *b_plus_leer_nodo(INDEXSPECS *idx, int num_node) {
 137
 138         int i = 0;
 139         FILE *fp;
 140         NODO_B_PLUS *memnode = b_plus_crearnodo(idx);
 141         char *disknode = (char*)malloc(idx->tam_bloque);
 142
 143         if (disknode == NULL) return NULL;
 144         if (memnode == NULL) return NULL;
 145
 146     /* Open up file */
 147         fp = fopen(idx->filename, "r+");
 148         if (fp == NULL) {
 149                 free(disknode);
 150                 free(memnode);
 151                 return NULL;
 152         }
 153
 154         /* Intentamos leer un nodo, sino podemos error! */
 155         fseek(fp, num_node*idx->tam_bloque, SEEK_SET);
 156         if (fread(disknode, idx->tam_bloque, 1, fp) != 1) {
 157                 free(disknode);
 158                 fclose(fp);
 159                 return NULL;
 160         }
 161         fclose(fp);
 162
 163         /* Pudimos leer un nodo de disco, ahora lo transformamos a nodo mem */
 164         memcpy(memnode,disknode,SIZE_B_PLUS_HEADER);
 165         memcpy(memnode->claves,disknode+SIZE_B_PLUS_HEADER,idx->size_claves);
 166         memcpy(memnode->hijos,disknode+SIZE_B_PLUS_HEADER+idx->size_claves,idx->size_hijos);
 167         free(disknode);
 168
 169         printf("Dumping Node_%i\n",num_node);
 170         printf("Nivel: %i  Cant Claves: %i\n",memnode->nivel,memnode->cant_claves);
 171         printf("Claves:");
 172         for (i = 0; i < idx->size_claves/sizeof(int); ++i) printf(" %i",memnode->claves[i]);
 173         printf("\nHijos:");
 174         for (i = 0; i < idx->size_hijos/sizeof(int); ++i) printf(" %i",memnode->hijos[i]);
 175         printf("\nEnd Dump\n");
 176
 177         return memnode;
 178
 179 }
 180
 181 int b_plus_grabar_nodo(INDEXSPECS *idx, NODO_B_PLUS *nodo, int num_node)
 182 {
 183         FILE *fp;
 184
 185         fp = fopen(idx->filename, "r+");
 186         if (fp == NULL) return -1;
 187
 188         fseek(fp,num_node*sizeof(NODO_B_PLUS),SEEK_SET);
 189         fwrite(nodo,SIZE_B_PLUS_HEADER,1,fp);
 190         fwrite(nodo->claves,idx->size_claves,1,fp);
 191         fwrite(nodo->hijos,idx->size_hijos,1,fp);
 192         fclose(fp);
 193
 194         return 0;
 195 }