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 la raiz esta vacia */
  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                 /*grabo el nodo en el archivo*/
  87                 b_plus_grabar_nodo(idx, &nodo, 0);
  88                 /* librero el nodo */
  89                 free(curnode);
  90                 return 0;
  91         }
  92
  93         /* Mientras no encontre la hoja con la clave, busco.. */
  94         /* RECORDAR QUE LAS CLAVES DEBEN ESTAR ORDENADAS PARA QUE ESTO FUNCIONE !! */
  95         while (curnode->nivel > 0 && curnode)
  96         {       /*recorro las claves hasta encontrar la primera mayor a la que quiero insertar*/
  97                 for(i=0; i<curnode->cant_claves; i++){
  98                         /* me fijo que si es mayor */
  99                         if ( (query->clave.i_clave > curnode->claves[i])) {
 100                                 if ( curnode->cant_claves != i ) /* si no es la ultima clave del nodo */
 101                                         continue; /*paso a la siguiente*/
 102                                 else {  /* si era la ultima, la clave deberia ir ahi */
 103                                         /*cargo el proximo nodo*/
 104                                         prox_nodo = curnode->hijos[i+1];
 105                                         break; /*salgo del for*/
 106                                 }
 107                         } else {  /*si no es mayor o igual es menor*/
 108                                 prox_nodo = curnode->hijos[i];
 109                                 break;
 110                         }
 111                 }
 112                 free(curnode);
 113                 curnode = b_plus_leer_nodo(idx, prox_nodo);
 114         }
 115
 116         /*cuando salgo de aca deberia tener cargado en curnode el nodo hoja que busque*/
 117         for (i=0; i<curnode->cant_claves-1; i++){
 118                 if ( query->clave.i_clave >= curnode->claves[i] ){
 119                         if ( curnode->cant_claves != i ) /* si no es la ultima clave */
 120                                 continue;
 121                         else {   /* si era la ultima */
 122                                 /* cargo en query el numero del bloque donde deberia ir la nueva clave */
 123                                 query->num_bloque = curnode->hijos[i];
 124                                 free(curnode);
 125                                 return 0;
 126                         }
 127                 } else {  /* si no era mayor, era menor */
 128                         /* guardo el bloque anterior porque me pase.. */
 129                         if ( i == 0 )
 130                                 /*CREAR UN NODO NUEVO PARA METER UNA CLAVE MENOR A TODAS */
 131                         else {
 132                                 query->num_bloque = curnode->hijos[i-1];
 133                                 free(curnode);
 134                                 return 0;
 135                         }
 136                 }
 137         }
 138
 139         if (curnode) free(curnode);
 140         return 0;
 141 }
 142
 143 NODO_B_PLUS *b_plus_leer_nodo(INDEXSPECS *idx, int num_node) {
 144
 145         int i = 0;
 146         FILE *fp;
 147         NODO_B_PLUS *memnode = b_plus_crearnodo(idx);
 148         char *disknode = (char*)malloc(idx->tam_bloque);
 149
 150         if (disknode == NULL) return NULL;
 151         if (memnode == NULL) return NULL;
 152
 153     /* Open up file */
 154         fp = fopen(idx->filename, "r+");
 155         if (fp == NULL) {
 156                 free(disknode);
 157                 free(memnode);
 158                 return NULL;
 159         }
 160
 161         /* Intentamos leer un nodo, sino podemos error! */
 162         fseek(fp, num_node*idx->tam_bloque, SEEK_SET);
 163         if (fread(disknode, idx->tam_bloque, 1, fp) != 1) {
 164                 free(disknode);
 165                 fclose(fp);
 166                 return NULL;
 167         }
 168         fclose(fp);
 169
 170         /* Pudimos leer un nodo de disco, ahora lo transformamos a nodo mem */
 171         memcpy(memnode,disknode,SIZE_B_PLUS_HEADER);
 172         memcpy(memnode->claves,disknode+SIZE_B_PLUS_HEADER,idx->size_claves);
 173         memcpy(memnode->hijos,disknode+SIZE_B_PLUS_HEADER+idx->size_claves,idx->size_hijos);
 174         free(disknode);
 175
 176         printf("Dumping Node_%i\n",num_node);
 177         printf("Nivel: %i  Cant Claves: %i\n",memnode->nivel,memnode->cant_claves);
 178         printf("Claves:");
 179         for (i = 0; i < idx->size_claves/sizeof(int); ++i) printf(" %i",memnode->claves[i]);
 180         printf("\nHijos:");
 181         for (i = 0; i < idx->size_hijos/sizeof(int); ++i) printf(" %i",memnode->hijos[i]);
 182         printf("\nEnd Dump\n");
 183
 184         return memnode;
 185
 186 }
 187
 188 int b_plus_grabar_nodo(INDEXSPECS *idx, NODO_B_PLUS *nodo, int num_node)
 189 {
 190         FILE *fp;
 191
 192         fp = fopen(idx->filename, "r+");
 193         if (fp == NULL) return -1;
 194
 195         fseek(fp,num_node*sizeof(NODO_B_PLUS),SEEK_SET);
 196         fwrite(nodo,SIZE_B_PLUS_HEADER,1,fp);
 197         fwrite(nodo->claves,idx->size_claves,1,fp);
 198         fwrite(nodo->hijos,idx->size_hijos,1,fp);
 199         fclose(fp);
 200
 201         return 0;
 202 }
 203
 204 int emufs_b_plus_insertar_clave(INDEX_DAT *dataset)
 205 {
 206         return 0;
 207 }